Systèmes modernes à clé publique
0. Genèse des systèmes à clef publique
Généralités
Stéganographie
Cryptanalyse
Littérature
Transpositions
Subs. monoα
Subs. polyα 1 - 2
One-time pad
DES 1 - 2
Clef publique
inconvénients de la clef secrète
calculs faciles et difficiles
fonctions à sens unique
sans trappe
avec trappe
fonctions de hachage
Knapsack
Diffie-Hellman
RSA 1 - 2
Grands noms
Références
Inconvénients de la clef secrète
Quelle que soit la valeur des algorithmes de cryptage, les systèmes a clef secrète ont un handicap incontournable. La clef doit être détenue par le chiffreur et le déchiffreur. Sa distribution (ou son partage) exige un canal de transmission distinct de celui par lequel vont transiter les messages (mais d'une sécurité au moins égale).Disposer d'un tel canal a un coût. Il est dans les moyens d'un gouvernement, encore supportable pour une grande société. Mais il est bien sûr inaccessible aux personnes privées. Jusqu'au début des années 70, un organisme dédié, la COMSEC [1] était chargé de l'acheminement des clefs cryptographiques vers leurs destinataires. Celles-ci transitaient par bateaux entiers sous des formes diverses (cartes perforées, disquettes, rouleaux de papier). Des "crypto-gardiens" veillaient jalousement sur le chargement et le déchargement.
Il y a autre chose que les algorithmes à clef secrète ne savent pas faire : l'authentification. Si l'on suppose qu'Eve a intercepté ou cryptanalysé la clef secrète par laquelle Alice et Bob communiquent, ceux-ci n'ont aucun moyen de distinguer les messages authentiques (les leurs) des faux élaborés par leur ennemi.
Jusqu'au milieu des années 70, on ne connaissait que les systèmes à clef secrète.
L'idée des systèmes à clef publique est apparue comme une réponse à ces inconvénients. Dans un système asymétrique (à clefs publique et privée), n'importe qui peut chiffrer à l'attention du destinataire à l'aide de sa clef publique. (Il n'est même pas nécessaire de le connaître.)
Lorsqu'en 1976 Whitfield Diffie et Martin Hellman ont annoncé leur protocole public d'échange de clef, ils ont ouvert de nouvelles perspectives en cryptographie.
Les recherches portaient alors sur la création d'une paire de fonctions : publique, P, et secrète, S, impossible à déduire de la précédente en pratique.
Calculs faciles et difficiles
Dans la pratique, il est utile de distinguer entre deux types d'algorithmes.- les algorithmes en temps polynomial (classe P) demandent un nombre T(d) d'opérations majoré par une puissance constante de la taille d des données : T(d) ≤ Kdα, ou T(d) = O(dα). Par exemple :
- l'addition de deux entiers de d bits, la recherche d'un élément dans un tableau de longueur d sont en O(d) (linéaires) ;
- la multiplication naïve de deux entiers de d bits, les tris naïfs (bulle, Shell) d'un tableau de longueur d sont en O(d2) (quadratiques) etc.
- les algorithmes en temps non polynomial (classe NP) exigent un nombre d'opérations T(d) qui augmente plus vite que n'importe quelle puissance de la taille d des données. Par exemple :
- le test naïf de primalité d'un entier n de d bits (en testant tous les facteurs jusqu'à √n̅) est en O(√n̅) = O(exp(d/2)) (exponentiel) [2] ;
- la recherche d'un chemin hamiltonien (passant par tous les nœuds) d'un graphe à d sommets ;
- la factorisation d'un entier n de d bits -- le plus important en cryptographie.
Fonctions à sens unique
Le passage du clair M au chiffré C est assuré par la fonction de cryptage F de l'espace des clairs ℳ dans l'espace des chiffrés 𝒞. F doit être injective : un même chiffré ne peut provenir de deux clairs distincts, sous peine de rendre impossible le déchiffrage [3]. F est alors une bijection de ℳ sur 𝒞 ' = F⟨ℳ⟩. Par abus de langage, nous notons encore F : ℳ → 𝒞 '.Mathématiquement, G = F−1 est parfaitement définie. Cependant, algorithmiquement, il se peut que la fonction F soit facile à calculer. C'est le cas si elle résulte d'un algorithme en temps polynomial (de la classe P). Il n'en va pas forcément de même pour la fonction G qui peut être difficile à calculer, se situant dans la classe NP.
On parle alors de fonction à sens unique (one-way function). Cette idée a émergé avant même que de telles fonctions soient mises en évidence. On en distingue deux catégories.
sans trappe
Dans une fonction à sens unique sans trappe F, l'inversion est inconditionnellement difficile :| M |
F (facile) ⇄ G (difficile [*]) |
C |
[*] où "difficile" signifie : difficile pour presque tous les éléments de l'image de F.
exemple : le logarithme discret
Soit p∈ℙ un nombre premier. Soit α un élément non nul (donc inversible) du corps 𝔽p = ℤ/pℤ. On considère l'exponentielle modulaire de base α :|
F : 𝔽p* → 𝔽p*; x ↦ αx (mod. p). |
Il n'existe pas aujourd'hui d'algorithme efficace (en temps polynomial) pour trouver x connaissant F(x). C'est le problème du logarithme discret. Il est à la base du protocole de Diffie-Hellman.
avec trappe
Dans cette situation, la fonction F contient un paramètre (trappe). Si l'on connaît celui-ci, F s'inverse facilement. Sans cette trappe, F se comporte comme dans le cas précédent.| M |
F (facile) ⇄ G (difficile [*] sans la trappe) |
C |
(Même remarque en ce qui concerne le sens de "difficile".)
exemple
Soit n un entier composé mais "presque premier" : n = pq avec p, q∈ℙ. On rappelle que φ(n), l'indicateur d'Euler de n, vaut dans ce cas φ(n) = (p−1)(q−1). On considère, pour un e "judicieux" -- voir ci-après -- la fonction puissance e modulaire :| F(x) = xe (mod. n). |
On montre :
Proposition :
1) Si e∧φ(n) = 1 (e est premier avec φ(n)), F est une bijection de ℤ/nℤ ;
2) G = F−1 est de la forme G(y) = yd (mod. n) où ed = 1 mod. φ(n).
e et n sont connus ; d (ou p et q) est secret (on peut montrer que : connaître d ⇔ connaître p et q).
On ne connaît pas d'algorithme efficace pour trouver p et q connaissant e et n -- à moins de se situer dans un cas trivial, nous y reviendrons.
En effet, ce problème de factorisation est au cœur du système RSA.
Fonctions de hachage
Une autre catégorie de fonctions "presque inversibles" intervient dans le protocole RSA lorsqu'il s'agit d'authentifier des messages.On souhaite "signer" un message de ℓ bits (disons ℓ ≃ 106) en lui ajoutant une "signature" sur k bits (disons k ≃ 103). Mathématiquement, aucune application de {0, 1}ℓ dans {0, 1}k ne peut être injective (puisque 2ℓ > 2k).
Mais, algorithmiquement, on peut concevoir une fonction H : {0, 1}ℓ → {0, 1}k "presque injective" dans le sens suivant :
- H(x) est facile à calculer (en temps polynômial) pour tout x∈{0, 1}ℓ ;
- Étant donné y∈Im(H), il est difficile de trouver x∈{0, 1}ℓ tel que y = H(x)
(résistance au premier antécédent) ;
- Étant donné x∈{0, 1}ℓ il est difficile de trouver x'∈{0, 1}ℓ tel que H(x) = H(x')
(résistance au deuxième antécédent) ; - Il est difficile de trouver x, x' aléatoirement tels que H(x) = H(x')
(résistance aux collisions)
- H soit impossible à distinguer d'une fonction aléatoire.
Vous rencontrez de telles fonctions chaque fois que vous calculez l'empreinte MD4 ou MD5 d'une archive téléchargée, afin de vérifier son intégrité [4].
Nous verrons à l'occasion du RSA comment une bonne fonction de hachage, associée à un chiffrage asymétrique, permet la signature ou l'authentification des messages.
Notes
[1] COMmunication SECurity[2] Toutefois, en 2002, 3 mathématiciens indiens ont montré que le problème du test de primalité appartenait à la classe P ("Primes is in P")
[3] Elle n'est peut-être pas surjective (s'il existe des chiffrés qui ne correspondent à aucun clair).
[4] Malheureusement, MD4 et MD5, fonctionnant sur 128 bits, sont cassées, de même que leurs successeurs SHA-0 et SHA-1 (160 bits). La sécurité procurée par SHA-256 et SHA-512 semble précaire, et un concours a été lancé par le NIST pour désigner la nouvelle norme SHA-3. Le résultat a été publié le 2/10/2012. L'algorithme vainqueur s'appelle Keccak ; il est dû à un Italien et trois Belges [lien]