systèmes de cryptage dits à clef publique

Dans un système classique, nous avons des fonctions de cryptage EK et des fonctions de décryptage DK de telle sorte que DK(EK)(T)=T pour tout texte T . Dans le système à clef privée (comme DES), DK est identique à EK ou peut s'en déduire facilement (par exemple pour DES, le déchiffrement et le chiffrement sont identiques, mais avec un ordre des sous-clefs inversé).

Ces systèmes présentent comme inconvénient de nécessiter la communication de la clef EK entre les deux correspondants, et si ceux-ci sont éloignés (par exemple s'ils correspondent par internet), la publication de la clef sera possible et rendrait le système peu sûr. Le principe des systèmes à clef publique sera de rendre la règle DK impossible à retrouver à partir de la publication de EK Ainsi il n y aura plus besoin de se préoccuper des éventuels espions qui pourraient intercepter les messages.

Chiffrement d'Elgamal

Le chiffrement d' Elgamal est basé sur le problème du logarithme discret exposé ci-dessous :

• Soit p un nombre premier, a E ZZp un entier primitif, ie d'ordre p-1, et b E ZZp*.
• Trouver l'unique c, 0<=c<=p-2 tel que a^c =b mod p.On note cet entier loga(b).

Le problème du logarithme discret est utile pour la cryptographie car le calcul de logarithmes discrets est difficile tandis que l'opération inverse d'exponentiation peut se faire efficacement avec des algorithmes appropriés.

Soit p un nombre premier tel que le problème du logarithme discret dans ZZp soit difficile, et soit a E ZZp* un élément primitif .

Soit P=ZZp*, C=ZZp*.ZZp*, et K={(p,a,c,b) : b=a^c mod p}

Les valeurs p, a, et b sont publiques et c est secret.

Pour K=(p,a,c,b) et pour un k E ZZp-1 aléatoire (secret), on définit

eK(x,k) = (y1,y2)

où y1=a^k mod p et y2 =x.b^k mod p

Pour (y1,y2) E ZZp*, on définit

dK (y1,y2) =y2(y1^c)^(-1) mod p

Autres chiffrements à clef publique

• Citons le chiffrement de Merkle-Hellman (1978) bien qu'il fut cassé dans les années 80. Ce chiffrement se base sur le problème dit du sac à dos ou de la somme de sous-ensembles. Ce problème est NP complet mais peut être résolu par des algorithmes polynomiaux dans certains cas.
• On définira alors la règle de chiffrement et de déchiffrement à l'aide d'une suite supercroissante à laquelle on appliquera les méthodes de résolution que l'on connait.