Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 09-12-2015 06: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 :)

#2 09-12-2015 09:59:42

Rossignol
Membre
Inscription : 19-06-2015
Messages : 189

Re : Signature El Gamal

Bonjour Didi

Il suffit de lire le corrigé (exercice 3).

:-))

Hors ligne

#3 10-12-2015 03:31:41

Didi
Invité

Re : Signature El Gamal

Bonsoir,

MERCI infiniment pour le lien.

:D :D :D

Bonne soirée.

#4 09-10-2019 23: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 15:34:38

Rossignol
Membre
Inscription : 19-06-2015
Messages : 189

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

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
trente huit plus trente et un
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums