前言

填一下以前的坑，补习了一下Wiener's attack和格密码攻击的内容，找到了其中一些共通之处，在这记个笔记（主要做题被暴打了- -

正文

About aX=b%p

设有：

aX≡b\ mod\ p

其中，p是素数~~（当然不是素数应该也可以？不过为了方便一些条件的讨论，比如求逆，还是假设素数）~~，X是大的数，a和b是小的数，这里说的大小关系是指（特殊情况下a或b还可以大一点？）：

X = \Theta(p)\\ a, b ≤ O(p^{1/2})

根据aX=b%p，可以写成aX+kp=b或aX-kp=b，易得k ≤ O(p^{1/2})（aX=b+kp的话，左右都是≤O(p^{3/2})的量级，p是Ⲑ(p)的，除一下就好了）。

现在假设X和p已知，需要求a和b，那么根据以往的经验，一条方程中有三个未知数是不可解的，但现在有了大小关系的条件，就有两种方法可以解：

Wiener's

现有：

aX-kp=b

左右同除ap：

\frac{X}{p}-\frac{k}{a}=\frac{b}{ap}

由于有a, b ≤ O(p^{1/2})，即有：

\frac{b}{ap} = \frac{1}{ap/b} ≤ \frac{1}{2*a^2}

于是就有了：

|\frac{X}{p}-\frac{k}{a}| ≤ \frac{1}{2*a^2}

就可以用连分数的方法（好像是Legendre’s theorem？），用X/p求出k和a，进而也解出b。（到这步看不懂的话可以翻下面看Wiener's扩展，逃

Lattices

现有：

aX+kp=b

如果增加一个恒等的式子：

a*1+k*0=a\\ aX+kp=b

就可以构造出：

(a, k)*\begin{bmatrix} 1 & X \\ 0 & p \\ \end{bmatrix} = (a, b)

令上面的东西记为：

A*M=B

还记得有a, b ≤ O(p^{1/2})，即可以算出：

||B|| = (a^2+b^2)^{1/2} ≤ O(p^{1/2}) = \sqrt{2}p^{1/2} = \sqrt{2}det(M)^{1/2} ≈ \sigma(M)

所以B有很大概率为M里的最短向量，使用LLL算法reduce后可求出最短向量，即解出B=(a, b) 。（到这步看不懂的话可以翻下面看Latticces扩展，逃

更紧的界

上面考虑的都是a=\Theta (b)的情况，如果 a=o(b) 或者 b=o(a) 呢。首先假设：

a = \Theta(p^\alpha) \\ b = \Theta(p^\beta)

根据上面构造出的A*M=B：

(a, k)*\begin{bmatrix} 1 & X \\ 0 & p \\ \end{bmatrix} = (a, b)

有：

B ≈ (p^\alpha, p^\beta)

推算一下的话可知道，B的长度其实是由“最大”的元素决定的，就是说假设 \alpha>\beta的话，有：

\|B\| ≈ \sqrt{2}\ p^\alpha

也就是如果对M的第二列同乘一个c，使得a=\Theta(cb)的话，B的长度不会变，但det(M)会变大，即\sigma会变大。根据这个思路，可构造对角矩阵D：

D = \begin{bmatrix} 1 & 0 \\ 0 & p^{\alpha-\beta} \\ \end{bmatrix}

然后计算得到：

\|BD\| ≈ \sqrt{2}\ p^\alpha \\ \sigma(MD) ≈ \sqrt{2}\ p^{1/2+\frac{\alpha-\beta}{2}}

要能用Lattices的方法算的话，即：

\alpha < \frac{1}{2}+\frac{\alpha-\beta}{2} \\ \alpha+\beta < 1

也就是 ab≤\Theta(p)即可，也就是a和b一个小一点的话，另一个就可以大一点。 \alpha<\beta的情况也一样。

例题

这里用[IMC]7.1节的NTRU toy scheme来作例子：

根据题目的信息可以推出：

fh≡g\ mod\ p\\ h = \Theta(q)\\ f, g ≤ O(q^{1/2})

Wiener's做法：

#!/usr/bin/env sage
from Crypto.Util import number

BITS = 128
q = number.getPrime(BITS)
#f = number.getRandomRange(2, floor((q//2)^(1/2)))
#g = number.getRandomRange(2, floor((q//2)^(1/2)))
f = Integer(randint(2, floor((q//2)^(1/2))))
g = Integer(randint(2, floor((q//2)^(1/2))))
h = (f.inverse_mod(q)*g) % q

print('q = %s' % q)
print('f = %s' % f)
print('g = %s' % g)
print('h = %s' % h)

# debug
k = (f*h-g)//q
assert (f*h)%q == f*h-k*q
print((h/q-k/f) < 1/(2*f^2))
# end debug

f2 = f
g2 = g
N = 20000
fra = (h/q).n(N).exact_rational().continued_fraction()
for i in range(len(fra)):
    k = fra.numerator(i)
    f = fra.denominator(i)
    
    if f<=floor((q//2)^(1/2)) and f*h-k*q==(f*h)%q:
        g = f*h-k*q
        if g <= floor((q//2)^(1/2)):
            print(f2==f and g2==g, f, g)

在实践时搞出来的f和g有时会是原f和g的某个倍数（或整除），虽然还是符合fh≡g\ mod\ p

Lattices做法：

#!/usr/bin/env sage
from Crypto.Util import number

BITS = 128
q = number.getPrime(BITS)
#f = number.getRandomRange(2, floor((q//2)^(1/2)))
#g = number.getRandomRange(2, floor((q//2)^(1/2)))
f = Integer(randint(2, floor((q//2)^(1/2))))
g = Integer(randint(2, floor((q//2)^(1/2))))
h = (f.inverse_mod(q)*g) % q

print('q = %s' % q)
print('f = %s' % f)
print('g = %s' % g)
print('h = %s' % h)

M = matrix([
    [1, h],
    [0, q]
    ])

# debug
k = -(f*h-g)//q
assert (f*h)%q == f*h+k*q
a = vector(ZZ, [f, k])
b = vector(ZZ, [f, g])
assert a*M == b
lenB = (b*b)^(1/2)
detM = M.det()
print(lenB.n(10) <= ((detM)^(1/2)).n(10))
# end debug

f2 = f
g2 = g
L = M.LLL()
b = vector(ZZ, L[0])
f = abs(b[0])
g = abs(b[1])
print(f2==f and g2==g, f, g)

同样还是会有倍数的问题，但其实两个方法的倍数都很小，还是可以爆破出来（如果有条件爆破的话-

What about a_iX_i=B\ \%\ p ？

~~(前两天被吊打的hws)~~
如果是B是未知大数的情况怎么样呢，即：

a_iX_i≡B\ mod\ p \\ X_i, B = \Theta(p)\\ a_i ≤ O(p^{1/2})

知道X和p，求a和B。如果有多组这样的式子的话是可以转化成aX=b%p的情况的。

先来看一下a_iB=X_i\ \%\ p的情况：

a_1B≡X_1\ mod\ p \\ a_2B≡X_2\ mod\ p

可以推出（不排版了，能看懂就好-）：

a' = (X_1B^{-1}≡a_1\ mod\ p)\ \ \ \ \ \ ≤ O(p^{1/2}) \\ b' = (X_2B^{-1}≡a_2\ mod\ p)\ \ \ \ \ \ ≤ O(p^{1/2})\\ X' = ({X_1}^{-1}X_2≡{a_1}^{-1}a_2 \ mod\ p)\ \ \ \ \ \ \ \ =\Theta(p)

即可消去未知大数B：

a'X' ≡ b' \ mod\ p

再来看回a_iX_i=B\ \%\ p，其实只要稍微转化成：

a_iB^{-1}=X_i^{-1}\ \%\ p

就是上面的情况。

What about a_iX_i=B_i\ \%\ p ？

按照上面的经验，要解这东西，就要消去B_i，但我目前没有找到消去的方法，所以暂时不会解（？？？

What about \sum_{i=1}^{n} a_iX_i ≡ b \ mod\ p

\sum_{i=1}^{n} a_iX_i ≡ b \ mod\ p \\ \sum_{i=1}^{n} a_iX_i +kp = b \\ \ \\ (a_1, a_2, ..., a_n, k) \begin{pmatrix} 1 & 0 & \cdots & 0 & X_1 \\ 0 & 1 & \cdots & 0 & X_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & X_n \\ 0 & 0 & \cdots & 0 & p \\ \end{pmatrix} = (a_1, a_2, ..., a_n, b)\\ \ \\ 记为 A*M=B

记a = max(a_i)，有：

\sigma(M) ≈ \sqrt{n+1}\ p^{1/(n+1)} \\ ||B|| ≈ \sqrt{n+1}\ a

所以只要有 a≤O(p^{1/(n+1)}) 就可解 a_i 。

PS：这个矩阵跟解背包密码（Knapsacks）的那个矩阵有点像，但又不完全像，因为两个问题其实就有点像，但又不完全像（逃

What about \sum_{i=1}^{n} a_iX_i ≡ Y \ mod\ p

如果现在等式右边是大数Y，而且Y已知的话，就是背包密码（Knapsacks）的解法了：

\sum_{i=1}^{n} a_iX_i ≡ Y \ mod\ p \\ \sum_{i=1}^{n} a_iX_i +kp - Y = 0 \\ \ \\ (a_1, a_2, ..., a_n, k， -1) \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 & X_1 \\ 0 & 1 & 0 & \cdots & 0 & 0 & X_2 \\ 0 & 0 & 1 & \cdots & 0 & 0 & X_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 & X_n \\ 0 & 0 & 0 & \cdots & 0 & 1 & p \\ 1 & 1 & 1 & \cdots & 1 & 1 & Y \\ \end{pmatrix} = (a_1-1, a_2-1, ..., a_n-1, k-1, 0)\\ \ \\ 记为 A*M=B

记a = max(a_i)，有：

\sigma(M) ≈ \sqrt{n+2}\ Y^{1/(n+2)} \\ ||B|| ≈ \sqrt{n+2}\ a

注意到这里其实B的最后一个元素是0，所以如果M的最后一列和B的最后一个元素同乘一个超大的C的话（即M和B同乘一个对角阵D，D的对角线上的最右下一个是C，其他是1），det(M)会变大，而B则不变，可以得到：

\sigma(MD) ≈ \sqrt{n+2}\ (CY)^{1/(n+2)} \\ ||BD|| ≈ \sqrt{n+2}\ a

所以如果C足够大的话，就会有\|BD\| ≤ \sigma(MD)，即可解 a_i

What about a_iX_i ≡ b_i \ mod\ (P+s)

现在假设原来的p可以拆成(P+s)，P已知，s未知但一定会存在：

X_i = \Theta(P) \\ a_i ≤ O(P^\alpha) \\ b_i ≤ O(P^\beta) \\ s ≤ O(P^\gamma)

有时(P+s)的值并不知道，但会知道P的值，比如RSA中，\phi(N)并不知道，但会知道 N=\phi(N)+(1-(p+q))，用类似扩展维纳攻击[HS99] 的方法可以用(P+s)代替P，然后用格的方法做，但需要的a和b要更小。~~（其实这部分就是在讲扩展维纳攻击）~~

假设现在是有两组的情况：

a_1X_1 ≡ b_1 \ mod\ (P+s) \\ a_2X_2 ≡ b_2 \ mod\ (P+s)

拆开：

a_1X_1+k_1P = b_1-k_1s \ \ \ \ \ \ \ \ ① \\ a_2X_2+k_2P = b_2-k_2s \ \ \ \ \ \ \ \ ②

可以看到①和②两个方程的未知数很不一样，即很难构造像之前的线性方程，但是看一下①*②的式子：

①*② = (a_1X_1+k_1P)(a_2X_2+k_2P) = X_1X_2a_1a_2+X_1Pa_1k_2+X_2Pa_2k_1+P^2k_1k_2

通过①*k_2和②*k_1的方式，构造出来的未知数不会比①*②中的多，于是就可以构造出下面四条方程（构造时尽量弄成上三角的矩阵）：

恒等式引入k_1k_2
k_1k_2 = k_1k_2
①*k_2
X_1a_1k_2+Pk_1k_2 = k_2(b_1-sk_1)
①*k_2-②*k_1
X_1a_1k_2-X_2a_2k_1 = b_1k_2-sk_1k_2-(b_2k_1-sk_1k_2) = b_1k_2-b_2k_1
①*②
X_1X_2a_1a_2+X_1Pa_1k_2+X_2Pa_2k_1+P^2k_1k_2 = (b_1-k_1s)(b_2-k_2s)

重点关注第3条，很巧妙地把右边的sk_1k_2消去了，使得\alpha或\beta可以更大一点，这也是扩展维纳攻击d的大小比普通维纳攻击d的大小大一点的原因（吗？

于是就有：

(k_1k_2, a_1k_2, a_2k_1, a_1a_2) \begin{pmatrix} 1 & P & 0 & P^2 \\ 0 & X_1 & X_1 & X_1P \\ 0 & 0 & -X_2 & X_2P \\ 0 & 0 & 0 & X_1X_2 \end{pmatrix} \\ =(k_1k_2, k_2(b_1-sk_1), b_1k_2-b_2k_1, (b_1-k_1s)(b_2-k_2s))

记作A*M=B，跟之前同样的方法构造D把B弄齐次（这里先假设 \alpha+\gamma \ge \beta）：

B ≈ (P^{2\alpha}, P^{2\alpha+\gamma}, P^{\alpha+\beta}, P^{2\alpha+2\gamma}) \\ D = \begin{pmatrix} P^{2\gamma} & 0 & 0 & 0 \\ 0 & P^{\gamma} & 0 & 0 \\ 0 & 0 & P^{\alpha-\beta+2\gamma} & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \\

可以计算：

\sigma(MD) ≈ 2P^{1+\frac{5\gamma+\alpha-\beta}{4}} \\ \|BD\| ≈ 2P^{2\alpha+2\gamma}

要最短向量为B即：

\|BD\| ≤ \sigma(MD) \\ 2\alpha+2\gamma ≤ 1+\frac{5\gamma+\alpha-\beta}{4} \\ 7\alpha+\beta+3\gamma ≤ 4

在扩展维纳攻击中是\beta=0，\gamma=1/2，所以算出\alpha≤5/14。

另外，在假设 \alpha+\gamma<\beta 的情况下，推出：\alpha+\beta ≤ 1，即和之前一样。

可以看出上面的情况\alpha和\beta的系数和都是右边的两倍，而且还引入了\gamma，所以在\alpha≈\beta的情况下，\alpha和\beta都需要更小（不会比已知(P+s)的解法更优）。

What about x_i=pq_i+r_i

其实这是ACD问题，参考[GGM16]，和21wmctf的easylsb。

现有（个人更喜欢加的，所以把论文的符号换了一下。。。）：

p = \Theta(2^\alpha)\\ q_i = \Theta(2^\beta)\\ r_i = \Theta(2^\rho)\\ \rho<\alpha\\ \rho<\beta\\ ↓\\ x_i = \Theta(2^{\alpha+\beta})

其中[GGM16]第三章中提到一个技巧，x是很大的，但是q_0x_i-q_ix_0可以减少规模：

q_0x_i-q_ix_0=q_0(pq_i+r_i)-q_i(pq_0+r_0)=q_0r_i-q_i-r_0\\ 2^{\alpha+2\beta} → 2^{\beta+\rho}

于是构造：

(q_0, q_1, ..., q_t) \begin{pmatrix} R & x_1 & x_2 & \cdots & x_t \\ 0 & -x_0 & 0 & \cdots & 0 \\ 0 & 0 & -x_0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -x_0 \\ \end{pmatrix} _{(t+1)*(t+1)} \\ =(q_0R, q_0x_1-q_1x_0, ..., q_0x_t-q_tx_0)\\ =(q_0R, q_0r_1-q_1r_0, ..., q_0r_t-q_tr_0)

记上式为vL=w，其中设R=2^\rho，这里的R的作用其实是上面“更紧的界”里说的要把w配齐次。可以算出：

\sigma(L) ≈ \sqrt{t+1}\ 2^{(t(\alpha+\beta)+\rho)/(t+1)} \\ \|w\| ≈ \sqrt{t+1}\ 2^{\beta+\rho}

要能用格解，则：

\beta+\rho \le (t(\alpha+\beta)+\rho)/(t+1)\\ \beta \le t(\alpha-rho)

在“easylsb”中是t=4, \beta=\alpha=512, \rho=368，512 \le 4(512-368) = 4*144=576

(PS：瞎写的，待验证)

Wiener's 扩展

现在说的Wiener's attack指Wiener在[Wiener90]提出的针对RSA的攻击，但其实更多时候说的是他用到的方法，即Legendre’s theorem（其实这里说的也是，也许只是Wiener当时的攻击比较出名？）：

就是说如果能找到\alpha符合上面的关系的话，那p/q就是\alpha那堆连分数里的其中一个，\alpha是知道的，所以\alpha的连分数可以求出来，p和q就是\alpha某一个连分数的分子和分母（当然也可能会是某个倍数）。

Wiener's attack说的是在RSA中，当d很小时（d<\frac{1}{3}N^(1/4)），可以通过连分数的方法解出d。先来看看RSA的密钥生成，ed ≡ 1 \ mod\ \phi(N)，e是大的，d是小的，1是小的，刚好符合上面说的方程大小关系，于是可以：

ed ≡ 1 \ mod\ \phi(N) \\ ed-k\phi(N) = 1 \\ |\frac{e}{\phi(N)}-\frac{k}{d}| = \frac{1}{d\phi(N)} < \frac{1}{2d^2}

好像可以解，但问题在于\phi(N)是不知道的，于是需要一些“近似替换”的方法。由于p, q ≈ O(N^{1/2})，所以：

\phi(N) = (p-1)(q-1) = N-p-q+1 ≈ N

于是就可以用N来近似\phi(N)，由于N是知道的就可以求k和d，但需要一个证明[Bon99 Th.2]：

然后就可以愉快地用e和N计算k和d了。

Wiener's attack是1990提出来的东西了，所以后来也有了很多改进的版本，用其他的东西近似替换\phi(N)，而不是用N，比如

上面那个是[OP12]里的一个定理：

2020的湖湘杯的crypto4就照搬了这个定理（网上找不到writeup，最近拿出来鞭尸x）（原题忘了，只剩个图）

wp：https://paste.ubuntu.com/p/DBmB5RntqB/

Lattices 扩展

格（Lattices）的话可以看成是一个向量空间里的一堆点，就是一组基通过“整数”的线性组合“张成”的空间（具体可以看[IMC]的7.4，那里会说得更详细）。

这里主要说一下用格解方程的方法和原理。主要用到一个叫Gaussian expected shortest length的东西：

就是说，在格L中的最短非零向量的长度大概有\sigma(L)那么长，如果可以构造出整数向量A、B和格L（其中A、B未知，L已知），使得：

A*L = B \\ ||B|| ≤ \sigma(L)

的话，B就大概率是L的最短向量（第一个式子说明向量B在格L中，第二个式子说明B大概率是L的最短向量），通过找L的最短向量可解出B，通过B*L^{-1}可解A。在L的维度不大的情况下，用LLL算法可以找到L的最短向量（Sage中可以直接调用，详细原理可以看[IMC]的7.13），LLL算法主要用于把“垂直程度低”的格“reduce”成“垂直程度高”的格，而且reduce后的第一个基即是L的最短向量（见下图性质）。另外格很“垂直”的话，就可以用Babai的算法解CVP问题（略）。

总结来说，只要构造出L和A*L = B并且符合||B|| ≤ \sigma(L)的关系的话就可以解出A和B，然后利用A和B中的元素解决其他的问题。在用格攻击密码算法时基本都是这个套路，~~（所以略了）~~

另外有个叫扩展维纳的攻击也用到这个套路，这里引一下[Gm1y]大佬的博客，里面基本说的很清楚了，里面一个“通过对矩阵的列乘上一个倍数”的方法也非常有用（但里面没详说hhh）：

由于有下面的关系：

就有：

B ≈ (N^{2\alpha}, N^{2\alpha+1/2}, N^{\alpha}, N^{2\alpha+1})

B的长度其实由最大的元素决定的，即现在是：

||B|| ≈ \sqrt{2}*N^{2\alpha+1}

如果A*L=B左右同乘对角阵D，使得B的元素“齐次”（即每个元素指数规模一样，为2\alpha+1），那么B的长度几乎不变，但L的行列式会变大，即\sigma(L)变大，通过计算（就是2\alpha+1减去原指数的值）可得对角阵每个元素为：

D → (N^1, N^{1/2}, N^{\alpha+1}, 1)

即[Gm1y]博客里的值。

总结

一个方程里如果知道所有的“大数”（包括未知的“大数”可以消去的情况），可以用Wiener's（Legendre’s theorem）或格（Lattices）的方法解出未知的“小数”。这里的具体大小关系可能需要计算一下，一般会是小数≤O((最大数)^{1/小未知数的数量}) （当然，只是一般，-

我个人比较偏向用格的方法（很明显上面写的几乎都是用格的-），感觉格的话会更通用（特别高维的情况），但也不排除自己对Legendre’s theorem那堆东西不是很熟了（逃

另外，遇到不等式的关系时可以多考虑Wiener's的方法；遇到等式时可以考虑Lattices的方法。

引用

[IMC] Hoffstein J, Pipher J, Silverman J H, et al. An introduction to mathematical cryptography[M]. New York: Springer, 2008.
[Wiener90] M. J. Wiener, Cryptanalysis of short RSA secret exponents", IEEE Transactions on Information Theory, vol. IT(36), pp. 553-558, 1990.
[Bon99] Boneh D. Twenty years of attacks on the RSA cryptosystem[J]. Notices of the AMS, 1999, 46(2): 203-213.
[OP12] Ojha N, Padhye S. Weak Keys in RSA over The Work of Blomer & May[J]. Int. J. Netw. Secur., 2012, 14(2): 80-85.
[HS99] Howgrave-Graham N, Seifert J P. Extending Wiener’s attack in the presence of many decrypting exponents[C]//International Exhibition and Congress on Network Security. Springer, Berlin, Heidelberg, 1999: 153-166.
[GGM16] Galbraith S D, Gebregiyorgis S W, Murphy S. Algorithms for the approximate common divisor problem[J]. LMS Journal of Computation and Mathematics, 2016, 19(A): 58-72.
[Gm1y] 密码学硬核笔记——扩展维纳攻击

PS：其实后来我在博客上改/加了挺多东西的，后来想merge到论坛的时候嫌太太太太太多公式要改了就算了（懒），所以可以直接访问https://tover.xyz/p/wieners-lattices-equations/；不过原则性的错误这里都有修改（逃