#=========================================================# # Key exchabge by ECC # # n,m: secret random number, P: shared point # #---------------------------------------------------------# # copy right : Ushiro Yasunori (ISCPC) # # date : 2020/03/21 # #=========================================================# # ecc.py # # set_g(p,r,a,b) : g_p,g_r,g_a,g_b # # inv_mod(a,p) : 1/a (mod p) # # ecc_Add1(A,B) : A+B on ECC # # ecc_Add2(A) : 2*A on ECC # # ecc_Mul(n,A) : n*A on ECC # # y^2=x^3+g_a*x+g_b (mod p) on ECC # # x,y,g_a,g_b:integer, p,r:prime, r:order # #=========================================================# inport math,random #======= global constant =================================# global fin # input,output file global g_p,g_r,g_a,g_b # values on ECC global p_P,p_Q,p_R # ECC point global p_S,p_T # ECC point global n,m # random number #=========================================================# # inv_mod(a,p) = 1/a (mod p) # # a:integer p:prime number # #---------------------------------------------------------# # copy right : Ushiro Yasunori (ISCPC) # # date : 2020/03/17 # #=========================================================# def inv_mod(a, p): rn,ro, sn,so = p,a, 0,1 while rn != 0: q = ro//rn un,vn = rn,sn rn = ro - q*rn sn = so - q*sn ro,so = un,vn if (so < 0): so += p return so #=========================================================# # C : ecc_Add2(A) = 2*A on ECC # # C[0] = e^2 - 2*A[0] (mod p) # # C[1] = e*(A[0]-C[0]) - A[1] (mod p) # # d=1/(2*A[1]), e=d*(3*A[0]^2+g_a) (mod p) # #---------------------------------------------------------# # copy right : Ushiro Yasunori (ISCPC) # # date : 2020/01/30 # #=========================================================# def ecc_Add2(A): a2 = 2*A[1] if a2 == 0: return A #special case # compute d,e d = inv_mod(a2, g_p) #d=1/a2 (mod p) h = (3*A[0]*A[0] + g_a) % g_p e = (d*h) % g_p # compute C=[c0,c1] cx = (e*e - 2*A[0]) % g_p cy = (e*(A[0]-cx) - A[1]) % g_p C = [cx, cy] return C #=========================================================# # C : ecc_Add1(A,B) = A+B on ECC # # C[0] = e^2 - A[0] - B[0] (mod p) # # C[1] = e*(A[0]-C[0]) - A[1] (mod p) # # d=1/(B[0]-A[0]), e=d*(B[1]-A[1]) (mod p) # #---------------------------------------------------------# # copy right : Ushiro Yasunori (ISCPC) # # date : 2020/03/19 # #=========================================================# def ecc_Add1(A, B): # special check if A == [0,0]: return B if B == [0,0]: return A if A[0] == B[0]: if A[1] == B[1]: if A[1] == 0: C = [0, 0] else: C = ecc_Add2(A) return C elif (A[1]+B[1]) == g_p: C = [0, 0] return C # compute d,e d = inv_mod(B[0]-A[0], g_p) #d=1/(Bx-Ax) (mod p) e = ( d*(B[1] - A[1]) ) % g_p # compute C=[c0,c1] cx = (e*e - A[0] - B[0]) % g_p cy = (e*(A[0] - cx) - A[1]) % g_p C = [cx, cy] return C #=========================================================# # C : ecc_Mul(n,A) = n*A on ECC # # n: integer, A,C: point in ECC # #---------------------------------------------------------# # copy right : Ushiro Yasunori (ISCPC) # # date : 2020/01/30 # #=========================================================# def ecc_Mul(n, A): W, nw = A, n C = [0, 0] while nw > 0: if (nw&1) == 1: C = ecc_Add1(C, W) W = ecc_Add2(W) nw = nw >> 1 return C #=========================================================# # file read function # # return: integer value # #---------------------------------------------------------# # copy right : Ushiro Yasunori (ISCPC) # # date : 2020/03/21 # #=========================================================# def val_read(name): global fin # input file data = fin.readline() val = data.split() rv = int(val[0]) return rv #=========================================================# # file open and read data # # g_p,t_r,g_a,g_b : values on ECC # # p_P,on ECC # #---------------------------------------------------------# # copy right : Ushiro Yasunori (ISCPC) # # date : 2020/03/21 # #=========================================================# def ecc_read(): global g_p,g_r,g_a,g_b # values on ECC global n,m, p_P # random number ECC point global fin # input file p_P = [0,0] # clear p_P # file open fin = open("secp256.txt", "r") # read g_p,t_r,g_a,g_b g_p = val_read("p") g_r = val_read("r") g_a = val_read("a") g_b = val_read("b") # read t_Q p_P[0] = val_read("Px") p_P[1] = val_read("Py") # Check p_P Qm = ecc_Mul(g_r, p_P) if Qm != [0,0]: print("P is not ECC point") sys.exit() fin.close() #=========================================================# # Main program for key exchabge by ECC # # n,m : random number # # p_Q=m*p_P, p_R=n*p_P # #---------------------------------------------------------# # copy right : Ushiro Yasunori (ISCPC) # # date : 2020/03/21 # #=========================================================# ecc_read() print("-- key exchabge by ECC --") m = random.randint(1,g_r) p_P = ecc_Mul(m, p_P) print("shared point P=(Px,Py)") print(" Px=",p_P[0]) print(" Py=",p_P[1]) # m,n random number print("random number get; A:m, B:n") m = random.randint(1,g_r) n = random.randint(1,g_r) print(" m=",m) print(" n=",n) print("A: Q=m*P -->B, B: R=n*P -->A") p_Q = ecc_Mul(m, p_P) p_R = ecc_Mul(n, p_P) print(" Qx=",p_Q[0]) print(" Qy=",p_Q[1]) print(" Rx=",p_R[0]) print(" Ry=",p_R[1]) print("A: S=m*R, B: T=n*Q, key: Sx=Tx") p_S = ecc_Mul(m, p_R) p_T = ecc_Mul(n, p_Q) print(" Sx=",p_S[0]) print(" Tx=",p_T[0])