Source: http://www.criptored.upm.es/crypt4you/temas/RSA/leccion6/leccion06.html
Timestamp: 2013-06-19 01:59:35+00:00

Document:
Dr. Jorge Ramió Aguirre - 13/06/2012 Twittear
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.
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.
Apartado 6.6. Datos estadísticos de esta lección
Apartado 6.7. Encuesta
1. Apreciar la bondad de aplicar el TRC en las operaciones de descifrado en RSA.
2. Saber resolver las ecuaciones del TRC para RSA y reconocer sus elementos.
3. Preparar los conceptos asociados al TRC en RSA para su uso con OpenSSL.
1. Fortaleza de Cifrados
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 Theorem de 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.
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 ∈ .
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)
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
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:
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ático Harvey 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 m2 respectivamente, y trabajando en mod q en vez de p, tenemos:
h = qInv * [(m1 - m2)] mod p
dp = d mod (p-1) (precalculado)
dq = d mod (q-1) (precalculado)
qInv = q-1 mod p (precalculado)
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
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.
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
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
Observa que el software genRSA muestra resultados parciales ligeramente diferentes al aplicar el TRC en el descifrado. Comprenderás esto cuando hagamos el siguiente ejemplo usando la fórmula de Garner.
TRC optimizado con fórmula de Garner:
Ahora usaremos la fórmula de Garner para descifrar el criptograma 3.108.635 en un sistema RSA en el que:
p = 3.449, q = 3.061 (n = 10.557.389), d = 2.335.691.
Usando el software Fortaleza de Cifrados:
dp = d mod (p-1) = 2.335.691 mod (3.449 - 1) = 1.395 (precalculado)
dq = d mod (q-1) = 2.335.691 mod (3.061 - 1) = 911 (precalculado)
qInv = q-1 mod p = inv (3.061, 3.449) = 80 (precalculado)
m1 = Cdp mod p = 3.108.635 1.395 mod 3.449 = 1.342
m2 = Cdq mod q = 3.108.635 911 mod 3.061 = 993
h = 80 * [1.342 - 993] mod 3.449 = 27.920 mod 3.449 = 328
m = 993 + 328 * 3.061 = 1.005.001, que es el mensaje que se observa en la figura al descifrar el criptograma 3.108.635.
En la prácticaRSA6.3.1 vas utilizar el teorema chino del resto para descifrar distintos criptogramas.
1. ¿Por qué crees que la fórmula de Garner es una optimización de la fórmula estándar del TRC?
2. ¿Por qué decimos que sólo el dueño de la clave puede usar el TRC?
Aunque en este curso sólo nos interesa el uso del teorema chino del resto como herramienta de aceleración de las operaciones de cifra en RSA, lo cierto es que dicho teorema tiene varias aplicaciones en criptografía y en la vida real. En este apartado mostraremos sólo algunos ejemplos.
Vamos a comenzar con un pequeño juego, que no es otra cosa que llevar las ecuaciones básicas del TRC a un enunciado diferente como muestra esta página Web del Departamento DIATEL de la UPM. Accede a la página pinchando en la figura de abajo y realiza al menos un par de pruebas.
¿Impresionado? No es para tanto. Si editas el código fuente de esa página (botón derecho del ratón: ver código fuente) verás que en los comentarios de dicho código se explica claramente cómo se realizan las operaciones.
Enunciado original del teorema chino del resto
El matemático chino Sun Tzu presenta en el siglo IV antes de Cristo el siguiente problema
Un número que se divide repetidamente por 3, entrega el resto 2; si se divide de igual forma por 5, entrega el resto es 3 y si se divide también por 7, entrega el resto 2. ¿De qué número estamos hablando?
Podemos representar el problema por este sistema de ecuaciones:
a) x ≡ 2 mod 3 b) x ≡ 3 mod 5 c) x ≡ 2 mod 7
Podemos deducir de a) que:
x = 3*r + 2 para algún entero r
Si sustituimos este valor de x en la ecuación b):
Como x ≡ 3 mod 5 y x = 3*r + 2, entonces 3*r + 2 ≡ 3 mod 5, es decir 3*r ≡ 1 mod 5
Como inv (3, 5) = 2 tenemos:
r ≡ 2 mod 5, que es equivalente a decir: r = 5*s + 2 para cualquier entero s = 0, 1, 2, 3, ....
Reemplazando el valor de r en x = 3*r + 2, se tiene: x = 3(5*s + 2) + 2 = 15*s + 8
Tomamos la ecuación c) x ≡ 2 mod 7 y reemplazamos el valor de x, obteniendo:
15*s + 8 ≡ 2 mod 7 que reduciendo mod 7 queda s + 1 ≡ 2 mod 7, por tanto s ≡ 1 mod 7
s = 7*t + 1 para cualquier entero t = 0, 1, 2, 3, ... Y finalmente x = 15*s + 8 = 15*(7*t + 1) + 8
x = 105*t + 23 con t = 0, 1, 2, 3, ... Finalmente, las soluciones al problema serán x = 23, 128, 233, 338, ...
Observa que 105 = 3*5*7 es el producto de los módulos porque no tienen factores en común; los números han de ser primos entre sí dos a dos.
Comprueba con la calculadora de Windows que 338 ≡ 2 mod 3, 338 ≡ 3 mod 5 y 338 ≡ 2 mod 7.
Software online para resolución de sistemas de congruencias mediante el TRC
Desde la siguiente página del Departamento de Matemática Aplicada de la Facultad de Informática de la Universidad Politécnica de Madrid, tienes un software online para la Resolución de Sistemas de Congruencias. Comprueba tú mismo el ejercicio anterior, cuya captura de pantalla aparece en la figura siguiente.
El problema del matemático chino Sun Tzu
Brahmagupta y la cesta con huevos
Aprovecha la página anterior para resolver este problema presentado por el matemático indio Brahmagupta en el siglo VII.
Una cesta tiene un conjunto de huevos que si se sacan en grupos de 2, de 3, de 4, de 5 y de 6 queda siempre un huevo en la cesta. En cambio si se sacan en grupos de 7, no queda ninguno. Encuentra el número más pequeño de huevos que hay en la cesta.
Las ecuaciones son x ≡ 1 mod 2, x ≡ 1 mod 3, x ≡ 1 mod 4, x ≡ 1 mod 5, x ≡ 1 mod 6, x ≡ 0 mod 7.
La primera congruencia x ≡ 1 mod 2 nos dice que x será impar, lo recordaremos e ignoramos la ecuación. Quedan los módulos 3, 4, 5, 6 y 7. Podemos descartar x ≡ 1 mod 6 para que se cumpla que los módulos sean primos entre sí para aplicar el TRC y nos quedamos entonces sólo con:
1 mod 3, x ≡ 1 mod 4, x ≡ 1 mod 5, x ≡ 0 mod 7.
Comprueba con la calculadora de Windows que el número en cuestión es el 301. La solución completa a este ejercicio puedes verla en este documento de la Universidad de Denver y puedes hacerla online con el programa Resolución de Sistemas de Congruencias ya visto. Para una profundización en estos temas, te recomiendo la lectura de Introducción a la Matemática Discreta de D. Javier Cobos Gavala de la la ETS de Ingeniería Informática de la Universidad de Sevilla. Así mismo, en esta página del Departamento de Matemáticas de la Universidad Complutense de Madrid de D. Enrique Arrondo encontrarás interesantes ejercicios.
Otras aplicaciones del TRC en criptografía
Existen muchas aplicaciones del teorema chino del resto en problemas de la vida real; puedes encontrarlos si buscas adecuadamente en Internet. Sin embargo, como todo esto va más allá del objetivo de esta lección, sólo comentaremos brevemente a continuación otros usos que tiene este teorema en la criptografía.
Su principal aporte lo encontramos en los denominados protocolos criptográficos muy bien explicados en esta página del grupo de Criptología de la Universidad de La Laguna CryptULL y, en particular, en el protocolo conocido como transferencia inconsciente o trascordada presentado por Michael Rabin en 1979, también conocido como Criptosistema de Rabin, y que forma parte medular de un buen número de dichos protocolos como, por ejemplo, el problema del lanzamiento de la moneda, el problema de la firma de contratos, el problema de los prisioneros, ... presentados en el capítulo 19 de mi libro electrónico, y que está replicado en esta dirección en una edición del año 2005 pero sin embargo completa.
Mención especial requiere el Algoritmo Esquema de umbral de Shamir para compartir secretos usando el teorema chino del resto, aunque sea más conocida la solución que utiliza la interpolación de Lagrange como se muestra en el vídeo de intypedia "Protocolo de reparto de secretos". Pincha en el siguiente enlace para ver el vídeo.
1. Una variación del problema de la cesta de huevos es la siguiente: al sacarlos en grupos de 2, 3, 4, 5 y 6 quedan, respectivamente 1, 2, 3, 4 y 5 huevos ... pero si se sacan en grupos de 7, no queda ninguno. Comprueba que había 119 huevos en la cesta.
2. En este apartado se ha indicado que los números han de ser primos entre sí dos a dos. ¿Qué sucede si no son primos? ¿Cómo aplicamos aquí el TRC? Haz una prueba con el software online para la resolución de sistemas de congruencias que has visto.
3. Busca en la red esas aplicaciones del TRC en el mundo real que se indicaban en el apartado, coméntalas y discútelas en las redes sociales de c4y.
4. Resuelve algún problema de reparto de secretos, usando la página Web de referencia de este apartado y el software online para la resolución de sistemas de congruencias .
APARTADO 6.5. TEST DE EVALUACION DE LA LECCION RSA06
1. El teorema chino del resto permite:
a) Optimizar la factorización de n en sus primos p y q
b) Optimizar el cifrado y el descifrado RSA
c) Reducir el tiempo para encontrar los primos p y q
2. Podemos decir que usando el teorema chino del resto en el descifrado:
a) Se realizan más operaciones pero con un menor costo general en cómputo
b) Se realizan más operaciones pero con un mayor costo general en cómputo
c) Se realizan el mismo número operaciones pero al 10% del costo en cómputo
3. Si usamos el TRC para descifrar un criptograma de un texto que se ha cifrado en un cuerpo 1.024 de bits:
a) Las operaciones se realizarán en un cuerpo de 1.023 bits
b) Las operaciones se realizarán en un cuerpo de 1.024 bits
c) Las operaciones se realizarán en un cuerpo de 512 bits
4. En la resolución del TRC en el descifrado RSA, se cumple que:
a) Es necesario resolver un sistema de congruencias mod Φ(n)
b) Es necesario usar los valores de Φ(n), p y q
c) Hay algunos valores que pueden ser precalculados
5. Aplicando la fórmula de Garner en el descifrado RSA:
a) El descifrado es unas 4 veces más rápido
b) El descifrado es unas 2 veces más rápido
c) El descifrado es unas 8 veces más rápido
APARTADO 6.6. DATOS ESTADISTICOS DE ESTA LECCION
Más de 125.000 accesos al proyecto Crypt4you en un año: 15 de marzo de 2012 al 15 de marzo de 2013.
Si aún no lo has hecho, por favor contesta a la encuesta sobre este MOOC que encontrarás en la siguiente dirección.
Ir a: [Portada c4y] [Lección 5] [Índice] [Lección 7]

References: resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 resolución