Cryptographie asymétrique¶
Note
Intercaler ce chapitre avec les chapitres d’algo arithmétique qu’il motive, par exemple : RSA, primalité, sécurité de RSA, carrés, système de Rabin, factorisation, El Gamal, logarithme discret.
Principe¶
Chaque agent possède un couple (clef publique, clef privée) de sorte que
avec la clef publique, tout le monde peut chiffrer ;
seule la clef privée peut déchiffrer un message chiffré avec la clef publique.
Avantage pratique : un couple de clefs par agent suffit pour toutes les communications, et non un couple par paire de correspondants.
Pour mettre cela en œuvre, besoin de «fonctions trappes» : faciles à calculer mais dont on ne sait pas calculer l’inverse de manière raisonnable à moins de disposer d’une information supplémentaire (la trappe).
On pourrait formaliser une définition de fonction trappe (par exemple calcul direct de complexité polynomiale, mais probabilité négligeable de calculer l’inverse pour toute machine de Turing sur une instance aléatoire). Dans tous les cas on ne sait pas démontrer l’existence d’une telle fonction, on en est réduit à choisir des problèmes réputés durs, comme la factorisation.
Quelques exemples de problèmes mathématiques donnant naissance à des fonctions trappes :
cryptosystème |
cadre |
problème simple |
problème dur |
information |
RSA |
\((\Z/n\Z)^\times\), \(n=pq\) |
puissance |
puissance inverse |
\(\phi(n)\) |
Rabin |
\((\Z/n\Z)^\times\), \(n=pq\) |
carré |
racine |
\(p\), \(q\) |
EL Gamal |
\(\F_p^\times\), \(E(\F_p)\)… |
exponentiation |
logarithme |
(pas besoin) |
NTRU, LWE |
réseau \(\Z^n\subset\R^n\) |
combinaisons |
vecteur court |
bonne base |
Mac Eliece |
code correcteur |
codage |
décodage |
structure cachée |
Le chiffrement RSA¶
Principe¶
Choisir \(p,q\) deux grands nombres premiers aléatoires.
Poser \(n=pq\)
Calculer \(\varphi(n)=(p-1)(q-1)\)
Choisir \(e\in(\Z/\phi(n)\Z)^\times\) (en général \(2^{16}+1=65537\) convient)
Calculer \(d=e^{-1}\bmod \varphi(n)\).
Alors la clef publique est constituée du couple \((n,e)\), et la clef privée du couple \((n,d)\).
Sur \(\cM=\cC=(\Z/n\Z)^\ast\), on a une application de chiffrement
et une application de déchiffrement
Remarque
On reviendra sur l’importance d’avoir de «grands» premiers «aléatoires».
Sécurité¶
Toute la sécurité de RSA est fondée sur le fait que connaissant \(n\), on ne sache pas calculer \(\varphi(n)\), ou de manière équivalente factoriser \(n\).
On considère \(N=\set{ n=pq, p<q<2p }\).
Définition
On définit la suite de problèmes
\(\pb{RSA}\): étant donné \((n,e)\) et \(c\in(\Z/n\Z)^\ast\), déterminer \(m\in(\Z/n\Z)^\ast\) tel que \(c=m^e\).
\(\pb{RSA-d}\): étant donné \((n,e)\), trouver \(d\) tel que \(ed=1\bmod \phi(n)\).
\(\pb{RSA-phi}\): étant donné \(n\), calculer \(\varphi(n)\).
\(\pb{factor}\): étant donné \(n\), factoriser \(n=p\times q\).
Pour tous problèmes \(\pb A, \pb B\), on note \(\pb A\leq \pb B\) s’il existe un algorithme polynomial qui permet de ramener la résolution d’une instance du problème \(A\) à un nombre polynomial de résolutions d’instances problème \(B\). Et on note \(\pb A = \pb B\) si \(\pb A\leq \pb B\) et \(\pb B\leq \pb A\).
Proposition
On a
Démonstration
On a d’après la description du système
Il suffit donc de montrer que \(\pb{factor}\leq \pb{RSA-d}\).
Soit donc un couple \((n,e)\) fixé. On récupère via \(\pb{RSA-d}\) un exposant \(d\) tel que \(ed=1\bmod \varphi(n)\), de sorte que \(\forall a\in\Z/n\Z\), \(a^{ed-1}=1\).
On va appliquer le lemme de factorisation, il suffit de déterminer un exposant \(m\) convenable.
Or puisque \(p,q\) sont impairs, \(e\) et \(d\) sont impairs et on écrit \(ed-1=2^r\ell\), \(2\nmid\ell\).
Puisque \((-1)^\ell=-1\) il existe un exposant \(k\) pour lequel l’exposant \(m=2^k\ell\) vérifie
\(\exists a, a^{m}=-1\)
\(\forall a, a^{2m}=1\)
Ainsi, il existe un entier \(m\) de la forme \((ed-1)/2^i\) tel que pour la moitié des \(a \bmod n\), \(\pgcd(a^m+1,n)\) est un facteur de \(n\).
En essayant plusieurs valeurs, on obtient un algorithme (probabiliste) de factorisation de \(n\).
Remarque
Le fait qu’on ait une inégalité a priori stricte \(\pb{RSA} < \pb{factor}\) est plutôt une bonne nouvelle : l’accès au déchiffrement ne permet pas de factoriser \(n\). Sinon RSA serait vulnérable aux attaques chiffré choisi.
Mise en œuvre¶
Il existe beaucoup d’attaques sur la mise en œuvre de RSA, qui doit obéir à des règles strictes.
Mentionnons un aspect essentiel : \(p\) et \(q\) doivent être vraiment aléatoires. On a de nombreux exemples de clefs vulnérables à cause de génération biaisée. Par exemple :
des nombres premiers obtenus via
nextprime(random)où random est issu d’un générateur pseudo-aléatoire de bibliothèque standard.en 2012, diverses équipes se sont amusées à calculer des \(\pgcd(n,n')\) de diverses clefs publiques collectées sur internet [LHA+12], pour constater que 0.2% des clefs reposaient sur des nombres premiers utilisés plusieurs fois. Ce qui ne devrait évidemment jamais arriver s’ils étaient choisis avec un bon aléa.
Il faut prendre garde à beaucoup de choses, en particulier
ne jamais chiffrer directement un message donné mais toujours ajouter un padding aléatoire (plus généralement, un cryptosystème à clef publique doit toujours chiffrer de manière randomisée).
avoir une implantation sécurisée : si on calcule l’exponentiation rapide de manière naturelle, on fait une multiplication de plus à chaque bit non nul de l’exposant ; mettre en œuvre des techniques d’observation de la consommation électrique ou des rayonnements émis pour deviner des bits de l’exposant de déchiffrement (side-channel attack) est plus simple que factoriser \(n\).
Cryptosystème de Rabin¶
Lemme
Soit \(p\equiv 1\bmod 4\) un nombre premier, et \(a\) un carré modulo \(p\). Alors \(a^{\frac{p+1}4}\bmod p\) est une racine carrée de \(a\) modulo \(p\).
Démonstration
On fait le calcul en isolant \(a^{\frac{p-1}2}=1\).
On peut aussi remarquer que le sous-groupe des carrés est de cardinal impair \(\frac{p-1}2\), donc la puissance \(x\mapsto x^2\) y est inversible, son inverse étant la puissance \(x\mapsto x^{\frac{p+1}4}\).
Principe¶
On choisit \(p,q\) deux grands premiers congrus à \(3 \bmod 4\), on pose \(n=pq\).
Le chiffrement est l’application carré \(m\mapsto m^2\bmod n\).
On déchiffre en calculant une racine carrée modulo \(p\) et \(q\), via le lemme chinois.
En l’état ce n’est pas un cryptosystème, puisque le chiffrement n’est pas injectif : un carré possède 4 racines carrées modulo \(n=pq\).
Ce peut être corrigé en rajoutant deux bits d’information permettant de choisir la bonne racine :
Proposition
Soit \(n=pq\) impair, l’application
est bijective de \(\Z/n\Z)^\times\) sur \(\set{\text{carrés}}\times\set{\pm1}\times\set{0,1}\).
Démonstration
Voir feuille d’exercices.
Soit \((c,s,b)\) un chiffré. Notons \(m_p = c^{\frac{p+1}4}\bmod p\) et \(m_q = c^{\frac{q+1}4}\bmod q\), ce sont des carrés modulo \(p\) et \(q\).
Alors les 4 racines carrées de \(c\) sont
\((m\mod p, m\mod q)\) |
\(\kronecker{m}{n}\) |
\(m \bmod 2\) |
\((m_p,m_q)\) |
\(1\) |
\(\epsilon_1\) |
\((-m_p,-m_q)\) |
\(1\) |
\(1-\epsilon_1\) |
\((-m_p,m_q)\) |
\(-1\) |
\(\epsilon_2\) |
\((m_p,m_q)\) |
\(-1\) |
\(1-\epsilon_2\) |
la bonne est donc déterminée par les deux bits \(s\in\set{\pm1}\) et \(b\in\set{0,1}\).
Mise en œuvre¶
On choisit \(p,q\) deux premiers congrus à \(3 \bmod 4\), on pose \(n=pq\).
La clef publique est \(n\).
La clef privée est le couple \((p,q)\).
Le chiffrement est l’application \(m\mapsto (m^2\bmod n,\kronecker{m}{n},m\bmod 2)\).
Pour déchiffrer, on calcule des racines carrée modulo \(p\) et \(q\), on recompose via le lemme chinois en choisissant parmi les 4 racines celle qui a le bon symbole de Jacobi et la bonne parité.
Sécurité¶
On définit les problèmes
\(\pb{rabin}\) : avoir accès à la fonction de déchiffrement \((m^2,\kronecker{m}{n},m\bmod 2)\mapsto m\).
\(\pb{sqrt}\) : étant donné \(n\) et \(a\) un carré modulo \(n\), en déterminer une racine carrée.
Proposition
\(\pb{factor} = \pb{rabin} = \pb{sqrt}\)
Démonstration
Si l’on a accès au déchiffrement, pour tout message \(m\), le déchiffrement de \((m^2,-\kronecker{m}{n},m\bmod 2)\) est un \(m'\) tel que \(m'\equiv \pm m\bmod p\) et \(m'\equiv \pm m\bmod q\), de sorte que \(\pgcd(m-m',n)\) vaut \(p\) ou \(q\).
Si l’on n’a accès qu’à une fonction de racine carrée, la même technique devient probabiliste : il y a deux chances sur quatre qu’une racine \(m'\) de \(m^2\) soit distincte de \(\pm m\), ce qui fournit une factorisation.
Cela montre la force du cryptosystème, mais aussi sa faiblesse puisqu’il est vulnérable aux attaques à chiffré choisi. On peut corriger ce point en restreignant l’espace des messages admissibles : par exemple en ne chiffrant que des concaténations binaires \(m|m\).
El Gamal¶
Principe¶
On choisit un groupe cyclique \(G\) d’ordre \(n\) donné par un générateur \(g\). Par exemple, \(G=\F_q^\ast\) d’ordre \(q-1\).
Alice tire aléatoirement \(a\in\Z/n\Z\) et calcule \(A=g^a\). Sa clef secrète est \(a\), sa clef publique \(A\).
Le chiffrement procède comme suit : pour tout message \(m\), on tire un exposant \(r\) aléatoirement dans \(\Z/n\Z\), et on transmet le chiffré
Pour déchiffrer un message \((R,M)\) de la forme ci-dessus, on calcule
Sécurité¶
Soit \(G=\langle g\rangle\) un groupe cyclique. On définit les problèmes
\(\pb{ElGamal}\) : étant donnés \((g^a, g^r)\in G^2\), calculer \(g^{ar}\) ;
\(\pb{Log}\) : étant donné \(g^a\), calculer \(a\).
Le problème El Gamal est équivalent à savoir déchiffrer les messages (sans connaissance de la clef privée), le problème du Log discret est équivalent à retrouver la clef privée.
On a en particulier
On ne sait rien faire dans l’autre sens.
Groupes utilisés¶
\(\F_p^\times\), pour \(p\) premier. On choisit en pratique un nombre premier \(p\) de Sophie Germain, c’est-à-dire tel que \(p=2q+1\) pour \(q\) premier, de sorte que l’ordre \(p-1\) se factorise le moins possible (cf. décomposition en restes chinois).
\(\F_q^\times\) pour \(q=p^e\). En pratique il faut éviter les petites valeurs de \(p\), car on a de bons algorithmes de calcul de logarithme discret dans ce cadre.
\(E(\F_p)\) où \(E\) est une courbe elliptique d’équation \(y^2=x^3+ax+b\) (pour des coefficients \(a,b\in\F_p\) tels que \(p\nmid 4a^3+27q^2\)), c’est-à-dire l’ensemble
\[E(\F_p) = \set{(x,y),y^2=x^3+ax+b}\cup\set{\infty}\]muni de la loi d’addition «corde et tangente» : si \(P=(x_P,y_P)\) et \(Q=(x_Q,y_Q)\) sont deux points, la droite passant par \(P\) et \(Q\) intersecte la courbe en un troisième point \(R=(x_R,y_R)\). On pose \(P\oplus Q=\ominus R=(x_R,-y_R)\).
Alors \((E(\F_p),\oplus)\) est un groupe abélien d’élément neutre \(\infty\).
En outre,
\(p+1-2\sqrt p\leq \#E(\F_p)\leq p+1+2\sqrt p\) (Théorème de Hasse)
pour tout \(p\), et pour tout \(n\) dans l’intervalle ci-dessus, il existe des courbes elliptiques de cardinal \(n\). En particulier il existe des courbes de cardinal un nombre premier (pour lesquelles \(E(\F_p)\) est cyclique et robuste du point de vue de la décomposition en restes chinois)