"¿Puedes descifrar el criptograma (c) que se facilita como recurso asociado al reto?. Para ello tendrás que averiguar, de entre los diez números que figuran también como recursos asociados al reto, cuáles son los dos números primos que empleé para generar el par de claves, pública y privada. Ah..., se me olvidaba, también es importante saber que el exponente de la clave pública es 65537".
Este reto es de criptografía y programación y su solución es:
1.- Ya decía en el citado post que en primer lugar iba a crear un script en Python para intentar resolver este reto. El siguiente:
from random import randint
from time import time
def inv(n1, n):
"""
Calculo del inverso multiplicativo de un numero (n1) modulo n
"""
global a, u0
a = n1
b = n
u0 = 1
u1 = 0
v0 = 0
v1 = 1
while b != 0:
q = a//b
r = a-b*q
u = u0-q*u1
v = v0-q*v1
a = b
b = r
u0 = u1
u1 = u
v0 = v1
v1 = v
if a != 1:
u0 = 0
elif u0 < 0:
u0 = n+u0
return a, u0
def exp_modular(base, exponente, modulo):
"""
Funcion exponenciacion modular rapida
"""
global x
B = bin(exponente)[2:]
x = 1
i = 0
while i < len(B):
x = (x**2)%modulo
if B[i]=="1":
x = x*base%modulo
i = i+1
return x
def es_primo(numero):
"""
Funcion que nos indica si un numero es compuesto o, por el contrario y con un alto
nivel de confianza, es primo (Test de primalidad de Miller-Rabin).
Tiene que recibir el numero entero impar
"""
r = numero-1
k = 10
t = 0
i = 1
s= 0
while r%2 == 0:
s = s+1
r = r/2
while i <= k and t != 1:
a = randint(2, numero - 1)
j = 0
exp_modular(a, r, numero)
y = x
if y <> 1 and y <> numero - 1:
j = 1
while y <> numero - 1 and t <> 1 and j <= s - 1:
y = y**2%numero
if y == 1:
t = 1
else:
j = j+1
if y <> numero -1:
t = 1
i = i+1
if t == 0:
return True
else:
return False
def t_chino_resto(p, q, n, d, c):
"""
Descifrado RSA utilizando el teorema chino del resto
"""
global m
inv(p, q)
p1 = u0
dp = d%(p-1)
dq = d%(q-1)
cp = c%p
cq = c%q
k1 = exp_modular(cp, dp, p)
k2 = exp_modular(cq, dq, q)
m = k1+p*(((k2-k1)*p1)%q)
return m
p = int(input('Introduzca el factor primo del modulo p ......... : '))
q = int(input('Introduzca el factor primo del modulo q ......... : '))
error = 0
if p < 2 or q < 2:
error = 1
print 'Los factores del modulo deben ser numeros naturales mayores que 1'
if error == 0:
if es_primo(p) == False:
error = 1
print 'El factor del modulo p debe ser un numero primo'
if es_primo(q) == False:
error = 1
print 'El factor del modulo q debe ser un numero primo'
if error == 0:
n = p*q
print 'modulo n ........................................ :', n
fi = (p-1)*(q-1)
print 'fi(n) ........................................... :', fi
e = int(input('Introduzca el exponente de la clave publica e ... : '))
inv(e, fi)
if a !=1:
error = 1
print e, ' no es primo relativo de ', fi
else:
print 'exponente de la clave privada (d) ............... :', u0
if error == 0:
c = int(input('Introduzca el criptograma c ..................... : '))
tiempo_inicial = time()
t_chino_resto(p, q, n, u0, c)
print 'm (decimal) ..................................... :', m
tiempo_final = time()
tiempo_ejecucion = tiempo_final - tiempo_inicial
print 'Tiempo de ejecucion en segundos:',tiempo_ejecucion
1.1.- Ejecuto este script con los dos primeros números facilitados como recursos asociados al reto; tras introducir el primer número como 'p' (primer factor primo del módulo) y el segundo como 'q' (segundo factor primo del módulo), obtengo (test de primalidad de Miller-Rabin, ver este post donde lo explico) que ninguno de ambos es primo:
1.3.- Obtengo la representación ASCII y ya puedo ver la clave del reto: "T35t_Pr1m4l1d4d":
2.- Una vez resuelto el reto mediante el script de Python, tal y como dije en post en el que enuncié este reto, lo resuelvo utilizando un software especializado, genRSA 2.1.
2.1.- De la misma forma que en el caso anterior, introduzco el primer número como 'p' (primer factor primo del módulo) y el segundo como 'q' (segundo factor primo del módulo), y el software me indica que ninguno de ambos es primo.
2.3.- Obtengo la representación ASCII y ya puedo ver la clave del reto: "T35t_Pr1m4l1d4d":
Reto 2 (Programación): "Reunión secreta".
Comentarios
Publicar un comentario