• Author / Uploaded
• Martin Cruz Otiniano

Citation preview

El criptosistema de Rabin - SER

Sistema de Encriptación de Rabin Reporte Final. Agosto de 2002

Oscar Gonzalo Landa Rosales Departamento de Ingeniería Eléctrica Sección de Computación. Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional.

e-mail: [email protected]

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_1

El criptosistema de Rabin - SER

Centro de Investigación y de Estudios Avanzados – IPN 5 de Agosto del 2002. Reporte del Proyecto

Sistema de Encriptación de Rabin (SER) (Especificación y Diseño de Sistema) Oscar Gonzalo Landa Rosales

Resumen Se presenta una breve introducción a los conceptos básicos de criptografía y en particular al Criptosistema de Rabin; pretendiendo entrar en contexto con este sistema, el cual se analiza la complejidad de esta tema que abarca desde conceptos matemáticos, hasta serios problemas de software y sistemas, pasando por problemas de diseño y análisis de algoritmos, y donde todo esto debe interactuar como un todo para lograr una implementación de un sistema de encriptamiento seguro. Finalmente, se pretende destacar la importancia, que tiene un buen análisis y diseño de un Criptosistema, para las siguientes etapas de desarrollo del sistema.

1.

Introducción

En este documento se realizo un análisis de requerimientos y de diseño, donde se persiguió el descubrir los alcances y limites, refinamiento, modelización y especificación del sistema SER. Comienza con una descripción detallado del ámbito del programa, con objeto de poder establecer un buen diseño del sistema. Se crearon los modelos del flujo de la información y del control, del comportamiento en operacional y del contenido de los datos. Se analizan

las soluciones

alternativas, con la asignación de los distintos elementos del software. El objetivo de este Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_2

El criptosistema de Rabin - SER documento es poder reducir el mayor numero de malas interpretaciones o falta de información que da por ende un mal diseño. Por ultimo la especificación de requisitos del sistema SER, facilitara al equipo de desarrollo la especificación de la función y del rendimiento del software, la descripción de la interfaz con otros elementos del sistema y el establecimiento de las restricciones de diseño que debe considerar el SER.

1 .1

Contexto del sistema.

Las amenazas que sufre la información durante su proceso, almacenamiento y transmisión son crecientes, multiformes y complejas, más aun, desde la globalización de Internet. Dada la potencialidad de esta herramienta y de sus innumerables aplicaciones cada vez más personas y empresas sienten la necesidad de conectarse a este magnífico mundo. Para contrarrestar estas amenazas se han desarrollado numerosas medidas de protección, que se implementan en el equipo físico o lógico mediante los denominados mecanismos de seguridad. De éstos, el mecanismo por excelencia es el cifrado de la información, de los cuales existen diversos métodos que se encuentran clasificados en dos importantes ramas : criptografía clásica o de clave simétrica y criptografía moderna o de clave publica.

1.1.1 Criptografía clásica También conocida como criptografía de clave simétrica, este tipo de criptografía ha sido usada por años, su nombre proviene del hecho que ambos, remitente y destinatario en una comunicación comparten una sola clave que se debe guardar en secreto. Si se quiere comunicar secretamente con alguien, lo primero que se debe hacer es notificar al destinatario cual es la clave que se usará para encriptar el mensaje, este proceso es muy importante y difícil de realizar adecuadamente además de él depende el éxito de la comunicación. La siguiente figura 1. muestra una comunicación entre dos partes usando encriptación con clave simétrica. [4]

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_3

El criptosistema de Rabin - SER

Figura 1. El uso de una sola clave implica que el mensaje se encripta con e ^ K y se desencripta con d = e^ (-1). No debemos basar la seguridad de nuestro sistema en suponer que nadie sabe cual es la transformación aplicada. Siempre se debe asumir que todas las partes conocen el conjunto de transformaciones de encriptación/desencriptación (es decir, adversarios, emisor y receptor). Lo único que se debe mantener en secreto es la clave d, y por supuesto e dado que d puede ser deducida de ésta. Hay dos clases de esquemas de encriptación de claves simétricas las cuales son comúnmente distinguibles : Cifrados de bloque y Cifrado corriente.

Cifrado por Bloque El cifrado en bloques es un esquema de encriptación el cual descansa sobre los mensajes de texto puro que serán transmitidos dentro de strings (llamados bloques) de largo fijo t sobre el alfabeto A , encriptando un bloque a la vez. La mejor técnica de encriptación con clave simétrica conocida es el cifrado en bloque. Dos importantes clases de cifrados en bloque son : cifrado por sustitución y cifrado por transposición, además del cifrado por producto que es una combinación de los dos anteriores.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_4

El criptosistema de Rabin - SER Cifrado por Sustitución El cifrado por sustitución es cifrado de bloques con reemplazo de símbolos o grupos de símbolos por otros símbolos o grupos de símbolos. Cifrado por sustitución simple Sea A un alfabeto de q símbolos y M el conjunto de todos los strings de largo t sobre A. Sea K, el conjunto de todas las permutaciones en el conjunto A. Se define para cada símbolo e | K la transformación de encripción Ee como sigue : Ee(m) = (e(m1) e(m2) ........ e(mt)) = (c1 c2 c3 ....... ct) = c donde m=(m1 m2 m3 ...... mt) En otras palabras, para cada símbolo en t-tupla, reemplace éste por otro símbolo de A de acuerdo a algunas permutaciones fijas de e. Para encriptar c=(c1 c2 ... ct) calcule la permutación inversa de d = e^ -1 y Dd(c) = (d(c1) d(c2) ... d(ct)) = (m1 m2 ... mt) = m Ee es llamado cifrado de sustitución simple o cifrado de sustitución monoalfabético. El número de cifrados distintos es q! y es independiente del tamaño del bloque en el cifrado.

Cifrado Corriente El cifrado corriente aplica transformaciones de encriptación simples, según la clave a ser usada, sobre bloques de largo 1. Lo que tiene de útil es que la transformación de encriptación puede cambiar para cada símbolo del texto puro que se está encriptando. Sea K el espacio de claves para el conjunto de transformaciones de encriptación, la secuencia de símbolos e1e2e3...ei | K, son llamadas claves corrientes. Sea A un alfabeto de q símbolos y sea Ee la sustitución de cifrado con bloques de largo 1 donde e | K. Sea m1m2m3...mi el string de texto puro y e1e2e3...ei, las claves corrientes de K. El cifrado corriente toma el string de texto puro y produce otro string de texto cifrado c1c2c3...ci. El cifrado corriente aplica transformaciones de encriptación simples, según la clave corriente a ser usada, se puede generar la clave corriente al azar, o por un algoritmo que genere la clave corriente a través de una semilla

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_5

El criptosistema de Rabin - SER

1.1.2 Criptografía con Clave-Pública El concepto de encripción con clave-pública es simple y elegante, pero tiene grandes consecuencias.

Encripción con Clave-Pública Sea (Ee: e | K) un conjunto de transformación de encripción, y sea (Dd : d | K) el conjunto de la transformación de decripción correspondiente, donde K es el espacio de claves. Considere algún par de transformaciones de encripción / decripción asociadas (Ee, Dd) y suponga que cada par tiene la propiedad de que Ee es computacionalmente in factible de calcular, dado un texto cifrado al azar c | C, se quiere encontrar el mensaje m | M tal que Ee (m)= c. Esta propiedad implica que dado e es in factible determinar la correspondiente clave de decripción d ( por supuesto e y d son simplemente medios para describir la función de encripción y decripción correspondiente) Ee es vista aquí como una función unidireccional con trampa con d la trampa de información necesaria para calcular la función inversa y así permitir la decripción. Esto es distinto del cifrado con ClaveSimétrica donde e y d son esencialmente iguales. Dentro de esta suposición, considere la comunicación entre dos partes Maria y Juan mostrado en la Figura 1 Juan escoge el par de claves (e, d). Juan envía la clave de encripción e (llamada clave pública) a Maria en algún canal, pero guarda la clave de decripción d (llamada clave privada) segura y secretamente. Maria puede subsiguientemente enviar un mensaje m a Juan aplicando la transformación de encripción determinada por la clave pública de Juan para hacer c=Ee(m). Juan decripta el texto cifrado c aplicando la transformación inversa Dd únicamente determinado por d. Aquí la clave de encripción es transmitida a Maria a través de un canal no seguro. Este canal no seguro tal vez el mismo canal sobre el cual el texto cifrado es transmitido. Puesto que la clave de encripción e no necesita mantenerse en secreto ésta puede hacerse pública. Cualquiera entidad puede enviar subsiguientemente mensajes encriptados a Juan que sólo Juan puede decriptar. La Figura 2 muestra esta idea, donde A1, A2, y A3 son entidades distintas. Note que si A1 destruye el mensaje m1 después de encriptarlo con c1, entonces A1 no puede recobrar m1 por c1.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_6

El criptosistema de Rabin - SER

Una analogía física, considere una caja de metal con una tapa de seguridad que tiene una combinación secreta. La combinación es conocida sólo por Bob. Si la cerradura se abre hacia la izquierda y esto se hace público entonces cualquier persona puede poner un mensaje dentro y cerrar la tapa. Pero sólo Bob puede recuperar el mensaje. Aún la entidad que puso el mensaje dentro de la caja no puede recuperarlo. La encripción con clave-pública, es descrita aquí, se asume el conocimiento de la clave-pública e y no se permite el cálculo de la clave privada d. En otras palabras, Se asume la existencia de una función unidireccional.

Figura 2. Uso esquemático de la encriptación con clave-pública.

Definición : Considere un esquema de encripción compuesto por un conjunto de transformaciones de encripción y decripción (Ee: e | K) y (Dd : d | K), respectivamente. El método de encripción se llama un esquema de encripción con clave-pública si por cada par asociado de encripción/decripción (e,d), una clave e (la clave pública) se hace públicamente disponible, mientras que la otra d (la clave-privada) se guarda confidencialmente. Para que el esquema sea seguro, debe ser in factible computacionalmente calcular d a partir de e.

Comentario: (Clave pública vs Clave secreta) para evitar ambigüedad, se llego a un acuerdo en común de usar el término clave-privada en asociación con el criptosistema con clave-pública y clave- secreta en asociación con el criptosistema con clave simétrica. Esto motivado por el siguiente pensamiento: Son necesarias dos o más partes para compartir un secreto, pero una clave es en verdad privada cuando sólo una parte la sabe. Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_7

El criptosistema de Rabin - SER Hay muchos esquemas conocidos que creen ser claves públicas seguras para un método de encripción, pero no tienen ninguna evidencia matemática para asegurar la independencia de ser sólo suposiciones. Esto no es diferente en el caso de la clave-simétrica donde el único sistema que ha probado ser seguro es el one-time-pad

1.2 La necesidad de autenticación en sistemas con claves-públicas. Autenticación e Identificación Recordemos que autenticación es un término que es usado (y a menudo abusado) en un sentido muy extenso. Por lo mismo éste tiene un significado pequeño en cosas que llevan a la idea de que algún medio tiene que ser provisto de seguridad para las entidades, o dar seguridad de que la información no ha sido manipulada por partes no autorizadas. Autenticación es el objetivo específico de la seguridad que uno trata de alcanzar. Unos de los ejemplos para especificar los objetivos incluyen control de acceso, autenticación de las entidades, autenticación del mensaje, integridad de los datos, no tener rechazos, y autenticación de la clave.

Autenticación es uno de los objetivos más importantes de la seguridad de la información. Hasta mediados de los 1970s generalmente se creyó que secreto y autenticación estaban intrínsecamente conectados. Hasta que el descubrimiento de las funciones hash y las firmas digitales, dieron cuenta que el secreto y autenticación estaban separado en verdad y que la información era independiente de los objetivos de la seguridad. No parecería al principio importante separar los dos pero hay situaciones donde no es sólo útil sino esencial. Por ejemplo en la comunicación entre dos partes Maria y Juan, Maria está en un país y Juan en otro, ambos países no permiten secretos en el canal de comunicación; uno o ambos países quieren tener la posibilidad de supervisar todo tipo de comunicación. A Maria y Juan, de todas formas, les gustaría estar seguros de la identidad el uno del otro, y de la integridad y origen de la información que ellos enviarán y recibirán.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_8

El criptosistema de Rabin - SER El problema anterior ilustra varios aspectos independientes de la autenticación. Si Maria y Juan desean asegurarse de la entidad de cada uno, hay dos posibilidades a considerar. 1.- Maria y Juan pueden comunicarse sin retraso de tiempo. Esto es, ambos son activos en la comunicación de "tiempo real" 2.- Maria o Juan puede intercambiar mensajes con algún retraso. Esto es, pueden dirigir el mensaje a través de varias redes, que lo almacenan, y luego lo reenvían un tiempo más tarde. En el primer ejemplo Maria y Juan querrían verificar las identidades en tiempo real. Esto se puede lograr si por ejemplo Maria envía a Juan un mensaje-secreto o desafío, que sólo Juan pueda responder correctamente. Juan podría ejecutar una acción similar para identificar Maria. Este tipo de autenticación es comúnmente llamado autenticación de la entidad o simplemente identificación. Con respecto a la posibilidad del segundo no es conveniente mandar un mensaje-secreto o desafío y esperar una respuesta correcta, ya que el camino de la comunicación es sólo en una dirección. Técnicas diferentes son ahora necesarias para autenticar al originador del mensaje. Esta forma de autenticación es llamada autenticación del origen de los datos.

Autenticación de los datos en el origen. Definición: (Autenticación de los datos en el origen o autenticación de mensajes) Existen técnicas que proveen que una de las partes reciba un mensaje seguro (por evidencia corroborada) y la identidad de la parte que originó el mensaje. A menudo se proporciona un mensaje a B con información adicional para que B pueda determinar la identidad de la entidad que originó el mensaje. Esta forma de autenticación típica no provee ninguna garantía, pero es útil en situaciones donde una de las partes no es activa en la comunicación.

Ejemplo (Necesidad de la autenticación del origen de los datos) Uno le envía un mensaje a B por el correo electrónico. El mensaje puede viajar por sistemas de redes de comunicación y guardarse para enviarlo a B un tiempo más tarde. A y B no tienen usualmente una comunicación directa.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_9

El criptosistema de Rabin - SER A B le gustaría tener algún medio para verificar que el mensaje recibido y su contenido fueron originados verdaderamente por A. La autenticación del origen de los datos implícitamente provee la integridad de los datos ya que, si el mensaje fue modificado durante la transmisión, A podría no recibir el mensaje con el largo original. Pareciera que una criptografía con clave-pública es un sistema ideal, ya que no se requiere de un canal seguro para pasar la clave de encripción. Esto implica que dos entidades podrían comunicarse sobre en canal no seguro nunca teniendo claves de intercambio en el medio. Desgraciadamente, éste no es el caso. La Figura 1. 3 muestra cómo un adversario activo puede derrotar el sistema (decriptando el mensaje destinado a una segunda entidad) sin romper el sistema del encripción. Este es un tipo de personificación y es un ejemplo de fracaso protocolar. En este texto el adversario personifica a la entidad B y envía a la entidad A una clave-pública la cual A asume (incorrectamente) que es la clave-pública de B. El adversario intercepta el mensaje encriptado de A para B decriptándolo con su propia clave-privada d, reencriptando el mensaje bajo la clave-pública de B e, y lo envía a B. Esto destaca la necesidad de autenticar las claves públicas para lograr datos originales se debe autenticar la clave pública. Se debe convencer que ella está encriptada bajo una legítima clave pública de B. Afortunadamente las técnicas de clave pública también permiten una elegante solución a este problema.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_10

El criptosistema de Rabin - SER Hace algunos años, este tipo de sistemas no parecía tener ninguna ventaja en el mundo criptográfico, porque tradicionalmente la criptografía se usaba sólo con propósitos militares y diplomáticos, y en estos casos el grupo de usuarios es lo suficientemente pequeño cómo para compartir un sistema de claves. Sin embargo, en la actualidad, las aplicaciones de la criptografía han aumentado progresivamente, hasta alcanzar muchas otras áreas donde los sistemas de comunicación tienen un papel vital. Cada vez con mayor frecuencia se pueden encontrar grandes redes de usuarios en las que es necesario que dos cualesquiera sean capaces de mantener secretas sus comunicaciones entre sí. En estos casos, el intercambio continuo de claves no es una solución muy eficiente. Por otro lado, hay que resaltar la ventaja que representa en los sistemas asimétricos la posibilidad de iniciar comunicaciones secretas sin haber tenido ningún contacto previo. A continuación, nombramos algunos de los sistemas de clave pública que han tenido más trascendencia. •

Sistema RSA. Se basa en el hecho de que no existe una forma eficiente de factorizar números que sean productos de dos grandes primos.

•

Sistema de Rabin. Se basa también en la factorizacion.

•

Sistema de ElGamal. Se basa en el problema del logaritmo discreto.

•

Sistema de Merkle-Hellman. Esta basado en el problema de la mochila.

•

Sistema de McEliece. Se basa en la teoría de la codificación algebraica, utilizando el hecho de que la decodificación de un código lineal general es un problema NP-completo.

•

Sistemas basados en curvas elípticas. En 1985, la teoría de las curvas elípticas encontró de la mano de Miller aplicación en la criptografía. La razón fundamental que lo motivó fue que las curvas elípticas definidas sobre cuerpos finitos proporcionan grupos finitos abelianos, donde los cálculos se efectúan con la eficiencia que requiere un criptosistema, y donde el cálculo de logaritmos es aún más difícil que en los cuerpos finitos. Además, existe mayor facilidad para escoger una curva elíptica que para encontrar un cuerpo finito, lo que da una ventaja más frente a su predecesor, el sistema de ElGamal.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_11

El criptosistema de Rabin - SER

2. Descripción del problema Para poder conseguir un proyecto de software fructífero, analizamos y delimitamos correctamente el planteamiento del problema del Sistema de Encriptación de Rabin (SER) siguiente:

“ Se diseñara e implementara un Sistema de Encriptación de Rabin, que consiste en Implementar el Algoritmo del criptosistema propuesto por M. O. Rabin. El proyecto se desarrollara en el leguaje de programación JAVA. La cual nos permitirá poder hacer encriptaciones y decriptación de mensajes a través de este sistema. Y si el tiempo lo permite, se implementara una interfaz de usuario del sistema la cual le facilitara interactuar al cliente con el programa.”

3. Descripción del ámbito del SER. 3.1

Descripción General del Algoritmo de Rabin.

El sistema de llave asimétrica de Rabin se basa en el problema de calcular raíces cuadradas módulo un número compuesto. Este problema se ha demostrado que es equivalente al de la factorización de dicho número. En primer lugar escogemos dos números primos, p y q, ambos congruentes con 3 módulo 4 (los dos últimos bits a 1). Estos primos son la clave privada. La clave pública es su producto, n = pq. Para codificar un mensaje m, simplemente se calcula

c = m2 (mod n) La descodificación del mensaje se hace calculando lo siguiente: m1 = c(p+1)/4 (mod p) m2 = (p - c(p+1)/4) (mod p) m3 = c(p+1)/4 (mod q) m4 = (q -c(p+1)/4) (mod q)

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_12

El criptosistema de Rabin - SER Luego se escogen a y b tales que a = q(q -1 (mod p)) y b = p(p -1 (mod q)). Los cuatro posibles mensajes originales son ma = (am1 + bm3) (mod n) mb = (am1 + bm4) (mod n) mc = (am2 + bm3) (mod n) md = (am2 + bm4) (mod n) Desgraciadamente, no existe ningún mecanismo para decidir cuál de los cuatro es el auténtico, por lo que el mensaje deberá incluir algún tipo de información para que el receptor pueda distinguirlo de los otros.

3.2

Fundamentación del Algoritmo de Rabin.

Ahora presentaremos el Criptosistema de Rabin, el cual es computacionalmente seguro contra todo ataque de texto plano elegido bajo el supuesto que es computacionalmente in factible factorizar números de la forma n = p * q, donde p y q son primos. Sea n el producto de dos primos distintos p y q, con p, q ≡ 3(mod A). Sea P = C = Ζn y definamos

Para K =(n , p, q, B) definimos y

La clave pública es (n, B), y p y q se mantienen secretos. La función de encripción no es inyectiva, así que la decripción es ambigua. En efecto si w es una raíz cuadrada no trivial de 1, entonces para todo texto plano x hay tres valores distintos que producen el mismo texto cifrado , y son Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_13

El criptosistema de Rabin - SER

x, -x – B, w(x + B/2) – B/2, -w (x + B/2) – B/2. Por ejemplo:

Ek(w(x + B/2) – B/2) = (w(x + B/2) – B/2)*(w(x + B/2) – B/2) = w2 (x + B/2) 2 – B2/4 = x(x-B)(mod n) = x(x-B)(mod n) En general, el receptor del mensaje no tiene forma de distinguir entre estos cuatro textos planos posibles a menos que el texto plano contenga suficiente redundancia como para eliminar tres de las cuatro posibilidades. Para decriptar debemos resolver

o equivalentemente,

donde x1 = x + B/2. Sea entonces C = y + B2. Observemos que C es un residuo cuadrático si la encripción se hizo correctamente. Las soluciones de la ecuación (x1)2

=

C (mod n) se pueden obtener mediante el

Teorema Chino del Resto a partir de las soluciones de las ecuaciones:

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_14

El criptosistema de Rabin - SER Cada una de estas ecuaciones tiene dos raíces. Estas se pueden combinar para obtener las cuatro soluciones de la ecuación original (por el TCR). Por el criterio de Euler sabemos que si se encriptó correctamente C es un residuo cuadrático módulo p y módulo q. Pero esto no basta para poder resolver las ecuaciones. En realidad el elemento clave para esto es el hecho que p ≡ 3(mod 4) y q ≡ 4, pues en este caso tenemos un algoritmo determinista polinomial que nos permite calcular las raíces cuadradas de residuos cuadráticos módulo p o q. Las raíces de la primera ecuación vienen dadas por ±C(p+1)/4(mod p). En efecto: (±C(p+1)/4) 2

≡ C(p+1)/2(mod p). ≡ C(p-1)/2 C (mod p). ≡ C (mod p).

esto debido a que C es residuo cuadrático, luego por el criterio de Euler se tiene que: C(p-1)/2 ≡ 1(mod p). Análogamente, las raíces de la segunda ecuación son ±C(q+1)/4(mod q). Teniendo las soluciones de ambas ecuaciones se obtienen directamente las cuatro raíces de C módulo n usando el Teorema Chino del Resto. Cabe hacer dos observaciones: 1. El adversario no sabe cuál de las cuatro es la decripción correcta, pero el receptor tampoco. Esto se resuelve acordando ciertas reglas de redundancia en el mensaje (i.e. el mensaje se transmite como dos copias concatenadas, el tercer bit se repite tres veces, etc.) para poder distinguir cuál de las cuatro raíces corresponde al mensaje original. 2. Es interesante el hecho que para el caso en que un primo p es congruente a 1 modulo 4 no se conoce ningún algoritmo polinomial determinista para determinar las raíces cuadradas de residuos cuadráticos módulo p, i.e. el hecho que p ≡ 3 (mod 4) y q ≡ 4 (mod 3) es vital para el algoritmo de decripción (Sin embargo, se conoce un algoritmo probabilista de tiempo polinomial que cumple este propósito).

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_15

El criptosistema de Rabin - SER

3.3

Pasos del Algoritmo de Rabin.

Estos algoritmos son tomados de “Handbook of Applied Cryptography” [10].

Algorithm 1 Key generation for Rabin public-key encryption SUMMARY: each entity creates a public key and a corresponding private key. Each entity A should do the following: 1. Generate two large random (and distinct) primes p and q, each roughly the same size. 2. Compute n = pq. 3. A’s public key is n; A’s private key is (p; q).

Algorithm 2 Rabin public-key encryption SUMMARY: B encrypts a message m for A, which A decrypts. 1. Encryption. B should do the following: (a) Obtain A’s authentic public key n. (b) Represent the message as an integer m in the range {0,1, … , n – 1}. (c) Compute c = m2 mod n. (d) Send the ciphertext c to A. 2. Decryption. To recover plaintext m from c, A should do the following: (a) Use Algorithm 3 to find the four square roots m1,m2,m3, and m4 of c modulo n2. (See next Note). (b) The message sent was either m1,m2,m3, or m4. A somehow decides which of these is m.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_16

El criptosistema de Rabin - SER

Algorithm 3 Finding square roots modulo n given its prime factors p and q INPUT: An integer n, its prime factors p and q, and a ∈ Qn. OUTPUT: the four square roots of a modulo n. 1. Use Algorithm 4 to find the two square roots r and -r of a modulo p. 2. Use Algorithm 4 to find the two square roots s and -s of a modulo q. 3. Use the extended Euclidean algorithm to find integers c and d such that cp + dq = 1. 4. Set x ←(rdq + scp) mod n and y ← (rdq - scp) mod n. 5. Return(±x mod n, ±y mod n).

Algorithm 4 Finding square roots modulo a prime p INPUT: An odd prime p and a square a ∈ Qp. OUTPUT: the two square roots of a modulo p. 1. Choose random b ∈ Zp until b2 - 4a is a quadratic non-residue modulo p, i.e., (b2 -4a)/p = -1.. 2. Let f be the polynomial x2 - bx + a in Zp[x]. 3. Compute r = x(p+1)/2 mod f 4. Return(r, -r).

Note (finding square roots of c modulo n = pq when p ≡ q ≡ 3 (mod 4)) If p and q are both chosen to be ≡ 3 (mod 4), then Algorithm 4 for computing the four square roots of c modulo n simplifies as follows: 1. Use the extended Euclidean algorithm to find integers a and b satisfying ap + bq = 1. Note that a and b can be computed once and for all during the key generation stage. 2. Compute r = c (p+1)/4 mod p. 3. Compute s = c(q+1)/4 mod q. 4. Compute x = (aps + bqr) mod n. 5. Compute y = (aps - bqr) mod n. 6. The four square roots of c modulo n are x, -x mod n, y, and -y mod n.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_17

El criptosistema de Rabin - SER

3.4

Comentarios del Criptosistema de Rabin.

Ahora probaremos que el criptosistema de Rabin es computacionalmente seguro. Suponemos entonces que si existe un algoritmo A que conociendo n y B y dada una entrada y ∈ C entrega un x ∈ P tal que eK(x) = y. El siguiente algoritmo toma como entrada n y B y utiliza A como subrutina y factoriza el módulo n con probabilidad de a lo menos ½.

Existen varios puntos a explicar en este algoritmo. Primero observemos que:

Luego en el paso 3, A retorna un valor x ∈ P tal que:

De esta manera obtenemos que: Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_18

El criptosistema de Rabin - SER

donde w es una raíz cuadrada no trivial de 1 modulo n. Si x ≠ ± 1 (mod n) entonces como n|(x1 + r )(x1 - r) sigue que al calcular mcd((,x)1 + r, n) se obtiene p o q. Para determinar la probabilidad de éxito de quebrar el criptosistema de Rabin, definimos en Zn\{0} la relación de equivalencia.

Se verifica fácilmente que ~ es relación de equivalencia. Notar que la clase de equivalencia de un elemento r tiene cardinal

4 en efecto:

Pero todo elemento de [r] genera el mismo y ∈ C para el paso 2 y luego da lugar al mismo x1 en el paso 4. Luego con probabilidad de a lo menos ½ en el paso 1 se eligió un término tal que x ≠ ±r(mod n), luego el Criptosistema de Rabin es computacionalmente seguro bajo ataques de texto plano elegido bajo el supuesto que no existe un algoritmo probabilística eficiente que permita factorizar números de la forma n = p * q, p y q primos. Cabe hacer notar que bajo ataques de texto cifrado conocido el Criptosistema de Rabin es inseguro, dado que el algoritmo A es reemplazado por el algoritmo de decripción del Criptosistema de Rabin conocido por la persona que realiza el ataque.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_19

El criptosistema de Rabin - SER

4. Metodología de desarrollo para el diseño del SER. En los cifrados asimétricos o de clave pública, tal y como ya se definieron anteriormente, la clave de descifrado no se puede calcular a partir de la de cifrado. En 1975, dos ingenieros electrónicos de la Universidad de Standford, Whitfield Diffie y Martín Hellman[1], sugieren usar problemas computacionalmente irresolubles para el diseño de criptosistemas seguros. La idea consiste básicamente en encontrar un sistema de cifrado computacionalmente fácil (o al menos no difícil), de tal manera que el descifrado sea por el contrario, computacionalmente irresoluble a menos que se conozca la clave. Para ello, hay que usar una transformación criptográfica Tk de fácil aplicación, pero de tal manera que sea muy difícil hallar una transformación inversa Tk ^(-1) sin la clave de descifrado. Dicha función Tk es, desde el punto de vista computacional, no inversible sin cierta información adicional (clave de descifrado) y se llama función de una vía o función trampa. En estos esquemas se utiliza una clave de cifrado (clave pública) k que determina la función trampa Tk, y una clave de descifrado (clave secreta o privada) que permite el cálculo de la inversa Tk ^(-1). En consonancia con el espíritu de la criptografía moderna, y tal como sucedía en los sistemas simétricos, los algoritmos de cifrado y de descifrado son públicos, por lo que la seguridad del sistema se basa únicamente en la clave de descifrado. Según Diffie y Hellman, todo algoritmo de clave pública debe cumplir las siguientes propiedades de complejidad computacional: 1. Cualquier usuario puede calcular sus propias claves pública y privada en tiempo polinomial. 2. El emisor puede cifrar su mensaje con la clave pública del receptor en tiempo polinomial. 3. El receptor puede descifrar el criptograma con la clave privada en tiempo polinomial. 4. El criptoanalista que intente averiguar la clave privada mediante la pública se encontrará con un problema intratable. 5. El criptoanalista que intente descifrar un criptograma teniendo la clave pública se encontrará con un problema intratable.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_20

El criptosistema de Rabin - SER En la práctica el diseñador de algoritmos asimétricos se encuentra con cinco problemas numéricos distintos. Los tres primeros, correspondientes a las condiciones 1, 2 y 3, deben pertenecer a la clase polinomial. Los otros dos, correspondientes a las condiciones 4 y 5, son problemas complejos, preferiblemente NP-completos, ya que aunque un problema pertenezca a esta clase siempre puede darse algún ejemplo concreto que se resuelva en tiempo polinomial.

Cómo construir un criptosistema de Clave Pública En líneas generales, un esquema a seguir para la construcción de un criptosistema de clave pública es el siguiente: 1) Escoger un problema P difícil, a se posible intratable. 2) Escoger un subproblema de P fácil, P fácil

que se resuelva en tiempo polinomial,

preferiblemente en tiempo lineal. 3) Transformar el problema P fácil de tal manera que el problema resultante, P difícil, no se parezca al inicial, pero si al problema original P. 4) Publicar el problema P difícil y la forma en que debe ser usado, constituyendo este proceso la clave (pública) de cifrado. La información sobre cómo se puede recuperar el problema P fácil a partir del problema P difícil se mantiene en secreto y constituye la clave secreta de descifrado. Los usuarios legítimos utilizan la clave secreta para llevar a cabo el descifrado, convirtiendo el problema P difícil en el problema P fácil mientras que el criptoanalista tiene que enfrentarse forzosamente a la resolución del problema P difícil. En la construcción de criptosistemas se pueden observar diferencias entre los algoritmos para sistemas simétricos y los algoritmos usados en clave pública. En primer lugar existen mayores restricciones de diseño para un algoritmo asimétrico que para un simétrico, debido a que la clave pública representa información adicional que potencialmente un enemigo puede usar para llevar a cabo el criptoanálisis. Normalmente el algoritmo de clave pública basa su seguridad en la dificultad de resolver algún problema matemático conocido, mientras que algunos algoritmos simétricos, se diseñan de tal manera que las ecuaciones matemáticas que los describen son tan complejas que no son resolubles analíticamente.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_21

El criptosistema de Rabin - SER En segundo lugar, existen grandes diferencias en la generación de claves. En los algoritmos simétricos en los que el conocimiento de la clave de cifrado es equivalente a la de descifrado, y viceversa, la clave se puede seleccionar de forma aleatoria. Sin embargo, en los algoritmos asimétricos, como la relación entre la clave de cifrado y la de descifrado no es pública, se necesita un procedimiento para calcular la pública a partir de la clave privada que sea computacionalmente eficiente y tal que el cálculo inverso sea imposible de realizar. Después de lo señalado hasta ahora hay que mencionar tres problemas o inconvenientes que se suelen presentar en la Criptografía de Clave secreta : 1. Distribución de claves Dos usuarios tienen que seleccionar una clave en secreto antes de empezar a comunicarse, lo que deberán hacer bien personalmente (cosa que no siempre es posible ), bien por medio de un canal inseguro. 2.

Manejo de claves. En una red de n usuarios cada pareja debe tener su clave secreta particular, lo que hace un total de n(n-1)/2 claves para esa red.

3.

Sin firma digital. Una firma digital es lo análogo a una firma digital o rúbrica, pero en una red de comunicaciones. En los criptosistemas de clave secreta no hay posibilidad, en general , de firmar digitalmente los mensajes, con lo que el receptor del mismo no puede estar seguro de que quien dice que le envia el mensaje sea realmente quien lo ha hecho.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_22

El criptosistema de Rabin - SER

5. Diseño e Implementación del Sistema de Encriptación de Rabin. Para el desarrollo del diseño e Implementación se tomaron en consideración dos cosa: 1. El lenguaje de programación. 2. Y el protocolo de encriptación y desencriptación. Estos dos punto se deben principalmente a que estos determinan la forma de organizar el concepto del modelo de programación, y la forma de poder controlar el flujo de datos entre los diferentes módulos. El desarrollo de este punto dentro del reporte se describe de la siguiente reporte. Inicialmente se discutirá el diseño del sistema; a partir de esto se discutirá los puntos mas importantes que se deben tomar en cuenta sobre la implantación con base al diseño. En seguida se describirá la implementación de cada uno de los módulos. Y por ultimo se explica el diseño y funcionamiento de la interfase de usuario para el sistema SER.

5.1 Diseño del Sistema de SER.

RabinFrame

SetKey

DecryptMessage

Roots

EncryptMessage

EEC

Figura 5.1: Interrelación de las clases del sistema SER. Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_23

El criptosistema de Rabin - SER Como se muestra en la figura 5.1 se muestra el concepto de la Programación Orientada a Objetos, que esta basada en dividir el problema en entidades que realizan un o varias funciones para el Sistema. En este caso el Sistema se divide en 6 clases principales, mas una clase que sirve como la clase que se encarga de ejecutar el Sistema. La figura 5.1 muestra una clase llamada RabinFrame; que es, la que hace uso de todas las clases, esto se debe a que la clase contiene la interfaz del sistema y dentro de esa Interfaz hace llamadas (agregación de los objetos) al resto de las 5 clases que se implementan. Hay tres clases importantes dentro del Sistema de Encriptación de Rabin; y estas son las clases KeySet, DecryptMessage y EncryptMessage; Esta división es obvia por la simple razón de que el sistema realiza estas tres tareas. Las ultimas dos clases hasta ahora no mencionadas son parte importante para que la clase DecryptMessage realice su tarea de desencriptar el mensaje. Entre estas dos clases, la mas importante para el sistema es la EEC, que realmente es la implantación del Algoritmo extendido de Euclides y la pieza clave dentro de la implementación.

Figura 5.2. Relación que guardan las tres clases. La clase DescryptMessage agrega a ella a la clase Roots y a su vez la clase Roots a la clase EEC.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_24

El criptosistema de Rabin - SER En la etapa de diseño del Sistema; se basa principalmente en las diferentes pruebas de programación que se hacen antes de poder valorar y cuantificar el poder del lenguaje de programación. En este caso se escogió Java.

5.2 Transición del Diseño a Implementación. Uno de los problemas principales que se enfrenta con los lenguajes de programación, es implementar la Aritmética de precisión infinita. Por ejemplo en C o C++, esta implementación se debe de realizar a fuerza, si se quiere realizar un criptosistema seguro. Pero primeramente, Que es Aritmética de precisión infinita?

5.2.1

Aritmética de precisión Infinita.

Sistemas de numeración posicionales. En los sistema de numeración posicionales, el valor de una cifra depende del lugar que ésta ocupe dentro del número. El más conocido es el sistema decimal. En el número decimal 221 el dígito 2 figura dos veces, pero el de la derecha representa 2 decenas mientras que el de la izquierda representa dos centenas. Generalizando, en un sistema de numeración posicional de base b, la representación de un número se define a partir de la regla: (… a3 a2 a1 a0.a-1 a-2 a-3 …)b = … + a2 b2 + a1 b1 + a0 b0 + a-1 b-1 + a-2 b-2 + a-3 b-3 + …(1) Por ejemplo, (423.1)6 = 4⋅62 + 2⋅61 + 3⋅60 + 1⋅6-1. Cuando b es diez y los ai se eligen del conjunto de dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 se trata del sistema decimal; y en este caso el subíndice b de la expresión (1) puede omitirse. Las generalizaciones más simples del sistema decimal se obtienen cuando b es un entero no negativo mayor a 1 y cuando los ai pertenecen al conjunto de enteros en el rango 0 ≤ ai < b. Así, cuando b es 2 se obtiene el sistema de numeración binario, cuando b es 8 el octal y cuando b es 16 el hexadecimal. Pero en general, se podría elegir cualquier b distinto de cero, y los ai de cualquier conjunto de números, obteniendo sistemas muy interesantes (ver [1] para más información). Números de precisión finita Al hacer operaciones aritméticas, en muy raras ocasiones uno se preocupa por la cantidad de dígitos decimales que son necesarios para representar a un número. Se puede calcular que hay 1078 electrones en el universo sin molestarse por el hecho de que se requieren 79 lugares decimales para escribir el número completo. Una persona que evalúa una función a mano buscando una solución de 6 dígitos significativos, simplemente trabaja con resultados intermedios de 7, 8 o cuantos dígitos necesite. Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_25

El criptosistema de Rabin - SER

Con las computadoras, las cosas son bastante diferentes. En la mayoría de las computadoras, la cantidad de memoria disponible para guardar números se fija en el momento de su diseño. Con un poco de esfuerzo, el programador puede llegar a representar números 2 o 3 veces más grandes que este tamaño prefijado, pero al hacerlo no termina de cambiar la naturaleza del problema: la cantidad de dígitos disponibles para representar un número siempre será fija. Llamaremos a estos números: números de precisión finita. Para poder estudiar las propiedades de los números de precisión finita, se examinará el conjunto de los números enteros positivos que se pueden representar con tres dígitos decimales, sin punto decimal ni signo. Este conjunto tiene exactamente 1000 elementos: 000, 001, 002, 003, …., 999. Con estas restricciones es imposible representar algunos conjuntos de números enteros, como ser: 1. 2. 3. 4. 5.

Números mayores a 999 Números negativos Fracciones Números irracionales Números complejos

El conjunto de los números enteros tiene la propiedad de ser cerrado con respecto a la suma, resta y multiplicación. Es decir, para todo par de enteros a y b, a + b, a - b y a x b son también enteros. Pero el conjunto de enteros no es cerrado con respecto a la división ya que existen enteros a y b para los cuales el resultado de a / b no es un número entero. Desafortunadamente, el conjunto de los números de precisión finita no es cerrado con respecto a las operaciones aritméticas básicas, como se muestra a continuación, usando números de tres dígitos decimales como ejemplo: 600 + 600 = 1200 003 - 005 = -2 050 x 050 = 2500 007 / 002 = 3,5

(muy grande) (negativo) (muy grande) (no es un entero)

Las exclusiones se pueden dividir en dos clases: las operaciones cuyo resultado es mayor al máximo número del conjunto (error de overflow) o menor al mínimo número del conjunto (error de underflow), y las operaciones cuyos resultados simplemente no pertenecen al conjunto. De las cuatro exclusiones del ejemplo, las primeras tres pertenecen a la primera categoría y la última a la segunda. Como las computadoras tienen memoria finita y por lo tanto, deberán realizar operaciones sobre números de precisión finita, los resultados de algunos operaciones serán, desde el punto de vista matemático, totalmente erróneos. Una calculadora que da la respuesta incorrecta aunque todos sus circuitos estén funcionando en perfectas condiciones puede resultar extraña al principio, pero el error que comete es una consecuencia lógica de su naturaleza finita. Algunas computadoras tienen hardware que detecta los errores de overflow. El álgebra de los números de precisión finita es bastante diferente al álgebra al que estamos acostumbrados. Por ejemplo, consideremos la ley asociativa: a + (b - c) = (a + b) - c Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_26

El criptosistema de Rabin - SER

Evaluemos ambos lados de este igualdad con los siguientes valores: a = 700, b = 400, c = 300. Para calcular el término de la izquierda, primero evaluamos (b - c) que es 100, valor que sumamos a a, obteniendo 800. Para calcular el término de la derecha calculamos primero (a + b), que resulta en un error de overflow en aritmética de números de 3 dígitos decimales. El resultado dependerá de la máquina que se esté usando, pero no se puede garantizar que sea 1100. Al restar 300 de un número que es distinto de 1100, jamás obtendremos 800. La ley asociativa no se cumple, por lo tanto el orden de las operaciones es importante. Como otro ejemplo, consideremos la ley distributiva: a x (b - c) = a x b - a x c Si evaluamos ambos lados de la igualdad con a = 5, b = 210 y c = 195, el término izquierdo es 5 x 15 dando 75. El término de la izquierda no es 75 porque a x b resulta en un error de overflow. A juzgar por estos ejemplos, uno podría concluir que aunque las computadoras son máquinas de propósito general, su naturaleza finita las hace inadecuadas para llevar a cabo operaciones aritméticas. Esta conclusión, por supuesto, no es verdadera, pero sirve para mostrar lo importante que es saber cómo trabajan las computadoras y cuáles son sus limitaciones.

5.2.2 Que ofrece Java para la Aritmética de precisión Infinita. Package java.math Description Provides classes for performing arbitrary-precision integer arithmetic (BigInteger) and arbitraryprecision decimal arithmetic (BigDecimal). BigInteger is analogous to Java's primitive integer types except that it provides arbitrary precision, hence operations on BigIntegers do not overflow or lose precision. In addition to standard arithmetic operations, BigInteger provides modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous operations. BigDecimal provides arbitrary-precision signed decimal numbers suitable for currency calculations and the like. BigDecimal gives the user complete control over rounding behavior, allowing the user to choose from a comprehensive set of eight rounding modes Class BigInteger. Immutable arbitrary-precision integers. All operations behave as if BigIntegers were represented in two's-complement notation (like Java's primitive integer types). BigInteger provides analogues to all of Java's primitive integer operators, and all relevant methods from java.lang.Math. Additionally, BigInteger provides operations for modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous operations.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_27

El criptosistema de Rabin - SER

5.3 Implementación del Sistema de Encriptación de Rabin. El desarrollo de este punto radica principalmente en la explicación de la clase y su implementación de la misma. Solo se explican las cinco clases que forman la medula del sistema, con respecto a la interfase solo se detalla el funcionamiento para el usuario.

5.3.1| Implementación de la clase KetSet Esta clase es la encarga de generar las llaves publicas y privadas a partir del hecho que: n = p * q, donde p y q son números primos muy grandes. Con esto, se definen como llave privada el par de primos grandes (p , q) y como llave publica el resultado del producto de los dos numeros primos ( n ). Esta clase esta conformada por 3 variables que representan las llaves y los cinco métodos que las generan y las muestran.

KetSet q, p, n KeySet( ); getPrime ( ); getP ( ); getQ ( ); getN ( );

Los métodos mas importantes para ser explicados son los siguientes:

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_28

El criptosistema de Rabin - SER

public KeySet (int size) { Size = size; long time = System.currentTimeMillis(); p = getPrime(time); while((p.mod(four)).compareTo(three) != 0){ time += 8; p = getPrime(time); } time = System.currentTimeMillis(); q = getPrime(time); while((q.mod(four)).compareTo(three) != 0) { time += 12; q = getPrime(time); } n = p.multiply(q); }

El constructor de la clase KeySet es realmente la encargada de generar las llaves n, p y q: aplicando n = p*q.

Para poder generar un numero primo aleatorio grande se utiliza el constructor de la clase BigInteger, como se muestra en la especificación. Para mas informes ver la documentación de java 1.4.0.01 [11].

BigInteger(int bitLength, int certainty, Random rnd) Constructs a randomly generated positive BigInteger that is probably prime, with the specified bitLength.

Este método getPrime, hace uso del constructor BigInteger para generar el primo largo. Como argumento se obtiene un numero de tipo long, la cual se utiliza para generar un numero aleatorio que a su vez servia para obtener el numero primo largo. private static BigInteger getPrime ( long n ) { Random num = new Random(n); BigInteger prime = new BigInteger(Size, 100, num); return prime; }

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_29

El criptosistema de Rabin - SER

5.3.2 Implementación de la clase EncryptMessage. En este caso, la clase esta formada por tres métodos; pero realmente el mas importante de explicar es el encipher( ).

EncryptMessage q, p, n plainText cipherText

EncryptMessage( n , plainText)

getCipherText() getPlainText() encipher()

/* Matodo que encripta el Mensaje de plainText.*/ public void encipher() { StringTokenizer t = new StringTokenizer(plaintext, "\n"); while ( t.hasMoreTokens()) { // El mensaje se almacena linea a linea, en cipherText. String s = new String(); s = t.nextToken(); // Adiciona un bit extra al final de plaintext(Parte del Protocolo). byte[] temp = s.getBytes(); // Transforma una cadana a Bytes con el byte[] rabinbytes = new byte[temp.length + 1]; // objeto de obtener el tamaño del numero // bytes de cada cadena. System.arraycopy(temp, 0, rabinbytes, 0, temp.length); // Protocolo de reconocimiento. System.arraycopy(rabinbytes, (rabinbytes.length - 2), rabinbytes, (rabinbytes.length - 1), 1); BigInteger m = new BigInteger(rabinbytes); // Transforma la linea de mensaje en un BigInteger. c = m.modPow(two, n); ciphertext += c.toString() ; ciphertext += "\n"; } System.out.println("cipher text Completo: " + ciphertext); }

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_30

El criptosistema de Rabin - SER Este método tiene realmente dos puntos de interesantes. Primero, se sigue al pie de la letra el algoritmo de encriptación, pero la representación del mensaje se realiza por medio de una secuencia de mensajes mas pequeños; Estos mensajes son una línea del plainText, es decir que cada línea de texto representa un submensaje, la cual se debe de encriptar. Segundo; Además como sabemos que el algoritmo de desencriptación se debe de obtener 4 raíces, se agrega a cada línea el ultimo carácter dos veces con objeto de identificar la raíz indicada o correcta.

5.3.3 Implementación de la clase EEC. Antes que nada debemos explicar un poquito que es el Algoritmo de Euclides. Algoritmo de Euclides básico y extendido Algoritmo de Euclides Sirve para calcular el máximo común divisor de dos números a y b. Para enunciar este algoritmo nos serviremos de una proposición y un teorema previos. Proposición Sean a ≤ b con b ≠ 0, por el algoritmo de la división tendremos que a = bq + r. Entonces se cumple: 1) Los divisores comunes de a y b también son divisores de r 2) Los divisores comunes de b y r también son divisores de a Demostración: (1) Sea c tal que c|a, c|b, entonces a = cq1, b = cq2. Luego cq2q + r = cq1 ⇒ r = c(q1 – q2·q) ⇒ c|r. (2) Supongamos ahora c tal que c|b, c|r. Por tanto b = cq1, r = cq2 y tendremos a = cq1q + cq2 ⇒ a = c(q1q+q2) ⇒ c|a. Teorema En una división el máximo común divisor del dividendo y el divisor es igual al máximo común divisor del divisor y el resto, es decir, si a = bq + r, con a, b, q, r∈Z, b ≠ 0, se cumple mcd(a,b) = mcd(b,r). Demostración: Como vimos antes, dividendo y divisor tienen los mismos divisores que divisor y resto. Por tanto, ambos tendrán el mismo máximo común divisor.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_31

El criptosistema de Rabin - SER Algoritmo de Euclides Como mcd(a,b) = mcd(|a|,|b|), podemos suponer sin perdida de generalidad que a ≥ b > 0. Dividimos a por b, a = bq1 + r1 , con 0 ≤ r1< b Si r1 = 0, ya que a ≤ b, es obvio que b = mcd(a,b) y hemos terminado. Si r1 ≠ 0, dividimos b por r1, b = r1q2 + r2 , con 0 ≤ r2 < b Si r2 = 0, entonces mcd(b,r1) = r1 y por el teorema anterior mcd(b,r1) = r1 = mcd(a,b). Si r2 ≠ 0 continuamos dividiendo r1 por r2, y así sucesivamente De este modo obtenemos un conjunto de números r1 > r2 >...., de modo que llegaremos a un rn = 0. Entonces: rn–1 = mcd(rn–2, rn–1) =...= mcd(b,r1) = mcd(a,b) Nota.- El número de pasos necesarios es como máximo 5 veces el número de dígitos del número más pequeño de entre los a, b por los que comenzamos a calcular el máximo común denominador

Algoritmo extendido de Euclides Sirve para hallar los términos de la combinación lineal que da origen al máximo común divisor. Para ello se realiza el proceso inverso al seguido en el algoritmo de Euclides. Vamos a verlo con un ejemplo: Ejemplo: Calcular mcd(3120,270) y los números x, y tales que mcd(3120,270) = 3120x + 270y. 1.- Algoritmo de Euclides: 3120 = 11·270 + 150 270 = 1·150 + 120 150 = 1·120 + 30 120 = 4·30 + 0 30 = mcd(120,30) = mcd(150,120) = mcd(270,150) = mcd(3120,270) 30 = mcd(3120,270) 2.- Algoritmo extendido de Euclides: Realizamos el camino inverso al algoritmo de Euclides empezando por la expresión donde el máximo común divisor es igual al resto. Iremos sustituyendo valores con el objeto de llegar a los números de los que se hallo el máximo común denominador. 150–1·120 = 30 150–1·(270–1·150) = 30 → 150–270+150 = 30 → 2·150–270 = 30 2·(3120–11·270)–270 = 30 → 2·3120–22·270–270 = 30 → 2·3120–23·270–270 = 30 Así pues, mcd(3120, 270) = 30 = 2·3120+(–23)·270. Luego, x = 2, y = –23.

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_32

El criptosistema de Rabin - SER -

Algoritmo de Euclides extendido: Si mcd (a,b) = c, entonces c se puede expresar como combinación lineal de a y b, es decir, existen dos números k1 y k2 tal que: c = k1*a + k2*b, con k1 y k2 números enteros. Dicho algoritmo determina los valores de k1 y k2 . Se trata de ir despejando en el Algortimo de Euclides desde la última división obtenida hasta llegar a la primera.

EEC A B D

EEC(p_ in, q_in); Compute( ); getA( ); getB( ); getD( );

/* * @(#)proyectos.Encriptamiento de Rabin * @author Oscar G. Landa Rosales * @version 1.0, 4/07/2002 * @since JDK_1.4.0 */ import java.math.*;

4/07/2002

/********************************************************* *Inmplementacion del algoritmo extendido de Euclides. *********************************************************/ class EEC{ private BigInteger p,q; // private BigInteger p,q; private BigInteger a,b,d; private BigInteger x1,x2,y1,y2,t1,t2; public EEC(BigInteger pin, BigInteger qin){ p = pin; q = qin; } public void compute( ){ Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_33

El criptosistema de Rabin - SER if (q.equals(BigInteger.valueOf(0))) { d = p; a = BigInteger.valueOf(1); b = BigInteger.valueOf(0); } else { x2 = BigInteger.valueOf(1); x1 = BigInteger.valueOf(0); y2 = BigInteger.valueOf(0); y1 = BigInteger.valueOf(1); while(q.compareTo(BigInteger.valueOf(0)) > 0){ t1 = p.divide(q); t2 = p.add((t1.multiply(q)).negate()); a = x2.add((t1.multiply(x1)).negate()); b = y2.add((t1.multiply(y1)).negate()); p = q; q = t2; x2 = x1; x1 = a; y2 = y1; y1 = b; } d = p; a = x2; b = y2; } } public BigInteger getD( ){ return d; } public BigInteger getA( ){ return a; } public BigInteger getB( ){ return b; } }

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_34

El criptosistema de Rabin - SER

5.3.4 Implementación de la clase Roots. Roots q, p, n plainText cipherText

Roots( p_in, q_in, cipherText)

computeRoots( )

/* * @(#)proyectos.Encriptamiento de Rabin 24/07/2002 * * "Codigos y Criptografia" * CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS AVANZADOS DEL * INSTITUTO POLITECNICO NACIONAL. [CINVESTAV-IPN] * CINVESTAV - IPN * * Encuentra las cuatro raíces m1, m2, m3 y m4 de [c mod (n^2)]. * * @author Oscar G. Landa Rosales * @version 1.0, 24/07/2002 * @since JDK_1.4.0 * */ import java.math.*; import java.util.*; public class Roots{ private final BigInteger one = BigInteger.valueOf(1); private final BigInteger four = BigInteger.valueOf(4); private BigInteger p; private BigInteger q; private BigInteger n; private BigInteger cipher; private BigInteger roots[] = new BigInteger[4];

Oscar Gonzalo Landa Rosales

- Códigos y Criptografía Página_35

El criptosistema de Rabin - SER

/* Como argumentos se ingresa p, q y ciphertext. */ public Roots(BigInteger pin, BigInteger qin, BigInteger c){ p = pin; q = qin; n = p.multiply(q); cipher = c; } /* Optiene las raices r, s, x, y de */ public BigInteger[] computeRoots( ) { BigInteger a, b, r, s, x, y, exp; EEC eec; exp = p.add(one).divide(four); r = cipher.modPow(exp, p);

Se sigue los pasos del algoritmo tradicional, para obtener las 4 raíces. Se calcula r = c (p+1)/4 mod p. Se calcula s = c(q+1)/4 mod q.

exp = q.add(one).divide(four); s = cipher.modPow(exp, q); if (p.compareTo(q) > 0){ eec = new EEC(p,q); } else { eec = new EEC(q,p); } eec.compute(); a = eec.getA(); b = eec.getB();

Se calcula el Algoritmo Extendido de E. Se calcula x = (aps + bqr) mod n. Se calcula y = (aps - bqr) mod n. 6. Las cuatro raices del c mod n son: x, -x mod n, y, and -y mod n.

x = a.multiply(p).multiply(s).add(b.multiply(q).multiply(r)).mod(n); y = a.multiply(p).multiply(s).add(b.multiply(q).multiply(r).negate()).mod(n); roots[0] = x; roots[1] = y; roots[2] = x.negate().mod(n); roots[3] = y.negate().mod(n); if(cipher.compareTo(roots[0].modPow(BigInteger.valueOf(2),n)) != 0) System.out.println("Raiz No Valida -> x y -x -y