虽然没打但是拿到了题 -

Elgamal使用线性相关的随机数,顺便AMM算法练手(挺阴间的 -

题目:https://paste.ubuntu.com/p/7793PFBR4b/

首先题目只给了pp,而qq是必会用到的,所以会选择先提取qq。由keygen可以看出q只有8080位的大小,且是群阶(p1p-1)的因子(因为gq1(modp)g^q \equiv 1 \pmod p),所以直接上yafu分解,分解出来的P24刚好是8080位,基本可以确定就是qq了:

1
2
3
4
5
6
7
8
9
10
11
12
***factors found***

P1 = 2
P1 = 5
P2 = 29
P4 = 1621
P4 = 3719
P5 = 41927
P24 = 791763770658839585424113

***co-factor***
C271 = 1123636664726630998275667045059214857021268560333173479449308028763868302012798770340527130132430481340323131813835615529948284264416590543063810310761463564241842705664625568460750891757649443885331925482273332596241826223708885363691353210748069567213006840649556674611

接着AABB在生成随机数(rand)中会用到,题目的漏洞明显是随机数线性相关,所以AABB是必会用到的,使用后面的s0~s4和那串assert就可以提取(注意要使用到刚才提取的qq):

(si+1si)A(sisi1)(modq)A(si+1si)(sisi1)1(modq)B(siAsi1)(modq)(s_{i+1}-s_i) \equiv A*(s_i-s_{i-1}) \pmod q \\ A \equiv (s_{i+1}-s_i)*(s_i-s_{i-1})^{-1} \pmod q \\ B \equiv ( s_i - A*s_{i-1} ) \pmod q

解出A=12742153496769814072597A = 12742153496769814072597B=3035433788765894539799B = 3035433788765894539799

剩下还没用到的就是C1C_1C2C_2C1C_1'C2C_2',由rand可知rAr+B(modq)r' \equiv Ar+B \pmod q,分别代进C1C_1'C2C_2'里,可得:

C1grgAr+B(gr)AgBC1AgB(modp)C2mhrmhAr+Bm(A1)(mgr)AgBm(A1)C2AhB(modp)C_1' \equiv g^{r'} \equiv g^{Ar+B} \equiv (g^r)^Ag^B \equiv C_1^Ag^B \pmod p \\ C_2' \equiv mh^{r'} \equiv mh^{Ar+B} \equiv m^{-(A-1)}(mg^r)^Ag^B \equiv m^{-(A-1)}C_2^Ah^B \pmod p

C1C_1'那个其实作用不大(可以用来做个assert),C2C_2'那个换个顺序就是:

mAmA1C2AhB(C2)1(modp)m_A \equiv m^{A-1} \equiv C_2^Ah^B(C_2')^{-1} \pmod p

e=A1e=A-1的话,就是个“普通”的RSA解密了。但是eeφ=p1\varphi=p-1是不互素的(按RSA密钥生成的要求应该要是互素的,不然不能求出dd),就不能通过模φ\varphi求逆的方法解出mm,而需要用AMM(Adleman-Manders-Miller)的方法求,具体做法我直接Copy了Arpe1sFurutsuki的代码;有一点要注意的是,当ee很大时直接调用AMM是很慢的(甚至不可能算出来),这时可以把ee分解一下,拆成e=e1e2e=e_1e_2,其中gcd(e1,φ)=1gcd(e_1, \varphi)=1,对e2e2mAm_A做一次AMM后可得me1m^{e_1},由于e1e_1φ\varphi互素,所以可以求逆得出d1d_1然后求出mm。不过实际操作时发现e2e_2中每个素因子只能是一次的,不然代码会报错,所以实际分解时可能会分成多个:e=e1e2...ene=e_1e_2...e_n,然后做多次AMM;比如这题就是e=2e1e2e=2e_1e_2,由于这题中pp是模4433的,所以可以通过计算mip+14(modp)m_i^{\frac{p+1}{4}} \pmod p直接开方,而不用再求一次AMM。

最终代码(代码中其实是分解成e=e3e22e=e_3*e_2*2,后来懒得改了):

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

s0 = 543263588863771657634119
s1 = 628899245716105951093835
s2 = 78708024695487418261582
s3 = 598971435111109998816796
s4 = 789474285039501272453373

p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
g = 27642593390439430783453736408814717946185190497201679721975757020767271070510268596627490205095779429964809833535285315202625851326460572368018875381603399143376574281200028337681552876140857556460885848491160812604549770668188783258592940823128376128198726254875984002214053523752696104568469730021811399216
h = 54585833166051670245656045196940486576634589000609010947618047461787934106392112227019662788387352615714332234871251868259282522817042504587428441746855906297390193418159792477477443129333707197013251839952389651332058368911829464978546505729530760951698134101053626585254469108630886768357270544236516534904

c1 = 60724920570148295800083597588524297283595971970237964464679084640302395172192639331196385150232229004030419122038089044697951208850497923486467859070476427472465291810423905736825272208842988090394035980454248119048131354993356125895595138979611664707727518852984351599604226889848831071126576874892808080133
c2 = 48616294792900599931167965577794374684760165574922600262773518630884983374432147726140430372696876107933565006549344582099592376234783044818320678499613925823621554608542446585829308488452057340023780821973913517239972817669309837103043456714481646128392677624092659929248296869048674230341175765084122344264
c1_ = 42875731538109170678735196002365281622531058597803022779529275736483962610547258618168523955709341579773947887175626960699426438456382655370090748369934296474999389316334717699127421889816721511602392591677377678759026657582648354688447456509292302633971842316239774410380221303269351351929586256938787054867
c2_ = 64829024929257668640929285124747107162970460545535885047576569803424908055130477684809317765011143527867645692710091307694839524199204611328374569742391489915929451079830143261799375621377093290249652912850024319433129432676683899459510155157108727860920017105870104383111111395351496171846620163716404148070

# yafu -> find q
q = 791763770658839585424113

# find A, B
A = ( (s2-s1) * libnum.invmod((s1-s0), q) ) % q
B = ( s1 - A*s0 ) % q
print('A = %d' % A)
print('B = %d' % B)

# check A, B
assert ( A * s0 + B ) % q == s1
assert ( A * s1 + B ) % q == s2
assert ( A * s2 + B ) % q == s3
assert ( A * s3 + B ) % q == s4
assert ( pow(c1, A, p) * pow(g, B, p) ) % p == c1_ % p

# m ^ {A-1} % p
ma = ( pow(c2, A, p) * pow(h, B, p) * libnum.invmod(c2_, p) ) % p
print('ma = %d' % ma)

# AMM
def eth_root(x, e, p):
assert isPrime(p)
assert (p - 1) % e == 0
assert (p - 1) % (e**2) != 0

l = (p - 1) % (e**2) // e
a = -libnum.invmod(l, e) % e
return pow(x, (1 + a * (p - 1) // e) // e, p)

def findAllPRoot(p, e):
print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
start = time.time()
proot = set()
while len(proot) < e:
proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
end = time.time()
print("Finished in {} seconds.".format(end - start))
return proot

def findAllSolutions(mp, proot, cp, p, e):
print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
start = time.time()
all_mp = set()
for root in proot:
mp2 = mp * root % p
#print('debug -> %d' % pow(root, e3, p))
assert(pow(mp2, e, p) == cp)
all_mp.add(mp2)
end = time.time()
print("Finished in {} seconds.".format(end - start))
return all_mp

e = A-1
e2 = libnum.gcd(e, p-1)
m2 = eth_root(ma, e2, p)
e3 = e // e2
assert pow(m2, e2, p) == ma

proot = findAllPRoot(p, e2)
ms = findAllSolutions(m2, proot, ma, p, e2)
d2 = libnum.invmod(e3//2, p-1)
for m3 in ms:
if pow(m3, (p-1)//2, p) != 1: # QR
continue
m = pow(m3, (p+1)//4, p) # 2-root
m = pow(m, d2, p) # normal RSA
assert pow(m, e, p) == ma
flag = libnum.n2s(int(m))
#if b'{' in flag and b'}' in flag:
if b'flag' in flag:
print(flag)
# b'flag{19e9f185e6a680324cedd6e6d9382743}'

PS:代码跑了大概四分钟- -