虽然没打但是拿到了题 -

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

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

首先题目只给了pp，而qq是必会用到的，所以会选择先提取qq。由keygen可以看出q只有8080位的大小，且是群阶（p−1p-1）的因子（因为gq≡1(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

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

(si+1−si)≡A∗(si−si−1)(modq)A≡(si+1−si)∗(si−si−1)−1(modq)B≡(si−A∗si−1)(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 = 12742153496769814072597，B=3035433788765894539799B = 3035433788765894539799；

剩下还没用到的就是C1C_1、C2C_2和C1′C_1'、C2′C_2'，由rand可知r′≡Ar+B(modq)r' \equiv Ar+B \pmod q，分别代进C1′C_1'和C2′C_2'里，可得：

C1′≡gr′≡gAr+B≡(gr)AgB≡C1AgB(modp)C2′≡mhr′≡mhAr+B≡m−(A−1)(mgr)AgB≡m−(A−1)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

C1′C_1'那个其实作用不大（可以用来做个assert），C2′C_2'那个换个顺序就是：

mA≡mA−1≡C2AhB(C2′)−1(modp)m_A \equiv m^{A-1} \equiv C_2^Ah^B(C_2')^{-1} \pmod p

令e=A−1e=A-1的话，就是个“普通”的RSA解密了。但是，ee与φ=p−1\varphi=p-1是不互素的（按RSA密钥生成的要求应该要是互素的，不然不能求出dd），就不能通过模φ\varphi求逆的方法解出mm，而需要用AMM（Adleman-Manders-Miller）的方法求，具体做法我直接Copy了Arpe1s和Furutsuki的代码；有一点要注意的是，当ee很大时直接调用AMM是很慢的（甚至不可能算出来），这时可以把ee分解一下，拆成e=e1e2e=e_1e_2，其中gcd(e1,φ)=1gcd(e_1, \varphi)=1，对e2e2和mAm_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是模44余33的，所以可以通过计算mip+14(modp)m_i^{\frac{p+1}{4}} \pmod p直接开方，而不用再求一次AMM。

最终代码（代码中其实是分解成e=e3∗e2∗2e=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：代码跑了大概四分钟- -