ilove2025 crypto

(Updated: )

[Week1]

Basic Number theory

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import flag

def gift(m, prime):
    return pow(m, (prime + 1) // 2, prime)

m = bytes_to_long(flag)
p = getPrime(256)
q = getPrime(256)

print(f'p = {p}')
print(f'q = {q}')
print(f'gift1 = {gift(m, p)}')
print(f'gift2 = {gift(m, q)}')

# p = 71380997427449345634700552609577271052193856747526826598031269184817312570231
# q = 65531748297495117965939047069388412545623909154912018722160805504300279801251
# gift1 = 40365143212042701723922505647865230754866250738391105510918441288000789123995
# gift2 = 10698628345523517254945893573969253712072344217500232111817321788145975103342
1
2
def gift(m, prime):
    return pow(m, (prime + 1) // 2, prime)

所以我们有

由二次剩余

然后我们可以中国剩余定理crt一下计算 exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from sage.all import *

p = 71380997427449345634700552609577271052193856747526826598031269184817312570231
q = 65531748297495117965939047069388412545623909154912018722160805504300279801251
g1 = 40365143212042701723922505647865230754866250738391105510918441288000789123995
g2 = 10698628345523517254945893573969253712072344217500232111817321788145975103342

for s1 in (1, -1):
    for s2 in (1, -1):
        a = (s1 * g1) % p   # m mod p 的候选： ±gift1 (模 p)
        b = (s2 * g2) % q   # m mod q 的候选： ±gift2 (模 q)
        m = crt([a, b], [p, q])  # 合并成 mod p*q 的唯一解
        flag = long_to_bytes(m)
        if b'flag{' in flag:
            print(flag)

beyondHex

1
2
这是什么东西？
807G6F429C7FA2200F46525G1350AB20G339D2GB7D8

17进制转字符 exp

1
2
3
4
5
6
7
8
9
10
11
s = "807G6F429C7FA2200F46525G1350AB20G339D2GB7D8"

table = {str(i): i for i in range(10)}
for i, ch in enumerate("ABCDEFG", start=10):
    table[ch] = i

v = 0
for ch in s:
    v = v * 17 + table[ch]

print(long_to_bytes(v))

certificate

手撕私钥，然后解高次dp攻击

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
dp=0x26b285848e6997fa01376059a8b4dff8d69c1aa4c5af399b8bb45515a378de45d85eed75bab5f22d39dc7c95c1a5186d18576c2f7d638acc21898469f728d3fb
n=0x009d034fa9ab29cabdcdff047e688e751704c756cbd2f38bd4f049a3a0889ea4cbffd006b58608d6a7f7c09835ca0abb1db23ad1ca223c54acf87e2dd823996fbfa5a58f272ae7a10c394aa0fe16fa8d4e31bb024bf1f93517c8c7e52fdaa876b58111b97fc66374d506e2be8dfaf94d6614307ee8b10d93fdc1c165c7563d03bd
e=0x00beed55cdffde31057bea5a58a3684d5fbed81f03d53fa28bb658b32de4535c8d
c=82404436498466895324733436901056359489189960512493202570903960333247277400247388969097533191635462377037232768074464944681385506170855774688613792302290304494481765906529480985984818897269069587516233500512849282866396228645039453616712857020451120948641770106851301755195757766245239907077580562163260112662
a = 2
p = GCD(pow(a, e*dp, n) - a, n)
q = n // p
d = inverse(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))

two Es

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

p, q = getPrime(512), getPrime(512)
n = p * q

e1 = random.getrandbits(32)
e2 = random.getrandbits(32)

m = bytes_to_long(flag)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f'{n = }')
print(f'{e1 = }')
print(f'{e2 = }')
print(f'{c1 = }')
print(f'{c2 = }')

'''
n = 118951231851047571559217335117170383889369241506334435506974203511684612137655707364175506626353185266191175920454931743776877868558249224244622243762576178613428854425451444084313631798543697941971483572795632393388563520060136915983419489153783614798844426447471675798105689571205618922034550157013396634443
e1 = 2819786085
e2 = 4203935931
c1 = 104852820628577684483432698430994392212341947538062367608937715761740532036933756841425619664673877530891898779701009843985308556306656168566466318961463247186202599188026358282735716902987474154862267239716349298652942506512193240265260314062483869461033708176350145497191865168924825426478400584516421567974
c2 = 43118977673121220602933248973628727040318421596869003196014836853751584691920445952955467668612608693138227541764934104815818143729167823177291260165694321278079072309885687887255739841571920269405948846600660240154954071184064262133096801059918060973055211029726526524241753473771587909852399763354060832968
'''

共模攻击再开方 exp

1
2
3
4
5
6
7
8
9
10
11
n = 118951231851047571559217335117170383889369241506334435506974203511684612137655707364175506626353185266191175920454931743776877868558249224244622243762576178613428854425451444084313631798543697941971483572795632393388563520060136915983419489153783614798844426447471675798105689571205618922034550157013396634443
e1 = 2819786085
e2 = 4203935931
c1 = 104852820628577684483432698430994392212341947538062367608937715761740532036933756841425619664673877530891898779701009843985308556306656168566466318961463247186202599188026358282735716902987474154862267239716349298652942506512193240265260314062483869461033708176350145497191865168924825426478400584516421567974
c2 = 43118977673121220602933248973628727040318421596869003196014836853751584691920445952955467668612608693138227541764934104815818143729167823177291260165694321278079072309885687887255739841571920269405948846600660240154954071184064262133096801059918060973055211029726526524241753473771587909852399763354060832968
from Crypto.Util.number import *
import gmpy2
s,x,y = gmpy2.gcdext(e1,e2)
m = (pow(c1,x,n)*pow(c2,y,n))%n
#print(s)
print(long_to_bytes(gmpy2.iroot(m,s)[0]))

xorRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from secret import flag

p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
p_q = p ^ q

print(f'{n = }')
print(f'{e = }')
print(f'{c = }')
print(f'{p_q = }')

'''
n = 18061840786617912438996345214060567122008006566608565470922708255493870675991346333993136865435336505071047681829600696007854811200192979026938621307808394735367086257150823868393502421947362103403305323343329530015886676141404847528567199164203106041887980250901224907217271412495658238000428155863230216487699143138174899315041844320680520430921010039515451825289303532974354096690654604842256150621697967106463329359391655215554171614421198047559849727235032270127681416682155240317343037276968357231651722266548626117109961613350614054537118394055824940789414473424585411579459583308685751324937629321503890169493
e = 65537
c = 17953801553187442264071031639061239403375267544951822039441227630063465978993165328404783737755442118967031318698748459837999730471765908918892704038188635488634468552787554559846820727286284092716064629914340869208385181357615817945878013584555521801850998319665267313161882027213027139165137714815505996438717880253578538572193138954426764798279057176765746717949395519605845713927900919261836299232964938356193758253134547047068462259994112344727081440167173365263585740454211244943993795874099027593823941471126840495765154866313478322190748184566075583279428244873773602323938633975628368752872219283896862671494
p_q = 88775678961253172728085584203578801290397779093162231659217341400681830680568426254559677076410830059833478580229352545860384843730990300398061904514493264881401520881423698800064247530838838305224202665605992991627155227589402516343855527142200730379513934493657380099647739065365753038212480664586174926100
'''

pq剪枝 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
def get_pq(n, x):
    a = [0]
    b = [0]
    maskx = 1
    maskn = 2
    for i in range(1024):
        xbit = (x & maskx) >> i
        nbit = n % maskn
        t_a = []
        t_b = []
        for j in range(len(a)):
            for aa in range(2):
                for bb in range(2):
                    if aa ^ bb == xbit:
                        tmp2 = n % maskn
                        tmp1 = (aa * maskn // 2 + a[j]) * (bb * maskn // 2 + b[j]) % maskn
                        if tmp1 == tmp2:
                            t_a.append(aa * maskn // 2 + a[j])
                            t_b.append(bb * maskn // 2 + b[j])
        maskx *= 2
        maskn *= 2
        a = t_a
        b = t_b
    for a1, b1 in zip(a, b):
        if a1 * b1 == n:
            return a1, b1
n = 18061840786617912438996345214060567122008006566608565470922708255493870675991346333993136865435336505071047681829600696007854811200192979026938621307808394735367086257150823868393502421947362103403305323343329530015886676141404847528567199164203106041887980250901224907217271412495658238000428155863230216487699143138174899315041844320680520430921010039515451825289303532974354096690654604842256150621697967106463329359391655215554171614421198047559849727235032270127681416682155240317343037276968357231651722266548626117109961613350614054537118394055824940789414473424585411579459583308685751324937629321503890169493
e = 65537
c = 17953801553187442264071031639061239403375267544951822039441227630063465978993165328404783737755442118967031318698748459837999730471765908918892704038188635488634468552787554559846820727286284092716064629914340869208385181357615817945878013584555521801850998319665267313161882027213027139165137714815505996438717880253578538572193138954426764798279057176765746717949395519605845713927900919261836299232964938356193758253134547047068462259994112344727081440167173365263585740454211244943993795874099027593823941471126840495765154866313478322190748184566075583279428244873773602323938633975628368752872219283896862671494
p_q = 88775678961253172728085584203578801290397779093162231659217341400681830680568426254559677076410830059833478580229352545860384843730990300398061904514493264881401520881423698800064247530838838305224202665605992991627155227589402516343855527142200730379513934493657380099647739065365753038212480664586174926100
leak= p_q
from Crypto.Util.number import *
p, q = get_pq(n, leak)
print(f'p = {p}')
print(f'q = {q}')
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

Strange Machine

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
from secret import msg_len, offset, plaintext
from Crypto.Util.number import long_to_bytes
from random import randbytes
from base64 import b64encode
from pwn import xor
import os

flag = os.getenv('FLAG')


def banner():
    print("你发现了一个奇怪的机器，它对你的消息进行了加密。")
    print("你截获了这个机器第一次的密文，同时可以继续使用该机器进行加密。")
    print("注意:所有密文输出都经过 base64 编码，方便你复制分析。\n")


def menu():
    print(f"1. 加密消息")
    print(f"2. 校验明文是否正确")
    print(f"3. 退出")


class Key:
    def __init__(self):
        self.seed = randbytes(msg_len)

    def generate(self):
        self.seed = self.seed[offset:] + self.seed[:offset]
        return self.seed


def pad(msg):
    pad_len = msg_len - len(msg)
    return msg + pad_len * long_to_bytes(pad_len)


def encrypt(msg, key):
    cipher = xor(pad(msg), key)
    return b64encode(cipher)


def main():
    banner()
    key = Key()
    cur_key = key.generate()
    cipher1 = encrypt(plaintext, cur_key)
    print(f'[*] 首次密文(base64):{cipher1}\n')
    while True:
        try:
            menu()
            choice = int(input(f"[?] 请输入你的选择:"))
            if choice == 1:
                msg = input(f"[?] 请输入要加密的消息(长度小于等于{msg_len}): ").encode()
                if len(msg) > msg_len:
                    print(f"[!] 输入消息过长，最长为 {msg_len} 字节\n")
                    continue

                cur_key = key.generate()
                cipher = encrypt(msg, cur_key)

                print(f"[*] 你的消息已加密(密文): {cipher}\n")
                continue

            if choice == 2:
                msg = input(f"[?] 请输入待校验的明文: ").encode()
                if msg == plaintext:
                    print(f"[*] 这是你的flag: {flag}\n")
                    break
                print("[!] 校验错误!\n")
                continue

            if choice == 3:
                print("再见~\n")
                break

            print("[!] 无效输入\n")
        except Exception:
            print("[!] 出现错误!\n")
            break


if __name__ == "__main__":
    main()

没看，ai秒了 exp

1

[Week2]

Furious BlackCopper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from secret import flag

p,q,r = [getPrime(1024) for _ in range(3)]
n = p*q*r
e = 65537

c = pow(bytes_to_long(flag),e,n)

print(f"n = {n}")
print(f"c = {c}")
print(f"hint1 = {p % (1<<20)}")
print(f"hint2 = {(p>>30) % (2**800)}")

'''
n = 2319000650261946023915014206488070911640109367250016568220614383532952214807761334558144208472659838958984936464737359601178199471300591809378861719725166071293490337849460977334088817981122030848611809302595213167700327022424485330558133803551058332751191386670140430591951239225137235559261920346492292931776544999900411323158373028200548312764177981464990638015835702492874152704590840093556205478901618714235042276132193643820011286079020600820330604377153242537768363399127325275405368576324108320705517778045911592243192206637554003492442058363346021771705706076757889394174566970697156452713746460116694890476180599323974313009004900787705445305524094335957604088726075970520060978159945766075715871582835253817257735855172650619000718520587778706871170904747089132157549968207256556609060157681221165756365791620541073993550257247751386345594088623340417061806929245714999520220438960372195265546782502907343855788577
c = 1312431694904328111780426560035505882847885739731876317571257464906825734204933816113372504839088670643195989177569949377517123438201824279247608568699561057482330558039296008315782977478101848813741726654243732783839391998886721404635297928977792605627502180127696927378119466225798392853417088954570631565570973202717529604340075835044597519741996534553925543479235889306624531207327427624103988434939518732341796383732086485277180212113415284650071149267580793350758438950453934211274178830302236693064826616375397152045594336577917485934307703262074980594657132021858937328828017831874934945555874286196775661905842629738284617715824957593409581994376032525637671092419057427541956714584967278598190421273604293216212080790867530792388678597948920872325098486444223785108892158072625104934781926821974205890499552986515486164864944654160208151684128390420512040349571993995324224935664722188207527753890311873774929256151
hint1 = 104933
hint2 = 249231134914993957949482231198967609483717484780914014047312121163289039867757770164810674646280242374849088943758284579101792336244843385393432327534356753329591313697147372369033868132522997567291163165320430574331836011085519584900949698
'''

已知低20位和中间800位p，仍有10位和194位p未知 爆破10位然后打高位194位copper即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 2319000650261946023915014206488070911640109367250016568220614383532952214807761334558144208472659838958984936464737359601178199471300591809378861719725166071293490337849460977334088817981122030848611809302595213167700327022424485330558133803551058332751191386670140430591951239225137235559261920346492292931776544999900411323158373028200548312764177981464990638015835702492874152704590840093556205478901618714235042276132193643820011286079020600820330604377153242537768363399127325275405368576324108320705517778045911592243192206637554003492442058363346021771705706076757889394174566970697156452713746460116694890476180599323974313009004900787705445305524094335957604088726075970520060978159945766075715871582835253817257735855172650619000718520587778706871170904747089132157549968207256556609060157681221165756365791620541073993550257247751386345594088623340417061806929245714999520220438960372195265546782502907343855788577
c = 1312431694904328111780426560035505882847885739731876317571257464906825734204933816113372504839088670643195989177569949377517123438201824279247608568699561057482330558039296008315782977478101848813741726654243732783839391998886721404635297928977792605627502180127696927378119466225798392853417088954570631565570973202717529604340075835044597519741996534553925543479235889306624531207327427624103988434939518732341796383732086485277180212113415284650071149267580793350758438950453934211274178830302236693064826616375397152045594336577917485934307703262074980594657132021858937328828017831874934945555874286196775661905842629738284617715824957593409581994376032525637671092419057427541956714584967278598190421273604293216212080790867530792388678597948920872325098486444223785108892158072625104934781926821974205890499552986515486164864944654160208151684128390420512040349571993995324224935664722188207527753890311873774929256151
hint1 = 104933
hint2 = 249231134914993957949482231198967609483717484780914014047312121163289039867757770164810674646280242374849088943758284579101792336244843385393432327534356753329591313697147372369033868132522997567291163165320430574331836011085519584900949698

from Crypto.Util.number import *
from tqdm import trange
PR.<x> = PolynomialRing(Zmod(n))
for i in trange(2**10):
    lower = hint1 + (i<<20)
    p_lower = (hint2<<30) + lower
    f = p_lower + x*2**830
    f = f.monic()
    res = f.small_roots(X=2**194, beta=0.33,epsilon=0.05)
    if res != []:
        p=(int(res[0]))*2**830 + p_lower
        print(p)
        d=inverse(e,p-1)
        m=pow(c,d,p)
        print(long_to_bytes(m))

strange random

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
from Crypto.Util.number import *
import random
from sympy import prime
def sssstranger(p,q):
    n = p*q
    list=[]
    for i in range(312):
        x=random.getrandbits(32)
        list.append(x)
    print(list)
    return n

p=getStrongPrime(512)
q=getStrongPrime(512)
r=getStrongPrime(512)
n1=sssstranger(p,q)
print(n1)
n2=sssstranger(q,r)
print(n2)
e=random.getrandbits(32)
m=bytes_to_long(b"xxx")
c=pow(m,e,n1*n2//q)
print(c)
'''
'''

求一个GCD能拿到q，p，r 给了624组数据，可以直接用RandCrack预测得到e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import random
from randcrack import RandCrack
from tqdm import trange
import gmpy2
from sympy import *
q = GCD(n1, n2)
p = n1 // q
r = n2 // q
'''print(f"p = {p}")
print(f"q = {q}")
print(f"r = {r}")'''
N = p * q * r 
phi = (p - 1) * (q - 1) * (r - 1)
#print(f"phi = {phi}")
rc = RandCrack()
list=list1+list2
for i in trange(624):
    rc.submit(list[i])
e = rc.predict_getrandbits(32)

然后测一下数据，发现e和phi不互素，在模q下有限域开根 exp

1
2
3
d=inverse(e//2, (q-1)//2)
m=pow(c,d,q)
print(long_to_bytes(nthroot_mod(m,2,q)))

或者写成

1
2
3
4
5
6
phi1=q-1
a,b,o=gmpy2.gcdext(e,phi1)
#print(a,b,o)

mg=pow(c,b,q)
print(long_to_bytes(nthroot_mod(mg,a,q)))

Common RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from secret import flag

assert flag.startswith(b'flag{') and flag.endswith(b'}')

p, q = getPrime(512), getPrime(512)
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)

hint = pow(p + q, 2, n)

print(f'{n = }')
print(f'{e = }')
print(f'{c = }')
print(f'{hint = }')

'''
n = 131597024257614620869648421307952022599943625170798058722475560465555374754170467986433278540604131619940641178519954230167502146438244308999511105433219427638803460889093328223802388178143540560813587991639442439109510325931982801296494725966519902673302205827914999084293810023067168509012158443748031939483
e = 65537
c = 1968659140793648429069472000786965200510587960406184785982668854732724642287423003255222009970017202179772168410459767605874195614574533370563277818681668876342943583147204497260995173839443989636764614809399895977498001560095317260220383552929292480197409615426208803132661827666690467265686165715909909838
hint = 8041845809205494984282719083536906169105876887210623661715566866580197885950852556859414098121226785749033039450259965513505083753685569890927709072642971188655408152663342066047346862975209503093968807589977151718256296935551857116746970823854584764670720138775077146982697233376686489502015164620786724
'''

先解一个方程拿到p和q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def hint_solve(n, hint):
    for k in trange(2, 400):
        C = hint + k * n
        D = C*C - 4*n*n
        if D < 0:
            continue
        r = isqrt(D)
        if r*r != D:
            continue
        if (C + r) % 2 != 0:
            continue
        x_root = (C + r) // 2
        p = isqrt(x_root)
        if p*p == x_root and n % p == 0:
            q = n // p
            return p, q

result= hint_solve(n, hint)
p, q = result
print(f"p = {p}")
print(f"q = {q}")

然后发现e和phi不互素，解amm

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
# 设置模数
def GF(a):
    global p
    p = a

# 乘法取模
def g(a, b):
    global p
    return pow(a, b, p)

def AMM(x, e, p):
    GF(p)
    y = random.randint(1, p - 1)
    while g(y, (p - 1) // e) == 1:
        y = random.randint(1, p - 1)
        print(y)
    # p-1 = e^t*s
    t = 1
    s = 0
    while p % e == 0:
        t += 1
        print(t)
    s = p // (e ** t)
    # s|ralpha-1
    k = 1
    while ((s * k + 1) % e != 0):
        k += 1
    alpha = (s * k + 1) // e
    # 计算a = y^s b = x^s h =1
    # h为e次非剩余部分的积
    a = g(y, (e ** (t - 1)) * s)
    b = g(x, e * alpha - 1)
    c = g(y, s)
    h = 1
    #
    for i in range(1, t - 1):
        d = g(b, e ** (t - 1 - i))
        if d == 1:
            j = 0
        else:
            j = -math.log(d, a)
        b = b * (g(g(c, e), j))
        h = h * g(c, j)
        c = g(c, e)
    # return (g(x, alpha * h)) % p
    root = (g(x, alpha * h)) % p
    roots = set()
    for i in range(e):
        mp2 = root * g(a, i) % p
        # assert(g(mp2, e) == x)
        roots.add(mp2)
    return roots

def check(m):
    if 'flag' in m:
        print(m)
        return True
    else:
        return False

mps = AMM(c, e, q)

for mpp in mps:
    solution = str(long_to_bytes(mpp))
    if check(solution):
        print(solution)

baby Elgamal

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

p = getPrime(512)
g = random.randint(2, p - 2)
x = random.getrandbits(32)
y = pow(g, x, p)

print(f'{p = }')
print(f'{g = }')
print(f'{y = }')

k = random.randint(2, p - 2)
m = bytes_to_long(flag)
c1 = pow(g, k, p)
c2 = m ^ pow(y, k, p)

print(f'{c1 = }')
print(f'{c2 = }')

'''
p = 10560464175631160709999383504944939280267067560378620626979040921315467798501630079655340663547895515812021911470304483075907600549587171358369476255124337
g = 5572911063894340974483734192541353411838868965361107134612465011908061780180242348779533324820127053271574799429894984956163372524626786431177292215721384
y = 2551976503972625362405323290468587787679347326045114894085518452627208422960190509410833573983206966744456211220857302778318665690771595372276106771043208
c1 = 1205617983130100879228661072981675725569095797251301660744333997969095366993470887762473783053252549837619991656838026541987751368433948599410216526314464
c2 = 135410793997875487972298785237681131478761447205213610635842285010164308038301697054176371628605014267489864238137735560888444688177201474949707954751577
'''

Elgamal算法＋BSGS，但是sage的bsgs不知道为啥32位的都能跑炸掉16G内存

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

# 已知参数
p = 10560464175631160709999383504944939280267067560378620626979040921315467798501630079655340663547895515812021911470304483075907600549587171358369476255124337
g = 5572911063894340974483734192541353411838868965361107134612465011908061780180242348779533324820127053271574799429894984956163372524626786431177292215721384
y = 2551976503972625362405323290468587787679347326045114894085518452627208422960190509410833573983206966744456211220857302778318665690771595372276106771043208
c1 = 1205617983130100879228661072981675725569095797251301660744333997969095366993470887762473783053252549837619991656838026541987751368433948599410216526314464
c2 = 135410793997875487972298785237681131478761447205213610635842285010164308038301697054176371628605014267489864238137735560888444688177201474949707954751577

def bsgs_small_exponent(g, y, p, N):
    """
    使用BSGS算法在 [0, N] 范围内寻找 x
    使得 y = g^x (mod p)
    """
    B = math.ceil(math.sqrt(N))
    print(f"[+] 搜索范围 N = {N}")
    print(f"[+] 步长 B = {B}")
    # 预计算 g 的逆元
    g_inv = pow(g, -1, p)
    baby_steps = {}
    current_baby = y
    for j in range(B):
        baby_steps[current_baby] = j
        current_baby = (current_baby * g_inv) % p
    # Giant steps: 计算 (g^B)^i
    giant_step_base = pow(g, B, p)
    current_giant = 1  # 对应 i = 0 
    for i in range(B):
        if current_giant in baby_steps:
            j = baby_steps[current_giant]
            x = i * B + j
            if x < N:
                print(f"[+] 找到碰撞! i = {i}, j = {j}")
                return x
        current_giant = (current_giant * giant_step_base) % p      
    return None
N = 2**32
x = bsgs_small_exponent(g, y, p, N)
if x:
    print(f"\n[SUCCESS] 成功找到私钥 x: {x}")
    
    # 2. 用 x 解密
    # 共享密钥 S = (c1)^x mod p
    shared_key = pow(c1, x, p)

    m_long = c2 ^ shared_key
    
    # 3. 转换回 flag
    flag = long_to_bytes(m_long)
    print(f"[FLAG] 解密得到的 Flag: {flag.decode()}")
else:
    print("\n[FAILURE] 未能找到私钥 x。")

findKey in middle

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
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from random import getrandbits
from Crypto.Cipher import AES
from hashlib import sha256
from secret import flag

def f(x, y):
    return (pow(3, x, p) * pow(5, y, p)) % p

def split_key(key):
    x, y = getPrime(16), getPrime(16)
    assert x * y > key
    k1, k2 = key % x, key % y
    return k1, k2, x, y

def aes_encrypt(key, flag):
    aes = AES.new(key, AES.MODE_ECB)
    return aes.encrypt(pad(flag, 16))   

p = 1000000007

key = getrandbits(32)
k1, k2, mod1, mod2 = split_key(key)
x = f(k1, k2)

cipher = aes_encrypt(sha256(long_to_bytes(key)).digest()[:16], flag)

print(f'x = {x}')
print(f'mod = {(mod1, mod2)}')
print(f'cipher = {cipher}')
# x = 367608838
# mod = (41813, 53149)
# cipher = b'\x98\xfd\xa8\x05R\x17\xb6y%"\t\xb4\xd7\x82\xc4\'\x0b8\x14q\xff.\x13\xfb\xa4D\xb4\xde-\xd5c\xd6M\x13\x90\xdb\x81\xbd\xd0c>A\xbc)\xd0U\x7fW'

中间相遇攻击+crt x = 3x1 ⋅ 5x2 (mod  p) 移项x1到左边，变为 3k1 ≡ x ⋅ (5k2)−1 (mod  p) 然后左边枚举k1进行建字典，右边同样枚举k2然后查字典验证拿到k1和k2 最后用函数恢复 官方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
from sympy.ntheory.modular import crt
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from tqdm import tqdm

p = 1000000007
f = 367608838
mod = (41813, 53149)
cipher = b'\x98\xfd\xa8\x05R\x17\xb6y%"\t\xb4\xd7\x82\xc4\'\x0b8\x14q\xff.\x13\xfb\xa4D\xb4\xde-\xd5c\xd6M\x13\x90\xdb\x81\xbd\xd0c>A\xbc)\xd0U\x7fW'

dic = {}
for x in tqdm(range(mod[0])):
    tmp = pow(3, x, p)
    dic[tmp] = x


ans = []
for y in tqdm(range(mod[1])):
    tmp = f * inverse(pow(5, y, p), p) % p
    if tmp in dic.keys(): 
        
        k1 = dic[tmp]
        ans.append((k1, y))

for val in ans:
    try:
        key, _ = crt(mod, val)
        key = sha256(long_to_bytes(key)).digest()[:16]
        aes = AES.new(key, AES.MODE_ECB)
        print(aes.decrypt(cipher))
    except:
        pass