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 3mod4$. 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)modn$

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 cmodn$ qui équivaut à résoudre $x^2+Bx-c\equiv 0modn$. 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}modn$ où $\delta$ est une des quatre racines carrées modulo $n$ du discriminant $\mathrm{\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 $\mathrm{\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 {\mathrm{\Delta }}^{\frac{p+1}{4}}modp$ et $\delta \equiv \pm {\mathrm{\Delta }}^{\frac{q+1}{4}}modq$ ; 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}modn$ 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 $\mathrm{\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, $\mathrm{\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\equiv ̸-{\delta }_{2}modn$. On a alors ${\delta }_1^2-{\delta }_2^2\equiv 0modn$, c'est-à-dire par différence de deux carrés $({\delta }_1+{\delta }_2)({\delta }_1-{\delta }_2)\equiv 0modn$ où ${\delta }_1+{\delta }_2\equiv ̸0modn$ et ${\delta }_1-{\delta }_2\equiv ̸0modn$. 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.

La sécurité du cryptosystème de Rabin est maintenue dans le cadre d'une attaque à texte clair connu. En revanche dans le cas d'une attaque à texte chiffré choisi la sécurité du chiffrement est menacée. En effet à chaque message chiffré correspondent quatre messages clairs potentiels, et d'après ce qui précède la connaissance de deux d'entre eux peut suffire à factoriser la clé publique et donc casser la sécurité du chiffrement. Il s'ensuit que si l'on peut faire déchiffrer un message dont on connaît déjà l'un des clairs correspondants possibles, on peut obtenir avec une probabilité de $\frac{1}{2}$ un deuxième clair qui permet la connaissance de la clé privée.

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)modn\equiv 20\times 48mod77\equiv 1120mod77\equiv 36mod77$.

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 0mod77$.
  • Son discriminant vaut $\mathrm{\Delta }\equiv 28^2-4\times (-36)\equiv 928\equiv 4mod77$.
  • $\mathrm{\Delta }$ a quatre racines carrées $\delta$ vérifiant $\delta \equiv \pm 4^{\frac{7+1}{4}}\equiv \pm 2mod7$ et $\delta \equiv \pm 4^{\frac{11+1}{4}}\equiv \pm 9mod11$ (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 2mod7$ et ${\delta }_1\equiv 9mod11$ correspond à ${\delta }_1\equiv 9mod77$
  • ${\delta }_2\equiv 2mod7$ et ${\delta }_2\equiv -9mod11$ correspond à ${\delta }_2\equiv 2mod77$
  • ${\delta }_3\equiv -2mod7$ et ${\delta }_3\equiv 9mod11$ correspond à ${\delta }_3\equiv 75mod77$
  • ${\delta }_4\equiv -2mod7$ et ${\delta }_4\equiv -9mod11$ correspond à ${\delta }_4\equiv 68mod77$
• ${\dot{2}}^{-1}=39$ car $2\times 39\equiv 1mod77$ (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 20mod77$
  • $m_2\equiv (-28-2)\cdot 39\equiv 62mod77$
  • $m_3\equiv (-28-75)\cdot 39\equiv 64mod77$
  • $m_4\equiv (-28-68)\cdot 39\equiv 29mod77$

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

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Ouvrage.