解方程、解方程和解方程,反正我当时是没找到论文然后就一直在推解密方法,感觉有非预期- -

题目链接:https://paste.ubuntu.com/p/RGgs3dCFmC/

前言

首先go里的密钥生成是典型的Wiener攻击的密钥生成方法,所以当时很自然地就往Wiener方面想了,然后就可以分解hintnn,但是分解不了flag的,就又很自然地往Coppersmith想(而且hint也提示了Coppersmith),最后跑了很久都没跑出来(感觉参数被卡了)。

后来赛后看其他队大佬的wp才知道qqp+21024βp+2^{1024\beta}接近,可以解方程加枚举直接分解- -(虽然我也看漏了next_prime里面的1 << int(nbits * beta)是个定值)。反正如果next_prime的偏移是知道的话,肯定是不需要Coppersmith的,甚至beta还可以更大(所以感觉是非预期了)。

然后,比赛时没有找到相关论文(这关键词搜啥啊,),就硬推解密函数(+解方程),感觉这个解方程的方法还是挺有用的,所以就水篇博客。赛后跟@晓鹿交流才发现有这个论文,加密方法都一样的,对着抄就好了- -

最后,这篇博客大概以记录为主吧,记一下分解n时分别想到的几个(格)方法和推解密函数的过程。

分解模数

Wiener变种

首先看q = next_prime(p + (1 << int(nbits * beta)))这句,就可以得出qp<Nβ+ϵq-p < N^{\beta+\epsilon}ϵ\epsilon表示一个可忽略的数。另,事实上这是不够紧致的,一会再说),作平方:

(qp)2=p2+q22pq=p2+q22N<N2β+2ϵ(q-p)^2=p^2+q^2-2pq=p^2+q^2-2N < N^{2\beta+2\epsilon}

由于φ=(p21)(q21)=p2q2+1(p2+q2)\varphi=(p^2-1)(q^2-1)=p^2q^2+1-(p^2+q^2),令s=p2+q22Ns=p^2+q^2-2NN=N22N+1N'=N^2-2N+1,则有s<N2β+2ϵs < N^{2\beta+2\epsilon},且:

Ns=N22N+1(p2+q22N)=N2+1(p2+q2)=φN'-s = N^2 - 2N + 1 - (p^2 + q^2 - 2N) = N^2 + 1 - (p^2 + q^2) = \varphi

根据edkφ=1ed-k\varphi=1,有:

edk(Ns)=1edkN=1ksed - k(N'-s) = 1 \\ ed - kN' = 1-ks

然后到这里就是之前讲Wiener与格的套路,可以选择用eN\frac{e}{N'}逼近得到kd\frac{k}{d},或者构造格(个人偏好):

(k,d)[N2βN0e]=(kN2β,1ks)(k, d)*\begin{bmatrix} N^{2\beta} & -N' \\ 0 & e \\ \end{bmatrix} \\ = (kN^{2\beta}, 1-ks)

大概估算一下,kNδk \approx N^\deltasN2βs \approx N^{2\beta}eN2e \approx N^2,则:

σ([N2βN0e])N2+2β2=N1+β(kN2β,1ks)Nδ+2β\sigma(\begin{bmatrix} N^{2\beta} & -N' \\ 0 & e \\ \end{bmatrix}) \approx N^{\frac{2+2\beta}{2}} = N^{1+\beta} \\ \|(kN^{2\beta}, 1-ks)\| \approx N^{\delta+2\beta}

计算得,若:

δ+2β<1+ββ+δ<1\delta+2\beta < 1+\beta \\ \beta + \delta < 1

则则(kN2β,1ks)(kN^{2\beta}, 1-ks)大概率是L([N2βN0e])L(\begin{bmatrix} N^{2\beta} & -N' \\ 0 & e \\ \end{bmatrix})的最短向量,LLL解之,然后可解(k,d)(k, d)

β=0.33\beta=0.33δ=0.63\delta=0.63时是符合条件的,β=0.44\beta=0.44δ=0.63\delta=0.63不符合,所以只能解hint那部分。

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
# sage 
# for hint

n = 122774778628333786198247673730199699244621671207929503475974934116435291656353398717362903500544713183492877018211738292001516168567879903073296829793548881467270228989482723510323780292947403861546283099122868428902480999485625751961457245487615479377459707992802193391975415447673215862245349068018710525679
e = 7105408692393780974425936359246908629062633111464343215149184058052422839553782885999575538955213539904607968494147112651103116202742324255190616790664935322773999797774246994193641076154786429287567308416036562198486649223818741008968261111017589015617705905631979526370180766874051731174064076871339400470062519500450745667838729104568633808272577378699913068193645578675484681151593983853443489561431176000585296710615726640355782811266099023653898050647891425956485791437516020367967793814415345332943552405865306305448753989707540163585481006631816856260061985275944250758886027672221219132999488907097750048011
c = 2593129589804979134490367446026701647048897831627696427897506570257238733858989741279626614121210703780002736667183915826429635213867589464112850355422817678245007337553349507744893376944140333333044928907283949731124795240808354521353751152149301719465724014407412256933045835977081658410026081895650068864922666975525001601181989114436054060461228877148361720945120260382962899756912493868467226822547185396096960560068874538680230073168773182775945272726468512949751672553541335307512429217493003429882831235199830121519272447634533018024087697385363918421438799206577619692685090186486444886371979602617584956259

size=1024
beta = 0.33
n2 = (n-1)^2
R = int(n^(2*beta))
m = matrix(ZZ, [
[R, -n2],
[0, e]
])

L = m.LLL()
w = L[0]

v = m.solve_left(w)
print('v = %s' % v)

k, d = v
print(len(bin(d)))
print((e*d-1) % k)
phi = (e*d-1)//k

pq_p = Integer(sqrt(n^2+2*n+1-phi))
pq_m = Integer(sqrt(n^2-2*n+1-phi))
p = (pq_p+pq_m)//2
q = pq_p-p
if p*q == n:
print('p = %d' % p)
print('q = %d' % q)

d = e.inverse_mod(phi)
print('d = %d' % d)

'''
p = 11080378090495548888711346538044743233499815208179802720810821877018321760024765272011515142380916992839687768295921206534475286830411300347575580967025893
q = 11080378090495548888711346538044743233499815208179802440842729104792795440344480200955980377175229838508495905797283586060491389310293127737888922016136003
d = 121139118831078102076565175484037979390315779651424626323741939233877664377574934056315052293655422386668889543147047138108873461630703630129146688760636392702002802083436463455161665094535393763
'''

Boneh-Durfee变种

利用上面推出的关系edkN=1ksed - kN' = 1-ks,转化一下可得:

k(Ns)+10(mode)k(N'-s)+1 \equiv 0 \pmod e

然后就推出了跟Boneh-Durfee差不多的关系,Coppersmith解之。

不过,令x=kx=ky=sy=s的话,即取X=21024δX=2^{1024\delta}Y=22048βY=2^{2048\beta},根据之前讲Coppersmith时推出的关系,需要符合(下图的xxyy换成大写- -):

大概推算了一下,发现mm要设置为1515以上(PS:m=16m=16时取t=4t=4有最优),推算过程就不详说了,下面截图留了个过程。反正mm这么大的话是要跑很久的(渣机表示一下午没出来,把方法在这里留一下,放个20年看看以后的电脑能不能算出来吧,x)

忽略的条件

赛后再看了一下才发现,我把1 << int(nbits * beta)是已知的这个条件忽略了(即,当成随机数了- -),如果加上这个条件的话根本就不需要用到Coppersmith。

首先令a=21024βa=2^{1024\beta}(即上面的移位的值),由于q = next_prime(p + a),令s=q(p+a)s=q-(p+a)ss相对于NN来说其实是一个非常小的值(两个素数的差值其实是很小的,这个不用怀疑- ),整理一下则qp=a+sq-p=a+s,同样做个平方:

(qp)2=p2+q22N=(a+s)2=a2+2as+s2(q-p)^2 = p^2+q^2-2N = (a+s)^2 = a^2 + 2as + s^2

t=p2+q22Na2=2as+s2t = p^2+q^2-2N - a^2 = 2as + s^2,则t<Nβ+ϵt<N^{\beta+\epsilon}(这里的ϵ\epsilon是为了考虑上ss,实际应该是可忽略的,吧,反正不能忽略也可以枚举)。

然后也一样,由于φ=(p21)(q21)=p2q2+1(p2+q2)\varphi=(p^2-1)(q^2-1)=p^2q^2+1-(p^2+q^2),令u=p2+q22Na2u=p^2+q^2-2N-a^2N=N22N+1a2N'=N^2-2N+1-a^2,则有u<Nβ+ϵu < N^{\beta+\epsilon},且:

Ns=N22N+1a2(p2+q22Na2)=φN'-s = N^2 - 2N + 1 - a^2 - (p^2 + q^2 - 2N - a^2) = \varphi

根据edkφ=1ed-k\varphi=1,有:

edk(Ns)=1edkN=1ksed - k(N'-s) = 1 \\ ed - kN' = 1-ks

然后也是可以选择连分数/格,个人偏好用格解:

(k,d)[NβN0e]=(kNβ,1ku)(k, d)*\begin{bmatrix} N^{\beta} & -N' \\ 0 & e \\ \end{bmatrix} \\ = (kN^{\beta}, 1-ku)

大概估算一下,kNδk \approx N^\deltauNβu \approx N^{\beta}eN2e \approx N^2,则:

σ([NβN0e])N2+β2(kNβ,1ks)Nδ+β\sigma(\begin{bmatrix} N^{\beta} & -N' \\ 0 & e \\ \end{bmatrix}) \approx N^{\frac{2+\beta}{2}} \\ \|(kN^{\beta}, 1-ks)\| \approx N^{\delta+\beta}

计算得,若:

δ+β<2+β22δ+β<2\delta+\beta < \frac{2+\beta}{2} \\ 2 \delta + \beta < 2

(kNβ,1ks)(kN^{\beta}, 1-ks)大概率是L([NβN0e])L(\begin{bmatrix} N^{\beta} & -N' \\ 0 & e \\ \end{bmatrix})的最短向量,LLL解之,然后可解(k,d)(k, d)。(其实基本上跟前面的是一样的- -)

如果固定δ=0.63\delta=0.63的话,可得β<220.63=0.74\beta < 2-2*0.63 = 0.74,即hint部分的0.330.33flag部分的0.440.44都在范围,甚至还能更大。

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
# sage
# for flag

n = 59969098213446598961510550233718258878862148298191323654672950330070587404726715299685997489142290693126366408044603303463518341243526241117556011994804902686998166238333549719269703453450958140262475942580009981324936992976252832887660977703209225426388975233018602730303262439218292062822981478737257836581
e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672

size=1024
beta = 0.44
a = 1 << int(size * beta)
n2 = (n-1)^2 - a^2
R = int(n^(beta))
m = matrix(ZZ, [
[R, -n2],
[0, e]
])

L = m.LLL()
w = L[0]

v = m.solve_left(w)
print('v = %s' % v)

k, d = v
print(len(bin(d)))
print((e*d-1) % k)
phi = (e*d-1)//k

pq_p = Integer(sqrt(n^2+2*n+1-phi))
pq_m = Integer(sqrt(n^2-2*n+1-phi))
p = (pq_p+pq_m)//2
q = pq_p-p
if p*q == n:
print('p = %d' % p)
print('q = %d' % q)

d = e.inverse_mod(phi)
print('d = %d' % d)

'''
p = 7743971733771153105036156209981171560215008954284943420880584133648389139833517283670475349302080701240378945438911146974137885250527042074631329729385091
q = 7743971733771153102128801312798743998017713722732925283466018690899116898707556486947918196848489007935614742583856884731087798825462330340492923214926391
d = 91530255743213804238059422201508844509005370104602135173607248138301475575179518423751713150218534315997028245173456360624292973766196816229696622248975836077175204186997500189564114519436678423
'''

Coppersmith的界

没推过,咕

推解密函数

首先讲一下思路,由加密函数里的c(1+mn)v(modn2)c \equiv (1+mn)v \pmod {n^2},可以盲猜m<nm < n,不然mnmnn2n^2会有数据损失,整理一下提取出mnmn

mn=cv11(modn2)mn = cv^{-1}-1 \pmod {n^2}

注意上面是==而不是\equiv,因为m<nm < nmn<n2mn < n^2,模运算可忽略,上面式子右边未知的只有v(modn2)v \pmod {n^2}。首先vmodnv \mod n其实是已知的,因为cc模个nn就可得到vc(modn)v \equiv c \pmod n。假设有v(modn)v \pmod n可以解出r(modn)r \pmod n的话,由于r<nr < n,即(modn)\pmod n可忽略,解出的是真实的rr,然后把rr代进seq(r, e)就可以解vv了。所以现在问题可以分解为

  1. ppqqv(modn)v \pmod n,求rr
  2. rreev(modn2)v \pmod {n^2}
  3. mn=cv11(modn2)mn = cv^{-1}-1 \pmod {n^2}mnmn
  4. m=mnnm=\frac{mn}{n}求flag。

其中最难的是第一步。

1. 求r

刚开始的时候给题目的phi = (p**2 - 1) * (q**2 - 1)误导了(大概),因为,在seq中,如果令A=[r110]A=\begin{bmatrix} r & -1 \\ 1 & 0 \\ \end{bmatrix}v0=(r,2)Tv_0=(r, 2)^T的话,seq(r, k)就是在做vk=Akv0v_k=A^kv_0的操作,然后返回vkv_k的第一个元素。由之前讲一般线性群时的推导加上一点验算可得phi就是AA的群阶,所以就很自然地往一般线性群上面想,但这个结构好像解不出来(菜)。

既然往矩阵上想不行的话就要换一个思路了,首先seqseq的操作跟Fibonacci数列非常像(矩阵也很像),那么seq应该是可以推出通项公式的,推公式可以用解特征方程的方法(具体自行Google),偷懒的就直接在这里查到了:

代进这题的seq就是(附Wolfram代码):

1
2
3
4
5
Solve[x^2 - r*x + 1 == 0, x]
x1 = (r + Sqrt[r^2 - 4])/2;
x2 = (r - Sqrt[r^2 - 4])/2;
g[i_] := Simplify[x1^i + x2^i];
g[e]

(上图左边要加个v=v=)。令a=r+r24a=r+\sqrt{r^2-4}b=rr24b=r-\sqrt{r^2-4},则上式简化为:

2ev=ae+be2^{e}v = a^e+b^e

且有规律

ab=r2(r2+4)=4r=a+b2ab = r^2-(r^2+4) = 4 \\ r = \frac{a+b}{2}

利用第一个规律,把2ev=ae+be2^{e}v = a^e+b^e再整理一下:

2ev=ae+(4a1)e=ae+4eae2^{e}v = a^e+(4a^{-1})^e = a^e + 4^ea^{-e}

x=aex=a^e,上式左右乘个xx即:

2evx=x2+4e2^evx = x^2 + 4^e

是个二次方程,由于现在已知的是v(modn)v \pmod n,如果把上面方程放在(modn)\pmod n下,则可解出ae(modn)a^e \pmod{n},然后就转化为普通的RSA问题,现在知道ppqq了自然可以解密出a(modn)a \pmod n,同理可解出b(modn)b \pmod n,代入上面规律r=21(a+b)(modn)r=2^{-1}(a+b) \pmod {n}所以合理地转化为解模nn的二次方程

x22evx+4e0(modn)x^2 -2^evx + 4^e \equiv 0 \pmod n

然后就是很麻烦的扩域问题了(PS:这里的解并不小(甚至不是整数- -),所以不能Coppersmith解)。扩域可以类比一下初中学的整数域扩复数域,x2=1x^2=1,在整数域Z\mathbb{Z}上明显是没解的,所以就要扩到复数域C\mathbb{C}上解出x1=ix_1=ix2=ix_2=-i

扩域解方程

看回这个题目,首先名字都叫扩域了那就得先转成一个域,由于nn的分解已经知道了,即ppqq已经知道了,即可以先解出rp in Fpr_p\ in\ \mathbb{F}_prq in Fqr_q\ in\ \mathbb{F}_q然后上CRT解出r(modn)r \pmod{n}。先拿pp作栗子,令f(x)=x22evx+4ef(x) = x^2 -2^evx + 4^e,那现在就是解:

f(x)0 in Fpf(x) \equiv 0 \ in\ \mathbb{F}_p

然后扩域的方法之前在讲Jordan Form的时候大概提到过,先算出f(x)f(x)的度为22(最高项次数),于是就把域扩到:

Fp2=F[x]/f(x)\mathbb{F}_{p^2} = \mathbb{F}[x] / f(x)

至于为什么是Fp2\mathbb{F}_{p^2},因为f(x)f(x)最高项是2次,所以应该会有2个解,而现在就恰好有两个解:

x=xp0,xp1 in Fp2x = x^{p^0}, x^{p^1} \ in\ \mathbb{F}_{p^2}

这里补一下之前留的坑,说一下为什么这两个东西是解(大概,我也不确定)。首先xp0=xx^{p^0}=x肯定是f(x)0 in Fpf(x) \equiv 0 \ in\ \mathbb{F}_p的解,而在Fp\mathbb{F}_p上会有xp1xpxx^{p^1} \equiv x^p \equiv x(后面的等号大概是费马小定理),那么xp1x^{p^1}也是f(x)0 in Fpf(x) \equiv 0 \ in\ \mathbb{F}_p的解。注意在Fp\mathbb{F}_pxp0x^{p^0}xp1x^{p^1}是一样的,但是在Fp2\mathbb{F}_{p^2}上是不一样的(即刚才说的两个解)。

这里先令x0=xp0x_0 = x^{p^0}x1=xp1x_1 = x^{p^1}in Fp2in\ \mathbb{F}_{p^2})。由于rpr_p是个整数(或者说在Fp\mathbb{F}_p上),所以最后肯定是要转回Fp\mathbb{F}_p上的关系的,但x0x_0x1x_1不能直接转回Fp\mathbb{F}_p(上面说过不然就变相等了),所以还需要一点转化在Fp2\mathbb{F}_{p^2}上。

首先解出来的xx应该会是之前设的x=aex=a^e,那么应该会有ax0da \equiv x_0^dax1da \equiv x_1^d(注意这里的ddde1(mod(p1)(q1))d \equiv e^{-1} \pmod {(p-1)(q-1)},另外实验测试用x0x_0和用x1x_1解出来的是一样的),即现在可以知道a in Fp2a \ in\ \mathbb{F}_{p^2}

翻一下上面说的两个规律,现在有(注意在Fp2\mathbb{F}_{p^2}上也是成立的):

b=4a1r=a+b2b = 4a^{-1} \\ r = \frac{a+b}{2}

于是就可以解出r in Fp2r \ in\ \mathbb{F}_{p^2}。由于rr是个整数(即在Fp\mathbb{F}_p上),所以解出来的也是rp in Fpr_p \ in\ \mathbb{F}_p

同理可以解出rq in Fqr_q\ in\ \mathbb{F}_q。最后crt([int(rp), int(rq)], [p, q])就可恢复rr

比论文的好像复杂一点- -,但这个解方程的方法是通用的(扩域\to转成整数\to“缩域”\to得解),以后应该也能用到。

234. 求m

这个有了rr根据刚开始的思路就很容易解了(略,有问题的话可以评论-),最后附代码:

hint

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
80
# sage

n = 122774778628333786198247673730199699244621671207929503475974934116435291656353398717362903500544713183492877018211738292001516168567879903073296829793548881467270228989482723510323780292947403861546283099122868428902480999485625751961457245487615479377459707992802193391975415447673215862245349068018710525679
e = 7105408692393780974425936359246908629062633111464343215149184058052422839553782885999575538955213539904607968494147112651103116202742324255190616790664935322773999797774246994193641076154786429287567308416036562198486649223818741008968261111017589015617705905631979526370180766874051731174064076871339400470062519500450745667838729104568633808272577378699913068193645578675484681151593983853443489561431176000585296710615726640355782811266099023653898050647891425956485791437516020367967793814415345332943552405865306305448753989707540163585481006631816856260061985275944250758886027672221219132999488907097750048011
c = 2593129589804979134490367446026701647048897831627696427897506570257238733858989741279626614121210703780002736667183915826429635213867589464112850355422817678245007337553349507744893376944140333333044928907283949731124795240808354521353751152149301719465724014407412256933045835977081658410026081895650068864922666975525001601181989114436054060461228877148361720945120260382962899756912493868467226822547185396096960560068874538680230073168773182775945272726468512949751672553541335307512429217493003429882831235199830121519272447634533018024087697385363918421438799206577619692685090186486444886371979602617584956259

p = 11080378090495548888711346538044743233499815208179802720810821877018321760024765272011515142380916992839687768295921206534475286830411300347575580967025893
q = 11080378090495548888711346538044743233499815208179802440842729104792795440344480200955980377175229838508495905797283586060491389310293127737888922016136003
phi = (p-1)*(q-1)
d1 = e.inverse_mod(phi)
v = c%n

# get rp
Fp.<ap> = GF(p)
Rp.<xp> = PolynomialRing(Fp)
fp = xp^2 - pow(2, e, n)*v*xp + pow(4, e, n)
Sp = Rp.quotient(fp, 'yp')
deg = fp.degree() # 2

lambdap = []
lam = Sp(xp)
for di in range(deg+1):
if di != 0:
lam = power(lam, p)
lambdap.append(lam)

# get rq
Fq.<aq> = GF(q)
Rq.<xq> = PolynomialRing(Fq)
fq = xq^2 - pow(2, e, n)*v*xq + pow(4, e, n)
Sq = Rq.quotient(fq, 'yq')
deg = fq.degree() # 2

lambdaq = []
lam = Sq(xq)
for di in range(deg+1):
if di != 0:
lam = power(lam, q)
lambdaq.append(lam)

x1 = lambdaq[0]^d1
x2 = lambdaq[1]^d1
rq1 = 4*x1^(-1) + x1
rq2 = 4*x2^(-1) + x2
assert rq1 == rq2
rq = rq1 / 2
print('rq = %d' % rq)


x1 = lambdap[0]^d1
x2 = lambdap[1]^d1
rp1 = 4*x1^(-1) + x1
rp2 = 4*x2^(-1) + x2
assert rp1 == rp2
rp = rp1 / 2
print('rp = %d' % rp)

r = crt([int(rp), int(rq)], [p, q])
print('r = %d' % r)
# r = 94481828629554556545829029253743639447330281687996501375557067273722993889483560013238090578754733435061039628971763184648836020175350429440493279023808177274857411552495011041326858998774439225875373629039942586972277592866979375576806144415372496959932885289333063119248077134254345866166462313245694271456

A = matrix(Zmod(n^2), [
[r, -1],
[1, 0]
])
v0 = vector(Zmod(n^2), [r, 2])
ve = pow(A, e)*v0
print(ve[1] % n == v)
v2 = int(ve[1])
print('v2 = %s' % v2)

import libnum
mn = (c*libnum.invmod(v2, n^2) - 1) % n^2
#mn = (c*v2.inverse_mod(n^2) - 1) % n^2
print(mn % n == 0)
m = mn//n

hint = libnum.n2s(int(m))
print(hint)
# b'The original challenge picks beta = 0.33, which yields straightforward unintended solution. BTW do you know coppersmith?'

flag

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
# sage
n = 59969098213446598961510550233718258878862148298191323654672950330070587404726715299685997489142290693126366408044603303463518341243526241117556011994804902686998166238333549719269703453450958140262475942580009981324936992976252832887660977703209225426388975233018602730303262439218292062822981478737257836581
e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672

p = 7743971733771153105036156209981171560215008954284943420880584133648389139833517283670475349302080701240378945438911146974137885250527042074631329729385091
q = 7743971733771153102128801312798743998017713722732925283466018690899116898707556486947918196848489007935614742583856884731087798825462330340492923214926391
phi = (p-1)*(q-1)
d1 = e.inverse_mod(phi)
v = c%n

# get rp
Fp.<ap> = GF(p)
Rp.<xp> = PolynomialRing(Fp)
fp = xp^2 - pow(2, e, n)*v*xp + pow(4, e, n)
Sp = Rp.quotient(fp, 'yp')
deg = fp.degree() # 2

lambdap = []
lam = Sp(xp)
for di in range(deg+1):
if di != 0:
lam = power(lam, p)
lambdap.append(lam)

x1 = lambdap[0]^d1
x2 = lambdap[1]^d1
rp1 = 4*x1^(-1) + x1
rp2 = 4*x2^(-1) + x2
assert rp1 == rp2
rp = rp1 / 2
print('rp = %d' % rp)

# get rq
Fq.<aq> = GF(q)
Rq.<xq> = PolynomialRing(Fq)
fq = xq^2 - pow(2, e, n)*v*xq + pow(4, e, n)
Sq = Rq.quotient(fq, 'yq')
deg = fq.degree() # 2

lambdaq = []
lam = Sq(xq)
for di in range(deg+1):
if di != 0:
lam = power(lam, q)
lambdaq.append(lam)

x1 = lambdaq[0]^d1
x2 = lambdaq[1]^d1
rq1 = 4*x1^(-1) + x1
rq2 = 4*x2^(-1) + x2
assert rq1 == rq2
rq = rq1 / 2
print('rq = %d' % rq)


r = crt([int(rp), int(rq)], [p, q])
print('r = %d' % r)

A = matrix(Zmod(n^2), [
[r, -1],
[1, 0]
])
v0 = vector(Zmod(n^2), [r, 2])
ve = pow(A, e)*v0
print(ve[1] % n == v)
v2 = int(ve[1])
print('v2 = %s' % v2)

import libnum
mn = (c*libnum.invmod(v2, n^2) - 1) % n^2
#mn = (c*v2.inverse_mod(n^2) - 1) % n^2
print(mn % n == 0)
m = mn//n

flag = libnum.n2s(int(m))
print(flag)
# b'HFCTF{5eb34942-bd0d-4efd-b0e1-a73225d92678}'

总结

想复杂了-

PS:hint的coppersmith都不需要用到,合理推测非预期