Criptosistema Rabin
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de agosto de 2021; la verificación requiere 1 edición .El criptosistema Rabin es un sistema criptográfico de clave pública cuya seguridad está garantizada por la dificultad de encontrar raíces cuadradas en el anillo de residuos módulo a número compuesto . La seguridad del sistema, al igual que la seguridad del método RSA , se debe a la dificultad de factorizar números grandes. Un mensaje cifrado se puede descifrar de 4 formas. La desventaja del sistema es la necesidad de seleccionar un mensaje verdadero entre 4 posibles.
Historia
En enero de 1979, Michael O. Rabin publicó una descripción de su sistema. Se ha demostrado que restaurar texto sin formato a partir de texto cifrado es tan difícil como factorizar números grandes. El sistema de Rabin se convirtió en el primer criptosistema asimétrico para el que se realizó tal prueba. La complejidad de la recuperación está relacionada con la dificultad de extraer la raíz cuadrada módulo un número compuesto N = p · q . El problema de factorización y el problema de la raíz cuadrada son equivalentes, es decir:
- conociendo los divisores primos del número N , puedes extraer las raíces cuadradas módulo N ;
- sabiendo cómo extraer raíces cuadradas módulo N , uno puede factorizar N en factores primos.
Generación de claves
El sistema Rabin, como cualquier criptosistema asimétrico , utiliza una clave pública y otra privada. La clave pública se utiliza para cifrar mensajes y se puede divulgar al público. La clave privada es necesaria para el descifrado y solo deben conocerla los destinatarios de los mensajes cifrados.
El proceso de generación de claves es el siguiente:
- Se eligen dos números aleatorios p y q teniendo en cuenta los siguientes requisitos:
- los números deben ser grandes (ver profundidad de bits );
- los números deben ser primos ;
- se debe cumplir la siguiente condición: p ≡ q ≡ 3 mod 4 .
- se calcula el número n = p · q ;
- el número n es la clave pública; los números p y q son cerrados.
Ejemplo. Sean p = 7 y q = 11 . Entonces n = pag · q = 7 · 11 = 77 . El número n = 77 es la clave pública y los números p = 7 y q = 11 son la clave privada. El destinatario les dice a los remitentes el número 77. Los remitentes encriptan el mensaje usando el número 77 y lo envían al destinatario. El destinatario descifra el mensaje usando los números 7 y 11. Las claves dadas son malas para el uso práctico, ya que el número 77 se descompone fácilmente en factores primos (7 y 11).
Cifrado
El mensaje original m (texto) se cifra utilizando la clave pública, el número n de acuerdo con la siguiente fórmula:
c = m² mod n .Debido al uso de la multiplicación de módulos, la velocidad de cifrado del sistema Rabin es mayor que la velocidad de cifrado del método RSA , incluso si en este último caso se elige un valor de exponente pequeño.
Ejemplo (continuación). Sea el texto fuente m = 20 . Entonces el texto cifrado sería: c = m² mod n = 20² mod 77 = 400 mod 77 = 15 .
Descifrado
Para descifrar el mensaje, necesita una clave privada: los números p y q . El proceso de descifrado es el siguiente:
- primero, utilizando el algoritmo de Euclides , los números y se encuentran a partir de la ecuación ;
- luego, usando el teorema chino del resto , se calculan cuatro números:
Ejemplo (fin). Como resultado de la decodificación obtenemos: . Vemos que una de las raíces es el texto original m .
Evaluación de algoritmos
Eficiencia
Descifrar el texto, además del correcto, conduce a tres resultados falsos más. Esta es la principal desventaja del criptosistema Rabin y uno de los factores que impidieron que encontrara un amplio uso práctico.
Si el texto de origen es un mensaje de texto, no es difícil determinar el texto correcto. Sin embargo, si el mensaje es un flujo de bits aleatorios (por ejemplo, para generar claves o una firma digital ), determinar el texto correcto se convierte en un verdadero problema. Una forma de resolver este problema es agregar un encabezado conocido o algún tipo de etiqueta al mensaje antes del cifrado.
Velocidad de cálculo
El algoritmo Rabin es similar a la codificación RSA, pero en lugar de elevar el mensaje a la potencia e , el cifrado utiliza la operación de cuadrar el bloque del mensaje, lo que afecta favorablemente la velocidad del algoritmo sin sacrificar la fuerza criptográfica.
Para la decodificación, se aplica el Teorema del Resto Chino junto con dos módulos de exponenciación. Aquí la eficiencia es comparable a RSA.
Seleccionar el texto deseado de los cuatro conduce a costos computacionales adicionales. Y esto sirvió para asegurar que el criptosistema Rabin no recibiera un uso práctico amplio.
Seguridad
La gran ventaja del criptosistema Rabin es que el texto aleatorio se puede recuperar por completo del texto cifrado solo si el descifrador es capaz de factorizar eficientemente la clave pública n.
Se ha demostrado que un criptosistema Rabin es resistente a un ataque de todo o nada basado en un ataque de texto cifrado simple elegido si y solo si el problema de factorizar un número entero en factores primos es intratable.
La seguridad de todo o nada significa que, teniendo un texto encriptado con un determinado algoritmo, un atacante debe recuperar un bloque del texto original, cuyo tamaño suele estar determinado por el parámetro de seguridad del criptosistema. Dado el original y el texto cifrado, el atacante debe recuperar todo el bloque de clave privada . En este caso, el atacante logra un éxito completo o no recibe nada. La palabra "nada" significa que el atacante no tiene ninguna información secreta ni antes ni después de un ataque fallido.
El criptosistema de Rabin está completamente indefenso frente a ataques basados en el texto cifrado elegido . Por regla general, el atacante utiliza todas las posibilidades que tiene. Se pone en contacto con el usuario atacado, le envía el texto cifrado para su posterior descifrado y exige la devolución del texto original.
Por ejemplo, agregar redundancia, como repetir los últimos 64 bits, puede hacer que la raíz sea única. El algoritmo de descifrado en este caso produce una raíz única, que el atacante ya conoce.
El proceso es además vulnerable porque solo se utilizan residuos cuadrados en la codificación. En el ejemplo con n = 77, solo se utilizan 23 de los 76 estados posibles.
Véase también
Literatura
- Mao V. Cifrado: métodos asimétricos // Criptografía moderna : teoría y práctica / trad. D. A. Klyushina - M. : Williams , 2005. - 768 p. — ISBN 978-5-8459-0847-6
- Schneier B. Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .