Cryptosystème de Rabin

cryptosystème asymétrique

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

modifier

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[1]:

  • Choisir deux grands nombres premiers, et , au hasard, de telle sorte que . Ils constituent la clé privée.
  • Calculer (autrement dit, est un entier de Blum). Choisir un entier inférieur à . Le couple constitue la clé publique.

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

Chiffrement

modifier

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

Soit l'espace des textes en clair possibles (tous des nombres) et posons comme étant le texte en clair. Le texte chiffré se détermine comme suit[1]:

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

Déchiffrement

modifier

Le message clair est solution de l'équation du second degré qui équivaut à résoudre . Si l'on est capable de calculer des racines carrées modulo , 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écessite de savoir factoriser en produit de facteurs premiers[1]. 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, est égal à l'un des nombres s'écrivant est une des quatre racines carrées modulo du discriminant et où est l'inverse modulaire de 2 modulo , que l'on peut calculer efficacement à l'aide de l'algorithme d'Euclide étendu.

Les quatre racines carrées de sont calculées efficacement en connaissant la clé privée et en utilisant les propriétés des entiers de Blum : et  ; il reste alors juste à déterminer modulo à l'aide du théorème des restes chinois.

Comme et que l'on a calculé et les quatre valeurs possibles de , il ne reste plus qu'à déduire les quatre valeurs possibles de 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 à . C'est un inconvénient qui rend délicate l'automatisation du déchiffrement[1].

Preuve de sécurité de l'algorithme

modifier

Contrairement au chiffrement RSA, il est prouvé que l'on ne peut pas retrouver un message clair à partir du message chiffré correspondant sans être capable de retrouver les facteurs premiers et du module 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[1]. 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[1].

On montre que retrouver les quatre messages clairs possibles à partir du chiffré implique de savoir factoriser . Il est facile de calculer à partir du chiffré et il est facile de calculer les valeurs de à partir des valeurs de (pour allant de 1 à 4). On peut donc associer un nombre, et ses quatre racines carrées modulo .

On peut choisir deux de ces quatre racines et qui vérifient . On a alors , c'est-à-dire par différence de deux carrés et . Autrement dit, ni ni ne sont des multiples de mais leur produit l'est. Il s'ensuit que divise et divise .

Le PGCD de et est donc égal à  : on peut le trouver efficacement à l'aide de l'algorithme d'Euclide et de là déduire l'autre facteur de  : être capable de trouver les clairs possibles correspondant à un message chiffré donné implique d'être capable de factoriser l'entier utilisé comme clé publique[1].

Exemple d'exécution

modifier

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

modifier

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

Chiffrement du message

modifier

= 77 donc est l'espace des textes en clair possibles. On choisit par exemple comme texte en clair. Seule la clé publique est nécessaire pour chiffrer.

Le texte chiffré est alors .

Remarque

modifier

Le texte chiffré 36 est produit pour quatre différentes valeurs de m, soit . 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[1].

Déchiffrement

modifier

En poursuivant l'exemple précédent, le destinataire reçoit le message chiffré 36. Il connait le nombre qui est public ainsi que le clé privée . Le déchiffrement s'effectue comme suit :

  • Le message en clair est solution de l'équation .
    • Son discriminant vaut .
    • a quatre racines carrées vérifiant et (car est un entier de Blum)
  • En appliquant le théorème des restes chinois, on déduit les quatre valeurs possibles de  :
    • et correspond à
    • et correspond à
    • et correspond à
    • et correspond à
  • car (obtenu à l'aide de l'algorithme d'Euclide étendu)
  • Les quatre valeurs possibles de sont les valeurs avec

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[1].

Notes et références

modifier
  1. a b c d e f g h et i Gilles Bailly-Maitre, Arithmétique et cryptologie, Ellipses, , 2e éd., 317 p. (ISBN 9782340046191), III - Cryptologie moderne, chap. 9 (« Cryptographie à clé publique »), p. 220 - 223.

Annexes

modifier

Bibliographie

modifier
  • [Buchmann 2001] (de) Johannes Buchmann, Einführung in die Kryptographie, Berlin, Springer, , 2e é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, , 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,‎ (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 », .
  • [Kumanduri et Romero 1997] R. Kumanduri et C. Romero, Number Theory with Computer Applications, Prentice Hall, .