前言

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

PS:如无特殊说明文中假设x,X,y,Y,s...x,X,y,Y,s...的是未知量,a,A,b,B,P,...a, A, b, B, P, ...的是已知量;其中小写字母表示“小”的数,大写字母表示“大”的数(2021.10.16更新)

正文

About aX=b%p

设有:

Axy mod PAx≡y\ mod\ P

其中,PP是素数~~(当然不是素数应该也可以?不过为了方便一些条件的讨论,比如求逆,还是假设素数)~~,AA是大的数,xxyy是小的数,这里说的大小关系是指(特殊情况下xxyy还可以大一点,后面再说):

A=Θ(P)x,yO(P1/2)A = \Theta(P)\\ x, y ≤ O(P^{1/2})

根据Axy(modP)Ax \equiv y \pmod P,可以写成Ax+kP=yAx+kP=yAxkP=yAx-kP=y,易得kO(P1/2)k ≤ O(P^{1/2})Ax=y+kPAx=y+kP的话,左右都是O(P3/2)≤O(P^{3/2})的量级,PPΘ(P)\Theta(P)的,除一下就好了)

现在假设AAPP已知,需要求xxyy,那么根据以往的经验,一条方程中有三个未知数是不可解的,但现在有了大小关系的条件,就有两种方法可以解:

Wiener’s

现有:

AxkP=yAx-kP=y

左右同除xPxP

APkx=yxP\frac{A}{P}-\frac{k}{x}=\frac{y}{xP}

由于有x,yO(p1/2)x, y ≤ O(p^{1/2}),即有:

yxP=1xP/y12x2\frac{y}{xP} = \frac{1}{xP/y} ≤ \frac{1}{2*x^2}

于是就有了:

APkx12x2|\frac{A}{P}-\frac{k}{x}| ≤ \frac{1}{2*x^2}

就可以用连分数的方法(好像是Legendre’s theorem?),用A/PA/P逼近求出kkxx(实际是k/gcd(k,x)k/gcd(k,x)x/gcd(k,x)x/gcd(k,x)),进而也解出yy。(到这步看不懂的话可以翻下面看Wiener’s扩展,逃

Lattices

现有:

Ax+kP=yAx+kP=y

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

x1+k0=xxA+kP=yx*1+k*0=x\\ xA+kP=y

就可以构造出:

(x,k)[1A0P]=(x,y)(x, k)*\begin{bmatrix} 1 & A \\ 0 & P \\ \end{bmatrix} = (x, y)

令上面的东西记为:

vM=wv*M=w

还记得有x,yO(P1/2)x, y ≤ O(P^{1/2}),即可以算出:

w=(x2+y2)1/2O(P1/2)=2P1/2=2det(M)1/2σ(M)\|w\| = (x^2+y^2)^{1/2} ≤ O(P^{1/2}) = \sqrt{2}P^{1/2} = \sqrt{2}det(M)^{1/2} ≈ \sigma(M)

所以ww有很大概率为MM里的最短向量,使用LLL算法reduce后可求出最短向量,即解出w=(x,y)w'=(x, y) 。(到这步看不懂的话可以翻下面看Latticces扩展,逃

更紧的界

上面考虑的都是x=Θ(y)x=\Theta (y)的情况,如果 x=o(y)x=o(y) 或者 y=o(x)y=o(x) 呢。首先假设:

x=Θ(Pα)y=Θ(Pβ)x = \Theta(P^\alpha) \\ y = \Theta(P^\beta)

根据上面构造出的vM=wv*M=w

(x,k)[1A0P]=(x,y)(x, k)*\begin{bmatrix} 1 & A \\ 0 & P \\ \end{bmatrix} = (x, y)

有:

w(Pα,Pβ)w ≈ (P^\alpha, P^\beta)

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

w2 Pα\|w\| ≈ \sqrt{2}\ P^\alpha

也就是如果对wwMM的第二列同乘一个cc,使得a=Θ(cb)a=\Theta(cb)的话,ww的长度不会有太大变化,但det(M)det(M)会明显变大,即σ\sigma会变大,推一下可知大概是cPαβc \approx P^{\alpha-\beta}。根据这个思路,可构造对角矩阵DD

D=[100Pαβ]D = \begin{bmatrix} 1 & 0 \\ 0 & P^{\alpha-\beta} \\ \end{bmatrix}

然后计算得到:

wD2 Pασ(MD)2 P1/2+αβ2\|wD\| ≈ \sqrt{2}\ P^\alpha \\ \sigma(MD) ≈ \sqrt{2}\ P^{1/2+\frac{\alpha-\beta}{2}}

要能用Lattices的方法算的话,即:

α<12+αβ2α+β<1\alpha < \frac{1}{2}+\frac{\alpha-\beta}{2} \\ \alpha+\beta < 1

也就是 xyΘ(P)xy≤\Theta(P)即可,也就是xxyy一个小一点的话,另一个就可以大一点。$ \alpha<\beta$的情况也一样。

例题

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

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

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

Wiener’s做法:

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
#!/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的某个倍数(或整除),虽然还是符合fhg mod pfh≡g\ mod\ p

Lattices做法:

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
#!/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 AixiY(modP)A_ix_i \equiv Y \pmod P

(前两天被吊打的hws)
如果是YY是未知大数的情况怎么样呢,即:

AixiY(modP)Ai,Y=Θ(P)xiO(Pαi)A_ix_i \equiv Y \pmod P \\ A_i, Y = \Theta(P)\\ x_i ≤ O(P^{\alpha_i})

知道AiA_iPP,求xix_iYiY_i。如果有多组这样的式子的话是可以转化成Axy(modP)Ax \equiv y \pmod P的情况的。

先来看一下xiY=Ai(modP)x_iY=A_i \pmod P的情况:

x1YA1(modP)x2YA2(modP)x_1Y \equiv A_1 \pmod P \\ x_2Y \equiv A_2 \pmod P

可以推出(不排版了,能看懂就好-):

x=(A1Y1x1(modP))      O(Pα1)y=(A2Y1x2(modP))      O(Pα2)A=(A11A2x11x2(modP))      =Θ(P)x' = (A_1Y^{-1} \equiv x_1 \pmod P)\ \ \ \ \ \ ≤ O(P^{\alpha_1}) \\ y' = (A_2Y^{-1} \equiv x_2 \pmod P)\ \ \ \ \ \ ≤ O(P^{\alpha_2}) \\ A' = ({A_1}^{-1}A_2 \equiv {x_1}^{-1}x_2 \pmod P)\ \ \ \ \ \ =\Theta(P)

即可消去未知大数YY

Axy(modP)A'x' \equiv y' \pmod P

再来看回AixiY(modP)A_ix_i \equiv Y \pmod P,其实只要稍微转化成:

xiY1Ai1(modP)x_iY^{-1} \equiv A_i^{-1} \pmod P

就是上面的情况。

What about AixiYi(modP)A_ix_i \equiv Y_i \pmod P

按照上面的经验,要解这东西,就要消去YiY_i,但我目前没有找到消去的方法,所以暂时不会解(???

What about i=1nAixiy(modP)\sum_{i=1}^{n} A_ix_i \equiv y \pmod P

i=1nAixiy(modP)i=1nAixi+kP=y (x1,x2,...,xn,k)(100A1010A2001An000P)=(x1,x2,...,xn,y) \sum_{i=1}^{n} A_ix_i \equiv y \pmod P \\ \sum_{i=1}^{n} A_ix_i + kP = y \\ \ \\ (x_1, x_2, ..., x_n, k) \begin{pmatrix} 1 & 0 & \cdots & 0 & A_1 \\ 0 & 1 & \cdots & 0 & A_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & A_n \\ 0 & 0 & \cdots & 0 & P \\ \end{pmatrix} \\ = (x_1, x_2, ..., x_n, y)\\ \ \\

记上式为vM=wvM=w;记xmax=max(xi)x_{max} = max(x_i),有:

σ(M)n+1 P1/(n+1)wn+1 xmax\sigma(M) ≈ \sqrt{n+1}\ P^{1/(n+1)} \\ \|w\| ≈ \sqrt{n+1}\ x_{max}

所以只要有 xmaxO(P1/(n+1))x_{max}≤O(P^{1/(n+1)}) 就可解 xix_i ;这里同样可以用乘上一个对角阵DD的方法尽量把σ(M)\sigma(M)放大,跟“更紧的界”里说的一样所以略了(后面大部分方法都是适用的)。

PS:这个矩阵跟解背包密码(Knapsacks)的那个矩阵有点像,但又不完全像,因为两个问题其实就有点像,但又不完全像(逃

What about i=1nAixiB(modP)\sum_{i=1}^{n} A_ix_i \equiv B \pmod P

如果现在等式右边是大数BB,而且BB已知的话,就是背包密码(Knapsacks)的解法了:

i=1nAixiB(modP)i=1nAixi+kPB=0 (x1,x2,...,xn,k1)(10000A101000A200100A300010An00001P11111B)=(x11,x21,...,xn1,k1,0) \sum_{i=1}^{n} A_ix_i \equiv B \pmod P \\ \sum_{i=1}^{n} A_ix_i + kP - B = 0 \\ \ \\ (x_1, x_2, ..., x_n, k, -1) \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 & A_1 \\ 0 & 1 & 0 & \cdots & 0 & 0 & A_2 \\ 0 & 0 & 1 & \cdots & 0 & 0 & A_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 & A_n \\ 0 & 0 & 0 & \cdots & 0 & 1 & P \\ 1 & 1 & 1 & \cdots & 1 & 1 & B \\ \end{pmatrix} \\ = (x_1-1, x_2-1, ..., x_n-1, k-1, 0)\\ \ \\

记上式为vM=wvM=w;记xmax=max(xi)x_{max} = max(x_i),有:

σ(M)n+2 P1/(n+2)wn+2 xmax\sigma(M) ≈ \sqrt{n+2}\ P^{1/(n+2)} \\ \|w\| ≈ \sqrt{n+2}\ x_{max}

注意到这里其实ww的最后一个元素是00,所以如果MM的最后一列和ww的最后一个元素同乘一个超大的CC的话(即MMww同乘一个对角阵DDDD的对角线上的最右下一个是CC,其他是11),det(M)det(M)会变大,而ww则不变,可以得到:

σ(MD)n+2 (CP)1/(n+2)wDn+2 xmax\sigma(MD) ≈ \sqrt{n+2}\ (CP)^{1/(n+2)} \\ \|wD\| ≈ \sqrt{n+2}\ x_{max}

所以如果CC足够大的话,就会有wDσ(MD)\|wD\| ≤ \sigma(MD),即可解 xix_i(理论上

What about Aixiyi(mod(P+s))A_ix_i \equiv y_i \pmod {(P+s)}

现在假设模数未知,但可以拆成(P+s)(P+s)PP已知,ss未知但很“小”:

Ai=Θ(P)xiO(Pα)yiO(Pβ)sO(Pγ)A_i = \Theta(P) \\ x_i ≤ O(P^\alpha) \\ y_i ≤ O(P^\beta) \\ s ≤ O(P^\gamma)

比如RSA中,ϕ(N)\phi(N)并不知道,但会知道 N=ϕ(N)+(1(p+q))N=\phi(N)+(1-(p+q)),用类似 扩展维纳攻击[HS99] 的方法可以用(P+s)(P+s)代替原来的模数,然后用格的方法做,但需要的xxyy要更小。(其实这部分就是在讲扩展维纳攻击)

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

A1x1y1(mod(P+s))A2x2y2(mod(P+s))A_1x_1 \equiv y_1 \pmod {(P+s)} \\ A_2x_2 \equiv y_2 \pmod {(P+s)}

拆开:

A1x1+k1P=y1k1s        ①A2x2+k2P=y2k2s        ②A_1x_1+k_1P = y_1-k_1s \ \ \ \ \ \ \ \ ① \\ A_2x_2+k_2P = y_2-k_2s \ \ \ \ \ \ \ \ ②

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

(A1x1+k1P)(A2x2+k2P)=A1A2x1x2+A1Px1k2+A2Px2k1+P2k1k2(A_1x_1+k_1P)(A_2x_2+k_2P) = A_1A_2x_1x_2+A_1Px_1k_2+A_2Px_2k_1+P^2k_1k_2

通过k2①*k_2k1②*k_1的方式,构造出来的未知数不会比①*②中的多,于是就可以构造出下面四条方程(构造时尽量弄成上三角的矩阵):

  1. 恒等式引入k1k2k_1k_2

k1k2=k1k2k_1k_2 = k_1k_2

  1. k2①*k_2

A1x1k2+k1Pk2=(y1k1s)k2A_1x_1k_2+k_1Pk_2 = (y_1-k_1s)k_2

  1. k2k1①*k_2-②*k_1

A1x1k2A2x2k1=(y1k2k1sk2)(y2k1k2sk1)=y1k2y2k1A_1x_1k_2-A_2x_2k_1 = (y_1k_2-k_1sk_2)-(y_2k_1-k_2sk_1) = y_1k_2-y_2k_1

  1. ①*②

A1A2x1x2+A1Px1k2+A2Px2k1+P2k1k2=(y1k1s)(y2k2s)A_1A_2x_1x_2+A_1Px_1k_2+A_2Px_2k_1+P^2k_1k_2 = (y_1-k_1s)(y_2-k_2s)

重点关注第3条,很巧妙地把右边的sk1k2sk_1k_2消去了,使得α\alphaβ\beta可以更大一点,这也是扩展维纳攻击dd的大小比普通维纳攻击d的大小大一点的原因(吗?

于是就有:

(k1k2,x1k2,x2k1,x1x2)(1P0P20A1A1A1P00A2A2P000A1A2)=(k1k2,(y1k1s)k2,y1k2y2k1,(y1k1s)(y2k2s))(k_1k_2, x_1k_2, x_2k_1, x_1x_2) \begin{pmatrix} 1 & P & 0 & P^2 \\ 0 & A_1 & A_1 & A_1P \\ 0 & 0 & -A_2 & A_2P \\ 0 & 0 & 0 & A_1A_2 \end{pmatrix} \\ =(k_1k_2, (y_1-k_1s)k_2, y_1k_2-y_2k_1, (y_1-k_1s)(y_2-k_2s))

记作vM=wvM=w,跟之前同样的方法构造DDww弄齐次(这里先假设 α+γβ\alpha+\gamma \ge \beta,即ww最大元素约为P2α+2γP^{2\alpha+2\gamma}):

w(P2α,P2α+γ,Pα+β,P2α+2γ)D=(P2γ0000Pγ0000Pαβ+2γ00001)w ≈ (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} \\

可以计算:

σ(MD)2P1+5γ+αβ4wD2P2α+2γ\sigma(MD) ≈ 2P^{1+\frac{5\gamma+\alpha-\beta}{4}} \\ \|wD\| ≈ 2P^{2\alpha+2\gamma}

要最短向量为ww即:

wDσ(MD)2α+2γ1+5γ+αβ47α+β+3γ4\|wD\| ≤ \sigma(MD) \\ 2\alpha+2\gamma ≤ 1+\frac{5\gamma+\alpha-\beta}{4} \\ 7\alpha+\beta+3\gamma ≤ 4

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

另外,在假设 α+γ<β\alpha+\gamma<\beta 的情况下,推出:α+β1\alpha+\beta ≤ 1,即和之前一样 。

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

What about aiXyi(mod(Pi+si))a_iX \equiv y_i \pmod {(P_i+s_i)}

RSA多组密钥用同一个dd的情况,只不过那是eid1(modni)e_id \equiv 1 \pmod {n_i};现知道aiPia_i、P_i,其他未知,有:

X,Pi=Θ(P)aiO(Pα)yiO(Pβ)siO(Pγ)α,β,γ<1aiXyi(mod(Pi+si))aiX+kiPi=yikisikiaiO(Pα)X,P_i = \Theta(P) \\ a_i \le O(P^\alpha) \\ y_i \le O(P^\beta) \\ s_i \le O(P^\gamma) \\ \alpha, \beta, \gamma < 1 \\ a_iX \equiv y_i \pmod {(P_i+s_i)} \\ a_iX +k_iP_i = y_i - k_is_i \\ k_i \approx a_i \le O(P^\alpha)

即可构造:

(X,k1,k2,...,kn)(1a1a2an1an0P100000P200000Pn100000Pn)=(X,y1k1s1,y2k2s2,...,ynknsn)(X, k_1, k_2, ..., k_n) \begin{pmatrix} 1 & a_1 & a_2 & \cdots & a_{n-1} & a_n \\ 0 & P_1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & P_2 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & P_{n-1} & 0 \\ 0 & 0 & 0 & \cdots & 0 & P_n \\ \end{pmatrix} \\ = (X, y_1-k_1s_1, y_2-k_2s_2, ..., y_n-k_ns_n)

记上式为vM=wvM=w;先假设βα+γ1\beta \le \alpha+\gamma \le1,得:

w(P,Pα+γ,Pα+γ,...,Pα+γ)D=(1000P1(α+γ)000P1(α+γ))w \approx (P, P^{\alpha+\gamma}, P^{\alpha+\gamma}, ..., P^{\alpha+\gamma}) \\ D = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & P^{1-(\alpha+\gamma)} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & P^{1-(\alpha+\gamma)} \end{pmatrix} \\

计算出:

σ(MD)n+1Pnn+1+n(1(α+γ))n+1wDn+1P\sigma(MD) ≈ \sqrt{n+1} P^{\frac{n}{n+1}+\frac{n(1-(\alpha+\gamma))}{n+1}} \\ \|wD\| ≈ \sqrt{n+1} P

要最短向量为ww即要符合:

1nn+1+n(1(α+γ))n+1=nn+1(2(α+γ))1 \le \frac{n}{n+1}+\frac{n(1-(\alpha+\gamma))}{n+1} = \frac{n}{n+1}(2-(\alpha+\gamma))

即:

1/n1(α+γ)1/n \le 1-(\alpha+\gamma)

  • α+γβ1\alpha+\gamma \le \beta \le1,同样的方法可算出需符合:

1/n1β1/n \le 1-\beta

  • β1α+γ\beta \le 1 \le \alpha+\gamma,需符合:

    α+γ11/n\alpha+\gamma \le 1-1/n

    因为有1α+γ1 \le \alpha+\gamma,即无解。

What about Ai=xyi+ziA_i=xy_i+z_i

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

现有(把论文的符号换了一下。。。):

x=Θ(2α)yi=Θ(2β)zi=Θ(2ρ)ρ<αρ<βAi=Θ(2α+β)x = \Theta(2^\alpha)\\ y_i = \Theta(2^\beta)\\ z_i = \Theta(2^\rho)\\ \rho<\alpha\\ \rho<\beta\\ ↓\\ A_i = \Theta(2^{\alpha+\beta})

其中[GGM16]第三章中提到一个技巧,AA是很大的,但是Aiy0A0yiA_iy_0-A_0y_i可以减少规模:

Aiy0A0yi=(xyi+zi)y0(xy0+z0)yi=y0ziyiz02α+2β2β+ρA_iy_0-A_0y_i = (xy_i+z_i)y_0-(xy_0+z_0)y_i = y_0z_i-y_iz_0\\ 2^{\alpha+2\beta} → 2^{\beta+\rho}

于是构造:

(y0,y1,...,yn)(RA1A2An0A00000A00000A0)(n+1)(n+1)=(y0R,A1y0A0y1,...,Any0A0yn)=(y0R,y0z1y1z0,...,y0znynz0)(y_0, y_1, ..., y_n) \begin{pmatrix} R & A_1 & A_2 & \cdots & A_n \\ 0 & -A_0 & 0 & \cdots & 0 \\ 0 & 0 & -A_0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -A_0 \\ \end{pmatrix} _{(n+1)*(n+1)} \\ =(y_0R, A_1y_0-A_0y_1, ..., A_ny_0-A_0y_n)\\ =(y_0R, y_0z_1-y_1z_0, ..., y_0z_n-y_nz_0)

记上式为vM=wvM=w,其中设R=2ρR=2^\rho,这里的RR的作用其实是上面“更紧的界”里说的要把ww配齐次。可以算出:

σ(M)n+1 2(n(α+β)+ρ)/(n+1)wn+1 2β+ρ \sigma(M) ≈ \sqrt{n+1}\ 2^{(n(\alpha+\beta)+\rho)/(n+1)} \\ \|w\| ≈ \sqrt{n+1}\ 2^{\beta+\rho}

要能用格解,则:

β+ρ(n(α+β)+ρ)/(n+1)βn(αrho)\beta+\rho \le (n(\alpha+\beta)+\rho)/(n+1)\\ \beta \le n(\alpha-rho)

在“easylsb”中是n=4,β=α=512,ρ=368n=4, \beta=\alpha=512, \rho=3685124(512368)=4144=576512 \le 4(512-368) = 4*144=576

(PS:瞎写的,待验证)

Wiener’s 扩展

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

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

Wiener’s attack说的是在RSA中,当dd很小时(d<13N1/4d<\frac{1}{3}N^{1/4}),可以通过连分数的方法解出dd。先来看看RSA的密钥生成,ed1 mod ϕ(N)ed ≡ 1 \ mod\ \phi(N)ee是大的,dd是小的,11是小的,刚好符合上面说的方程大小关系,于是可以:

ed1 mod ϕ(N)edkϕ(N)=1eϕ(N)kd=1dϕ(N)<12d2ed ≡ 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}

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

ϕ(N)=(p1)(q1)=Npq+1N\phi(N) = (p-1)(q-1) = N-p-q+1 ≈ N

于是就可以用N来近似ϕ(N)\phi(N),由于NN是知道的就可以求kkdd,但需要一个证明[Bon99 Th.2]:

然后就可以愉快地用eeNN计算kkdd了。

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

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

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

wp:

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
# sage
from gmpy2 import iroot
import libnum

n = 45644374572906696918751526371540317432552767574531146725947197073091284249824311652929876880761183040024642912502639494246699284890420348711755152172125722304276541146638287085067604879135037538874624825231963426170448359129554061563687341132377272549120305441316002675552272436786866637426883885955669
e = 41481590714555165448395765336905824124002290841668481529563451625379681482568747653473952507567741287320305714776744069287119560788311144707988486438017581271859974139810844158857833808782692691546769253874942787868189158458052798618813933937987400708792117152522747046613196233766095230599127585735387
c = 25790054143492912038696919999059363251926853333642241274795090550534183356849875749287324824373062006504574906179764092648413976672912657535347328280694667704633525599132436478280986985933339098397197660180557793681265237430974006426519650760258181942099887311223904706872308373765682748061276137390494
i = 11
j = 2

X = 1000
rho = 11/2
sn = (sqrt(n)).n(X)
sr = (sqrt(rho)).n(X)
sij = (sqrt(i*j)).n(X)

left = e/(n-((i+j)/sqrt(i*j))*sqrt(n)+1)
fra = (left.n(X).exact_rational()).continued_fraction()
print(len(fra))

for i in range(1, len(fra)):
k = fra.numerator(i)
d = fra.denominator(i)
if (e*d-1)%k==0:
print(k, d)
x = var('x')
sol = solve([x^2-(n+1-(e*d-1)/k)*x+n==0], x)
p = sol[0].right()
q = sol[1].right()
if p.is_integer() and q.is_integer():
print('d = %s' % d)
print('p = %s' % p)
print('q = %s' % q)
print(libnum.n2s(int(pow(c, d, n))))
break
#print(i)

# DASCTF{d10a6523ab3c9b26238b523f1a9e3c73}

Lattices 扩展

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

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

就是说,在格LL中的最短非零向量的长度大概有σ(L)\sigma(L)那么长,如果可以构造出整数向量vvww和格LL(其中vvww未知,LL已知),使得:

vL=wBσ(L)vL = w \\ ||B|| ≤ \sigma(L)

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

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

总结

一个方程里如果知道所有的“大数”(包括未知的“大数”可以消去的情况),可以用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] 密码学硬核笔记——扩展维纳攻击

[silent] 基于格的通用私钥攻击(RSA用了同一个d)

( 原文地址:https://0xffff.one/d/1062-wiener-s-v-s-lattices-ax-b-p-de-fang-cheng-xie-fa-bi-ji