Crypto

RBG

  • 注意：此题并不是在该比赛中出现的，只是为了做出RBG+而做这题找思路。
  • 题目附件如下：
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
from Crypto.Util.number import *

PBITS, NDAT = 137, 13

with open("flag.txt", "rb") as f:
    m = int.from_bytes(f.read())

N = getPrime(PBITS) * getPrime(PBITS)
e = getRandomRange(731, N)
print(f"{N = }")

lcg = lambda s: (s * 3 + 1337) % N

for i in range(NDAT):
    print(pow(m, e := lcg(e), N))

"""
N = 9288011389664837847963670837039196937548434573294469245501561784245642854634445047
c0 = 7827437377925724428078233147899924081225364249930858942421079276821876942757073519
c1 = 8887391738833944793881713037947023989163050343070393147424888589467627754249865604
c2 = 8081548039727189478984198619032683177557008617453299085364096689176320484341697433
c3 = 2275794279542811986322743644529192750108107184530803067791576158460846098638595919
c4 = 6253142316263707598596838911072529989608774170182629190175128689020135811837569575
c5 = 4733751513227945548879795301848782446340444473234631092994528819564169644364997232
c6 = 7059294752711247585748476830322929650455626597483726834273561488576645863895400850
c7 = 3416115616735235302679100710807631760495960686259891905227746706138654756842094326
c8 = 8925820570540264143648581237815478995705636946118008059750128065916255778832895553
c9 = 2892105289971843001930724217759034130633547138605066058109243908372747042621581984
c10 = 314392853155476706788704773868088966795343394149871206877830575819199838027511362
c11 = 4327945167964771727885647567828770187834470062965467452997985192630056416939883267
c12 = 5004179351047061632898561578033712835850283897910028694457603173176131447102750100
"""

  • 此题代码加密流程如下：

    • 首先生成两个137位的素数p、qp、q，并计算N=pqN=pq，并会输出NN
    • 接着生成公钥指数ee。注意生成公钥指数并没有输出
    • 接着定义一个LCG生成器，该LCG公式为：si+1=3si+1337 mod( N)s_{i+1}=3s_{i}+1337~mod(~N)
    • 最后进行1313次循环，循环中会输出：ci=mei mod( N)c_i=m^{e_i}~mod(~N)

  • 先写出多组加密公式，对加密进行具体的推导：

    • 首先根据ci=mei mod( N)c_i=m^{e_i}~mod(~N)就会有：

    c0=me1 mod( N)c1=me2 mod( N)c2=me3 mod( N).......c_0=m^{e_1}~mod(~N)\\ c_1=m^{e_2}~mod(~N)\\ c_2=m^{e_3}~mod(~N)\\ .......

    • 接着根据LCG的公式带入一下：

    c0=m3e0+1337 mod( N) mod( N)c1=m3e1+1337 mod( N) mod( N)c2=m3e2+1337 mod( N) mod( N)\begin{array}{l} c_0=m^{3e_0+1337~mod(~N)}~mod(~N)\\ c_1=m^{3e_1+1337~mod(~N)}~mod(~N)\\ c_2=m^{3e_2+1337~mod(~N)}~mod(~N) \end{array}

    • 这里其实可以利用c0=me1 mod( N)c_0=m^{e_1}~mod(~N)与c1=me2=m3e1+1337 mod( N)c_1=m^{e_2}=m^{3e_1+1337}~mod(~N)求得c00=m1337 mod( N)c_{00}=m^{1337}~mod(~N)。注意：此时求得的并非是m1337m^{1337}的真实值，这是因为还需要考虑到LCG中的模NN，因此下面的这个式子是错误的。

    c0−3⋅c1=m−3e1⋅m3e1+1337=m1337=c00 mod( N)c_0^{-3}·c_{1}=m^{-3e_1}·m^{3e_1+1337}=m^{1337}=c_{00}~mod(~N)

    • 这时我们需要思考一下：c0−3⋅c1c_0^{-3}·c_{1}的值代表着什么含义，可以使用什么式子表达，首先我们有，满足e0,e1,...,e13<Ne_0,e_1,...,e_{13}<N：

    e1≡3e0+1337 mod( N)e2≡3e1+1337 mod( N)...ei≡3ei−1+1337 mod( N)e_1\equiv 3e_0+1337~mod(~N)\\ e_2\equiv3e_1+1337~mod(~N)\\ ...\\ e_i\equiv3e_{i-1}+1337~mod(~N)

    • 那么我们将同余号改为等号就会有如下等式：

    e1=3e0+1337−k1Ne2=3e1+1337−k2N....e12=3e12+1337−k12Ne_1 = 3e_0 + 1337-k_1N\\ e_2 = 3e_1 +1337-k_2N\\ ....\\ e_{12}= 3e_{12}+1337-k_{12}N

    • 接下来我们以c0−3⋅c1c_0^{-3}·c_1为例子，不妨设x1≡−3e1 mod( ϕ(N))x_1\equiv -3e_1~mod(~\phi(N))，那么就有x1=−3e1+k1′ϕ(N)x_1=-3e_1+k'_1\phi(N)。这个步骤需要特别注意

    c0−3≡m−3e1 mod( N)⇒c0−3≡mx1 mod( N)c_{0}^{-3}\equiv m^{-3e_1}~mod(~N)\Rightarrow c_0^{-3}\equiv m^{x_1}~mod(~N)

    • 那么c0−3⋅c1c_0^{-3}·c_1就会有如下式子，则有如下式子：

    c0−3⋅c1=m−3e1⋅me2=mx1+e2=m−3e1+k1′ϕ(N)+3e1+1337−k1N=m1337−k1N mod( N)c_0^{-3}·c_1=m^{-3e_1}·m^{e_2}=m^{x_1+e_2}=m^{-3e_1+k'_1\phi(N)+3e_1+1337-k_1N}=m^{1337-k_1N}~mod(~N)

    • 所以最终我们可以得出如下式子：

    c00=c0−3c1=m1337−k1N mod( N)c_{00}=c_0^{-3}c_1=m^{1337-k_1N}~mod(~N)

    • 如果我们遍历$c_{0},…,c_{12} ，那就可能会出现几组不同的值，我们记为，那就可能会出现几组不同的值，我们记为c_{00},c_{01},…,c_{0n}$，式子如下：

    c00=c0−3c1=m1337−k1N mod( N)c01=c1−3c2=m1337−k2N mod( N)....c0n=cn−3cn+1=m1337−knN mod(N)c_{00}=c_{0}^{-3}c_1=m^{1337-k_1N}~mod(~N)\\ c_{01}=c_{1}^{-3}c_2=m^{1337-k_2N}~mod(~N)\\ ....\\ c_{0n}=c_{n}^{-3}c_{n+1}=m^{1337-k_nN}~mod(N)

    • 由于e0∈[731,N)e_0\in [731,N)，所以3e0+1337∈[3∗731+1337,3N)3e_0+1337 \in [3*731+1337,3N)，因此可以得到ki∈{1,2,3,4}k_i \in \{1,2,3,4\}，大概可以得到有3,43,4种可能。

  • 知道了大致的值，其实可以直接用共模攻击爆破一下模数就可以求解了。

  • 完整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 *
from ast import literal_eval
import gmpy2

cs = [c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12]

NDAT = 13


candidates = set()
for i in range(NDAT - 1):
    a, b = cs[i], cs[i + 1]
    candidate = (b * pow(a, -3, N)) % N
    candidates.add(candidate)

candidates = list(candidates)
for i in range(0,2):
    for j in range(0,2):
        e1 = 1337 - i*N 
        e2 = 1337 - j*N
        _,s1,s2 = gmpy2.gcdext(e1,e2)
        m = (pow(candidates[0],s1,N) * pow(candidates[1],s2,N)) % N
        print(long_to_bytes(m))
"""
b'\x01\x04\xe5No\xb2\xd5?\x8d\xa8\x07+\xa8o\x9a\xbe~\xf3\xfd>z5\xec\xb5\xdf\xf3\x07r(\xce\xdd\xd82r\xa3'
b'Bf\xcc`HxuN\x9b\xc0\xf9<FD9VD\x00NkD\xba\x95j\xd7\x92^~\x0bQ\xbe\xfe\xd5\xee'
b'Alpaca{Thanks_SuperBeetleGamer!}\n'
b'\x01!\x18\x0b$<\x90\x04\xf5\xdc\xc8\xb9\xb0\xdeA@\x81\xbe\x1a\xb1\x8e=\x7f\x860\x14\xe4su-\xde\xfa\xa3\xb6\x02'
"""

*RBG+

  • 在做这题之前先来看看RBG，也就是上面的一题，看完RBG再看看这题。想不出来QAQ复现吧。

  • 题目附件如下：

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

PBITS, NDAT = 371, 13

with open("flag.txt", "rb") as f:
	m = int.from_bytes(f.read())

N = getPrime(PBITS) * getPrime(PBITS)
e = getRandomRange(731, N)
print(f"{N, e = }")

lcg = lambda s: (s * 3 + 1337) % N

for i in range(NDAT):
	print(pow(m, e, N) + pow(m, e:=lcg(e), N))
"""
N, e = (16673819280900186203183406086039305029633355503015642165177785252713821754128038245168506086742522561732200465183683933520327193142753150216626174796463570915178149915127289476561149748953613924583064836072383216584305426357, 12378119147501678610337261649770611209168151337774127524004772110238505033960085123372621415527094871150084993084871175112524327669409011359270267467857961107432922882670926622039355210186312510129989225708215580325230869835)
7421304196673813317975409923481375730643373464138577895117203478837741410253991957170542073505742688486777483036927401639081880938201581004682372699564975854353808846766926745565451164911108285235753042706684120135430062722
10310514708296950288418018094937293456136922163344078678133871479055435602257812692658780765570452760912905337448072845338821278761132696757453068531640517145787317571299628509729738456624596012868536351439237485358494717977
10706600270460904261196439831948408198329070106556083576592246263631682440995684375031051074126128841473794239728292781746101801250842154032948069298421719032802462540477381664361041294076387342161631416964497426527545132308
17741674878549150055251930474779884793602331126927020773267102003132346702388898201512988936342020399066931476771212177215502665122639813061873002807406302360850837715598523466004374145118320520081897521559699027539518539484
15052544499793645498232767317523228580089220569341603602968649807307916980377596934133596319710793566886440408075927443242091714220818231908920908753811465673709383950992164586398269410601381099541542654676270141785118215033
8955814504462314343066853791446124822530147494037537907055765588158166844758649181950768243148537456886167996676488531264881599233162195686649764303006485817384840286988058003839902706183720251006580981287740338680903664121
16136339792455854427434674586804472352383059375903191525063277616791595753708417918244779252435631150916026525881944228524641319477297729919628552665755839560857340524058104829639667171877532480115523482961460543323842377720
28310063699134702918116798170711016027734562946851282487553595132860170878004441342426255564029252986246490721388810405231142539826715563036189320023173250158659272250890922308913923376282302221401693895758867533557547875444
32670868781348673044025269699119924199399562645616825984163483819450694734799574409617222355463466017655024768715838697723619151110904107801820096656506143306581926496317476929409326933163041416961749056155540656067606648063
17637681715267043194845448101910627201691109692070216656091349138126163550163696902709742069059928388257199943048077466070836505294550990088754012496498363013667177990969346162095683079364952595112395867763632443443934609212
17408580429804501640126608038476405706480581520334696303243739284292472731336326590534904726234521357888440237787485906913908203825157713248321326321017378131615736898052161785896315956015224371155426218522440627580458109432
29900448516701048211030938187362905168626926018243317930313339549050126388508651420075860676206943453934596138263188191102734550227011950766997362484796312854673830122069517380447748301874106982742905878068693624980805022341
16260593621647839763080714574480088246384814991555016456995050536993176390650233691121417338817613099200688325932991811108698945811928985036801095250874906264755875035282417295663715794467581274069414499019261520411028552482
"""

  • 由该题附件可以得到，此题是RSA结合LCG，具体加密流程如下：

    • 首先读取flag，并将flag转换为大整数m、
    • 接着生成两个371位的素数p、qp、q，并计算模数N=pqN=pq
    • 之后随机生成一个加密指数e∈[731,N)e\in [731,N)，并输出公钥对(e,N)(e,N)
    • 定义一个lcglcg，其表达式为：si+1=3si+1337 mod( N)s_{i+1}=3s_{i}+1337~mod(~N)
    • 最后进行1313次的循环计算并输出：ci=mei mod( N)+mei+1 mod( N),i=0,....,12c_i=m^{e_i}~mod(~N)+m^{e_{i+1}}~mod(~N),i=0,....,12

  • 接下来对这个已经给出的式子进行推导

    • 我们先写出已知的式子：

    c0=me0 mod( N)+me1 mod( N)c1=me1 mod( N)+me2 mod( N)c2=me2 mod( N)+me3 mod( N).....c12=me12 mod( N)+me13 mod( N)c_0=m^{e_0}~mod(~N)+m^{e_1}~mod(~N)\\ c_1=m^{e_1}~mod(~N)+m^{e_2}~mod(~N)\\ c_2=m^{e_2}~mod(~N)+m^{e_3}~mod(~N)\\ .....\\ c_{12}=m^{e_{12}}~mod(~N)+m^{e^{13}}~mod(~N)

    • 从已知的式子中可以看出，cic_{i}是模幂运算再相加，相加之后没有再取模了，设mei≡xi mod( N)m^{e_i}\equiv x_i~mod(~N)，那么就可以写成如下式子：

    c0=x0+x1c1=x1+x2....c12=x12+x13c_0=x_0+x_1\\ c_1=x_1+x_2\\ ....\\ c_{12}=x_{12}+x_{13}

    • 由LCG线性同余我们还可以得到：

    mei+1=m3ei+1337−kiNm^{e_{i+1}} = m^{3e_{i}+1337-k_{i}N}

    • 因此还可以得到xix_i与xi+1x_{i+1}之间的关系：

    xi+1=xi3⋅m1337−kiNx_{i+1}= x_{i}^{3}·m^{1337-k_iN}

  • 上面是已经想到的地方，下面是没有想到的地方：

    • 通过xi+1=xi3⋅m1337−kiNx_{i+1}=x^{3}_{i}·m^{1337-k_iN}，通过这个同余式，我们就可以得到一个比值关系：xi+1xi3=m1337−kiN\frac{x_{i+1}}{x_i^{3}}= m^{1337-k_iN}，其中可以确定ki∈{0,1,2}k_i\in \{0,1,2\}
    • 这样我们在这1313组LCG中其实就应该存在一组或者多组数据使得：xk1+1xk13=xk2+1xk23\frac{x_{k_{1}+1}}{x^{3}_{k_1}}= \frac{x_{k_2+1}}{x^{3}_{k_{2}}}，这里不妨设me0≡x mod( N)m^{e_0}\equiv x~mod(~N)，那么mei≡x±Ai mod( N),i=1,...,12m^{e_i}\equiv x\pm A_{i}~mod(~N),i=1,...,12
    • 很自然的c0,c1,...c12c_0,c_1,...c_{12}就可以写成如下式子：

    c0=2x±A1c1=2x±A1±A2.....c12=2x±A11+A12\begin{array}{l} c_0=2x\pm A_1\\c_1=2x\pm A_1\pm A_2\\.....\\c_{12}=2x\pm A_{11}+A_{12} \end{array}

    • 那么这样其实就可以得到：x±A1(x±A2)3=x±A3(x±A4)3\frac{x\pm A_1}{(x\pm A_2)^{3}}=\frac{x\pm A_3}{(x \pm A_4)^{3}}，交叉相乘就可以得到：(x±A1)(x±A4)3=(x±A3)(x±A2)3(x\pm A_1)(x\pm A_4)^{3}=(x\pm A_3)(x\pm A_2)^{3}
    • 我们不妨取三组k=0k=0的情况，此时就会有xi+1=xi3⋅m1337x_{i+1}=x_i^{3}·m^{1337}，并且比值后就得到三组这样的值：

    xk1+1xk13=xk2+1xk23=xk3+1xk33⇒x±A1(x±A2)3=x±A3(x±A4)3=x±A5(x±A6)3\frac{x_{k_1+1}}{x^{3}_{k_1}}=\frac{x_{k_2+1}}{x^{3}_{k_2}}=\frac{x_{k_3+1}}{x^{3}_{k_3}}\Rightarrow \frac{x \pm A_1}{(x\pm A_2)^{3}}=\frac{x\pm A_3}{(x\pm A_4)^{3}}=\frac{x\pm A_5}{(x\pm A_6)^{3}}

    • 这样就可以得到：

    (x±A1)(x±A4)3=(x±A3)(x±A2)3(x±A1)(x±A6)3=(x±A5)(x±A2)3(x±A5)(x±A4)3=(x±A3)(x±A6)3(x\pm A_1)(x\pm A_4)^{3}=(x\pm A_3)(x\pm A_2)^{3}\\ (x\pm A_1)(x\pm A_6)^{3}=(x\pm A_5)(x\pm A_2)^{3}\\ (x\pm A_5)(x\pm A_4)^{3}=(x\pm A_3)(x\pm A_6)^{3}

    • 此时我们就可以构造出两个多项式：

    f=(x±A1)(x±A4)3−(x±A3)(x±A2)3g=(x±A1)(x±A6)3−(x±A5)(x±A2)3\begin{array}{l} f = (x\pm A_1)(x\pm A_4)^{3}-(x\pm A_3)(x\pm A_2)^{3}\\ g = (x\pm A_1)(x\pm A_6)^{3}-(x\pm A_5)(x\pm A_2)^{3} \end{array}

    • 由于c0=2x±A1c_0=2x\pm A_1，那么我们就可以变形得到：p0=c0−x=x±A1p_0=c_0-x = x\pm A_1，p1=c1−(c0−x)=c1−p0=x±A2p_1 = c_1-(c_0-x)=c_1-p_0=x\pm A_2，进而继续改写构造出的多项式：

    f=pk1⋅pk23−pk1⋅pk33g=....\begin{array}{l} f=p_{k_1}·p_{k_2}^{3}-p_{k_1}·p^{3}_{k_3}\\ g=.... \end{array}

    • 这样就可以使用多项式gcdgcd，求解出xx，也就是消息相关攻击。这样就可以直接求得mem^{e}，通过比值关系还可以求得m1337m^{1337}的值，接着就可以利用共模攻击求解了。

  • 具体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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from sage.all import *
from Crypto.Util.number import long_to_bytes
import gmpy2
from Crypto.Util.number import *
N, e = 
c0 = 
c1 = 
c2 = 
c3 = 
c4 = 
c5 = 
c6 = 
c7 = 
c8 = 
c9 = 
c10 = 
c11 = 
c12 = 
lcg = lambda s: (s * 3 + 1337) % N
e_list = []
c_list = [c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12]
k_list = []
e_next = e
# 计算出e_{i+1} = 3*e_{i} + 1337 - kN中的k,将k放在k_list中
# 并将lcg计算出的指数添加到e_list中
for i in range(13):
    e_list.append(e_next)
    e_next = e_next*3 + 1337
    k_list.append(e_next//N)
    e_next = e_next % N
    e = e_next
print(k_list)
# 定义一个模N的多项式环
P.<x> = PolynomialRing(Zmod(N))
eq_list = [x]
# 写出线性方程 
for i in range(12):
    eq_list.append(c_list[i]-eq_list[-1])

# 选用k_list[i] = 0的索引1,3,4
index1 = 1
index2 = 3
index3 = 4
# 构造多项式
f = eq_list[index1+1]*eq_list[index2]^3 - eq_list[index2+1]*eq_list[index1]^3
g = eq_list[index1+1]*eq_list[index3]^3 - eq_list[index3+1]*eq_list[index1]^3
while g != 0:
    f,g = g , f % g
    
f = f.monic()
c11 = -f[0] # 得到m^{e_0},由于常数项a是正整数,那么就需要将其变成N-a
c12 = (eq_list[index1+1](c11)) // (eq_list[index1](c11)^3) # 得到m^{1337} 
# assert gcd(1337,e_list[0]) == 7
#c13 = c_list[0] - c11 # 由c0 = m^{e_0} + m^{e_1}计算出m^{e_1} 
_,s1,s2 = gmpy2.gcdext(e_list[1],1337)
print(_,s1,s2)
m = (pow(int(c13),s1,N) * pow(int(c12),s2,N)) % N
flag = long_to_bytes(m)
print(flag)
"""
[2, 0, 2, 0, 0, 1, 0, 1, 2, 0, 0, 1, 0]
1 272 -770372128310896373600173968143183852326601419583529335625414259146074101320700564921758985700955229077152057814009587925775511075976095401136798178381386451614324247143029654700709340374917751153989481940559045417745877495
b'kalmar{GCD_is_handy_like_always}'
"""

*RBG++

  • 题目附件如下：
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
from Crypto.Util.number import *

PBITS, NDAT = 371, 13

with open("flag.txt", "rb") as f:
	m = int.from_bytes(f.read())

N = getPrime(PBITS) * getPrime(PBITS)
e = getRandomRange(731, N)
print(f"{N = }")

lcg = lambda s: (s * 3 + 1337) % N

for i in range(NDAT):
	print(pow(m, e:=lcg(e), N) + pow(m, e:=lcg(e), N))

N = 16167885915193478051793877611486619241886473426863252783094589654879500659067740377062272392685930800102844215704528436693321982169968535528301909521740422063158802614037675785775081053858036967400526899115004867166488372889
c0 = 23524356627767287626245212608188456486510486842884944774388457118524878337010325280806281200006513760569554973350027623280980530389685273358299240165163348831178950906369654270836363037734464763165971796940465525441254094362
c1 = 20417144512792463288144454294819320198675053687066876812066787608526065186517106068771714888222417207180901619094929565058749740851992567962732918068890150032710566113874561398162760409944385995695085324172030092973190257577
c2 = 10520424976309587244912110505341168843522648629096918766553735784501443210882592550479277468613423963705805659813405742198752350482717828219056306550361834962704972988508557816667577007199850461049600946454322911178025895814
c3 = 28416909341346079015691726773959094667208223393729534452929780717857409186196632999871779099602625608658264267942740600698923013514062007796972264721858347629495290125482551932172999550972465888918986818817641605942946302269
c4 = 13726101796518918198841603477266908176269927986721419094170346997210468256681669596811076017288635901027824214355508759505804142713134671111828180284950952694760868431615260399550164769569802678738352767488681833934922352002
c5 = 7059135920136984682619547524136733590336084747127571833901574207695908758597030628819518078734835875903676286698006677227435366797878296640870110580930580780541831515247457659036913180316011519506533739371284803446264538047
c6 = 18114330070303714127374862852404836446338473800998137260854472721402718228910593862247576904584967808037790567556386654254596987775778643091953549798333260613932749414814771423294192557048787267003770652263973921262534377183
c7 = 14024559830863501172859236595254018083386450610113957720574936260200693385470309651122263774523894338056498251126676380775402987334909286674227528042523017547040815880712344650862892304870500894966837134039228748259027891163
c8 = 20783427409134089929631861486165320405260692137373818253653583741789894085587697897073730814517050409045721495693810063852809883234663040555437009593591701039747744925654448134629852690869255270077530796315385494306996697237
c9 = 20078852233838560639474148300385005821619143638582187979901861615368043340588155414143943202029115867837960897653409172923499731121080322641384046093907847951840290312518580774674105539882427972148432914953002780564372917221
c10 = 7369159821229098087225095068409607495246454419419870990600774955280641204545018542922173971731656269817893121699839305129912165346852811633532702577660379661244835089560383766746905538158461209678477015180929067852326898444
c11 = 22986319046510221561726808690526226110839995853248874441983040062613836917937033996788905178648980051469309280020942527768493330242853133998218474862906255053829012993692501729318766820549090466990211697110374008758984176878
c12 = 19954562328217256097554541794609662507532316318267407018994469798461250289180783564705578124471535425509772315004669932259619221040010043045394925680826128717825820746481384587930181846263862127788673776096640745472574724624

  • 由该题附件可以得到，本题加密过程如下：

    • 首先读取flag，将flag转换为大整数；并且生成两个素数p,qp,q，并计算模数N=pqN = pq
    • 接着定义一个LCG线性同余方程，与RBG和RBG+一样的同余方程：ei+1≡3ei+1337 mod( N)e_{i+1}\equiv 3e_i + 1337~mod(~N)
    • 对于此题来说，并没有泄露ee，而是只给出模数NN
    • 最后进行循环得到的结果与RBG+稍微有所不同，式子如下：

    c0=me1 mod( N)+me2 mod( N)c1=me3 mod( N)+me4 mod( N)c2=me5 mod( N)+me6 mod( N).....c12=me25 mod( N)+me26 mod( N)c_0=m^{e_1}~mod(~N)+m^{e_2}~mod(~N)\\ c_1=m^{e_3}~mod(~N)+m^{e_4}~mod(~N)\\ c_2=m^{e_5}~mod(~N)+m^{e_6}~mod(~N)\\ .....\\ c_{12}=m^{e_{25}}~mod(~N)+m^{e_{26}}~mod(~N)

  • 对比RBG+来说，此题不能使用RBG+的用me≡x mod( N)m^{e}\equiv x~mod(~N)，构造出c0−x=x±A1,c1−(c0−x)=x±A2,...c_0-x=x\pm A_1,c_1 - (c_0-x)=x\pm A_2,...这么一系列的递推关系。但是对于此题来说c0=me1 mod( N)+me2 mod( N)c_0=m^{e_1}~mod(~N)+m^{e_2}~mod(~N)并且e0e_0还没给出来，这就很蛋糕了，还需要再次详细的进行分析。

    • 通过线性同余方程依然可以得到等量关系，其中k∈{0,1,2}k\in \{0,1,2\}：

    e1=3e0+1337−k1Ne2=3e1+1337−k2Ne3=3e2+1337−k3N....e26=3e25+1337−k25Ne_1 = 3e_0+1337 - k_1N\\ e_2 = 3e_1+1337 - k_2N\\ e_3 = 3e_2+1337 - k_3N\\ ....\\ e_{26} = 3e_{25}+1337 - k_{25}N\\

    • 如果我们像刚刚那样假设x=me1x=m^{e_1}，那么c0−x=x+A1c_0-x=x+A_1，但是c1−(c0−x)=x+A3+A4−A1c_1-(c_0-x)=x+A_3+A_4-A_1，这就导致这个递推式子就会出现更多的未知量，这并不是我们想要的结果，而且这样计算也构造不出来RBG+中的那个比值的式子。

*RBG+++

  • 题目附件如下：
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
from Crypto.Util.number import *

PBITS, NDAT = 137, 137

with open("flag.txt", "rb") as f:
	m = int.from_bytes(f.read())

N = getPrime(PBITS) * getPrime(PBITS)
e = getRandomRange(731, N)
print(f"{N = }")

lcg = lambda s: (s * 3 + 1337) % N

for i in range(NDAT):
	print(pow(m, e:=lcg(e), N) + pow(m, e:=lcg(e), N))

	# Internal audit
	e = getRandomRange(731, N)
	print(f"[DEBUG] {e = }")
"""
N = 15799570859077053940492342195534009129029031475644902333347360612140434908889342119
26125861269452745191108099740846419951580490075712753923760740162242479453492091008
[DEBUG] e = 9458973750340238239581769205772038870352840756366415832778530623531149580406802089
15382220576957221323138823422557477132324765769486261239685481386596394245392607625
[DEBUG] e = 13668913207107248348508108990006896711492510067745428166264047390992263187648665917
20081874742437640458852890114931041077696527882906352227358367349852439880463037714
[DEBUG] e = 13798033086422292757566320320386894392860596366034493087266617679690813090164846918
11301297450552812475801311598855933707216479760381664659415161811437202824143704487
[DEBUG] e = 7753419255702967059572507670827815388578740828845605233321566754348636987256373366
15860316800378226417552844834404358932240296231398306261016527670230047886629548948
[DEBUG] e = 1744753830955405763129396945684809720032679777954546980524195319301826292577584383
2745555175206709412911972787999262835297281850071147534624730117162657966134675028
[DEBUG] e = 3872618946887734677363166874362671955313207622265308972271721900591369207058386959
16005088592530920970971122263733504398276663473949744121958568455650300088784405131
[DEBUG] e = 8761727122317001757090917613559692955272926640359231313614845831666131198993202215
20063693792227344727983346571170816103955319336660989085468207537946677863107901597
[DEBUG] e = 360217655375523525308236733557144437447741171723226773676271864042581355162269372
12046099786688352210758369462787436837988969377578505396829822982011785325032760686
[DEBUG] e = 3822754713067468295779474487888187843839264757634835182362407613070484546943285617
18118396207397454121218831630270812717338341134450618226943374194702005599585677950
[DEBUG] e = 4163258936346155921520536562854669215176397575812893410228912027653604893322695338
15536530904718330121158407983605506034182994191099213341895704220192195294233397108
[DEBUG] e = 15103282756994770052153123675746840892959657211177707386288594381840580682084737077
15024818462615119674370805045238192267485564776228093909237812573362380777443019850
[DEBUG] e = 12803682582907194374657306449004742188783286568487254667754249172358070726611635625
19971957641338837029161090326867712661872679435231303756645827949792660156409471074
[DEBUG] e = 14226973186563693328590299335973521696648571809314587336875970085683945400151542385
18769225049886973657873212845838021938534664679406580813202921010464602705584706741
[DEBUG] e = 7765901987686525529652473342597584671584577185729760456762222531775330238249087723
22855005796860456363870966804444283885813099229902660953059357171249996174168955501
[DEBUG] e = 8641692649787805957997609474680043547424996634304156228576202739491429140204430607
17659759724694180690954245563366774587218862462689675523775088160983073049711973758
[DEBUG] e = 5382596293738435477597912004277498272482483916638043203135096540164447640133495784
3946139451830416292081686476295521996481013708497272769518552882171687146189460903
[DEBUG] e = 15748022972856681783732619605543858600237099662570047053904445272189768776595371074
13091536445594347494449787788253700869443038462275008351071347215156271300568280434
[DEBUG] e = 3181978266164377628655243753100078767843678760904140655721958361070736318922313595
21601497591455082555688725898798722798958320626014763537708712979195045364858669297
[DEBUG] e = 13382415273751396461803580096521642390954623479026503222565472763518573515526798960
20236705906101476645587953521321236888709091272325135646238982911469298028722957115
[DEBUG] e = 1618215924198970640572455408182236042147846404938919923177231093920715423206663154
12986797221242966539044655272039208894407062503770090741721619445488776580949839181
[DEBUG] e = 7037704290222971675364259057853088527733381075364716587181793041411097726947130249
24117041271979434041708016775270608009119479599356421081798425842113852242473825323
[DEBUG] e = 11063573887372745521221591435150878059748477065167762445702049645658679683570935252
27702355867370027861538409379309546380599652937286432549505370593348920219423219123
[DEBUG] e = 13205870858022210256912593694909327146962474848086898043936604987734992156644981638
3530864881608910438409841240336326484205445665604746719525894795825634347487664687
[DEBUG] e = 14665874168418534251144458924121657202600851963635938500535115945150095846292597198
27531188697521031765181979844509267340006863097912534628344245709910118458867932159
[DEBUG] e = 420658571210518908888954861216507174160672479191692552544578935416053900794223429
16337667553942104543947171481417959552984365609289081552010802631524162060232681552
[DEBUG] e = 6451541499404732048575901570081228982949186538424140846055328063288309749747819876
9558899243412424337368130888908813973364464761957135715861289233739473070729728729
[DEBUG] e = 3323353389613147411676512739458485049127855172532886816138271851509741630322368153
24793187466531219659039922978776819899342023888148382465050201394566718268047271402
[DEBUG] e = 4770535023519095062851791257209548142507836425331721154152473655389184557100202499
21518635804124300116264883848244448285078874937220409646701720010484748890172280098
[DEBUG] e = 10947159066023486368255503862333042975171093277087347016679927297650470249942956462
12161954831263393772329526680878230825117544446228775891762433376684644315853590196
[DEBUG] e = 7686532456500885393950214015183654836624020134802497181136200424054286440368108638
7028682877073307832545356057709910865391447058513100052217777687480716084428973543
[DEBUG] e = 9575170608735829892475066373394217927042739025765497785906119802532376125376837401
13729601845432478953155898109112515432427056811990939340166840585602662948439460375
[DEBUG] e = 7417627595342148780907106119349714316121271003340956067141410768380132259572616519
11107489469535464998635119383807354513432529605057749663578210245599747861521103522
[DEBUG] e = 14690352214638142727230228595861882791621729846756568704250312782133518729755294532
18344725018862414629345816542662695526901203565007231729010107053627089903690841929
[DEBUG] e = 13112943586760512896323347201477261631207344640767468546579502747952577653512682066
9755055246011429227505032236338245590751487414579832795245802270841439739807202607
[DEBUG] e = 3334514457949991865486510212804308240874508591330697418598999402723315123194191286
15052334770114785642261829042211937907550529229591710018654016684342952710746765100
[DEBUG] e = 14828667435080097824843428982740649472782536492854862832294963001020776451453676082
12670550804074050100737067110564447671059753110226709349500080095966551968795252738
[DEBUG] e = 10802350027720898231671879915765006940062284851187124641606967347100784795556028740
14230338254978573231599146694862206102965477938399337792080398144063414803193947765
[DEBUG] e = 14969740814239120081371659533118395051685692477361976787307874374946445320766087938
2976373496947266858953716695350999120830748656625558665385979530949940700760017695
[DEBUG] e = 7642502845990973360830822473200163773819065923390490675625296703141962088766162752
19794576251263830338850948948366554728456681418085201273797975096953768249417060719
[DEBUG] e = 3805079009813500025522379176884222141591900721574082932098248153070966942168001265
12041301216747700898427661544625445113680904136814556238111644970419320891987850763
[DEBUG] e = 9958964904698241102048702084187179513133438781356180202222090653089811113556802825
21247728204049195708439219207404784541000386342735260402603398596933803297942866917
[DEBUG] e = 2849133878951575126723894668022092624361240173101958434884223652742455630472857683
4053482893551247177910627187717063112595831554850490660827621712523963035780549692
[DEBUG] e = 196825619515950747266415588513929867841276554943353681032782963887352081277199338
14963626367169572604949503816341665863913364958504093625965868182250931209912448933
[DEBUG] e = 8269888889742115334391211590227102284127660606026071984984856904019390480533166413
16527889091525583652795653069775920100032148415509951723648590285428689100635404989
[DEBUG] e = 7248915842197216556126307082375700236871504225736385618405769680847495570539141914
15765295077775995196423888403057862351887614948613770806360683498023784331964547525
[DEBUG] e = 1324799475663982686412691955141553263969468436725845092955442072379974038629935413
16274666858978105121213760631488723468781058281363359587396921745754542646094027088
[DEBUG] e = 15514610507897939194593405324710047923955947082826731560556417858460050456364302602
13700774783793574966370740150750146843167582773936837517545883284024104549680508422
[DEBUG] e = 7468372913771986085279265892599642403716124479318581998137922661265394476839261330
13348541043592838320956952493763160524135435667696447806283553693809915273616770311
[DEBUG] e = 4712230647298490597320166793707834293162698408800112177208516939129232755841630945
23522780254325209049360041596114912527173298639156700754278679011834543948299568298
[DEBUG] e = 6368196610277946455972365534842675664742037098663083508523025457868774527223907977
7448920817366428115953750495281381046420375102869513768834183273943769709877951464
[DEBUG] e = 1147883617361737688903297603111273349597369096198593376135714460382670726329444019
14859161218779807812058738970472100290888615188636993531282736040179595081062297523
[DEBUG] e = 9924546743032759455002754896151545277786413775439752391045990548221714689070047972
6911667302835969542531460433709663941364691571730291518341349649847799803406062824
[DEBUG] e = 13854700552347896575935361910867682330724055933064791355999462958687220139005168229
27527551382518156030060960020382923179513664074481401015052666078562569103204660075
[DEBUG] e = 2847724440140075128905521335915084612029931904647876637459452204982066198342009927
28147995128719463924469343184039056877809332087918527353012836641087392427776104089
[DEBUG] e = 1090900472030727305597767167575576629678993640189245313893100361404969769032640905
6541451551789777349803058423781838171312003303810885861407372277570180052112764643
[DEBUG] e = 14071129302522341638918705576384645093400006394871373280329948065694545660889746939
20154246458990581176428041543280767360316540049980444537215886987305981294663402541
[DEBUG] e = 7277739724593353712883256565677619285897134690652913134255940963025172718803750688
7496906798101669323320290643415860136406863038592551824070972171884880378449024310
[DEBUG] e = 11072908280551662172218835678684399109610646853838799776186043084216363461755869031
10204561526411849564533109033629010916834988574148832737285780707533222529185721318
[DEBUG] e = 3970179758565740365656014197236660995182338865678460355591542500456833117073351668
23579999221940101117137913133611773795196344757704874614936466161211154340114147396
[DEBUG] e = 12881699865242026108082691299091609877168159561695118055359043325029552285086480530
20994706032815312205634293600518775548194164233127280655153965205555026426114951965
[DEBUG] e = 193942374359018544547941067223900774981594510485705519406163245115332422326148118
19474592641182708225392205863185362472716939407262665252831694589045249838589411818
[DEBUG] e = 3084319377012175628827102615281833869230842947177938349828197322590988628788319032
10302982772771310438581674114903056763747606628125757157222904349927851832044883174
[DEBUG] e = 6077645784153690015922252176566255644288519332953031784752118575138138996799865358
21413926096323579355361934064527845708552252162624176207151411273939862540424845284
[DEBUG] e = 11604080198629774450846188582708470587778699650383888406775972877403534212975351478
26774387499919370228796616709665100180107651475490810176143526684007993778531242002
[DEBUG] e = 10259824422428692261333448173259588182982550128804109709368062232016059251029654966
9056298406475490390319059459654269124212377465170557206332430513202499280391653167
[DEBUG] e = 2324567182844482223979152430440191443334911059139880688127895987768018447292767446
25821182867079786609244965567207095659924788161137471554911117400734236661399828375
[DEBUG] e = 12810241567116933367796853749048100825100184540222776863129508582261272436719010778
19518797500573650014123043389240466223937047028881889122941317358628573612372398997
[DEBUG] e = 14883763669645735642054156604978138006157853586334687283193494196105533373032289487
17441122954489376118359881815789442105511070637130838829393398480236948857642543603
[DEBUG] e = 14941525264561648824738607887500012081208480140094010841241123616417660242722700592
14511474113986466193979036381769039626361279666924426650738685669278668747442655375
[DEBUG] e = 2121883136621290636283303063866788108424277520821446112793121233400352344061304191
12111128151713732341450648687030487698953163286375770919010802879182809473925783183
[DEBUG] e = 12208442514446210617540521955970386732705798110791031347550174527081815615246514811
14007844016334952267667458584122261182371105909522870754549869466146451077737876316
[DEBUG] e = 15219582898923405945013485121353885031260025043226754616297767172701094121687813070
22758228045690028300648124332193899956034195724055316296023687330418531727997096207
[DEBUG] e = 11761579764718523458550091893680112378697619171462475841683653910369140543327776496
28824226427735596692469360941736034306121531213215459686256305809406510230586716386
[DEBUG] e = 14145685218923513057918580357234162729659502117363999282981525166652502679470643654
10850059234009072279209824196991692201821100205248945902765315689170374232315266478
[DEBUG] e = 2309096763492060325467880746556807470474642786080324767034262292449830287575889619
17539513026175460192137042229528688432686298346208141004596752815474122722633995992
[DEBUG] e = 11176897237531593069038035338676326922835508429123371693010061339947755615418575332
18177385662790050467930060117513214207097733931262672395089584000423236151108673319
[DEBUG] e = 2166590787662661980070811900968964997492487995022045388455287749394887728646233274
15922072330010469188455819801048416003752661860566483980652978267583044147128215967
[DEBUG] e = 4225289351308302313198503300190773324269513287401105180029536885475101531365357283
18824708700703791455515369568828269201021359400601363498056252707085307187293323514
[DEBUG] e = 14758669574377713563494808902255298105225032957366622584735312438444487345061400759
20145179724805379010347944141424204051879752553987147020416389309746966239968113518
[DEBUG] e = 9280839290499535286756870882805335809294172953774306694338732365545624889327422522
14556020023020086078358819319177000705682200030741563914538448594453288595546017695
[DEBUG] e = 13658701598944888090775040046821142447629766637108851375412837145331356325017066722
14487234718523521105183207718021216884074292953829598302904696380674486739349888295
[DEBUG] e = 4449396686207463582200161474551287611446629692216930574897838099970189441271946344
16597967964684926485644938954210517670750190489594300512464990708052967527579140257
[DEBUG] e = 6560655921693068701590404435290061707125550169350113044740667336790374482341126462
3757584509857902753012722467213209475332822870326299197725490871962583118300710778
[DEBUG] e = 2896758473713408890793544371820246507694547513253809092473141849033550776931456342
17698120876015923419423057746936773291723273852399266148493459189714860308939512145
[DEBUG] e = 15689114026236769468458664762455221719606620625948850863485804146933561308029927437
22696668099234553131638185081366860731897171260833018505891912449325315954596301658
[DEBUG] e = 12159119002279413294000862761238991577988164379823683658854793409936598321463229123
16784426110002137565979075695156700711501481149119424093275625678991106336230687410
[DEBUG] e = 8951592487136556587132023088267443135316410548837682641039119082618635822251990899
21649926207035530486871180472386331424844436538363782897632281445098118391690132954
[DEBUG] e = 1322505478906901728482489138038648467692687549968834933623946420253625058690500526
16445964814762868248698078863457324375885470468507554150831589940172450185083247356
[DEBUG] e = 9486173052452718169302884632931740385493358570032839014544280864427076579480628314
12504153975362690267731880608275928723902345541055867485720112584442898160449439743
[DEBUG] e = 10545067600260123905481949096412713544636958562675715464427819891971630506597101015
20923066927542761211120395862447611891791851277512440768943027630918927370507140089
[DEBUG] e = 7703877219423292445154457346851801736589215146905116086580123935957105850177984947
11470670268071873570296305413976713429240398536409901662109522285238640888068382761
[DEBUG] e = 8488684624265955894422385338826285386638199098670190954665426349089654736950097050
15056617721986411547381801717796059476640330149601445555444614484398913982377927657
[DEBUG] e = 9153658248047551423495291961192790306362548369513048379537233522063695125857186339
16062293664276227617282851247511719176914160498985598009368551642638502618759507425
[DEBUG] e = 3645375008216853883002449492905863629673214753438807247855739453619944799743777223
19259904429035222185101318548526846443063469788145548010874409513813949514619602505
[DEBUG] e = 14777900231333286253016853750366289665155620123234865190935206143962065333358404716
12718998363459666604427629285570186346049426830160839989018478384399694081407559512
[DEBUG] e = 11798385480710825495188250211273754486626244062222647874965134100684863279664979099
22317551857526823423769050528897144641595193971550923660962935100929735528738619350
[DEBUG] e = 2144912465449515450892962873564401255903633755350032595199648735832685268045509577
1209810910976503142921383646535555513924119589661928045380149047767327523410740829
[DEBUG] e = 8757517954541213492934921137271943152976840134544525429023184075628238950286141040
17830707767541239558501511918190186138032249815691817382909695743569247229296765486
[DEBUG] e = 11814384518591782551993819988244998766745611397133042782357590752782430556754073565
9710724437248902020385615905161695097751386536741398286873697504027292613092839099
[DEBUG] e = 2189325689312760605478832547499308235930376944321916301588044717116567064641899434
22762674909838591242507335176434096408816354411045807602501602651056779223829145832
[DEBUG] e = 521791486684047175855934176027395330007193658546200897793765473563497911631385407
22643791570715396183464444611439852187827580868254287280729715889513556902151097465
[DEBUG] e = 13671209345152744318476079090982698384021660752329519305221523862411132484885684866
11205092143394925877968529301626140801633722967722905328174912477254559559024598943
[DEBUG] e = 3571266125781589572517601028492291976740814515561183345249090330470452735364748936
6192783510298122682437856336363629394750645261708866966555922742193811175773499624
[DEBUG] e = 1902495066415873974498505418777582755094645001526301637469307760955208084453414611
19061702756821476564042410860645306809010447171974602860114658304689398854792207771
[DEBUG] e = 11620639700752934649541395229541546158535771856504614620377409140083024541599456268
12406234816812931260226859208464543436737675372757834707674931649796836512633546038
[DEBUG] e = 8402549734931830197831325985591831893852923345116161021864772775004087040974858094
7715816134408463826305297228193939563140456022698701899778809431741208141603984905
[DEBUG] e = 3906971429757774733022394439497343545516726016714617166626945160551315026806036279
18877699815435836469859159552851237539832555465232794277318215216024898633828902171
[DEBUG] e = 1899096396258336874163093882413542285782118877062241379497770621905024348093567192
10069823363198144292808430332450572284190463234597135419438714601565439815705493308
[DEBUG] e = 9667290777367154158334876425865929665062456343494315976036210111023009163383960071
25413165204599420987652861914645885591125268546380252320584518401368481103241375432
[DEBUG] e = 13463567418759651741975169126028575753501500079952935643018643578914852536496932654
20946139700245758428568611713235301214246371632005386566647128964861807152789865101
[DEBUG] e = 9760986924483987435905009223169588418862046099498802960632872541782173879286973775
3392213165585201294145944113253310987116935376212853115237616717207608358924036809
[DEBUG] e = 10080782704144535942763523568473851156834308880239700378125538587768514491924985046
19398480242817108595654209920032139370622956463042469662290757405882591663085060909
[DEBUG] e = 5659723403560140449911424893315703232216706899858048061880713593853336796781647567
4969076967666155379118584723694921386343294026359550999921241128815620442073413400
[DEBUG] e = 6600175696296482343862930777412530709985856806697331077694336109823650683845398035
13043044180676512739915743641292811393831793755356094864508180427864826113786992789
[DEBUG] e = 13513018428284267516809703769123614134445969659973972977488804754467943430607705089
27284928118591735697550072237873296791562215096924095560057972007987697484618818102
[DEBUG] e = 2158066193566562343262757223341426063376765515615011133839914094585095655610347929
8313549303219910592082673478836391074630931643139298387580991839095784697180343847
[DEBUG] e = 12929843298846461699041478600577165961916010429006522771916051934664458748017425208
13276390778601721570621957119595630022152161244161599407058811990544240458024787066
[DEBUG] e = 11212027752508003551236789923153222134405118997630808233370921941154473111167354699
11619405704390934661447317024473672420479121951821777859548014340609652611933865090
[DEBUG] e = 15602148407735914832353601466975304267484421590269983704952131742676008762999579836
24139429168334748761111583031972031452077827771663385079149816944626534509121646453
[DEBUG] e = 13521913306185171987776927094319386524494320998471455817570858666535920748270303530
30011880307887090577802509160740546558627436646444795452925579690090156462209473656
[DEBUG] e = 10514386340979478028792270955148856122136833647130568744998627086748639125335528653
20016647319991084120700003522141043043634819376109066461113614065173864816796319095
[DEBUG] e = 2512160856895060492366685107502352520378916538695322156855951834607086612705210457
21567366753187247755671984247885977748253518263970395788452720133904006102284260115
[DEBUG] e = 603483090315000387847641842862956839318449458911072035056839467902044038960492942
17428268994814783774708320928615738456249874711470928403463046701113802383001614698
[DEBUG] e = 15478775221256725952116424629700846695973754977805089214179070264893950578422062319
13041446680344547463850685792383754701025277133192012028909922269889197614166453700
[DEBUG] e = 10090161874657908475902644455818774116116449286525699463261079139200723208143157932
26412472696822148281886433507470041696062869679556962794066799054933390525529689069
[DEBUG] e = 15243776668569256303722312210633534552964239307533415620671870492724653021268880626
13659329184017292160462467619732510386809499244367181033018361938345066620610097890
[DEBUG] e = 15587119902652451374318462924382928437588327397737355106326926604446146630607182707
16155004810911439112080060761035849907662618354527914551287706171877497140599692031
[DEBUG] e = 13608549725890230267193496692602609465761793797328563027045317222631759936398879767
16704249408691025865441853624515289804470546807187196542191545899455955358518842649
[DEBUG] e = 7825382616530969404301971314396025080354823070315166211024240354263082314087692131
25434858477894799739541893489039835955365024327556555488234685997362869057971552445
[DEBUG] e = 710225341053275028687955635670325726432866904571462785050517780841238679612988861
15723793357180790015485686935579552341072801457350399546347183700689792460594101843
[DEBUG] e = 7266179498252582912826958419678612217982273732007735075709886427036815479489425377
18523477976739214105405836655051544847076598137408517114080006254296246213217060645
[DEBUG] e = 12813143380029374233500237017018676757952298259019814196940159850764069373883131926
16314871036116342338066294041105185306627939722145377060811030328461377103431534919
[DEBUG] e = 13319254534696163323582549818306184847429283889832573973323407258066751723228648989
13439874267286602834130467803968404118130924182715048470700187763461436776180987515
[DEBUG] e = 1249117245733002614831966476801003129930276353328354186839320070284443976145216349
5937076116547203733392379892400326112773369507647691339722741519631535163942369031
[DEBUG] e = 1648604536534222076497334472022404067971238446351176300116762514043180938302535340
14701106730168383191689202370172233790966993320722849999437911403493221706753853808
[DEBUG] e = 15095147462531408994152177548826084570825298069925106486433754374997988329056952829
13954672313198923892567843196001030251554310964789764077509206398090506850398103482
[DEBUG] e = 14076344271334615393993515415673949316792281299986491558125859432731416787632697363
"""