在整数中,离散对数(Discrete Logarithm, DL)是一种基于同余运算和原根的一种对数运算。
在任何群 $G$ 中可为所有整数 $k$ 定义一个幂数为 $b^k$,而离散对数 $\log_ba$ 是指使得 $b^k = a$ 的整数 $k$。 离散对数在一些特殊情况下可以快速计算。然而,通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础,是假设寻找离散对数的问题解,在仔细选择过的群中,并不存在有效率的求解算法。
基本定义
生成元
在一个群 $G$ 中,如果 $g$ 是 $G$ 的生成元,即所有 $G$ 中的所有元素都可以被表示成 $y=g^x$,此时的 $x$ 称为 $y$ 在 $G$ 中的对数。
阶
设 $m \ge 1,\gcd(a,m)=1$,使得 $a^d \equiv 1 \pmod m$ 成立的最小正整数 $d$ 称为 $a$ 对模 $m$ 的指数或者阶。一般将其计为 $\delta_m(a)$。
满足 $a^d \equiv 1 \pmod m$ 的 $d$ 一定满足 $d \mid \varphi(m)$。
原根
当 $\delta_m(a)=\varphi(m)$ 时,称 $a$ 是模 $m$ 的原根,简称 $m$ 的原根。
只有 $m=2,4,p^\alpha,2p^\alpha$($p$ 为奇素数,$\alpha$ 为正整数)时,模 $m$ 的剩余系存在原根。(充要条件)
常规Sage函数
参数说明:求解以base
为底,a
的对数;ord
为base
的阶,可以缺省,operation
可以是+
与*
,默认为*
;bounds
是一个区间(ld,ud)
,需要保证所计算的对数在此区间内。
discrete_log(a,base,ord,operation)
通用的求离散对数的方法。
discrete_log_rho(a,base,ord,operation)
求离散对数的Pollard-Rho算法。
discrete_log_lambda(a,base,bounds,operation)
求离散对数的Pollard-kangaroo算法(也称为lambda算法)。
bsgs(base,a,bounds,operation)
小步大步法。
1 | #生成64位的素数p作为模数,int为32位,超过int要在数字后加L |
1 | #计算DLP的通用方法 |
大步小步算法(BSGS)
大步小步算法常用于求解用于解决解高次同余方程的问题,问题形式如:有同余方程$a^x \equiv b \pmod p$,$p$ 为质数,求最小非负整数解 $x$ 使得原方程成立。这类问题也称为离散对数问题。该算法的复杂度可以达到$O(\sqrt{p}\log{n})$甚至更低。
1 | #Sage |
1 | def babystep_giantstep(g, y, p): |
Pollard Rho算法
Pollard Rho算法是一种随机性的概率型算法,基于PR算法我们可以加速大整数的因子分解,这也是1975年Pollard提出该算法时的应用方面,这可以用来攻击RSA的公钥密码体制,之后在1978年Pollard又利用循环群 $ρ$ 形的特点提出了用于解决离散对数问题的PR算法,后来也扩展到了椭圆曲线上,这样PR算法便成功威胁到了整个公钥密码体系。
解决离散对数问题的Pollard Rho算法,可以帮助我们在有限的循环群上解决离散对数问题。简单来看我们取一个大素数 $P$,设 $G$ 为一个乘法的循环群,其生成元为 $g$,则该群的阶就是 $N=P-1$。此时在 $G$ 上的离散对数问题就是对于 $G$ 中的元素 $q$,找到 $x$ 使得 $g^x=q$,而Pollard Rho算法主要就是利用了循环群的生成序列呈现一个 $ρ$ 字形状。
使用Pollard Rho算法后可以将求解的时间复杂度降到 $O(\sqrt{N})$,至于空间复杂度则可以忽略不计,因为该算法是个概率型算法,每次只随机选取一对进行比较,所以不会占用存储,这与大步小步算法相反,其实PR算法也可以看作是大步小步算法的随机化版本,继承令时间复杂度的有点,同时还减少了空间的消耗,因为大步小步算法需要占用大量的存储空间。
此算法适用于生成元的阶的素因子都是大数的情形。
参考:https://xz.aliyun.com/t/2780
1 | #Sage |
1 | def pollard_rho(g, y, p): |
Pohlig-Hellman算法
Pohig-Hellman算法是一种求解光滑阶循环群上的离散对数的方法。
Pohlig-Hellman算法的复杂度在一般情况下比BSGS算法高,但是在特殊情况下(循环群的阶是光滑数,即可以因子分解成较小的数的乘积),使用Pohlig-Hellman能取得好的效果。而且有些时候,尽管BSGS能够将复杂度降至$\sqrt{p}$,但是这个数依然很大,所以不能用。这时可以考虑Pohlig-hellman方法能不能起作用。
算法思想
考虑DLP问题:$a^x \equiv b \pmod p$,因为 $p$ 是大素数,模 $p$ 的循环群的阶是 $p−1$。假设模 $p$ 的最小的本原元是 $g$(本原元是可以求的),那么有
$\left\{\begin{array}{c} a \equiv g^{a’} \pmod p \\ b \equiv g^{b’} \pmod p \end{array}\right.$
进一步有 $a^x \equiv b \pmod p \Longleftrightarrow g^{a’x} \equiv g^{b’} \pmod p$,
有 $a’x \equiv b’ \pmod {p-1}$,
如果求出了满足上式的 $a’$ 和 $b’$ ,通过扩展gcd方法可以求一次同余方程的解得到 $x$ 。
问题归结成如何求 $a’$ 和 $b’$ ,即原本的一个离散对数问题,现在变成两个离散对数问题:
$\left\{\begin{array}{c} a \equiv g^{a’} \pmod p \\ b \equiv g^{b’} \pmod p \end{array}\right.$
以求 $a’$ 为例,解DLP问题:$g^x \equiv a \pmod p$:
将 $p-1$ 进行标准的素因子分解,即 $p-1=\prod\limits_{i=1}^{m} p_i^{k_i}=p_1^{k_1}p_2^{k_2}p_3^{k_3} \cdots p_m^{k_m}$;
对每个素因子 $p_i$,将 $x$ 表示成 $p_i$ 进制,有
$x=a_0+a_1p_1+a_2p_2^2+a_3p_3^3+\dots+a_{k_i-1}p_i^{k_i-1} \pmod {p_i^{k_i}}$,
这样的 $p_i$ 进制表示,系数 $a_i$ 自然是小于 $p_i$;
令 $r=1$,有 $(g^x)^{\frac{p-1}{p_i^r}} \equiv a^{\frac{p-1}{p_i^r}} \pmod p$,展开 $x$ 有
$(g^{a_0+a_1p_1+a_2p_2^2+a_3p_3^3+\dots+a_{k_i-1}p_i^{k_i-1}})^{\frac{p-1}{p_i^r}} \equiv a^{\frac{p-1}{p_i^r}} \pmod p$
$g^{a_0{\frac{p-1}{p_i}}} \cdot g^{a_1(p-1)} \cdot g^{a_2(p-1)p_i} \cdots g^{a_{k_i-1}(p-1)p_i^{k_i-2}} \equiv a^{\frac{p-1}{p_i}} \pmod p$
注意从第二项开始,每一项指数都包含 $p−1$(由费马小定理知 $g^{p-1} \equiv 1 \pmod p$),所以式子变成
$g^{a_0{\frac{p-1}{p_i}}} \equiv a^{\frac{p-1}{p_i}} \pmod p$
这个式子中只有 $a_0$ 是未知的,因为 $a_0 \in [0,p_i−1]$,所以可以穷举得到 $a_0$ 的值。
再令 $r=2,3,4,\cdots,k_i$,重复步骤3,依次穷举求出 $a_1,a_2,\cdots,a_{k_i-1}$,整个的时间复杂度是 $\mathrm{O}(p_ik_i)$。可以得到
$x=a_0+a_1p_1+a_2p_2^2+a_3p_3^3+\dots+a_{k_i-1}p_i^{k_i-1} \pmod {p_i^{k_i}}$
重复上述过程,得到 $m$ 个关于 $x$ 的式子,利用中国剩余定理(CRT),可以计算出 $x$ 的值。
利用这个方法求出 $a’$ 和 $b’$ 后,就可以得到原DLP问题的解。
注:
Pohlig-Hellman算法最重要的点是利用了原根的性质,它只能解决 $a \equiv g^x \pmod p$($g$ 是原根)的问题,对于 $g$ 不是原根的情况,需要利用原根将原方程转化成两个关于原根的离散对数问题。
注意Pohlig-hellman只能用于求解光滑阶群,也就是 $p-1$ 可以分解成小的素因子乘积。否则,穷举 $a_i$ 的时间复杂度依旧很高。另外可以考虑在穷举 $a_i$ 时利用小步大步算法,进一步优划算法复杂度。
1 | # Baby-step Giant-step法 |
指数计算法 / Index Calculus Algorithm
1 | def is_Bsmooth(b, n): |
多项式DLP
1 | #Sage |
矩阵DLP
给定 $n$ 阶矩阵 $G$,求满足 $G^x=H$ 的 $x$ 值。
通常矩阵的乘法是复杂的,而矩阵的幂就更是这样了。注意到 $A^n=P(P^{-1}AP^n)P^{-1}$,
如果能找到合适的矩阵 $P$ 使得 $P^{−1}AP$ 的幂是简单的,就找到了计算矩阵的幂乃至多项式的简便方法。例如计算对角矩阵的幂只需对分量求幂,这就非常简单。
但是并非所有的 $n$ 阶矩阵都可以对角化,经过复杂的论证,得知 $n$ 阶矩阵一定有 Jordan 标准型,也就是对于 $n$ 阶矩阵 $A$,构造可逆矩阵 $P$ 使得 $P^{-1}AP=\text{diag}\{J_1,J_2,\cdots,J_s\}$,其中 $J_1,J_2,\cdots,J_s$ 是 Jordan 块。所谓特征值为 $\lambda$ 的 $n$ 阶 Jordan 块,就是 $n$ 阶矩阵
$J_n(\lambda)=\left(\begin{matrix} \lambda & 1 & 0 & \cdots & 0 & 0 \newline 0 & \lambda & 1 & \cdots & 0 & 0 \newline 0 & 0 & \lambda & \cdots & 0 & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & 0 & \cdots & \lambda & 1 \newline 0 & 0 & 0 & \cdots & 0 & \lambda \newline \end{matrix}\right)$
特别地,对于矩阵 $A$ 可对角化的情形,相应的 Jordan 块 $J_1,J_2,\cdots,J_s$ 均为一阶的。
计算 $(J_n(\lambda))^k$. 注意到 $J_n(\lambda)=\lambda E+J_n(0)$, 应用二项式定理,得到
$(J_n(\lambda))^k=\left(\begin{matrix} \lambda^k & k\lambda^{k-1} & \cdots & \mathrm{C}_k^{n-1}\lambda^{k-n+1} \newline 0 & \lambda^k & \cdots & \mathrm{C}_k^{n-2}\lambda^{k-n+2} \newline \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & \cdots & \lambda^k \newline \end{matrix}\right)$
参考:Sharif CTF 8 - ElGamat
1 | n = |