Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 09-12-2015 07:40:47
- Didi
- Invité
Signature El Gamal
Bonjour à tous,
j'étais à la recherche d'exercices traitant de la signature d'El Gamal et j'ai trouvé un exercice assez intéressant.
Le problème c'est que je n'arrive pas à le résoudre, je ne sais même pas par où commencer. Alors toute aide sera la bienvenue.
Voici donc l'énoncé:
On suppose que le chiffrement de El-Gamal est utilisé sans vérifier si 0 < r < p. On
suppose que l’attaquant connaît la signature (r, s) d’un message m. Soit m′ un message
arbitraire et s′ =sα avec α=H(m′)*H(m)^(-1) mod p-1
a) Trouver deux équations vérifiées par r′ ( l’une modulo p et l’autre modulo p − 1)
telles que (r′, s′) soit une signature de m′.
b) Comment peut on résoudre ces équations?
Merci d'avance :)
#3 10-12-2015 04:31:41
- Didi
- Invité
Re : Signature El Gamal
Bonsoir,
MERCI infiniment pour le lien.
:D :D :D
Bonne soirée.
#4 10-10-2019 00:09:54
- Fed
- Invité
Re : Signature El Gamal
Bonjour svp j’ai le même problème et malheureusement le lien ne marche plus
La solution svp
#5 13-10-2019 16:34:38
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 290
Re : Signature El Gamal
Bonjour,
Je vais encore me faire agonir d'injures par le prof qui a donné l'exercice :-)
Protocole de signature d'Elgamal :
Protocole défini par Taher Elgamal en 1985.
Génération des clés :
Le signataire choisit un nombre premier $p$, un générateur $g$ du groupe multiplicatif $\mathbb{Z}/p\mathbb{Z}^*$ et une fonction de hachage $H$ à valeurs dans $\mathbb{Z}/(p-1)\mathbb{Z}$ (autrement dit, pour un message $m$, on a $H(m)\in \mathbb{Z}/(p-1)\mathbb{Z})$.
Il tire au hasard uniformément un $x\in\mathbb{Z}/(p-1)\mathbb{Z}$ et calcule $y = g^x\mod p$.
La clé publique est $(p, g, H, y)$.
La clé privée secrète est $x$.
Signature d'un message :
Pour signer un message $m$, le signataire tire au hasard uniformément $k\in \mathbb{Z}/(p-1)\mathbb{Z}^*$ et calcule $r\equiv g^k\mod p$, puis $s\equiv (H(m)-xr)k^{-1}\mod p-1$
La signature du message $m$ est alors le couple ($r, s)$.
Vérification de la signature :
On peut vérifier, en n'utilisant que la clé publique, si $(r, s)$ est une signature valide du message $m$.
La signature est valide si $g^{H(m)} \equiv y^r r^s \mod p$
En effet, on a facilement :
$$y^r r^s \equiv (g^x)^r(g^k)^s \equiv g^{xr}g^{ks} \equiv g^{xr+ks}\equiv g^{xr+k(H(m)-xr)k^{-1}}\equiv g^{H(m)} \mod p$$
Le problème
L’attaquant connaît la signature $(r, s)$ d’un message $m$.
Soit $m′$ un message arbitraire et $s′ =s\alpha$ avec $\alpha=H(m′)H(m)^{-1} \mod p-1$
$$g^{H(m^\prime)} \equiv g^{\alpha H(m)} \equiv (g^{H(m)})^\alpha \equiv (y^r r^s)^\alpha
\equiv y^{\alpha r} r^{\alpha s} \equiv y^{\alpha r} r^{s^{\prime}} \mod p$$
Pour que $(r', s')$ soit une signature valide de $m'$ il faut que
$$g^{H(m^{\prime})} \equiv y^{r^{\prime}} {r^{\prime}}^{s^{\prime}} \mod p$$
ce qui donne la condition
$$y^{r^{\prime}} {r^{\prime}}^{s^{\prime}} \equiv y^{\alpha r} r^{s^{\prime}} \mod p$$
et par identification, le système
$$\left\{ \begin{array}{l}
r^{\prime} \equiv \alpha r \mod p-1\\
r^{\prime} \equiv r \mod p
\end{array}\right.$$
(Attention pour l'identification, les exposants sont définis modulo $p-1$ en vertu du p'tit théorème de Fermat $n^{p-1}\equiv 1 \mod p$.)
Comme $p$ est premier, $p$ et $p-1$ sont premiers entre eux. Le théorème des restes chinois permet d'affirmer qu'il existe une unique solution $r^{\prime}$ du système modulo $p(p-1)$.
L'attaquant a forgé une signature $(r^{\prime}, s^{\prime})$ du message $m^\prime$ qui vérifie la condition $g^{H(m^{\prime})} \equiv y^{r^{\prime}} {r^{\prime}}^{s^{\prime}} \mod p$.
Seulement $r^\prime$ n'est pas dans $\mathbb{Z}/p\mathbb{Z}$; c'est ce qui permet de rejeter cette fausse signature.
Puisque $r^{\prime} \equiv r \mod p$, il existe un entier naturel $n$ tel que $r^\prime = r+np$ (on a clairement $r^\prime \geqslant r$).
On ne peut pas avoir $n=0$ car alors $r^\prime=r \Rightarrow \alpha = 1 \Rightarrow H(m′)=H(m) \Rightarrow m^\prime = m$ (si on a une bonne fonction de hachage)
De $n>0$ et $r^\prime = r+np$, on déduit $r^\prime \geqslant p$.
Conclusion : la signature $(r, s)$ est une signature valide du message $m$ si
$$0<r<p ~~~~\textrm{ et }~~~~ g^{H(m)} \equiv y^r r^s \mod p$$
La sécurité de ce protocole de signature est basée sur la difficulté du problème du logarithme discret : on ne connaît pas d'algorithme rapide qui donne $x$ pour l'équation $y \equiv g^x \mod p$ si $p$ est assez grand et si $p-1$ n'est pas friable.
@+
Hors ligne
Pages : 1