Cryptosystème de Rabin

Le cryptosystème de Rabin est un cryptosystème asymétrique basé sur la difficulté du problème de la factorisation (comme RSA). Il a été inventé en 1979 par Michael Rabin : c'est le premier cryptosystème asymétrique dont la sécurité se réduit à la difficulté calculatoire de la factorisation d'un nombre entier.

Le cryptosystème de Rabin a l'avantage de disposer d'une preuve de difficulté aussi grande que la factorisation d'entiers, preuve qui n'existe pas encore pour RSA. Il a par contre un désavantage dû à un non-déterminisme : une sortie produite par la fonction présente dans le cryptosystème peut être le résultat de quatre entrées distinctes. Il faut donc déterminer quelle entrée est la bonne par un mécanisme annexe.

Génération de clés

Comme pour tous les algorithmes de cryptographie asymétrique, le cryptosystème de Rabin fait usage d'une clé publique et d'une clé privée. La clé publique est utilisée pour chiffrer et n'est pas secrète, tandis que la clé privée est secrète et ne doit être connue que de son propriétaire: le destinataire du message (afin qu'il soit le seul à pouvoir déchiffrer).

La génération de clés est effectuée comme suit:

• Choisir deux grands nombres premiers, $p$ et $q$, au hasard, de telle sorte que $p\equiv q\equiv 3\mod 4$. Ils constituent la clé privée.
• Calculer $n=p\cdot q$ (autrement dit, $n$ est un entier de Blum). Choisir un entier $B$ inférieur à $n$. Le couple $(n,B)$ constitue la clé publique.

Pour chiffrer, on n'a besoin que de la clé publique, $(n,B)$. Pour déchiffrer il est nécessaire de connaître $p$ et $q$ les facteurs de $n$.

Chiffrement

Pour le chiffrement, seule la clé publique, $(n,B)$, est utilisée. On produit le texte chiffré à partir du texte en clair $m$ comme suit.

Soit $P=\{0,...,n-1\}$ l'espace des textes en clair possibles (tous des nombres) et posons $m\in P$ comme étant le texte en clair. Le texte chiffré $c$ se détermine comme suit:

$c=m(m+B)\,{\bmod {\,}}n$

En pratique du chiffrement par bloc est généralement utilisé.

Déchiffrement

Le message clair $m$ est solution de l'équation du second degré $x(x+B)\equiv c\mod n$ qui équivaut à résoudre $x^{2}+Bx-c\equiv 0\mod n$. Si l'on est capable de calculer des racines carrées modulo $n$, la méthode de résolution est semblable à celle utilisée pour des nombres réels. Cependant calculer efficacement une racine carrée modulo $n$ nécessite de savoir factoriser $n$ en produit de facteurs premiers. Pour déchiffrer, la clé privée est donc nécessaire. Le processus est comme suit.

De façon analogue aux équations du second degré dans le cas réel, $m$ est égal à l'un des nombres s'écrivant $(-B-\delta ){\dot {2}}^{-1}\mod n$ où $\delta$ est une des quatre racines carrées modulo $n$ du discriminant $\Delta =B^{2}+4c$ et où ${\dot {2}}^{-1}$ est l'inverse modulaire de 2 modulo $n$, que l'on peut calculer efficacement à l'aide de l'algorithme d'Euclide étendu.

Les quatre racines carrées de $\Delta$ sont calculées efficacement en connaissant la clé privée $(p,q)$ et en utilisant les propriétés des entiers de Blum : $\delta \equiv \pm \Delta ^{\frac {p+1}{4}}\mod p$ et $\delta \equiv \pm \Delta ^{\frac {q+1}{4}}\mod q$ ; il reste alors juste à déterminer $\delta$ modulo $n$ à l'aide du théorème des restes chinois.

Comme $m=(-B-\delta ){\dot {2}}^{-1}\mod n$ et que l'on a calculé ${\dot {2}}^{-1}$ et les quatre valeurs possibles de $\delta$, il ne reste plus qu'à déduire les quatre valeurs possibles de $m$ et de se servir du contexte pour déduire laquelle correspond au message envoyé. En d'autres termes, la fonction de chiffrement n'est pas injective même restreinte à des entiers inférieurs à $n$. C'est un inconvénient qui rend délicate l'automatisation du déchiffrement.

Preuve de sécurité de l'algorithme

Contrairement au chiffrement RSA, il est prouvé que l'on ne peut pas retrouver un message clair $m$ à partir du message chiffré $c$ correspondant sans être capable de retrouver les facteurs premiers $p$ et $q$ du module $n$ de la clé publique. Comme la factorisation de grands nombres entiers est en 2023 considérée comme un problème calculatoirement difficile par la communauté des cryptographes, il s'ensuit que la cryptanalyse du chiffrement de Rabin l'est aussi. Cela pourrait changer si des ordinateurs quantiques sont mis au point car alors il serait possible d'implémenter l'algorithme de Shor qui lui factorise efficacement les nombres entiers.

On montre que retrouver les quatre messages clairs $m_{1},m_{2},m_{3},m_{4}$ possibles à partir du chiffré $c$ implique de savoir factoriser $n$. Il est facile de calculer $\Delta =B^{2}+4c$ à partir du chiffré $c$ et il est facile de calculer les valeurs de $\delta _{i}=B-2m_{i}$ à partir des valeurs de $m_{i}$ (pour $i$ allant de 1 à 4). On peut donc associer un nombre, $\Delta$ et ses quatre racines carrées modulo $n$.

On peut choisir deux de ces quatre racines $\delta _{1}$ et $\delta _{2}$ qui vérifient $\delta _{1}\not \equiv -\delta _{2}\mod n$. On a alors $\delta _{1}^{2}-\delta _{2}^{2}\equiv 0\mod n$, c'est-à-dire par différence de deux carrés $(\delta _{1}+\delta _{2})(\delta _{1}-\delta _{2})\equiv 0\mod n$ où $\delta _{1}+\delta _{2}\not \equiv 0\mod n$ et $\delta _{1}-\delta _{2}\not \equiv 0\mod n$. Autrement dit, ni $\delta _{1}+\delta _{2}$ ni $\delta _{1}-\delta _{2}$ ne sont des multiples de $n$ mais leur produit l'est. Il s'ensuit que $p$ divise $\delta _{1}+\delta _{2}$ et $q$ divise $\delta _{1}-\delta _{2}$.

Le PGCD de $n$ et $\delta _{1}-\delta _{2}$ est donc égal à $q$ : on peut le trouver efficacement à l'aide de l'algorithme d'Euclide et de là déduire l'autre facteur $p$ de $n$ : être capable de trouver les clairs possibles correspondant à un message chiffré donné implique d'être capable de factoriser l'entier utilisé comme clé publique.

Exemple d'exécution

Génération de la clé publique et de la clé privée

Les nombres $p$ et $q$ choisis doivent être suffisamment grands pour qu'une factorisation de $pq$ ne soit pas envisageable. À titre d'exemple on choisira cependant ici $p$ = 7 et $q$ = 11, qui sont bien tous les deux congrus à 3 modulo 4. En plus de cela, on choisit par exemple $B$ = 28, la clé publique est donc (77,28) et la clé privée correspondante est (7,11).

Chiffrement du message

$n$ = 77 donc $\{0,...,76\}$ est l'espace des textes en clair possibles. On choisit par exemple $m=20$ comme texte en clair. Seule la clé publique $(n=77,B=28)$ est nécessaire pour chiffrer.

Le texte chiffré est alors $c\equiv m(m+B)\,{\bmod {\,}}n\equiv 20\times 48{\bmod {7}}7\equiv 1120\,{\bmod {\,}}77\equiv 36{\bmod {7}}7$.

Remarque

Le texte chiffré 36 est produit pour quatre différentes valeurs de m, soit $m\in \{20,29,62,64\}$. Ceci est le maximum du nombre d'antécédents possibles pour un même message chiffré, et cette situation se produit pour la plupart des textes chiffrés produits par l'algorithme de Rabin.

Déchiffrement

En poursuivant l'exemple précédent, le destinataire reçoit le message chiffré 36. Il connait le nombre $B=28$ qui est public ainsi que le clé privée $(p=7,q=11)$. Le déchiffrement s'effectue comme suit :

• Le message en clair $m$ est solution de l'équation $x^{2}+28x-36\equiv 0\mod 77$.
  • Son discriminant vaut $\Delta \equiv 28^{2}-4\times (-36)\equiv 928\equiv 4\mod 77$.
  • $\Delta$ a quatre racines carrées $\delta$ vérifiant $\delta \equiv \pm 4^{\frac {7+1}{4}}\equiv \pm 2\mod 7$ et $\delta \equiv \pm 4^{\frac {11+1}{4}}\equiv \pm 9\mod 11$ (car $n$ est un entier de Blum)
• En appliquant le théorème des restes chinois, on déduit les quatre valeurs possibles de $\delta$ :
  • $\delta _{1}\equiv 2\mod 7$ et $\delta _{1}\equiv 9\mod 11$ correspond à $\delta _{1}\equiv 9\mod 77$
  • $\delta _{2}\equiv 2\mod 7$ et $\delta _{2}\equiv -9\mod 11$ correspond à $\delta _{2}\equiv 2\mod 77$
  • $\delta _{3}\equiv -2\mod 7$ et $\delta _{3}\equiv 9\mod 11$ correspond à $\delta _{3}\equiv 75\mod 77$
  • $\delta _{4}\equiv -2\mod 7$ et $\delta _{4}\equiv -9\mod 11$ correspond à $\delta _{4}\equiv 68\mod 77$
• ${\dot {2}}^{-1}=39$ car $2\times 39\equiv 1\mod 77$ (obtenu à l'aide de l'algorithme d'Euclide étendu)
• Les quatre valeurs possibles de $m$ sont les valeurs $m_{i}=(-B-\delta _{i}){\dot {2}}^{-1}$ avec $i\in \{1,2,3,4\}$
  • $m_{1}\equiv (-28-9)\cdot 39\equiv 20\mod 77$
  • $m_{2}\equiv (-28-2)\cdot 39\equiv 62\mod 77$
  • $m_{3}\equiv (-28-75)\cdot 39\equiv 64\mod 77$
  • $m_{4}\equiv (-28-68)\cdot 39\equiv 29\mod 77$

Le message en clair était donc 20 ou 29 ou 62 ou 64, ce qui est cohérent avec le fait que l'on a chiffré le nombre 20. Sans information supplémentaire, notamment par reconnaissance d'un motif particulier dans le message chiffré on ne peut pas savoir laquelle des quatre valeurs est la bonne.

Annexes

Bibliographie

• [Buchmann 2001] (de) Johannes Buchmann, Einführung in die Kryptographie, Berlin, Springer, 2001, 2^e éd., 231 p. (ISBN 3-540-41283-2, OCLC 248045737).
• [Menezes, van Oorschot et Vanstone 1996] (en) Alfred Menezes et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, octobre 1996, 780 p. (ISBN 0-8493-8523-7, OCLC 849453812).
• [Rabin 1979] (en) Michael O. Rabin, « Digitalized Signatures and Public-Key Functions as Intractable as Factorization », MIT Laboratory for Computer Science,‎ janvier 1979 (lire en ligne [PDF]).
• [Lindhurst 1999] (en) Scott Lindhurst, « An analysis of Shank's algorithm for computing square roots in finite fields », dans R. Gupta et K. S. Williams, Proc 5th Conf Can Nr Theo Assoc, vol. 19, AMS, coll. « CRM Proc & Lec Notes », août 1999.
• [Kumanduri et Romero 1997] R. Kumanduri et C. Romero, Number Theory with Computer Applications, Prentice Hall, 1997.