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

基础知识

ElGamal

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

加密：选择随机的$r$，其中$0<r<p-1,r\in\mathbb Z$，得到密文$(y_1,y_2)$为$(g^r\bmod p,my^r\bmod p)$，其中$m$为明文。

解密：通过私钥$k$计算：

$$
\begin{align*}
\displaylines{
&\left(y_1^k\right)^{-1}y_2\bmod p\\
=&(g^{rk})^{-1}my^r\bmod p\\
=&m
}
\end{align*}
$$

ECC

圆锥曲线公钥密码使用形如$y^2=x^3+ax+b$且满足$(4a^2+27b^2)\bmod p\neq 0$的曲线来进行计算。

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

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

加密：选择一个小于曲线$E$的阶的随机$k$，其中$k\in\mathbb N_+$，计算$kG=(x_1,y_1)$，将待加密的信息编码为$E$上的一个点，计算$M+kP=(x_2,y_2)$，其中$P$为公钥，加密结果为$((x_1,y_1),(x_2,y_2))$。

解密：计算$n(x_1,y_1)=nkG=kP$，得到明文$M=(x_2,y_2)-kP$。

暴力计算

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

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

暴力解法：

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=g^x\bmod p$：

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='+')

椭圆曲线的情况：

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='+')