椭圆曲线密码体制具有对带宽和存储空间的需求相对较小以及安全曲线选择丰富等优势,其安全性主要依赖于椭圆曲线离散对数问题的难解性。但如果相关密码系统的曲线参数和加密过程中的随机数发生器选择不当,都有可能使得该系统不安全。对一些特殊的椭圆曲线离散对数问题,存在多项式时间或者亚指数时间算法。但对任意给定椭圆曲线上的离散对数问题,在经典计算机模型下目前仍然没有多项式时间算法,值得深入探究。

有限域中的离散对数问题可用亚指数时间的指标演算法求解。 对于 ECDLP 常见的求解算法有大步 - 小步法、 Pollard’s rho 算法等。一般来说,当参数 p 较大时,这些算法并不容易求解。而在参数设定不当时,ECDLP 的困难性会下降; 如 MOV 攻击可以利用双线性对将 ECDLP 求解转为有限域中乘法群的 DLP 求解,而有限域的乘法群中 DLP 存在亚指数时间的算法。

指数积分算法是目前已知最有力的计算离散对数方法,这项技术并不能应用于所有群。

指数积分算法

输入:乘法群Zp的生成元αβ输入:乘法群Z_p^*的生成元 \alpha 和\beta

输出:离散对数x=logαβ输出:离散对数x=log_\alpha \beta

指数积分算法需要选择一个相对较小在Zp中的元集合S={p1,p2.....,pi}称之为分解基(都是素数)。这种方法中,Zp中大的元可以有效表示为集合S上元的乘积。指数积分算法需要选择一个相对较小在Z_p^∗ 中的元集合S=\lbrace p_1,p_2,.....,p_i \rbrace称之为分解基(都是素数)。这种方法中,Z_p^∗ 中大的元可以有效表示为集合S上元的乘积。

首先我们先选择一个分解基 S,然后收集关于 S 上对数元的线性关系

  1. 选择一个随机整数k0kn1,计算αk选择一个随机整数k,0\leq k\leq n-1,计算\alpha ^k

  2. αkS中元的乘积:αki=1tpicimodP,ci0令\alpha^k为S中元的乘积: \alpha^k \equiv \prod_{i=1}^{t}p_i^{c_i}modP, \quad c_i \geq0

    ifsucceed:上式取对数得到一个线性关系:ki=1tlogαPimod(P1)if \quad succeed:\quad上式取对数得到一个线性关系:\quad k \equiv \sum _{i=1}^{t}log_\alpha P_i mod(P-1)

  3. 重复 1and2 直到得到 t+c 个关系

  4. 找出S上元的离散对数,在模p1意义下,解在第2步中收集到的t+c个线性方程的线性系统得到所有值logαPi,1it找出S上元的离散对数,在模p-1意义下,解在第2步中收集到的t+c个线性方程的线性系统得到所有值log_\alpha P_i,\quad 1 \leq i \leq t

  5. 计算 x

  6. 选择一个随机整数k0kn1,计算βαk选择一个随机整数k,0\leq k\leq n-1,计算\beta ·\alpha ^k

  7. βαkS中元的乘积:βαki=1tpidimodP,di0令\beta ·\alpha ^k为S中元的乘积: \beta ·\alpha ^k \equiv \prod_{i=1}^{t}p_i^{d_i}modP, \quad d_i \geq0

    如果不成功则重复第6步,否则,方程两边取对数:logαβ=[(i=1tlogαPi)k]mod(p1)=xReturn(x)如果不成功则重复第6步,否则,方程两边取对数: \quad log_\alpha \beta=[(\sum_{i=1}^{t}log_\alpha P_i)-k]mod(p-1)=x \quad Return(x)

例如

p=229.有限乘法群Zp生成元α=6β=13,使用指数积分算法计算离散对数log613令p=229.有限乘法群Z_p^*生成元 \alpha=6。\beta=13,使用指数积分算法计算离散对数log_613

参照第七步

x=logαβc1logαp1+c2logαp2++cBlogαpBk(modp1)x=logα_β≡c_1​log_α​p1​+c_2​log_α​p2​+⋯+c_B​log_α​pB-k​(modp−1)

利用 CRT 求 x

#g=65537, p=26622572818608571599593915643850055101138771
#g^x=14632691854639937953996750549254161821338360 (mod p)
import math
 
#欧几里得算法求最大公约数
 
def get_gcd(a, b):
 
	k = a // b
 
	remainder = a % b
 
	while remainder != 0:
 
		a = b 
 
		b = remainder
 
		k = a // b
 
		remainder = a % b
 
	return b
 
	
 
#扩展欧几里得算法求线性方程的 x 与 y
 
def get_(a, b):
 
	if b == 0:
 
		return 1, 0
 
	else:
 
		k = a // b
 
		remainder = a % b		
 
		x1, y1 = get_(b, remainder)
 
		x, y = y1, x1 - k * y1			
 
	return x, y
 
	
 
#计算逆元的函数,返回值是逆元
def answer(a,b):        
        #将初始 b 的绝对值进行保存
        if b < 0:
                m = abs(b)
        else:
                m = b
                flag = get_gcd(a, b)
                if flag == 1:	
                        x, y = get_(a, b)	
                        x0 = x % m #对于 Python '%' 就是求模运算,因此不需要 '+m'
                        return x0
                else:
                        return("Do not have!")
 
 
def str_to_hex(s):
    return ' '.join([hex(ord(c)).replace('0x', '') for c in s])
 
def hex_to_str(s):
    return ''.join([chr(i) for i in [int(b, 16) for b in s.split(' ')]])
    
def str_to_bin(s):
    return ' '.join([bin(ord(c)).replace('0b', '') for c in s])
    
def bin_to_str(s):
    return ''.join([chr(i) for i in [int(b, 2) for b in s.split(' ')]])
 
 
 
 
def exGcd(a,b,xy):#求特解
    if b==0:
        xy[0]=1
        xy[1]=0
        #print ("(f, g) is ", a)
        return a
    r=exGcd(b,a%b,xy)
    t = xy[0]
    xy[0] = xy[1]
    xy[1]=t-a//b*xy[1]
    return r
#----------------------------------------- 以下为求出密文的 e 次方 ---------------------------#
 
 
 
 
a=26622572818608571599593915643850055101138771
h=14632691854639937953996750549254161821338360
s=[[2, 1], [3, 1], [5, 1], [7, 1], [11, 1], [13, 1], [17, 1], [19, 1], [29, 1], [31, 1], [37, 1], [41, 1], [47, 1], [53, 1], [61, 1], [73, 1], [97, 1], [101, 1], [103, 1], [107, 1], [113, 1], [137, 1], [139, 1], [151, 1], [167, 1], [173, 1], [179, 1]]
 
g=65537
x=1
n=[]#模数 mi
e=[]#加密指数
c=[]#密文
hi=[]
gi=[]
r=len(s)
 
for i in s:
    for j in range(i[1]):
        x=x*i[0]
        n.append(i[0])
#print(x-(a-1))
 
 
for i in range(r):
    q=a//s[i][0]
    x=pow(g,q,a)
    gi.append(x)
for i in range(r):
    q=a//s[i][0]
    x=pow(h,q,a)
    hi.append(x)
 
for i in range(r):
    for j in range(0,s[i][0]-1):
        x=j
        t=pow(gi[i],x,a)
        if(t==hi[i]):
            c.append(x)
            break
        
 
print(c)
#print(hi)
#print(gi)
#print(len(c)-len(n))
    
    
 
 
Z=1#即是 m
for i in range(r):
    Z=Z*n[i]  
#print(Z)
 
z=[]#保存的是每一项的 ai*Mi*Mi'
 
for i in range(r):
    Mi=(Z//n[i])#即是 Mi
    #print(Mi)
    x=(answer(Mi,int(n[i])))#求出 Mi'
    print(x)
    s=Mi*x
    #print(s)
    s=s*c[i]
    z.append(s)
    
ans=0#求和的结果
for i in z:
        ans=ans+i
 
p=ans%Z#即是密文的 e 次方
#a=e [0]# 本题的加密指数为 5
print(p)
 
'''#———————————————————————以下为大数开方(考虑牛顿迭代法)———————————————#
def five_e_root(x):
        if(x==0):
                return 0
        x0=x
        x1=(4*x0//5)+(x//(x0*x0*x0*x0*5))#迭代法求五次方根
        while(abs(x1-x0)>0.00001):#要求精度
                x0=x1
                x1=(4*x0//5)+(x//(x0*x0*x0*x0*5))
        return x1
                
#print(p)
p=five_e_root(p)
#print(p)#结果
p=hex(p)#转换为16进制
print(p)
        '''

ECDLP

椭圆曲线是secp256k1y2=x3+ax+b,其中a=0b=7p=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F=225623229282726241椭圆曲线是secp256k1 \quad y^2 = x^3 + ax + b,其中 a = 0,b = 7\quad p = FFFFFFFF \quad FFFFFFFF \quad FFFFFFFF \quad FFFFFFFF \quad FFFFFFFF \quad FFFFFFFF \quad FFFFFFFE \quad FFFFFC2F = 2 ^ {256} - 2 ^ {32} - 2 ^ 9 - 2 ^ 8 - 2 ^ 7 - 2 ^ 6 - 2 ^ 4 - 1

G.x=79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798G.x=79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

G.y=483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8G.y=483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

'''
已知私钥为您的学号,求公钥
[115558381663906209150297993116070464229031829974553177032784681955324439750888, 84875200934012589315793426756669380005172249774350913639994928299122491983685]
'''
#coding:utf-8
#欧几里得算法求最大公约数
def get_gcd(a, b):
    k = a // b
    remainder = a % b
    while remainder != 0:
        a = b 
        b = remainder
        k = a // b
        remainder = a % b
    return b
    
#改进欧几里得算法求线性方程的 x 与 y
def get_(a, b):
    if b == 0:
        return 1, 0
    else:
        k = a // b
        remainder = a % b       
        x1, y1 = get_(b, remainder)
        x, y = y1, x1 - k * y1          
    return x, y
 
#返回乘法逆元
def yunsle(a,b):
    #将初始 b 的绝对值进行保存
    if b < 0:
        m = abs(b)
    else:
        m = b
    flag = get_gcd(a, b)
 
    #判断最大公约数是否为 1,若不是则没有逆元
    if flag == 1:   
        x, y = get_(a, b)   
        x0 = x % m #对于 Python '%' 就是求模运算,因此不需要 '+m'
    #print (x0) #x0 就是所求的逆元
        return x0
    else:
        print("Do not have!")
 
 
mod=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
#print(mod)
#mod=23
a=0
b=7
G=[0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8]
#G=[3,10]
#次数
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#私钥 k 为您的学号
k=xxxxxxx
temp=G
 
def get_result2(tmp_list):
  P=tmp_list[0]
  for i in range(1,len(tmp_list)):
    Q=tmp_list[i]
    if P == Q:
        aaa=(3*pow(P[0],2) + a)
        bbb=(2*P[1])
        if aaa % bbb !=0:
            val=yunsle(bbb,mod)
            y=(aaa*val) % mod
        else:
            y=(aaa/bbb) % mod 
    else:
        aaa=(Q[1]-P[1])
        bbb=(Q[0]-P[0])
        if aaa % bbb !=0:
            val=yunsle(bbb,mod)
            y=(aaa*val) % mod
        else:
            y=(aaa/bbb) % mod
    Rx=(pow(y,2)-P[0] - Q[0])  % mod
    Ry=(y*(P[0]-Rx) - P[1])  % mod
    P=[Rx,Ry]
  return P
 
 
def jieguo(G,num):
    global list1
    temp=G
    i=2
    while(i*2<=num):
            aaa=(3*pow(temp[0],2) + a)
            bbb=(2*temp[1])
            if aaa % bbb !=0:
                val=yunsle(bbb,mod)
                y=(aaa*val) % mod
            else:
                y=(aaa/bbb) % mod
    
            Rx=(pow(y,2)-temp[0] - temp[0]) % mod
            Ry=(y*(temp[0]-Rx) - temp[1]) % mod
            temp=[Rx,Ry]
            i=i*2
    list1.append(temp)
    rest_num=num-i
    if rest_num!=0:
        jieguo(G,rest_num)
 
 
list1=[]
jieguo(G,k)
list1.append(G)
result=get_result2(list1)
 
 
print(result)
 
 
 
#print(temp)

加以验证一下

总的来说就是求指数 x,转换为 log 进行离散计算

αx=βmodP\alpha^x=\beta mod P

更新于

请我喝[茶]~( ̄▽ ̄)~*

1sme 微信支付

微信支付