Cryptosystème de Rabin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 à l'intractabilité 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 | modifier le code]

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écrypter).

Explicitement, la génération de clés est 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).)
  • Posons n=p*q, ce qui fait de n la clé publique. Les nombres premiers p et q constituent la clé privée.

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.

Voici un exemple qui, par contre, n'utilise pas des paramètres assez grands pour garantir la sécurité dans le monde réel  : Si p = 7 et q = 11, alors n=77. C'est évidemment un piètre choix de clé, puisqu'il est trivial de factoriser le nombre 77.

Chiffrement[modifier | modifier le code]

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 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^2 \, \bmod \, n

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[modifier | modifier le code]

Dans notre exemple précédent, P = \{ 0, ..., 76 \} est l'espace des textes en clair possibles. Prenons m = 20 comme texte en clair. Le texte chiffré est alors c = m^2 \, \bmod \, n = 400 \, \bmod \, 77 = 15.

Note[modifier | modifier le code]

Le texte chiffré 15 est produit pour quatre différentes valeurs de m, soit m \in \{ 13, 20, 57, 64 \}. 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[modifier | modifier le code]

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

Les racines carrées m_p = \sqrt{c} \, \bmod \, p et m_q = \sqrt{c} \, \bmod \, q sont calculées. L'algorithme d'Euclide étendu permet de calculer y_p et y_q, tels que y_p \cdot p + y_q \cdot q = 1.

On invoque alors le théorème des restes chinois pour calculer les quatre racines carrées +r, -r, +s et -s de c + n \mathbb{Z} \in \mathbb{Z} / n \mathbb{Z}. (\mathbb{Z} / n \mathbb{Z} est l'ensemble de la classe des restes modulo n ; les quatre racines carrées sont dans l'ensemble \{ 0, ..., n-1 \}):

\begin{matrix}
r  & = & ( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \, \bmod \, n  \\
-r & = & n - r  \\
s  & = & ( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \, \bmod \, n  \\
-s & = & n - s 
\end{matrix}

Exemple[modifier | modifier le code]

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

L'algorithme d'Euclide étendu donne ensuite y_p = -3 et y_q = 2.

Le théorème des restes chinois donne les quatre racines carrées possibles, m \in \{ 64, \mathbf{20}, 13, 57 \}, dont m=20, le texte en clair original.

Références[modifier | modifier le code]

  • Buchmann, Johannes. Einführung in die Kryptographie. Second Edition. Berlin: Springer, 2001. ISBN 3-540-41283-2
  • Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7
  • Rabin, Michael. Digitalized Signatures and Public-Key Functions as Intractable as Factorization (in PDF). MIT Laboratory for Computer Science, January 1979.
  • Scott Lindhurst, An analysis of Shank's algorithm for computing square roots in finite fields. in R Gupta and K S Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, Aug 1999.
  • R Kumanduri and C Romero, Number Theory w/ Computer Applicatiosn, Alg 9.2.9, Prentice Hall, 1997. A probablistic for square root of a quadratic resiue modulo a prime.