Cryptosystème de Rabin

Un article de Wikipédia, l'encyclopédie libre.

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.

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

Explicitement, la génération de clés est comme suit.

Choisisr deux grands nombres premiers, p et q, au hasard. (Pour simplifier les calculs, on peut les choisir tels que p≡q≡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 chiffer, on n'a besoins que de la clé publique, n. Pour déchiffrer, les facteurs de n, p et q, sont nécessaires.

Exemple

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.

[modifier] Chiffrement

Pour le chiffrement, seulement 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é.

[modifier] Exemple

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 chiffé est alors $c = m^2 \, \bmod \, n = 400 \, \bmod \, 77 = 15$ .

[modifier] Note

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 ».

[modifier] Déchiffrement

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$

$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}$

[modifier] Exemple

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.

[modifier] Références

Buchmann, Johannes. Einführung in die Kryptographie. Second Edition. Berlin: Springer, 2001. ISBN 3540412832
Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0849385237
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.