Cryptosystème de Rabin

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 p ≡ q ≡ 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.

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 ${\displaystyle P=\{0,...,n-1\}}$ l'espace des textes en clair possibles (tous des nombres) et posons ${\displaystyle m\in P}$ comme étant le texte en clair. Le texte chiffré ${\displaystyle c}$ se détermine comme suit :

${\displaystyle 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é.

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

Les racines carrées ${\displaystyle m_{p}={\sqrt {c}}\,{\bmod {\,}}p}$ et ${\displaystyle m_{q}={\sqrt {c}}\,{\bmod {\,}}q}$ sont calculées. L'algorithme d'Euclide étendu permet de calculer ${\displaystyle y_{p}}$ et ${\displaystyle y_{q}}$, tels que ${\displaystyle 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 ${\displaystyle +r}$, ${\displaystyle -r}$, ${\displaystyle +s}$ et ${\displaystyle -s}$ de ${\displaystyle c+n\mathbb {Z} \in \mathbb {Z} /n\mathbb {Z} }$. (${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ est l'ensemble de la classe des restes modulo n ; les quatre racines carrées sont dans l'ensemble ${\displaystyle \{0,...,n-1\}}$):

${\displaystyle {\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}}}$