离散对数问题:
在循环群(循环群的定义见密码协议学习笔记(1.4):密码学的一些数学基础 - Isakovsky - 博客园 (cnblogs.com))$(\mathbb{G},\cdot)$上已知两个元素$g,h\in\mathbb{G}$,求式子$g^x=h$中$x$的值的问题,叫做离散对数问题,亦可记为$x=\log_gh$
BSGS(Baby Step Giant Step,大步小步)算法:
本质上是一种分块.
选取$t$使得群的阶$|\mathbb{G}|\leq t^2$,将$x$表示为$x=At+B$,其中$A,B\in[0,t-1]$.
小步:预处理出$B=0,1,\cdots,t-1$时,$h\cdot g^{-B}$的值保存到dict里.注意,为了方便查找,应当将$h\cdot g^{-B}$作为下标,$B$作为值.
大步:遍历$a=0,1,\cdots,t-1$,计算$g^{At}$的值,然后在预处理信息中查找是否存在$B$满足$g^{At}=h\cdot g^{-B}$,则说明$g^{At+B}=h$,将答案输出即可.
示例代码:在$y^2=x^3+ax+b \mod p$的椭圆曲线循环群$E_p(a,b)$(参见密码协议学习笔记(1.5):几种常用的非对称密码体系 - Isakovsky - 博客园 (cnblogs.com))上求解离散对数
import math
def qpow(base,exp,mod): #快速幂
ans = 1
while(exp>0):
if(exp%2 == 1):
ans = ans*base%mod
exp = exp//2
base = base*base%mod
return ans
def rev(a,mod): #求整数乘法逆元
return qpow(a,mod-2,mod)
def ECCAdd(p1,p2,mod,a,b): #椭圆曲线上的加法
if(p1=='inf'):
return p2
elif(p2=='inf'):
return p1
# 无穷远点定义为零元
x1,y1=p1
x2,y2=p2
if(x1==x2 and y1+y2==mod):
return 'inf'
# 定义关于y轴对称两点(在模意义下实际上是相加得p)互为加法逆元,相加得零元
if(x1==x2 and y1==y2):
λ=(3*x1*x1+a)*rev(2*y1,mod)%mod # 两点不重合,过此两点做一条直线
else:
λ=(y2-y1)*rev((x2-x1+mod)%mod,mod)%mod # 两点重合,则取其与曲线的切线
x3=(λ*λ-x1-x2+mod)%mod
y3=(λ*(x1-x3)-y1+mod)%mod
# 定义这条直线与曲线的另一个交点为群上加法的结果
return (x3,y3)
def ECCMinus(p1,p2,mod,a,b): #做减法就是加上加法逆元
if(p2=='inf'):
return p1
else:
return ECCAdd(p1,(p2[0],mod-p2[1]),mod,a,b)
def ECCMult(k,base,mod,a,b): #椭圆曲线上的数乘(龟速乘)
ans = 'inf'
while(k>0):
if(k%2 == 1):
ans = ECCAdd(ans,base,mod,a,b)
k = k//2
base = ECCAdd(base,base,mod,a,b)
return ans
def ECCValid(p,mod,a,b): #检查点是否在椭圆曲线上
if(p=='inf'):
return True
else:
z=(p[0]*p[0]*p[0]+a*p[0]+b)%mod
if(p[1]*p[1]%mod==z):
return True
else:
return False
mod=11 #定义模数
a=1
b=6 #当4a^3+27b^2 ≠0 mod p 时,可定义一个交换群
print('p =',mod,'a =',a,'b =',b)
if(4*a*a*a+27*b*b%mod==0):
print("无法构成交换群")
exit()
else:
print("可以构成交换群")
# print("群上的元素有:")
# n=0 #统计椭圆曲线上的元素个数
# for x in range(mod):
# z=(x*x*x+a*x+b)%mod
# for y in range(mod):
# if(y*y%mod==z):
# print((x,y))
# n=n+1
# print('inf')
# n=n+1 #这个值同时也是(除零元O以外的)所有的点的阶数
# # 即,使得 nP=O 最小的正整数n
g=(5,2)
h=(8,8)
if(ECCValid(g,mod,a,b)==False):
print("点"+str(g)+"不在曲线上!")
exit(0)
if(ECCValid(h,mod,a,b)==False):
print("点"+str(h)+"不在曲线上!")
exit(0)
print('求解log('+str(g)+','+str(h)+')')
if(h=='inf'):
print('log('+str(g)+','+str(h)+')=0')
elif(g=='inf'):
print('无解!')
else:
t=math.ceil(math.sqrt(2*mod+1))
dict0={}
#预处理
for B in range(t):
val=ECCAdd(h,ECCMult(B,ECCMinus('inf',g,mod,a,b),mod,a,b),mod,a,b) # h*g^{-B}
dict0[val]=B
for A in range(t):
val=ECCMult(t*A,g,mod,a,b)
if(dict0.get(val) is not None):
print('log('+str(g)+','+str(h)+')='+str(A*t+dict0[val]))
exit(0)