Criptografía (CCXCI): Curva elíptica sobre cuerpo finito ℤp en python

Otro post con un script de programación en python para automatizar tareas que tengan relación con la criptografía.

En este post incluyo un script en python para  obtener los puntos de una curva elíptica definida sobre un cuerpo finito del tipo ℤ_p y para obtener la representación gráfica de ambas curvas, la definida sobre los número reales y la definida sobre el cuero finito ℤ_p.

En el post anterior puse como ejemplo de lo anterior la curva sobre números reales que sirve para ilustrar este post:

Y decía que al definir la curva elíptica sobre un cuerpo finito se obtiene algo que se asemeja poco o nada a la representación gráfica de la curva sobre números reales, más bien tiene el aspecto de un conjunto de puntos aleatorios, pero que todavía se puede observar la simetría.

El script es el siguiente:

- Script python para la obtención y representación de los puntos de una curva elíptica sobre un cuerpo finito ℤ_p:

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

# PUNTOS DE UNA CURVA ELÍPTICA (EC):
#
# Obtención de los puntos de una Curva Elíptica (y^2 = x^3 + ax + b) definida
# sobre un cuerpo finito.
#
# http://mikelgarcialarragan.blogspot.com/

import sympy
import numpy as np
import matplotlib.pyplot as plt

def main():
# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Obtención puntos Curva Elíptica sobre cuerpo finito.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- PUNTOS DE UNA CURVA ELIPTICA DEFINIDA SOBRE UN CUERPO FINITO:")
            # Se introducen:
            # p = número primo que caracteriza al cuerpo finito.
            # a = coeficiente 'a' de la curva elíptica.
            # b = coeficiente 'b' de la curva elíptica.
            primo = a_entero = b_entero = 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
                                    curva_eliptica_r = "y^2 = x^3 "
                                    curva_eliptica_f = "y^2 mod " + p + " = x^3 "
                                    if int(a) >= 0:
                                        curva_eliptica_r += "+ "+ a + " x "
                                        curva_eliptica_f += "+ "+ a + " x "
                                    else:
                                        curva_eliptica_r += a + " x "
                                        curva_eliptica_f += a + " x "
                                    if int(b) >= 0:
                                        curva_eliptica_r += "+ "+ b + " "
                                        curva_eliptica_f += "+ "+ b + " "
                                    else:
                                        curva_eliptica_r += b + " "
                                        curva_eliptica_f += b + " "
                                    curva_eliptica_f +=  "mod " + p
                                    print ("[+] Curva elíptica sobre los números reales:    ", curva_eliptica_r)
                                    ec_r = plt.figure()
                                    ec_r, ax = plt.subplots()
                                    ax.set_title(curva_eliptica_r)
                                    ax.xaxis.grid()
                                    ax.yaxis.grid()
                                    y, x = np.ogrid[-5:5:100j, -5:5:100j]
                                    plt.contour(x.ravel(), y.ravel(), pow(y, 2) - pow(x, 3) - x * int(a) - int(b), [0], colors = ["r"])
                                    plt.savefig('EC_R.png')
                                    plt.show()
                                    print ("[+] Curva elíptica definida sobre cuerpo finito:", curva_eliptica_f)
                                    print ("[+] Puntos curva elíptica sobre cuerpo finito:")
                                    exp = int((int(p)-1)/2)
                                    y_2 = [pow(y,2,int(p)) for y in range(0, int(p))]
                                    coordenadas = []
                                    for x in range(0, int(p)):
                                        f_x = (pow(x,3) + int(a)*x + int(b))%int(p)
                                        if pow(f_x,exp,int(p)) == 0 or pow(f_x,exp,int(p)) == 1:
                                           for y in range(len(y_2)):
                                               if  f_x == y_2[y]:
                                                  print ("    (", x, ",", y, ")")
                                                  coordenadas.append(x)
                                                  coordenadas.append(y)
                                    coordenadas_x = coordenadas[0::2]
                                    coordenadas_y = coordenadas[1::2]
                                    ec_f = plt.figure()
                                    ec_f, ax = plt.subplots()
                                    ax.set_title(curva_eliptica_f)
                                    ax.xaxis.grid()
                                    ax.yaxis.grid()
                                    plt.scatter(coordenadas_x, coordenadas_y)
                                    plt.savefig('EC_F.png')
                                    plt.show()
                                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:

Tras pedir como datos de entrada: el número primo que caracteriza al cuerpo finito y los coeficientes 'a' y 'b' de la curva elíptica, el script obtiene los puntos de la curva definida sobre el cuerpo finito y genera sendos gráficos para la representación de la misma sobre números reales y sobre el cuerpo finito.

Quizás también te interese: