Criptosistema Rabin

Las claves para el criptosistema Rabin se generan de la siguiente manera:

1. Elige dos números primos grandes y distintos.${\displaystyle p}$y${\displaystyle q}$de tal manera que${\displaystyle p\equiv 3{\bmod {4}}}$y${\displaystyle q\equiv 3{\bmod {4}}}$.
2. Calcular${\displaystyle n=pq}$.

Entonces${\displaystyle n}$es la clave pública y el par${\displaystyle (p,q)}$es la clave privada.

Un mensaje${\displaystyle M}$se puede cifrar convirtiéndolo primero en un número${\displaystyle m<n}$utilizando un mapeo reversible y luego calculando${\displaystyle c=m^{2}{\bmod {n}}}$El texto cifrado es${\displaystyle c}$.

El mensaje${\displaystyle m}$se puede recuperar del texto cifrado${\displaystyle c}$tomando su raíz cuadrada módulo${\displaystyle n}$como sigue.

1. Calcula la raíz cuadrada de${\displaystyle c}$módulo${\displaystyle p}$y${\displaystyle q}$utilizando estas fórmulas:

   ${\displaystyle {\begin{aligned}m_{p}&=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}\\m_{q}&=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}\end{aligned}}}$

2. Utilice el algoritmo euclidiano extendido para encontrar${\displaystyle y_{p}}$y${\displaystyle y_{q}}$de tal manera que${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$.
3. Utilice el teorema chino del resto para hallar las cuatro raíces cuadradas de${\displaystyle c}$módulo${\displaystyle n}$:

   ${\displaystyle {\begin{aligned}r_{1}&=\left(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{2}&=n-r_{1}\\r_{3}&=\left(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{4}&=n-r_{3}\end{aligned}}}$

Uno de estos cuatro valores es el texto plano original.${\displaystyle m}$, aunque no se puede determinar cuál de las cuatro es la correcta sin información adicional.

Como ejemplo, tomemos${\displaystyle p=7}$y${\displaystyle q=11}$, entonces${\displaystyle n=77}$. Llevar${\displaystyle m=20}$como nuestro texto plano. El texto cifrado es, por lo tanto, ${\displaystyle c=m^{2}{\bmod {n}}=400{\bmod {77}}=15}$.

El proceso de descifrado se lleva a cabo de la siguiente manera:

1. Calcular${\displaystyle m_{p}=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}=15^{2}{\bmod {7}}=1}$y${\displaystyle m_{q}=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}=15^{3}{\bmod {11}}=9}$.
2. Utilice el algoritmo euclidiano extendido para calcular${\displaystyle y_{p}=-3}$y${\displaystyle y_{q}=2}$Podemos confirmar que${\displaystyle y_{p}\cdot p+y_{q}\cdot q=(-3\cdot 7)+(2\cdot 11)=1}$.
3. Calcula los cuatro candidatos de texto plano:

   ${\displaystyle {\begin{aligned}r_{1}&=(-3\cdot 7\cdot 9+2\cdot 11\cdot 1){\bmod {77}}=64\\r_{2}&=77-64=13\\r_{3}&=(-3\cdot 7\cdot 9-2\cdot 11\cdot 1){\bmod {77}}=\mathbf {20} \\r_{4}&=77-20=57\end{aligned}}}$

y vemos que${\displaystyle r_{3}}$es el texto plano deseado. Tenga en cuenta que los cuatro candidatos son raíces cuadradas de 15 mod 77. Es decir, para cada candidato,${\displaystyle r_{i}^{2}{\bmod {77}}=15}$, así que cada${\displaystyle r_{i}}$cifra al mismo valor, 15.

El descifrado produce tres resultados falsos además del correcto, por lo que hay que adivinar el resultado correcto. Esta es la principal desventaja del criptosistema Rabin y uno de los factores que han impedido su uso práctico generalizado.

Si el texto plano pretende representar un mensaje de texto, adivinarlo no es difícil; sin embargo, si pretende representar un valor numérico, este problema debe resolverse mediante algún tipo de esquema de desambiguación. Es posible elegir textos planos con estructuras especiales o añadir relleno para eliminar este problema. Blum y Williams sugirieron una forma de eliminar la ambigüedad de la inversión: los dos números primos utilizados se restringen a primos congruentes con 3 módulo 4 y el dominio de la elevación al cuadrado se restringe al conjunto de residuos cuadráticos. Estas restricciones convierten la función de elevación al cuadrado en una permutación de puerta trasera , eliminando la ambigüedad. ^{[ 8 ]}

Para el cifrado, se debe calcular un módulo cuadrado n . Esto es más eficiente que RSA , que requiere el cálculo de al menos un cubo.

Para el descifrado, se aplica el teorema chino del resto , junto con dos exponenciaciones modulares . En este caso, la eficiencia es comparable a la de RSA.

Se ha demostrado que cualquier algoritmo que encuentre uno de los posibles textos planos para cada texto cifrado encriptado por Rabin puede utilizarse para factorizar el módulo.${\displaystyle n}$Por lo tanto, el descifrado Rabin para texto plano aleatorio es al menos tan difícil como el problema de factorización de enteros, algo que no se ha demostrado para RSA. Generalmente se cree que no existe un algoritmo de tiempo polinomial para la factorización, lo que implica que no existe un algoritmo eficiente para descifrar un valor cifrado Rabin aleatorio sin la clave privada.${\displaystyle (p,q)}$.

El criptosistema Rabin no ofrece indistinguibilidad frente a ataques de texto plano elegido, ya que el proceso de cifrado es determinista. Un adversario, dado un texto cifrado y un mensaje candidato, puede determinar fácilmente si el texto cifrado codifica o no el mensaje candidato (simplemente comprobando si al cifrar el mensaje candidato se obtiene el texto cifrado dado).

El criptosistema Rabin es inseguro frente a un ataque de texto cifrado elegido (incluso cuando los mensajes de desafío se eligen uniformemente al azar del espacio de mensajes). ^{[ 6 ] : 214} Al añadir redundancias, por ejemplo, la repetición de los últimos 64 bits, se puede hacer que el sistema produzca una única raíz. Esto frustra este ataque específico de texto cifrado elegido, ya que el algoritmo de descifrado solo produce la raíz que el atacante ya conoce. Si se aplica esta técnica, la prueba de equivalencia con el problema de factorización falla, por lo que, a fecha de 2004, no se sabe con certeza si esta variante es segura. El Manual de Criptografía Aplicada de Menezes, Oorschot y Vanstone considera probable esta equivalencia, siempre que la búsqueda de las raíces siga siendo un proceso de dos partes (1. raíces${\displaystyle {\bmod {p}}}$y${\displaystyle {\bmod {q}}}$y 2. aplicación del teorema chino del resto).