Cata1yst's blog

祇今尚有清流月，曾照高王万马过

0%

key recovery for RSA DSA and DH with partial key leaked

发表于 更新于 分类于 ，
记录一下公钥密码体制下各种私钥泄露的攻击手段

摘要

本篇的攻击针对于 $RSA$ 、 $DSA$ 、 $DH$ 三种情况，只是自己的理解。内容来自于Recovering cryptographic keys from partial information, by example

数学基础

​ 这里会频繁用到 $coppersmith$ 的攻击，所以需要对格理论具有一定了解。本人对格也是一知半解，只能讲述一下自己的理解和该理论的一些结论。

一元 $coppersmith$ 攻击

​ 首先是格，格的抽象定义就是一组在欧氏空间中的线性无关的向量的线性组合，而这组线性无关的向量称为格的一组基。如果只从计算需要来说，格就是一个秩不为0的方阵。

​ 然后是格中最短向量的问题，这里不得不说一下伟大的 $Minkowski$ 边界。我们假设格中最短向量是 $\overrightarrow \lambda_1$ 那么它应该满足下面的式子：
$$
||\overrightarrow \lambda_1||<\sqrt(n)*det(L)^\frac{1}{n}\ \ \ \ n是格的维数，L是格的基矩阵
$$
​ 接下来是 $LLL$ 算法，这个算法的具体原理不展开了，结论就是这个算法作用于任何一个格，会返回它的一组约化基 $b_1…b_n$ ，它们满足下面的约束
$$
||\overrightarrow{b_1}|| \le 2^\frac{n-1}{4}*det(L)^\frac{1}{n}
$$
需要指出，约化基满足的条件不只有这一条，但是我们接下来讨论的问题中多数时候只用到了这个。

​ 最后来看 $coppersmith$ 给出的攻击模式。首先我们知道，对于方程 $f(x)=0$ 我们是比较容易找到它的解的，无论是求根公式抑或是牛顿法都是计算机能够完成的。那么再来看 $f(x)=0\ mod \ n$ ，这实际上是一个二元高次方程，以及是几乎不可能求解了。我们很自然地想到，是否存在一个办法可以实现 $f(x)=0\ mod\ n$ 到 $f(x)=0$ 的转化，但不改变它的解。
$$
\begin{align}
&Howgrave-Graham引理\\
&设h(x)是含有\lambda个单项式的多项式，满足\\
&h(x)=0\ mod\ n，且其解|x_0|<X\\
&若||\overrightarrow{h(xX)}||<\frac{n}{\sqrt \lambda}，其中\overrightarrow{h(xX)}是多项式h(xX)的系数向量\\
&则x_0是h(x)=0的一个解
\end{align}
$$
​ 这个证明比较简单，
$$
\begin{align}
&|h(x_0)|=\sum_ia_ix_0^i\le\sum_i|c_ix_0^i|\le\sum_i|c_i|X^i\\
&由基本不等式\ \frac{\sum_ix_i}{n}\le\sqrt \frac{\sum_ix_i^2}{n}得\\
&\sum_i|c_i|X^i\le \sqrt{\lambda\sum_i(c_iX^i)^2}=\sqrt \lambda||\overline{h(xX)}||<n
\end{align}
$$
也就是说，$h(x_0)$ 既是 $n$ 的倍数又比它小，那么显然只能是等于0了。

延申知识——多元 $coppersmith$ 攻击

多元 $coppersmith$ 攻击的本质和一元是一样的，只不过这里我们求解的是 $n$ 元高次方程。

首先利用 $coppersmith$ 方法，我们得到一组从小到大的向量。之前我们只采用了第一个向量构造多项式，现在为了求解这 $n$ 个未知数，我们至少需要 $n$ 个方程才行，于是我们需要采用约化基的 $n$ 个向量。

多元 $coppersmith$ 的第一个困难在于，没有已知的定理告诉我们约化基其他向量的大小（第一个向量有闵可夫斯基定理约束）我们需要验证所选向量是否满足 $||v_i||< N$ 。而随着未知数地增多，这个条件会很难满足。

不论如何，假设我们已经通过上述方法成功构造了一系列争整数域的方程，如何求解多元高次方程依旧是一个难题。这里我们使用魔法——结式 （$resultant$）。

原理不太好懂，这里给出个人理解。首先是结式原本只作用于一元多项式，比如我们有两个多项式 $f(x)、g(x)$ ，我们把它们的系数按照一定的规则构成一个行列式，这个行列式有一个专属名词—— $Sylvester$ 行列式。然后有定理告诉我们当多项式 $f、g$ 互素的时候，该行列式的值为0。

以二元多项式为例，我们把其中一个元 $y$ 看作是系数的一部分放进行列式，那么行列式的值应该是 $y$ 的一个多项式 $h(y)$ 。如果我们已知这两个二元多项式互素，则 $h(y)=0$ 。

如果觉得上面的描述不太清楚，也可以单纯地理解为二元方程消元（你可以控制消哪个元）。不论怎么说，运用结式我们得到了一个整数域的一元方程，完全可解，然后把解带入回原方程求解另一个未知数即可。

那么显然，如果之前选取的向量所构成的多项式中有两个是不互素的，我们需要重新选取向量构造。这使得对于 $n$ 元 $copper$ ，我们往往需要选取多于 $n$ 个向量才能够求解，导致了 $||v_i||< N$ 这一个条件更难被满足。

至此我们基本上回顾了一遍之后我们需要用到的数学知识。

$RSA$

基本原理

这里不是说 $RSA$ 的原理。我们知道 $RSA$ 有几个比较重要的参数，$p、q、d、d_p、d_q$ ，以及下面的几个方程
$$
\begin{align}
&pq=N\tag{1}\\
&ed=1\ mod\ (p-1)(q-1)\ \Leftrightarrow\ ed=1+k(p-1)(q-1),1<k<e\tag{2}\\
&ed_p=1\ mod\ (p-1)\ \Leftrightarrow\ ed_p=1+k_p(p-1),1<k_p<e\tag{3}\\
&ed_q=1\ mod\ (q-1)\ \Leftrightarrow\ ed_q=1+k_q(q-1),1<k_q<e\tag{4}\\
&(ed_p-1-k_q)(ed_q-1-k_q)=k_pk_qN\ \Leftrightarrow\ (k_p-1)(k_q-1)=k_pk_qN\ mod\ e\tag{5}\\
&k=-k_pk_q\ mod\ e\tag{6}\\
&p=gcd(\frac{ed_p − 1}{k_p} + 1, N)\tag{7}\\
&p = gcd(a^{ed_p−1} − 1, N),a\in\ Z_N\tag{8}
\end{align}
$$
利用这些方程，我们只需要直到上述五个值中的任意一个，就可以计算其他的，从而分解 $N$ 达到攻击目的。而我们的基于部分私钥泄露的攻击也是以此作为基础的。

$p$ 的高（低）位泄露

这个问题非常经典，我们一样构造方程 $f(x)=0\ mod\ p^b$ ，这里我们通过组合 $h(x)=(p_0+x)$ 和 $N$ 来构造一系列满足条件的方程 $N^{b-i}h(Xx)^{i}\ ,0\le i\le b-1$ 以及 $x^{b-i}h(Xx)^b\ 0\le i \le b$ 。这样我们可以得到 $2b+1$ 个解相同的方程，正好组成一个 $2b+1$阶方阵。下面以 $b=2$ 为例构造格，$X$ 为 $x$ 的上界
$$
\left[\begin{matrix}
X^4&2p_0X^3&p_0^2X^2&0&0\\
0&X^3&2p_0X^2&p_0^2X&0\\
0&0&X^2&2p_0X&p_0^2\\
0&0&0&NX&p_0N\\
0&0&0&0&N^2
\end{matrix}\right]
$$
同样，我们讨论该方法可解所需的条件。$det(L)=X^{b(2b+1)}N^{\frac{b(b+1)}{2}}$ ，这里取 $p>\sqrt N$ 由此得到 $X<\frac{1}{\sqrt 2}N^{\frac{b}{2(2b+1)}}(2b+1)^{\frac{1}{2b}}\approx N^{\frac{b}{2(2b+1)}}$ 。显然我们容易得出一个极限就是 $N^{\frac{1}{4}}$ ，也就是说我们必须知道一半以上的 $p$ 时才可能计算出结果。

上面讨论的都是 $p$ 的高位泄露，如果换成低位泄露，思路也是一样的，就不再赘述了（脚本改一下就行）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#p高位泄露攻击
def RSA_most_significant_bits_of_p(n,p0,bits):
    PR.<x>=PolynomialRing(Zmod(n))
    f=p0+x
    f=f.monic()
    roots=f.small_roots(X=1<<bits,beta=0.4)
    if(roots):
        X=roots[0]
        p=ZZ(p0+X)
        assert n%p==0,n%p
        print(f"p={p}")
        return p
    print("not found")
#p低位泄露攻击
def RSA_least_significant_bits_of_p(n,p0,bits):
    k=1<<p0.bit_length()
    PR.<x>=PolynomialRing(Zmod(n))
    f=p0+k*x
    f=f.monic()
    roots=f.small_roots(X=1<<bits,beta=0.4)
    if(roots):
        X=roots[0]
        p=ZZ(p0+k*X)
        assert n%p==0,n%p
        print(f"p={p}")
        return p
    print("not found")

$p$ 的连续中间比特泄露

二元 $coppersmith$ 。

首先是方程 $f(x,y)=x+a+2^ty\ mod\ p$ ，设 $X,Y$ 分别是 $x,y$ 的上界。为了尽可能使得约化基中各个向量的范数小于 $p$ ，我们可以稍微使格大一些。比如我们使用$f^3、f^2y、fy^2、y^3N、f^2、fy、y^2N、f、yN、N$ 这一系列模 $p$ 的方程，把它们的系数放进格子里。
$$
\left[\begin{matrix}
X^3&3\cdot2^tX^2Y&3\cdot2^{2t}XY^2&2^{3t}Y^3&3aX^2&6\cdot2^taXY&3\cdot2^{2t}a\cdot Y^2&3\cdot a^2X&3\cdot 2^t\cdot a^2Y&a^3\\
0&X^2Y&2\cdot2^tX^2Y&2^{2t}XY^2&0&2aXY&2\cdot2^taY^2&0&a^2Y&0\\
0&0&X^2Y&2^tY^3&0&0&aY^2&0&0&0\\
0&0&0&Y^3N&0&0&0&0&0&0\\
0&0&0&0&X^2&2\cdot2^tXY&2^{2t}Y^2&2aX&2^{2t}aY&a^2
\end{matrix}\right]
$$
剩下的几行摸了（明白就彳亍

然后我们拿出约化基中的两个基向量作为方程系数，利用结式求解即可。需要注意，一般来说我们是直接拿第一二行用，但有时候可能得到的两个多项式不互素，这时候只能拿更大的向量来构造多项式了。

稍微描述一下这个方法的缺陷困难性，即保证 $||v_i||\le p$ 。首先就是我们需要多个约化基向量，而 $copper$ 只能保证第一个约化向量的范围。然后就是最终构造的整数域方程的互素问题，这可能导致我们被迫选取更大的约化向量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#根据给定系数和自变量列表构造多元多项式
def gen_function(coe_list,var_list):
    assert len(coe_list)==len(var_list)
    f=0
    for i in range(len(coe_list)):
        f+=coe_list[i]*var_list[i]
    return f
#根据多项式、自变量上界、自变量列表构造格
def gen_matrix(f_list,upper_list,var_list):
    assert len(f_list)==len(var_list)==len(upper_list)
    s=gen_function([1]*len(var_list),var_list)
    L=[]
    for i in range(len(f_list)):
        cc=(f_list[i]+s).coefficients()
        coe=[(cc[_]-1)*upper_list[_] for _ in range(len(cc))]
        L.append(coe)
    return matrix(L)
def RSA_middle_bits_of_p(X,Y,N,p0,bits):
    PRxy.<x,y> = PolynomialRing(ZZ)
    f=x+(2^bits)*y+p0
    variable=[x^3,x^2*y,x*y^2,y^3,x^2,x*y,y^2,x,y,1]
    f_list=[f^3,f^2*y,f*y^2,y^3*N,f^2,f*y,y^2*N,f,N*y,N]
    upper_list=[X^3,X^2*Y,X*Y^2,Y^3,X^2,X*Y,Y^2,X,Y,1]
    #格构造及规约
    L=gen_matrix(f_list,upper_list,variable)
    LLL=L.LLL()
    Coefficient=[]
    #将约化基还原成系数矩阵
    for i in range(len(f_list)):
        Coefficient.append([int(LLL[i][j])//upper_list[j] for j in range(len(list(LLL[i])))])
      #取出两组系数矩阵构造二元方程组，其范数小于p
    h=gen_function(Coefficient[1],variable)
    g=gen_function(Coefficient[2],variable)
    #取结式消元
    q=h.resultant(g)
    assert q!=0,"两个方程不互素,请重新选择向量"
    q=q.univariate_polynomial()
    PRx.<xn>=PolynomialRing(ZZ)
    q=q.change_ring(PRx).subs(y=xn)
    q=q.monic()
    #求取结式的根即为y
    roots=q.roots()
    assert roots,"No roots found"
    res_y=int(roots[0][0])
    #将Y回代入上述方程之一，再解一元方程即得x
    g=eval(str(g).replace('y','res_y').replace('^','**'))
    g=g.change_ring(PRx).subs(x=xn)
    res_x=g.roots()[0][0]
    p=int(f(res_x,res_y))
    q=N//p
    assert p*q==N,"error"
    print("p={}\nq={}".format(p,q))
    return p,q
p,q=RSA_middle_bits_of_p(X,Y,N,p0,bits)

啸砣斩

有了上面几种关于 $p$ 泄露的情形，我们不禁思考如果 $p$ 泄露了不连续的多段比特，是否还可以恢复。其实这就是一个多元 $copper$ 问题，显然随着未知元的增多，我们需要更多的约化向量来构造我们的方程，那么在保证各个向量的范数小于 $p$ 这件事上的困难就更大了。

当然如果可解，方法还是和二元的差不多的。

低加密指数下明文部分泄露

当我们已知 $m$ 的一部分 $m_0$ 时，构造方程 $f(x)=(m_0+x)^e=c\ mod\ N$ ，联系我们之前关于格的知识，我们需要构造一个长度小于 $N$ 的方程。于是我们利用一系列解和 $f(x)$ 相同的方程 $f(Xx)$ 、$Nx^i$ 的系数向量构造一个格（这里取 $e=3$ ，$M$ 是 $x$ 的上界 ）
$$
\left[\begin{matrix}M^3&3m_0M^2&3m_0^2M&m_0^3\\
0&NM^2&0&0\\0&0&NM&0\\0&0&0&N
\end{matrix}\right]
$$
我们分析一下此方法成功所需要的对 $m_0$ 的约束。

对于加密指数为 $e$ 的情况，$det(L)=M^{\frac{e(e+1)}{2}}N^e$ ，根据闵可夫斯基边界，约化基的最短向量 $||\overrightarrow b_1||\le(2^{\frac{e}{4}}M^{\frac{e(e+1)}{2}}N^e)^{\frac{1}{e+1}}$ 应当小于 $\frac{N}{\sqrt(e+1)}$ 。这里我们做一些近似计算，在 $e$ 不是很大的情况下（一般都是3左右），$||\overrightarrow b_1||\le (M^{\frac{e(e+1)}{2}}N^e)^{\frac{1}{e+1}}$ , 由此计算得 $M<N^{\frac{2}{e(e+1)}}(e+1)^\frac{1}{e}$ （这个结果是自己计算的，没有验证） 。对于 $e=3$ ，大约需要满足 $M<N^\frac{1}{6}$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def RSA_most_significant_bits_of_m(n,e,bits,c,m0):
	P.<x>=PolynomialRing(Zmod(n))
	f=(m0+x)^e-c
	f=f.monic()
	roots=f.small_roots(X=2^(bits+1),beta=0.5)
	assert roots,"no roots found"
	print(long_to_bytes(m0+int(roots[0])))
RSA_most_significant_bits_of_m(n,e,bits,c,m0)
def RSA_least_significant_bits_of_m(n,e,bits,c,m0):
    k=1<<m0.bit_length()
	P.<x>=PolynomialRing(Zmod(n))
	f=(m0+k*x)^e-c
	f=f.monic()
	roots=f.small_roots(X=2^(bits+1),beta=0.5)
	assert roots,"no roots found"
	print(long_to_bytes(m0+k*int(roots[0])))
RSA_most_significant_bits_of_m(n,e,bits,c,m0)

如果泄露的是高位，原理也是一致的，仿照 $p$ 的情况修改一下 ；中段泄露或者是不连续泄露也可以按照 $p$ 的方法做，不过可能性不大，因为这里原多项式就是三次，构造的格那恐怕要上10了，能不能规约都是问题。

$d_p$ 高位泄露

有了上面的经验，这里就非常好处理了。构造方程 $f(x)=e(a+x)-1+k_p\ mod\ p$ 。这里 $ed_p-1=k_p(p-1)$。现在方程里的未知数还有一个 $k_p$ ，好在我们知道 $1\le k_p<e$ ，一般来说 $e=56637$ 已经是最大了，所以爆破也不难。

那我们稍微修改一下方程 $f(x)=A+x\ mod\ p$ ，其中 $A=a+e^{-1}(k_p-1)$ 。题目完全回到了之前 $p$ 泄露的情况。不过还是有一点小区别的，虽然同为模 $p$ 的方程，在 $p$ 泄露的情形中，$(p_0+x)$ 算出来直接就是 $p$ 的值；而在此处只是 $p$ 的倍数，还需要将计算结果和 $N$ 取公约数才是 $p$ 。

同样地，这里我们最大也只能求解 $X<p^{\frac{1}{2}}$ 的情况。

其实也可以考虑不爆破直接当二元问题求解。（后续补充：自己试了一下，貌似不行，等待好心人解释

顺带一提，这里如果 $e$ 还是一般的65537的话，要花很多时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#高位泄露
def RSA_most_significant_bits_of_dp(d0,n,e,bits):
    P.<x>=PolynomialRing(Zmod(n))
    for k in range(1,e):
        f=e*(d0+x)+k-1
        f=f.monic()
        roots=f.small_roots(X=2^bits,beta=0.4)
        if roots:
            np=int(f(int(roots[0])))
            p=gcd(np,n)
            q=n//p
            assert p*q==n
            print("p={}\nq={}".format(p,q))
            return p,q
    print("not found")
p,q=RSA_most_significant_bits_of_dp(n,e,d0,bits)
#低位泄露
def RSA_least_significant_bits_of_dp(n,e,d0,bits):
    d0bits=d0.bit_length()
    P.<x>=PolynomialRing(Zmod(n))
    for k in range(1,e):
        f=e*(d0+(2^d0bits)*x)+k-1
        f=f.monic()
        roots=f.small_roots(X=2^bits,beta=0.4)
        if roots:
            np=int(f(int(roots[0])))
            p=gcd(np,n)
            q=n//p
            assert p*q==n
            print("p={}\nq={}".format(p,q))
            return p,q
p,q=RSA_least_significant_bits_of_dp(n,e,d0,bits)

$d$ 低位泄露

$$
\begin{align}
&e(d_0+2^kx)=1\ mod\ \phi(N)\\
\Leftrightarrow&ep(d_0+2^kx)=p+k(Np-p^2-N+p)\\
\Rightarrow&ed_0=p+k(Np-p^2-N+p)\ mod\ 2^k
\end{align}
$$

此时未知数还有 $p、k$ ，仿照前面 $d$ 泄露的处理，我们还是爆破 $k$ ，就可以得到关于 $p$ 的一元二次同余方程，虽然还是很难求解，但是 $sage$ 上有一个 $solve_mod$ 函数可以用。于是我们得到 $p$ 在模 $2^k$ 下的解 $p_0$ ，问题就变成了熟悉的 $p$ 低位泄露了。

关于 $solve_mod$ 的运行时间，貌似每次都要跑很久，对数值比较敏感。（小看了一眼源码，貌似是爆破，以源定真，鉴定为慢）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def partial_p(p0,kbits,n):
    PR.<x>=PolynomialRing(Zmod(n))
    nbits=n.nbits()
    f=2^kbits*x+p0
    f=f.monic()
    roots=f.small_roots(X=2^(nbits//2-kbits), beta=0.4)
    if roots:
        x0=roots[0]
        p=f(x)
        return ZZ(p)
def find_p(d0,kbits,e,n):
    X=var('X')
    for k in range(1,e+1):
        results=solve_mod([e*d0*X-k*X*(n-X+1)+k*n==X],2^kbits)
        for x in results:
            p0=ZZ(x[0])
            p=partial_p(p0, kbits, n)
            if p and p!=1:
                return p
n=
e=
d0=
kbits=d0.bit_length()
p=find_p(d0,kbits,e,n)
q=n//p
assert p*q==n
print(f'p={p}\nq={q}')

顺带一提， $d$ 泄露没有高位的情况，高位没有模 $2^k$ 这样的操作，只有纯纯的三元。

$p、q$ 随机比特泄露

$p、q$ 随机位上的一些比特泄露，显然不可能用 $x$ 元 $coppersmith$ （未知数太多了）。

这个时候不妨采用笨办法——爆破。没错，摁爆。

摁爆也是有寄巧的，我们回忆一下十进制整数的乘法
$$
\begin{array}
\ \ \ \ \ 123\\
\times\ 123\\
\hline
\ \ \ \ 369\\
\ \ 246\\
123\\
\hline
15129\\
\end{array}
$$
不难发现，结果的个位完全由乘数的个位决定，十位由乘数的个位和十位共同决定。换成数学语言，
$$
(a\ mod\ 10^i)\times(a\ mod\ 10^i)\equiv c\ mod\ 10^i
$$
再变得简洁一点
$$
a\times b\equiv c\ mod\ 10^i
$$
是不是发现这是一个显然的命题？

那么我们以此为原理进行爆破，从 $p、q$ 的最后一位开始，如果它们对应位已知，则直接拿来用，否则取遍0、1。之后相乘，根据 $p\times q\equiv n\ mod\ 2^i$ 判断所选取的值是否正确。

我们来分析一下这个方法的可行性,首先如果 $p、q$ 该位均未知，则我们取00、01、10、11四个可能的组合，其中也许会有多个组合满足上式，不论如何，我们暂且将所有满足等式的值记录；如果其中之一的该位泄露或者两个均泄露，我们可以根据泄露值来反推之前保留的那些数是否正确。

这和二叉树有点像，从根节点 $p=0、q=0$ 开始，每次记录的可能值为一层，不过我们在过程中不断否定其中的一些值，最后保留下来的只会有一个。

然后想想最后保留的真的只有一个吗？

如果我们从最低位一直操作到 $pbits(qbits)$ 位，此时的 $p、q$ 满足 $p\times q\equiv n\ mod\ 2^{pbits}$ 。假如有两组 $p、q$ 满足条件，那么一定有 $p_1q\equiv _1p_2q_2\ mod\ 2^{pbits}$ ，这应该不难实现（比如$72\equiv56\ mod\ 8$ 而 $2、7、6$ 都是三位二进制数）。也就是说，只取到 $pbits(qbits)$ 位可能会有多解。好消息是，显然我们需要的 $p、q$ 在这些可能解中，而从这些有限解中找出一组特定的实在不难。于是，该算法是可行的。

然后就是泄露位数问题，这个比较困难。在可接受时间内运行算法，一般要求泄露位数在一半左右（最好以上）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from Crypto.Util.number import *
'''
import random
def hide(p,q,mask):
    p = list(bin(p)[2:])
    q = list(bin(q)[2:])
    while(p.count('*')<mask*(len(p))):
        p[random.randint(1,len(p)-1)]='*'
    while (q.count('*') <mask*(len(q))):
        q[random.randint(1, len(q)-1)] = '*'
    return "".join(p).zfill(k + 1),"".join(q).zfill(k + 1)
#p的比特长度
k = 1024
#掩蔽因子（大约kd位被隐藏）
d = 0.45
#情景生成
p = getPrime(k)
q = getPrime(k)
# print(p)
# print(q)
n = p * q
#泄露的p、q，未知位用*表示
p,q=hide(p,q,d)
print(f"p={p}\nq={q}")
'''
#开始算法
def RSA_random_bits_of_pq(p,q,n):
    P = 0
    Q = 0
    res = [(P, Q)]
    for bits in range(1, k + 2):
        # print(f"bits={bits}")
        new_res = []
        moulde = 1 << (bits)
        # 计算p、q在bits位上可能的值
        qbits = pbits = (0, 1 << (bits - 1))
        if (p[-bits] != "*"):
            pbits = [int(p[-bits]) << (bits - 1)]
        if (q[-bits] != "*"):
            qbits = [int(q[-bits]) << (bits - 1)]
        # 对之前记录的p、q，在加上bits位后验证是否仍然满足条件
        for p_, q_ in res:
            for pbit in pbits:
                for qbit in qbits:
                    tmp_p = p_ + pbit
                    tmp_q = q_ + qbit
                    # 将满足条件的p、q记录
                    if (((tmp_p * tmp_q) % moulde == n % moulde) and (tmp_p, tmp_q) not in new_res):
                        new_res.append((tmp_p, tmp_q))
        res = new_res
    for p, q in res:
        if (p * q == n):
            print(f"p={p}\nq={q}")
            return p, q
    print('not found')
p,q=RSA_random_bits_of_pq(p,q,n)

$Xor\ RSA$

这种情况和随机比特泄露类似，我们已知 $h=p\bigoplus q$ ，那么假定 $p$ 的一位，则 $q$ 的对应位可以根据 $h$ 推算出来

。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import *
'''
#情景生成
k = 100
p = getPrime(k)
q = getPrime(k)
n = p * q
h = p ^ q
'''
#算法主体
def XorRSA(h,n):
    P = 0
    Q = 0
    res = [(P, Q)]
    for bits in range(0, k + 2):
        new_res = []
        moulde = 1 << (bits + 1)
        for pbit in (0, 1 << bits):
            hbit = (h >> bits) % 2
            if (hbit == 1):
                qbit = (moulde >> 1) - pbit
            else:
                qbit = pbit
            for p_, q_ in res:
                p_tmp = p_ + pbit
                q_tmp = q_ + qbit
                if ((p_tmp * q_tmp) % moulde == n % moulde):
                    new_res.append((p_tmp, q_tmp))
        res = new_res
    for P, Q in res:
        if (P * Q == n):
            print(F"p={P}\nq={Q}")
            return P,Q
    print("not found")
p,q=XorRSA(h,n)

$d、d_p、d_q$ 随机比特泄露

算法其实还是爆破，通过确定 $p、q、d、d_p、d_q$ 在特定位上的关系，可以帮助我们判断之前爆破的结果中哪些是错误的。

第一步，我们还是爆破 $k、k_p、k_q$ ，范围都是 $(1,e)$ 。得到 $k$ 以后，我们干一件事，观察$ ed-1=k(p-1)(q-1)$ ，定义一个函数$ \tau(x)={y:2^y|x\ and\ 2^{y+1}\nmid\ x}$ ,那么我们可以得到方程$ d=e^{-1}\ mod\ 2^{\tau(k)}$ 。就是一旦我们爆破了 $k$ ，我们就知道了 $d$ 的某些连续低位。

之后再观察 $ed=k(N-p-q)+1$ ，如果等式右边的 $p$ 的第 $i$ 位发生变化，即 $kp$ 项发生变化。$kp$ 可以写成
$$
\begin{cases}
&k=k_02^{\tau(k)}\\
&p=p_i2^i+p_0\\
&(k_02^{\tau(k)})(p_i2^i+p_0)\\
\end{cases}\\
\begin{align}
\Leftrightarrow&ed-1=(k_0p_i2^{\tau(k)+i})+C\tag{1}\\
\end{align}
$$
而所谓 $p$ 的第 $i$ 位变化其实就是*(1)中 $p_i$ 的最低位变化，那么我们可以看出，这一变化会使得 $k_0p_i$ 的最低位变化；换算到整个式子，就是右边运算结果的第 $\tau(k)+i$ 位变化。这一变化反应到左边来，对应着 $e、d$ 的第 $\tau(k)+i$ 位（可以类比 $n$ 的第 $i$ 位和 $p、q$ 的关系）**。而 $e$ 是确定的，因此得出结论， $p、q$ 的第 $i$ 位决定了 $d$ 的第 $i+\tau(k)$ 位。

该结论对于 $d_p、d_q$ 同样适用。

当然了，也可以完全不按照上述算法，照搬之前的方法全部模 $2^i$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from Crypto.Util.number import *
'''
import random
def hide(p,q,d,mask):
    p = list(bin(p)[2:])
    q = list(bin(q)[2:])
    d = list(bin(d)[2:])
    while(p.count('*')<mask*(len(p))):
        p[random.randint(1,len(p)-1)]='*'
    while (q.count('*') <mask*(len(q))):
        q[random.randint(1, len(q)-1)] = '*'
    while (d.count('*') < mask*len(d)):
        d[random.randint(1, len(d)-1)] = '*'
    return ''.join(p),''.join(q),''.join(d)
#p、q的比特长度
lb=1000
#隐蔽因子
mask=0.6
p,q=[getPrime(lb) for _ in range(2)]
n=p*q
print(f"p={p}\nq={q}")
e=getPrime(10)
d=inverse(e,(p-1)*(q-1))
p,q,d=hide(p,q,d,mask)
print(f"p:{p.count('*')/len(p)}\nq:{q.count('*')/len(q)}\nd:{d.count('*')/len(d)}")
#泄露的p、q，未知位用*表示
p = "".join(p).zfill(lb + 1)
q = "".join(q).zfill(lb + 1)
d = "".join(d).zfill(lb + 1)
print(f"p={p}\nq={q}\nd={d}")
'''
#定义tau函数，含义同前文
def tau(k):
    bit=0
    while(k%(1<<bit)==0):
        bit+=1
    return bit-1
def RSA_random_bit_of_pqd(p,q,d,n):
    # 爆破k
    for k in range(1, e):
        # print(f"k={k}")
        t = tau(k)
        d = d.zfill(t + lb + 1)
        # 计算d的低tau(k)位
        _d = inverse(e, (1 << t))
        # 初始化结果
        res = [(0, 0, _d)]
        for bits in range(1, lb + 1):
            new_res = []
            moulde = 1 << (bits)
            mod = 1 << (bits + t)
            # 寻找p、q的第bits位以及d的bits+tau(k)位的可能值
            qbits = pbits = (0, 1 << (bits - 1))
            dbits = (0, 1 << (bits + t - 1))
            if (p[-bits] != "*"):
                pbits = [int(p[-bits]) << (bits - 1)]
            if (q[-bits] != "*"):
                qbits = [int(q[-bits]) << (bits - 1)]
            if (d[-(bits + t)] != "*"):
                dbits = [int(d[-(bits + t)]) << (bits + t - 1)]
            # 遍历所有可能
            for p_, q_, d_ in res:
                for pbit in pbits:
                    for qbit in qbits:
                        for dbit in dbits:
                            tmp_p = p_ + pbit
                            tmp_q = q_ + qbit
                            tmp_d = d_ + dbit
                            # 将满足条件的p、q记录
                            if (((tmp_p * tmp_q) % moulde == n % moulde) and (
                                    (e * tmp_d) % mod == (1 + k * (n - tmp_p - tmp_q + 1)) % mod)):
                                new_res.append((tmp_p, tmp_q, tmp_d))
            res = new_res
        for P, Q, D in res:
            if (Q * P == n):
                print(f"p={P}\nq={Q}\nd={D}")
                return P,Q,D
    print("not found")
p,q,d=RSA_random_bit_of_pqd(p,q,d,n)

$DSA$

基本原理

稍微提一下 $DSA$ 的原理罢。 $p$ 是一个大素数（一般是1024位）； $q$ 是 $p-1$ 的一个因子（一般是160位左右）； $g$ 满足 $g^q=1\ mod\ p$；$d$ 是一个随机数，$y=g^d\ mod\ p$ 。

签名过程如下
$$
\begin{align}
&r=(g^k\ mod\ p)\ mod\ q，k\in[1,p-1]\tag{1}\\
&s=k^{-1}(h+dr)\ mod\ p，h是消息的哈希值\tag{2}\\
\end{align}
$$
验证过程如下
$$
\begin{align}
&e_1=hs^{-1}\ mod\ q\tag{1}\\
&e_2=rs^{-1}\ mod\ q\tag{2}\\
&ver(key,sign)=true\Leftrightarrow (g^{e_1}y^{e_2}\ mod\ p)\ mod\ q=s\tag{3}
\end{align}
$$
下面是一些私钥恢复过程中常见的恒等式
$$
d=r^{-1}(ks-h)\ mod\ q
$$

随机数 $k$ 过小

这种情况我们需要知道至少两组签名，然后利用 $SVP$ 问题的解法可以解决。
$$
\begin{align}
&r_1=(g^{k_1}\ mod\ p)\ mod\ q\tag{1}\\
&s_1=k_1^{-1}(h_1+dr_1)\ mod\ p\tag{2}\\
&r_2=(g^{k_2}\ mod\ p)\ mod\ q\tag{3}\\
&s_2=k_2^{-1}(h_2+dr_2)\ mod\ p\tag{4}\\
\end{align}
$$
利用第一组签名**(1)、(2)算出 $d$ 的表达式后带入第二组(3)、(4)**
$$
\begin{align}
&k_1−s^{−1}_1s_2r_1r^{−1}_2k_2 + s^{−1}_1r_1h_2r^{−1}_2−s^{−1}_1h_1\equiv0\ mod\ q\\
\Leftrightarrow
&k_1+tk_2+u\equiv 0\ mod\ q\tag{1}\\
&\begin{cases}
&t=−s^{−1}_1s_2r_1r^{−1}_2\\
&u=s^{−1}_1r_1h_2r^{−1}_2−s^{−1}_1h_1
\end{cases}
\end{align}
$$
这样我们得到了一个关于 $k_1、k_2$ 的线性方程，然后构造格
$$
B=\left[\begin{matrix}
q&0&0\\
t&1&0\\
u&0&K
\end{matrix}\right]\\
K是随机数k_1,k_2的上界
$$
显然我们有
$$
\left[\begin{matrix}
n&k_2&1
\end{matrix}\right]*B=
\left[\begin{matrix}
-k_1&k_2&K
\end{matrix}\right]=v\\
其中，k_1+tk_2+u=nq
$$
所以 $v$ 就是格 $B$ 中的一个向量，由于 $K$ 比较小，所以这个向量很可能是格中最短向量，我们利用 $LLL$ 算法即可计算出 $k_1、k_2$ ，然后恢复出私钥 $d$ 。

我们来看一下 $K$ 大致的范围。$LLL$ 算法求解的最短向量满足之前说过的 $||v_1||\le 2^{\frac{n-1}{2}}det(B)^{\frac{1}{n}}$ 。故该解法可行，必须满足
$$
\begin{align}
&||v||\le \sqrt 3K\le||v_1||\le2\sqrt2(qK)^{\frac{1}{3}}\tag{1}\\
\Leftrightarrow&3\sqrt3K^3\le8qK\tag{2}\\
\Leftrightarrow&K^2\le\frac{8}{3\sqrt3}q\tag{3}\\
\Leftrightarrow&K\approx\sqrt q\tag{4}\\
\end{align}
$$
最后附上解题代码

1
2
3
4
5
6
7
8
9
def DSA_with_small_k(q,r1,s1,r2,s2,h1,h2,bits):
    t=-inverse_mod(s1,q)*r1*s2*inverse_mod(r2,q)
    u=inverse_mod(s1,q)*r1*h2*inverse_mod(r2,q)-inverse_mod(s1,q)*h1
    L=matrix(ZZ,[[q,0,0],[t,1,0],[u,0,1<<bits]])
    L=L.LLL()
    k1,k2=-int(L[0][0]),int(L[0][1])
    d=int((inverse_mod(r1,q)*(k1*s1-h1))%q)
    print(f"k1={k1}\nk2={k2}\nd={d}")
    return k1,k2,d

顺带一提，上述方法还有扩展，如果知道更多组签名，就可以进一步扩大 $K$ 的范围。方法是用其中一组计算 $d$ 的表达式后依次带入前面几组得到多元不定方程组然后利用 $SVP$ 问题解答。

已知 $k$ 高位

这个问题其实是前面的延申。

我们令 $k_i=a_i+x_i$ , $|x_i|<X$ ，利用上一个问题的等式得到
$$
\begin{align}
&(a_1+x_1)+t(a_2+x_2)+u\equiv 0\ mod\ q\Leftrightarrow\tag{1}\\
&x_1+tx_2+(a_1+ta_2+u)\equiv 0\ mod\ q\Leftrightarrow\tag{2}\\
&x_1+tx_2+u’\equiv 0\ mod\ q\tag{3}
\end{align}
$$
之后就照搬前面。

1
2
3
4
5
6
7
8
9
def DSA_most_significant_bits_of_k(bits,q,h1,h2,r1,s1,r2,s2,a1,a2):
    t=-1*inverse(s1,q)*s2*r1*inverse(r2,q)
    u=inverse(s1,q)*r1*h2*inverse(r2,q)-inverse(s1,q)*h1+a1+t*a2
    L=matrix(ZZ,[[q,0,0],[t,1,0],[u,0,1<<bits]]).LLL()
    K1=int(-L[0][0])+a1
    K2=int(L[0][1]+a2)
    d=int((int(inverse(r1,q))*(K1*s1-h1))%q)
    print(f"k1={K1}\nk2={K2}\nd={d}")
    return k1,k2,d

既然和前面一模一样，那么 $X$ 的上界也应当小于 $\sqrt q$ ，以及可以利用多组前面扩大 $X$ 的上界。

已知 $k$ 低位

啊这个就，完全和低位泄露一模一样吧，直接上脚本了就。

1
2
3
4
5
6
7
8
9
10
11
12
def DSA_least_significant_bits_of_k(bits,q,r1,s1,r2,s2,h1,h2,a1,a2):
    shift=min(a1.bit_length(),a2.bit_length())
    s1_inv=inverse(s1,q)
    r2_inv=inverse(r2,q)
    t=-1*s1_inv*s2*r1*r2_inv
    u=(s1_inv*r1*h2*r2_inv-s1_inv*h1+a1+t*a2)*inverse(2^shift,q)
    L=matrix(ZZ,[[q,0,0],[t,1,0],[u,0,1<<hbits]]).LLL()
    K1=(int(-L[0][0])<<shift)+a1
    K2=(int(L[0][1])<<shift)+a2
    d=int((int(inverse(r1,q))*(K1*s1-h1))%q)
    print(f"k1={K1}\nk2={K2}\nd={d}")
    return K1,K2,d

边界分析方法同上。

$k$ 中段泄露

这种情况稍微复杂一点，首先我们令 $k_i=2^lx_i+a_i+y_i$ ，利用恒等变换得到
$$
y_1+2^lx_1+ty_2+t2^lx_2+(u+a_1+ta_2)\equiv0\ mod\ q
$$
这是一个四元一次同余方程，需要用 $coppersmith$ 方法转化成整数域方程组，故构造格
$$
B=\left[\begin{matrix}
K&2^lK&tK&2^ltK&u’\\
0&Kq&0&0&0\\
0&0&Kq&0&0\\
0&0&0&Kq&0\\
0&0&0&0&q
\end{matrix}\right]
\\K\ge max{x_1,y_1,x_2,y_2}
\\u’=u+a_1+ta_2
$$
规约后取前四个向量构造方程组求解出四个未知数即可。

边界分析。
$$
\begin{align}
&\begin{cases}
&det(B)=K^4q^4\\
&||v_1||\le(K^4q^4)^{\frac{1}{5}}\le q\\
\end{cases}\\
\Leftrightarrow&K\le n^{\frac{1}{4}}
\end{align}
$$
这只是一个必要条件，因为不知道后三组向量的具体范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def DSA_middle_bits_of_k(bits,q,r1,s1,r2,s2,h1,h2,a1,a2):
    K,1<<bits
    shift=1<<min(len(bin(a1)[2:]),len(bin(a2)[2:]))
    s1_inv=inverse(s1,q)
    r2_inv=inverse(r2,q)
    t=-1*s1_inv*s2*r1*r2_inv
    u=s1_inv*r1*h2*r2_inv-s1_inv*h1+a1+t*a2
    L=[[K,K*shift,K*t,K*t*shift,u],[0,K*q,0,0,0],[0,0,K*q,0,0],[0,0,0,K*q,0],[0,0,0,0,q]]
    L=matrix(L).LLL()
    A=[]
    b=[]
    for i in range(4):
        A.append([_/K for _ in L[i][:-1]])
        b.append(int(-L[i][-1]))
    A=matrix(A).transpose()
    b=vector(b)
    x=A.solve_left(b)
    K1=shift*x[1][0]+a1+x[0][0]
    K2=shift*x[3][0]+a2+x[2][0]
    d=int((int(inverse(r1,q))*(K1*s1-h1))%q)
    print(f"k1={K1}\nk2={K2}\nd={d}")
    return K1,K2,d

$DH(ECDH)$

基本原理

$DH$ 其实还是离散对数问题的一种。给定一组素数 $p、q=2q-1$ ， $g$ 是 $p$ 中阶数为 $q$ 的元素。交换双方分别再选取一个随机数 $a、b$ ，发送 $A=g^a、B=g^b$ 给对方。最终确定密钥为 $s=g^{ab}$ 。

$s$ 高(低)位泄露

想要以此获取 $s$ 的要求有点复杂。首先我们要获得某个参与者(B) 和另外两个参与者(A、C)之间的交换信息，同时还要知道 A、C两人私钥差值 $d=a-c$ 。

不论怎么说，假使我们已经得到了相关信息，约定相关变量如下
$$
\begin{align}
&A=g^a\ mod\ p\tag{1}\\
&B=g^b\ mod\ p\tag{2}\\
&C=g^c\ mod\ p\tag{3}\\
&s_{ab}=A^b=B^a=r_1+x_1\ mod\ p\tag{4}\\
&s_{bc}=C^b=B^c=r_2+x_2\ mod\ p\tag{5}\\
&d=c-a\tag{6}\\
&t=B^d\ mod\ p\tag{7}\\
\end{align}
$$
现在我们已知 $A、B、C、r_1、r_2、X、d$ ，其中 $X$ 是未知数 $x_i$ 的上界。接下来我们做一些变换
$$
\begin{align}
&s_{bc}=B^c=B^{a+d}=B^a*B^d=s_{ab}*t=r_2+x_2\ mod\ p\tag{8}\\
&s_{ab}=t^{-1}(r_2+x_2)\ mod\ p\tag{9}
\end{align}
$$

把(9)带入(4)
$$
\begin{align}
&t^{-1}(r_2+x_2)=r_1+x_1\ mod\ p\Leftrightarrow\\
&x_1-t^{−1}x_2+r1−t^{−1}r2 ≡ 0\ mod\ p\tag{10}
\end{align}
$$
那么我们可以构造格
$$
\left[\begin{matrix}
u&x_2&1
\end{matrix}\right]\times
\left[\begin{matrix}
p&0&0\\
t^{-1}&1&0\\
t^{-1}r_2-r_1&0&X
\end{matrix}\right]=
\begin{matrix}
[x_1&x_2&X]
\end{matrix}
$$
这就是一个标准的 $SVP$ 。同样的，我们分析算法成立的必要条件。
$$
\begin{align}
&||v_1||\le\sqrt3X\le\sqrt 2*(pX)^{\frac{1}{3}}\Leftrightarrow\\
&X\le\sqrt{\frac{2\sqrt2}{3\sqrt3}p}\approx\sqrt p
\end{align}
$$

1
2
3
4
5
6
7
8
9
10
11
12
#most significant bits leak
from Crypto.Util.number import *
def DH_most_significant_bits_of_s(d,p,g,B,r1,r2,bits):
    X=1<<bits
    t=int(inverse(ZZ(pow(B,d,p)),p))
    L=matrix(ZZ,[[p,0,0],[t,1,0],[(t*r2-r1),0,X]]).LLL()
    x1,x2=int(L[0][0]),int(L[0][1])
    Sab=(x1+r1)
    Sbc=(x2+r2)
    print(f"sab={Sab}\nsbc={Sbc}")
    return Sab,Sbc
DH_most_significant_bits_of_s(d,p,g,B,r1,r2,bits)

对于低位泄露，我们修改方程为
$$
\begin{cases}
s_{ab}=r_1+kx_1\ mod\ p\\
s_{ac}t=r_2+kx_2\ mod\ p\\
k=1<<bits，bits是s泄露的位数
\end{cases}\\
\begin{align}
\Leftrightarrow bitsx_1-t^{−1}bitsx_2+r1−t^{−1}r2 ≡ 0\ mod\ p\tag{11}
\end{align}
$$
对应格
$$
\left[\begin{matrix}
p&0&0\\
t^{-1}&1&0\\
k^{-1}(t^{-1}r_2-r_1)&0&X
\end{matrix}\right]
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#least significant bits leak
#please make sure that c>a
#bitLength(r1)==bitLength(r2)
from Crypto.Util.number import *
def DH_least_significant_bits_of_s(d,p,g,B,r1,r2,bits):
    X=1<<bits
    shift=min(r1.bit_length(),r2.bit_length())
    k=int(inverse(1<<shift,p))
    t=int(inverse(ZZ(pow(B,d,p)),p))
    L=matrix(ZZ,[[p,0,0],[t,1,0],[k*(t*r2-r1),0,X]]).LLL()
    x1,x2=int(L[0][0]),int(L[0][1])
    Sab=((x1<<shift)+r1)
    Sbc=((x2<<shift)+r2)
    print(f"sab={Sab}\nsbc={Sbc}")
    return Sab,Sbc
DH_least_significant_bits_of_s(d,p,g,B,r1,r2,bits)

当然情况还可以更复杂，比如泄露位数不同或者是中间泄露，但是原理是一样的。