'''
二元扩域模运算和点运算工具类
'''
class ECC_2m:
def __init__(self,poly,Gx,Gy,ecc_a=1,ecc_b=1):
self.poly=poly
self.ecc_a=ecc_a
self.ecc_b=ecc_b
self.Gx=Gx
self.Gy=Gy
def gf2_divmod(self,a, b):
if b == 0:
raise ZeroDivisionError
ans = 0
digit_a, digit_b = a.bit_length(), b.bit_length()
while not a < b:
rec = digit_a - digit_b
a = a ^ (b << rec)
ans = ans | (1 << rec)
digit_a = a.bit_length()
return ans, a
def gf2_ex_gcd(self,a,b):
x1, y1, x2, y2 = 1, 0, 0, 1
while b:
q, r = self.gf2_divmod(a, b)
a, b = b, r
x1, x2 = x2, x1 ^ self.gf2_mul(q, x2)
y1, y2 = y2, y1 ^ self.gf2_mul(q, y2)
return a, x1, y1
'''res = a*b mod poly'''
def gf2_mul(self,a,b):
ans = 0
digit_1 = self.poly.bit_length() - 1
while b:
if b & 1:
ans = ans ^ a
a, b = a << 1, b >> 1
if a >> digit_1:
a = a ^ self.poly
return ans
'''res = a^-1 mod poly'''
def gf2_inverse(self,a):
x1, x2 = 1, 0
b = self.poly
while b:
q, r = self.gf2_divmod(a, b)
a, b = b, r
x1, x2 = x2, x1 ^ self.gf2_mul(q, x2)
return x1
'''res = a^k mod poly'''
def gf2_quick_pow_mod(self,a,k):
res = 1
while k:
if k & 1:
res = self.gf2_mul(res, a)
k = k // 2
a = self.gf2_mul(a, a)
return res
'''仿射坐标点加运算'''
def affine_pt_add(self,x1,y1,x2,y2):
inv=self.gf2_inverse(x2^x1)
nmd=self.gf2_mul(y2 ^ y1, inv)
nmd2=self.gf2_mul(nmd, nmd)
x3=nmd2^nmd^x1^x2^self.ecc_a
t=self.gf2_mul(x1 ^ x3, nmd)
y3=t^x3^y1
return x3,y3
'''仿射坐标倍点运算'''
def affine_pt_double(self,x1,y1):
inv=self.gf2_inverse(x1)
nmd=x1^self.gf2_mul(y1, inv)
nmd2=self.gf2_mul(nmd, nmd)
x2=nmd2^nmd^self.ecc_a
xx1=self.gf2_mul(x1, x1)
t=self.gf2_mul(nmd ^ 1, x2)
y2=xx1^t
return x2,y2
'''标准投影坐标点加运算'''
def sproject_pt_add(self,x1,z1,x2,z2):
p=self.gf2_mul(x1, z2)
q=self.gf2_mul(x2, z1)
z3=self.gf2_mul(p ^ q, p ^ q)
m=self.gf2_mul(p, q)
n=self.gf2_mul(self.Gx,z3)
x3=m^n
return x3,z3
'''标准投影坐标倍点运算'''
def sproject_pt_double(self, x1, z1):
xx1=self.gf2_mul(x1, x1)
zz1=self.gf2_mul(z1,z1)
z2=self.gf2_mul(xx1,zz1)
x14=self.gf2_mul(xx1,xx1)
z14=self.gf2_mul(zz1,zz1)
bz=self.gf2_mul(self.ecc_b,z14)
x2=x14^bz
return x2,z2
'''仿射坐标下二进制展开法多倍点运算'''
def affine_pt_mul(self,k,Px,Py):
lbk=bin(k)[3:]
Qx,Qy=Px,Py
for i in lbk:
Qx,Qy=self.affine_pt_double(Qx,Qy)
if int(i):
Qx, Qy=self.affine_pt_add(Qx,Qy,Px,Py)
return Qx,Qy
'''标准投影坐标下蒙格玛利多倍点运算'''
def montgomery_pt_mul(self,k,Px,Py):
lbk = bin(k)[3:]
x1,z1=Px,1
z2=self.gf2_mul(Px,Px)
x2=self.gf2_mul(z2,z2)^self.ecc_b
for i in lbk:
if int(i):
x1,z1=self.sproject_pt_add(x1,z1,x2,z2)
x2,z2=self.sproject_pt_double(x2,z2)
else:
x2,z2=self.sproject_pt_add(x2,z2,x1,z1)
x1,z1=self.sproject_pt_double(x1,z1)
t0=self.gf2_mul(Px,z1)
t1=self.gf2_mul(t0,z2)
inv=self.gf2_inverse(t1)
t2=self.gf2_mul(Px,z2)
t3=self.gf2_mul(t2,x1)
Qx=self.gf2_mul(t3,inv)
t4=self.gf2_mul(t0,x2)
m=self.gf2_mul(t4,inv)
t5=self.gf2_mul(Qx^Px,m^Px)
t6=self.gf2_mul(Px,Px)
t7=t5^t6^Py
t8=self.gf2_mul(t7,Qx^Px)
t9=self.gf2_mul(z1,z2)
t10=self.gf2_mul(t8,t9)
Qy=self.gf2_mul(t10,inv)^Py
return Qx,Qy
def test(self,x1,z1,x2,z2):
inv0_1,inv0_2,mul0_1,mul0_2,temp1,temp2=self.Gx,z1,self.Gx,x1,x2,z2
t0=self.gf2_mul(inv0_1,inv0_2)
t1=self.gf2_mul(mul0_1,mul0_2)
inv0_1,inv0_2,mul0_1,mul0_2,temp1,temp2=t0,temp2,t0,temp1,inv0_2,t1
t3 = self.gf2_mul(inv0_1, inv0_2)
t2 = self.gf2_mul(mul0_1, mul0_2)
inv0_1, mul0_1, mul0_2, temp1=t3,temp1,inv0_2,t2
t4=self.gf2_mul(mul0_1,mul0_2)
mul0_1,temp2=temp2,t4
t5=self.gf2_mul(mul0_1,mul0_2)
inv=self.gf2_inverse(inv0_1)
inv0_1, inv0_2, mul0_1, mul0_2=inv,t5,inv,temp1
print("inv1:%x" % inv0_1)
print("inv2:%x" % inv0_2)
print("mul1:%x" % mul0_1)
print("mul2:%x" % mul0_2)
print("temp1:%x" % temp1)
print("temp2:%x" % temp2)
m=self.gf2_mul(inv0_1,inv0_2)
n=self.gf2_mul(mul0_1,mul0_2)
inv0_1, inv0_2, mul0_1, mul0_2,temp1 =m^self.Gx,n^self.Gx,temp2,inv0_1,m
t6 = self.gf2_mul(inv0_1, inv0_2)
t7 = self.gf2_mul(mul0_1, mul0_2)
Gx_2=self.gf2_mul(self.Gx,self.Gx)
inv0_2=t6^Gx_2^self.Gy
t8=self.gf2_mul(inv0_1,inv0_2)
inv0_1,inv0_2=t8,t7
t9=self.gf2_mul(inv0_1,inv0_2)
temp2=t9^self.Gy
return temp1,temp2
# if __name__ == '__main__':
# x1 = 0x7019ab6ef087ed8ed9307e423cd6f7f953fbc86a31a1b4d17daebfc61a13f9e8
# z1 = 0x1550071e12ace8b324af7c1a8c90132dfdc7397bae7be53d7ef884ea4aeb8b70a
# x2 = 0xf111861f422a383ebb914ac48228cec614f093646595234360717164fe857d40
# z2 = 0xaff0d461848c3cc27950c846db4fed7ac51f26afe2a54b969f820c527a02b6a9
# k = 0x6D3B497153E3E92524E5C122682DBDC8705062E20B917A5F8FCDB8EE4C66663D
# Gx = 0xCDB9CA7F1E6B0441F658343F4B10297C0EF9B6491082400A62E7A7485735FADD
# Gy = 0x13DE74DA65951C4D76DC89220D5F7777A611B1C38BAE260B175951DC8060C2B3E
# poly = 0x20000000000000000000000000000000000000000000000000000000000001001
# b = 0x00E78BCD09746C202378A7E72B12BCE00266B9627ECB0B5A25367AD1AD4CC6242B
# a = 0
# ECC = ECC_2m(poly, Gx, Gy, a, b)
# Qx,Qy=ECC.test(x1,z1,x2,z2)
if __name__ == '__main__':
k = 0x36CD79FC8E24B7357A8A7B4A46D454C397703D6498158C605399B341ADA186D6
Gx = 0xCDB9CA7F1E6B0441F658343F4B10297C0EF9B6491082400A62E7A7485735FADD
Gy = 0x13DE74DA65951C4D76DC89220D5F7777A611B1C38BAE260B175951DC8060C2B3E
poly = 0x20000000000000000000000000000000000000000000000000000000000001001
b = 0x00E78BCD09746C202378A7E72B12BCE00266B9627ECB0B5A25367AD1AD4CC6242B
a = 0
ECC = ECC_2m(poly, Gx, Gy, a, b)
'''计算Q=[k]G'''
# Qx,Qy=ECC.affine_pt_mul(k,Gx,Gy)
Qx, Qy = ECC.montgomery_pt_mul(k, Gx, Gy)
# 目标值：
Qx_right = 0x3FD87D6947A15F9425B32EDD39381ADFD5E71CD4BB357E3C6A6E0397EEA7CD66
Qy_right = 0x807711146D73951E9EB373A658214054B7B56D1D50B4CD6EB32ED387A65AA6A2
if (Qx == Qx_right) & (Qy == Qy_right):
print("#####计算正确#####")
else:
print("*****计算错误*****")
评论0