Criptografía (CCXCII): Suma de puntos de una curva elíptica sobre un cuerpo finito ℤp en python

Continúo poniendo scripts de programación en python para automatizar tareas que tengan relación con la criptografía.

En este post incluyo un script en python que implementa la suma de dos puntos de una curva elíptica definida sobre un cuerpo finito ℤ_p.

Ya expliqué en este post como se podía obtener el punto resultado de sumar dos puntos de una curva elíptica definida sobre los números reales mediante el llamado método de la cuerda y la tangente, y en esta entrada indico el algoritmo para hacerlo con las fórmulas matemáticas oportunas en una curva elíptica definida sobre un cuerpo finito ℤ_p.

El pseudocódigo para implementar dicha suma es:

- Script python para implementar la suma de dos puntos de una curva elíptica definida sobre un cuerpo finito ℤ_p:

El script es el siguiente:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# SUMA DE DOS PUNTOS DE UNA CURVA ELÍPTICA (CE):
#
# http://mikelgarcialarragan.blogspot.com/

import sympy

def suma_puntos(p,a,x1,y1,x2,y2):
    if x1 == -1 and y1 == -1:
        x3, y3 = x2, y2
        return x3, y3

    if x2 == -1 and y2 == -1:
        x3, y3 = x1, y1
        return x3, y3

    if x1 == x2 and y1 == y2:
        if y1 == 0:
            x3, y3 = -1, -1
            return x3, y3
        else:
            m = (3*pow(x1,2)+a)*pow(2*y1,-1,p)
    else:
        if  x1 == x2:
            x3, y3 = -1, -1
            return x3, y3
        else:
            m = (y2-y1)*pow(x2-x1,-1,p)

    x3 = (pow(m,2)-x1-x2)%p
    y3 = (m*(x1-x3)-y1)%p
    return x3, y3

def main():
# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Suma de puntos de una Curva Elíptica.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- SUMA DE DOS PUNTOS DE UNA CURVA ELÍPTICA:")
            # Se introducen:
            # p = número primo que caracteriza al cuerpo finito.
            # a = coeficiente 'a' de la curva elíptica
            # x1, y1 = coordenadas del primer punto a sumar.
            # x2, y2 = coordenadas del segundo punto a sumar.
            primo = a_entero = b_entero = p_ok = q_ok = p_si_no_inf = q_si_no_inf = False
            while not primo:
                p = input("Introduzca el número primo que caracteriza al cuerpo finito: ")
                if p.isnumeric() and sympy.isprime(int(p)):
                    primo = True
                    while not a_entero:
                        a = input("Introduzca el coeficiente 'a' de la curva elíptica: ")
                        try:
                            int(a)
                            a_entero = True
                            while not b_entero:
                                b = input("Introduzca el coeficiente 'b' de la curva elíptica: ")
                                try:
                                    int(b)
                                    b_entero = True
                                    while not p_si_no_inf:
                                        p_sn_inf = input("¿Es el primer punto a sumar ('P') el punto en el infinito (s/n)?: ")
                                        if p_sn_inf == "s" or p_sn_inf == "S" or p_sn_inf == "n" or p_sn_inf == "N":
                                            p_si_no_inf = True
                                            if p_sn_inf == "s" or p_sn_inf == "S":
                                                x1, y1 = -1, -1
                                            if p_sn_inf == "n" or p_sn_inf == "N":
                                                while not p_ok:
                                                    x1 = input("Introduzca x1: ")
                                                    if not x1.isnumeric():
                                                        print ("*** ERROR: Valor x1 incorrecto.")
                                                    else:
                                                        y1 = input("Introduzca y1: ")
                                                        if not y1.isnumeric():
                                                            print ("*** ERROR: Valor y1 incorrecto.")
                                                        else:
                                                            if pow(int(y1),2,int(p)) == (pow(int(x1),3,int(p)) + int(x1)*int(a) + int(b))%int(p):
                                                                p_ok = True
                                                            else:
                                                                print ("*** ERROR: El punto 'P' introducido no es un punto de la curva.")
                                        else:
                                            print ("*** ERROR: Introduzca 's', 'S', 'n' o 'N'.")
                                    while not q_si_no_inf:
                                        q_sn_inf = input("¿Es el segundo punto a sumar ('Q') el punto en el infinito (s/n)?: ")
                                        if q_sn_inf == "s" or q_sn_inf == "S" or q_sn_inf == "n" or q_sn_inf == "N":
                                            q_si_no_inf = True
                                            if q_sn_inf == "s" or q_sn_inf == "S":
                                                x2, y2 = -1, -1
                                            if q_sn_inf == "n" or q_sn_inf == "N":
                                                while not q_ok:
                                                    x2 = input("Introduzca x2: ")
                                                    if not x2.isnumeric():
                                                        print ("*** ERROR: Valor x2 incorrecto.")
                                                    else:
                                                        y2 = input("Introduzca y2: ")
                                                        if not y2.isnumeric():
                                                            print ("*** ERROR: Valor y2 incorrecto.")
                                                        else:
                                                            if pow(int(y2),2,int(p)) == (pow(int(x2),3,int(p)) + int(x2)*int(a) + int(b))%int(p):
                                                                q_ok = True
                                                            else:
                                                                print ("*** ERROR: El punto 'Q' introducido no es un punto de la curva.")
                                        else:
                                            print ("*** ERROR: Introduzca 's', 'S', 'n' o 'N'.")
                                    x3,y3 = suma_puntos(int(p),int(a),int(x1),int(y1),int(x2),int(y2))
                                    if x3 == -1 and y3 == -1:
                                        print ("[+] El punto resultado es el punto en el infinito (𝒪).")
                                    else:
                                        print ("[+] R = P + Q = (x3, y3) = (", x3, ",", y3, ")")
                                except ValueError:
                                    print ("*** ERROR: Coeficiente 'b' de la curva elíptica incorrecto.")
                        except ValueError:
                            print ("*** ERROR: Coeficiente 'a' de la curva elíptica incorrecto.")
                else:
                    print ("*** ERROR: Número primo que caracteriza al cuerpo finito incorrecto.")
        elif opcion == "2":
            print ("*** FIN ******************************************")
            salir = True
        else:
            print ("*** ERROR: Opción no válida.")
	
if __name__ == '__main__':
    main()

Lo ejecuto:

Quizás también te interese: