SHCTF--crypto复现

crypto
赛题
发布日期:   2024-12-01

SHCTF2023

[WEEK1]Crypto_Checkin

1
QZZ|KQbjRRS8QZRQdCYwR4_DoQ7~jyO>0t4R4__aQZQ9|Rz+k_Q!r#mR90+NR4_4NR%>ipO>0s{R90|SQhHKhRz+k^S8Q5JS5|OUQZO}CQfp*dS8P&9R8>k?QZYthRz+k_O>0#>

base85(IPV6) -> base64 -> base32 -> base16

最后flag为

1
flag{Th1s_1s_B4s3_3nc0d3}

[WEEK1]立正

1
wl hgrfhg 4gNUx4NgQgEUb4NC64NHxZLg636V6CDBiDNUHw8HkapH :jdoi vl vlkw  ~xrb wd nrrT Y:

密文中间 4gNUx4NgQgEUb4NC64NHxZLg636V6CDBiDNUHw8HkapH 这一串应该是 Base64 编码后的字符串，直接解码不行，需要预处理。发现hgrfhg 可能是单词 decode，尝试凯撒发现不行，但是发现 Reverse 后可以通过凯撒得到单词 decode：

对大写字母，小写字母还有数字分别用不同值进行ROT解密，之后中间部分base64解密即可。

cyberchef的参数

1
2
3
4
5
6
7
Reverse('Character')

ROT13(true,false,false,23)  

ROT13(false,true,false,18)

ROT13(false,false,true,5)

最后flag为

1
flag{Y0U_MU57_5t4nd_uP_r1gHt_n0W}

残缺的md5

1
2
3
苑晴在路边捡到了一张纸条，上面有一串字符串：KCLWG?K8M9O3?DE?84S9
问号是被污染的部分，纸条的背面写着被污染的地方为大写字母，还给了这串字符串的md5码值：F0AF????B1F463????F7AE???B2AC4E6
请提交完整的md5码值并用flag{}包裹提交

爆破md5

exp:

1
2
3
4
5
6
7
8
9
10
11
12
import hashlib

for i in range(65, 91):
    for j in range(65, 91):
        for k in range(65, 91):
            str = "KCLWG" + chr(i) + "K8M9O3" + chr(j) + "DE" + chr(k) + "84S9"
            md5obj = hashlib.md5()
            md5obj.update(str.encode("utf-8"))
            hexmd5 = md5obj.hexdigest()
            if hexmd5[0:4].upper() == "F0AF":
                print("原字符串为:" + str)
                print("md5字符串为:" + hexmd5.upper())

运行得到

最后flag为

1
flag{F0AF1443B1F463EAFFF7AEBB8B2AC4E6}

[WEEK1]凯撒大帝

1
pvkq{mredsrkyxkx}

凯撒解密，key=10

最后flag为

1
flag{chutihaonan}

[WEEK1]进制

1
2
好熟悉的进制，但不知道加密了几层
3636366336313637376236313638363636623661366336383662363136383764

赛博厨子一把梭

最后flag为

1
flag{ahfkjlhkah}

[WEEK1]okk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook? Ook. Ook? Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook! Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook? Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook! Ook! Ook! Ook!
Ook! Ook! Ook? Ook. Ook? Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook? Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook. Ook? Ook! Ook. Ook? Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook!
Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook? Ook. Ook? Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook. Ook. Ook. Ook! Ook. Ook. Ook. Ook! Ook. Ook. Ook. Ook! Ook. Ook. Ook.
Ook! Ook. Ook. Ook. Ook! Ook. Ook. Ook. Ook! Ook. Ook. Ook. Ook! Ook. Ook.
Ook. Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook.
Ook? Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook?
Ook.

ook在线解密

[Brainfuck/Ook! Obfuscation/Encoding splitbrain.org]

最后flag为

1
flag{123456789}

[WEEK1]熊斐特

1
2
熊斐特博士发现了一种新的密码。
uozt{zgyzhs xrksvi}

埃特巴什码解码

最后flag为

1
flag{atbash cipher}

[WEEK1]黑暗之歌

1
2
3
密文：

⠴⡰⡭⡳⠴⡰⡭⡰⡷⡲⡢⡩⡭⡡⠯⡩⡭⡡⡺⡩⡭⡡⠳⡩⡭⡡⡺⡩⡭⡡⡶⡩⡭⡡⡶⡩⡭⡡⡲⡩⡭⡡⡺⡩⡭⡡⠯⡩⡧⡊⡢⡩⡭⡡⠯⡩⡭⡡⡺⡃⡰⠫⡋⡚⡲⡍⡋⡮⠴⡰⡭⡶⡷⡲⡢⡩⡧⡊⡢⡃⡴⡵⡋⡁⡬⡵⡋⡁⡬⡵⡋⡁⡬⡳⡋⠲⠴⡯⡃⡗⠴⡰⡭⡴⠴⡰⡭⡶⡷⡲⡢⡩⡧⡊⡢⡩⡭⡡⡺⡩⡭⡡⡺⡩⡭⡡⠳⡩⡧⡊⡢⡩⡭⡡⠯⡩⡧⡊⡢⡃⡴⡵⡋⡚⡱⠫⡋⡚⡱⠫⡋⡚⡲⠵⠲⡺⠰⠽

盲文点字解密

http://www.atoolbox.net/Tool.php?Id=837

base64解密

音符解密

文本加密为音乐符号,可自设密码|文本在线加密解密工具

最后flag为

1
flag{b2cc-9091-8a29}

[WEEK1]佛说：只能四天

1
陀即我叻我莊如亦婆愍降吽兜哉念色夷嚩喼哉宣宣羅僧慧喼喃塞修菩哉菩哉吶宣囉哆念隸是喃哉嚩是念哉我嘚般訶尊是是闍哉訶咤聞訶念兜喼哉是般哉尊波祗迦念彌哆塞咤寂祗蜜劫塞迦劫諸隸菩哉缽即哉耨若夷夷吽斯空須囉諦諸須塞缽是若咤劫若哉嚴莊須哉闍須叻耨降菩哉般哆哉耨是叻色迦羅缽哉吽哉降聞叻彌蜜彌所斯嚴薩所陀波婆喃夷愍所囉哉叻伏空般耨囉隸劫般夷降嘇慧哆摩我念羅哉摩修叻喼羅般須吶囉尊伏斯若喼羅

新佛曰论禅解密

新约佛论禅/佛曰加密 - 萌研社 - PcMoe!

社会核心价值观解密

CTF在线工具-在线核心价值观编码|核心价值观编码算法|Core Values Encoder

栅栏解密 key=4

栅栏密码在线加密解密 - 千千秀字

凯撒解密 key=3

凯撒密码在线加密解密 - 千千秀字

hex解密

最后flag为

1
flag{mission_accomplish}

[WEEK1]迷雾重重

1
2
3
4
5
6
7
8
题目描述：

morse？ASCII？


密文：

0010 0100 01 110 1111011 11 111 010 000 0 001101 00 000 001101 0001 0 010 1011 001101 0010 001 10 1111101

将0替换为. 将1替换为- 摩斯解密

最后flag为

1
flag{MORSE_IS_VERY_FUN}

[WEEK1]难言的遗憾

1
2
3
4
5
6
7
8
题目描述：
我们本可以早些进入信息化时代的，但是清政府拒不采纳那份编码规则。 （注：flag为中文，使用flag{}包裹提交）



密文：

000111310008133175592422205314327609650071810649

中文电码解密

最后flag为

1
flag{一天不学高数我就魂身难受}

[WEEK1]小兔子可爱捏

1
2
3
4
5
6
7
8
9
题目描述：宇宙的终极答案是什么？





U2FsdGVkX1/lKCKZm7Nw9xHLMrKHsbGQuFJU5QeUdASq3Ulcrcv9

你可能会需要一把钥匙，钥匙就是问题的答案。

搜索得知“宇宙的终极答案”为42，rabbit解密

Rabbit加密-Rabbit解密-在线Rabbit加密解密工具

最后flag为

1
flag{i_love_technology}

[WEEK1]电信诈骗

1
2
3
你好，我是秦始皇，我并没有死，我得到了长生不老药，但是药效有副作用，现在才醒。我刚花了一年在互联网上了解现在的时代，现在我要利用我地宫第四行第七列的无敌兵马俑军队卷土重来，但是我需要启动资金，vivo50作为启动资金，待我横扫天下，封你为大将军，赏你黄金万两！

050f000a7e407151537802540b747176075178027552756d0256726262627c

题目描述里注意到第四行第七列，可以联想到rot47，vivo50猜测是xor

最后flag为

1
flag{Cr42y_7hursd4y_v1v0_5o!!!}

[WEEK1]what is m

1
2
3
4
5
6
7
from Crypto.Util.number import bytes_to_long
from secret import flag

m = bytes_to_long(flag)
print("m =",m)

# m = 7130439814059469468283453306474762597662200964569822450992947069270358633350825292519907651172662386623695614894328026733970950248860196582407906780557645747858488590328089601116815068447101

转字节

exp:

1
2
3
4
5
6
from Crypto.Util.number import *


m = 7130439814057443320243429681414325827764276336619224666345619443395537485957854189297932224912609723041581517677307856605461596899730610191483141925166742595935133698302588072550682167948413
flag=long_to_bytes(m)
print("flag =",flag)

运行得到flag

最后flag为

1
flag{TH3r3_ARe_5eveRaI_4LtERN4tIVe5_T0_7He_I0N9_t0_8ytEs_1UNction_soogOB4bBcE4}

[WEEK1]really_ez_rsa

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

e = 65537
m = b''

p = getPrime(128)
q = getPrime(128)
n = p * q
m = bytes_to_long(m)
c = pow(m, e, n)

print("p =", p)
print("q =", q)
print("c =", c)
print("e =", e)

# p = 217873395548207236847876059475581824463

# q = 185617189161086060278518214521453878483

# c = 6170206647205994850964798055359827998224330552323068751708721001188295410644

# e = 65537

rsa已知(p, q, e,c)，求m题型

exp:

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
from Crypto.Util.number import *
p=217873395548207236847876059475581824463
q=185617189161086060278518214521453878483
e=65537
c=6170206647205994850964798055359827998224330552323068751708721001188295410644

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,p*q)

print(long_to_bytes(m))

运行得到flag

最后flag为

1
flag{Y0ung_meiyou_xiaojj}

[WEEK2]XOR

1
2
3
4
n = 20810298530643139779725379335557687960281905096107101411585220918672653323875234344540342801651123667553812866458790076971583539529404583369246005781146655852295475940942005806084842620601383912513102861245275690036363402134681262533947475193408594967684453091957401932685922178406769578067946779033282889429596341714417295489842047781388337010440309434639274398589029236213499110100040841426995862849012466514170374143655264739023758914247116354182164550612494432327931655944868705959874670536031052370968354394583880324756639698871918124498442308334232127034553164826483441746719644515097123067550594588348951855987
c = 15294238831055894095745317706739204020319929545635634316996804750424242996533741450795483290384329104330090410419090776738963732127756947425265305276394058773237118310164375814515488333015347737716139073947021972607133348357843542310589577847859875065651579863803460777883480006078771792286205582765870786584904810922437581419555823588531402681156158991972023042592179567351862630979979989132957073962160946903567157184627177910380657091234027709595863061642453096671316307805667922247180282486325569430449985678954185611299166777141304330040782500340791721548519463552822293017606441987565074653579432972931432057376
e = 65537
p⊕q = 66138689143868607947630785415331461127626263390302506173955100963855136134289233949354345883327245336547595357625259526618623795152771487180400409991587378085305813144661971099363267511657121911410275002816755637490837422852032755234403225128695875574749525003296342076268760708900752562579555935703659615570

已知n, p ^ q, e, c，直接高低位爆破

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
import gmpy2
import libnum
n = 20810298530643139779725379335557687960281905096107101411585220918672653323875234344540342801651123667553812866458790076971583539529404583369246005781146655852295475940942005806084842620601383912513102861245275690036363402134681262533947475193408594967684453091957401932685922178406769578067946779033282889429596341714417295489842047781388337010440309434639274398589029236213499110100040841426995862849012466514170374143655264739023758914247116354182164550612494432327931655944868705959874670536031052370968354394583880324756639698871918124498442308334232127034553164826483441746719644515097123067550594588348951855987
x1 = 66138689143868607947630785415331461127626263390302506173955100963855136134289233949354345883327245336547595357625259526618623795152771487180400409991587378085305813144661971099363267511657121911410275002816755637490837422852032755234403225128695875574749525003296342076268760708900752562579555935703659615570
x1 = bin(x1)[2:].zfill(1024)
pre_sol = [(0, 0)]
for x in range(1024 - 1, -1, -1):
    cur_pow = pow(2, len(x1) - x - 1)
    cur_sol = []
    for p, q in pre_sol:
        for i in range(2):
            for j in range(2):
                if str((i + j) % 2) == x1[x]:
                    cur_p = p + i * cur_pow
                    cur_q = q + j * cur_pow
                    if cur_p * cur_q % pow(2, len(x1) - x) == n % pow(2, len(x1) - x):
                        cur_sol.append((cur_p, cur_q))
    pre_sol = cur_sol
for p, q in pre_sol:
    if p * q == n:
        print(p, q)
        break
e=65537
c=15294238831055894095745317706739204020319929545635634316996804750424242996533741450795483290384329104330090410419090776738963732127756947425265305276394058773237118310164375814515488333015347737716139073947021972607133348357843542310589577847859875065651579863803460777883480006078771792286205582765870786584904810922437581419555823588531402681156158991972023042592179567351862630979979989132957073962160946903567157184627177910380657091234027709595863061642453096671316307805667922247180282486325569430449985678954185611299166777141304330040782500340791721548519463552822293017606441987565074653579432972931432057376
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(libnum.n2s(int(m)))

运行得到flag

最后flag为

1
flag{7428fbd7-639b-11ee-b51b-64d69af3cb76}

[WEEK2]easymath

output.txt

1
[288530505749272642500730917886204398531, 63547143998110685331032679758907988154, 15151206512028268617888756820805603406, 268092204209244869520724955865278855216, 261067075335188593563542448889694952077, 138067838531633886698552659065694918861, 201319433320428898153580935653793106657]

task.py

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 *
from random import *
p = getPrime(128)
seed = randint(2, p - 1)

class prng:
    n = p
    a,b = [randint(2, p - 1) for _ in range(2)]
    def __init__(self,seed):
        self.state = seed
    def next(self):
        self.state = (self.state * self.a + self.b) % self.n
        return self.state

    
def main():
    gen = prng(seed)
    s = [seed]
    s.append(gen.next())
    s.append(gen.next())
    s.append(gen.next())
    s.append(gen.next())
    s.append(gen.next())
    s.append(gen.next())
    f = open("output.txt",'w')
    json.dump(s,f)
    f.close()
    flag = "flag{"+str(gen.next())+"}"
    return flag
main()

LCG，已知seed,但是不知道a,b,n

参考LCG | DexterJie’Blog

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

output = [288530505749272642500730917886204398531, 63547143998110685331032679758907988154, 15151206512028268617888756820805603406, 268092204209244869520724955865278855216, 261067075335188593563542448889694952077, 138067838531633886698552659065694918861, 201319433320428898153580935653793106657]
t = []
for i in range(1,len(output)):
    t.append(output[i]-output[i-1])

T = []
for i in range(1,len(t)-1):
    T.append(t[i+1]*t[i-1] - t[i]**2)

m = []
for i in range(len(T)-1):
    mm = gmpy2.gcd(T[i],T[i+1])
    if isPrime(mm):
        m.append(int(mm))
    else:
        for i in range(1,100):
            if isPrime(mm // i):
                mm = mm // i
                m.append(int(mm))
                break
print(m)

for i in m:
    if isPrime(i):
        a = gmpy2.invert(t[0],i) * t[1] % i
        b = output[1] - a*output[0] % i
        a_ = gmpy2.invert(a,i)

        seed = output[0]
        print("seed =",seed)
        for j in range(7):
            seed = (a * seed + b) % i
        flag = "flag{"+str(seed)+"}"
        print(flag)

运行得到flag

最后flag为

1
flag{302184756857257140159769321021979097116}

[WEEK2]ez_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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# from flag import flag
from Crypto.Util.number import getPrime, bytes_to_long
from math import prod
import libnum

with open("flag.txt","rb") as f:
    flag = f.read().strip()

m = int.from_bytes(flag[:19],"big")
m1 = int.from_bytes(flag[19:],"big")

e = 65537

primes = [getPrime(64) for i in range(32)]
n = prod(primes)
c = pow(m,e,n)
print("c =",c)
print("n =",n)

p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
e1 = 13
e2 = 15
n1 = p * q
c1 = pow(m1, e1, n1)
c2 = pow(m1, e2, n1)
print("n1 =", n1)
print("e1 =", e1)
print("c1 =", c1)
print("n2 =", n1)
print("e2 =", e2)
print("c2 =", c2)

# c = 28535916699190273475273097091422420145718978597126134891571109006456944397344856577421369324831702083810238921719657496747722337086131545474384253288151783029981352196506749672783866527948391034258269669654392993063423671431837882584570973320095601407578443348352802850496429240170710269529489900871208384711844617081275862971410246759090936379744946527813691945129059991795202769186014306943707223831130752782380563227353615164053563120572722464543812139164048342504963081408349934180883607554389607335607410546630525512019818062185681153477671373000186961748278118124044645584490544698827467815360888525822167
# n = 114107341297408283801468814470303963122122556489590451040619457052827864984505912502462030175984161431709841571908269123131659496812467145870607611968843929870716066046232009282431653653484798819370087696248364531531706249180822839879862098012984590503284615395588919199545142177727328844260380842155437987767067800740569616584597507776426572206990858918111272636507821551592564540694671795374831548677720629329358177802890287837056940407030212276399942462042866947423728888561392653713356355778914658317507319575084393752755452971007289968044006561357799908892371839922838486713582082980752194204224263283004373
# n1 = 21235204662158833223664424963408105101885570855652885953922511758363954474947609854216589644512813634294435585894296340005122907229365513346971631594453999584706013889403572150499529308966742992668850443386284277210686717652643585324255759216699733045642544284406720854291604837774882256435503827543483289606177965628162259184958789025311291796067574924595051311298594432767265114154138693108465671184854794167878031822162731921299518989845784744659944947091213703810190708463199067553747177712259911724424547999547534441790125049383068377243727588278432796727885216967953646999183906479537750330738956233695342750567
# e1 = 13
# c1 = 5640630966585093229374938575158853304507369792931959909038819773057666482368490365383634362421839045569190487785222799103423460816096797210546343809620912249021763787314569982909943181390882015170344954037813745251119237402775124991005154299085147091159741067430623420349690886728161235034687649593258746455165172528681627568611599473627285223154284756417744280966157271904828156564067870877521824545300153084830020169048653830385763172792698591998191641849931039720453035065355411394516308865955772746815765864888631258825704788352584540380169938419618543124830541663995097651872542381
# n2 = 21235204662158833223664424963408105101885570855652885953922511758363954474947609854216589644512813634294435585894296340005122907229365513346971631594453999584706013889403572150499529308966742992668850443386284277210686717652643585324255759216699733045642544284406720854291604837774882256435503827543483289606177965628162259184958789025311291796067574924595051311298594432767265114154138693108465671184854794167878031822162731921299518989845784744659944947091213703810190708463199067553747177712259911724424547999547534441790125049383068377243727588278432796727885216967953646999183906479537750330738956233695342750567
# e2 = 15
# c2 = 5481001445755770090420425478456880914921441486935672376394423326451811448703288166341447356603281843336826624725965666634194700496514262129376916108926167953996689011980280761368893884042609095616407660087448963015169181749124738976578495911295096014725354350167650232970262765851074146687931181216305972147994236689422572940877763047930111954798962097847426932730342258169023809341164876019161104439561164839132092594444017039073155506935768658830659965630065643619399324102814118128802834719820426253836317043818687888302054465994498115387703382090351794495827905499417861507007863378916334790750453883661675063377

flag被分成两段进行加密，将第一段的n分解后发现n是由多个素因数相乘得出的，phi_n为所有素因数分别减一后相乘之后正常解RSA得出flag前半段，再采用共模攻击解出后半段拼接得出完整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
import libnum
import gmpy2
n = 114107341297408283801468814470303963122122556489590451040619457052827864984505912502462030175984161431709841571908269123131659496812467145870607611968843929870716066046232009282431653653484798819370087696248364531531706249180822839879862098012984590503284615395588919199545142177727328844260380842155437987767067800740569616584597507776426572206990858918111272636507821551592564540694671795374831548677720629329358177802890287837056940407030212276399942462042866947423728888561392653713356355778914658317507319575084393752755452971007289968044006561357799908892371839922838486713582082980752194204224263283004373
phi_n = (17075632607344331131-1)*( 15774106340553595249-1)*( 11718181938374860349-1)*( 10621161426185076191-1)*( 13498192768855092449-1)*(13618885037077024279-1)*( 17088379813205887661-1)*( 11777892065426651999-1)*( 15616762946597906161-1)*( 16880270107514803247-1)*(10126802520926958821-1)*( 13428970346605599557-1)*( 10635881647150245973-1)*( 9723861249937499279-1)*( 11964584391817142269-1)*(15622487550947237203-1)*( 10100522426677320149-1)*( 14147604789494386003-1)*( 14198042938738648387-1)*( 10986943768724409089-1)*(10270880245559150279-1)*( 16651625235320957803-1)*( 16340211116882594287-1)*( 16946507762934111301-1)*( 10040612110882504553-1)*(9281508366366115669-1)*( 10436802938040427139-1)*( 11502613740816749197-1)*( 9356350172425710359-1)*( 12712357180113548549-1)*(10203735303764112277-1)*( 9261040693807289549-1)
e = 65537
c = 28535916699190273475273097091422420145718978597126134891571109006456944397344856577421369324831702083810238921719657496747722337086131545474384253288151783029981352196506749672783866527948391034258269669654392993063423671431837882584570973320095601407578443348352802850496429240170710269529489900871208384711844617081275862971410246759090936379744946527813691945129059991795202769186014306943707223831130752782380563227353615164053563120572722464543812139164048342504963081408349934180883607554389607335607410546630525512019818062185681153477671373000186961748278118124044645584490544698827467815360888525822167

d = gmpy2.invert(e, phi_n)
m = gmpy2.powmod(c, d, n)

n1 = 114107341297408283801468814470303963122122556489590451040619457052827864984505912502462030175984161431709841571908269123131659496812467145870607611968843929870716066046232009282431653653484798819370087696248364531531706249180822839879862098012984590503284615395588919199545142177727328844260380842155437987767067800740569616584597507776426572206990858918111272636507821551592564540694671795374831548677720629329358177802890287837056940407030212276399942462042866947423728888561392653713356355778914658317507319575084393752755452971007289968044006561357799908892371839922838486713582082980752194204224263283004373
e1 = 13
c1 = 5640630966585093229374938575158853304507369792931959909038819773057666482368490365383634362421839045569190487785222799103423460816096797210546343809620912249021763787314569982909943181390882015170344954037813745251119237402775124991005154299085147091159741067430623420349690886728161235034687649593258746455165172528681627568611599473627285223154284756417744280966157271904828156564067870877521824545300153084830020169048653830385763172792698591998191641849931039720453035065355411394516308865955772746815765864888631258825704788352584540380169938419618543124830541663995097651872542381
n2 = 21235204662158833223664424963408105101885570855652885953922511758363954474947609854216589644512813634294435585894296340005122907229365513346971631594453999584706013889403572150499529308966742992668850443386284277210686717652643585324255759216699733045642544284406720854291604837774882256435503827543483289606177965628162259184958789025311291796067574924595051311298594432767265114154138693108465671184854794167878031822162731921299518989845784744659944947091213703810190708463199067553747177712259911724424547999547534441790125049383068377243727588278432796727885216967953646999183906479537750330738956233695342750567
e2 = 15
c2 = 5481001445755770090420425478456880914921441486935672376394423326451811448703288166341447356603281843336826624725965666634194700496514262129376916108926167953996689011980280761368893884042609095616407660087448963015169181749124738976578495911295096014725354350167650232970262765851074146687931181216305972147994236689422572940877763047930111954798962097847426932730342258169023809341164876019161104439561164839132092594444017039073155506935768658830659965630065643619399324102814118128802834719820426253836317043818687888302054465994498115387703382090351794495827905499417861507007863378916334790750453883661675063377

assert gmpy2.gcd (e1, e2) == 1
_, s1, s2 = gmpy2.gcdext(e1, e2)
m1 = pow(c1, s1, n2) if s1 > 0 else pow(gmpy2.invert(c1, n2), -s1, n2)
m1 *= pow(c2, s2, n2) if s2 >0 else pow(gmpy2.invert(c2, n2), -s2, n2)

print(libnum.n2s(int(m)).decode() + libnum.n2s(int(m1 % n2)).decode())

运行得到flag

最后flag为

1
flag{05929ec9778ed739d94ee1a77b742714}

[WEEK2]e？

1
2
3
4
p= 70724362259337647663584082414795381346569735601816096923682814277857463878289
q= 114427188167532721707398034034072867253267857672869034942206947096293901917007
e= 1314
c= 4308122681135507736058122041934864039713319497673888928736468819190185301630702240416683093700232966794026900978699666246019059398861283337865339404916304

e和ϕ(n)不互素

exp：

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
p= 70724362259337647663584082414795381346569735601816096923682814277857463878289
q= 114427188167532721707398034034072867253267857672869034942206947096293901917007
e= 1314
c= 4308122681135507736058122041934864039713319497673888928736468819190185301630702240416683093700232966794026900978699666246019059398861283337865339404916304
n = p * q
phi = (p-1)*(q-1)
t = gmpy2.gcd(e,phi)
d = gmpy2.invert(e // t,phi)
M = pow(c,d,n)
m = gmpy2.iroot(M,t)[0]
print(bytes.fromhex((hex(m)[2:])))

运行得到

最后flag为

1
flag{This_e_is_real_or_not}

[WEEK2]factorizing_n

1
2
3
n = 226515252384227990547287743140613580056836242860947832749754689048997071950972581790210817523352001702907675581567498443649554801433663166425134375454937126656357069687274036935331269594383360450823787099121079436459236734336130768046337169817940540921822023269188752420603975467384377614321048859304185067329741055517464271746238143742661897809442359331215501438861121047081117632626097939097519866099140569819965948998542652908170134545593659233229897003698175558888336706474178958535138595687148003367152624421106553412886263257022809480187410133186189435436294593588009551451899398811758511878324326255293307347560753524372663257044426744744426759970254203341706284024734042826158828749144322843934985927079504722440497388146240627249465363931951790326885478025237643
c = 52409805591744226507807531465616894934028463651864630447934395956954575834603756391651746535033902964658694070544877880970130028487381287088425209448038533705903737694267359561133766799228825599943891152463160326583722749586721691729062524310148743637505134465210906856660867852927837112666513674858029892207902196213784902541173835447263733760225682942461048573387925463479672527491229113710629340960375692432470493054415657845868577650170648157402682163577152288432313996310562452677399267755695644659367792066311336521698894993982901657735586844358679888210537898629281625526455444811591386493005341435516094660429968084363084301878446471676122069724608083578102382181382107225473535696274374370868301830807644939881080301668756603163431000745972823980427048672732291
e = 65537

yafu分解后发现n为一个数的五次幂
exp:

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
import gmpy2

n = 226515252384227990547287743140613580056836242860947832749754689048997071950972581790210817523352001702907675581567498443649554801433663166425134375454937126656357069687274036935331269594383360450823787099121079436459236734336130768046337169817940540921822023269188752420603975467384377614321048859304185067329741055517464271746238143742661897809442359331215501438861121047081117632626097939097519866099140569819965948998542652908170134545593659233229897003698175558888336706474178958535138595687148003367152624421106553412886263257022809480187410133186189435436294593588009551451899398811758511878324326255293307347560753524372663257044426744744426759970254203341706284024734042826158828749144322843934985927079504722440497388146240627249465363931951790326885478025237643
c = 52409805591744226507807531465616894934028463651864630447934395956954575834603756391651746535033902964658694070544877880970130028487381287088425209448038533705903737694267359561133766799228825599943891152463160326583722749586721691729062524310148743637505134465210906856660867852927837112666513674858029892207902196213784902541173835447263733760225682942461048573387925463479672527491229113710629340960375692432470493054415657845868577650170648157402682163577152288432313996310562452677399267755695644659367792066311336521698894993982901657735586844358679888210537898629281625526455444811591386493005341435516094660429968084363084301878446471676122069724608083578102382181382107225473535696274374370868301830807644939881080301668756603163431000745972823980427048672732291
e = 65537

p = 11776588228599764849559519654482976956833367474471407292255776713760090338489966385328569279135095351660161277221351884258247731394014018172166064062551483
phi = p**4 * (p-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

运行得到flag

最后flag为

1
flag{1f95f530f85b940db810fc917607ee22}

[WEEK2]哈希猫

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
import hashlib
from secret import flag

assert flag[:5] == "flag{"
assert flag[-1:] == "}"
flag = flag[5:-1]
assert len(flag) == 43


print(hashlib.md5(flag[0:3].encode()).hexdigest())
print(hashlib.sha256(flag[3:5].encode()).hexdigest())
print(hashlib.sha512(flag[5:7].encode()).hexdigest())
print(hashlib.sha256(flag[7:9].encode()).hexdigest())
print(hashlib.sha256(flag[9:11].encode()).hexdigest())
print(hashlib.sha224(flag[11:13].encode()).hexdigest())
print(hashlib.sha224(flag[13:15].encode()).hexdigest())
print(hashlib.sha224(flag[15:17].encode()).hexdigest())
print(hashlib.sha1(flag[17:20].encode()).hexdigest())
print(hashlib.sha1(flag[20:23].encode()).hexdigest())
print(hashlib.sha512(flag[23:25].encode()).hexdigest())
print(hashlib.sha1(flag[25:28].encode()).hexdigest())
print(hashlib.sha256(flag[28:30].encode()).hexdigest())
print(hashlib.md5(flag[30:33].encode()).hexdigest())
print(hashlib.sha256(flag[33:35].encode()).hexdigest())
print(hashlib.sha1(flag[35:38].encode()).hexdigest())
print(hashlib.sha224(flag[38:40].encode()).hexdigest())
print(hashlib.md5(flag[40:43].encode()).hexdigest())


# bba78e7d3d6ea696bfef6e87a26a6c03
# 894461aba3e5e2724278cfc40fa15dc1510b0cd56430fec9fc8a90d6d8ebe5f7
# 092ca0da5f25c595eae6cc725dc12ae75889a639d205733223cb9cfaeaa702a521971e57f768079b03d53c8f092bb2c597cc3adb4a98224a144c5d62461beb52
# 122c597083bd438b7f6d72af75d025948899647711b806bdd2cd82fa69713db3
# 153812ae5fea0b73a011bf28bd7cea93644437c3fe3260b7b2d7e1e2f9f46bde
# 24296a0d1555ad424b04dd5f6268c5613dae32cde8a469ca8c9065b9
# 15d46f8eae648f5945c4605b15e0507836ee1251b74de2e95bf9394d
# 9afdf5d1027172492a32833975a69a1e501e6f824d3e5a7121ad18af
# 2b7655eb53f6f92086e58da465c6733bd8d8a1a3
# a44fce0412ae28173cf036700c3f1cc8c7a279c6
# 7356ea99a4fa12c6a3ed8ecc1e78a7bb28cdc1208962848646cf34e0d836f420cf594606cde74bec1dc2efe511dff0dd07b558bd0c7d01a526de2e9c25d47a6f
# cc5c3fe6e7356a26a134cff5633349f597c40a9d
# 757d22f85733770bae59cc857dcfc369db29031459421b808377cf06bc9881ad
# a2c7bdf97e3c761c431f8891dcc39fa9
# 0606c0e8f78de4d7a78522a5ae2f7b70e31e669e6e2a16e11c393e4443069813
# cb6c6c7cc8189868e1feaae773f947908233cdcc
# 2cb5169af85bd3122276f8b0a731ed2ea30c8bef366bfafe76b5e7db
# d1de3eac41792a7f498dae8f439bf16d

一堆hash，直接爆破

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
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
import hashlib
from itertools import product

c = ["bba78e7d3d6ea696bfef6e87a26a6c03",
"894461aba3e5e2724278cfc40fa15dc1510b0cd56430fec9fc8a90d6d8ebe5f7",
"092ca0da5f25c595eae6cc725dc12ae75889a639d205733223cb9cfaeaa702a521971e57f768079b03d53c8f092bb2c597cc3adb4a98224a144c5d62461beb52",
"122c597083bd438b7f6d72af75d025948899647711b806bdd2cd82fa69713db3",
"153812ae5fea0b73a011bf28bd7cea93644437c3fe3260b7b2d7e1e2f9f46bde",
"24296a0d1555ad424b04dd5f6268c5613dae32cde8a469ca8c9065b9",
"15d46f8eae648f5945c4605b15e0507836ee1251b74de2e95bf9394d",
"9afdf5d1027172492a32833975a69a1e501e6f824d3e5a7121ad18af",
"2b7655eb53f6f92086e58da465c6733bd8d8a1a3",
"a44fce0412ae28173cf036700c3f1cc8c7a279c6",
"7356ea99a4fa12c6a3ed8ecc1e78a7bb28cdc1208962848646cf34e0d836f420cf594606cde74bec1dc2efe511dff0dd07b558bd0c7d01a526de2e9c25d47a6f",
"cc5c3fe6e7356a26a134cff5633349f597c40a9d",
"757d22f85733770bae59cc857dcfc369db29031459421b808377cf06bc9881ad",
"a2c7bdf97e3c761c431f8891dcc39fa9",
"0606c0e8f78de4d7a78522a5ae2f7b70e31e669e6e2a16e11c393e4443069813",
"cb6c6c7cc8189868e1feaae773f947908233cdcc",
"2cb5169af85bd3122276f8b0a731ed2ea30c8bef366bfafe76b5e7db",
"d1de3eac41792a7f498dae8f439bf16d"]

flag = "flag{"
table = [chr(i) for i in range(32,128)]

for i in product(table,repeat=3):
    m = "".join(i)
    hash = hashlib.md5(m.encode()).hexdigest()
    if hash == c[0]:
        flag += m
print(flag)
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha256(m.encode()).hexdigest()
    if hash == c[1]:
        flag += m
print(flag)     
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha512(m.encode()).hexdigest()
    if hash == c[2]:
        flag += m
print(flag)    
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha256(m.encode()).hexdigest()
    if hash == c[3]:
        flag += m
print(flag)
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha256(m.encode()).hexdigest()
    if hash == c[4]:
        flag += m
print(flag)        
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha224(m.encode()).hexdigest()
    if hash == c[5]:
        flag += m
print(flag)
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha224(m.encode()).hexdigest()
    if hash == c[6]:
        flag += m
print(flag)
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha224(m.encode()).hexdigest()
    if hash == c[7]:
        flag += m
print(flag)     
for i in product(table,repeat=3):
    m = "".join(i)
    hash = hashlib.sha1(m.encode()).hexdigest()
    if hash == c[8]:
        flag += m
print(flag)        
for i in product(table,repeat=3):
    m = "".join(i)
    hash = hashlib.sha1(m.encode()).hexdigest()
    if hash == c[9]:
        flag += m
print(flag)      
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha512(m.encode()).hexdigest()
    if hash == c[10]:
        flag += m
print(flag)       
for i in product(table,repeat=3):
    m = "".join(i)
    hash = hashlib.sha1(m.encode()).hexdigest()
    if hash == c[11]:
        flag += m
print(flag)       
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha256(m.encode()).hexdigest()
    if hash == c[12]:
        flag += m
print(flag)              
for i in product(table,repeat=3):
    m = "".join(i)
    hash = hashlib.md5(m.encode()).hexdigest()
    if hash == c[13]:
        flag += m
print(flag)       
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha256(m.encode()).hexdigest()
    if hash == c[14]:
        flag += m
print(flag)
for i in product(table,repeat=3):
    m = "".join(i)
    hash = hashlib.sha1(m.encode()).hexdigest()
    if hash == c[15]:
        flag += m
print(flag)      
for i in product(table,repeat=2):
    m = "".join(i)
    hash = hashlib.sha224(m.encode()).hexdigest()
    if hash == c[16]:
        flag += m
print(flag)       
for i in product(table,repeat=3):
    m = "".join(i)
    hash = hashlib.md5(m.encode()).hexdigest()
    if hash == c[17]:
        flag += m
flag += "}"
print(flag)

运行得到flag

最后flag为

1
flag{YOU'vE_c0m3_To_UNDerS7anD_Ha5H_GDIbgdF3EocT}

[WEEK3]Classical Master

1
2
3
4
5
6
7
8
9
10
import math
from secret import s
s = s.lower()
keyM = [?]
l = len(keyM)
assert(math.gcd(l,26)==1)
for i in range(len(s)):
    print(chr((ord(s[i])*l-97+(keyM[i % l]))%26+97),end="")

#uvgbdzbihyfxvqipvvwxqnpwybaomhnibglpncsdohyespkglzbbfpgwxjsludjcyesphzlcsznuflejzezmnqpktbjbbajocrqlfzogrpuzwesgqbvhvzpongpdbewtihwvuwrgrzbmudnuaxgzgcknydxhhlqguabnjhczkrfjmxbtavbeennkojetoqtpqlwwupkorramvwhhngyytwzybtriaaxgaodzhzvypiszcmbwchuwrjjfdzqpgvbigxsdzfbbgfyzypiblpflirexudlhfvgpebazjwbabglrorulkzpquvgbdzttgittuxgaodkphelvcpepubfuirzaarfdgzevjxmiwhqtgvnbhqspxlagpluwrrrhshshpptrrpaxozjkdkrbvolwwevbojerxvaghmyvlchzmizeflyytvpqbhwnsxwtvojzhenjozircttqqbcgxgabytqvhlyjcjfoopdrsyhlaokbpweecrbfpyqwjtcxjgzcskojorejtpnokoptlfyzypibsrnkpgjrudkojhchqtgnybpsbcxmzaodoxppkevbpqlzorkrfgzhcxsnedkoaarypoptnanxeaodbpwesbrcjxvagebuazlqpbkojbuwrgpsjozefxwzogfvwnzcrogcyhhipwejfylvottgirfhgtaoqhbfccpelqnxzxrelcpcxfkhujtbwjxynyatvvjyrggppzhjfleknapsohrfwxjsludwnibglrghzcaajfxgzfbhykspijyenndcbkdtuxpozqxohtdapmziujgzhnrkczerpunyhuvazqhqjqjmthmorzmihwctnjcbpsbpehccxyjfvhcubyzdsjsdknhpwargcpvabwvwxjsludazxvcxjojflazjquvbfqzobzeespibpqvjlnvcyrijqlzzrzppicrwujzeqrfjgrkdfqbetkglzruohadypgexuttfybvxmiiuvwlbmkppjyzhixbuklllghnbnderaaarfkjwpljhmcxqkbfdqkhnaanorhruuwizpzmtnedgeybiyvwhhtwxemrtjwwthvvpcrimopodhxmcgudjrhpgyjsrmdwqqvhvqirclsyivjhmcyhzjuyvgvcarfububklnhlqgbbhtqrzxgrqkjcthojpcehtjuyedzrcrphihhdkoaajczzqpcdzhaxgvghhgrcryruwvqbcturoxqmihipmjefxsdkhwqdydfrqttqqngzdbqgjkqjkuhbtjrxzqaittalvhmihriuvckzqvbcnvwveozqxohrzunmtwhqtcqdjyrcxlqbpsvuwrzqzibvbqhvcbqgmohjttwlogudqtjdynjrehfvzwvaxmzmzjwyidgyjrxgstcengphtrvbtoralojyrwlzpebghxoiglwqbesxpoxquahrtlebtmnttxppkepckhhhrjespngrpmbfsbwvqlwhmohjttkglmqqvqqespngrpmbfsbwnzsrfnjcrqawxjhzcaqqnjirbvljlyinjwricnqtoralkrlaodoqqvzkxjqhsxhebyyytriububvgtrcxphizjalyytnudjqevjnzogpcohrkxhybwhbkbtokpglmzzwnwdgtrbmwojgivghmcxyjhghbwnrscyvktsclxmrhhqtfhnvgqtjxvagnbvzrovhnnkppykrflcdwldfepetgxvkojnuwrgaodrhbrsyxelcybljtjxeffcjrgjkhpxgaodipekdtzkxsnbpenglqtpfdcyjidpmxrclkbwvtoetzwpiphtfgisjhslhznuwfoxxcbwfvtkglmfmtcnewxepehlkhwesxmbmtwbphedkaarsjohhetkgcyhijgdvraruihqthezlhpzwhqopsvajpnzgcnavbkebtmxkhcpkbhptqtlwwhmlxfrabutwihdkaglqkbiavyhrovhmbpnclnaaxujvdquxbrcyhqfndijpxejcbkudzuhxoghihbwtvpmrdhlofhbuwryzgxbnuclcqtpfjwfynvhmlpodzxbesyytaznbcjzlnpbetmhpnxfhetyhqzyjzdxqjjfshrsclpmiczyqfbebxpcrwjwwjdazrocbqkojivvetriububvgtrlpljlyritiqtanojfqnrkzozlmtneesxakenibwhpptrrpsxaqpktbhlqgwbbelrcfbkgdjcynvgebvqvfpierzxgenthcihccjovzuahhvgelgrpyqqqvjpjoxxuhfhvjnczeqkbgrljyybaxvagivtebtanzohregpprzudfneethmtgzykojlrcgrxsmihhvjtezqgbroreuwrfhzcaqjdpwbtjfnhujergetwhyksrnkjetaolwqprthmrllhbfhgrchazqvzfdzppprxqkbusctkzrapmbnufdkgjyzhiqzbtzxonpminddgehlphnbcznkogtczybfdzppprjcmihhdvphzewbnhsgthqnehvzpiltbpirfhozcvailcxcdrpvgthqnehvzrrqjhmbkzctqvercrbvoktffbtoplmgvmhzctyryrumihvftbktjcmobscuwrzmgpqzuglcrovhwbqzvlkaaxfdropcturezzcbwrqayyzphtinqdqppnvldzfjkkhrrjcmihynwargrchbnuespjgypwtqhrrvgazavkfrilyytfhpknruknlxvhbzarksxklaflohscljmsxlrbwybrcazcpvabwvuwlraodmzwtuozjjxvagpolbhajlksujzlercypcansclcplpzttgigrcbpxnsipcnunzogadfntvuwrlefcjmjdjxvajgstxrtjozyrqjltbfcjqrrfyhxbdvnqbwhmhrvctijcppbjujdkongxxylhensxwtpbqoheklcribtoohjldoqcxqkbtjdynxezlhvrdutyriypwtqhdgeaarylzqyvlepzcrpazuvsxwtzgqbpyhvxehrwjvqrmtyyjyzhiqqilxatmfmhztmyhpzmrpmbspypbfzlmtnettcrglgdqavdcgrcjqdsphtdvmkehgvwbzlletrwchmjglxetmmvoneflkaazavkpekuwrjxubknuespptatqjcstdnybkzmkojilaxgrzotrdtuirbpglghsbsxklagdkrjolxpszmdknfbreybkzmzrvoteybkzmzrdtuirirfmonvvaxmimhtmbwirfpkehujujkwvepxnszhjkdfjsqsjorfbreybkzmzpekepvzbhmihbijozyrpyqoplbhqsjphfntmkhpaaovzwbgwhvnqqobpsescxnnomihhvjtezqgbtqznkoktgnybspilxvaplqhgizrkabjcbjywngtjkqhtizncbhqsguvghroteybkzmmupfvbqlchlwwwvcozxrzmrzscrkrjyzhixbukielmdnblibjpecxfxfljtjaxgjqvzpebuwrgxsyjqdilnqbhfmipsbgodbypwtqndgnlmgbdjcpespeazavkfpngveiruohusclnrjezmkhelrcgranubuubyzaarzqfoptlkabpvvlbheahpxjyctcjfxnrscxvkosclajgpqjmrvqlfybkzmzxqnpwjrzfohgibbnjjjgcohrklxvaplqhgigrcaajumnwrhjhmcyzbsujtpcjmrwnjcevyirexudtywbpprianmihevmypxencasbijyjjjgcohrkuwrjxuszzetdorovhtihentcjrrqkbcbldoqgrpskojlrcgrjcbtgjqppzeahqtoralgzgaprbcpgvbblgwlnrjdkozrazttgiilxgcyhthuyttlzlmkxzqcvwvetjudkzwvtygbdfdwwrqazxraznsnwetkazmqktfpzpxplxcvrziuypziaodrnwkjxqzlwjwqqvgpscgpptxbukcrkrpmkobtccxxrwxohrqahhlqghhcsngjrlmgvphtdgkrgcnqkobiubgbdfmihenbhqsabqwqpespmtsqbfupukxmiehubpseshpkenhbwdilaxgzcjkojiuwjgatsjthnbhqsvnykzeplhmcyzblpeqlcloazctoralojyrwttqqvttyrvujagubyyyleqpqpvttkgddudjwbqhwzrkhhhrjctijczcsrorebhqskhlflpfcojryhsrzscuwjrypwtqqvypjoqzdzqqvshgircbblwvuvcbqgnjchdptxdigvzotvgypbpzqbyjduyythnqqfyddodcyhprziujvxokhhhrjdcxecxsnnpnedurdjcsubsfrcrlbyjoqrquyytdxvagrujvptryvwqpfxvaaruntcyesxaddfmbubbfnpzluhbxqnpwmtwhqzgjvcnhajlkfujduppddwqbptttkgzcqdwrrjlnbtzlmtczdxnjixcjklpfccrarcsjfsclfxggfjmqqvjppxencafriltxopbnbwchvbbfpqdozppjzjogzttgiolljoanlrpxvlxvabnqwzerbhaazmvkpinubjazmdwhovydmzhcwbspilzdyjdjoxbukhmxehlzhthlkaalfvjftldoqgjfdltyvjhetannbhsesphzegsrziururgvnnbhovybctzuvhcnvzkrjzqbvcwnjpzogzttgiolwzkizdoqqdghryruwbgbvqpglayjzfbokpazkhvwqqnjfxgqwjmfsidarbmwbhuwbbpwtmqxjgihdfjsqsvwwthjpqeehlfqbqhyxbqgbtqdduhxopxktlqzrkcgxcmlhrtdfzrvnnlpeklejoaodzlwbkopcxudjlsdgepzxcmihhvttalxcbjcyilxvcjnyzxbukirxxrdbphhuvitesjorubyxmfzlmrzsccczxazhbajzrzrrrpbnqqpjxmthpyqdpbawzmjqvzapigaxghodwpedpyktvnnbfjdjbaaenxxonbgnabmqqbyjedyxojqwblpflnzkqhlzbwvuvitesjorrqahclazbjyivtnlgrqjshwgrcblazblpetgxanehmhyjiwvedjqjmqjqbwrojydospivhazcqdwzsoltxdrflipcnuxmijadfntvdyprqpibpekjhmxrzmtfrrrvgazavkqqnjhpddxvagsbaxdlkhztcrqlfqlchlwwbftdrbpncbrebtyycxrpzhiguwzcmnmizerbhqsehmjuyfxkrjqzobffirfaajxvagibjpmzapsjtuirzaarfdohrkdknrcnqkoreaxdxzcyhqcvypagjhibwebytzojfxufsnujatzcjkojiwvelaznvfsqryjjjgcwnsoypzhaovzorodyxegpvatwvtejonsqhrsclnrrvujaghdgejoauxkosclarjbnnbcstjgroahlfoydxvmcyzbwhzctijczudubsdjzzsqyqtljergzfcnqkojctgilmhbzpekjjvxrfbkorebhqskhntcjdjhetzwlwwwvypziaodrnwkjhmcyhbfupuknazcncanzqlurghzcazrukvhcyhwohonubxerphifniroqoxumihhnvgqlvzmnnununhzewbknndfnrdrqjkujduyytplqhgitvpprzddazfcuodcynxzpekjvcpepubfrilgetpfdqqpgdoqzmhgjuznuwhlmhlwwscllebihbpzedgeinqylohsbjnrianmihcnyeprxzmtfznuwaarfdxurmlnxehzbqntgyvbcyhlxhhfftyazfwbhegdoatehsjcyernptgqjkojldkgzmgpkojmfcrcebmigbvjejrazcahyngyythnqqfsbpvbtjxvagyidkfbpzyzqwppyrizcszybukkxczwqhyrqayytphdqnutftvtpfvrziujfzsqntknydxzdzqwbpzectnktvnnbphkfnalhzcaxruzyzsqpnhcfflkzogqkbtznkofoxxnbcpewvecxwlnzrftkrjbpyrzsctkrjqzobojilhpfxbqmgrrxvlbehmihwvtobbpqdo

频率分析：

在任何一种书面语言中，不同的字母或字母组合出现的频率各不相同。而且，对于以这种语言书写的任意一段文本，都具有大致相同的特征字母分布。比如，在英语中，字母E出现的频率很高，而X则出现得较少。类似地，ST、NG、TH，以及QU等双字母组合出现的频率非常高，NZ、QJ组合则极少。英语中出现频率最高的12个字母可以简记为“ETAOIN SHRDLU”

常见的频率分析的场景为破解替换密码。

普遍情况下26字母的频率分布如下

重合指数：

重合指数是衡量频率分布和均匀分布相似程度的度量。频率分析是经典密码分析里的重要工具，如果我们分别使用替换密码和维吉尼亚密码加密一段文本，我们可以发现维吉尼亚的频率分布更加平坦，而替换密码的频率分布更加“粗糙”。而重合指数正是将频率分布这种直观的视觉转换为数字表达式。

数学定义：

数学定义：其中f_i代表i字母的个数，N是字母总个数。

IC=\frac{\sum\limits_{i=A}^{i=Z}f_i(f_i-1)}{N(N-1)}

维基的解释：

重合指数又称重合概率，是指从一段密文种随机抽取两个字母，这两个字母相同的概率,已知一个完全随机的英文文本重合指数约为：0.0385；而有意义的英文文本重合指数CI约为0.065，从定义来看，肯定不是用用来破解凯撒，无论你怎么移动它的重合指数都不变。

拟重合指数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
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
#去除非字母
def check(i):
    if ord(i)>=97 and ord(i)<=122:
        return True
    else:
        return False
# 计算重合指数
def Index_of_Coincidence(string):
    IC = 0
    alpha = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0,
             'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}

    N = len(string)
    N = float(N * (N - 1))

    for i in string:
        alpha[i] += 1
    for i in alpha:
        i = alpha[i]
        IC += i * (i - 1)
    IC = IC / N
    return IC


# 得到密钥长度
def guess_len_key(text):
    l = 1
    while True:
        sum_index = 0.0
        for i in range(l):
            sum_index += Index_of_Coincidence(text[i::l])

        sum_index = sum_index / l
        if sum_index >= 0.06 and sum_index <= 0.07:
            break
        else:
            l += 1
    return l


from gmpy2 import *


# 拟重合指数，确定密钥
def keyword(Ciphertext, keylength):
    ListCiphertext = list(Ciphertext)
    Standard = {'a': 0.08167, 'b': 0.01492, 'c': 0.02782, 'd': 0.04253, 'e': 0.12702, 'f': 0.02228, 'g': 0.02015,
                'h': 0.06094, 'i': 0.06966, 'j': 0.00153, 'k': 0.00772, 'l': 0.04025, 'm': 0.02406, 'n': 0.06749,
                'o': 0.07507, 'p': 0.01929, 'q': 0.00095, 'r': 0.05987, 's': 0.06327, 't': 0.09056, 'u': 0.02758,
                'v': 0.00978, 'w': 0.02360, 'x': 0.00150, 'y': 0.01974, 'z': 0.00074}
    while True:
        key1 = []
        key2 = []
        for i in range(keylength):
            PresentCipherList = ListCiphertext[i::keylength]
            QuCoincidenceMax = 0
            # 分别爆破m,n
            for m in range(26):
                if gcd(m, 26) == 1:
                    for n in range(26):
                        QuCoincidencePresent = 0
                        for Letter in set(PresentCipherList):
                            LetterFrequency = PresentCipherList.count(Letter) / len(PresentCipherList)
                            k = chr(invert(m, 26) * (ord(Letter) - n) % 26 + 97)
                            StandardFrequency = Standard[k]
                            # 拟重合指数
                            QuCoincidencePresent = QuCoincidencePresent + LetterFrequency * StandardFrequency

                        if QuCoincidencePresent > QuCoincidenceMax:
                            # 取最大的拟重合指数对应位移为密钥
                            QuCoincidenceMax = QuCoincidencePresent
                            k1 = m
                            k2 = n
            key1.append(k1)
            key2.append(k2)

        break
    return key1, key2


# 解密
def decrypt(Ciphertext, key1, key2, length):
    message = ""
    flag = 0
    for i in Ciphertext:
        if check(i):
            message += chr(invert(key1[flag % length], 26) * (ord(i) - key2[flag % length]) % 26 + 97)
            flag += 1
        else:
            message += i
    return message


# 默认全为小写字母
Ciphertext = 'uvgbdzbihyfxvqipvvwxqnpwybaomhnibglpncsdohyespkglzbbfpgwxjsludjcyesphzlcsznuflejzezmnqpktbjbbajocrqlfzogrpuzwesgqbvhvzpongpdbewtihwvuwrgrzbmudnuaxgzgcknydxhhlqguabnjhczkrfjmxbtavbeennkojetoqtpqlwwupkorramvwhhngyytwzybtriaaxgaodzhzvypiszcmbwchuwrjjfdzqpgvbigxsdzfbbgfyzypiblpflirexudlhfvgpebazjwbabglrorulkzpquvgbdzttgittuxgaodkphelvcpepubfuirzaarfdgzevjxmiwhqtgvnbhqspxlagpluwrrrhshshpptrrpaxozjkdkrbvolwwevbojerxvaghmyvlchzmizeflyytvpqbhwnsxwtvojzhenjozircttqqbcgxgabytqvhlyjcjfoopdrsyhlaokbpweecrbfpyqwjtcxjgzcskojorejtpnokoptlfyzypibsrnkpgjrudkojhchqtgnybpsbcxmzaodoxppkevbpqlzorkrfgzhcxsnedkoaarypoptnanxeaodbpwesbrcjxvagebuazlqpbkojbuwrgpsjozefxwzogfvwnzcrogcyhhipwejfylvottgirfhgtaoqhbfccpelqnxzxrelcpcxfkhujtbwjxynyatvvjyrggppzhjfleknapsohrfwxjsludwnibglrghzcaajfxgzfbhykspijyenndcbkdtuxpozqxohtdapmziujgzhnrkczerpunyhuvazqhqjqjmthmorzmihwctnjcbpsbpehccxyjfvhcubyzdsjsdknhpwargcpvabwvwxjsludazxvcxjojflazjquvbfqzobzeespibpqvjlnvcyrijqlzzrzppicrwujzeqrfjgrkdfqbetkglzruohadypgexuttfybvxmiiuvwlbmkppjyzhixbuklllghnbnderaaarfkjwpljhmcxqkbfdqkhnaanorhruuwizpzmtnedgeybiyvwhhtwxemrtjwwthvvpcrimopodhxmcgudjrhpgyjsrmdwqqvhvqirclsyivjhmcyhzjuyvgvcarfububklnhlqgbbhtqrzxgrqkjcthojpcehtjuyedzrcrphihhdkoaajczzqpcdzhaxgvghhgrcryruwvqbcturoxqmihipmjefxsdkhwqdydfrqttqqngzdbqgjkqjkuhbtjrxzqaittalvhmihriuvckzqvbcnvwveozqxohrzunmtwhqtcqdjyrcxlqbpsvuwrzqzibvbqhvcbqgmohjttwlogudqtjdynjrehfvzwvaxmzmzjwyidgyjrxgstcengphtrvbtoralojyrwlzpebghxoiglwqbesxpoxquahrtlebtmnttxppkepckhhhrjespngrpmbfsbwvqlwhmohjttkglmqqvqqespngrpmbfsbwnzsrfnjcrqawxjhzcaqqnjirbvljlyinjwricnqtoralkrlaodoqqvzkxjqhsxhebyyytriububvgtrcxphizjalyytnudjqevjnzogpcohrkxhybwhbkbtokpglmzzwnwdgtrbmwojgivghmcxyjhghbwnrscyvktsclxmrhhqtfhnvgqtjxvagnbvzrovhnnkppykrflcdwldfepetgxvkojnuwrgaodrhbrsyxelcybljtjxeffcjrgjkhpxgaodipekdtzkxsnbpenglqtpfdcyjidpmxrclkbwvtoetzwpiphtfgisjhslhznuwfoxxcbwfvtkglmfmtcnewxepehlkhwesxmbmtwbphedkaarsjohhetkgcyhijgdvraruihqthezlhpzwhqopsvajpnzgcnavbkebtmxkhcpkbhptqtlwwhmlxfrabutwihdkaglqkbiavyhrovhmbpnclnaaxujvdquxbrcyhqfndijpxejcbkudzuhxoghihbwtvpmrdhlofhbuwryzgxbnuclcqtpfjwfynvhmlpodzxbesyytaznbcjzlnpbetmhpnxfhetyhqzyjzdxqjjfshrsclpmiczyqfbebxpcrwjwwjdazrocbqkojivvetriububvgtrlpljlyritiqtanojfqnrkzozlmtneesxakenibwhpptrrpsxaqpktbhlqgwbbelrcfbkgdjcynvgebvqvfpierzxgenthcihccjovzuahhvgelgrpyqqqvjpjoxxuhfhvjnczeqkbgrljyybaxvagivtebtanzohregpprzudfneethmtgzykojlrcgrxsmihhvjtezqgbroreuwrfhzcaqjdpwbtjfnhujergetwhyksrnkjetaolwqprthmrllhbfhgrchazqvzfdzppprxqkbusctkzrapmbnufdkgjyzhiqzbtzxonpminddgehlphnbcznkogtczybfdzppprjcmihhdvphzewbnhsgthqnehvzpiltbpirfhozcvailcxcdrpvgthqnehvzrrqjhmbkzctqvercrbvoktffbtoplmgvmhzctyryrumihvftbktjcmobscuwrzmgpqzuglcrovhwbqzvlkaaxfdropcturezzcbwrqayyzphtinqdqppnvldzfjkkhrrjcmihynwargrchbnuespjgypwtqhrrvgazavkfrilyytfhpknruknlxvhbzarksxklaflohscljmsxlrbwybrcazcpvabwvuwlraodmzwtuozjjxvagpolbhajlksujzlercypcansclcplpzttgigrcbpxnsipcnunzogadfntvuwrlefcjmjdjxvajgstxrtjozyrqjltbfcjqrrfyhxbdvnqbwhmhrvctijcppbjujdkongxxylhensxwtpbqoheklcribtoohjldoqcxqkbtjdynxezlhvrdutyriypwtqhdgeaarylzqyvlepzcrpazuvsxwtzgqbpyhvxehrwjvqrmtyyjyzhiqqilxatmfmhztmyhpzmrpmbspypbfzlmtnettcrglgdqavdcgrcjqdsphtdvmkehgvwbzlletrwchmjglxetmmvoneflkaazavkpekuwrjxubknuespptatqjcstdnybkzmkojilaxgrzotrdtuirbpglghsbsxklagdkrjolxpszmdknfbreybkzmzrvoteybkzmzrdtuirirfmonvvaxmimhtmbwirfpkehujujkwvepxnszhjkdfjsqsjorfbreybkzmzpekepvzbhmihbijozyrpyqoplbhqsjphfntmkhpaaovzwbgwhvnqqobpsescxnnomihhvjtezqgbtqznkoktgnybspilxvaplqhgizrkabjcbjywngtjkqhtizncbhqsguvghroteybkzmmupfvbqlchlwwwvcozxrzmrzscrkrjyzhixbukielmdnblibjpecxfxfljtjaxgjqvzpebuwrgxsyjqdilnqbhfmipsbgodbypwtqndgnlmgbdjcpespeazavkfpngveiruohusclnrjezmkhelrcgranubuubyzaarzqfoptlkabpvvlbheahpxjyctcjfxnrscxvkosclajgpqjmrvqlfybkzmzxqnpwjrzfohgibbnjjjgcohrklxvaplqhgigrcaajumnwrhjhmcyzbsujtpcjmrwnjcevyirexudtywbpprianmihevmypxencasbijyjjjgcohrkuwrjxuszzetdorovhtihentcjrrqkbcbldoqgrpskojlrcgrjcbtgjqppzeahqtoralgzgaprbcpgvbblgwlnrjdkozrazttgiilxgcyhthuyttlzlmkxzqcvwvetjudkzwvtygbdfdwwrqazxraznsnwetkazmqktfpzpxplxcvrziuypziaodrnwkjxqzlwjwqqvgpscgpptxbukcrkrpmkobtccxxrwxohrqahhlqghhcsngjrlmgvphtdgkrgcnqkobiubgbdfmihenbhqsabqwqpespmtsqbfupukxmiehubpseshpkenhbwdilaxgzcjkojiuwjgatsjthnbhqsvnykzeplhmcyzblpeqlcloazctoralojyrwttqqvttyrvujagubyyyleqpqpvttkgddudjwbqhwzrkhhhrjctijczcsrorebhqskhlflpfcojryhsrzscuwjrypwtqqvypjoqzdzqqvshgircbblwvuvcbqgnjchdptxdigvzotvgypbpzqbyjduyythnqqfyddodcyhprziujvxokhhhrjdcxecxsnnpnedurdjcsubsfrcrlbyjoqrquyytdxvagrujvptryvwqpfxvaaruntcyesxaddfmbubbfnpzluhbxqnpwmtwhqzgjvcnhajlkfujduppddwqbptttkgzcqdwrrjlnbtzlmtczdxnjixcjklpfccrarcsjfsclfxggfjmqqvjppxencafriltxopbnbwchvbbfpqdozppjzjogzttgiolljoanlrpxvlxvabnqwzerbhaazmvkpinubjazmdwhovydmzhcwbspilzdyjdjoxbukhmxehlzhthlkaalfvjftldoqgjfdltyvjhetannbhsesphzegsrziururgvnnbhovybctzuvhcnvzkrjzqbvcwnjpzogzttgiolwzkizdoqqdghryruwbgbvqpglayjzfbokpazkhvwqqnjfxgqwjmfsidarbmwbhuwbbpwtmqxjgihdfjsqsvwwthjpqeehlfqbqhyxbqgbtqdduhxopxktlqzrkcgxcmlhrtdfzrvnnlpeklejoaodzlwbkopcxudjlsdgepzxcmihhvttalxcbjcyilxvcjnyzxbukirxxrdbphhuvitesjorubyxmfzlmrzsccczxazhbajzrzrrrpbnqqpjxmthpyqdpbawzmjqvzapigaxghodwpedpyktvnnbfjdjbaaenxxonbgnabmqqbyjedyxojqwblpflnzkqhlzbwvuvitesjorrqahclazbjyivtnlgrqjshwgrcblazblpetgxanehmhyjiwvedjqjmqjqbwrojydospivhazcqdwzsoltxdrflipcnuxmijadfntvdyprqpibpekjhmxrzmtfrrrvgazavkqqnjhpddxvagsbaxdlkhztcrqlfqlchlwwbftdrbpncbrebtyycxrpzhiguwzcmnmizerbhqsehmjuyfxkrjqzobffirfaajxvagibjpmzapsjtuirzaarfdohrkdknrcnqkoreaxdxzcyhqcvypagjhibwebytzojfxufsnujatzcjkojiwvelaznvfsqryjjjgcwnsoypzhaovzorodyxegpvatwvtejonsqhrsclnrrvujaghdgejoauxkosclarjbnnbcstjgroahlfoydxvmcyzbwhzctijczudubsdjzzsqyqtljergzfcnqkojctgilmhbzpekjjvxrfbkorebhqskhntcjdjhetzwlwwwvypziaodrnwkjhmcyhbfupuknazcncanzqlurghzcazrukvhcyhwohonubxerphifniroqoxumihhnvgqlvzmnnununhzewbknndfnrdrqjkujduyytplqhgitvpprzddazfcuodcynxzpekjvcpepubfrilgetpfdqqpgdoqzmhgjuznuwhlmhlwwscllebihbpzedgeinqylohsbjnrianmihcnyeprxzmtfznuwaarfdxurmlnxehzbqntgyvbcyhlxhhfftyazfwbhegdoatehsjcyernptgqjkojldkgzmgpkojmfcrcebmigbvjejrazcahyngyythnqqfsbpvbtjxvagyidkfbpzyzqwppyrizcszybukkxczwqhyrqayytphdqnutftvtpfvrziujfzsqntknydxzdzqwbpzectnktvnnbphkfnalhzcaxruzyzsqpnhcfflkzogqkbtznkofoxxnbcpewvecxwlnzrftkrjbpyrzsctkrjqzobojilhpfxbqmgrrxvlbehmihwvtobbpqdo'
length = guess_len_key(Ciphertext)
key1, key2 = keyword(Ciphertext, length)
print(key1)
print(key2)
print(decrypt(Ciphertext, key1, key2, length))

运行得到flag

最后flag为

1
flag{youaretherealmaster}

[WEEK3]e=3

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 secret import flag

M = 2**54
k = 6

def gen_prime(M, k):
    while True:
        prime = sum([random.getrandbits(16) * M**i for i in range(k)])
        if isPrime(prime) and (prime-1) % 3 == 0:
            return prime
        
p, q, r = [gen_prime(M, k) for i in range(3)]
N = p * q * r
e = 3
m = bytes_to_long(flag)
c = pow(m, e, N)
print(f'N = {N}')
print(f'c = {c}')

"""
N = 3298593732762513945346583663585189774036688951059270517149719979434109398447628726951796006700754759352430339647168415338320547665794785951232342902233013221132246450312038122695046634624323814318286314664160113738299465643128504110932989263063331290006313
c = 869489491924953293290699796392271834401780578884556874640489836779925847562085802848542382525324081900560761299059365684697233025590164192409062717942292142906458498707677300694595072310705415037345581289469698221468377159605973403471463296806900975548438
"""

多项式分解，把M当成多项式的未知数，那每个素数就是系数都是16比特的多项式.

N是三个素数的多项式相乘。因为54>16*3，所以可以恢复N的多项式的系数.

分解多项式不是难题，每个带入x=M就分解出p,q,r.

f(x) = a_{k-1}x^{k-1}+a_{k-2}x^{k-2}+…+a_1x^1+a_0

令x = M时，分别有p，q，r

所以N可以看作在M进制下的三个多项式相乘。用多项式分解可以得到三个多项式，再将M分别代入即可得到p，q，r

1
2
if isPrime(prime) and (prime-1) % 3 == 0:
            return prime

再由于关键代码中prime-1 \mid 3 即p-1,q-1,r-1 与3都不互素，用有限域开根的办法，进行CRT的组合就能得到flag

p,q,r都可以表示为M进制，于是可以用多项式来分解N，因为e和phi不互素，所以用有限域开根，再用中国剩余定理

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

N = 3298593732762513945346583663585189774036688951059270517149719979434109398447628726951796006700754759352430339647168415338320547665794785951232342902233013221132246450312038122695046634624323814318286314664160113738299465643128504110932989263063331290006313
c = 869489491924953293290699796392271834401780578884556874640489836779925847562085802848542382525324081900560761299059365684697233025590164192409062717942292142906458498707677300694595072310705415037345581289469698221468377159605973403471463296806900975548438
M = 2^54
poly = sum(e * x^i for i,e in enumerate(Integer(N).digits(M)))
# poly = 483094776500*x^15 + 67737188732830*x^14 + 124085394790974*x^13 + 195683246513428*x^12 + 273742579935809*x^11 + 458380068952801*x^10 + 592623629284873*x^9 + 582132325688443*x^8 + 685453135920467*x^7 + 720971197330040*x^6 + 597860219518539*x^5 + 434712532854786*x^4 + 332870394840336*x^3 + 251268756615643*x^2 + 110730229142998*x + 17535693800233
(p,_),(q,_),(r,_) = poly.factor_list()

p, q ,r = p(x=M),q(x=M),r(x=M)
# print(p)
# print(q)
# print(r)
# 103574226729554375480512668967949133854292403117507474988278388756193462602107352821951
# 47963432552002818180880760250824590058982930733941748241661938238195705638187268342813
# 663998156522471100999941798165706402858681862228017448075268472245282758965006970051

e = 3
R.<x> = Zmod(p)[]
f = x^e-c
f = f.monic()
res1 = f.roots()

R.<x> = Zmod(q)[]
f = x^e-c
f = f.monic()
res2 = f.roots()

R.<x> = Zmod(r)[]
f = x^e-c
f = f.monic()
res3 = f.roots()

for i in res1:
    for j in res2:
        for k in res3:
            m = crt([int(i[0]),int(j[0]),int(k[0])],[int(p),int(q),int(r)])
            flag = long_to_bytes(int(m))
            if b"flag" in flag:
                print(flag)
                break

运行得到flag

最后flag为

1
flag{e1b7d2c2-e265-11eb-b693-98fa9b5bc5fe}

[WEEK3]撤退！

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

flag = *******
p = getPrime(1024)
q = getPrime(1024)
n = p * q

hb = len(flag)//2
hb1 = bytes_to_long(flag[:hb])
hb2 = bytes_to_long(flag[hb:])
D = 117
x = *******
y = *******
assert x**2 - D * y**2 == 1
enc1 = pow(334 * n ** 2 + 1, hb1, n ** 3)
enc2 = pow(y * n + 1, hb2, n ** 3)
print(n)
print(enc1)
print(enc2)

'''
22970461944771505344360312103272646796516672838005008112295760406393062653512719537671401409823031480497512491850701737384621917068068328814717390355072928714618936469722031401433712342846780800586803218279291870162605299119904016959036663767093191710796830156169925350938267584422752300171293262391805105435418210827517225439398971437884496416502510866914857269951072184669675339439115587325754431761172634305242650221404868035624879538862880516438147301289746375407945908866907822940285764276956194031840381838253923392794376568293056359058519233175242523219646628321609305890926063856400793680641992567798104042179
26380574883568223071748995929433720836641856899148821439556557592284999544802260386919172895274884666117488851000353221957579311943624258651646692068406462392980585841604755021251430357273933800209194484692955106014890051223465745443628784077844452303995642424661442978294757109040081050794398646640530714904683097650259060507908334791761124660725589404056356987726993518057050112725483482660202442987346646160168856264312557595890710521723067518303906942469282527855551751244126251698491010628369012024332666619702895796133780038584346428759785302542637171018926824843416176876077558936427399803328577151066597396550597352625005028261156114571696860700477410270949916316951150072218466374341394892405947793726872954497972795793421222424616005278493704125169150432275472846871295341469911428057621028515874978272004775903906188556908968810828510069826724631700523623584802605889173266453916347583720706846630531082266742377818663000322817114065116737931523412220137972079139507877669106470150742546914051556747087768279286696519700220233815812834114117581332234344024169109786527295900675653245014343393093832478814567179131966404207553408747774003319241150221488231674711614902743345516888975702483348011349617017294004761259419165663633915672647187482242462163420462987034240805524991
21190674872507845600786632640969893237129139877891071648594239906632201421611954626926407751780936578853046780585253060958265549804784845192757301417173404074965693840282568701968464564320290763073618132775799910356101999797720378313304899173154753858674284071499775857913937184713024788245068426198878834805943703426673512761178072458895973672088230653246356764681418231485563287856188079274727706554037799748595877069143254516390328019381867648697880975670688337068196993846986940286056873616919629721264139576692806770826129279380704466982862393203486037890448173834315360975464927583664991534571518159777852793416869350127023692816051992183670690315184731534611966603509867722931839839084915943647295195314171688904055674915382434841320612108023531722571519492067471405656160804893645713608592561788743509876384862097871840094582513721456962354498561006793609200187065931433827465455037397503619844768415369973322759940610358415184510344945559838007474725413347675347453443583610217539704055467297318282309867987435252614428856515259899385689971172417660178761139941056839133998928898528744331662995956041897599276732929020537698559927654297185422925737241274711904687894411308774527520523946951208805307060323875839353707549772052299847176824964552693112658495961070555882583739017417359463576705453026824255338859618053086622031941

'''

参考https://mp.weixin.qq.com/s/mrho95iae_jBHGxapEp2hg

首先解一个佩尔方程
这里直接暴力枚举求解
得到x,y
然后分析下enc1,enc2 由于n ^ 3超级大 不可能直接求离散对数吧。。。
注意到mod n ^ 3 考虑二项式展开
这样n的次数>=3的直接Mod意义下就消掉了
最后得到hb1,hb2的两个简单的<=2次的方程 考虑到模数3072bit
同余可以转等式 直接利用solve解方程即可(注意这里solve的用法 不是solve(…==0,x) 而是 solve(…,x))

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
#sage
from libnum import *
from sympy import *
from primefac import *
from gmpy2 import *

x ,y= 649 ,60

n = 22970461944771505344360312103272646796516672838005008112295760406393062653512719537671401409823031480497512491850701737384621917068068328814717390355072928714618936469722031401433712342846780800586803218279291870162605299119904016959036663767093191710796830156169925350938267584422752300171293262391805105435418210827517225439398971437884496416502510866914857269951072184669675339439115587325754431761172634305242650221404868035624879538862880516438147301289746375407945908866907822940285764276956194031840381838253923392794376568293056359058519233175242523219646628321609305890926063856400793680641992567798104042179
enc1 = 26380574883568223071748995929433720836641856899148821439556557592284999544802260386919172895274884666117488851000353221957579311943624258651646692068406462392980585841604755021251430357273933800209194484692955106014890051223465745443628784077844452303995642424661442978294757109040081050794398646640530714904683097650259060507908334791761124660725589404056356987726993518057050112725483482660202442987346646160168856264312557595890710521723067518303906942469282527855551751244126251698491010628369012024332666619702895796133780038584346428759785302542637171018926824843416176876077558936427399803328577151066597396550597352625005028261156114571696860700477410270949916316951150072218466374341394892405947793726872954497972795793421222424616005278493704125169150432275472846871295341469911428057621028515874978272004775903906188556908968810828510069826724631700523623584802605889173266453916347583720706846630531082266742377818663000322817114065116737931523412220137972079139507877669106470150742546914051556747087768279286696519700220233815812834114117581332234344024169109786527295900675653245014343393093832478814567179131966404207553408747774003319241150221488231674711614902743345516888975702483348011349617017294004761259419165663633915672647187482242462163420462987034240805524991
enc2 = 21190674872507845600786632640969893237129139877891071648594239906632201421611954626926407751780936578853046780585253060958265549804784845192757301417173404074965693840282568701968464564320290763073618132775799910356101999797720378313304899173154753858674284071499775857913937184713024788245068426198878834805943703426673512761178072458895973672088230653246356764681418231485563287856188079274727706554037799748595877069143254516390328019381867648697880975670688337068196993846986940286056873616919629721264139576692806770826129279380704466982862393203486037890448173834315360975464927583664991534571518159777852793416869350127023692816051992183670690315184731534611966603509867722931839839084915943647295195314171688904055674915382434841320612108023531722571519492067471405656160804893645713608592561788743509876384862097871840094582513721456962354498561006793609200187065931433827465455037397503619844768415369973322759940610358415184510344945559838007474725413347675347453443583610217539704055467297318282309867987435252614428856515259899385689971172417660178761139941056839133998928898528744331662995956041897599276732929020537698559927654297185422925737241274711904687894411308774527520523946951208805307060323875839353707549772052299847176824964552693112658495961070555882583739017417359463576705453026824255338859618053086622031941

var('x')
ans = solve([334*x*n^2 + 1 - enc1],x)
print(ans)

var('x')
f = 1800*x*(x-1)*n*n+60*x*n+1-enc2
ans = solve(f,x)
print(ans)
hb1 = 149691910197777805350862530703771372803641869951585
hb2 = 149371042625025154522769720206540986718252215526781
flag = b''
flag += n2s(int(hb1))
flag += n2s(int(hb2))
print(flag)

运行得到flag

最后flag为

1
flag{6c6eb27a-061b-baf4-4cae26-5a609588ce}

[WEEK3]好好好！

1
2
3
4
5
6
7
8
9
***EGK*MAPZ**3TISLXYHW*B4*R*6CQV




e=65537
dp=89183181604123417010894108474901628410408206538085478807758137668201829058797702838603939730356798163745078443656032825128645105954284119126609502005130005399692420386460970318283171848176434285488698019425286328269756591931253074416895028845240978211030365697435579850343911269163064228581083838914477473793
n=17133884272385326910236146208723169235592379139078245324256146697759098524213354087333170410075813764497353656874360657828668202585141557095326829141561993608634568037533128091918704136052835609732443342167341276983343070200953604216445186924411131823487594273213380078485528148801722039459601896275130691200206027353715109606722659553700867073796386669768748305283547862565020499794358571741903375812063001390288166187510171105241363677243530996160649133253643422391688399573703498726489248479978887237752214015456924632092625018668632234215462091314384917176427670194819828555385014264912614752917792278216214856001
c=7297673446200396117470312266735704951424121735299327785232249350567349180167473433806232931862684106388722088953786183522191592452252650217579986150373463901393038386627370305688040315665037164819432754099421229466379901436696822022518438390977543864543590936753547325597766614648063328562516667604171990354928485383191174966274941678597887943784661684719053108281896697098991347034225406718530599672101743303723470910913422462764406680309933367328977341637394665138995676573466380198978810546689819954949832833954061771415463198737542769848298258925680570823701939997224167603657418270886620562332895947413332492672

dp泄露，先还原m，然后爆破得到表，来解变表Base32

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
import libnum
import gmpy2
from Crypto.Util.number import bytes_to_long
import base64
import itertools
e=65537
dp=89183181604123417010894108474901628410408206538085478807758137668201829058797702838603939730356798163745078443656032825128645105954284119126609502005130005399692420386460970318283171848176434285488698019425286328269756591931253074416895028845240978211030365697435579850343911269163064228581083838914477473793
n=17133884272385326910236146208723169235592379139078245324256146697759098524213354087333170410075813764497353656874360657828668202585141557095326829141561993608634568037533128091918704136052835609732443342167341276983343070200953604216445186924411131823487594273213380078485528148801722039459601896275130691200206027353715109606722659553700867073796386669768748305283547862565020499794358571741903375812063001390288166187510171105241363677243530996160649133253643422391688399573703498726489248479978887237752214015456924632092625018668632234215462091314384917176427670194819828555385014264912614752917792278216214856001
c=7297673446200396117470312266735704951424121735299327785232249350567349180167473433806232931862684106388722088953786183522191592452252650217579986150373463901393038386627370305688040315665037164819432754099421229466379901436696822022518438390977543864543590936753547325597766614648063328562516667604171990354928485383191174966274941678597887943784661684719053108281896697098991347034225406718530599672101743303723470910913422462764406680309933367328977341637394665138995676573466380198978810546689819954949832833954061771415463198737542769848298258925680570823701939997224167603657418270886620562332895947413332492672
for x in range(1, e):
    if(e*dp%x==1):
        p=(e*dp-1)//x+1
        if(n%p!=0):
            continue
        q=n//p
        phin=(p-1)*(q-1)

        d=gmpy2.invert(e, phin)
        m=gmpy2.powmod(c, d, n)
        print(m)
        print(libnum.n2s(int(m)))

m='7U25DUJJ7USYATEN5SREOFFG5NY57FPS77U5DFPY54JEG3NYKWSYA3YD5CXYTTNW53QS===='
base32table='ABCDEFGHIJKLMNOPQRSTUVWXYZ234567'
hint='***EGK*MAPZ**3TISLXYHW*B4*R*6CQV'
unkonwnletter=''
for i in base32table:
    if hint.find(i)== -1:
        unkonwnletter=unkonwnletter+i
print(unkonwnletter)
unkonwnletter='DFJNOU257'

# 利用itertools库中的permutations函数,给定一个排列,输出他的全排列
def allPermutation(n):
    permutation = []
    # 首先需要初始化一个1-n的排列
    for i in range(n):
        permutation.append(i+1)
    # itertools.permutations返回的只是一个对象,需要将其转化成list
    # 每一种排列情况以元组类型存储
    all_permutation = list(itertools.permutations(permutation))
    return all_permutation

Per=allPermutation(len(unkonwnletter))
# print(Per,len(Per))

for i in range(0,362880):
    templist=Per[i]
    temstr=''
    for j in range(0,9):
        temstr=temstr+unkonwnletter[templist[j]-1]
    tempbase=temstr[0:3]+'EGK'+temstr[3]+'MAPZ'+temstr[4:6]+'3TISLXYHW'+temstr[6]+'B4'+temstr[7]+'R'+temstr[8]+'6CQV'

    # base64.b32decode(m.translate(str.maketrans(tempbase, base32table)))
    outcome=base64.b32decode(m.translate(str.maketrans(tempbase,base32table)))
    # print(outcome)
    oc=str(outcome)
    if 'flag' in oc or 'ctf' in oc :
        print(oc)

运行得到flag

最后flag为

1
flag{fa48a440-d0ff-0c2a-366243-a46b7e7853}

[WEEK3]easyrsa

output.txt

1
2
3
4
5
n1 = 105813626754830369767796578799226643889033227412658130226893708851110720416468059965713264658478299377654212587044247669928410442281831382577490105352633718272894531572352233211881056495752193201866649055622358234888531194346296702453105176147272971386928767457928148705433435309063146652094354833396307613911
n2 = 20369481027961668058257949652346266097405331865071244844827896944882851755421021125005038786750268341013032202394581223828526073179263634639721089663050687773353438686984875196973012077948955566738301337866191557952973517042420660699281973702694965572488938789954679350791243570953680441483360036599350550534192027759384675611155970913348616382186229565994100357427843446265863186624731991521034305958565644266001622849342042747046352413268149901263629515623929619659379883036239511300563910486156582808698915297257307692017642458823600500445082987244477251123335410633989767118317681371314078169733374888688620813839
leak1 = 110733171993470709195465104383246525062178362778220972191726705114514369848757940664883819735824778128179586221599072975207093223575285541338555960658178287486722693023393688158120847028382
enc = 3724360314735337348015983350518926695244720487101059718828225257324872465291143851090607580822961202894850524395217010317254775500983396154162166500198523991652838543842978138662752717532358799622372813160573374563924704242911344052149200174619645796187521459916955545794017698320367273671936314947729523150627463505338870024421481261166504454532278895870561732979282672259730923724762173494886613682487373643406390205027508946750313076817576295795818790961232101069994823561840743308871216879655652136743807002025483269687509388947008928281179566366429525183899914275273098400627187051739816901887290337980735995613
c = 38127787578353827234498259231834082660893046004292279030517959465543348558091033172704284501791369355347078715874056471582324178524957666710131669794646539355849074198396968523041568909435662208846480656877184197877122598569708545477705274221697660270808685794034776172296500330563270867517390911486555286886

task.py

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 *
from flag import flag

p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1 * q1

e = 65537

p2 = getPrime(1024)
q2 = getPrime(1024)
n2 = p2 * q2

leak1 = (p2+q2) >> 400
leak2 = (p1 & ((1 << 350) - 1)) >> 5

enc = pow(leak2,e,n2)
c = pow(bytes_to_long(flag),e,n1)
f = open(f'output.txt','w')
f.write(f'n1 = {n1}\n')
f.write(f'n2 = {n2}\n')
f.write(f'leak1 = {leak1}\n')
f.write(f'enc = {enc}\n')
f.write(f'c = {c}')
f.close()

参考2023 贵阳大数据安全精英赛 — Crypto childrsa wp_贵州网络安全大赛childrsa-CSDN博客

两次rsa，可以根据leak1=(p2+q2)>>400求出得到p2,q2，然后求出leak2,再根据leak2求p1

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
n1 = 105813626754830369767796578799226643889033227412658130226893708851110720416468059965713264658478299377654212587044247669928410442281831382577490105352633718272894531572352233211881056495752193201866649055622358234888531194346296702453105176147272971386928767457928148705433435309063146652094354833396307613911
n2 = 20369481027961668058257949652346266097405331865071244844827896944882851755421021125005038786750268341013032202394581223828526073179263634639721089663050687773353438686984875196973012077948955566738301337866191557952973517042420660699281973702694965572488938789954679350791243570953680441483360036599350550534192027759384675611155970913348616382186229565994100357427843446265863186624731991521034305958565644266001622849342042747046352413268149901263629515623929619659379883036239511300563910486156582808698915297257307692017642458823600500445082987244477251123335410633989767118317681371314078169733374888688620813839
leak1 = 110733171993470709195465104383246525062178362778220972191726705114514369848757940664883819735824778128179586221599072975207093223575285541338555960658178287486722693023393688158120847028382
enc = 3724360314735337348015983350518926695244720487101059718828225257324872465291143851090607580822961202894850524395217010317254775500983396154162166500198523991652838543842978138662752717532358799622372813160573374563924704242911344052149200174619645796187521459916955545794017698320367273671936314947729523150627463505338870024421481261166504454532278895870561732979282672259730923724762173494886613682487373643406390205027508946750313076817576295795818790961232101069994823561840743308871216879655652136743807002025483269687509388947008928281179566366429525183899914275273098400627187051739816901887290337980735995613
c = 38127787578353827234498259231834082660893046004292279030517959465543348558091033172704284501791369355347078715874056471582324178524957666710131669794646539355849074198396968523041568909435662208846480656877184197877122598569708545477705274221697660270808685794034776172296500330563270867517390911486555286886
e = 65537 
 
#leak1 = (p2+q2) >> 400
RF = RealField(2048) #2048位精度实数
X = polygen(RF)
f = X*((leak1<<400)-X) -n2 
P_high = int(f.roots()[1][0])
#P_high = (P<<410)>>410    #未知部分400位,但会有进位影响
PR.<x> = PolynomialRing(Zmod(n2))
f1 = x + P_high 
x0 = f1.small_roots(X=2^410, beta=0.4)[0]
p2 = f1(x0)
print(n2%p2)
 
p2 = 151399048655298148018688323609718705920605086712318698086250277971491481779504840614471253946764630599745412866850500656954922361816231030123945084396794404269982437117950486373905356265950808460057643971210951709676705550508291196476405125057071271317182732652055355984683359771176148502822187125614565868259
q2 = 134541671225018271403953787373408507465730892003631249716123043010464351342881237505189677861071006923092011330983761091184598196512437449946447759771425031294468141216072218813533336313651823171925311705682558765317115569680736707328403560829555033008387085671352235353814183291570781754064065104600110875621
#enc = pow(leak2,e,n2)
leak2 = pow(enc,inverse_mod(e,(p2-1)*(q2-1)), n2)
#leak2 = 22334810767801800995021872014176778873829048161801414909315794486047873481911273730826962574216771288781
 
#leak2 = (p1 & ((1 << 350) - 1)) >> 5
for i in range(32):
    p1_l = (leak2<<5) + i
    P.<x> = PolynomialRing(Zmod(n1))
    f = x*2^350 + p1_l 
    v = f.monic().small_roots(X=2^(512-350), beta=0.4)
    if v != []:
        x0 = v[0]
        p1 = f(x0)
        print(p1)
        p1 = int(p1)
        q1 = n1//p1 
        break 
p1 = 11239391699442192016394616757221620834717629054697859972076207292592548525033647125013001671320452447403380966370885392089905799108483165855335320142731687
q1 = 9414533240271523909175466549989578413560381929724653857969276831718175551727032446390484582550970699995107874013408751551550726534204653674601330352393553
 
#c = pow(bytes_to_long(flag),e,n1)
flag = pow(c,inverse_mod(e,(p1-1)*(q1-1)),n1)
bytes.fromhex(hex(int(flag))[2:])

运行得到flag

最后flag为

1
flag{9995eae8acaac286c7b72e50e5258dc3}

[WEEK3]ECC

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
from Crypto.Util.number import bytes_to_long ,getPrime
from random import randint
from secret import flag , p, A, B
class LCG:
    def __init__(self, seed, multiplier, increment, modulus):
        self.state = seed
        self.multiplier = multiplier
        self.increment = increment
        self.modulus = modulus

    def round(self):
        self.state = (self.state * self.multiplier + self.increment) % self.modulus
        return self.state

LcG = LCG(p, A, B, getPrime(300))
hint = []
rounds = randint(9,999)
for i in range(rounds):
    hint.append(LcG.round())

print('N =', LcG.modulus)
print('hint =', hint[rounds-3:])
print('rounds =',rounds)

m = bytes_to_long(flag)
E = EllipticCurve(GF(p),[A,B])
P = E.random_point() 
Q = m*P

print ('P:',P)
print ('Q:',Q)


# N = 1125392927988753896854987957148056354386201827125826069477430909854868805443615107220135227 
# hint = [825813301880753373732934814247174237721328354873363505242992660466604295345057194572371404, 193506213000330656490077191285643229375552421315935920380892315144744168185305147553188913, 781344433110886833161070243607022756966332440670095586827286027916242665663408020350654624]
# rounds = 115

# P:(619326880264692377569802611646224559591538974546589002470546562638173936726 : 81627180675445791425374987242866450950481926359435412640524431271834119975628 : 1)
# Q:(87681515903238224431774052699069990150932842506415240241654023140523858249426 : 88769930715686795609594132659431641447201063838148146744733325748739313420051 : 1)

先解LCG得到椭圆曲线的参数，然后发现椭圆曲线的阶和p一样，运用SmartAttack

exp1:

1
2
3
4
5
6
7
8
9
10
11
12
13
N = 1592666040773288237864960405116272477285413902052528659895355898525096633482218848317798659 
hint = [1394593694312257895786772657718236632208180081954584278582726499587495471046605157854010244, 957352598346966110459998186901601582694524293959852393538910343072839464237771546151573955, 693812013080850001623907916411861671437064059415845429735416503191943824861563095835885411]
rounds = 483

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
A=(hint[2]-hint[1])* MMI((hint[1]-hint[0]),N) % N
ani=MMI(A,N)
B=(hint[1]-A*hint[0])%N
seed = (ani*(hint[0]-B))%N
for i in range(rounds-3):
    seed = (ani*(seed-B))%N
p = seed
print(p,A,B)

拿到p，发现 E.order()==p

椭圆曲线的阶和p相等

exp2:

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

N = 1592666040773288237864960405116272477285413902052528659895355898525096633482218848317798659 
hint = [1394593694312257895786772657718236632208180081954584278582726499587495471046605157854010244, 957352598346966110459998186901601582694524293959852393538910343072839464237771546151573955, 693812013080850001623907916411861671437064059415845429735416503191943824861563095835885411]
rounds = 483


MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
A=(hint[2]-hint[1])* MMI((hint[1]-hint[0]),N) % N
ani=MMI(A,N)
B=(hint[1]-A*hint[0])%N
seed = (ani*(hint[0]-B))%N
for i in range(rounds-3):
    seed = (ani*(seed-B))%N
p = seed
print(p,A,B)


E = EllipticCurve(GF(p),[A,B])
P = E(22848890707179000954203658007030229334930230033288546935111873538205494755744  , 15625318813860427793184320591571256965351190504127303241852375250972299079519 )
Q = E(47068429748309827354877617860222778745533747650312830303181668257713524033902 , 54803159468735797341287321575486297217260035098908326234825325428617201791330 )
def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

r = SmartAttack(P, Q, p)
print(r)

print(long_to_bytes(int(r)))

最后flag为

1
flag{7h4t5_E4SY3sT_ecc_E4s5G8}

SHCTF2024

[Week1] EzAES

题目描述:

1
2
3
4
最最简单的AES

hint：
如果记事本打开乱码，请使用UTF8编码打开

源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Cipher import AES
import os

iv = os.urandom(16)
key = os.urandom(16)
my_aes = AES.new(key, AES.MODE_CBC, iv)
flag = open('flag.txt', 'rb').read()
flag += (16 - len(flag) % 16) * b' '
c = my_aes.encrypt(flag)
print(c)
print(iv)
print(key)
'''
b'2]\x80\nV\x8c\x13\x96\x98\xea\x9d<\xe9\x0e"M\xd8\x05g\xee\xdd\x01\x13\xbds\xe6\xf9PC1\xd2\xc6\xce\x1b\xf1+_=\x95\x1c\x02Q\xa0j\xfd\x82\x12\xfb'
b"\xc9\xe5z\x00\xb9\xb5')W\xb8\xf3\xf6\x92\xa1\xf1\xae"
b'D\x88\xaaID\xe3[\xd0\xde\xe8\xc2Oq\xa4\x1b\x9b'

iv，key都给了直接解即可

exp：

1
2
3
4
5
6
7
from Crypto.Cipher import AES
import os
c=b'r~\xf7X\x02\xfa\xa2\xdeQxeEMt\t\xa1\xb3zP\xf9|]\xbc}\x08\x135k\xccQM\xc7\x1d\x88"\xf3\x1fZ\x10\xeaf\x08\x84\xb4\x17\xd9\xf0g'
iv=b'\xc2\x0f)\x90\x05\xc8\xc7\x1d\xdaw\xce\xef\x1c\xad\x94\x82'
key=b'\xc1%L\xde^G\xd5\xd1\x0bL\x8c\x8e\x8a]\xe5x'
my_aes = AES.new(key, AES.MODE_CBC, iv)
print(my_aes.decrypt(c))

运行得到flag

最后flag为

1
SHCTF{c447cb1d-95eb-4f75-9981-34fac0b0ea40}

[Week1] Hello Crypto

题目描述:

1
你好，现代密码学

源码:

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import bytes_to_long
from secret import flag

m = bytes_to_long(flag)
print("m =",m)

# In cryptography, m stands for message, also plaintext
# so, why this m is number?
# decrypt this Message to get flag!
# m = 215055650564999214432481721620349452551335695400264927572015727788155305524804669987176578958480868587462065269077477385341

题目将bytes类型转换成了long，使用long_to_bytes()还原即可

exp：

1
2
3
from Crypto.Util.number import *
m=215055650564999215579245928124952980123288513022545529850203187480529839299468491786758554221504598006880888099480186348157
print(long_to_bytes(m))

运行得到flag

最后flag为

1
SHCTF{He1Lo_C71er_w31cOM3_t0_CRYP7O_wOrLD_S8524O7b}

[Week1] baby_mod

题目描述:

1
模 = mod

源码:

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 enc import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
r = getPrime(777)
t = getPrime(777)
tmp = getPrime(15)
e = 65537
n = p*q
print(f"c = {pow(m,e,n)}")
print(f"leak = {p*r-q*t-tmp}")
print(f"r = {r}")
print(f"t = {t}")
'''
c = 35857366982775001163709706329132332129198562983552555511448083061094074669367979015502333655278358684215098932326553825603777958659467839552023261967262155060047349317949372168443797925987589341141784363926818023942586766459965585442275161660496483943439811305741403600798781521493945596720341427195652558982
leak = -5107674358711210737882494560600732791250179840213777878888742767072553601532851356174469874415525598099784626254736798887864004592486656924693910840719154658345309893577671078559048443103458488949868885242719962169826277868747448883258671173380665395991841102565616620599430325928316062708093158365313039616780800181953903262119219194662255877127252423803664500326116132967895674755318333
r = 427739103077047625426916895132281505001313159709352606025959054820813531804226670721756929096768625197253280880742580777066841078876572635973636127334499956675238416213015698247320484024411157066485154540723957147830456103921568392463
t = 773129208699516655257957729253412604551004875734627930238689617634544979256037522273993830764784153590420820657543888389030152966691534764852115784862118761663077170184672486097878417040033408467378713210212052027822419477186926443517
'''

mp的位数很短，可以直接爆破，然后简单通过逆元运算还原一下p，q，最后解rsa即可

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
c = 65265123447008258739823881253712618855743207785592071810644071874471454798965431864181558270515969975401779411159259620667145535502782388827453948759536453090157143513842262984080955436790285942593808080674810671659937071774640340301058624158681806442296843209117027874540870493389811029485723774603940459931
leak = -1881106132641375766133152112994342828119507378423559202061011439431676741051181472792518761177923228320675561642303505560173244613826660782873926155801303026571840606723122154327074309447021178342715055202519901129413832136624928053700924802374945948348465888722289137690374416181636017104657953399802111144453712033848995292512199872962369387501841940260849404025832310508178966959630599
r = 689839718515414045347531054798592836275085962314657856397942159221016166456189623820611888405075883279780102461231672312404949575925749307043031295884384652026524084689147502352355810597083171521378638677978233709474271040306038502549
t = 647727769527784822813022490299374784755946413414746266210566017574837948278435467708771115603807186721672249532692759668966009734084189972055937240072075537738265026402349477053316703320748318615949497601429699712749230261751610326943
from Crypto.Util.number import *
for tmp in range(2**14,2**15):
    if(isPrime(tmp)):
        a=(leak+tmp)%t
        p=(inverse(r,t)*a)%t
        if(isPrime(p)):
            q=(p*r-tmp-leak)//t
            d = inverse(65537, (p-1)*(q-1))
            m = pow(c, d, p*q)
            if(b"SHCTF" in long_to_bytes(m)):
                print(long_to_bytes(m))

运行得到flag

最后flag为

1
SHCTF{fb11d39d-b8c4-4383-b97e-879e174350da}

[Week1] d_known

题目描述:

1
I have already given d

源码：

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

m = bytes_to_long(flag)
p = getPrime(1024)
q = next_prime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(m, e, n)
print(c)
print(d)

'''
c = 7213195970946414494399936005853857718667183289002657745425826899675505345092410605306273256707139098406806877866783808225699699153131518431058837041898056635569462573018269354822073724073186863406695022867486589182929956653958688868914980841766248650873362702654070654099196728093121739048898877974090285416322377748172401439445013712171771290791764561786363083491903500516498779936218437731816689640378835101004444325311935444361117867298206427260685502890826985072360523550983696868343672260058703115516420868602347194939498566092792298332593157486811902508956916646508566101952913802328259951922032875243261746398
d = 11374161004143224297857427972123650051817838266744954985176449803443993639681829350421670096244079413680651354438570218232399810991059271154140489557252022338073865604314293892339861008006618141349894409084809998582948313432672960456743754281343481937261375000507562174065065880906720832053362364083365904266644557726250401471556412448254288945122405181998702767640084770161015136589322854284878886197014034178702935041751464665012249646921403796241758544943898602305756124625964412171765129448039702672032125162007935162528269764600731791450129712120059202127541295803978007131688606036996619262039597789584178465781
'''

给了d，e没有给n，我们可以通过式子e*d=kphi+1去爆破k，然后计算p，q从而恢复n，phi在2048位左右，ed-1在2062位左右，所以k在14位左右

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
c = 13998366132734013319249048018499721727403050055254830737165179815983174285094393811325317317707128169153747434539118667623037019064533046594022573065875581294785385142093123366582995660562519940300917436620199974944002032196285634314609637977477434533746886235396111536255895390881412677753832625863390895836662350922697007715599509322861755480647929903940260628645583640152138179517885654751583490965972388372271554280530740511905338458340643029412576307967139635209283971616883255921829012138299312649474227584899470833990216120417712813771473123864504615899719024784578351759126535133249810557879432468662111246756
d = 6186307221105193352691057064378083444102547927738467465977546108536504224736220521681776623838157046814488098519802281948740570876242421910761870223095950497932655227854763895791142746073533615758212149012339780764791952070111547882806078367662018142231111368026760745780001429632626690120267713461833155263999190169323361616261471171466376850603039245760941631447279085661336021231244447002160296108132410418096192785324911387745606685573373927641181915986750527672891859352431803724080648873404129461871440807973918135937518755071755788371017542741975270811592593185041832523882700159301503991521722975840533177473
e=0x10001
from Crypto.Util.number import *
import sympy.crypto
import gmpy2
e_d_1=e*d-1
p=0
q=0
for k in range(pow(2,14),pow(2,15)):#k的位数可通过e*d-1和p*q的位数判断大概
    if e_d_1%k==0:
        p=sympy.prevprime(gmpy2.iroot(e_d_1//k,2)[0])
        q=sympy.nextprime(p)
        if (p-1)*(q-1)*k==e_d_1:
            n = p * q
            m = gmpy2.powmod(c, d, n)
            print(long_to_bytes(m))
            break

运行得到flag

最后flag为

1
SHCTF{05b67275-2d96-4347-935d-0190d07be011}

[Week1] factor

题目描述:

1
factor and combination

源码：

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

m = bytes_to_long(flag)
e = 65537
def prod(iterable):
    result = 1
    for num in iterable:
        result *= num
    return result
prime_list = [getPrime(64) for _ in  range(10) ]
N = prod(prime_list)
p_list = random.sample(prime_list,7)
n = prod(p_list)
c = pow(m,e,n)
print(f"c = {c}")
print(f"N = {N}")
'''
c = 21099412508066134448833601327531130254841970307583743440904427862261018157661704095318489657585060412937329404596855083064223128884217
N = 196486093018693545881219604198701182153503448356179877871459414937506610219572314388331866984271195629379318545940521489711575171183252048175771478816736376926623376026779460050211170712705761
'''

yahu可以分解N，然后调用函数排列组合一下n的所有情况解rsa即可

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c = 80038347277707557882787621949903452127505520309886916983104635131036184133624980068763353920983104291651397984336218086685818505948467
N = 559704346214144849792849530805862849762498088797002489893146572384205039174770967158398367639001657471766106887193926875072019608438590249173683560795647756077002146916428951021908930523828157
prime=[15403782804101998057,18103658262367718303,13866126321230022239,18102062360713946731,11273373202499290079,12433538555022691247,11660765547174259697,17748239951194552549,15895608218623897717,17340978744243565351]
from itertools import *
from Crypto.Util.number import *
n=list(permutations(prime,7))
for i in n:
    nn=1
    phi=1
    for j in i:
        nn*=j
        phi*=j-1
    d=inverse(65537,phi)
    m=pow(c,d,nn)
    if(b"SHCTF" in long_to_bytes(m)):
        print(long_to_bytes(m))
        break

运行得到flag

最后flag为

1
SHCTF{bf2fced0-c929-4a16-9747-0a277fb0b6b1}

[Week2] E&R

题目描述:

1
ECC and 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
25
26
27
28
29
#sage
from Crypto.Util.number import *
from secret import flag

flag = flag[6:-1]
l = len(flag)
m1 = bytes_to_long(flag[:l//2])
m2 = bytes_to_long(flag[l//2:])
#RSA
p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65537
r_q = int(bin(q)[2:][::-1] , 2)
leak = p ^^ r_q
c = pow(m2,e,n)

#ECC
E = EllipticCurve(Zmod(n),[114514,1919810])
G = E.lift_x(Integer(m1))
P = G * e
print(f'leak = {leak}')
print(f'n = {n}')
print(f'c = {c}')
print(f'P = {P}')
# leak = 5599968251197363876087002284371721787318931284225671549507477934076746561842
# n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
# c = 6803450117490196163076010186755045681029929816618361161925865477601994608941714788803007124967390157378525581080320415602012078322064392991884070073083436
# P = (4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627 : 3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519 : 1)

参考https://tangcuxiaojikuai.xyz/post/342113ee.html

「已知条件：」

  • p 与 q 的反方向二进制的异或值，共256bit，记为pxorq

「搜索方式：」

  • 从两端向中间搜索
  • 每一次搜索，需利用当前 pxorq 两端的bit位。这是因为，pxorq 的当前最高位对应p的最高位及q的最低位，pxorq 的当前最低位对应p的最低位及q的最高位 (其中最高、最低均是对于当前搜索而言)
  • 如果当前需搜索的最高位为”1”，则对应两种可能：p该位为1，q对应低位为0；p该位为0，q对应低位为1。剩下依此类推

「剪枝条件：」

  • 将p、q未搜索到的位全填0，乘积应小于n
  • 将p、q未搜索到的位全填1，乘积应大于n
  • p、q 低 k 位乘积再取低 k 位，应与 n 的低 k 位相同

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

pxorq = 5599968251197363876087002284371721787318931284225671549507477934076746561842
n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
c = 6803450117490196163076010186755045681029929816618361161925865477601994608941714788803007124967390157378525581080320415602012078322064392991884070073083436
e = 65537
pxorq = str(bin(pxorq)[2:]).zfill(256)


def find(ph, qh, pl, ql):
    l = len(ph)
    tmp0 = ph + (256 - 2 * l) * "0" + pl
    tmp1 = ph + (256 - 2 * l) * "1" + pl
    tmq0 = qh + (256 - 2 * l) * "0" + ql
    tmq1 = qh + (256 - 2 * l) * "1" + ql
    if (int(tmp0, 2) * int(tmq0, 2) > n):
        return
    if (int(tmp1, 2) * int(tmq1, 2) < n):
        return
    if (int(pl, 2) * int(ql, 2) % (2 ** (l - 1)) != n % (2 ** (l - 1))):
        return

    if (l == 128):
        pp0 = int(tmp0, 2)
        if (n % pp0 == 0):
            pf = pp0
            qf = n // pp0
            print(pf)
            print(qf)
            phi = (pf - 1) * (qf - 1)
            d = inverse(e, phi)
            m1 = pow(c, d, n)
            print(long_to_bytes(m1))
            exit()

    else:
        if (pxorq[l] == "1" and pxorq[255 - l] == "1"):
            find(ph + "1", qh + "0", "1" + pl, "0" + ql)
            find(ph + "0", qh + "0", "1" + pl, "1" + ql)
            find(ph + "1", qh + "1", "0" + pl, "0" + ql)
            find(ph + "0", qh + "1", "0" + pl, "1" + ql)
        elif (pxorq[l] == "1" and pxorq[255 - l] == "0"):
            find(ph + "1", qh + "0", "0" + pl, "0" + ql)
            find(ph + "0", qh + "0", "0" + pl, "1" + ql)
            find(ph + "1", qh + "1", "1" + pl, "0" + ql)
            find(ph + "0", qh + "1", "1" + pl, "1" + ql)
        elif (pxorq[l] == "0" and pxorq[255 - l] == "1"):
            find(ph + "0", qh + "0", "1" + pl, "0" + ql)
            find(ph + "0", qh + "1", "0" + pl, "0" + ql)
            find(ph + "1", qh + "0", "1" + pl, "1" + ql)
            find(ph + "1", qh + "1", "0" + pl, "1" + ql)
        elif (pxorq[l] == "0" and pxorq[255 - l] == "0"):
            find(ph + "0", qh + "0", "0" + pl, "0" + ql)
            find(ph + "1", qh + "0", "0" + pl, "1" + ql)
            find(ph + "0", qh + "1", "1" + pl, "0" + ql)
            find(ph + "1", qh + "1", "1" + pl, "1" + ql)


find("1", "1", "1", "1")

运行得到

第二部分是ECC，曲线在模n上的阶不好直接算，而n = pq，那么我们可以分别构建在模p和模q上的曲线，然后分别计算其阶，进而得到曲线在模n上的阶，接下来就计算出e对于曲线的逆元求出点G，其横坐标即为flag部分

exp:

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

p = 64760524083545528318139240449356269097871629401328435356643510319660757701117
q = 109947782034870726628911928816041880655659770652764045401662566933641952899777
e = 65537
n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
E = EllipticCurve(Zmod(n),[114514,1919810])
Eq = EllipticCurve(Zmod(p),[114514,1919810])
Ep = EllipticCurve(Zmod(q),[114514,1919810])
P = E(4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627,3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519)

phi = Ep.order()*Eq.order()
d = inverse_mod(e,phi)
G = P*d
x = G.xy()[0]
flag = long_to_bytes(int(x))
print(flag)

运行得到

最后flag为

1
SHCTF{a67b2a9b-0542-4646-908f-7c002c687387}

[Week2] pading

题目描述:

1
pading

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import gmpy2
flag = b'SHCTF{********}'
assert len(flag) == 39
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x3
pad = b'a_easy_problem'
c = pow(bytes_to_long(flag + pad),e,n)
print(f'n = {n}')
print(f'c = {c}')
'''
n = 67219682521889611200535740700046034591278684417245884022626251453613750726649388729365893941338791019347350801693059880007369876453267730593111137953064615807027757344395502702406776487798831111522462657078919839757324535769045997675231103438079624202976125755572726027118465249485833502062909286699717648971
c = 6625793114740414141092936144768053994988173765784117221183180050633237248002752082604284135985358968626643292590263617643508394334790647151294197710216884421870709940171611555343059583922633618665803317378004094563800335551672054740340815095435990804050447839173637531531052786989637260725728540269251733602
'''

cooper求解

exp:

1
2
3
4
5
6
7
8
9
10
11
12
import libnum
n = 101194231761192803646875794770841105131876105333404505987513576849142365482512109876401629071314564545841743473668262668053559550015874646299248232349238400201145583346187330958825878235324968882794481192056169683711007095999439320830763275487477094590502701333963154552470777678553556993349171608134555815527
c = 54067443511581567434123971345564905390315631873898717856316286990552318113901362505672245448553258416669456882532743580961176229271906817289588426185966004215569829572814038485471312399063659287164712291139771809733004385057875146223151700601326161190474536508680332925332614914475852998934930375151571163346
e = 0x3
pad = b'a_easy_problem'
PR.<x> = PolynomialRing(Zmod(n))
f = (x * 256 ** len(pad) + libnum.s2n(pad)) ** e - c

f = f.monic()
root = f.small_roots(X=2 ** (39 * 8),beta=0.9,epsilon=0.03)
print(root)
print(libnum.n2s(int(root[0])))

运行得到flag

最后flag为

1
SHCTF{aRE_yOu_pADddin6_mE_6OY_3cC65T9E}

[Week2] worde很大

题目描述:

1
坏了，遍历不了了

源码：

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = getPrime(200)
d = gmpy2.invert(e,(p-1)*(q-1))
dp = d % (p-1)
c = pow(m,e,n)

print(f"n = {n}")
print(f"c = {c}")
print(f"e = {e}")
print(f"dp = {dp}")
'''
n = 97739581889632954234601858759571081789754504672329469738269643858628171179979321162815724769763412619658408405561478415765157611834487029518603453949039811351774714269236098042747462249483159920892787880824947161619349365408723745597374900248853539355902068757352718380757435102982626591377274232865521423593
c = 26095643922655432035645565370397905490618809009650196884320884690932728598472348373974111279047676471785244145462027954594592764745880778338322677944627577258518907083319422813654909740872087096442399700413016570335466727074072995067816630078330581839031275625322409682728582976462918057471689932076496248561
e = 1058438161083937018846240581507476333099964317214574618899221
dp = 6623881351846499714531478675982358905817722714244973535482245648175040985521546527487014125094982161277969708987494393354573825274342203928772386877484365
'''

dp泄露，e很大，使用费马小定理

exp:

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from gmpy2 import *
n = 137936518212795016631995520838472302149141790253254063746644690789087238703518209864090400488867329204081462188070717686809252787882402936392955629363437184771842206953074183149138159637950191923912242531961311599662318655990865727657664205013000939289803471731705713740024391474024499546638888872254845182913
c = 121609905093326965529278560764503008737291822872196092526081697008572697757921850313770648096987000708617211869169540739201090558646483774562605091601996034685597344346173308271051378164676552111608917552372843867408949249508989974751671092015244566198448302722139817527780990490118285683385534014911565099055
e = 1475558511269133981422224090204112278405693168473364430129339
dp = 8218282983473677655187341896314032453994259573173123901161646379674688283023199060920450160589079068624519308615175274441217089076660114575658298351670291
 
p=gcd(pow(2,dp*e,n)-2,n)
print(long_to_bytes(pow(c,dp,p)))

运行得到flag

最后flag为

1
SHCTF{w0Rd_E_yoU_dlAN_DA_512AdE}

[Week2] 魔鬼的步伐

题目描述：

1
在这光滑的地上摩擦，摩擦是魔鬼的步伐

源码：

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

m = bytes_to_long(flag)
def get_primes(limit):
    primes = []
    is_prime = [True] * (limit + 1)
    for num in range(2, limit + 1):
        if is_prime[num]:
            primes.append(num)
            for multiple in range(num * num, limit + 1, num):
                is_prime[multiple] = False
    return primes

def get_Prime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 65537
primes = get_primes(e)
p = get_Prime(512)
q = get_Prime(512)
n = p*q
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
'''
n = 191391402321228989848155650067508199812678899282682122972025905368468768560184422674261799388520495661779976374235493058962832462315523086047824395094709035265668669747388593473248973494351185574014025479557832664755858051300171898648320930506613240827056482673798009478558230762422107733716790153457531744221
e = 65537
c = 156885505675405519969445340645816863312190799955985515608142981757756621179440280697590392519375729966582551238002395565882926385298560533937698387435154919654508221842499369407453141585375956692070619745212788641357237448133434888343210717508713960076983647435375611441985514004471103496212280381251986017661
'''

p-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
from Crypto.Util.number import long_to_bytes
from math import gcd

def pollard_p1(n):
    a = 2
    for i in range(2, 100000):
        a = pow(a, i, n)
        d = gcd(a - 1, n)
        if 1 < d < n:
            return d
    return None

n = 2831832791030609530715813213220019883048914189158756797307958158408447051630508377374040550762130532585789257283656903976093710799661936572635199760487152921738463539735395878201301223666364287975878427298711981759489133322514450542491313745324153974993874104970865609328318781784747005428502998650052645698811657
e = 65537
c = 277886534227205145921457730106662348869574033254759302593748922500501707927099574576237860088700790266316998558285705873756211980752787668038757766667343292786435728705389634346196021354871807428435121426405798244396230131921055698729045936487882618606410991938850305317286706006559422640483458860444177938881800

# 使用 Pollard's p-1 算法来因式分解 n
p = pollard_p1(n)
q = n // p

phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

m = pow(c, d, n)

flag = long_to_bytes(m).decode()

print(f"Decrypted flag: {flag}")

运行得到flag

最后flag为

1
SHCTF{FRIctIoN_1S_7hE_d3vils_s7ep_8D}

[Week2]ezECC

题目描述:

1
ecc简单哎

data.txt

1
2
3
4
p =  9799485259524549113003780400336995829253375211044694607315372450399356814285244762186468904824132005209991983177601498069896166228214442123763065076327679
k =  73771953838487511457389800773038323262861649769228176071578897500004883270121
A1 =  (5945412329827707694132352090606154232045921322662767755331097180167148601629747751274580872108985870208681845078153424348847330421799769770041805208089791 : 4113102573821904570542216004200810877456931033522276527318388416329888348077285857968081007666714313806776668203284797556825595791189566621228705928598709 : 1)
C = (2336301464307188733995312208152021176388718095735565422234047912672553316288080052957448196669174030921526180747767251838308335308474037066343018337141276 : 6868888273736103386336636953449998615833854869329393895956720058438723636197866928342387693671211918574357564701700555086194574821628053750572619551290025 : 1)

ezECC.py

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 flag import flag

assert flag.startswith(b'SHCTF{')

m = next_prime(bytes_to_long(flag))
p = getPrime(512)
a,b = getPrime(128),getPrime(128)
E = EllipticCurve(Zmod(p),[a,b])
k = getPrime(256)
A1 = E.random_point()
A2 = A1*k
M = E.lift_x(m)
C = M+A2

print('p = ',p)
print('k = ',k)
print('A1 = ',A1)
print('C = ',C)

已知A1和C两个在曲线上的点和曲线的p值，根据曲线

y^2=x^3+ax+b mod p

两个式子相减求得a和b值。构造曲线，由于C = M+A2，且A2 = k*A1，A1和k值都已知。M = C-k*A1求得M的值。由于M的x坐标是明文m的下一个素数，爆破即可：

exp:

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 *

p =  9799485259524549113003780400336995829253375211044694607315372450399356814285244762186468904824132005209991983177601498069896166228214442123763065076327679
k =  73771953838487511457389800773038323262861649769228176071578897500004883270121
A1 =  (5945412329827707694132352090606154232045921322662767755331097180167148601629747751274580872108985870208681845078153424348847330421799769770041805208089791,4113102573821904570542216004200810877456931033522276527318388416329888348077285857968081007666714313806776668203284797556825595791189566621228705928598709)
C = (2336301464307188733995312208152021176388718095735565422234047912672553316288080052957448196669174030921526180747767251838308335308474037066343018337141276,6868888273736103386336636953449998615833854869329393895956720058438723636197866928342387693671211918574357564701700555086194574821628053750572619551290025)

a = inverse(A1[0]-C[0],p)*((A1[1]**2-A1[0]**3)-(C[1]**2-C[0]**3))% p
b = (C[1]**2-C[0]**3-a*C[0])%p

E = EllipticCurve(Zmod(p),[a,b])
A1 = E(A1)
C = E(C)
M = C-k*A1

mm = (M.xy())[0]
for i in range(292):
    m = long_to_bytes(int(mm-i))
    if m.endswith(b'}'):
        print(m)

运行得到flag

最后flag为

1
SHCTF{fo1und_adm1n_1st111}

[Week3] Approximate_n

题目描述：

1
知道n相似值，能怎么办呢

源码:

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

class gen_AGCD():
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)

    def enc_(self,M,e):
        C = pow(M,e,self.p*self.q)
        return C

    def re_n(self):
        n = self.p * self.q
        return n

    def re_approximate_n(self):
        k = getPrime(512)
        r = getPrime(247)
        n_approx = k*self.p + r
        return n_approx

if __name__ == '__main__':
    e = 65537
    m1 = flag[:len(flag)//2]
    m2 = flag[len(flag)//2:]
    Encrypt1,Encrypt2 = gen_AGCD(),gen_AGCD()
    C1,C2 = Encrypt1.enc_(bytes_to_long(m1),e),Encrypt2.enc_(bytes_to_long(m2),e)
    N1,N2 = Encrypt1.re_n(),Encrypt2.re_n()

    N1_reveal = []
    for i in range(3):
        N1_reveal.append(Encrypt1.re_approximate_n())

    N2_reveal = Encrypt2.re_approximate_n()

    print('N1 = ',N1)
    print('N1_reveal = ',N1_reveal)
    print('N2 = ',N2)
    print('N2_reveal = ',N2_reveal)
    print('C1 = ',C1)
    print('C2 = ',C2)


N1 =  154883139856627938801258055572977220654436379062666376789356914300085976240128659149752074764643476500074796800488895828728433332181624971921429284434579225801336541489342935332238702961125804962878554927100141412713650044001032012246708262401946764189434647278591395045151315835552961804356205100470027503191
N1_reveal =  [164933966102699012367418601279996770022415771139213506820934866452049102845745760600942770703912200527848725573588451812027778458969685089784921662517652154169167484869589930610567943842955374649729223042222494436287132155794683413874833856926844440019261036752686751460092869804858499160736190132217569789592, 131046165080354811554495951056464017791716097134011211676424662523011784062527704336124166904578723996429892251136670201639532620417588200069401011811978782585301486923242086514080273998076338127056451169001194768189302460368517901241306503197311526846869073812402757974300787564589628102906328365913632430854, 86279088143399467277083162720862225017506665297700928231548301647578976104561754525275823538585497658010497296562611090395702448308783934700219076643369044141154216620299808098211455021663919172853452835780280350662816748198542959483303075122821252835496819628822821356618993011258602824662795415229837446806]
N2 =  79793452404307772991357344993106825535881437651850989190167207780182633931014302377773537243505994706450846080369833744972497120593642751948607469336232224028321583664800564796793083753556408470068321691187266652001488918837258680058128328775215726635920122393445851305853361309411426980950362464138398747181
N2_reveal =  83896928254754053852112270886742722580566787976815300127356643189202374829913383753429846968926718515376095303482766372842187805901953258592983924709001668332006717903959248830478401668527422840163854229711822637026285723609632065896093558760350869572587252843861786079790186895561877471685831321032033216380
C1 =  42157017177317501300226837372353141947728676743117515316202001833714770690668313640304009109000914642717282563899303786732606524101864439259372083578759649985331980222923365282479635294537517877761432691528751021535678664985591900183366387685996869599529096769832340362117594801740589147019454712853414581910
C2 =  69127221550243400982633636364132600912444942339595294851235671831631164900383743105129003781800435434669074322062786007699146572531470021591138371468664463329988054420303837630787122729881668649111295247589177206298483207220984832474347513635910780186187775586426925959476556109594413402116969009308476300141

参考https://eprint.iacr.org/2016/215.pdf

AGCD问题(The Approximate Common Divisor Problem, 近似最大公约数问题)

1
第一部分中返回了三个AGCD值，此时我们可以考虑使用传统的AGCD问题中的SDA丢番图格进行攻击

第二部分知道N2和N2_reveal的值，PACD问题。通过论文 Passive SSH Key Compromise via Lattices，我们可以知道PACD问题的解决手段，选取参数Qj(x)Qj(x)

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


def solve1(N1_reveal):
    Len = len(N1_reveal)
    A = [[0 for i in range(Len)] for j in range(Len)]

    for i in range(Len):
        A[0][0] = 2**251
        A[i][i] = -N1_reveal[0]
        A[0][i] = N1_reveal[i]

    A = matrix(ZZ,A)
    A_solve = A.LLL()

    k0 = abs(A_solve[0,0])//(2^251)
    p = N1_reveal[0]//k0
    return p


def solve2(N,N1,t,k,sys):
    var('x y')
    f = N1-x
    Q_polys = []
    for j in range(t + 1):
        # print(max(k-j,0),min(j,k),max(j-k,0))
        x1,x2,x3 = max(k-j,0),min(j,k),max(j-k,0)
        Q_polys.append(N^(max(k-j,0))*f^(min(j,k))*x^(max(j-k,0)))

    # print(Q_polys)
    len = t+1
    B = []
    num = 0
    for i in Q_polys:
        J = i.coefficients()
        b = [0*x for x in range(len)]
        for j in J:
            # print(j[0],j[1])
            b[j[1]] = ZZ(j[0])*(2**sys)**ZZ(j[1])
        B.append(b[::-1])
        num+=1
    B = matrix(QQ,B)
    solve_B = B.LLL()

    print('===We have find the right B_LLL===')
    BB = solve_B[0]
    a = []
    for i in range(len):
        a.append(BB[i]//((2^sys)^(t-i)))
    f1 = 0
    for i in range(t+1):
        f1 += a[i]*x^(t-i)
    m = f1.roots(multiplicities=False)
    print(m)
    return m

if __name__ == '__main__':
    e = 65537
    # 第一部分
    N1 = 152952981944000100965638860967602827566778521492487050491892827674361544670819337749785802004935917933682378674371592431931030006263550462078568397201797421799133055122247087592029620139237110046703705970063264710838333520122569715133956574555308030406142657069010739854876223563665391381467693316799077562631
    N1_reveal = [
        93468146961503699670349582663589460392367381003360753998849635467834109329797684521052329961180631916859515284206764142310372205159222106596242263153896728879084898629423535394124469773008692396830494914352138651073601861340964731819865482810779087666392285305203522266859409492705495993697069222798873726960,
        104236574927656394650569462832082413075782565853751822615159241825222661691226282897836986441960802720967958907731302400903695988149825216397968325252362370979139937478581483399525815281298614897697149261611978635688552921229950818270323755332455301763156318841119986217470444550142872582768290596482687744424,
        111344636205100432122150931949073552736191028277954358828475656601131912158613340112534257389822848254590508022360957981663909238892049647529257898438607265543877295425311970143364489439451122473266322338624662429675715687546673545518635013973444850954299112981470324421581526800664146117051212442370458976160]
    N2 = 161000399096301338674145679646803449371884584783717643268822418066620108407731540425248748533274852271981238626583833936952481982310960867551626932936647644974305095312215770087022986994903359281662387821626872045714904933693788625089056417708989083541828993779459498763207176730305258351465296844035402992037
    N2_reveal = 94357561554041679026592892471969668587647998642633209852151089525750487249954579819289811636051497958155667305620006329556344469501081714147153506848627046878474589251168180372471471342863289188504937739676178745002243329722947845252016138510055976215692978579052562147323290563188038148717392659754084259868
    C1 = 58594793302586275577689791690916913430813466918408684969682636302311071900226219937673437452062598539194973815823691328343903675454727770424091510402364067928727276503529768938503877868193223803409389316480107820270032654504227476928880926262835555278965327337517905481056020439215084989992384844952072797767
    C2 = 96355602042990531636996233678782492485176551414647666201694738677085382408306061625779061776073653265708098763914371044105367860146561867196601390320646644981522466233466082942467352765311760481386653836121412702539810520173452171910779083525937819154456189707020401497882337846898520990299400500600590240447

    p0 = solve1(N1_reveal)
    q0 = N1//p0
    phi0 = (p0-1)*(q0-1)
    d0 = inverse(int(e),int(phi0))
    flag1 = long_to_bytes(pow(int(C1),int(d0),int(N1)))
    print(flag1)

    # 第二部分
    start = time.time()
    r_solve = solve2(N2, N2_reveal, 32, 16, 247)[0]
    end = time.time()
    print('The consumption of time is:',end-start)

    # print(r_solve)
    p1 = GCD(int(N2),int(N2_reveal-r_solve))
    # print(p)
    q1 = N2//p1
    phi1 = (p1-1)*(q1-1)
    d1 = inverse(int(e),int(phi1))
    flag2 = long_to_bytes(pow(int(C2),int(d1),int(N2)))

    flag = flag1+flag2
    print(flag)

最后flag为

1
SHCTF{APPROxiMaTE_n_H4PpY_7hE_NEW_GGag_2_Da}

[Week3] Lattice

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
n = getPrime(1024)
x = getPrime(200)
hint = (x*gmpy2.invert(m,n)) % n
print(f'n = {n}')
print(f'hint = {hint}')
'''
n = 111051803526627850153468174186159893243636318493876676666213150015180184635779236922789460461035302699199035298913035640661230419535670788105417496144705274540495134064339311859851203384873756502359729860000236357582420446691011264455212498934817789185230625910879476573553389199816471538453119368614765942573
hint = 110345908551293525210623869859380393592605374931641446269963676795739050993529372395865985806230139631392835452643945742549699964073384096383040762557251566689070250457572753393317989274200447452984900286455685076227248192002082088232772081206011308116275900028392632018036348485154311801858729346468635905269
'''

hint = xm^-1 mod n直接用hint和n造格 mhint = x + kn

exp:

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import long_to_bytes
n = 139375501266966354110560987602941579720343298682302380213629012399146702255224092464371860285892594606518682202746469996717869266755804902133065746523678610701447709661598475045236643942670878454454914242366823865911620343171523738762438337620932812380503714497659323917884890957898967721924886002184816388909
hint = 30111064015548195748229136433160596861378053894649564473559454623946601615359833481249637332444935789833334802877702902155500934637824299425212772699568531012251263573286943567743990513595674983034259871038496370389371165018799403318568607201602419538351281864014621535790322463730848699042720151828377672492
 
h_ni=inverse_mod(hint,n)
L=Matrix(ZZ,[[1,h_ni],
             [0,n]])
 
L=L.LLL()
print(long_to_bytes(abs(int(L[0][1]))))

运行得到flag

最后flag为

1
SHCTF{1a7t1cE_lS_MADE_Of_LA_tt_1CE_O2}

[Week3] Shamir

源码:

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 Crypto.Util.number import getPrime,bytes_to_long
import random
from os import getenv

BANNER = """
 __          __  _                            _______       _____ _                     _      
 \ \        / / | |                          |__   __|     / ____| |                   (_)     
  \ \  /\  / /__| | ___ ___  _ __ ___   ___     | | ___   | (___ | |__   __ _ _ __ ___  _ _ __ 
   \ \/  \/ / _ \ |/ __/ _ \| '_ ` _ \ / _ \    | |/ _ \   \___ \| '_ \ / _` | '_ ` _ \| | '__|
    \  /\  /  __/ | (_| (_) | | | | | |  __/    | | (_) |  ____) | | | | (_| | | | | | | | |   
     \/  \/ \___|_|\___\___/|_| |_| |_|\___|    |_|\___/  |_____/|_| |_|\__,_|_| |_| |_|_|_|   
"""
print(BANNER)

flag = getenv("GZCTF_FLAG","GZCTF_NOT_DEFINE")
m = bytes_to_long(flag.encode())
n = getPrime(1024)
coefficients = [m] + [random.randrange(1,n-1) for i in range(100)]
print(f"n = {n}")

def f(x):
    sum = 0
    for i in range(len(coefficients)):
        sum += coefficients[i]*pow(x,i,n) % n
        sum %= n
        
    return sum

while 1:
    x = int(input("Please Input x: "))
    if x == 0:
        print("Not Allowed!!!")
        exit()
    res = (x,f(x))
    print(res)

hamir门限，多项式最大系数为100，通过交互得到101个点的坐标，利用拉格朗日插值法得到这100个系数的值

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
from pwn import *
from Crypto.Util.number import *
 
r=remote("210.44.150.15",40430)
 
r.recvuntil(b'n = ')
n=eval(r.recvline().strip().decode())
 
m=[]
for i in range(1,101+1):
    r.recvuntil(b'Please Input x: ')
    r.sendline(str(i).encode())
 
    tmp=eval(r.recvline().strip())
    m.append(tmp)
    
flag=0
for i in range(len(m)):
    tmp1=1
    tmp2=1
    for j in range(len(m)):
        if i==j:
            continue
        tmp1*=-m[j][0]
        tmp2*=(m[i][0]-m[j][0])
    flag=(flag+m[i][1]*tmp1*inverse(tmp2,n))%n
print(long_to_bytes(flag))

运行得到flag

最后flag为

1
SHCTF{SHAmlr_No7_ShErLoCk_56dd9e0cb08c}

[Week3] babyLCG

源码：

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 enc import flag

seed = bytes_to_long(flag)

a = getPrime(400)
b = getPrime(400)
p = getPrime(400)
c = []
for i in range(3):
    seed = (seed*a+b)%p
    c.append(seed>>80)
print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')
print(f'c = {c}')

'''
a = 1547590086339921220070164693013433178129012130173764257824775545676373473156144022624729835852716119498945096741206112677
b = 1653230507631776108239599869514745743813873238577133534741893878725373810514436945728277899021074102284044893293963204179
p = 2228418810108046582099529384009362039972975593517554854991389164085574099475172221612851934893757966802191686004464600251
c = [377698572900926852243044329817924686049709287332115265917047424852869686538401326387310804632255, 584244490694537564992592098730351139901943109220188262221948929027036684631269441221751517008499, 773074856634956069461859034956441843062461345428667848075059476078570749448643053813193752727548]
'''
'''

参考

记 LCG 例题_# a = 73111197104586312977084921341458383051320481-CSDN博客

https://dexterjie.github.io/2024/07/16/%E6%B5%81%E5%AF%86%E7%A0%81/%E6%B5%81%E5%AF%86%E7%A0%81-LCG/

seed>>80有位移，应该要用格

2元cooper

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
import itertools
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

output =  [3046229294982134450591178033489768650552322716872597427107928034748567068803980276957057890481, 973001372006880118889917783354942758117321515064139462745181212051769645104406522505813126876854, 890186362163854321562009885401997664814267684052369722289787654117599676602992999049017980432156]
a = 2475888996632094582034122163505958703059936413843532352796751833709426858969562425221138286394228921214141232352754363633
b = 1905480696303984902796083235070180899781860050180854546296493122498519159940315402346589283466547617432046217796603160773
n = 2209046612698920104484284797114056179410109590589945885514075526562344194607111614640088528695744803046785464320831674877


PR.<x,y> = PolynomialRing(Zmod(n))
f = ((output[0]<<80)+ x) * a + b - ((output[1]<<80) + y)
roots = small_roots(f,(2^80, 2^80), m=4, d=4)
s1 = (output[0]<<80) + roots[0][0]
m = (s1 - b) * inverse_mod(a, n) % n
print(bytes.fromhex(hex(m)[2:]))

运行得到flag

最后flag为

1
SHCTF{lC9_MAY_ME4nS_IOU_D0n9_CAl_8I}

[Week3] baby_lock

题目描述:

1
生蚝家里装了一个新款智能门锁，每次都要输入很长的密码，但你在偷窥的时候发现好像有一些规律？

源码：

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
class Random(object):
    def __init__(self, s0, s1):
        self.s0 = s0
        self.s1 = s1
        self.state = [s0, s1]
    def current(self):
        val = (self.s0 + self.s1) & 0x1fffffffffffff
        return val >> 4
    def __next__(self):
        s1 = self.state[0]
        s0 = self.state[1]
        
        self.state[0] = s0
        s1 ^= (s1 << 23)
        s1 &= 0xffffffffffffffff
        self.state[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26)
                
        random_val = (self.state[1] + s0) & 0xffffffffffffffff 
        
        return random_val
    def Next(self):
        return next(self) & 0x1fffffffffffff

import colorama, hashlib, random, string
from colorama import Fore as cf
from os import urandom, getenv

flag = getenv("GZCTF_FLAG","GZCTF_NOT_DEFINE")
s0, s1 = [int.from_bytes(urandom(8), 'big') for _ in [0, 0]]
prng = Random(s0, s1)
colorama.init()

def number_to_circled(num):
    circled_numbers = {
        '0': '⓪', '1': '①', '2': '②', '3': '③', '4': '④', '5': '⑤',
        '6': '⑥', '7': '⑦', '8': '⑧', '9': '⑨'
    }
    return ' '.join(circled_numbers[d] for d in str(num))

welcome = f"""
        ╔═══════════════════════════╗
        ║  🔒 Smart Lock System 🔒  ║
        ╠═══════════════════════════╣
        ║                           ║
        ║   1.  {cf.YELLOW} Spy   password{cf.RESET}     ║
        ║   2.  {cf.YELLOW}Input  password{cf.RESET}     ║
        ║                           ║
        ╚═══════════════════════════╝
"""
print(welcome)

def proof_of_work():
    prefix = "".join(random.choices(string.ascii_letters, k=8))
    answer = "".join(random.choices(string.ascii_letters, k=4))
    hashes = hashlib.sha256((prefix + answer).encode()).hexdigest()
    print(f"🔍 Prove you deserve to see the password! Solve this PoW:")
    print(f"   Find a ANSWER {cf.LIGHTGREEN_EX}hashlib.sha256(('{prefix}'+{cf.RED} ANSWER{cf.LIGHTGREEN_EX}).encode()).hexdigest()[:10] =='{hashes[:10]}'{cf.RESET}")
    
    suffix = input(f"   Enter your {cf.RED}ANSWER{cf.RESET}: ")
    attempt = hashlib.sha256((prefix + suffix).encode()).hexdigest()
    
    if attempt.startswith(hashes[:10]):
        return True
    else:
        print(f"❌ {cf.RED}Spy failed. {cf.RESET}\n")
        return False

while True:
    chose = input("Please make your selection: ")
    if chose == "1":
        if proof_of_work():
            password = prng.Next()
            password = number_to_circled(password)
            output_text = f"👀 The Peek at password: {cf.LIGHTGREEN_EX}{password}{cf.RESET}"
            box_width = len(output_text) - 6
            print("╔" + "═" * box_width + "╗")
            print(f"║ {output_text}  ║")
            print("╚" + "═" * box_width + "╝\n")
        else:
            continue
    elif chose == "2":
        password = prng.Next()
        print(                  "╔═════════════════════════════════════╗")
        user_input = input(    f"║ 🔑 Enter password: {cf.YELLOW}")
        print(  f"{cf.RESET}╚═════════════════════════════════════╝")
        if user_input == str(password):
            output_text = f"🔓 {cf.GREEN}Access Granted!{cf.RESET} Secret is {cf.LIGHTMAGENTA_EX}{flag}{cf.RESET}"
            box_width = len(output_text) - 17
            print("╔" + "═" * box_width + "╗")
            print(f"║ {output_text} ║")
            print("╚" + "═" * box_width + "╝\n")
            break
        else:
            output_text = f"❌ {cf.RED}Access Denied! Incorrect password.{cf.RESET}"
            box_width = len(output_text) - 7
            print("╔" + "═" * box_width + "╗")
            print(f"║ {output_text} ║")
            print("╚" + "═" * box_width + "╝\n")
            break
    else:
        output_text = f"⚠️ {cf.RED}Invalid selection. Please choose 1 or 2.{cf.RESET}"
        box_width = len(output_text) + -8
        print("╔" + "═" * box_width + "╗")
        print(f"║ {output_text} ║")
        print("╚" + "═" * box_width + "╝\n")

本题考点的PRNG，是「Xorshift128Plus」

https://blog.securityevaluators.com/hacking-the-javascript-lottery-80cc437e3b7f

这个漏洞在v8的Math.random()中被发现（已修复）

https://github.com/v8/v8/tree/7a4a6cc6a85650ee91344d0dbd2c53a8fa8dce04 本题进行了一点点魔改

增加PoW算是提示不需要太多次的获取数值

实际上也只需要3个连续state，Z3求解即可

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
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
import z3
import sys
import itertools

# XorShift128+ algorithm in python
class XorShift128Plus(object):
    def __init__(self, s0, s1):
        self.s0 = s0
        self.s1 = s1
        self.state = [s0, s1]
    
    def current_double(self):
        val = (self.s0 + self.s1) & 0x1fffffffffffff
        return val
    
    # This function generates another 64-bit integer
    def __next__(self):
        s1 = self.state[0]
        s0 = self.state[1]
        
        self.state[0] = s0
        s1 ^= (s1 << 23)
        s1 &= 0xffffffffffffffff
        self.state[1] = s1 ^ s0 ^ (s1>>17) ^ (s0>>26)
                
        random_val = (self.state[1] + s0) & 0xffffffffffffffff 
        
        return random_val
    
    # This function generates another floating point-type number in the range [0,1)
    def next_double(self):
        return next(self) & 0x1fffffffffffff
    
class Cracker(object):
    def __init__(self, known_values):
        self.s0 = z3.BitVec('s0', 64)
        self.s1 = z3.BitVec('s1', 64)
        self.state = [self.s0, self.s1]

        self.solver = z3.Solver()

        # The known variable will contain the values that we generated in Firefox
        self.known = known_values
    
    def __next__(self):
        s1 = self.state[0]
        s0 = self.state[1]
        
        self.state[0] = s0
        s1 ^= (s1 << 23)
        self.state[1] = s1 ^ s0 ^ z3.LShR(s1,17) ^ z3.LShR(s0,26)
                
        return self.state[1] + s0
    
    def crack(self):
        for val in self.known:
            nextval = z3.fpToFP(z3.get_default_rounding_mode(), next(self) & 0x1fffffffffffff, z3.Float64())
            self.solver.add(nextval == val)

        if self.solver.check() != z3.sat:
            raise Exception("Not solved!")
        
        model = self.solver.model()
        s0 = model[self.s0].as_long()
        s1 = model[self.s1].as_long()
        
        return (s0, s1)

def circled_to_num(num):
    circled_numbers = {
        '0': '⓪', '1': '①', '2': '②', '3': '③', '4': '④', '5': '⑤',
        '6': '⑥', '7': '⑦', '8': '⑧', '9': '⑨'
    }
    circled_numbers = {y:x for x,y in circled_numbers.items()}
    return int(''.join(circled_numbers[digit] for digit in str(num).replace(' ','')))

import hashlib, itertools, string
def pow(s1,s2):
    for s in itertools.product(string.ascii_letters,repeat=4):
        if hashlib.sha256((s1 + "".join(s)).encode()).hexdigest()[:10] == s2:
            return "".join(s)

from pwn import *
p = remote('210.44.150.15', 20786)

pwd = []
def get_num():
    p.sendlineafter(b'Please make your selection: ',b'1')
    p.recvuntil(b'Find a ANSWER ')
    PoW_data = p.recvline().decode()

    print(PoW_data)
    import re
    pattern = r"sha256\(\('(\w+)'\+.*\)\.hexdigest\(\)\[:10\] =='(\w+)'"
    match = re.search(pattern, PoW_data)

    if match:
        p1 = match.group(1)
        p2 = match.group(2)
        print(p1,p2)

    answer = pow(p1,p2) 
    p.sendline(answer)
    p.recvuntil(b'The Peek at password: ')
    num = p.recvline().decode()
    print(num)
    num = num[5:-9]
    print(num)

    pwd.append(num)

get_num()
get_num()
get_num()

known_values = [circled_to_num(x) for x in pwd]

cracker = Cracker(known_values)
(s0, s1) = cracker.crack()
print(s0,s1)
prng = XorShift128Plus(s0, s1)

assert prng.next_double()==known_values[0]
assert prng.next_double()==known_values[1]
assert prng.next_double()==known_values[2]

x3= prng.next_double()
success(str(x3))

p.sendlineafter(b'Please make your selection: ',b'2')
p.sendlineafter(b'Enter password: ',str(x3).encode())
# p.interactive()
p.recvuntil(b'Access Granted!')
success(p.recvline())

[Week3] 大学×高中√

题目描述：

1
死去的高中数学知识突然攻击我！！！

源码：

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
assert len(flag)==47
leak = cos(m).n(1000)
print(leak)
# 0.472571442349678503734313771966614730374489176653617901351947519259324612818582963776515929972837113551103871572902183903855953532573696742421159694782140195528006269288005805314356959841424498944676981202896008813660479951222670655462306975438747073021880542138034483647445105966977935010272471678091

参考第二届黄河流域网络安全技能挑战赛 | DexterJie’Blog

exp:

1
2
3
4
5
6
7
8
9
10
#sage

leak = 0.472571442349678503734313771966614730374489176653617901351947519259324612818582963776515929972837113551103871572902183903855953532573696742421159694782140195528006269288005805314356959841424498944676981202896008813660479951222670655462306975438747073021880542138034483647445105966977935010272471678091
acos = arccos(leak)
RF = RealField(1000)
pi = RF(pi)
M = Matrix(QQ,[[1,0,2^760],[0,2^376,2^760*acos],[0,0,2^760*2*pi]])
m = abs(M.LLL()[0][0])
flag = bytes.fromhex(hex(m)[2:])
print(flag)

运行得到flag

最后flag为

1
SHCTF{arCCo5_LE4rnED_iN_H1gh_ScHoOI_USEd_1atER}

[Week4] BabyHash1

题目描述:

1
Magic Hash : )

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

FLAG = b"SHCTF{XXX_FAKE_FLAG_XXX}"
p = 334641907675981737343904379204876337859127829299172648068105540032137951559908027120450949854596026146898543
G = [random_matrix(GF(p), 2) for _ in range(64)]
I = identity_matrix(GF(p), 2)
save(G, "G.sobj")
key = os.urandom(8)

H = lambda m: prod([G[i%64] if int(j) else I for i,j in enumerate(bin(int(m.hex(), 16))[2:])])
Q = list(H(key))
c = AES.new(2*key, AES.MODE_ECB).encrypt(pad(FLAG,16)).hex()
print(f"{Q = }")
print(f"{c = }")
"""
Q = [(92408373140638310582912266568541040708090711689280871505631689622417484347016487049244869849344848494009962, 53959869712387349430336059834241967356744173550876450413296700728311848545577500067458604734684838108665050), (252347024205859090718692136370078190718071419535216876332667850755617010322625175614169994287981074023442001, 248109129148524862390611680382928105844063942809716627922076622327580907465285046951446750474905265881834033)]
c = 'bbf4e7820865cc2fa3739a1d86006d83015180776a3285d4c14f5ee95685ac1ef64122e0f3603a794b4f170ec827dbb1'
"""

利用矩阵的非交换性质构造的哈希函数

类似于一个乘法背包，但是不同于数域上的，这里很难找到统一的生成元，但是我们可以利用行列式做转换

即判断

由哪些行列式的乘积构成，这样我们可将其视作一般的乘法背包，但是问题在于题目中选择的 p 不够光滑，我们需要选择其中光滑的那部分求解离散对数。

故只需要得到

即可，这两者我们均可以在光滑阶下进行求解。

最终利用 (*) 式构造格通过 LLL 还原 key 并解密。

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

p = 334641907675981737343904379204876337859127829299172648068105540032137951559908027120450949854596026146898543
F = GF(p)
Q = [(92408373140638310582912266568541040708090711689280871505631689622417484347016487049244869849344848494009962, 53959869712387349430336059834241967356744173550876450413296700728311848545577500067458604734684838108665050), (252347024205859090718692136370078190718071419535216876332667850755617010322625175614169994287981074023442001, 248109129148524862390611680382928105844063942809716627922076622327580907465285046951446750474905265881834033)]
c = 'bbf4e7820865cc2fa3739a1d86006d83015180776a3285d4c14f5ee95685ac1ef64122e0f3603a794b4f170ec827dbb1'

G = load("G.sobj")
delta = []
for g in G:
    delta.append(g.det())

target = matrix(F, Q).det()
q = 1327433362304639193864290941923656426545922990449
qs = factor((p-1)//q)

def dlog(y, g):
    y, g = pow(y, q, p), pow(g, q, p)
    return log(F(y), F(g))

ds = []
for i in delta:
    ds.append(dlog(i, 5))

e = dlog(target, 5)
w = 2**128
A = matrix(ZZ, 64+2, 64+2)
A[:64,:64] = identity_matrix(64)*2
A[64,:65] = matrix(ZZ, 1, 65, [1]*65)
A[:65,65] = matrix(ZZ, 65, 1, ds+[e])*w
A[-1,-1] = (p-1)//q*w
AL = A.LLL()
key = int(''.join(['0' if i == 1 else '1' for i in AL[0][:-2]]), 2)
print(AES.new(2*long_to_bytes(key), AES.MODE_ECB).decrypt(bytes.fromhex(c)))

最后flag为

1
SHCTF{master_of_the_linear_algebra}

[Week4] BabyHash2

题目描述:

1
Magic Hash : )

Algebra Hash 比较经典的攻击方式

利用矩阵的非交换性质构造的哈希函数

其中

构造碰撞的关键在于能否找到单位阵在 A0,A1下的非平凡分解,显然

注意到

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

def solver(p):
    for c in range(1, 2**15):
        p_ = random_prime(2**90)
        PR.<x> = PolynomialRing(GF(p_))
        f = x**2-c*p*x-c
        root = f.roots()
        if root:
            k1 = ZZ(root[0][0])
            k4 = c*p-k1
            k2 = -(k1**2-c*p*k1-c)//p_
            return (k1, k2, p_, k4)

def gcd(a, b, q):
    r = a%b
    q.append(int(a//b))
    if r: return gcd(b,r,q)
    else: return b
        
def Fac(I):
    q = []
    gcd(I[0,0], I[0,1], q)
    m = ''
    if len(q) %2 == 0:
        for i in range(len(q)):
            if i%2: I *= A^-q[i]; m += '1'*q[i]
            else: I *= B^-q[i]; m += '0'*q[i]
        alpha = int(I[1,0])
        m += '0'*alpha
        return m

p = 1167195242552699154956050457
msg = b"$ Welcome to SHCTF!!! :)"
A = matrix(ZZ, [[1, 1], [0, 1]])
B = matrix(ZZ, [[1, 0], [1, 1]])

while True:
    k1, k2, k3, k4 = solver(p)
    I_ = matrix(ZZ, [[1+k1*p, k2*p],
                    [k3*p, 1+k4*p]])
    pad = Fac(I_)
    if pad:
        if len(pad)%8 == 0 and len(pad) < 100*8-24*8:
            print(msg.hex()+long_to_bytes(int(pad, 2)).hex())
            break

最后flag为

1
SHCTF{ez_att@ck_2_th15_weak_hash}

[Week4] MT19937

data.txt

1
2
3
4
[1212937457, 714280275, 2934808054, 289447810, 634020656, 2582053193, 2648476152, 3584472561, 2877037797, 1051288028, 3007240724, 3583122714, 2377373219, 2233668169, 2300136290, 4277363949, 572508719, 3707687803, 868724505, 2234515288, 2182162330, 2354654192, 3676064525, 16386761, 1934246009, 396534601, 3406538372, 1978740790, 51554945, 1642830773, 3255471879, 249329746, 1871028531, 1670146144, 3955249559, 3523216280, 4225679888, 1979625069, 1711120506, 4224015378, 2357192253, 1437719734, 1861766583, 252037050, 3805173581, 3845899039, 239338040, 3335618070, 1909354144, 2380236080, 3120658839, 2738735651, 1749563272, 4028406006, 198730175, 4095736523, 2224365497, 1850797931, 123559677, 277130374, 1547602417, 2312967225, 1064405558, 620877831, 4182002366, 2717144120, 2424475877, 1261886189, 2666842961, 1250633055, 1445939400, 2496676732, 46718503, 1726056600, 2892333819, 3874613567, 2801764620, 3279121957, 62950328, 14090298, 3016963976, 235881318, 1152787765, 3549713637, 3184265794, 461262349, 1835258817, 706701716, 366259495, 2484440259, 2306336615, 2418024433, 107268664, 3018120752, 3915797798, 1685880034, 2782876985, 2876720582, 3803172243, 1745503879, 1965535595, 2831775453, 3139448870, 770826076, 559187920, 4292272948, 86904027, 1821662944, 58381562, 250790584, 2122997254, 2937312684, 3225034461, 1493971528, 913420791, 2911905254, 2938402784, 1430747115, 2654595902, 3315197237, 602765188, 1471009311, 3788529131, 913593424, 3280524381, 1554400422, 3250536147, 3480550436, 821401975, 3216026683, 762420368, 1733854366, 2395038075, 533527872, 3040490234, 2855012365, 2984904790, 2830464734, 2200935030, 523059886, 3795772367, 2905400361, 667720140, 3155311553, 1860651089, 1053555607, 2889478721, 1812821011, 3391980212, 3433665687, 2480476597, 1319654037, 1076583906, 2287201297, 966928688, 2542225146, 2246098689, 3117124345, 1844896511, 3104215564, 1303510082, 2924158615, 3648677443, 3308489255, 3809196505, 3199516268, 2254502655, 2126047470, 1763846642, 3851973930, 1280609700, 2415985988, 1312349771, 2103486452, 4229394974, 1937464844, 2763672456, 1366425769, 1532462738, 1864298394, 1203192658, 3679892306, 4138733297, 39437090, 1317880030, 132948638, 2315846286, 3394291148, 3207221552, 3834885856, 2367158425, 3183864791, 3303289072, 519407526, 4127464161, 1556426685, 2427155757, 2010011401, 2823249259, 3638339516, 2266010959, 345885116, 471672470, 2713191580, 731238671, 1694687550, 2523761501, 3533913138, 163820753, 1829608711, 587056408, 1129980234, 3642159144, 2546599527, 758703728, 1713442774, 1864598338, 2763096157, 2308766766, 1132350895, 2776604596, 1921085522, 1409581297, 2643399928, 3285649744, 1248611904, 2694186262, 2676127368, 2579578748, 3784393865, 2655293049, 1378866508, 1251610536, 1048557165, 3045231444, 4236456301, 2496231577, 4118010676, 3079411364, 2425576144, 2431718306, 543894373, 118186072, 2594647421, 1833894329, 3876640493, 1916631983, 2765860034, 3905895682, 2207230275, 2554838603, 3199831939, 2516271151, 3080023814, 3594335532, 1197450849, 2621744299, 447615180, 1616950869, 3109651542, 2553431350, 4165466937, 2130063794, 1459492895, 1141470511, 948009682, 325807524, 1681494454, 3137320840, 4219461371, 609761579, 942363481, 2404858793, 1697226342, 830264373, 230968933, 831865647, 4164463522, 2968510743, 1464271639, 1397831008, 2559413030, 3515044508, 772056268, 3152446673, 3117754594, 833212973, 4252629747, 2565179775, 3005093783, 3595030314, 4042182692, 298671165, 3183128227, 3429794312, 4122368172, 1900961662, 3589294443, 3190786481, 1744404482, 1921785452, 3011999869, 642164068, 3695788414, 2275346981, 1428956574, 2697326707, 2202213004, 3287889517, 919861723, 726410498, 337174656, 2417998504, 2752587611, 3856581958, 141509063, 1762431188, 2065705145, 2031960873, 1892209091, 2395039500, 1058479586, 1537034270, 502217054, 3102018820, 1433274316, 1372952271, 2918921770, 239909451, 1398298200, 2339489735, 372558373, 2263872236, 2426192905, 337209508, 3983991978, 2574803724, 2837664572, 1569892789, 2625063195, 3262762020, 24150029, 2016099290, 2239153990, 85602273, 973040529, 2956276779, 4218049523, 2043716624, 2788573458, 1218787308, 939708241, 2861205992, 2427634523, 4128874493, 2326852266, 2593724377, 1680473968, 2763572707, 4240616686, 2863701585, 3551633590, 1765256405, 2110583291, 357590304, 2511138801, 859903599, 35591840, 3786321031, 3559501147, 3107666783, 2356867678, 1369801910, 2488594855, 2148205170, 3944224524, 2219844222, 466009157, 2328231114, 2777059464, 1585865212, 2871297568, 2558165993, 1561563095, 438633926, 2619385032, 2185942244, 2501145168, 2161107203, 912485991, 3956413626, 4065963551, 1527306118, 378382496, 1016367697, 82832444, 2484726280, 867566307, 1037338825, 4291735272, 901722138, 3956112428, 1060890097, 4210262544, 2525835262, 786274933, 2563584713, 2738164238, 3438656534, 564065202, 3288501195, 1074332184, 2947775555, 3790174897, 3607901153, 2332098514, 3648669449, 3879104921, 3983960923, 548882335, 1817587379, 1555057777, 2705918139, 2755720626, 2706833366, 2947946695, 3082750952, 2323554320, 1804494628, 1677086381, 2771841028, 2470056271, 3431120732, 4073503495, 2929631518, 80800254, 605951710, 1664206366, 2498279527, 360922649, 2590660538, 3724444465, 3559953317, 3002864163, 3369368155, 1569518356, 3831143803, 4184782515, 1602338537, 2640186368, 2864951447, 514648741, 887020932, 166121609, 476244781, 2238614863, 3039706334, 3586500526, 3038068930, 3989751746, 3699955508, 3559348520, 884358906, 444882591, 3769021913, 3665754928, 1911261614, 1234192084, 3450557803, 3232410240, 494096069, 660552292, 1365481833, 520081058, 1027987838, 3165505556, 1257833693, 2146291679, 3634622224, 589123893, 1195030125, 1602406253, 772753497, 2661121530, 2938530200, 1070706826, 3890477657, 2112901265, 4253917692, 2291562806, 67613984, 2608069358, 1726139310, 3018885048, 367067728, 3838771641, 1357927847, 2616452172, 722979624, 4153031784, 607660099, 3164865398, 3199368055, 1885230388, 1055777913, 3475913336, 1546318749, 578282810, 1558944130, 2955660875, 2214838829, 4202836988, 1405916968, 2593459723, 3648360966, 3644813488, 598912719, 876098814, 355483438, 685352898, 4099087273, 2983380912, 450980374, 2753208777, 429297943, 3462109454, 3134522829, 2064548393, 2200750558, 4247753845, 251220053, 1556849099, 2022648175, 3563632884, 2175932589, 1463719656, 1887673611, 3541708446, 3033219582, 3255799816, 534398633, 3481196045, 825005812, 1629237540, 640085217, 899503755, 3105157116, 488231507, 2708835929, 2648663900, 2048030022, 1503411342, 4059850866, 1281156549, 3171426598, 2637361895, 1110841056, 606897504, 3001264062, 912267483, 148124465, 202684836, 1425732680, 3637635336, 1455737055, 2977077407, 54987379, 1056796337, 1832170261, 1870208138, 4074249428, 2993704297, 381772606, 2362720677, 2164369676, 250156737, 3409786877, 1590821450, 2959971180, 3682255149, 302283211, 4204651015, 1294232346, 3088162584, 4209012441, 784333825, 1275400791, 885466807, 1249631254, 1236809354, 2627231325, 2391839654, 1638467843, 2797229961, 3799496431, 237846505, 3432655604, 1690038717, 1493561006, 4229115929, 3784624191, 2891696687, 3557702324, 1120718375, 2593253432, 1415584860, 551110044, 1510986691, 3267929936, 2341598281, 247215742, 3192053018, 2856032615, 3290505354, 907961089, 4128700570, 4195745607, 2035634741, 1047086449, 216435127, 1997121891, 3391563810, 2813128796, 1517545322]
[2137201486, 2243095490, 3817098931, 229608464, 73854451, 2470370137, 647955184, 1997583099, 2122796155, 3754429965, 915090235, 3330907022, 4045925639, 1616378187, 3477748127, 3235608209, 4168058459, 137624259, 2992531650, 509166204, 3920545433, 1915159362, 3901263233, 4228481818, 2816405167, 1786108715, 3305752402, 2384763695, 227465801, 1052658065, 3153900057, 117311308, 1595474528, 1087880165, 3166831564, 1588364714, 528237288, 617272354, 618281932, 1618791873, 3810883062, 894018392, 2575794219, 103568311, 3298607681, 536028939, 3467146346, 2201685940, 1076138845, 918210863, 1341794665, 3456513087, 1710914773, 1894309846, 2312381988, 127727152, 876614149, 1709878784, 1156541415, 1555452594, 182448271, 408344822, 2898434231, 1998211488, 3592206445, 1085073460, 3397525879, 663024038, 3434587726, 2768736843, 617681814, 2865397550, 3463093384, 2746629701, 2006818690, 1121017677, 2047400279, 1921768902, 528024592, 2892263293, 2798869302, 3481658697, 2848153687, 1134481165, 3720776629, 486120970, 2683483151, 3252410704, 2891974166, 2121509882, 4160792826, 2915283137, 4014112386, 1792273527, 805496405, 1407962158, 3622679727, 3512697173, 2901255951, 3111681208, 2877903904, 827923100, 3729787569, 925768344, 923906770, 3606973890, 1181029191, 689515782, 1651144572, 3459362488, 2412684107, 1362064386, 4159398924, 2922809145, 1602978249, 3705882625, 4293462677, 764953390, 4178674632, 2074025926, 1925824438, 2523046149, 1263372335, 1677306491, 760292173, 3736532489, 2036587975, 514100070, 706857874, 1060105302, 2578078966, 2320134376, 3639164974, 1710455599, 45505402, 2407597519, 2537656373, 56251495, 1630733521, 519864415, 1444518872, 513906964, 3852284907, 800496493, 872675679, 3155530732, 683268660, 3856797215, 137673146, 3607443770, 3700387644, 965766446, 2454233777, 954672952, 2855774032, 3552757435, 3025907069, 1402938518, 3041387870, 3456472325, 447871942, 1327563590, 620160190, 1007188755, 180115074, 52020277, 1774723235, 2887773879, 3508414970, 3631951842, 1763635376, 1924307117, 4204987693, 2494477117, 4017134019, 368620157, 2814392181, 2199699352, 1158269085, 2580589087, 1747804339, 1012560482, 933361529, 176586313, 2808905110, 83750114, 3090684109, 1767704883, 4189833886, 4249260150, 2157821862, 2112716220, 261010276, 3168798078, 1920566780, 1823590666, 2244335700, 2816218464, 3295774792, 2283997010, 3733740723, 3169836042, 1782097885, 1421909608, 3071286976, 2529056825, 2917504380, 2500113967, 1340022169, 1325786585, 2696541388, 3763160733, 3603998832, 72655495, 2892272720, 2785458061, 1724578654, 2144338844, 2899719547, 318345339, 2511462884, 3220707099, 1676208778, 2586878575, 3209502577, 3013180194, 2700788434, 3611106949, 1712906930, 3381158761, 962420077, 1928661992, 1241692316, 3587734972, 2361851891, 729570171, 1255993130, 2059230370, 3819451535, 2490865889, 1229457976, 3062266381, 3350574651, 1861939269, 3074031276, 1122137253, 3267903554, 2691684836, 3042505532, 1103427454, 2126863565, 3686667924, 4181984974, 238390653, 2037278833, 2930470784, 424623283, 3074336567, 4019540123, 447553681, 491252047, 2134100060, 3683266682, 2218397687, 1535505498, 628745497, 445350701, 186184731, 3190072310, 1084556173, 277509904, 2898643406, 4292667973, 2903270520, 2565372604, 303440546, 1808627640, 3069152665, 2075086265, 350493108, 3426866771, 1167370872, 2856612905, 1133769957, 2168578594, 361418126, 1788736419, 3450707887, 1988560242, 3106183307, 420765626, 1595814948, 813997149, 2474462651, 3945801301, 1785414095, 4177305184, 3071687740, 1273724577, 4178527412, 2536332142, 2692000853, 2172897829, 1472311250, 1630835977, 2274186143, 3947343331, 1836099636, 3955763613, 271610193, 2479541262, 3666471942, 4217699594, 341808580, 1517926781, 3311123634, 1738600938, 3870938757, 2309182531, 3189576099, 1594683626, 1900151562, 3625455382, 3527220315, 471268317, 4085391597, 1205291118, 1903466784, 934489768, 717103328, 407385599, 1146912039, 2148396650, 3906209540, 3002211292, 4003244728, 1595357238, 4224659669, 3679773598, 1554305724, 1879798896, 856183762, 2448013518, 2839667183, 3541976537, 1201501683, 2210517506, 3074699110, 2545660131, 3696626258, 1684534318, 3093429986, 2603224784, 3784468515, 1931537793, 570789340, 376758771, 2307788100, 2180860578, 201860820, 3293433128, 1396840567, 2231737923, 3343569549, 890147328, 3369945506, 3155052764, 4225372249, 3097945008, 1976073442, 1939061106, 3009821364, 3636790064, 1722351481, 571067187, 3660829870, 625774796, 962877120, 4093260308, 2994561947, 1780515932, 4180215026, 4252365298, 2947348994, 2484307881, 1869054839, 1567538899, 2381016872, 650248596, 2837463974, 3547259433, 1653667021, 276270749, 1685266082, 3605301102, 3560229703, 3732548108, 3643340502, 2787020632, 301650068, 1692193275, 3053122330, 446613045, 753748541, 3639322954, 2521151846, 3846032512, 2540737292, 1022192711, 4242180248, 2050165414, 2033316505, 3063183472, 2547887329, 1562411323, 2846186023, 1057549601, 200005518, 2515317663, 614142733, 2822762719, 1111596810, 730033186, 3539522165, 2876952827, 1093300071, 2988803720, 2788643910, 1815173676, 923492540, 1571870569, 1732017323, 3912738621, 1932484987, 1369226061, 1043943980, 659920686, 87860672, 3117771700, 536701, 1276716714, 399069847, 675178237, 4148780498, 2293633457, 510556418, 3306441120, 3969884840, 931665570, 1269866789, 1486094185, 1896845492, 2955478105, 3949294788, 2483398248, 2792552965, 367597061, 955979053, 4141216471, 3162398417, 783759084, 605101703, 3200303074, 1835668453, 3586071304, 2174558649, 2997422459, 3634493394, 4138976583, 164027380, 490279465, 2469644175, 43130477, 1547916166, 2406583577, 1303190434, 1431585058, 1519905099, 1079834268, 231749295, 1635997362, 1423407810, 2814537500, 2894136671, 3686889877, 1812711299, 4226627996, 3754118359, 20804048, 4285391186, 2958387414, 2233166520, 3070925064, 1320913219, 2976334802, 4041836979, 382095839, 1388937175, 1819247059, 3838255239, 3380204370, 3935811842, 2751480313, 164540071, 2340071112, 610666648, 595972300, 2011517128, 213838138, 4255091509, 3777157969, 2402199559, 3852693289, 4206005132, 3787527275, 1471785983, 2589388076, 631286274, 3524096200, 590972337, 1887865600, 1760603763, 643231370, 2643740969, 2388499010, 1722852753, 645073667, 3177739276, 1242181637, 2984331308, 567911875, 753620395, 3743678155, 4278357119, 2815496781, 1270587449, 4259346098, 589049437, 3257834517, 3637173709, 2882662502, 2892380404, 1843952012, 2832065071, 1053718106, 330418109, 3909969653, 916711438, 3709287944, 2455153252, 763050070, 1667025352, 3019273370, 3814458403, 1093369006, 3332713718, 752637853, 100085835, 523535862, 4068027345, 1845694557, 2754500540, 3395089568, 2675873208, 525907800, 937117572, 3313729567, 1112554253, 114888315, 619966459, 1641381760, 1017743298, 1178701646, 1581336326, 362103885, 3516308826, 869224156, 376989708, 633412018, 1074308065, 3818889570, 4249601414, 2417156426, 2229939059, 1313267093, 2929434755, 783116601, 1643811645, 996372459, 3352907069, 953035592, 1641549976, 2112115418, 1350813227, 3528081888, 1136982588, 1390912242, 2659886726, 1031606598, 2617877628]
b'\x04\xd6k\xe5:\x9a\xabu\xb3\r\x06\xd9\x8e\x04\x87\xc7\x10\xecv\x0bG,\x9c\xb5\xb5q\xd6\x9c\xb8\xb7\xb1d'
b'CT\x1a>\x12\x8ff"\x89\xde\x9a\x0f\xf4\xac\xa2\xe7\xd2%\x15\xdd`\x03\xf4?u\x07#\xf9\x03\xde\xd4\x97'

源码：

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
import hashlib
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import os
from my_own_flag import flag

def MT_19937(num,en_c):
    seed1 = os.urandom(16)
    random.seed(seed1)
    number = []
    for i in range(num):
        number.append(random.getrandbits(32))
    cal = 0
    for i in range(num,num+en_c):
        cal += random.getrandbits(32)
    return number,cal

def encrypt(cal,flag):
    key = hashlib.sha256(str(cal).encode()).digest()
    A = AES.new(key, AES.MODE_ECB)
    c = A.encrypt(pad(flag,16))
    return c

def main():
    LEN = len(flag)
    m1,m2 = flag[:LEN//2],flag[LEN//2:]

    Num = 624
    # encrypt m1
    K1 = MT_19937(Num,Num)
    c1 = encrypt(K1[1],m1)

    # encrypt m1
    K2 = MT_19937(Num, Num//4)
    c2 = encrypt(K2[1], m2)

    with open('data.txt','w') as f:
        f.write(str(K1[0])+'\n')
        f.write(str(K2[0][:600])+'\n')
        f.write(str(c1)+'\n')
        f.write(str(c2)+'\n')

if __name__ == '__main__':
    main()

参考

mt19937 - Liooooo - 博客园

浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台

MT19937伪随机数算法，生成范围在 [232−1][232−1] 的均匀分布的32位整数，该算法的周期为219937−1219937−1，故名为 MT19937

最简单的题/(ㄒoㄒ)/~~

两部分，第一部分就是最常见的已知MT19937 的624组32比特连续随机数，预测后续的随机数问题

第二部分就是当已知超过397组连续的32位比特随机数，预测625位之后32比特随机数问题

当获得连续n个（398<=n<=624）完整的伪随机数输出单元序列时，可以对从624-n个伪随机数输出单元后的，连续n-397个输出进行预测。即下一次Twist后的对应单元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
输入：随机数输出序列R1[]

输出：随机数输出序列R2[]

1:        「function」 F(R1[]):

2:                l = len(R1)

3:                assert l > 397

4:                for i from 0 to l-397:

5:                        y = R1[i] & 0x80000000 + R1[i+1] & 0x7fffffff

6:                         R2[i] = (y >> 1) ^ R1[i+397]

7:                        if y % 2 != 0:

8:                                R2[i] ^= 0x9908b0df

9:                return R2

10:        end function

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
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
from Crypto.Util.number import *
from Crypto.Cipher import AES
import gmpy2
import hashlib
from extend_mt19937_predictor import ExtendMT19937Predictor
from Crypto.Util.Padding import pad, unpad

K2 = [2137201486, 2243095490, 3817098931, 229608464, 73854451, 2470370137, 647955184, 1997583099, 2122796155, 3754429965, 915090235, 3330907022, 4045925639, 1616378187, 3477748127, 3235608209, 4168058459, 137624259, 2992531650, 509166204, 3920545433, 1915159362, 3901263233, 4228481818, 2816405167, 1786108715, 3305752402, 2384763695, 227465801, 1052658065, 3153900057, 117311308, 1595474528, 1087880165, 3166831564, 1588364714, 528237288, 617272354, 618281932, 1618791873, 3810883062, 894018392, 2575794219, 103568311, 3298607681, 536028939, 3467146346, 2201685940, 1076138845, 918210863, 1341794665, 3456513087, 1710914773, 1894309846, 2312381988, 127727152, 876614149, 1709878784, 1156541415, 1555452594, 182448271, 408344822, 2898434231, 1998211488, 3592206445, 1085073460, 3397525879, 663024038, 3434587726, 2768736843, 617681814, 2865397550, 3463093384, 2746629701, 2006818690, 1121017677, 2047400279, 1921768902, 528024592, 2892263293, 2798869302, 3481658697, 2848153687, 1134481165, 3720776629, 486120970, 2683483151, 3252410704, 2891974166, 2121509882, 4160792826, 2915283137, 4014112386, 1792273527, 805496405, 1407962158, 3622679727, 3512697173, 2901255951, 3111681208, 2877903904, 827923100, 3729787569, 925768344, 923906770, 3606973890, 1181029191, 689515782, 1651144572, 3459362488, 2412684107, 1362064386, 4159398924, 2922809145, 1602978249, 3705882625, 4293462677, 764953390, 4178674632, 2074025926, 1925824438, 2523046149, 1263372335, 1677306491, 760292173, 3736532489, 2036587975, 514100070, 706857874, 1060105302, 2578078966, 2320134376, 3639164974, 1710455599, 45505402, 2407597519, 2537656373, 56251495, 1630733521, 519864415, 1444518872, 513906964, 3852284907, 800496493, 872675679, 3155530732, 683268660, 3856797215, 137673146, 3607443770, 3700387644, 965766446, 2454233777, 954672952, 2855774032, 3552757435, 3025907069, 1402938518, 3041387870, 3456472325, 447871942, 1327563590, 620160190, 1007188755, 180115074, 52020277, 1774723235, 2887773879, 3508414970, 3631951842, 1763635376, 1924307117, 4204987693, 2494477117, 4017134019, 368620157, 2814392181, 2199699352, 1158269085, 2580589087, 1747804339, 1012560482, 933361529, 176586313, 2808905110, 83750114, 3090684109, 1767704883, 4189833886, 4249260150, 2157821862, 2112716220, 261010276, 3168798078, 1920566780, 1823590666, 2244335700, 2816218464, 3295774792, 2283997010, 3733740723, 3169836042, 1782097885, 1421909608, 3071286976, 2529056825, 2917504380, 2500113967, 1340022169, 1325786585, 2696541388, 3763160733, 3603998832, 72655495, 2892272720, 2785458061, 1724578654, 2144338844, 2899719547, 318345339, 2511462884, 3220707099, 1676208778, 2586878575, 3209502577, 3013180194, 2700788434, 3611106949, 1712906930, 3381158761, 962420077, 1928661992, 1241692316, 3587734972, 2361851891, 729570171, 1255993130, 2059230370, 3819451535, 2490865889, 1229457976, 3062266381, 3350574651, 1861939269, 3074031276, 1122137253, 3267903554, 2691684836, 3042505532, 1103427454, 2126863565, 3686667924, 4181984974, 238390653, 2037278833, 2930470784, 424623283, 3074336567, 4019540123, 447553681, 491252047, 2134100060, 3683266682, 2218397687, 1535505498, 628745497, 445350701, 186184731, 3190072310, 1084556173, 277509904, 2898643406, 4292667973, 2903270520, 2565372604, 303440546, 1808627640, 3069152665, 2075086265, 350493108, 3426866771, 1167370872, 2856612905, 1133769957, 2168578594, 361418126, 1788736419, 3450707887, 1988560242, 3106183307, 420765626, 1595814948, 813997149, 2474462651, 3945801301, 1785414095, 4177305184, 3071687740, 1273724577, 4178527412, 2536332142, 2692000853, 2172897829, 1472311250, 1630835977, 2274186143, 3947343331, 1836099636, 3955763613, 271610193, 2479541262, 3666471942, 4217699594, 341808580, 1517926781, 3311123634, 1738600938, 3870938757, 2309182531, 3189576099, 1594683626, 1900151562, 3625455382, 3527220315, 471268317, 4085391597, 1205291118, 1903466784, 934489768, 717103328, 407385599, 1146912039, 2148396650, 3906209540, 3002211292, 4003244728, 1595357238, 4224659669, 3679773598, 1554305724, 1879798896, 856183762, 2448013518, 2839667183, 3541976537, 1201501683, 2210517506, 3074699110, 2545660131, 3696626258, 1684534318, 3093429986, 2603224784, 3784468515, 1931537793, 570789340, 376758771, 2307788100, 2180860578, 201860820, 3293433128, 1396840567, 2231737923, 3343569549, 890147328, 3369945506, 3155052764, 4225372249, 3097945008, 1976073442, 1939061106, 3009821364, 3636790064, 1722351481, 571067187, 3660829870, 625774796, 962877120, 4093260308, 2994561947, 1780515932, 4180215026, 4252365298, 2947348994, 2484307881, 1869054839, 1567538899, 2381016872, 650248596, 2837463974, 3547259433, 1653667021, 276270749, 1685266082, 3605301102, 3560229703, 3732548108, 3643340502, 2787020632, 301650068, 1692193275, 3053122330, 446613045, 753748541, 3639322954, 2521151846, 3846032512, 2540737292, 1022192711, 4242180248, 2050165414, 2033316505, 3063183472, 2547887329, 1562411323, 2846186023, 1057549601, 200005518, 2515317663, 614142733, 2822762719, 1111596810, 730033186, 3539522165, 2876952827, 1093300071, 2988803720, 2788643910, 1815173676, 923492540, 1571870569, 1732017323, 3912738621, 1932484987, 1369226061, 1043943980, 659920686, 87860672, 3117771700, 536701, 1276716714, 399069847, 675178237, 4148780498, 2293633457, 510556418, 3306441120, 3969884840, 931665570, 1269866789, 1486094185, 1896845492, 2955478105, 3949294788, 2483398248, 2792552965, 367597061, 955979053, 4141216471, 3162398417, 783759084, 605101703, 3200303074, 1835668453, 3586071304, 2174558649, 2997422459, 3634493394, 4138976583, 164027380, 490279465, 2469644175, 43130477, 1547916166, 2406583577, 1303190434, 1431585058, 1519905099, 1079834268, 231749295, 1635997362, 1423407810, 2814537500, 2894136671, 3686889877, 1812711299, 4226627996, 3754118359, 20804048, 4285391186, 2958387414, 2233166520, 3070925064, 1320913219, 2976334802, 4041836979, 382095839, 1388937175, 1819247059, 3838255239, 3380204370, 3935811842, 2751480313, 164540071, 2340071112, 610666648, 595972300, 2011517128, 213838138, 4255091509, 3777157969, 2402199559, 3852693289, 4206005132, 3787527275, 1471785983, 2589388076, 631286274, 3524096200, 590972337, 1887865600, 1760603763, 643231370, 2643740969, 2388499010, 1722852753, 645073667, 3177739276, 1242181637, 2984331308, 567911875, 753620395, 3743678155, 4278357119, 2815496781, 1270587449, 4259346098, 589049437, 3257834517, 3637173709, 2882662502, 2892380404, 1843952012, 2832065071, 1053718106, 330418109, 3909969653, 916711438, 3709287944, 2455153252, 763050070, 1667025352, 3019273370, 3814458403, 1093369006, 3332713718, 752637853, 100085835, 523535862, 4068027345, 1845694557, 2754500540, 3395089568, 2675873208, 525907800, 937117572, 3313729567, 1112554253, 114888315, 619966459, 1641381760, 1017743298, 1178701646, 1581336326, 362103885, 3516308826, 869224156, 376989708, 633412018, 1074308065, 3818889570, 4249601414, 2417156426, 2229939059, 1313267093, 2929434755, 783116601, 1643811645, 996372459, 3352907069, 953035592, 1641549976, 2112115418, 1350813227, 3528081888, 1136982588, 1390912242, 2659886726, 1031606598, 2617877628, 1312353038, 1900681283, 601887302, 2769720460, 1217709138, 3563667637, 869537706, 2633853939, 1122781822, 182927757, 2254745080, 2811590437, 1721572654, 1428436730, 1530693342, 1127968140, 3076075258, 2498327846, 3359243428, 1067527473, 930785791, 3388263672, 482739763, 3879109524]
K1_num =  [1212937457, 714280275, 2934808054, 289447810, 634020656, 2582053193, 2648476152, 3584472561, 2877037797, 1051288028, 3007240724, 3583122714, 2377373219, 2233668169, 2300136290, 4277363949, 572508719, 3707687803, 868724505, 2234515288, 2182162330, 2354654192, 3676064525, 16386761, 1934246009, 396534601, 3406538372, 1978740790, 51554945, 1642830773, 3255471879, 249329746, 1871028531, 1670146144, 3955249559, 3523216280, 4225679888, 1979625069, 1711120506, 4224015378, 2357192253, 1437719734, 1861766583, 252037050, 3805173581, 3845899039, 239338040, 3335618070, 1909354144, 2380236080, 3120658839, 2738735651, 1749563272, 4028406006, 198730175, 4095736523, 2224365497, 1850797931, 123559677, 277130374, 1547602417, 2312967225, 1064405558, 620877831, 4182002366, 2717144120, 2424475877, 1261886189, 2666842961, 1250633055, 1445939400, 2496676732, 46718503, 1726056600, 2892333819, 3874613567, 2801764620, 3279121957, 62950328, 14090298, 3016963976, 235881318, 1152787765, 3549713637, 3184265794, 461262349, 1835258817, 706701716, 366259495, 2484440259, 2306336615, 2418024433, 107268664, 3018120752, 3915797798, 1685880034, 2782876985, 2876720582, 3803172243, 1745503879, 1965535595, 2831775453, 3139448870, 770826076, 559187920, 4292272948, 86904027, 1821662944, 58381562, 250790584, 2122997254, 2937312684, 3225034461, 1493971528, 913420791, 2911905254, 2938402784, 1430747115, 2654595902, 3315197237, 602765188, 1471009311, 3788529131, 913593424, 3280524381, 1554400422, 3250536147, 3480550436, 821401975, 3216026683, 762420368, 1733854366, 2395038075, 533527872, 3040490234, 2855012365, 2984904790, 2830464734, 2200935030, 523059886, 3795772367, 2905400361, 667720140, 3155311553, 1860651089, 1053555607, 2889478721, 1812821011, 3391980212, 3433665687, 2480476597, 1319654037, 1076583906, 2287201297, 966928688, 2542225146, 2246098689, 3117124345, 1844896511, 3104215564, 1303510082, 2924158615, 3648677443, 3308489255, 3809196505, 3199516268, 2254502655, 2126047470, 1763846642, 3851973930, 1280609700, 2415985988, 1312349771, 2103486452, 4229394974, 1937464844, 2763672456, 1366425769, 1532462738, 1864298394, 1203192658, 3679892306, 4138733297, 39437090, 1317880030, 132948638, 2315846286, 3394291148, 3207221552, 3834885856, 2367158425, 3183864791, 3303289072, 519407526, 4127464161, 1556426685, 2427155757, 2010011401, 2823249259, 3638339516, 2266010959, 345885116, 471672470, 2713191580, 731238671, 1694687550, 2523761501, 3533913138, 163820753, 1829608711, 587056408, 1129980234, 3642159144, 2546599527, 758703728, 1713442774, 1864598338, 2763096157, 2308766766, 1132350895, 2776604596, 1921085522, 1409581297, 2643399928, 3285649744, 1248611904, 2694186262, 2676127368, 2579578748, 3784393865, 2655293049, 1378866508, 1251610536, 1048557165, 3045231444, 4236456301, 2496231577, 4118010676, 3079411364, 2425576144, 2431718306, 543894373, 118186072, 2594647421, 1833894329, 3876640493, 1916631983, 2765860034, 3905895682, 2207230275, 2554838603, 3199831939, 2516271151, 3080023814, 3594335532, 1197450849, 2621744299, 447615180, 1616950869, 3109651542, 2553431350, 4165466937, 2130063794, 1459492895, 1141470511, 948009682, 325807524, 1681494454, 3137320840, 4219461371, 609761579, 942363481, 2404858793, 1697226342, 830264373, 230968933, 831865647, 4164463522, 2968510743, 1464271639, 1397831008, 2559413030, 3515044508, 772056268, 3152446673, 3117754594, 833212973, 4252629747, 2565179775, 3005093783, 3595030314, 4042182692, 298671165, 3183128227, 3429794312, 4122368172, 1900961662, 3589294443, 3190786481, 1744404482, 1921785452, 3011999869, 642164068, 3695788414, 2275346981, 1428956574, 2697326707, 2202213004, 3287889517, 919861723, 726410498, 337174656, 2417998504, 2752587611, 3856581958, 141509063, 1762431188, 2065705145, 2031960873, 1892209091, 2395039500, 1058479586, 1537034270, 502217054, 3102018820, 1433274316, 1372952271, 2918921770, 239909451, 1398298200, 2339489735, 372558373, 2263872236, 2426192905, 337209508, 3983991978, 2574803724, 2837664572, 1569892789, 2625063195, 3262762020, 24150029, 2016099290, 2239153990, 85602273, 973040529, 2956276779, 4218049523, 2043716624, 2788573458, 1218787308, 939708241, 2861205992, 2427634523, 4128874493, 2326852266, 2593724377, 1680473968, 2763572707, 4240616686, 2863701585, 3551633590, 1765256405, 2110583291, 357590304, 2511138801, 859903599, 35591840, 3786321031, 3559501147, 3107666783, 2356867678, 1369801910, 2488594855, 2148205170, 3944224524, 2219844222, 466009157, 2328231114, 2777059464, 1585865212, 2871297568, 2558165993, 1561563095, 438633926, 2619385032, 2185942244, 2501145168, 2161107203, 912485991, 3956413626, 4065963551, 1527306118, 378382496, 1016367697, 82832444, 2484726280, 867566307, 1037338825, 4291735272, 901722138, 3956112428, 1060890097, 4210262544, 2525835262, 786274933, 2563584713, 2738164238, 3438656534, 564065202, 3288501195, 1074332184, 2947775555, 3790174897, 3607901153, 2332098514, 3648669449, 3879104921, 3983960923, 548882335, 1817587379, 1555057777, 2705918139, 2755720626, 2706833366, 2947946695, 3082750952, 2323554320, 1804494628, 1677086381, 2771841028, 2470056271, 3431120732, 4073503495, 2929631518, 80800254, 605951710, 1664206366, 2498279527, 360922649, 2590660538, 3724444465, 3559953317, 3002864163, 3369368155, 1569518356, 3831143803, 4184782515, 1602338537, 2640186368, 2864951447, 514648741, 887020932, 166121609, 476244781, 2238614863, 3039706334, 3586500526, 3038068930, 3989751746, 3699955508, 3559348520, 884358906, 444882591, 3769021913, 3665754928, 1911261614, 1234192084, 3450557803, 3232410240, 494096069, 660552292, 1365481833, 520081058, 1027987838, 3165505556, 1257833693, 2146291679, 3634622224, 589123893, 1195030125, 1602406253, 772753497, 2661121530, 2938530200, 1070706826, 3890477657, 2112901265, 4253917692, 2291562806, 67613984, 2608069358, 1726139310, 3018885048, 367067728, 3838771641, 1357927847, 2616452172, 722979624, 4153031784, 607660099, 3164865398, 3199368055, 1885230388, 1055777913, 3475913336, 1546318749, 578282810, 1558944130, 2955660875, 2214838829, 4202836988, 1405916968, 2593459723, 3648360966, 3644813488, 598912719, 876098814, 355483438, 685352898, 4099087273, 2983380912, 450980374, 2753208777, 429297943, 3462109454, 3134522829, 2064548393, 2200750558, 4247753845, 251220053, 1556849099, 2022648175, 3563632884, 2175932589, 1463719656, 1887673611, 3541708446, 3033219582, 3255799816, 534398633, 3481196045, 825005812, 1629237540, 640085217, 899503755, 3105157116, 488231507, 2708835929, 2648663900, 2048030022, 1503411342, 4059850866, 1281156549, 3171426598, 2637361895, 1110841056, 606897504, 3001264062, 912267483, 148124465, 202684836, 1425732680, 3637635336, 1455737055, 2977077407, 54987379, 1056796337, 1832170261, 1870208138, 4074249428, 2993704297, 381772606, 2362720677, 2164369676, 250156737, 3409786877, 1590821450, 2959971180, 3682255149, 302283211, 4204651015, 1294232346, 3088162584, 4209012441, 784333825, 1275400791, 885466807, 1249631254, 1236809354, 2627231325, 2391839654, 1638467843, 2797229961, 3799496431, 237846505, 3432655604, 1690038717, 1493561006, 4229115929, 3784624191, 2891696687, 3557702324, 1120718375, 2593253432, 1415584860, 551110044, 1510986691, 3267929936, 2341598281, 247215742, 3192053018, 2856032615, 3290505354, 907961089, 4128700570, 4195745607, 2035634741, 1047086449, 216435127, 1997121891, 3391563810, 2813128796, 1517545322]
K2_num =  [2137201486, 2243095490, 3817098931, 229608464, 73854451, 2470370137, 647955184, 1997583099, 2122796155, 3754429965, 915090235, 3330907022, 4045925639, 1616378187, 3477748127, 3235608209, 4168058459, 137624259, 2992531650, 509166204, 3920545433, 1915159362, 3901263233, 4228481818, 2816405167, 1786108715, 3305752402, 2384763695, 227465801, 1052658065, 3153900057, 117311308, 1595474528, 1087880165, 3166831564, 1588364714, 528237288, 617272354, 618281932, 1618791873, 3810883062, 894018392, 2575794219, 103568311, 3298607681, 536028939, 3467146346, 2201685940, 1076138845, 918210863, 1341794665, 3456513087, 1710914773, 1894309846, 2312381988, 127727152, 876614149, 1709878784, 1156541415, 1555452594, 182448271, 408344822, 2898434231, 1998211488, 3592206445, 1085073460, 3397525879, 663024038, 3434587726, 2768736843, 617681814, 2865397550, 3463093384, 2746629701, 2006818690, 1121017677, 2047400279, 1921768902, 528024592, 2892263293, 2798869302, 3481658697, 2848153687, 1134481165, 3720776629, 486120970, 2683483151, 3252410704, 2891974166, 2121509882, 4160792826, 2915283137, 4014112386, 1792273527, 805496405, 1407962158, 3622679727, 3512697173, 2901255951, 3111681208, 2877903904, 827923100, 3729787569, 925768344, 923906770, 3606973890, 1181029191, 689515782, 1651144572, 3459362488, 2412684107, 1362064386, 4159398924, 2922809145, 1602978249, 3705882625, 4293462677, 764953390, 4178674632, 2074025926, 1925824438, 2523046149, 1263372335, 1677306491, 760292173, 3736532489, 2036587975, 514100070, 706857874, 1060105302, 2578078966, 2320134376, 3639164974, 1710455599, 45505402, 2407597519, 2537656373, 56251495, 1630733521, 519864415, 1444518872, 513906964, 3852284907, 800496493, 872675679, 3155530732, 683268660, 3856797215, 137673146, 3607443770, 3700387644, 965766446, 2454233777, 954672952, 2855774032, 3552757435, 3025907069, 1402938518, 3041387870, 3456472325, 447871942, 1327563590, 620160190, 1007188755, 180115074, 52020277, 1774723235, 2887773879, 3508414970, 3631951842, 1763635376, 1924307117, 4204987693, 2494477117, 4017134019, 368620157, 2814392181, 2199699352, 1158269085, 2580589087, 1747804339, 1012560482, 933361529, 176586313, 2808905110, 83750114, 3090684109, 1767704883, 4189833886, 4249260150, 2157821862, 2112716220, 261010276, 3168798078, 1920566780, 1823590666, 2244335700, 2816218464, 3295774792, 2283997010, 3733740723, 3169836042, 1782097885, 1421909608, 3071286976, 2529056825, 2917504380, 2500113967, 1340022169, 1325786585, 2696541388, 3763160733, 3603998832, 72655495, 2892272720, 2785458061, 1724578654, 2144338844, 2899719547, 318345339, 2511462884, 3220707099, 1676208778, 2586878575, 3209502577, 3013180194, 2700788434, 3611106949, 1712906930, 3381158761, 962420077, 1928661992, 1241692316, 3587734972, 2361851891, 729570171, 1255993130, 2059230370, 3819451535, 2490865889, 1229457976, 3062266381, 3350574651, 1861939269, 3074031276, 1122137253, 3267903554, 2691684836, 3042505532, 1103427454, 2126863565, 3686667924, 4181984974, 238390653, 2037278833, 2930470784, 424623283, 3074336567, 4019540123, 447553681, 491252047, 2134100060, 3683266682, 2218397687, 1535505498, 628745497, 445350701, 186184731, 3190072310, 1084556173, 277509904, 2898643406, 4292667973, 2903270520, 2565372604, 303440546, 1808627640, 3069152665, 2075086265, 350493108, 3426866771, 1167370872, 2856612905, 1133769957, 2168578594, 361418126, 1788736419, 3450707887, 1988560242, 3106183307, 420765626, 1595814948, 813997149, 2474462651, 3945801301, 1785414095, 4177305184, 3071687740, 1273724577, 4178527412, 2536332142, 2692000853, 2172897829, 1472311250, 1630835977, 2274186143, 3947343331, 1836099636, 3955763613, 271610193, 2479541262, 3666471942, 4217699594, 341808580, 1517926781, 3311123634, 1738600938, 3870938757, 2309182531, 3189576099, 1594683626, 1900151562, 3625455382, 3527220315, 471268317, 4085391597, 1205291118, 1903466784, 934489768, 717103328, 407385599, 1146912039, 2148396650, 3906209540, 3002211292, 4003244728, 1595357238, 4224659669, 3679773598, 1554305724, 1879798896, 856183762, 2448013518, 2839667183, 3541976537, 1201501683, 2210517506, 3074699110, 2545660131, 3696626258, 1684534318, 3093429986, 2603224784, 3784468515, 1931537793, 570789340, 376758771, 2307788100, 2180860578, 201860820, 3293433128, 1396840567, 2231737923, 3343569549, 890147328, 3369945506, 3155052764, 4225372249, 3097945008, 1976073442, 1939061106, 3009821364, 3636790064, 1722351481, 571067187, 3660829870, 625774796, 962877120, 4093260308, 2994561947, 1780515932, 4180215026, 4252365298, 2947348994, 2484307881, 1869054839, 1567538899, 2381016872, 650248596, 2837463974, 3547259433, 1653667021, 276270749, 1685266082, 3605301102, 3560229703, 3732548108, 3643340502, 2787020632, 301650068, 1692193275, 3053122330, 446613045, 753748541, 3639322954, 2521151846, 3846032512, 2540737292, 1022192711, 4242180248, 2050165414, 2033316505, 3063183472, 2547887329, 1562411323, 2846186023, 1057549601, 200005518, 2515317663, 614142733, 2822762719, 1111596810, 730033186, 3539522165, 2876952827, 1093300071, 2988803720, 2788643910, 1815173676, 923492540, 1571870569, 1732017323, 3912738621, 1932484987, 1369226061, 1043943980, 659920686, 87860672, 3117771700, 536701, 1276716714, 399069847, 675178237, 4148780498, 2293633457, 510556418, 3306441120, 3969884840, 931665570, 1269866789, 1486094185, 1896845492, 2955478105, 3949294788, 2483398248, 2792552965, 367597061, 955979053, 4141216471, 3162398417, 783759084, 605101703, 3200303074, 1835668453, 3586071304, 2174558649, 2997422459, 3634493394, 4138976583, 164027380, 490279465, 2469644175, 43130477, 1547916166, 2406583577, 1303190434, 1431585058, 1519905099, 1079834268, 231749295, 1635997362, 1423407810, 2814537500, 2894136671, 3686889877, 1812711299, 4226627996, 3754118359, 20804048, 4285391186, 2958387414, 2233166520, 3070925064, 1320913219, 2976334802, 4041836979, 382095839, 1388937175, 1819247059, 3838255239, 3380204370, 3935811842, 2751480313, 164540071, 2340071112, 610666648, 595972300, 2011517128, 213838138, 4255091509, 3777157969, 2402199559, 3852693289, 4206005132, 3787527275, 1471785983, 2589388076, 631286274, 3524096200, 590972337, 1887865600, 1760603763, 643231370, 2643740969, 2388499010, 1722852753, 645073667, 3177739276, 1242181637, 2984331308, 567911875, 753620395, 3743678155, 4278357119, 2815496781, 1270587449, 4259346098, 589049437, 3257834517, 3637173709, 2882662502, 2892380404, 1843952012, 2832065071, 1053718106, 330418109, 3909969653, 916711438, 3709287944, 2455153252, 763050070, 1667025352, 3019273370, 3814458403, 1093369006, 3332713718, 752637853, 100085835, 523535862, 4068027345, 1845694557, 2754500540, 3395089568, 2675873208, 525907800, 937117572, 3313729567, 1112554253, 114888315, 619966459, 1641381760, 1017743298, 1178701646, 1581336326, 362103885, 3516308826, 869224156, 376989708, 633412018, 1074308065, 3818889570, 4249601414, 2417156426, 2229939059, 1313267093, 2929434755, 783116601, 1643811645, 996372459, 3352907069, 953035592, 1641549976, 2112115418, 1350813227, 3528081888, 1136982588, 1390912242, 2659886726, 1031606598, 2617877628]
c1 =  b'\x04\xd6k\xe5:\x9a\xabu\xb3\r\x06\xd9\x8e\x04\x87\xc7\x10\xecv\x0bG,\x9c\xb5\xb5q\xd6\x9c\xb8\xb7\xb1d'
c2 =  b'CT\x1a>\x12\x8ff"\x89\xde\x9a\x0f\xf4\xac\xa2\xe7\xd2%\x15\xdd`\x03\xf4?u\x07#\xf9\x03\xde\xd4\x97'


pre = ExtendMT19937Predictor()
for i in K1_num:
    pre.setrandbits(i,32)

num = 0
for i in range(624):
    num += pre.predict_getrandbits(32)
key = hashlib.sha256(str(num).encode()).digest()
A = AES.new(key, AES.MODE_ECB)
flag1 = unpad(A.decrypt(c1),16)

def _int32(x):
    return int(0xFFFFFFFF & x)

def F(R1):
    l = len(R1)
    assert l > 397
    R2 = [0] * len(R1)  # 初始化R2数组，与R1长度相同，用于存储结果
    for i in range(l - 397):
        y = _int32(R1[i] & 0x80000000) + (R1[(i + 1) % l] & 0x7fffffff)
        R2[i] = (y >> 1) ^ R1[(i + 397) % l]
        if y % 2 != 0:
            R2[i] = R2[i]^0x9908b0df
    return R2

def twist(mt):
    for i in range(0, 3):
        y = _int32((mt[i] & 0x80000000) + (mt[(i + 1) % 624] & 0x7fffffff))
        mt[i] = (y >> 1) ^ mt[(i + 397) % 624]
        if y % 2 != 0:
            mt[i] = mt[i] ^ 0x9908b0df
    return mt


def extract_number1(mt):
    # mti = 0
    y = mt
    y = y ^ y >> 11
    y = y ^ y << 7 & 2636928640
    y = y ^ y << 15 & 4022730752
    y = y ^ y >> 18
    # mti = (mti + 1) % 624
    return _int32(y)

def reverse_right(x,bit,mask=0xffffffff):
    tmp=x
    for _ in range(32//bit):
        tmp=x^tmp>>bit&mask
    return tmp

def reverse_left(x,bit,mask=0xffffffff):
    tmp=x
    for _ in range(32//bit):
        tmp=x^tmp<<bit&mask
    return tmp

def reverse_extract_number(m):
    m=reverse_right(m,18)
    m=reverse_left(m,15,4022730752)
    m=reverse_left(m,7,2636928640)
    m=reverse_right(m,11)
    return m&0xffffffff


K2_re = []
for i in K2_num:
    K2_re.append(reverse_extract_number(i))

K2_next = F(K2_re)
print(K2_next)

num1 = 0
for i in K2_next[:156]:
    num1 += extract_number1(i)

key = hashlib.sha256(str(num1).encode()).digest()
A = AES.new(key, AES.MODE_ECB)
flag2 = unpad(A.decrypt(c2),16)
print(flag2)

flag = flag1+flag2
print(flag)

运行得到flag

最后flag为

1
SHCTF{TH1s_1s_YoU5_5TART_WAY_0F_CTF}

[Week4] baby_rsa

题目描述:

1
只有中间未知？

源码:

1
2
3
4
5
6
7
#https://github.com/jvdsn/crypto-attacks
n = 149172698687247343307484774427463947040435385939538317995577802933708356659744781308849658149199463270402946054959026247011496643609722381036883462993606208405454448793748282856217226973570288117498818638210423816294135228225752144034736417495450129714250843040389723696691326017062575682989124677170212774709
e = 117932126002671581139669626170313849654365346787524775666511151162210096339679521576248537514813055641658722582914817481701142826861992970974206985137736311670025047752207632786439134855261541672012123572997654885689727972923659090161642085293034838535696206768459211817851404605357080649176502772728128885161
c = 5560665954852260703690321742771294743847646190564920056638605621636133720600072404637746086157764356927591996611862975162275415163691292729424412545560091018172812509230401361899309377868998693154480684535377865697939714965280441927137203589475324582174585416573174423912557361267766810988676863548944796515
dm = 0x2498aa4c85de5a33d5766f28d879f0df7175f43dd71cd4ab56ab67bf76334e6e3dcb
dl = 0x4c21c14305c34ed8f5e8879452c4ce569ce0789e6b39
d_zj=???

论文题 34940373.pdf

已知的条件是d的高位和低位,猜测d是512bit

直接借用大佬脚本

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
65
66
67
68
69
70
71
72
73
74
75
from Crypto.Util.number import *
from tqdm import *
import itertools

#coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 149172698687247343307484774427463947040435385939538317995577802933708356659744781308849658149199463270402946054959026247011496643609722381036883462993606208405454448793748282856217226973570288117498818638210423816294135228225752144034736417495450129714250843040389723696691326017062575682989124677170212774709
e = 117932126002671581139669626170313849654365346787524775666511151162210096339679521576248537514813055641658722582914817481701142826861992970974206985137736311670025047752207632786439134855261541672012123572997654885689727972923659090161642085293034838535696206768459211817851404605357080649176502772728128885161
c = 5560665954852260703690321742771294743847646190564920056638605621636133720600072404637746086157764356927591996611862975162275415163691292729424412545560091018172812509230401361899309377868998693154480684535377865697939714965280441927137203589475324582174585416573174423912557361267766810988676863548944796515
dm = 0x2498aa4c85de5a33d5766f28d879f0df7175f43dd71cd4ab56ab67bf76334e6e3dcb
dl = 0x4c21c14305c34ed8f5e8879452c4ce569ce0789e6b39

leakh = 270
leakl = 175
dbits = 512
dh = dm * 2^(dbits-leakh)

k_ = e*dh // n

PR.<x,y> = PolynomialRing(Zmod(e*2^leakl))
f = 1 + (k_ + x) * ((n+1) - y) - e*dl

bounds = (2^(dbits - leakh),2^513)
res = small_roots(f,bounds,m=4,d=5)

from gmpy2 import *

pplusq = res[0][1]

pminusq = iroot(pplusq^2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p

d = inverse(e,(p-1)*(q-1))

print("d =",d)
print("p =",p)
print("q =",q)
assert p*q == n
print(long_to_bytes(int(pow(c,d,n))))

最后flag为

1
SHCTF{If_people_do_not_believe_that_mathematics_is_simple,it_is_only_because_they_do_not_realize_how_complicated_life_is.}

[Week4] siDH

output.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
P1=(3722377589495565619388409947786216655637784681305941494147641084588810631146007176891913880271007127410796381111369183814847421656105900790804342643108*x + 8802687499644901060050022727432797409089156524380319488542634490587555795650045132570968389279817924873049502727897060507742746276768059101617693509917 , 3719477936206364187390068985145413157800621156741491559595580900652585286439418248577575633342364501408686579893456793185782751143171546872666909621050*x + 11747436493943707843147767337329761069262174137296210697323632536020627422974942280457502098526627796314363833333722260721915312017545212458579310144482)
Q1=(12915018802277618444467947405666732828949451340216601075081682365787173754226880050603374384885896424371918951679575583901988634116566784032229862869167*x + 9007776929782360909455509476806206197092770009777355629134584109191428394613216631397127762352766433731005414625380856231942679613039804604556902750121 , 3337874847860908062006392359743970721822062807701776864258214454048414930046512179257997474360178458090070482273898812428917737854703385268693787730341*x + 2466887347330511324773080125454207491097000379360268269630202404092782122675750917288514012045044575681782320156449148824691799574240195537304046598804)
R1 =(5658557527226961352379349695298022272034591708614537846197946821664407815672677132716039709980366402273967153471450029112980202032504963557614554232081*x + 11551357271600404735819563619419067751607101807322269228277150670297507970164565732253196369722035427850219878923530600036342343824249401164519444699925 ,265897976893439254153074131180525503299599682872457003045711147421296792144844696453821448204074723372166153583764179699404006841669171292261372682675*x + 724107740695298992152442683362664457782010273239642672266143745994073399611599972677572553191510548840256649548349879064220814619385494208383928832803)
S1 = (4449849950679627875144313300296652171690240777751013993956114741413640793976703228710890484448481014950788184128005223666200974595989394007996227889227*x + 10221990584477216572376167606081943897583234679837301896971110421576150195418475700069646493255665879797854652838863654289069021445601907647135585418877 , 2307462255914883623706392794727437281947383985198148884124180699306428786822285241218884618081037544088797503669931959199490244566153811635971236094925*x + 12114989818233896956637793499130020016761661447768788981097230464243285295294294464715758630408703103345278454759389501739054553571870662915301521850727)



EB1:Elliptic Curve defined by y^2 = x^3 + 6*x^2 + (4189289089477997468544979453822695400500584265495091803346578638134562448932335970687326793676571649785862746844702037419185523428130990204162507604142*x+8453144899752979274082603184674998770084621842778345709593026085665609787243919407101520453085615209143595825360981888699031968367621444521989681207925)*x + (10876663327831437262436092946202594533286519870258843389665958485316202856443113411424811891669071467324995879309148604251803514827408043800152902428079*x+4101994484351838878118339435531362623951299298760741543454654959627592905764432016193446997841956209731202742983657859454109374390742351108699397540937) over Finite Field in i of size 13175843156907117380839252916199345042492186767578363998445663477035843932020761233518914911546024351608607150390087656982982306331019593961154237431807^2
PB1=(400743151686086340244873453949520840608574156208868642818110176396852951486095204394646889447695188912538995843668914636276137300969251924860731987594*x + 8066723303558125260716197269861828046216772084431033719257537396188532673015028142277860187197048570426361924628036485855109504692435989532466549892337 : 7857822094787553865337300888116802881139911120764957076597259295643802343603595437056405429678918577452653990040253270552510408546662517341930347472071*x + 10256174272055348496449952390378894222811363081031264681923652307005325570743231607657784873505317820364596562401946711140198577008958311498216702686123)
QB1=(11265527532569587904111577151486645315441536837729457283471778056974474854267045024868622287870300007236540035625960216806930485893214503444708227243383*x + 11572347052548869297030219234396257199641564118601390459458935400217229709294039384097088201478090062341631595370187207194936531910796633969532025890187 : 1238001162632333913423959416649793026045237600008578022715875560482397022195744581004778851687493893610142113162366180305156034033668836817430095906149*x + 9355808802624221590053977160056741459388657876928397271333623542173291286953283614788931011423156931539777202646167976404136542556319294668512474371234 )


P2 =(26532669647185534216919632454563012758176036840369727404445318596643186844961014237696589494044586519996222505129162421855623059726778064289730847721912630181732006537411094550079658466738877742707225452302161480055637595147605056943238961551962912726857744351864942655080809408252483764908*x + 5812125798407648530557806453276971100052617607817970289640758782839745787156978571675000742270104615849816276857241701143604798144853734688276746422525568056414894955227600694186327090639953921900591841375148784726343182974080826517494429823506784951108570345230509782432748957198973176557 , 18170912231945774226275509320755918597241684399013829358085583068620150918112942721642278196145025327426502604698222039788533590901192438632167767861918617714856305276236364591982716806931138652301078418873525926290927769922064835154806942253196121491744473872376873132890629881196649490629*x + 63449364629814972232211370797703143791798005155742711649921757750076247418977215094671070824854640922496466244527853596337389541043547252641029497892777720706149127263347252874027177102007048788926192874731602916383267663436392366016251960068968104701970215355153537253807070741855232748775)
Q2 =(42136584137812471055239712605979664248723194584329825504113325543473782453710246311097778204257972969988889548651858896024346287087771416233601557428774910464027636344801801157477551245445626845622940230448413907258474601435777417704217302132342224824779399945380325818482777959384425291202*x + 28296368679146068828136641681710295025336645284295264101756993260272669740048044336924939223851691772872478126511624718538627825216594660061759605074294632848971213782292601886969141003803207582527211891134999395005856333909777310102168312969406698423350527993168642419225166941765898216372 , 24252723040347680701413751304028021538994021203882796882406562234397335939592763757242534129915362456370369381794876781527365640074695381315843810927200394729665283960373930566280914193406969798955462142448747998461967647076878739164506097299031556840321385018392828143097654049003741477775*x + 33267720985746675210299288173839504448704818085049573573782475394127405092079693799437115220623519093827817268067436033899592961243028616775476581238880321680412934083591896010475885530871761321530855678932407897123073884230850264069659060055805157529775052479253840099694804476053775909667 )

R2 =(38436619031110865991923879368273825144591134194842250127138499745263028798151562949280051166055337764784928604655345143493484071370950291098970176327526604356876742861468639960728907306223619531997103795068973049143179040759482549370743939713683059322455935027250781363099017038267572070382*x + 41093937892203747071226497194460174684840688215389654564992940699770179304781361874671172244464825887258292329587141807444383894136057220808847808753364679351973663750364054669449905253193218352790909945369307367433850610807189354403253554148345197834701648188048050606356011567979827517009 , 9875876467935369638084938067896432182208690144531378403534745071976760997736224070951195614692508013003420177331978612557059092387961951203758997069353790956443826183851256825228023334285334341067097662506368272794278783481229345549459566223386198635792121370861583720130236996379339906174*x + 19447561977724594192572514756713004769718033798185884029348217371868425699196934174482768588729693090959863175090532851846013603063398325098484647069673894219675495546444516464516218477904028091215303855695854982251862178713199631677332189311907166991170300285734973720209408448016404386279 )

S2 =(71249861083363466146240185589742072416947001294427348758335822282789347285654895938446726327788096800499999553209177039582953195361659982428068926448233527913023420037219259936495112851482429822958147790870077230730091177257985429649031364838060427183913400513554819344862904827490880772682*x + 39578052854960012026255637126705373821483266678906490093269284444545750491201374187150247754423052586191953109246769525121762606083950469754696333553496751583744856481664734887761273029389862834902994256675947446700980363194864181267638836314434750455189422736876156451018780319594859427229 , 39197547329694719539529974714972757635993347219971485992350815969532199306333306049850413360278269128003596216529445446572820778213349500212847637573581492691769295796335260726180320712869520367834322990402467146959135659931987007965917989228442334598796126593765472147605031327475567701086*x + 78070033755581537489222113608059840236619421090183039048402466605471070294742099301510439400541337232022512116279912957923221843363406417706677109027135474092494932420033158293877172615616465938036108381979097606754379539534265853790205211707045379351990977911885255397786139615991362742209 )

EB2:Elliptic Curve defined by y^2 = x^3 + 6*x^2 + (59535702210902206632057724266122403485782121930269490904764357850731481931811358892291834226309250891450990328900036049280010419604141194291637296730727328703913164680567403783556426953678285004014585121686544887056773006148356101004676806983339649844157509652742849487058509475632164255987*x+64852232435177399443640158784531454040944394241934383260903245435876484235545723851033335774817478661385417394748201477353536461419931926490835275348734525706542632524107755972171394421922803412948624633078480838779833967459391738992623265735881364492275499237263259819337503800949666114300)*x + (61050690806389187934769383126786350986004548885068804715147802394614409167263078704960954888018441383310078678346054616498251041749628728818830924510356529523120808407048389377565446266649410216170097464816755297151018034985942268859099759375206161519933062527753348065060632492394513384086*x+8077074439258024172434168944099867368398890225954529153626574422394594541950204447361509876049948251527290252332533540126109187259353923004317852092303146292126930346834737856487032520566066787020590518347408517607586872466242304341998561230199735904938577495873392435708081679419091264767) over Finxte Field in x of size 82049429049937972170744454730593345160514304243739159904783417843550315750231928581899391756256783736403989271048847542926715937076900048775072545358407957727845645357780713979087402767756607414183416359287811818280895339396273490061030555956264309782382325666413874887621917291859821985791^2
PB2=(416996386611953912381825671411217896862273056276393640633857992847371853210568257096183885552618362723081850781382485053310040111838223298831389037016745104797263137119258673015585863160793951306139520262051168484452018201607146541321879548245965120060708406056548188263109428770184470679*x + 20592158493675665198495392336832601510295492846540435551041621150757189812529173392073328659255009380759876334891966292009700608091292588069484836373960820208560629600373809653827704658519366030767296831927997226766001416180323174025471476178795433544546769173932191085724053540646639944729 : 71934255319779473319456231037521357239577461842639834638995781561962276154205648471319881543016508220120521945006188958766711918515927736666300390531510013013219752222136876849357120821173182094753920757720079350217559660597480161836396311343966037676936442963053804573072914962152460674663*x + 79176415376881574459252426057416542844132750411766663750705407197328587941817178923562720329407116594864696212948749892818055154804078699130984677442760292980510087006005991843768472531019069389511942796903023273249068773581958501468457621161962887712050221461681839141585467402591793645894 )
QB2= (81399207896220104838523199229123942836223942998672721447617471088799933546789833887166127001116791183009155784956302068892276943497990222792723633019021458579696541635684638373573953057978849292600240170943085361633813448722609135351165092224283296296707819206674751128093132678767574518299*x + 59565272697509141787703630456883972192553675699784211987893422193583642170431575906952477269198392298815160807657217599332116732898901549042831683061911999197598082798698793498902676161570298508553574866686598052406458954435987817164049241700002339342165193999242704894297418052166335638731 : 21930351134214703951291759959503306221382335091685056420498342039206078305903361133512863350368812584471061688170029056369164678056492881926814997907481142982389978084439411052754236340914978327950474951824251797939798502875399920157660381059113442352137267881283959649753286318015289023163*x + 32177434323242823799795301005877693615760991886819458542076959058162762244773500905362804118528323187241784967539643917408903962138638896033673432863920521413676017199387780524917678271106039934571641676244524711655457465408480508716026824510901729812960266245895067755449573368867399411326 )

enc = 2ba4fd55c06bfcc9d253d3a60ec1eaaa82d482ff671d088b4f1354ebad2400d54a3bdd1dd1e38bf25a334f5fd3ec98ea89

源码:

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
#!/usr/bin/env sage

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from flag import flag

def gen_param(B):
 while True:
  a = randint(B >> 1, B)
  b = randint(B >> 2, B >> 1)
  p = 2**a * 3**b - 1
  if is_prime(p):
   return a, b

def gen_dmap(E):
 return E.isogeny(E.lift_x(ZZ(1)), codomain = E)

def gen_tpt(E, a, b):
 P, Q = [((p + 1) // 2**a) * _ for _ in E.gens()]
 R, S = [((p + 1) // 3**b) * _ for _ in E.gens()]
 return P, Q, R, S

def keygen(EC, b, P, Q, R, S):
 skey = randint(1, 3**b)
 T = R + skey * S
 phi = EC.isogeny(T, algorithm = "factored")
 _phi_dom, _phi_P, _phi_Q = phi.codomain(), phi(P), phi(Q)
 return skey, _phi_dom, _phi_P, _phi_Q


a1,b1 = gen_param(350)
p1 = 2**a1 * 3**b1 - 1
F1.<x> = GF(p1^2, modulus = x**2 + 1)
EC1 = EllipticCurve(F1, [0, 6, 0, 1, 0])
P1, Q1, R1, S1 = gen_tpt(EC, a1, b1)
print(f'P1={P1.xy()}')
print(f'Q1={Q1.xy()}')
print(f'R1={R1.xy()}')
print(f'S1={S1.xy()}')

sk1, _phi1_dom, _phi1_P, _phi1_Q = keygen(EC, b1, P1, Q1, R1, S1)
print(f'EC1:{_phi1_dom}')
print(f'PB1={_phi1_P.xy()}')
print(f'QB2={_phi1_Q.xy()}')

a2,b2 = gen_param(610)
p2 = 2**a2 * 3**b2 - 1
F2.<x> = GF(p2^2, modulus = x**2 + 1)
EC2 = EllipticCurve(F2, [0, 6, 0, 1, 0])
P2, Q2, R2, S2 = gen_tpt(EC, a2, b2)
print(f'P2={P2.xy()}')
print(f'Q2={Q2.xy()}')
print(f'R2={R2.xy()}')
print(f'S2={S2.xy()}')
sk2, _phi2_dom, _phi2_P, _phi2_Q = keygen(EC, b2, P2, Q2, R2, S2)
print(f'EC2:{_phi2_dom}')
print(f'PB2={_phi1_P.xy()}')
print(f'QB2={_phi1_Q.xy()}')

key = md5(long_to_bytes(sk1)).digest()
iv = md5(str(sk2).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
enc = cipher.encrypt(flag)

print(f'enc = {enc.hex()}')

又学到了，这个是SIDH（超奇异同源Diffie-Hellman秘钥交换算法），一种后量子安全秘钥交换协议

Castryck-Decru攻击是一种针对Supersingular Isogeny Diffie-Hellman (SIDH)协议的密钥恢复攻击。该攻击由Wouter Castryck和Thomas Decru于2022年提出，旨在利用椭圆曲线上的扭点信息和秘密同态的度数来计算所需的同态。攻击的核心在于利用椭圆曲线上的小非标量自同态的存在性，从而在多项式时间内恢复出用于生成秘密同态的整数。

论文原文： 975.pdf

攻击代码：GiacomoPope/Castryck-Decru-SageMath: A SageMath implementation of the Castryck-Decru Key Recovery attack on SIDH

p=2a∗3b−1p=2a∗3b−1

其中pp在EB1最后面找到

1
p = 13175843156907117380839252916199345042492186767578363998445663477035843932020761233518914911546024351608607150390087656982982306331019593961154237431807

分解找到aa,bb

\begin{array} \ a_1 = 250 \ b_1 = 159 \ a_2 = 486 \ b_2 = 301 \end{array}

构造椭圆曲线，后面有点超模了

(sage-build)$ sage sol1.sage –parallel

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
import public_values_aux
from public_values_aux import *

load('castryck_decru_shortcut.sage')
load('sandwich_attack.sage')

SIKE_parameters = {
    "SIKEp434" : (216, 137),
    "SIKEp503" : (250, 159),
    "SIKEp610" : (305, 192),
    "SIKEp751" : (372, 239),
    "SIKEp964" : (486, 301), # removed after NIST round 1
}

# Change me to attack different parameter sets
NIST_submission = "SIKEp503"
a, b = SIKE_parameters[NIST_submission]

print(f"Running the attack against {NIST_submission} parameters, which has a prime: 2^{a}*3^{b} - 1")

print(f"Generating public data for the attack...")
# Set the prime, finite fields and starting curve
# with known endomorphism
p = 2^a*3^b - 1
public_values_aux.p = p
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2, num_checks=0) # Speeds things up in Sage

# Generation of the endomorphism 2i
two_i = generate_distortion_map(E_start)

# Generate public torsion points, for SIKE implementations
# these are fixed but to save loading in constants we can
# just generate them on the fly


P =(3722377589495565619388409947786216655637784681305941494147641084588810631146007176891913880271007127410796381111369183814847421656105900790804342643108*i + 8802687499644901060050022727432797409089156524380319488542634490587555795650045132570968389279817924873049502727897060507742746276768059101617693509917 , 3719477936206364187390068985145413157800621156741491559595580900652585286439418248577575633342364501408686579893456793185782751143171546872666909621050*i + 11747436493943707843147767337329761069262174137296210697323632536020627422974942280457502098526627796314363833333722260721915312017545212458579310144482)
Q =(12915018802277618444467947405666732828949451340216601075081682365787173754226880050603374384885896424371918951679575583901988634116566784032229862869167*i + 9007776929782360909455509476806206197092770009777355629134584109191428394613216631397127762352766433731005414625380856231942679613039804604556902750121 , 3337874847860908062006392359743970721822062807701776864258214454048414930046512179257997474360178458090070482273898812428917737854703385268693787730341*i + 2466887347330511324773080125454207491097000379360268269630202404092782122675750917288514012045044575681782320156449148824691799574240195537304046598804)
R =(5658557527226961352379349695298022272034591708614537846197946821664407815672677132716039709980366402273967153471450029112980202032504963557614554232081*i + 11551357271600404735819563619419067751607101807322269228277150670297507970164565732253196369722035427850219878923530600036342343824249401164519444699925 ,265897976893439254153074131180525503299599682872457003045711147421296792144844696453821448204074723372166153583764179699404006841669171292261372682675*i + 724107740695298992152442683362664457782010273239642672266143745994073399611599972677572553191510548840256649548349879064220814619385494208383928832803)
S = (4449849950679627875144313300296652171690240777751013993956114741413640793976703228710890484448481014950788184128005223666200974595989394007996227889227*i + 10221990584477216572376167606081943897583234679837301896971110421576150195418475700069646493255665879797854652838863654289069021445601907647135585418877 , 2307462255914883623706392794727437281947383985198148884124180699306428786822285241218884618081037544088797503669931959199490244566153811635971236094925*i + 12114989818233896956637793499130020016761661447768788981097230464243285295294294464715758630408703103345278454759389501739054553571870662915301521850727)
P2, Q2, P3, Q3 = E_start(P), E_start(Q), E_start(R), E_start(S)
check_torsion_points(E_start, a, b, P2, Q2, P3, Q3)

# Generate Bob's key pair
EB = EllipticCurve(Fp2, [0,6,0,(4189289089477997468544979453822695400500584265495091803346578638134562448932335970687326793676571649785862746844702037419185523428130990204162507604142*i+8453144899752979274082603184674998770084621842778345709593026085665609787243919407101520453085615209143595825360981888699031968367621444521989681207925),(10876663327831437262436092946202594533286519870258843389665958485316202856443113411424811891669071467324995879309148604251803514827408043800152902428079*i+4101994484351838878118339435531362623951299298760741543454654959627592905764432016193446997841956209731202742983657859454109374390742351108699397540937)])
EB.set_order((p+1)**2, num_checks=0)
PB =EB(400743151686086340244873453949520840608574156208868642818110176396852951486095204394646889447695188912538995843668914636276137300969251924860731987594*i + 8066723303558125260716197269861828046216772084431033719257537396188532673015028142277860187197048570426361924628036485855109504692435989532466549892337 ,7857822094787553865337300888116802881139911120764957076597259295643802343603595437056405429678918577452653990040253270552510408546662517341930347472071*i + 10256174272055348496449952390378894222811363081031264681923652307005325570743231607657784873505317820364596562401946711140198577008958311498216702686123)
QB =EB(11265527532569587904111577151486645315441536837729457283471778056974474854267045024868622287870300007236540035625960216806930485893214503444708227243383*i + 11572347052548869297030219234396257199641564118601390459458935400217229709294039384097088201478090062341631595370187207194936531910796633969532025890187, 1238001162632333913423959416649793026045237600008578022715875560482397022195744581004778851687493893610142113162366180305156034033668836817430095906149*i + 9355808802624221590053977160056741459388657876928397271333623542173291286953283614788931011423156931539777202646167976404136542556319294668512474371234)


# ===================================
# =====  ATTACK  ====================
# ===================================

def RunAttack(num_cores):
    return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)

if __name__ == '__main__' and '__file__' in globals():
    if '--parallel' in sys.argv:
        # Set number of cores for parallel computation
        num_cores = os.cpu_count()
        print(f"Performing the attack in parallel using {num_cores} cores")
    else:
        num_cores = 1

    if '--sandwich' in sys.argv:
        # Use the fact that 2^a - 5*3^b is a sum of squares
        assert NIST_submission == "SIKEp964"
        assert two_squares(2^a - 5*3^b)
        recovered_key = SandwichAttack(E_start, P2, Q2, EB, PB, QB, two_i, k=5, alp=0)
    else:
        recovered_key = RunAttack(num_cores)

"""
Computing image of 3-adic torsion in split factor CB
Glue-and-split! These are most likely the secret digits.
Bob's secret key revealed as: 3599349351989826939257244168875987905412334469321466246296914822246846713144
In ternary, this is: [2, 1, 0, 2, 2, 1, 0, 1, 0, 1, 1, 1, 1, 2, 2, 0, 2, 2, 2, 0, 0, 2, 0, 2, 2, 1, 2, 0, 1, 2, 1, 2, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 0, 1, 2, 0, 2, 2, 1, 1, 0, 1, 0, 0, 0, 2, 1, 1, 0, 0, 1, 2, 0, 2, 2, 2, 1, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 2, 2, 1, 1, 1, 2, 2, 2, 0, 1, 0, 0, 1, 0, 0, 2, 1, 2, 1, 1, 2, 2, 1, 0, 0, 0, 2, 1, 2, 0, 2, 1, 0, 2, 2, 1, 1, 2, 1, 1, 1, 0, 0, 1, 2, 2, 0, 1, 0, 1, 2, 0, 2, 1, 0, 2, 1, 0, 1, 1, 2, 0, 2, 2, 0, 0, 0, 1, 1, 1, 1]
Altogether this took 20.913691997528076 seconds.
"""
#sk1 = 3599349351989826939257244168875987905412334469321466246296914822246846713144

(sage-build)$ sage sol2.sage –parallel –sandwich

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
import public_values_aux
from public_values_aux import *

load('castryck_decru_shortcut.sage')
load('sandwich_attack.sage')

SIKE_parameters = {
    "SIKEp434" : (216, 137),
    "SIKEp503" : (250, 159),
    "SIKEp610" : (305, 192),
    "SIKEp751" : (372, 239),
    "SIKEp964" : (486, 301), # removed after NIST round 1
}

# Change me to attack different parameter sets
NIST_submission = "SIKEp964"
a, b = SIKE_parameters[NIST_submission]

print(f"Running the attack against {NIST_submission} parameters, which has a prime: 2^{a}*3^{b} - 1")

print(f"Generating public data for the attack...")
# Set the prime, finite fields and starting curve
# with known endomorphism
p = 2^a*3^b - 1
public_values_aux.p = p
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2, num_checks=0) # Speeds things up in Sage

# Generation of the endomorphism 2i
two_i = generate_distortion_map(E_start)

# Generate public torsion points, for SIKE implementations
# these are fixed but to save loading in constants we can
# just generate them on the fly

P =(26532669647185534216919632454563012758176036840369727404445318596643186844961014237696589494044586519996222505129162421855623059726778064289730847721912630181732006537411094550079658466738877742707225452302161480055637595147605056943238961551962912726857744351864942655080809408252483764908*i + 5812125798407648530557806453276971100052617607817970289640758782839745787156978571675000742270104615849816276857241701143604798144853734688276746422525568056414894955227600694186327090639953921900591841375148784726343182974080826517494429823506784951108570345230509782432748957198973176557 , 18170912231945774226275509320755918597241684399013829358085583068620150918112942721642278196145025327426502604698222039788533590901192438632167767861918617714856305276236364591982716806931138652301078418873525926290927769922064835154806942253196121491744473872376873132890629881196649490629*i + 63449364629814972232211370797703143791798005155742711649921757750076247418977215094671070824854640922496466244527853596337389541043547252641029497892777720706149127263347252874027177102007048788926192874731602916383267663436392366016251960068968104701970215355153537253807070741855232748775)
Q =(42136584137812471055239712605979664248723194584329825504113325543473782453710246311097778204257972969988889548651858896024346287087771416233601557428774910464027636344801801157477551245445626845622940230448413907258474601435777417704217302132342224824779399945380325818482777959384425291202*i + 28296368679146068828136641681710295025336645284295264101756993260272669740048044336924939223851691772872478126511624718538627825216594660061759605074294632848971213782292601886969141003803207582527211891134999395005856333909777310102168312969406698423350527993168642419225166941765898216372 , 24252723040347680701413751304028021538994021203882796882406562234397335939592763757242534129915362456370369381794876781527365640074695381315843810927200394729665283960373930566280914193406969798955462142448747998461967647076878739164506097299031556840321385018392828143097654049003741477775*i + 33267720985746675210299288173839504448704818085049573573782475394127405092079693799437115220623519093827817268067436033899592961243028616775476581238880321680412934083591896010475885530871761321530855678932407897123073884230850264069659060055805157529775052479253840099694804476053775909667 )

R =(38436619031110865991923879368273825144591134194842250127138499745263028798151562949280051166055337764784928604655345143493484071370950291098970176327526604356876742861468639960728907306223619531997103795068973049143179040759482549370743939713683059322455935027250781363099017038267572070382*i + 41093937892203747071226497194460174684840688215389654564992940699770179304781361874671172244464825887258292329587141807444383894136057220808847808753364679351973663750364054669449905253193218352790909945369307367433850610807189354403253554148345197834701648188048050606356011567979827517009 , 9875876467935369638084938067896432182208690144531378403534745071976760997736224070951195614692508013003420177331978612557059092387961951203758997069353790956443826183851256825228023334285334341067097662506368272794278783481229345549459566223386198635792121370861583720130236996379339906174*i + 19447561977724594192572514756713004769718033798185884029348217371868425699196934174482768588729693090959863175090532851846013603063398325098484647069673894219675495546444516464516218477904028091215303855695854982251862178713199631677332189311907166991170300285734973720209408448016404386279 )

S =(71249861083363466146240185589742072416947001294427348758335822282789347285654895938446726327788096800499999553209177039582953195361659982428068926448233527913023420037219259936495112851482429822958147790870077230730091177257985429649031364838060427183913400513554819344862904827490880772682*i + 39578052854960012026255637126705373821483266678906490093269284444545750491201374187150247754423052586191953109246769525121762606083950469754696333553496751583744856481664734887761273029389862834902994256675947446700980363194864181267638836314434750455189422736876156451018780319594859427229 , 39197547329694719539529974714972757635993347219971485992350815969532199306333306049850413360278269128003596216529445446572820778213349500212847637573581492691769295796335260726180320712869520367834322990402467146959135659931987007965917989228442334598796126593765472147605031327475567701086*i + 78070033755581537489222113608059840236619421090183039048402466605471070294742099301510439400541337232022512116279912957923221843363406417706677109027135474092494932420033158293877172615616465938036108381979097606754379539534265853790205211707045379351990977911885255397786139615991362742209 )


P2, Q2, P3, Q3 = E_start(P), E_start(Q), E_start(R), E_start(S)
check_torsion_points(E_start, a, b, P2, Q2, P3, Q3)

# Generate Bob's key pair
EB = EllipticCurve(Fp2, [0,6,0,(59535702210902206632057724266122403485782121930269490904764357850731481931811358892291834226309250891450990328900036049280010419604141194291637296730727328703913164680567403783556426953678285004014585121686544887056773006148356101004676806983339649844157509652742849487058509475632164255987*i+64852232435177399443640158784531454040944394241934383260903245435876484235545723851033335774817478661385417394748201477353536461419931926490835275348734525706542632524107755972171394421922803412948624633078480838779833967459391738992623265735881364492275499237263259819337503800949666114300),(61050690806389187934769383126786350986004548885068804715147802394614409167263078704960954888018441383310078678346054616498251041749628728818830924510356529523120808407048389377565446266649410216170097464816755297151018034985942268859099759375206161519933062527753348065060632492394513384086*i+8077074439258024172434168944099867368398890225954529153626574422394594541950204447361509876049948251527290252332533540126109187259353923004317852092303146292126930346834737856487032520566066787020590518347408517607586872466242304341998561230199735904938577495873392435708081679419091264767)])
EB.set_order((p+1)**2, num_checks=0)
PB =EB(416996386611953912381825671411217896862273056276393640633857992847371853210568257096183885552618362723081850781382485053310040111838223298831389037016745104797263137119258673015585863160793951306139520262051168484452018201607146541321879548245965120060708406056548188263109428770184470679*i + 20592158493675665198495392336832601510295492846540435551041621150757189812529173392073328659255009380759876334891966292009700608091292588069484836373960820208560629600373809653827704658519366030767296831927997226766001416180323174025471476178795433544546769173932191085724053540646639944729 , 71934255319779473319456231037521357239577461842639834638995781561962276154205648471319881543016508220120521945006188958766711918515927736666300390531510013013219752222136876849357120821173182094753920757720079350217559660597480161836396311343966037676936442963053804573072914962152460674663*i + 79176415376881574459252426057416542844132750411766663750705407197328587941817178923562720329407116594864696212948749892818055154804078699130984677442760292980510087006005991843768472531019069389511942796903023273249068773581958501468457621161962887712050221461681839141585467402591793645894 )
QB =EB(81399207896220104838523199229123942836223942998672721447617471088799933546789833887166127001116791183009155784956302068892276943497990222792723633019021458579696541635684638373573953057978849292600240170943085361633813448722609135351165092224283296296707819206674751128093132678767574518299*i + 59565272697509141787703630456883972192553675699784211987893422193583642170431575906952477269198392298815160807657217599332116732898901549042831683061911999197598082798698793498902676161570298508553574866686598052406458954435987817164049241700002339342165193999242704894297418052166335638731 , 21930351134214703951291759959503306221382335091685056420498342039206078305903361133512863350368812584471061688170029056369164678056492881926814997907481142982389978084439411052754236340914978327950474951824251797939798502875399920157660381059113442352137267881283959649753286318015289023163*i + 32177434323242823799795301005877693615760991886819458542076959058162762244773500905362804118528323187241784967539643917408903962138638896033673432863920521413676017199387780524917678271106039934571641676244524711655457465408480508716026824510901729812960266245895067755449573368867399411326 )

# ===================================
# =====  ATTACK  ====================
# ===================================

def RunAttack(num_cores):
    return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)

if __name__ == '__main__' and '__file__' in globals():
    if '--parallel' in sys.argv:
        # Set number of cores for parallel computation
        num_cores = os.cpu_count()
        print(f"Performing the attack in parallel using {num_cores} cores")
    else:
        num_cores = 1

    if '--sandwich' in sys.argv:
        # Use the fact that 2^a - 5*3^b is a sum of squares
        assert NIST_submission == "SIKEp964"
        assert two_squares(2^a - 5*3^b)
        recovered_key = SandwichAttack(E_start, P2, Q2, EB, PB, QB, two_i, k=5, alp=0)
    else:
        recovered_key = RunAttack(num_cores)


"""
Running the attack against SIKEp964 parameters, which has a prime: 2^486*3^301 - 1
Generating public data for the attack...
Performing the attack in parallel using 14 cores
Computed image of 3-adic torsion in split factor C_B
Bob's secret key revealed as: 265224889924040230352809890018188742288829460808797625767564487574491813646343173069577492003667305149036083853277964262066159526193356944364624
In ternary, this is: [2, 0, 1, 1, 2, 2, 1, 1, 2, 1, 1, 0, 2, 0, 1, 2, 1, 1, 2, 2, 2, 2, 0, 0, 0, 1, 2, 1, 2, 0, 2, 1, 1, 2, 2, 2, 2, 2, 0, 0, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 0, 2, 1, 0, 1, 2, 0, 1, 1, 1, 2, 0, 1, 0, 2, 1, 0, 0, 0, 2, 0, 1, 2, 1, 2, 0, 1, 2, 2, 2, 1, 1, 2, 0, 0, 2, 1, 1, 2, 0, 0, 2, 2, 1, 1, 0, 0, 0, 1, 1, 2, 0, 2, 2, 1, 0, 0, 0, 2, 0, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 2, 0, 1, 0, 2, 1, 1, 0, 0, 0, 0, 1, 0, 1, 2, 0, 0, 0, 0, 0, 2, 1, 1, 1, 0, 1, 2, 0, 2, 1, 1, 1, 0, 2, 2, 0, 0, 0, 1, 2, 0, 1, 2, 2, 2, 1, 0, 1, 1, 0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 1, 2, 1, 1, 0, 1, 2, 2, 1, 0, 1, 0, 0, 0, 0, 2, 2, 1, 1, 2, 0, 2, 2, 2, 1, 1, 2, 0, 0, 1, 1, 1, 1, 0, 2, 1, 2, 1, 2, 2, 1, 1, 0, 1, 1, 2, 2, 2, 1, 1, 2, 2, 0, 2, 2, 1, 0, 1, 1, 1, 2, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 2, 1, 1, 2, 2, 1, 0, 0, 1, 2, 1, 1, 1, 1, 2, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 2, 1, 1, 1, 0, 2, 2, 0, 1, 2, 0, 1, 1, 2, 0, 1, 2, 2, 0, 1, 2, 2, 1]
Altogether this took 11.799392223358154 seconds.
"""

#sk2 = 265224889924040230352809890018188742288829460808797625767564487574491813646343173069577492003667305149036083853277964262066159526193356944364624

sol3.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5


sk1 = 3599349351989826939257244168875987905412334469321466246296914822246846713144
sk2 = 265224889924040230352809890018188742288829460808797625767564487574491813646343173069577492003667305149036083853277964262066159526193356944364624
key = md5(long_to_bytes(sk1)).digest()
iv = md5(str(sk2).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)

enc = '2ba4fd55c06bfcc9d253d3a60ec1eaaa82d482ff671d088b4f1354ebad2400d54a3bdd1dd1e38bf25a334f5fd3ec98ea89'
enc = bytes.fromhex(enc)
dec = cipher.decrypt(enc)
print(f'flag = {dec}')

最后flag为

1
SHCTF{The essence of mathematics is its freedom.}

文章作者: yiqing
文章链接: http://yiqing.asia/posts/77778.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 yiqing !
crypto
赏
  目录