Crypto入门-离散对数相关入门

基础知识

ElGamal

密钥生成方法：选择一个p∈P和Zp∗，且p−1有很大的素因子，选取Zp∗的生成元g，选择随机的k，其中0<k<p−1,k∈Z，计算y=gkmodp，即得到公钥为(p,g,y)，私钥为k。

加密：选择随机的r，其中0<r<p−1,r∈Z，得到密文(y1,y2)为(grmodp,myrmodp)，其中m为明文。

解密：通过私钥k计算：

(y1k)−1y2modp=(grk)−1myrmodp=m

ECC

圆锥曲线公钥密码使用形如y2=x3+ax+b且满足(4a2+27b2)modp≠0的曲线来进行计算。

对于圆锥曲线上的一个整点P=(x,y)，规定加法为：作P的切线交于圆锥曲线于另一点R，过R作Y轴的平行线交曲线于Q，则P+R=Q。规定乘法为：nP等于n个P相加，则n=logP⁡nP。如果nP可以表示椭圆曲线中的所有点，则称P为椭圆曲线的一个生成元，使nP称为无穷远点的最小的n称为P的阶。

密钥生成方法：选择一条满足性质的公开的圆锥曲线E和它的生成元G，再选择一个n∈N+，计算P=nG，公钥为P，私钥为n。

加密：选择一个小于曲线E的阶的随机k，其中k∈N+，计算kG=(x1,y1)，将待加密的信息编码为E上的一个点，计算M+kP=(x2,y2)，其中P为公钥，加密结果为((x1,y1),(x2,y2))。

解密：计算n(x1,y1)=nkG=kP，得到明文M=(x2,y2)−kP。

暴力计算

当p小于1e7数量级时可考虑暴力计算，时间复杂度为O(n)。

例如以下曲线和点，求logP⁡Q：a=123,b=234,p=31337,P(233,18927),Q(1926,3590)。

暴力解法：

python
1
2
3
4
5
6
7
8
9
#sage
k.<a>=GF(31337)
E=EllipticCurve(k,[123,234])
P=E([233,18927])
Q=E([1926,3590])
for i in xrange(31337):
    if(i*P==Q):
        print i
        break

更高效的计算方法

在p=31337,g=5,y=15676情况下，解y=gxmodp：

python
1
2
3
4
5
6
7
8
9
10
11
12
#sage
F=GF(31337)
g=F(5)
y=F(15676)
#BSGS大步小步算法 通用 时间复杂度$O(\sqrt{2})$
x=bsgs(g,y,(0,31336),operation='*')
#自动选择BSGS或Pohlig Hellman算法 当模数没有大素数因子 时间复杂度$O(\sqrt{p})$（p为模数最大素因子）
x=discrete_log(y,g,operation='*')
#Pollard rho算法 模p乘法群的阶为素数 时间复杂度$O(\sqrt{2})$
x=discrete_log_rho(y,g,operation='*')
#Pollard Lambda算法 确定所求值在某一小范围
x=discrete_log_lambda(y,g,(5000,6000),operation='+')

椭圆曲线的情况：

python
1
2
3
4
5
6
7
8
k.<a>=GF(31337)
E=EllipticCurve(k,[123,234])
P=E([233,18927])
Q=E([1926,3590])
#BSGS
n=bsgs(P,Q,(0,31336),operation='+')
#BSGS或Pohlig Hellman
x=discrete_log(Q,P,operation='+')