Cryptosysteme de Rabin

Cryptosysteme de Rabin

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

Sommaire

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

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

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.

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

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

et

m_q = \sqrt{c} \, \bmod \, q

sont calculées. L'algorithme d'Euclide étendu permet de calculer yp et yq, 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

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

L'algorithme d'Euclide étendu donne ensuite yp = − 3 et yq = 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

  • 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.
  • Portail de la cryptologie Portail de la cryptologie
Ce document provient de « Cryptosyst%C3%A8me de Rabin ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Cryptosysteme de Rabin de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • 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 …   Wikipédia en Français

  • 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 …   Wikipédia en Français

  • 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 …   Wikipédia en Français

  • Cryptosysteme — Cryptosystème Un cryptosystème est un terme utilisé en cryptographie pour désigner un ensemble composé d algorithmes cryptographiques et de tous les textes en clairs, textes chiffrés et clés possibles (définition de Bruce Schneier). Cette… …   Wikipédia en Français

  • Rabin (Homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Cryptosystème de Rabin Yitzhak Rabin, homme politique israëlien. Voir aussi : Rabbin Ce document provient de « Rabin (homonymie) ». Catégorie :… …   Wikipédia en Français

  • Cryptosystème — Un cryptosystème est un terme utilisé en cryptographie pour désigner un ensemble composé d algorithmes cryptographiques et de tous les textes en clairs, textes chiffrés et clés possibles (définition de Bruce Schneier). Cette dénomination est… …   Wikipédia en Français

  • Rabin (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Cryptosystème de Rabin Yitzhak Rabin, homme politique israélien. Voir aussi : Rabbin Catégorie : Homonymie …   Wikipédia en Français

  • Michael O. Rabin — Michael Rabin  Pour l’article homonyme, voir Michael Rabin (violoniste).  Michael O. Rabin (né en 1931 à Breslau en Allemagne, maintenant Wrocław en Pologne) est un informaticien et un logicien ; il a été récipiendaire du prix… …   Wikipédia en Français

  • Michael Rabin —  Pour l’article homonyme, voir Michael Rabin (violoniste).  Michael Rabin Michael Oser Rabin (né en 1931 à Breslau en Allemagne, maintenant …   Wikipédia en Français

  • Cryptologue — Un cryptologue est un spécialiste en cryptologie, il étudie et conçoit les méthodes de chiffrement. Il analyse également les algorithmes et les implémentations afin de valider leur sécurité et assurer la confidentialité, l authenticité et l… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”