====== Chiffrement de ElGamal ======

Le [[https://fr.wikipedia.org/wiki/Cryptosyst%C3%A8me_de_ElGamal|chiffrement de ElGamal]] est une technique cryptographique asymétrique voisine de la technique [[nsi:terminales:securite:rsa|RSA]] vue en Terminale NSI, mais plus simple.

{{page>..:chiffrement_symetrique_asymetrique#Chiffre Symétrique / Asymétrique&noheader}}

===== Calculs modulo =====

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 [[nsi:terminales:chiffrement_modulo|l'intérêt des modulos en cryptographie]]

Vous devrez aussi passer voir ces deux exercices avant :
  * [[nsi:tds:cryptographie:exponentiation_modulaire|exponentiation rapide]]
  * [[nsi:tds:cryptographie:inverse_modulaire|Inverse modulaire]]

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

<WRAP important>Je noterai ci-dessous $\cdots\overset{p}{\equiv}\cdots$ pour $\cdots = \cdots \mod p$.
</WRAP>

===== Principe du chiffre de ElGamal =====

==== Clés ====

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.

<WRAP tip>
L'idée est que $s$ sera utile au calcul de déchiffrement et que $s$ est difficile à trouver quand on ne connaît que $(p, d, h)$. Vous pouvez consulter [[nsi:terminales:chiffrement_modulo|cette page]] pour comprendre mieux pourquoi.
</WRAP>

==== Chiffrement ====

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

==== Déchiffrement ====

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'[[nsi:tds:cryptographie:inverse_modulaire|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 $.

<WRAP tip>
Comme vous le voyez, le déchiffrement exploite le fait que calculer $a^b \mod p$ est très rapide. Connaissant $s$, les calculs à faire pour déchiffrer sont rapides.

En connaissant la clé publique $(p, d, h)$, on pourrait trouver la valeur de $s$ mais cela nécessiterait beaucoup de calculs et donc beaucoup de temps. En gros il faudrait essayer toutes les valeurs entre 1 et $p$ ce qui serait long pour un $p$ très grand.</WRAP>

<WRAP box>
===== À faire =====

Vous disposes déjà des fonctions :
  * ''%%puissance_rapide_mod(a,b,q)%%'' vue dans [[nsi:tds:cryptographie:exponentiation_modulaire|Exponentiation modulaire]]
  * ''%%inverse_modulaire(a,p)%%'' vue dans [[nsi:tds:cryptographie:inverse_modulaire|Inverse modulaire]]

Pour le choix de ''a'' lors du chiffrement, vous pouvez générer un entier aléatoire par exemple avec ''randrange'' du module ''random''.

Écrire de plus les fonctions suivantes :

  * ''%%calculer_cle_publique(Kpr)%%'' qui reçoit ''%%Kpr = (p, d, s)%%'' et renvoie ''%%Kpu = (p, d, h)%%''
  * ''%%chiffrer(m, Kpu)%%'' qui reçoit le message ''m'' et la clé publique ''Kpu'' et renvoie la paire ''%%mc = (r, t)%%'' du message chiffré
  * ''%%dechiffrer(mc, Kpr)%%'' qui reçoit le message chiffré et la clé privée et renvoie le message déchiffré..

Faire le test en choisissant ''%%Kpr(7639, 59, 13), m = 253%%''.
</WRAP>