Dr. Jorge Ramió Aguirre

En esta sexta lección del curso nos dedicaremos a analizar la importancia de utilizar un teorema de las matemáticas discretas, el teorema chino del resto, también conocido como teorema del resto chino TRC. Con ello optimizaremos algunas operaciones en RSA.

Si deseas ver todas las diapositivas de las 10 lecciones de este curso en formato Power Point animado o bien en pdf, puedes descargar el archivo desde esta dirección.

IMPORTANTE: Aunque existe un enlace directo a cada ejercicio y práctica de esta lección, éstos se encuentran todos juntos en el documento anexo [PDF-Ejercicios-Prácticas RSA06] de esta lección, que te recomiendo lo descargues e imprimas ahora mismo.

Recuerda que el tiempo máximo recomendado para el seguimiento de esta lección, la realización de sus prácticas y ejercicios, así como la búsqueda de información en la red sobre los temas abiertos planteados al final de cada apartado, es de dos semanas.

Temario

Objetivos

Software que vas a utilizar en esta lección


APARTADO 6.1. ¿POR QUE SE RECOMIENDA USAR ESTE TEOREMA?

Ya hemos comentado que los sistemas de cifra con clave pública o asimétricos son muy lentos si los comparamos con los algoritmos de cifra simétrica, por el tipo de operaciones que deben realizar. En el primer caso, normalmente se trata de una elevación a potencia o exponenciación (RSA, Elgamal) y en el segundo (TDES, AES, etc.), será un conjunto de operaciones lógicas y desplazamientos de bits en registros que les convierte en unas mil veces más rápidos que los primeros.

Como la operación que se realiza para la cifra RSA es Nclave mod n, siendo n un cuerpo de al mínimo 1.000 bits producto de dos primos y recomendable en la actualidad 2.048 bits, nuestro talón de Aquiles estará en los valores que puedan tomar el número N que se cifra y/o la clave que usemos en el exponente en dicha cifra dentro del cuerpo n.

Dejando de lado -de momento- consideraciones de relleno o padding que veremos más adelante, en un intercambio de clave entre un cliente Cl y un servidor Sv, por ejemplo una clave de sesión Ks de 256 bits para el algoritmo simétrico AES, la operación que debe realizar el cliente será de este orden: C = KseSv mod nSv = 256 bits 17 bits mod 2.048 bits Siendo obviamente C un criptograma de 2.048 bits.

Pero como ya hemos visto, en la práctica la clave privada del servidor dSv será un número muy cercano a los 2.048 bits. Por tanto la operación que debe realizar el servidor para recuperar el secreto recibido y recuperar el valor de Ks será del orden: Ks = CdSv mod nSv = 2.048 bits 2.048 bits mod 2.048 bits Y esta operación es muy costosa en términos de cómputo.

Es aquí donde entra en acción el teorema chino del resto , en el descifrado de un intercambio de clave, en tanto las dimensiones de todos los números que intervienen en la ecuación son muy grandes. El servidor, en vez de realizar el descifrado en el cuerpo n de 2.048 bits, al ser dueño de la clave y poseer los primos p y q, podrá realizar un conjunto de operaciones para el descifrado de ese criptograma pero en los cuerpos p y q de la mitad de tamaño en bits que el cuerpo de cifra n y, por tanto, reduciendo de una manera significativa el tiempo de cómputo.

Así, en nuestro ejemplo el servidor Sv realizará operaciones modulares en 1.024 bits, en vez de 2.048 bits, una diferencia inmensa. Se trata de un atajo que sólo posee el dueño de la clave y que optimizará de forma notoria el tiempo de cálculo, en teoría unas 4 veces más rápido. Mira por ejemplo el apartado Faster RSA Implementation Using the Chinese Remainder Theoremde esta página Web o bien el apartado RSA-CRT Decryption: Performance en este artículo en PDF.

En la siguiente lección de este curso, dedicada a la generación de claves RSA con el software estándar OpenSSL, veremos que este programa al generar dicha clave nos entrega tres valores extras que son, precisamente, para usar el TRC en el descifrado. Por último, destacar que El teorema chino del resto tiene otras utilidades, que sólo esbozaremos en esta lección.

Cuestiones para reflexionar e investigar: 1. ¿Habías oído hablar antes del TRC? 2. ¿Si el TRC mejora en unas cuatro veces la velocidad de cómputo en una operación de descifrado, ¿sería equivalente a decir que reduce más de un 70% el tiempo de cálculo? 3. ¿Qué dice la complejidad algorítmica sobre el número de operaciones que deben realizarse en expresiones como Ne mod n cuando el valor del exponente e se duplica? Mira esta página Web sobre Análisis de la complejidad de los algoritmos del profesor José Antonio Mañas de la UPM.

APARTADO 6.2. DEFINICION DEL TEOREMA CHINO DEL RESTO Y SU USO EN RSA

Si bien podrás encontrar infinidad de sitios Web y documentos que traten este teorema, por ejemplo simplemente consultando en Google, lo cierto es que no existen demasiados documentos que expliquen de forma detallada y clara porqué puede usarse el TRC en una expresión del tipo Ab mod n, cuando n es el producto de dos primos p y q como es el caso de RSA.

Lo que sigue a continuación es la documentación generada por la profesora Dña. Ana Isabel Lías Quintero, del Departamento de Matemática Aplicada de la EUI UPM, a quien he pedido su colaboración para el contenido de este apartado y que desde aquí agradezco su trabajo. Las notaciones serán algo diferentes a las utilizadas en lecciones anteriores, pero sin embargo muy fáciles de seguir.

RSA: Cómo aplicar el TRC para ganar en eficiencia

La complejidad computacional del cálculo del texto en claro M = Cd mod n depende de d y n. De hecho, es O (lg d * lg2 n). Los tamaños de n y d son los que determinan la complejidad. Si k = máx {tam (n), tam (d)}, la complejidad es O (k3).

En lo siguiente veremos una forma de reducir el número de operaciones del cálculo de Cd mod n; para ello será fundamental el teorema chino del resto. En el caso de RSA, n = p * q, siendo p y q primos, y el enunciado del teorema quedaría:

Sean p, q primos distintos y n = p * q. Sean x1, x2. El sistema: x ≡ x1 mod p x ≡ x2 mod q Tiene solución, que además es única módulo n.

Dicha solución es de la forma: x = [x1 q (q-1 mod q) + x2 p (p-1 mod p)] mod n siendo:   q-1 = inv (q, p);    p-1 = inv (p, q)

En el ejercicioRSA6.2.1 realizarás algunos cálculos usando la ecuación anterior con la ayuda del software Fortaleza de Cifrados para comprobar el resultado que te entrega el TRC.

Tal vez aún no le encuentres sentido ni utilidad al planteamiento de este par de ecuaciones y la solución de x en n. No te preocupes, más adelante verás y comprobarás las aplicaciones reales que puede tener este teorema.

Hay otro resultado que, combinando con el TRC, es de gran utilidad.

Prop 1:    a ≡ b mod n    ⇒    a ≡ b mod d     para todo d divisor de n

Por ejemplo, si n = 585 = 32 5 13, entonces dado que el resto de dividir 1.263 x veces por 585 es 93, podemos concluir que: 1.263 ≡ 93 mod 585 Si tomamos ahora el número 65 = 5 * 13, divisor de 585: 1.263 ≡ 28 mod 65 y 93≡ 28 mod 65. Por tanto, 1.263 y 93 son congruentes mod 65, por transitividad.

Si conjugamos ambas propiedades, obtenemos el siguiente corolario:

Prop 2:    Sea n = p * q    con p y q primos distintos Entonces, para todo a, b ∈ a ≡ b mod n    ⇐⇒    a ≡ b mod p  y   a ≡ b mod q

La aplicación de la Prop 2 es una primera simplificación del cálculo de M = Cd mod n. Resolvemos esta ecuación realizando las siguientes operaciones: M ≡ Cd mod p (I) M ≡ Cd mod q (II)

Ventajas:

  1. En lugar de hacer cálculos mod n, los hacemos módulo p y q, cuyos tamaños son del orden de la mitad del de n.
  2. Los cálculos de (I) y (II) se pueden hacer en paralelo.

¿Hay más reducciones?

Sí, hay dos más. Las propiedades matemáticas en las que se basan son las siguientes.

Prop 3: Sea p primo y mcd (a, n) = 1. Entonces, Si r ≡ t mod Φ(p)    ⇒    ar ≡ at mod p Recuerda que como p es primo, Φ(p) = p - 1.

Vas a comprobar en el ejercicioRSA6.2.2 una aplicación de la Prop 3 al realizar la operación 23.104 mod 101 de una manera óptima.

La aplicación de esta Prop 3 nos permite una segunda simplificación del cálculo de M = Cd mod n: Cd mod p ≡ Cd mod (p-1) mod p ≡ Cpd mod (p-1) mod p    (con Cp = C mod p) Cd mod q ≡ Cd mod (q-1) mod q ≡ Cqd mod (q-1) mod q    (con Cq = C mod q) Si dp = d mod (p-1) y dq = d mod (q-1), entonces: Cd mod p ≡ Cpdp mod p Cd mod q ≡ Cqdq mod q

Ventajas:

  1. Aunque el tamaño de la clave privada d es del orden de tamaño del módulo n, los tamaños de dp y dq son del orden de la mitad.
  2. Además, dichos valores pueden calcularse una sola vez y tenerlos almacenados para descifrados posteriores.

Por último, para calcular el inverso modular podemos usar el Pequeño Teorema de Fermat que indicaremos como Prop 4.

Prop 4: Sea primo y mcd (a, p) = 1. Entonces a-1 = inv (a, p) ≡ ap-2 mod p (Pequeño Teorema de Fermat)

Retomando la ecuación del TRC, obtenemos: x = [x1 q (q-1 mod q) + x2 p (p-1 mod p)] mod n en donde: x1 = Cpdp mod p x2 = Cqdq mod q p-1 = pp-2 mod p q-1 = qq-2 mod q

Un último paso: la fórmula de Garner

Existe una última optimización basada en la siguiente regla conocida como fórmula de Garner propuesta por el matemáticoHarvey L. Garner.

Para obtener x mod n con n = p q, a partir de   x ≡ x1 mod p y x ≡ x2 mod q, debemos hacer: x = x1 + h p, en donde h = [(x2 - x1)(p-1 mod q)] mod q

En el ejercicioRSA6.2.3 comprobarás la validez de la fórmula de Garner.

Procedimiento final y complejidad asociada

Para calcular M = Cd mod n, con n = p q, hacemos: Precalcular estos valores: 1) dp = d mod (p-1) 2) dq = d mod (q-1) 3) p-1 mod q = pq-2 mod q Realizar operaciones de descifrado con el criptograma C: Paso 0: Calcular Cp = C mod p;   Cq = C mod q Paso 1: Calcular x1 = Cpdp mod p Paso 2: Calcular x2 = Cqdq mod q Paso 3: Calcular h = [(x2 - x1)(p-1 mod q)] mod q Paso 4: Devolver x = x1 + h p

En cuanto a la complejidad, podemos decir lo siguiente:

  1. Los pasos más costosos son el 1 y el 2.
  2. El paso 1 tiene una complejidad del orden (k/2)3
  3. El paso 2 tiene una complejidad del orden (k/2)3
  4. Los pasos 0, 3 y 4 son sumas y productos, que tienen una complejidad a lo sumo cuadrática en k.

Por lo tanto, sin contar con el preprocesamiento:

  1. Si los pasos 1 y 2 se paralelizan, este método es del orden de 8 veces más rápido.
  2. Si los pasos 1 y 2 no se paralelizan, este método es del orden de 4 veces más rápido. Esto es: 2(k/2)3 = 2(k/8) = k/4

Para un estudio más formal de éste y otros temas matemáticos relacionados con RSA, te recomiendo el documento Fundamentos matemáticos del método RSA del profesor Hugo Scolnik de la Universidad de Buenos Aires.

Adaptación final de las expresiones

Finalmente, adaptando los resultados a las expresiones que encontramos sobre el uso del TRC en el descifrado RSA y los valores que nos entregará OpenSSL cuando generemos una clave RSA en la siguiente lección, reemplazando x1 y x2 por m1 y m2respectivamente, y trabajando en mod q en vez de p, tenemos:

m = m2 + h q h = qInv [(m1 - m2)] mod p

Con: m1 = Cdp mod p m2 = Cdq mod q dp = d mod (p-1) (precalculado) dq = d mod (q-1) (precalculado) qInv = q-1 mod p (precalculado)

Cuestiones para reflexionar e investigar: 1. ¿Habías visto en la red la explicación detallada de cómo puede aplicarse el TRC en el descifrado RSA tal como se ha explicado aquí? 2. ¿En qué fecha Harvey L. Garner presenta esta fórmula? Mira este documento: The Residue Number System. 3. ¿Podría usarse también el TRC en la firma de un documento? ¿Por qué sí o no?

APARTADO 6.3. APLICACION DEL TRC EN EL DESCIFRADO RSA

Para el sistema RSA podemos utilizar cualquiera de las dos siguientes representaciones del teorema chino del resto, la que viene en los apuntes o la que se deriva de aplicar la fórmula de Garner ya vista, puesto que ambas son lo mismo.

TRC con fórmula estándar: M = {Ap[Cpdp (mod p)] + Aq[Cqdq (mod q)]} mod n siendo : Ap = q [inv (q,p)] = qp-1 mod n   (observa que esta reducción no se había visto en el apartado anterior) Aq = p [inv (p,q)] = pq-1 mod n   (observa que esta reducción no se había visto en el apartado anterior) dp = d mod (p-1);   dq = d mod (q-1) Cp = C mod p;   Cq = C mod q

Vamos a realizar a utilizar esta fórmula del TRC en el siguiente ejercicio: Se recibe como criptograma el valor decimal 582.819 y debemos descifrarlo usando el TRC, sabiendo que los datos privados del dueño de la clave son: p = 859, q = 907 (n = 779.113) y d = 17.249.

Solución: M = {Ap[Cpdp (mod p)] + Aq[Cqdq (mod q)]} mod n Usamos el software Fortaleza de Cifrados para los siguientes cálculos: Ap = qp-1 mod n = 907859-1 mod 779.113 = 470.733 (precalculado) Aq = pq-1 mod n = 859907-1 mod 779.113 = 308.381 (precalculado) dp = d mod (p-1) = 17.249 mod (859 - 1) = 89 (precalculado) dq = d mod (q-1) = 17.249 mod (907 - 1) = 35 (precalculado) Cp = C mod p = 582.819 mod 859 = 417 Cq = C mod q = 582.819 mod 907 = 525 Reemplazando: M = [470.733 41789 mod 859] + [308.381 52535 mod 907] mod 779.113 M = [470.733 322 + 308.381 824] mod 779.113 = [151.576.026 + 254.105.944] mod 779.113 M = 405.681.970 mod mod 779.113 = 543.210, que es el mensaje que se observa en la figura al descifrar el criptograma 582.819.

Descifrado del ejemplo usando el TRC
Equipo creador de Crypt4you →← Introducción al curso