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 $.