El criptosistema Rabin es una técnica criptográfica asimétrica , cuya seguridad, como la de RSA , está relacionada con la dificultad de factorización de enteros . Sin embargo, el criptosistema Rabin tiene la ventaja de que se ha demostrado matemáticamente que es seguro computacionalmente contra un ataque de texto plano elegido siempre que el atacante no pueda factorizar números enteros de manera eficiente, mientras que no existe tal prueba conocida para RSA. [1] : 145 Tiene la desventaja de que cada salida de la función Rabin puede ser generada por cualquiera de las cuatro entradas posibles; si cada salida es un texto cifrado, se requiere una complejidad adicional en el descifrado para identificar cuál de las cuatro posibles entradas era el verdadero texto sin formato.
Historia
El algoritmo fue publicado en enero de 1979 por Michael O. Rabin . [2] El criptosistema Rabin fue el primer criptosistema asimétrico en el que se pudo demostrar que recuperar el texto plano del texto cifrado era tan difícil como factorizar.
Algoritmo de cifrado
Como todos los criptosistemas asimétricos, el sistema Rabin utiliza un par de claves: una clave pública para el cifrado y una clave privada para el descifrado. La clave pública se publica para que la use cualquiera, mientras que la clave privada sigue siendo conocida solo por el destinatario del mensaje.
Generación de claves
Las claves para el criptosistema Rabin se generan de la siguiente manera:
- Elija dos números primos grandes y distintos y tal que y .
- Calcular .
Luego es la clave pública y el par es la clave privada.
Cifrado
Un mensaje se puede cifrar convirtiéndolo primero en un número usando un mapeo reversible, luego computando . El texto cifrado es.
Descifrado
El mensaje se puede recuperar del texto cifrado tomando su módulo de raíz cuadrada como sigue.
- Calcule la raíz cuadrada de modulo y usando estas fórmulas:
- Utilice el algoritmo euclidiano extendido para encontrar y tal que .
- Utilice el teorema del resto chino para encontrar las cuatro raíces cuadradas de modulo :
Uno de estos cuatro valores es el texto plano original , aunque cuál de los cuatro es el correcto no se puede determinar sin información adicional.
Calcular raíces cuadradas
Podemos demostrar que las fórmulas del paso 1 anterior en realidad producen las raíces cuadradas de como sigue. Para la primera fórmula, queremos demostrar que. Desde el exponente es un entero. La prueba es trivial si, entonces podemos asumir que no divide . Tenga en cuenta que implica que , entonces c es un módulo de residuo cuadrático. Luego
El último paso está justificado por el criterio de Euler .
Ejemplo
Como ejemplo, tome y , luego . Llevarcomo nuestro texto sin formato. El texto cifrado es así.
El descifrado procede de la siguiente manera:
- Calcular y .
- Utilice el algoritmo euclidiano extendido para calcular y . Podemos confirmar que.
- Calcule los cuatro candidatos de texto sin formato:
y vemos que es el texto sin formato deseado. Tenga en cuenta que los cuatro candidatos son raíces cuadradas de 15 mod 77. Es decir, para cada candidato,, entonces cada cifra con el mismo valor, 15.
Algoritmo de firma digital
El criptosistema Rabin se puede utilizar para crear y verificar firmas digitales . La creación de una firma requiere la clave privada. La verificación de una firma requiere la clave pública.
Firma
Un mensaje se puede firmar con una clave privada como sigue.
- Genera un valor aleatorio .
- Utilice una función hash criptográfica computar , donde la barra denota concatenación. debe ser un número entero menor que .
- Tratar como un valor cifrado por Rabin e intente descifrarlo, utilizando la clave privada . Esto producirá los cuatro resultados habituales,.
- Cabría esperar que cifrar cada produciría . Sin embargo, esto será cierto solo sipasa a ser un módulo de residuo cuadrático y . Para determinar si este es el caso, cifre el primer resultado de descifrado. Si no se encripta, repita este algoritmo con un nuevo aleatorio . El número esperado de veces que este algoritmo debe repetirse antes de encontrar un es 4.
- Habiendo encontrado un que encripta a , la firma es .
Verificando una firma
Una firma para un mensaje se puede verificar usando la clave pública como sigue.
- Calcular .
- Cifrar usando la clave pública .
- La firma es válida si y solo si el cifrado de es igual a .
Evaluación del algoritmo
Eficacia
El descifrado produce tres resultados falsos además del correcto, por lo que se debe adivinar el resultado correcto. Esta es la principal desventaja del criptosistema Rabin y uno de los factores que le han impedido encontrar un uso práctico generalizado.
Si el texto sin formato pretende representar un mensaje de texto, no es difícil adivinar; sin embargo, si se pretende que el texto sin formato represente un valor numérico, esta cuestión se convierte en un problema que debe resolverse mediante algún tipo de esquema de desambiguación. Es posible elegir textos planos con estructuras especiales, o agregar relleno , para eliminar este problema. Blum y Williams sugirieron una forma de eliminar la ambigüedad de la inversión: los dos primos utilizados se restringen a primos congruentes a 3 módulo 4 y el dominio del cuadrado se restringe al conjunto de residuos cuadráticos. Estas restricciones convierten la función de cuadratura en una permutación de trampilla , eliminando la ambigüedad. [3]
Eficiencia
Para el cifrado, se debe calcular un módulo n cuadrado . Esto es más eficiente que RSA , que requiere el cálculo de al menos un cubo.
Para el descifrado, se aplica el teorema del resto chino , junto con dos exponenciaciones modulares . Aquí la eficiencia es comparable a RSA.
La desambiguación introduce costos computacionales adicionales y es lo que ha impedido que el criptosistema Rabin encuentre un uso práctico generalizado. [ cita requerida ]
Seguridad
Se ha demostrado que cualquier algoritmo que descifre un valor cifrado por Rabin se puede utilizar para factorizar el módulo. . Por lo tanto, el descifrado de Rabin es al menos tan difícil como el problema de la factorización de enteros, algo que no se ha probado para RSA. En general, 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 por Rabin sin la clave privada..
El criptosistema Rabin no proporciona indistinguibilidad frente a los ataques de texto sin formato elegidos, 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 verificando si el cifrado del mensaje candidato produce el texto cifrado dado).
El criptosistema Rabin es inseguro contra un ataque de texto cifrado elegido (incluso cuando los mensajes de desafío se eligen uniformemente al azar en el espacio de mensajes). [1] : 150 Al agregar redundancias, por ejemplo, la repetición de los últimos 64 bits, se puede hacer que el sistema produzca una sola 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 es incierto a partir de 2004 si esta variante es segura. El Handbook of Applied Cryptography por Menezes, Oorschot y Vanstone considera esta equivalencia probable, sin embargo, siempre que el hallazgo de las raíces sigue siendo un proceso de dos partes (1. raíces y y 2. aplicación del teorema del resto chino).
Ver también
Notas
- ↑ a b Stinson, Douglas (1995). Criptografía: teoría y práctica . CRC Press LLC.
- ^ Rabin, Michael (enero de 1979). "Firmas digitalizadas y funciones de clave pública tan intratables como la factorización" (PDF) . Laboratorio de Ciencias de la Computación del MIT.
- ^ Shafi Goldwasser y Mihir Bellare "Notas de la conferencia sobre criptografía" . Curso de verano sobre criptografía, MIT, 1996-2001
Referencias
- Buchmann, Johannes. Einführung in die Kryptographie . Segunda edicion. Berlín: Springer, 2001. ISBN 3-540-41283-2
- Menezes, Alfred; van Oorschot, Paul C .; y Vanstone, Scott A. Manual de criptografía aplicada . CRC Press, octubre de 1996. ISBN 0-8493-8523-7
- Rabin, Michael. Firmas digitalizadas y funciones de clave pública tan intratables como la factorización (en PDF). Laboratorio de Ciencias de la Computación del MIT, enero de 1979.
- Scott Lindhurst, un análisis del algoritmo de Shank para calcular raíces cuadradas en campos finitos. en R Gupta y KS Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, agosto de 1999.
- R Kumanduri y C Romero, Teoría de números con aplicaciones informáticas, Alg 9.2.9, Prentice Hall, 1997. Una probabilística para la raíz cuadrada de un residuo cuadrático módulo un primo.