PDF de programación - CRYPT4YOU - DOCUMENTO ANEXO A LA LECCIÓN 6 DEL CURSO "EL ALGORITMO RSA" - EJERCICIOS Y PRÁCTICAS PROPUESTOS Y RESUELTOS

CRYPT4YOU

DOCUMENTO ANEXO A LA LECCIÓN 6

DEL CURSO "EL ALGORITMO RSA"

EJERCICIOS Y PRÁCTICAS PROPUESTOS Y RESUELTOS



Autor: Dr. Jorge Ramió Aguirre
Fecha de publicación: 13 de junio de 2012
http://www.criptored.upm.es/crypt4you/temas/RSA/leccion6/leccion06.html



TABLA DE CONTENIDOS


LECCIÓN 6. RSA Y EL TEOREMA CHINO DEL RESTO ..................................................................... 2
Apartado 6.2. Definición del teorema chino del resto y su uso en RSA ..................................... 2
ejercicioRSA6.2.1 ........................................................................................................................... 2
ejercicioRSA6.2.2 ........................................................................................................................... 3
ejercicioRSA6.2.3 ........................................................................................................................... 4
Apartado 6.3 Aplicación del TRC en el descifrado RSA ............................................................... 5
prácticaRSA6.3.1 ........................................................................................................................... 5



Crypt4you. El algoritmo RSA. Ejercicios y prácticas de la Lección 6
Creative Commons (CC) - NoCommercial-Attribution-ShareAlike


www.crypt4you.com
Página 1

LECCIÓN 6. RSA Y EL TEOREMA CHINO DEL RESTO

Apartado 6.2. Definición del teorema chino del resto y su uso en RSA



ejercicioRSA6.2.1


x ≡ 32 mod 71
x ≡ 84 mod 101

x ≡ x1 mod p
x ≡ x2 mod q
x = [x1 * q * (q-1 mod q) + x2 * p * (p-1 mod p)] mod n

Ejercicio 1

Conociendo que el teorema chino del resto se expresa como:

Si


Entonces
Para el módulo n = 7.171 compuesto por el producto de los primos p = 71 y q = 101, usa la
ecuación del teorema chino del resto y encuentra el valor de x que cumple con las siguientes
congruencias:



Solución:

x1 = 32; x2 = 84; p = 71; q = 101; n = 7.171
q-1 mod q = inv (q, p) mod q = inv (101, 71) mod 101 = inv (30, 71) mod 101 = 45 mod 101 = 45
Nota: inv (101, 71) mod 101 = inv (30, 71) mod 101 porque 101 mod 71 = 30
p-1 mod p = inv (p, q) mod p = inv (71, 101) mod 71 = 37 mod 71 = 37
Luego:


Efectivamente, se comprueba fácilmente que:



Ejercicio 2

x = [32 * 101 * 45 + 84 *71 * 37] mod 7.171
x = [145.440 + 220.668] mod 7.171 = 366.108 mod 7.171 = 387

387 ≡ 32 mod 71
387 ≡ 84 mod 101

Es decir, 387 mod 71 = 32
Es decir, 387 mod 101 = 84

Resuelve ahora el valor de x para estos dos casos

x ≡ 12 mod 19
x ≡ 40 mod 2001

x ≡ 25 mod 31
x ≡ 100 mod 2011

a)
b)



Crypt4you. El algoritmo RSA. Ejercicios y prácticas de la Lección 6
Creative Commons (CC) - NoCommercial-Attribution-ShareAlike


www.crypt4you.com
Página 2



ejercicioRSA6.2.2


Aplicando la propiedad r ≡ t mod φ(p) ⇒ ar ≡ at mod p, calcula 23.104 mod 101 y saca

conclusiones de lo observado.

Solución

Comprobado que 101 es número primo y que mcd (2, 101) = 1, aplicando la propiedad
indicada tenemos:

φ(101) = 100
3.104 ≡ 4 mod 100

Luego:

23.104 ≡ 24 ≡ 16 mod 101

Por tanto, la propiedad anterior nos permite reducir significativamente el número de potencias
a calcular.



Crypt4you. El algoritmo RSA. Ejercicios y prácticas de la Lección 6
Creative Commons (CC) - NoCommercial-Attribution-ShareAlike


www.crypt4you.com
Página 3



ejercicioRSA6.2.3


Para obtener x mod n, con n = p * q, a partir de x1 ≡ x mod p y x2 ≡ x mod q, se hace:



x = x1 + h * p, donde h = [(x2 - x1)(p-1 mod q)] mod q (fórmula de Garner)

Demuestra que la fórmula de Garner es correcta.

Demostración

Basta comprobar que cuando hacemos x mod p y x mod q, para x = x1 + h * p, obtenemos x1 y
x2 respectivamente.

Primera ecuación:

x mod p = (x1 + h * p) mod p = x1 mod p + h * p mod p



= x1 mod p (pues h * p mod p = 0)

Luego x1 mod p = x1

Segunda ecuación:

x mod q = (x1 + h * p) mod q



= x1 mod q + h * p mod q

= x1 mod q + p [(x2 - x1)(p-1 mod q)] mod q

= x1 mod q + {(p mod q) [(x2 - x1)mod q] (p-1 mod q)]} mod q

= x1 mod q + [(x2 - x1) mod q] mod q (porque (p mod q) (p-1 mod q) = 1)

= x1 mod q + x2 mod q - x1 mod q

= x2 mod q = x2



Crypt4you. El algoritmo RSA. Ejercicios y prácticas de la Lección 6
Creative Commons (CC) - NoCommercial-Attribution-ShareAlike


www.crypt4you.com
Página 4

LECCIÓN 6. RSA Y EL TEOREMA CHINO DEL RESTO

Apartado 6.3. Aplicación del TRC en el descifrado RSA



prácticaRSA6.3.1


Para las siguientes claves, descifra el criptograma C utilizando el teorema chino del resto.
SW genRSA: http://www.criptored.upm.es/software/sw_m001d.htm
SW Fortaleza de Cifrados: http://www.criptored.upm.es/software/sw_m001e.htm
SW dec4hex: http://www.criptored.upm.es/software/sw_m051b.htm

Clave RSA1:
Clave RSA2:
Clave RSA3:

p = 223, q = 251, e = 131, C = 44.683
p = 23.357, q = 29.759, e = 4321, C = 487.735.883
p = 18EE7F9, q = 1DB117F, e = 5FB9, C = 2E1EEB6C98D7B (M en decimal)



Crypt4you. El algoritmo RSA. Ejercicios y prácticas de la Lección 6
Creative Commons (CC) - NoCommercial-Attribution-ShareAlike


www.crypt4you.com
Página 5