啊比赛的时候刚好和npy出去玩了, 也没怎么看题, 就看了半个下午的Common prime rsa. 也没整出来.
最近又在忙学校的HW就是什么成果都没, 只能看着大佬干自己划水的那种. 所以题目复现什么的就慢了好多.
慢慢的更新完吧, 每次做题都一堆paper, 想慢慢的看完只能花多点时间了吧

Strange_GCD

problem

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
from gmpy2 import *
from random import *
from Crypto.Util.number import *
from os import urandom
from flag import flag

P_bits = 444
Q_bits = 666
R_bits = 333
key_num = 9
e = 0x1337

while True:
could_not_solve = False
p = getPrime(P_bits)
if gcd(p-1, e) != 1:
continue
R = []
Q = []
N = []
for i in range(key_num):
Q.append(getPrime(Q_bits))
R.append(getrandbits(R_bits))
N.append(p * Q[-1] + R[-1])
if gcd(Q[-1], e) != 1:
could_not_solve = True
break
if not could_not_solve:
break


C = []
assert len(flag) == 45
for i in range(key_num):
tmp_cipher = flag[i*len(flag)//key_num:(i+1)*len(flag)//key_num].encode()
tmp_cipher = urandom(128 - len(tmp_cipher)) + tmp_cipher
tmp_cipher = pow(bytes_to_long(tmp_cipher), e, p * Q[i])
C.append(tmp_cipher)

print('N =', N)
print('C =', C)

'''
N = [...]
C = [...]
'''

analyses

这题比完赛以后做的, paper也是直接就看别人找了自己找太浪费时间啦

做的时候没看paper, 造格子没去思考怎么消去比较大的项, 看了paper才明白,

AGCD

先来看看这边的公钥生成, 这共生成了9个$N_i = p \cdot q_i + r_i,i=0,1,…,8$
其中$p,q,r$的位数分别为$444,666,333$, 这个问题看着像LWE但是我们只知道$N_i$. 尝试了一下造格子也没啥结果, 找paper找到了这个-> The Approximate GCD Problem 这里面提供了一个造格子的方法来分解$N_i$

其实这里面就有一种造格子的思想吧? 我们想要通过格基规约得出结果, 那么我们必须保证我们需要求出的量不会很大(只有这样才能使得我们要求的向量是最短向量), 所以我们的一个思路, 可以是消去一些比较大的数, 留下一些比较小的.

在这里我们先拿两行等式来分析
$$
N_0 = p \cdot q_0 + r_0 \\
N_1 = p \cdot q_1 + r_1
$$
我们可以看到式子里有个非常大的$p,q$, 可以想个办法消去这个大的项并且不引入比他更大的项. 一个办法就是通过减法!
$$
N_1q_0 - N_0q_1 = r_1q_0 - r_0q_1 \tag 1
$$
通过减法可以将$1110 $ bits的$pq$变成了小一点的$999$ bits 的$r_1q_0 - r_0q_1$, 这里小了点就可以尝试做文章了. 我们可以根据$(1)$这个式子写出剩下的一样的式子
$$
\begin{cases}
N_1q_0 - N_0q_1 = r_1q_0 - r_0q_1 \\
N_2q_0 - N_0q_2 = r_2q_0 - r_0q_2 \\
\vdots \\
N_8q_0 - N_0q_8 = r_8q_0 - r_0q_8
\end{cases}
$$
根据这个式子, 可以造出格子
$$
(q_0,q_1,…,q_8)
\begin{pmatrix}
2^\lambda&N_1&N_2&\cdots&N_8 \\
0&-N_0&0&\cdots&0 \\
0&0&-N_0&\cdots&0 \\
0&0&0&\ddots&0 \\
0&0&0&\cdots&-N_0
\end{pmatrix}
=
(2^\lambda q_0,r_1q_0-r_0q_1,…,r_8q_0-r_0q_8)
$$

$\lambda$ 的取值

这里有个参数$\lambda$需要确定下来, 这个参数跟最短向量的上界有关, 一直以来这个参数都是用来调目标向量长度和格的行列式用的, 也没有具体的分析过, 每次做的时候都直接爆破, 这次慢慢分析了一下.

先来看我们要求的向量, 暂时记为$v$
$$
\begin{align}
||v|| & = \sqrt{(2^\lambda q_0)^2 + (r_1q_0-r_0q_1)^2 + \cdots +(r_8q_0-r_0q_8)^2} \\
& \approx \sqrt{2^{2\lambda+1332}+2^{1998}+\cdots+2^{1998}} \\
& = \sqrt{2^{2\lambda+1332}+2^{2001}} \\
& \approx
\begin{cases}
2^{1001} , \lambda \le 335 \\
2^{\lambda + 666} , \lambda >335
\end{cases}
\end{align}
$$
再来看看$det(L)$

$$
det(L) = 2^\lambda \cdot N_0^8 \approx 2^{\lambda+8880}
$$
格子是9维的, 那么我们可以有一个粗略的不等式 $||v|| \le det(L)^{1/9}$
通过简单的计算就可以得到
$$
129 < \lambda < 360 \tag 2
$$
得到参数的大概取值范围, 选一个中间的就行了, 想刺激一点可以试试130 359之类的(反正我试了都是可以的).

(2) 式只是粗略得到的, 因为上界还有更严格的条件而且LLL算法实际上要比理论上要好….

我们构造出格子并规约后就能得到$q_0$了, 剩下的就是仿造这个格子构造求$q_1,\cdots,q_8$的格子, 求出所有的$q$以后, 因为$q>r$ , 所以$N = r \mod q$, 直接就可以求出$r$了, 继续求出$p$,然后就是正常的RSA解密了.

exp

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
from Crypto.Util.number import long_to_bytes
N = [...]
C = [...]
Q = []
R = []
D = []
t = 0
for _ in range(9):
M = 2^130
L = [[0 for _ in range(9)] for _ in range(9)]
L[0] = [M]+N[0:t] + N[t+1:]
for i in range(9):
L[i][i] = - N[t]
L[0][0] = M
MQ = abs(matrix(L).LLL()[0][0])
assert MQ % M == 0
Q.append(MQ // M)
t+=1

for n,q in zip(N,Q):
R.append(n % q)

p = (N[0] - R[0]) // Q[0]

for i in range(9):
phi = (p-1) * (Q[i]-1)
D.append(inverse_mod(0x1337,phi))
for c,d,q in zip(C,D,Q):
print(long_to_bytes(pow(c,d,p*q))[-5:].decode(),end='')

Common_Prime_RSA

problem

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
from Crypto.Util.number import *
from secret import flag

def get_my_prime(nibt, gamma):
g = getPrime(int(nibt * gamma))
while True:
p = 2 * g * getPrime(int(nibt * (0.5 - gamma))) + 1
if isPrime(p):
break

while True:
q = 2 * g * getPrime(int(nibt * (0.5 - gamma))) + 1
if isPrime(q):
break

assert 2 * p > q and 2 * q > p
return p, q, g

p1, q1, g1 = get_my_prime(1024, 0.2247)
p2, q2, g2 = get_my_prime(1024, 0.3247)
n1 = p1 * q1
n2 = p2 * q2

print(hex(n1))
# 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49

print(hex(pow(bytes_to_long(b'Common prime RSA is a variant of RSA' + long_to_bytes(g1) + b'And the common factor g is large prime and p=2ga+1 q=2gb+1'), 3, n1)))
# 0x27d8d7249643668ffc115be8b61775c60596e51f6313b47ad5af8493526922f5e10026a2cdaef74e22c3eec959dd8771abe3495b18d19f97623f5a3f65f22ff8fc294fc37ceb3b43ebbbf8a9bcf622922e22c5520dbd523483b9dc54fdffcd1a1b3f02ca1f53b75413fb79399ca00034f2acf108ac9a01bd24d2b9df6e27d156

print(hex(pow(g2, 65537, n1)))
# 0xeaf06b9050a809659f962251b14d6b93009a7010f0e8d8f0fa4d71591757e98243b8ff50ec98a4e140fd8a63bbb4b8bb0a6d302a48845b8b09d1e40874fcb586ddccbb0bbf86d21540ec6c15c1d2bf925942f6f384fdc1baae7f8e06150ccd9459eb65d0f07eea16a911fa0a17e876a145dbfec83537ca2bee4641897b9f7f5

print(hex(n2))
# 0x6d457110d6044472d786936acbd3cd93c7728daa3343b35ccaa5c55eba6b35c28c831bb245b8cdd8fc8cb67a72f57e62a0e1259f5e804c487a8478f6895b302d39277bd73947598a5f8ec0a535be9e9a4d34df91df948ee44cc3d13d14e23b9651089e4767c7f0e7245df55619c92fe24483225d35f5f3ee6f74375065766ffd

print(hex(pow(bytes_to_long(flag.encode()), 65537, n2)))
# 0x15be2b0eaef8837a753587c47d3f31696a7d239d88837a9b7d903cd0d0648ef8e225ea555402693a23f305d19e7e13905be61b44c651dba5b26614bcf876234e765a724e0ed8af4a4e408e6a233c48ab9cc63e9c552ef9cd1999512aa0aca830fe6cbcbcc3c6bb354903124a2c3a12d442cdbdefdae6576f4bbc1515051b7111

analyses

这道题做的时候自己踩了坑, 也没做出来, 后面看wp找到了那个paper才大概明白, 关于界的确定还得谢谢d33师傅.

coppersmith

这题的第一个problem就是求解$g_1$, 第一个明文可以分成三部分
$$
Plaintext_1 = high | g_1 | low \tag 1
$$
$high$和$low$我们都是知道的, 而$g1$和$low$的位数分别为$230,463$

所以理论上$(1)$式可以写成
$$
Plaintext_1 = 2^{693} \cdot high + 2^{463}\cdot g_1 + low
$$
这里就有个坑了, 字符串在拼接的时候肯定都是完整的字节在拼的, 所以每一段的位数都应该是8的倍数才对, 所以正确的$(1)$式应该为:
$$
Plaintext_1 = 2^{696} \cdot high + 2^{464} \cdot g_1 + low
$$
$g_1$的位数为$230$, 是满足coppersmith的条件的.

我们记$mbar = 2^{696}\cdot high + low$, 那么就有$c_1 = (mbar+2^{464}\cdot g_1)^3 \mod n_1$, 化成首一多项式后coppersmith method即可求出$g_1$

further attacks on server-aided rsa

我们从上部分得到了$g_1$ , 我们可以看看$p,q$和$g$的关系, 为了方便讨论, 直接记$g = 2g_1$
$$
p = xg+1 \\
q = yg+1
$$
那么我们有
$$
{N - 1 \over g} = xyg + (x+y) \tag 2
$$
这里设$xy = u - c, x+y =v+cg$, 那么$(2)$式可以化成
$$
{N - 1 \over g} = ug+v
$$
这里的$v < g$ , 也就是把$v$看成是${N-1\over g }\mod g$的结果. 那么$u,v$都是可以计算出来的, 重点在于新引入的$c$, 求出$c$就可以求$p,q$了

paper里提供了一种利用bsgs北上广深思想的方法来求出这个c, 但这题跟paper在c的界上有区别.

原paper是这样的, 我们随便找一个素数$a$ , 观察下面的式子
$$
a^{ug} \equiv a^{xyg+cg} \equiv a^{cg} \mod N
$$
为什么$a^{xyg}$没有了呢? 因为$k \cdot lcm(p-1,q-1) = xyg$ .

然后求一下$c$的上界, 后面要用到
$$
\begin{align}
&\because x+y =v+ cg \\
&\therefore x+y > cg \\
&\because x,y \approx {\sqrt{N} \over g} \\
&\therefore cg < {2 \sqrt{N} \over g} \\
&\therefore 0<c < {2 \sqrt{N} \over g^2}
\end{align}
$$
记$b = a^g \mod N$, 我们有$b^u \equiv b^c \mod N$ , paper里提到了这个$u,c$是很大概率相等的, 有师傅知道为什么吗?
所以我们可以用bsgs的思想, 计算两组数.
$$
\begin{align}
& b^0,b^D,b^{2D},\cdots,b^{D^2} \mod N \\
& b^u,b^{u-1},b^{u-2},\cdots,b^{u-D} \mod N
\end{align}
$$
其中$D = \lfloor \sqrt{ {2 \sqrt N \over g^2}-0}\rceil$

在这两组数中搜索碰撞, 也就是$b^{u-i} \equiv b^{kD} \mod N$ . 找到碰撞以后就可以计算$c = kD + i$了, 有了$c$就可以分解$N$了

当我看完paper以后兴奋的写了$exp$, 却发现这个北上广深把我内存全部吃完都没有结果(早上起来发现电脑屏幕都打不开了….
怎么会没结果啊…只能去看d33师傅的wp了! 因为他什么都会, 看完才明白原来paper里的界太松散了, 导致$D$太大, 跑出来需要多几根内存才行, 可是我只有一根8G的内存.

d33师傅的界:

因为$p,q$的位数相同, 所以我们还有一个隐藏的关系式
$$
p>2q \implies x < 2y \tag3 \implies {x\over 2}< y
$$
这个式子很重要, 我们继续观察一下$x+y$和$c$的关系$x+y -v = cg$, 我们可以根据基本不等式写出上界, 再根据$(3)$式写出下界
$$
{ 3\sqrt N \over 2g } - v\approx {3\over 2}x-v\leq cg \leq 2 \sqrt{xy} - v \approx {2\sqrt N \over g} -v
$$
根据这个, 咱们就有一个更加严格的$c$的界
$$
c \in [ { 3\sqrt N - 2gv\over 2g^2 },{2\sqrt N - gv \over g^2} ]
$$
同样的, 计算$D = \lfloor {2\sqrt N - gv \over g^2}- { 3\sqrt N - 2gv\over 2g^2 } \rceil $, 再用bsgs就可以求出$c$了, 但我8G的小内存依旧跑不出来, 只能借用一下d33师傅的数据了

分解了$n_1$就能求出$g_2$, 由于$g_2$的位数比较大, $g_2 > x+y$, 直接就有:
$$
{n_2 - 1 \over 2g_2} = x+y \mod 2g_2
$$
$xy$也可以直接求出来了, 然后依旧是分解$n_2$, 就可以求出flag了

exp

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
from Crypto.Util.number import long_to_bytes as l2b,bytes_to_long as b2l
from time import time
from gmpy2 import iroot
n1 = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49
n2 = 0x6d457110d6044472d786936acbd3cd93c7728daa3343b35ccaa5c55eba6b35c28c831bb245b8cdd8fc8cb67a72f57e62a0e1259f5e804c487a8478f6895b302d39277bd73947598a5f8ec0a535be9e9a4d34df91df948ee44cc3d13d14e23b9651089e4767c7f0e7245df55619c92fe24483225d35f5f3ee6f74375065766ffd
c1 = 0x27d8d7249643668ffc115be8b61775c60596e51f6313b47ad5af8493526922f5e10026a2cdaef74e22c3eec959dd8771abe3495b18d19f97623f5a3f65f22ff8fc294fc37ceb3b43ebbbf8a9bcf622922e22c5520dbd523483b9dc54fdffcd1a1b3f02ca1f53b75413fb79399ca00034f2acf108ac9a01bd24d2b9df6e27d156
c2 = 0xeaf06b9050a809659f962251b14d6b93009a7010f0e8d8f0fa4d71591757e98243b8ff50ec98a4e140fd8a63bbb4b8bb0a6d302a48845b8b09d1e40874fcb586ddccbb0bbf86d21540ec6c15c1d2bf925942f6f384fdc1baae7f8e06150ccd9459eb65d0f07eea16a911fa0a17e876a145dbfec83537ca2bee4641897b9f7f5
c3 = 0x15be2b0eaef8837a753587c47d3f31696a7d239d88837a9b7d903cd0d0648ef8e225ea555402693a23f305d19e7e13905be61b44c651dba5b26614bcf876234e765a724e0ed8af4a4e408e6a233c48ab9cc63e9c552ef9cd1999512aa0aca830fe6cbcbcc3c6bb354903124a2c3a12d442cdbdefdae6576f4bbc1515051b7111
a = b2l(b'Common prime RSA is a variant of RSA') << 696
b = b2l(b'And the common factor g is large prime and p=2ga+1 q=2gb+1')


mbar = a+b
R.<x> = Zmod(n1)[]
f = ((2^464) * x + mbar) ^ 3 - c1
f = f.monic()
g1 = int(f.small_roots(X=2^230,beta=1)[0])

beta = 2* g1
v = ((n1 - 1) // beta)% beta
u = ((n1 - 1) // beta - v) // beta
b = pow(2,beta,n1)
left = (2*int(sqrt(n1))//beta-2-v)//beta
right = (3*int(sqrt(2)*sqrt(n1))//(2*beta) - 2 - v )//beta
D = int(sqrt(right - left)) + 1
#############################################################
# 这部分应该是bsgs部分由于没办法跑出结果,无法确定自己的算法是否正确 #
# 所以就先不放出来了,想知道具体的可以找d33师傅的博客 #
#############################################################

c=left+698170*D+5980588
xy = u - c
x_y = v + c * beta
x = var('x')
f = x^2 - x_y * x + xy
x,y = f.roots()[0][0],f.roots()[1][0]
p,q = x *beta+1,y*beta+1
assert p*q == n1
g2 = int(pow(c2,int(inverse_mod(65537,(p-1)*(q-1))),n1))
beta = 2 * g2
x_y = ((n2 - 1) // beta)% beta
xy = ((n2 - 1) // beta - x_y) // beta
x = var('x')
f = x^2 - x_y * x + xy
x,y = f.roots()[0][0],f.roots()[1][0]
p,q = x *beta+1,y*beta+1
assert p*q == n2
l2b(pow(c3,int(inverse_mod(65537,(p-1)*(q-1))),n2))

Strange_CRT

problem

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 gmpy2 import *
from random import *
from Crypto.Util.number import *
from flag import flag


beta = 0.34
delta = 0.02
amplification = 2048

p = getPrime(int(beta * amplification))
q = getPrime(int((1 - beta) * amplification))
N = p * q

while True:
dq = getrandbits(int(delta*amplification))
dp = getrandbits(int((beta-delta) * amplification))
if (dp-dq) % gcd(p-1, q-1) != 0:
continue
d = ((inverse((p-1)//gcd(p-1, q-1), (q-1)//gcd(p-1, q-1)) * (dq-dp)//gcd(p-1, q-1)) % ((q-1)//gcd(p-1, q-1))) * (p-1) + dp
if gcd(d, (p-1)*(q-1)) == 1:
break

e = inverse(d, (p-1)*(q-1))
m = bytes_to_long(flag.encode())
c = pow(m, e, N)
print('N =', N)
print('e =', e)
print('c =', c)

'''
N = 7194944829894746935571965271122989443610702698015123026500274312320541540511952275333536082176132102091625202863345739074691901574020649953130369453360247690506566827078013306825941200018330639608298539682191482947557146237487451707849833303794107411686130468587672820352641436722348277258977791778239539008852841749667581869688275892813664557078043533743669277649148468667399393518112220602616186358353262921270486781426670131125521444335280904901224934061164334131460273779473387748722008412594372005590209919098686472153912130124772089012962023984089123929555594332030502775588070235834837667605812843128059372243
e = 5872666789397408936685003821802975734744078884385553897196686533187747297681714766542317071546532454504513425295170366015384657690105523240363850101369048640430719519784564240908244756652800934680608667950183962226340288720771217107508516125044088043789281574833079766048266075717484676158307477384862873719462770774288252074344824446884295300603035728339571606659365040029505127532956295163195257002051007447197735267997104725561159289832252522298457628452222155625714679911912616173849423059919537353814530280736653541415686756485413316581322357887750268983241858913704388088485132644523120028234659344174431547087
c = 6601667269134560091452287214083525217696007424340765571114688738279264700361513951309195757650152324371826111195352731779137577044473630747863137747356695892337017953751159248388157498368915463745769509485009626774902347006319659852239932231921393353157319713540010424345134411781723171111939891127671029064626426950125001347122070491553845919803891156107693973027238705710354919725550360159383455222982999904576805089837067774838194257113022653159325313574447189639317397889065351340828031907571541750274329094240472180870714728295651611160552345500801797030280900507979459558944006193012524181456837126192865748097
'''

May2002_Chapter_CryptanalysisOfUnbalancedRSAWi 这篇paper介绍了针对dp过小并且p,q相差过大的情况下对rsa的一种攻击方法, 具体的原理可以看这篇论文, 这边就简单的说一下条件

要使用这个攻击方法必须满足两个条件
$$
q < N^\beta, d_p < N^\delta \
\beta < 0.382 , \delta \ 越小越好吧 具体的界我也没看明白
$$
这个方法利用了一个定理

(Howgrave-Graham) Let f (x, y) be a polynomial that is a sum of at most ω monomial. Suppose f (x0, y 0) = 0 mod pm for some positive integer m, where |x0| ≤ X and |y0| ≤ Y . If || f (xX, yY )|| < pm √ω , then f (x0, y 0) = 0 holds over the integers.

$f(x,y)$是一个最大w阶的多项式, 假设存在$|x_0| ≤ X,|y_0| ≤ Y$,对于一些正整数m有$f(x_0,y_0) = 0 \mod p^m$, 如果$||f(xX,yX)|| < {p^m \over \sqrt w}$, 那么$f(x_0,y_0) = 0$在整数上成立, 垃圾翻译 大概就是这个意思

构造格
$$
\begin{pmatrix}
N^2X^3&&& \
eNX^3&-NX^2Y&& \
e^2X^3&-2eX^2Y&XY^2& \
e^3X^3&-3e^2X^2Y&3eXY^2&-Y^3
\end{pmatrix}
$$
其中$X = N^\delta, Y = N^{\delta + \beta}$

这个格子每一行都是$eX - Y$的倍数, 所以最后组成的最短行向量中的$X,Y$替换成$x,y$, 得到的方程的根$(x_0,y_0)$就是,$ex-y$这个方程的根.

所以直接规约格基, 把最短向量中的$X,Y$都除掉, 利用得到的系数重新构造一个整数上的方程, 最后因式分解找到一次的项的系数就是$d_p,k+1$

exp

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
from sage.all import *
from Crypto.Util.number import long_to_bytes
N = 7194944829894746935571965271122989443610702698015123026500274312320541540511952275333536082176132102091625202863345739074691901574020649953130369453360247690506566827078013306825941200018330639608298539682191482947557146237487451707849833303794107411686130468587672820352641436722348277258977791778239539008852841749667581869688275892813664557078043533743669277649148468667399393518112220602616186358353262921270486781426670131125521444335280904901224934061164334131460273779473387748722008412594372005590209919098686472153912130124772089012962023984089123929555594332030502775588070235834837667605812843128059372243
e = 5872666789397408936685003821802975734744078884385553897196686533187747297681714766542317071546532454504513425295170366015384657690105523240363850101369048640430719519784564240908244756652800934680608667950183962226340288720771217107508516125044088043789281574833079766048266075717484676158307477384862873719462770774288252074344824446884295300603035728339571606659365040029505127532956295163195257002051007447197735267997104725561159289832252522298457628452222155625714679911912616173849423059919537353814530280736653541415686756485413316581322357887750268983241858913704388088485132644523120028234659344174431547087
c = 6601667269134560091452287214083525217696007424340765571114688738279264700361513951309195757650152324371826111195352731779137577044473630747863137747356695892337017953751159248388157498368915463745769509485009626774902347006319659852239932231921393353157319713540010424345134411781723171111939891127671029064626426950125001347122070491553845919803891156107693973027238705710354919725550360159383455222982999904576805089837067774838194257113022653159325313574447189639317397889065351340828031907571541750274329094240472180870714728295651611160552345500801797030280900507979459558944006193012524181456837126192865748097

beta = 0.34
delta = 0.02
amplification = 2048

X = int(N ** delta)
Y = int(N ** (delta + beta))

M = Matrix(
[
[N ** 2 * X ** 3, 0, 0, 0],
[e * N * X ** 3, -N * X ** 2 * Y, 0, 0],
[e ** 2 * X ** 3, -2 * e * X ** 2 * Y, X * Y ** 2, 0],
[e ** 3 * X ** 3, -3 * e ** 2 * X ** 2 * Y, 3 * e * X * Y ** 2, -(Y ** 3)],
]
)
L = M.LLL()[0]
x,y = var('x'),var('y')
f = x ** 3*(L[0] // X ** 3) + x ** 2 * y * (L[1] // X**2 // Y)+ x * y ** 2 * (L[2] // X // Y ** 2)+ y ** 3 * (L[3] // Y** 3)
print(f.factor())

'''
(144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717*x + 636751972323*y)
'''

dp = 636751972323
k = 144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717 + 1

assert (e * dp - 1 ) % k == 0
p = (e * dp - 1 ) // k + 1
assert N % p == 0
q = N // p
phi = (p - 1) * (q - 1)
d = inverse_mod(e,phi)
print(long_to_bytes(pow(c,d,N)))