sábado, 11 de agosto de 2018

Programación (IV): Solución Reto 1

El  enunciado del primer reto de programación que puse en este post era el siguiente:

"¿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:
Por tanto, descarto ambos números y vuelvo a ejecutar el script con el tercer y cuarto números, y obtengo que el único de ellos que es primo es el cuarto:
Fijo el cuarto número como como 'p' (primer factor primo del módulo) y voy probando el resto de ellos como 'q' (segundo factor primo del módulo). Los dos únicos números primos de la lista son el cuarto y el décimo, y tras ejecutar el script con ambos números e introducir el exponente de la clave pública (e), 65537, y el critograma (c) obtengo que m (el mensaje en claro en decimal) es: 437191574114813999946507697086805092.
1.2.- Convierto el mensaje (m) anterior a hexadecimal, lo que me da:  543335745F5072316D346C31643464.

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.
Por tanto, descarto ambos números e introduzco el tercer y cuarto números, y el software me indica que el único de ellos que es primo es el cuarto:
Fijo el cuarto número como 'p' (primer factor primo del módulo) y voy probando el resto de ellos como 'q' (segundo factor primo del módulo). Los dos únicos números primos de la lista son el cuarto y el décimo:
Introduzco el exponente de la clave pública (e), 65537, y genero el par de claves (pulso el botón "Generación Manual"), pública y privada:
y descifro el criptograma (Operaciones > Cifrar_Descifrar), introduciendo el criptograma (c) y pulsando el botón "Descifrar Datos"; obtengo que m (el mensaje en claro en decimal, "Datos Descifrados") es: 437191574114813999946507697086805092.
2.2.- Convierto el mensaje (m) anterior a hexadecimal, lo que me da: 543335745F5072316D346C31643464.

2.3.- Obtengo la representación ASCII y ya puedo ver la clave del reto: "T35t_Pr1m4l1d4d":

******** PRÓXIMO RETO
Reto 2 (Programación): Por publicar.

No hay comentarios:

Publicar un comentario