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. (Pour simplifier les calculs, on peut les choisir tels que pq ≡ 3 (mod 4).) Ils constituent la clé privée.
  • Calculer n=p*q. n constitue la clé publique.

Pour chiffrer, on n'a besoin que de la clé publique, n. Pour déchiffrer, les facteurs de n, p et q, sont nécessaires.

Chiffrement

Pour le chiffrement, seule la clé publique, n, est utilisée. On produit le texte chiffré à partir du texte en clair m 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 :

Autrement dit, c est le résidu quadratique du carré du texte en clair, pris modulo n. En pratique du chiffrement par bloc est généralement utilisé.

Exemple

Dans notre exemple précédent, est l'espace des textes en clair possibles. Prenons comme texte en clair. Le texte chiffré est alors .

Note

Le texte chiffré 15 est produit pour quatre différentes valeurs de m, soit . Ceci est aussi vrai pour la plupart des textes chiffrés produits par l'algorithme de Rabin. En d'autres termes, c'est une fonction de « quatre-en-un ».

Déchiffrement

Pour déchiffrer, la clé privée est nécessaire. Le processus est comme suit.

Les racines carrées et sont calculées. L'algorithme d'Euclide étendu permet de calculer et , tels que .

On invoque alors le théorème des restes chinois pour calculer les quatre racines carrées , , et de . ( est l'ensemble de la classe des restes modulo n ; les quatre racines carrées sont dans l'ensemble ):

Exemple

Dans l'exemple précédent, on trouve d'abord les racines modulo les nombres premiers de la clé privée : et .

L'algorithme d'Euclide étendu donne ensuite et .

Le théorème des restes chinois donne les quatre racines carrées possibles, , dont m=20, le texte en clair original.

Notes et références

    Annexes

    Bibliographie

    • [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, .
    • Portail de la cryptologie
    Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.