Chiffrement de ElGamal

Le chiffrement de ElGamal est une technique cryptographique asymétrique voisine de la technique RSA vue en Terminale NSI, mais plus simple.

Cette technique, comme RSA, basée sur des propriétés arithmétiques – mathématiques des nombres entiers – fait un grand usage des puissances et des modulos.

Vous pouvez donc consulter l'intérêt des modulos en cryptographie

Vous devrez aussi passer voir ces deux exercices avant :

• exponentiation rapide
• Inverse modulaire

Vous aurez besoin des fonctions puissance_rapide_mod et inverse_modulaire implémentées dans ces deux exercices.

Comme dit précédemment, il s'agit d'un chiffre asymétrique. Il y aura donc une clé publique Kpu pour le chiffrement et une clé privée Kpr pour le déchiffrement.

Voici comment Bob va créer ces clés :

• Bob choisit un nombre premier $p$ assez grand – plus il est grand, plus c'est sûr.
• il choisit un entier $1 < d < p$,
• il choisit un entier $1 < s$, ce sera sa clé privée,
• il calcule $h \overset{p}{\equiv} d^s$.

La clé publique de Bob est composé du triplet $(p, d, h)$. Il peut la transmettre en clair.

Alice veut transmettre un nombre $m$, c'est son message. Elle a reçu les trois morceaux de la clé de Bob.

• Alice choisit un nombre entier $1 < a$ comme elle veut,
• Elle calcule $r \overset{p}{\equiv} m\cdot h^a$ et $t \overset{p}{\equiv} d^a$
• Elle envoie le message chiffré composé des deux morceaux : $(r, t)$

Bob reçoit $(r, t)$, il peut utiliser $s$ qu'il est seul à connaître,

• il calcule $t^s \mod p$,
• il cherche l'entier $u$ qui vérifie $u\cdot t^s \overset{p}{\equiv} 1$
  $u$ est l'inverse modulaire de $t^s$,
• il calcule $m' \overset{p}{\equiv} r \cdot u$, le résultat $m'$ n'est autre que $m$.

Un mot d'explication :

• $t^s \overset{p}{\equiv} \left(d^a\right)^s = d^{a\cdot s} = \left(d^s\right)^a \overset{p}{\equiv} h^a$
• donc $r \overset{p}{\equiv} m \cdot h^a \overset{p}{\equiv} m \cdot t^s$
• et donc enfin $r\cdot u \overset{p}{\equiv} \left(m \cdot t^s\right) \cdot u \overset{p}{\equiv} m \cdot \left(t^s \cdot u\right) \overset{p}{\equiv} m \cdot 1 \overset{p}{\equiv} m $.