2023NewStarCTF

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 8.6k 阅读时长 ≈ 31 分钟

2023NewStarCTF——Crypto——Wp

除了密码，其他的内容建议别看，瞎做的

Week1

Crypto

brainfuck

1
++++++++[>>++>++++>++++++>++++++++>++++++++++>++++++++++++>++++++++++++++>++++++++++++++++>++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++++>++++++++++++++++++++++++>++++++++++++++++++++++++++>++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++<<<<<<<<<<<<<<<<-]>>>>>>>++++++.>----.<-----.>-----.>-----.<<<-.>>++..<.>.++++++.....------.<.>.<<<<<+++.>>>>+.<<<+++++++.>>>+.<<<-------.>>>-.<<<+.+++++++.--..>>>>---.-.<<<<-.+++.>>>>.<<<<-------.+.>>>>>++.

找个网站解密即可

flag{Oiiaioooooiai#b7c0b1866fe58e12}

Caesar’s Secert

1
kqfl{hf3x4w'x_h1umjw_n5_a4wd_3fed}

flag对应kqfl发现移动了5位

凯撒解密网站解密，得到flag{ca3s4r's_c1pher_i5_v4ry_3azy}

Fence

1
fa{ereigtepanet6680}lgrodrn_h_litx#8fc3

栅栏解密网站解密，栅栏数为2

flag{reordering_the_plaintext#686f8c03}

Vigenère

题目描述：le chiffre indéchiffrable

1
pqcq{qc_m1kt4_njn_5slp0b_lkyacx_gcdy1ud4_g3nv5x0}

对表👇，发现f对应p，l对应q，a对应c，g对应q，判断出key=KFCK，而且，题目描述是法语

Vigenere Solver | guballa.de网站解密把English换成French，直接秒了，没用上key

flag{la_c1fr4_del_5ign0r_giovan_batt1st4_b3ll5s0}

babyrsa

题目

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

def gen_prime(n):
    res = 1
    for i in range(15):
        res *= getPrime(n)

    return res


if __name__ == '__main__':
    n = gen_prime(32)
    e = 65537
    m = bytes_to_long(flag)
    c = pow(m,e,n)
    print(n)
    print(c)
# 17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
# 14322038433761655404678393568158537849783589481463521075694802654611048898878605144663750410655734675423328256213114422929994037240752995363595

题目说了n很容易分解，网站解密

得到一堆因子之后就常规解即可，没什么坑

我推荐用Sagemath的factor函数，直接分解n，不用一个一个输值

exp:

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

n = 
c = 

phi = 1
for i in factor(n):
    phi *= i[0] - 1
    
d = gmpy2.invert(65537,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))
#flag{us4_s1ge_t0_cal_phI}

Small d

题目：

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

p = getPrime(1024)
q = getPrime(1024)

d = getPrime(32)
e = inverse(d, (p-1)*(q-1))
n = p*q
m = bytes_to_long(flag)

c = pow(m,e,n)

print(c)
print(e)
print(n)

# c = 6755916696778185952300108824880341673727005249517850628424982499865744864158808968764135637141068930913626093598728925195859592078242679206690525678584698906782028671968557701271591419982370839581872779561897896707128815668722609285484978303216863236997021197576337940204757331749701872808443246927772977500576853559531421931943600185923610329322219591977644573509755483679059951426686170296018798771243136530651597181988040668586240449099412301454312937065604961224359235038190145852108473520413909014198600434679037524165523422401364208450631557380207996597981309168360160658308982745545442756884931141501387954248
# e = 8614531087131806536072176126608505396485998912193090420094510792595101158240453985055053653848556325011409922394711124558383619830290017950912353027270400567568622816245822324422993074690183971093882640779808546479195604743230137113293752897968332220989640710311998150108315298333817030634179487075421403617790823560886688860928133117536724977888683732478708628314857313700596522339509581915323452695136877802816003353853220986492007970183551041303875958750496892867954477510966708935358534322867404860267180294538231734184176727805289746004999969923736528783436876728104351783351879340959568183101515294393048651825
# n = 19873634983456087520110552277450497529248494581902299327237268030756398057752510103012336452522030173329321726779935832106030157682672262548076895370443461558851584951681093787821035488952691034250115440441807557595256984719995983158595843451037546929918777883675020571945533922321514120075488490479009468943286990002735169371404973284096869826357659027627815888558391520276866122370551115223282637855894202170474955274129276356625364663165723431215981184996513023372433862053624792195361271141451880123090158644095287045862204954829998614717677163841391272754122687961264723993880239407106030370047794145123292991433

维纳攻击，网上找个脚本就能出

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

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf


def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator


def solve_pq(a, b, c):
    """使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p，q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)


def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf


def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d


c = 
e = 
n = 

d = wienerAttack(e, n)
print(d)
m = pow(c, d, n)
print(long_to_bytes(m).decode())
# flag{learn_some_continued_fraction_technique#dc16885c}

babyxor

题目：

1
2
3
4
5
6
7
8
9
from secret import *

ciphertext = []

for f in flag:
    ciphertext.append(f ^ key)

print(bytes(ciphertext).hex())
# e9e3eee8f4f7bffdd0bebad0fcf6e2e2bcfbfdf6d0eee1ebd0eabbf5f6aeaeaeaeaeaef2

了解一下异或的性质，通过flag的开头flag{，以及密文的一小部分，即可求出key=143。需要注意类型转换

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
c = "e9e3eee8f4f7bffdd0bebad0fcf6e2e2bcfbfdf6d0eee1ebd0eabbf5f6aeaeaeaeaeaef2"
c = bytes.fromhex(c)

key = ord('f') ^ c[0]
# print(key)
key = 143
m = []
for i in c:
    m.append(i ^ key)

print(bytes(m).hex())
flag = "666c61677b7830725f31355f73796d6d337472795f616e645f65347a792121212121217d"
print(long_to_bytes(int(flag,16)))
#flag{x0r_15_symm3try_and_e4zy!!!!!!}

babyencoding

1
2
3
part 1 of flag: ZmxhZ3tkYXp6bGluZ19lbmNvZGluZyM0ZTBhZDQ=
part 2 of flag: MYYGGYJQHBSDCZJRMQYGMMJQMMYGGN3BMZSTIMRSMZSWCNY=
part 3 of flag: =8S4U,3DR8SDY,C`S-F5F-C(S,S<R-C`Q9F8S87T`

第一部分密文包括大小写字母和数字，判断是base64（具体码表自行了解），网站解密👉Base64解密

第二部分密文只有大写字母，判断是base32（具体码表自行了解），网站解密👉Base32解密

第三部分是UUencode，（不知道判断依据，我硬试出来的），网站解密👉在线UUencode解码

flag{dazzling_encoding#4e0ad4f0ca08d1e1d0f10c0c7afe422fea7c55192c992036ef623372601ff3a}

Affine

题目:

1
2
3
4
5
6
7
8
9
10
11
12
from flag import flag, key

modulus = 256

ciphertext = []

for f in flag:
    ciphertext.append((key[0]*f + key[1]) % modulus)

print(bytes(ciphertext).hex())

# dd4388ee428bdddd5865cc66aa5887ffcca966109c66edcca920667a88312064

设key[0]=a，key[1]=b，密文记作c，密文记作x

于是有等式$c_1 \equiv ax_1 +b \mod 256$，$c_2\equiv ax_2 + b \mod 256$

两式相减得$c_1-c_2 \equiv a(x_1-x_2) \mod 256$，于是$a \equiv (c_1-c_2)\times(x_1-x_2)^{-1} \mod 256$

求出$a$之后，$b \equiv c -ax \mod 256$

有了$a,b$之后，根据$x \equiv (c - b)\times a^{-1} \mod 256$求得$x$

这里$x_1,x_2$从flag的头部flag{选取，需要注意的就是对应上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
from Crypto.Util.number import *
import gmpy2

c = "dd4388ee428bdddd5865cc66aa5887ffcca966109c66edcca920667a88312064"
c = bytes.fromhex(c)

mod = 256
m = b"flag"

a = (c[2]-c[1])*gmpy2.invert((m[2]-m[1]),mod) % mod			
print(a)
#a = 17
b = (c[2] - a*m[2]) % mod
print(b)
#b = 23
flag = []
for i in c:
    flag.append((i-b)*gmpy2.invert(a,mod) % mod)

print(bytes(flag).hex())
flag = "666c61677b346666316e655f6331706865725f69355f766572795f33617a797d"
print(long_to_bytes(int(flag,16)))
#flag{4ff1ne_c1pher_i5_very_3azy}

babyaes

题目：

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


def pad(data):
    return data + b"".join([b'\x00' for _ in range(0, 16 - len(data))])


def main():
    flag_ = pad(flag)
    key = os.urandom(16) * 2
    iv = os.urandom(16)
    print(bytes_to_long(key) ^ bytes_to_long(iv) ^ 1)
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc_flag = aes.encrypt(flag_)
    print(enc_flag)


if __name__ == "__main__":
    main()
# 3657491768215750635844958060963805125333761387746954618540958489914964573229
# b'>]\xc1\xe5\x82/\x02\x7ft\xf1B\x8d\n\xc1\x95i'

根据异或的性质发现，key和iv异或之后，有一半的key是不受影响的，根据这个特性，我们可以求出key

求出key之后反求iv

exp:

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

tmp = 3657491768215750635844958060963805125333761387746954618540958489914964573229 ^ 1
tmp1 = long_to_bytes(tmp)

key = tmp1[:16] * 2
print(key)
#key = b'\x08\x16\x11%\xa0\xa6\xc5\xcb^\x02\x99NF`\xea,\x08\x16\x11%\xa0\xa6\xc5\xcb^\x02\x99NF`\xea,'
iv = long_to_bytes(bytes_to_long(key)^bytes_to_long(tmp1))
print(iv)
#iv = b'\xe3Z\x19Ga>\x07\xcc\xd1\xa1X\x01c\x11\x16\x00'
c = b'>]\xc1\xe5\x82/\x02\x7ft\xf1B\x8d\n\xc1\x95i'
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(c)
print(flag)

flag{firsT_cry_Aes}

Misc

CyberChef’s Secret

1
2
来签到吧！下面这个就是flag，不过它看起来好像怪怪的:-)
M5YHEUTEKFBW6YJWKZGU44CXIEYUWMLSNJLTOZCXIJTWCZD2IZRVG4TJPBSGGWBWHFMXQTDFJNXDQTA=

base32 -> base58 -> base64

flag{Base_15_S0_Easy_^_^}

Reverse

easy_RE

转ASCII码，再拼起来

flag{we1c0me_to_rev3rse!!}

Segments

ida64打开–>shift-F7

flag{You_ar3_g0od_at_f1ding_ELF_segments}

ELF

IDA打开

再查看encode函数

传入字符串s，把s中的每个字符先和0x20异或，再加上16

整个流程就是，用户传入一个字符串s，经过encode()函数加密，再经过base64加密，把base64加密后的字符串和VlxRV2t0II8kX2WPJ15fZ49nWFEnj3V8do8hYy9t比较。strcmp(a,b)：如果a,b相等，返回0

我们把密文解密回去就是flag

另外：Linux执行ELF文件，要先chmod +x +文件名

exp:

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

c = b"VlxRV2t0II8kX2WPJ15fZ49nWFEnj3V8do8hYy9t"
m = base64.b64decode(c)

mes = ''
for i in range(len(m)):
    mm = (m[i]-16) ^ 0x20
    mes += chr(mm)
    
print(mes)
#flag{D0_4ou_7now_wha7_ELF_1s?}

咳

Exeinfo Pe查壳

发现加壳了

用upx脱壳

脱壳后再丢入Exeinfo PE:

丢入IDA

我们传入一个字符串作为Str1，经过for循环，最后把Str1和enc比较，enc=gmbh|D1ohsbuv2bu21ot1oQb332ohUifG2stuQ[HBMBYZ2fwf2~

发现for循环中，每次把Str1[i]都自增了一次，所以只要把密文每个字符减去1就是flag

exp:

1
2
3
4
5
6
7
8
9
c = "gmbh|D1ohsbuv2bu21ot1oQb332ohUifG2stuQ[HBMBYZ2fwf2~"
flag = ''

for i in c:
    m = ord(i) - 1
    flag += chr(m)
    
print(flag)
#flag{C0ngratu1at10ns0nPa221ngTheF1rstPZGALAXY1eve1}

Endian

主要看这段验证函数

需要确保v5每次都等于array[i] ^ 0x12345678

由上图知array = [0x75553A1E,0x7B583A03,0x4D58220C,0x7B50383D,0x736B3819,0x0]

把array异或上0x12345678即是明文

exp:

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

a = [0x75553A1E,0x7B583A03,0x4D58220C,0x7B50383D,0x736B3819,0x0]

flag = b""
for i in range(5):
    m = long_to_bytes(a[i] ^ 0x12345678)[::-1]
    flag += m

print(flag + b"}")
#flag{llittl_Endian_a}

因为涉及大小端的知识，所以要逆序一下

值得注意的是v5 += 4指的是从v5[:4]到v5[4:8]，4为一个划分

AndroXor

安卓逆向，用上JEB工具

找到关键函数以及调用该函数的地方

加密过程可以理解为c[i] = s[i] ^ s1[i % len(s1)]

而c就是后面这段数组，从调用出可以知道s1=happyx3

exp:

1
2
3
4
5
6
7
8
9
key = "happyx3"
flag = ""
c = ['\u000E', '\r', '\u0011', '\u0017', '\u0002', 'K', 'I', '7', ' ', '\u001E', '\u0014', 'I', '\n', '\u0002', '\f', '>', '(', '@', '\u000B', '\'', 'K', 'Y', '\u0019', 'A', '\r']
for i in range(len(c)):
    m = ord(key[i % len(key)]) ^ ord(c[i])
    flag += chr(m)
    
print(flag)
#flag{3z_And0r1d_X0r_x1x1}

Web

泄露的秘密

参考在野web手的文章

robots后台泄露

访问url/robots.txt

得到flag{r0bots_1s_s0_us3ful

php源码泄露

访问url/www.zip，连同robots.txt都给了

得到_4nd_www.zip_1s_s0_d4ng3rous}

flag:flag{r0bots_1s_s0_us3ful_4nd_www.zip_1s_s0_d4ng3rous}

Week2

Crypto

滴啤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
import gmpy2
from flag import flag
def gen_prime(number):
    p = getPrime(number//2)
    q = getPrime(number//2)
    return p,q

m = bytes_to_long(flag.encode())
p,q = gen_prime(1024)
print(p*q)
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
print(d%(p-1))
print(pow(m,e,p*q))
# 93172788492926438327710592564562854206438712390394636149385608321800134934361353794206624031396988124455847768883785503795521389178814791213054124361007887496351504099772757164211666778414800698976335767027868761735533195880182982358937211282541379697714874313863354097646233575265223978310932841461535936931
# 307467153394842898333761625034462907680907310539113349710634557900919735848784017007186630645110812431448648273172817619775466967145608769260573615221635
# 52777705692327501332528487168340175436832109866218597778822262268417075157567880409483079452903528883040715097136293765188858187142103081639134055997552543213589467751037524482578093572244313928030341356359989531451789166815462417484822009937089058352982739611755717666799278271494933382716633553199739292089

$\because d_p \equiv d \mod (p-1)$

左右同乘$e$得到

$\therefore d_p \times e \equiv d \times e \mod (p-1)$

则$d \times e = k_1(p-1)+d_p\times e$

又$\because d\times e = k_2(p-1)(q-1) + 1$

化简得$d_p \times e = (p-1)[k_2(q-1)-k_1] + 1$

$\because d_p < p - 1$，$\therefore 0 < k_2(q-1)-k_1 < e$

遍历$i \in (0,e)$的所有值，如果$d_p \times e - 1$能够整除$i$，那我们就可以求得$p-1$

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 long_to_bytes
import gmpy2

n = 93172788492926438327710592564562854206438712390394636149385608321800134934361353794206624031396988124455847768883785503795521389178814791213054124361007887496351504099772757164211666778414800698976335767027868761735533195880182982358937211282541379697714874313863354097646233575265223978310932841461535936931
dp = 307467153394842898333761625034462907680907310539113349710634557900919735848784017007186630645110812431448648273172817619775466967145608769260573615221635
c = 52777705692327501332528487168340175436832109866218597778822262268417075157567880409483079452903528883040715097136293765188858187142103081639134055997552543213589467751037524482578093572244313928030341356359989531451789166815462417484822009937089058352982739611755717666799278271494933382716633553199739292089
e =65537

def dp_leak(dp,c,n,e):
    for i in range(1,e):
        t = (dp * e - 1) % i        
        if t == 0:
            p = (dp * e - 1) // i + 1
            if n % p == 0:
                q = n // p
                d = gmpy2.invert(e,(p-1)*(q-1))
                print(long_to_bytes(pow(c,d,n)))
                
dp_leak(dp,c,n,e)
#flag{cd5ff82d-989c-4fbf-9543-3f98ab567546}

不止一个pi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from flag import flag
from Crypto.Util.number import *
import gmpy2
p = getPrime(1024)
q = getPrime(1024)
n = p**3*q**2
print("q = ",q)
print("p = ",p)
m = bytes_to_long(flag.encode())
c = pow(m,65537,n)
print("c = ",c)

# q =  115478867870347527660680329271012852043845868401928361076102779938370270670897498759391844282137149013845956612257534640259997979275610235395706473965973203544920469416283181677660262509481282536465796731401967694683575843183509430017972506752901270887444490905891490955975762524187534052478173966117471143713
# p =  171790960371317244087615913047696670778115765201883835525456016207966048658582417842936925149582378305610304505530997833147251832289276125084339614808085356814202236463900384335878760177630501950384919794386619363394169016560485152083893183420911295712446925318391793822371390439655160077212739260871923935217
# c =  4459183928324369762397671605317600157512712503694330767938490496225669985050002776253470841193156951087663107866714426230222002399666306287642591077990897883174134404896800482234781531592939043551832049756571987010173667074168282355520711905659013076509353523088583347373358980842707686611157050425584598825151399870268083867269912139634929397957514376826145870752116583185351576051776627208882377413433140577461314504762388617595282085102271510792305560608934353515552201553674287954987323321512852114353266359364282603487098916608302944694600227628787791876600901537888110093703612414836676571562487005330299996908873589228072982641114844761980143047920770114535924959765518365614709272297666231481655857243004072049094078525569460293381479558148506346966064906164209362147313371962567040047084516510135054571080612077333228195608109065475260832580192321853906138811139036658485688320161530131239854003996457871663456850196483520239675981391047452381998620386899101820782421605287708727667663038905378115235163773867508258208867367314108701855709002634592329976912239956212490788262396106230191754680813790425433763427315230330459349320412354189010684525105318610102936715203529222491642807382215023468936755584632849348996666528981269240867612068382243822300418856599418223875522408986596925018975565057696218423036459144392625166761522424721268971676010427096379610266649911939139451989246194525553533699831110568146220347603627745407449761792135898110139743498767543521297525802809254842518002190381508964357001211353997061417710783337

$\because n = p^3\times q^2$，$\therefore \phi(n) = p^2\times (p-1) \times q \times (q-1)$

exp:

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

q =  115478867870347527660680329271012852043845868401928361076102779938370270670897498759391844282137149013845956612257534640259997979275610235395706473965973203544920469416283181677660262509481282536465796731401967694683575843183509430017972506752901270887444490905891490955975762524187534052478173966117471143713
p =  171790960371317244087615913047696670778115765201883835525456016207966048658582417842936925149582378305610304505530997833147251832289276125084339614808085356814202236463900384335878760177630501950384919794386619363394169016560485152083893183420911295712446925318391793822371390439655160077212739260871923935217
c =  4459183928324369762397671605317600157512712503694330767938490496225669985050002776253470841193156951087663107866714426230222002399666306287642591077990897883174134404896800482234781531592939043551832049756571987010173667074168282355520711905659013076509353523088583347373358980842707686611157050425584598825151399870268083867269912139634929397957514376826145870752116583185351576051776627208882377413433140577461314504762388617595282085102271510792305560608934353515552201553674287954987323321512852114353266359364282603487098916608302944694600227628787791876600901537888110093703612414836676571562487005330299996908873589228072982641114844761980143047920770114535924959765518365614709272297666231481655857243004072049094078525569460293381479558148506346966064906164209362147313371962567040047084516510135054571080612077333228195608109065475260832580192321853906138811139036658485688320161530131239854003996457871663456850196483520239675981391047452381998620386899101820782421605287708727667663038905378115235163773867508258208867367314108701855709002634592329976912239956212490788262396106230191754680813790425433763427315230330459349320412354189010684525105318610102936715203529222491642807382215023468936755584632849348996666528981269240867612068382243822300418856599418223875522408986596925018975565057696218423036459144392625166761522424721268971676010427096379610266649911939139451989246194525553533699831110568146220347603627745407449761792135898110139743498767543521297525802809254842518002190381508964357001211353997061417710783337
e = 65537

n = p**3*q**2
phi = p**2*(p-1) * q*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
#flag{bu_zhi_yige_p1dsaf}

halfcandecode

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 *
import gmpy2
from flag import flag
import os
from hashlib import md5

def gen_prime(number):
    p = getPrime(number // 2)
    q = gmpy2.next_prime(p)
    return p * q

def md5_hash(m):
    return md5(m.encode()).hexdigest()
e = 65537
n = gen_prime(1024)
m1 = bytes_to_long(flag[:len(flag) // 2].encode() + os.urandom(8))
c1 = pow(m1, e, n)
m2 = flag[len(flag) // 2:]
with open("out.txt","w") as f:
    f.write(str(n) + '\n')
    f.write(str(c1) + '\n')
    for t in m2:
        f.write(str(md5_hash(t))+'\n')

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
113021375625152132650190712599981988437204747209058903684387817901743950240396649608148052382567758817980625681440722581705541952712770770893410244646286485083142929097056891857721084849003860977390188797648441292666187101736281034814846427200984062294497391471725496839508139522313741138689378936638290593969
43054766235531111372528859352567995977948625157340673795619075138183683929001986100833866227688081563803862977936680822407924897357491201356413493645515962458854570731176193055259779564051991277092941379392700065150286936607784073707448630150405898083000157174927733260198355690620639487049523345380364948649
4a8a08f09d37b73795649038408b5f33
03c7c0ace395d80182db07ae2c30f034
e1671797c52e15f763380b45e841ec32
b14a7b8059d9c055954c92674ce60032
e358efa489f58062f10dd7316b65649e
cfcd208495d565ef66e7dff9f98764da
b14a7b8059d9c055954c92674ce60032
8fa14cdd754f91cc6554c9e71929cce7
0cc175b9c0f1b6a831c399e269772661
4a8a08f09d37b73795649038408b5f33
e358efa489f58062f10dd7316b65649e
cfcd208495d565ef66e7dff9f98764da
4b43b0aee35624cd95b910189b3dc231
cbb184dd8e05c9709e5dcaedaa0495cf

part1

这部分，$p,q$很接近，直接把$n$开根号取下一个素数作为$p$

part2

哈希，爆破就完了

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

n = 113021375625152132650190712599981988437204747209058903684387817901743950240396649608148052382567758817980625681440722581705541952712770770893410244646286485083142929097056891857721084849003860977390188797648441292666187101736281034814846427200984062294497391471725496839508139522313741138689378936638290593969
c = 43054766235531111372528859352567995977948625157340673795619075138183683929001986100833866227688081563803862977936680822407924897357491201356413493645515962458854570731176193055259779564051991277092941379392700065150286936607784073707448630150405898083000157174927733260198355690620639487049523345380364948649
HASH = ["4a8a08f09d37b73795649038408b5f33","03c7c0ace395d80182db07ae2c30f034","e1671797c52e15f763380b45e841ec32","b14a7b8059d9c055954c92674ce60032","e358efa489f58062f10dd7316b65649e","cfcd208495d565ef66e7dff9f98764da","b14a7b8059d9c055954c92674ce60032","8fa14cdd754f91cc6554c9e71929cce7","0cc175b9c0f1b6a831c399e269772661","4a8a08f09d37b73795649038408b5f33","e358efa489f58062f10dd7316b65649e","cfcd208495d565ef66e7dff9f98764da","4b43b0aee35624cd95b910189b3dc231","cbb184dd8e05c9709e5dcaedaa0495cf"]

t = gmpy2.iroot(n,2)[0]
p = gmpy2.next_prime(t)
q = n // p
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
flag1 = long_to_bytes(m)[:-8]

flag2 = ""
for i in trange(len(HASH)):
    for j in range(32,128):
        hash = hashlib.md5(chr(j).encode()).hexdigest()
        if hash == HASH[i]:
            flag2 += chr(j)
flag = flag1+ flag2.encode()
print(flag)
#flag{two_cloabcse_t0_fact0r}

Rotate Xor

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 secret import flag
from os import urandom
from pwn import xor
from Cryptodome.Util.number import *

k1 = getPrime(64)
k2 = getPrime(64)
ROUND = 12
ciphertext = xor(flag, long_to_bytes(k1))

def round_rotate_left(num, step):
    return ((num) << step | num >> (64-step)) & 0xffffffffffffffff

def encrypt_key(key):
    for _ in range(ROUND):
        key = round_rotate_left(key, 3) ^ k2
    return key

print('ciphertext =', ciphertext)
print('enc_k1 =', encrypt_key(k1))
print('k2 =', k2)

# ciphertext = b'\x8dSyy\xd2\xce\xe2\xd2\x98\x0fth\x9a\xc6\x8e\xbc\xde`zl\xc0\x85\xe0\xe4\xdfQlc'
# enc_k1 = 7318833940520128665
# k2 = 9982833494309156947

根据round_rotate_left(num,step)的特点

假设此函数加密后的结果为c，那么c的低num位就是m的高num位，c的高64-num位就是m的低64-num位，拼接即可

exp:

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

def decrypt(key,ROUND):
    for _ in range(ROUND):
        key= k2 ^ key
        bin_k = bin(key)[2:].zfill(64)
        k_h = bin_k[-3:]
        k_l = bin_k[:-3]
        key = int(k_h + k_l,2)
    return key


ciphertext = b'\x8dSyy\xd2\xce\xe2\xd2\x98\x0fth\x9a\xc6\x8e\xbc\xde`zl\xc0\x85\xe0\xe4\xdfQlc'
enc_k1 = 7318833940520128665
k2 = 9982833494309156947
ROUND = 12
k1 = decrypt(enc_k1,ROUND)
print(k1)
flag = xor(ciphertext,long_to_bytes(k1))
print(flag)
#flag{z3_s0lv3r_15_bri11i4nt}

partial decrypt

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

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(512)

n = p*q 

c = pow(m,e,n)

dp = inverse(e, (p-1))
dq = inverse(e, (q-1))
m1 = pow(c,dp, p)
m2 = pow(c,dq, q)
q_inv = inverse(q, p)
h = (q_inv*(m1-m2)) % p
print('m2 =', m2)
print('h =', h)
print('q =', q)

# m2 = 4816725107096625408335954912986735584642230604517017890897348901815741632668751378729851753037917164989698483856004115922538576470127778342121497852554884
# h = 4180720137090447835816240697100630525624574275
# q = 7325294399829061614283539157853382831627804571792179477843187097003503398904074108324900986946175657737035770512213530293277111992799331251231223710406931

考点：dp,dq泄露

原理见👉RSA(一) | DexterJie’Blog

最后得到

$m_p \equiv c^{d_p} \mod p$

$m_q \equiv c^{d_q} \mod q$

$m = ((m_q - m_p)\times p^{-1})\times p + m_p \mod n$，其中$p^{-1}$是$p$模$q$的逆元

exp:

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
m2 = 4816725107096625408335954912986735584642230604517017890897348901815741632668751378729851753037917164989698483856004115922538576470127778342121497852554884
h = 4180720137090447835816240697100630525624574275
q = 7325294399829061614283539157853382831627804571792179477843187097003503398904074108324900986946175657737035770512213530293277111992799331251231223710406931

m = h * q + m2
print(long_to_bytes(m))
#flag{rsa_with_crt#b12a3a020c9cc5f1a6df4618256f7c88c83fdd95aab1a2b2656d760475bd0bf1}

broadcast

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from secret import flag
from Cryptodome.Util.number import *

menu = '''
Welcome to RSA Broadcasting system

please select your option:

1. brocast the flag
2. exit
'''
e = 17
def broadcast_the_flag():
    p = getPrime(256)
    q = getPrime(256)
    n=p*q
    m = bytes_to_long(flag)
    c = pow(m,e,n)
    print('n =', n)
    print('c =', c)
    print('e =', e)
while True:
    print(menu)
    opt = input('> ')
    try:
        opt = int(opt)
        if opt == 1:
            broadcast_the_flag()
        elif opt == 2:
            break
        else:
            print('invalid option')
    except:
        print('oh no, something wrong!')

考点：中国剩余定理

一般$e=3$的时候，3组n,c就能解决，但是这题$e=17$，需要17组n,c才能解

所以写个脚本进行nc

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
from pwn import *
from tqdm import *
from sympy.ntheory.modular import *
from Crypto.Util.number import *
import gmpy2

host = 'node4.buuoj.cn'                  #ip地址
port =  28352                              #端口

sh = remote(host,port)                  #建立连接  
N = []
C = []

for i in trange(17):
    data = sh.recvuntil(b">")
    # print(data.decode())
    sh.sendline(b"1")
    n = sh.recvline().decode().split('=')[-1]
    N.append(eval(n))
    c = sh.recvline().decode().split('=')[-1]
    C.append(eval(c))
    if len(N) >= 17:
        M = crt(N,C)
        for j in M:
            m = gmpy2.iroot(int(j),17)[0]
            flag = long_to_bytes(m)
            if b"flag" in flag:
                print(flag)
                break
        break

#flag{d0_n0t_sh0ut_loud1y_1n_th3_d4rk_f0r3st}

Week3

Crypto

Rabin’s RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import flag
p = getPrime(64)
q = getPrime(64)
assert p % 4 == 3
assert q % 4 == 3

n = p * q

e = 2
m = bytes_to_long(flag)

c = pow(m,e,n)

print('n =', n)
print('c =', c)

# n = 201354090531918389422241515534761536573
# c = 20442989381348880630046435751193745753

n能分解，对Rabin不是很熟悉，套了一下Rabin脚本

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

p= 13934102561950901579
q= 14450452739004884887
n= p*q
c= 20442989381348880630046435751193745753
e= 2

mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)

a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)
# 因为rabin 加密有四种结果，全部列出。
aa = [a, b, c, d]
for i in aa:
    print(long_to_bytes(int(i)))
    # flag{r4b1n#4c58}

小明的密码题

高位泄露的考点

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 secret import *
flag_part = flag_content + '#' + secret_token
p = getPrime(512)
q = getPrime(512)

m = bytes_to_long(flag_part.encode())

e = 5
n = p*q

c = pow(m,e,n)

print('n =', n)
print('c =', c)
print('flag_part =', flag_part)
print()
print('--- hint begin ---')
print('flag = "flag{" + flag_part + "}"')
print('type of secret_token is', type(secret_token))
print('length of secret_token is', len(secret_token))

# n = 131889193322687215946601811511407251196213571687093913054335139712633125177496800529685285401802802683116451016274353008428347997732857844896393358010946452397522017632024075459908859131965234835870443110233375074265933004741459359128684375786221535003839961829770182916778717973782408036072622166388614214899
# c = 11188201757361363141578235564807411583085091933389381887827791551369738717117549969067660372214366275040055647621817803877495473068767571465521881010707873686036336475554105314475193676388608812872218943728455841652208711802376453034141883236142677345880594246879967378770573385522326039206400578260353074379
# flag_part = sm4ll_r00ts_is_brilliant#◼️◼️◼️◼️◼️◼️◼️◼️
# 
# --- hint begin ---
# flag = "flag{" + flag_part + "}"
# type of secret_token is <class 'str'>
# length of secret_token is 8

只有密文后8位不知道，把已知明文转为整形，然后左移64位，用copper

exp:

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

flag = b"sm4ll_r00ts_is_brilliant#"
m1 = bytes_to_long(flag)
m1 = m1 << 64
R.<x> = PolynomialRing(Zmod(n))
f = (m1 + x)^e - c
f = f.monic()
root = f.small_roots(X = 2^64)
print(root)
m = m1 + root[0]
flag = b"flag{" + long_to_bytes(int(m)) + b"}"
print(flag)
#flag{sm4ll_r00ts_is_brilliant#cc0dac72}

babyrandom

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
#!/usr/bin/python3
from secret import flag
from Crypto.Util.number import *
from random import randrange

p = 64999433139797068147576269731948390094958654326970231465808792590598519729077

a = randrange(2, p)
b = randrange(2, p)
x = bytes_to_long(flag)
menu = '''

Random as a Service with LCG backend

Enter your option
1. Reset
2. Get
3. Exit
'''

def GetRandom():
    global x
    nx = (a*x + b) % p
    print(nx)
    x = nx
    
while True:
    print(menu)
    opt = input('> ')
    try:
        opt = int(opt)
        if opt == 1:
            x = bytes_to_long(flag)
        elif opt == 2:
            GetRandom()
        elif opt == 3:
            break
        else:
            print('invalid option')
    except Exception as e:
        print('oh no, something wrong!')
        print(e)

从靶机获取几组数据然后求解lcg即可

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

output =  []

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 = a_ * (output[0]-b) % i
        flag = long_to_bytes(seed)
        if b'flag' in flag:
            print(flag)
            break
            #flag{lcg_1s_n0t_s3cur3#fb528ba5}

knapsack

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

m = [int(i) for i in bin(int(codecs.encode(flag,  'hex'), 16))[2:]]

# from ASIS Cyber Security Contest Quals 2014
def makeKey(n):
    privKey = [random.randint(1, 4**n)]
    s = privKey[0]
    for i in range(1, n):
        privKey.append(random.randint(s + 1, 4**(n + i)))
        s += privKey[i]
    q = random.randint(privKey[n-1] + 1, 2*privKey[n-1])
    r = random.randint(1, q)
    while gmpy2.gcd(r, q) != 1:
        r = random.randint(1, q)
    pubKey = [ r*w % q for w in privKey ]
    return privKey, q, r, pubKey

priv, q, r, pub = makeKey(len(m))

ciphertext = sum([i*j for i, j in zip(pub, m)])

print(ciphertext)
print(pub)

# ciphertext
# pub

背包密码，构造格

S是密文，M是公钥

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

M = #公钥
S = #密文

n = len(M)
Ge = Matrix.identity(n)
last_row = [0 for x in range(n)]
Ge_last_row = Matrix(ZZ, 1, len(last_row), last_row)

last_col = M[:]
last_col.append(S)
Ge_last_col = Matrix(ZZ, len(last_col), 1, last_col)

Ge = Ge.stack(Ge_last_row)
Ge = Ge.augment(Ge_last_col)

X = Ge.LLL()[-1]
X = X[:-1]

m = ""
for i in X:
    if abs(i) == 1:
        m += "1"
    if abs(i) == 0:
        m += "0"
        
print(m)
flag = bytes.fromhex(hex(int(m,2))[2:])
print(flag)
#flag{Lattice_reduction#c3662541}

easy_crt———留空

Door———留空

Week4

Crypto

RSA Variation II

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

p = getPrime(1024)
q = getPrime(1024)

N = p*p*q

d= inverse(N, (p-1)*(q-1)//GCD(p-1, q-1))

m = bytes_to_long(flag)

c = pow(m, N, N)

print('c =', c)
print('N =', N)
print('d =', d)

# c = 1653396627113549535760516503668455111392369905404419847336187180051939350514408518095369852411718553340156505246372037811032919080426885042549723125598742783778413642221563616358386699697645814225855089454045984443096447166740882693228043505960011332616740785976743150624114653594631779427044055729185392854961786323215146318588164139423925400772680226861699990332420246447180631417523181196631188540323779487858453719444807515638025771586275969579201806909799448813112034867089866513864971414742370516244653259347267231436131850871346106316007958256749016599758599549180907260093080500469394473142003147643172770078092713912200110043214435078277125844112816260967490086038358669788006182833272351526796228536135638071670829206746835346784997437044707950580087067666459222916040902038574157577881880027391425763503693184264104932693985833980182986816664377018507487697769866530103927375926578569947076633923873193100147751463
# N = 1768427447158131856514034889456397424027937796617829756303525705316152314769129050888899742667986532346611229157207778487065194513722005516611969754197481310330149721054855689646133721600838194741123290410384315980339516947257172981002480414254023253269098539962527834174781356657779988761754582343096332391763560921491414520707112852896782970123018263505426447126195645371941116395659369152654368118569516482251442513192892626222576419747048343942947570016045016127917578272819812760632788343321742583353340158009324794626006731057267603803701663256706597904789047060978427573361035171008822467120148227698893238773305320215769410594974360573727150122036666987718934166622785421464647946084162895084248352643721808444370307254417501852264572985908550839933862563001186477021313236113690793843893640190378131373214104044465633483953616402680853776480712599669132572907096151664916118185486737463253559093537311036517461749439
# d = 20650646933118544225095544552373007455928574480175801658168105227037950105642248948645762488881219576174131624593293487325329703919313156659700002234392400636474610143032745113473842675857323774566945229148664969659797779146488402588937762391470971617163496433008501858907585683428652637958844902909796849080799141999490231877378863244093900363251415972834146031490928923962271054053278056347181254936750536280638321211545167520935870220829786490686826062142415755063724639110568511969041175019898031990455911525941036727091961083201123910761290998968240338217895275414072475701909497518616112236380389851984377079

考察了Schmidt-Samoa密码系统，[GUET-CTF2019]Uncle Sam（考点：Schmidt-Samoa密码系统）-CSDN博客

密钥生成：①公钥：$N = p^2q$，②私钥：$d = invert(N,(p-1)(q-1))$

加密：$C = m^N \mod N$

解密：$m = C^d \mod pq$

攻击：

$\because Nd \equiv 1 \mod (p-1)(q-1)$

任意选取一个$a$，有$ a^{Nd} = a^{k(p-1)(q-1) + 1} = a \times a^{k(p-1)(q-1)} \equiv a \mod pq$

$\therefore k\times pq = a^{Nd} - a$

与N求公因数得到$pq$，即可求得明文

更多参考：其他加密算法 | Lazzaro (lazzzaro.github.io)

exp:

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

N =  
#N = p^2*q
d = 
c = 
tmp = pow(2,d*N,N) - 2
pq = gmpy2.gcd(mpz(tmp),N)

m = pow(c,d,pq)
print(bytes.fromhex(hex(m)[2:]))
# flag{l3arn_s0m3_e1ement4ry_numb3r_the0ry}

babyNTRU

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

q = getPrime(2048)

f = getPrime(1024)
g = getPrime(768)

h = (inverse(f, q) * g) % q

m = bytes_to_long(flag)

e = (getPrime(32) * h + m) % q

print((h, q))
print(e)

# (8916452722821418463248726825721257021744194286874706915832444631771596616116491775091473142798867278598586482678387668986764461265131119164500473719939894343163496325556340181429675937641495981353857724627081847304246987074303722642172988864138967404024201246050387152854001746763104417773214408906879366958729744259612777257542351501592019483745621824894790096639205771421560295175633152877667720038396154571697861326821483170835238092879747297506606983322890706220824261581533324824858599082611886026668788577757970984892292609271082176311433507931993672945925883985629311514143607457603297458439759594085898425992, 31985842636498685945330905726539498901443694955736332073639744466389039373143618920511122288844282849407290205804991634167816417468703459229138891348115191921395278336695684210437130681337971686008048054340499654721317721241239990701099685207253476642931586563363638141636011941268962999641130263828151538489139254625099330199557503153680089387538863574480134898211311252227463870838947777479309928195791241005127445821671684607237706849308372923372795573732000365072815112119533702614620325238183899266147682193892866330678076925199674554569018103164228278742151778832319406135513140669049734660019551179692615505961)
# 20041713613876382007969284056698149007154248857420752520496829246324512197188211029665990713599667984019715503486507126224558092176392282486689347953069815123212779090783909545244160318938357529307482025697769394114967028564546355310883670462197528011181768588878447856875173263800885048676190978206851268887445527785387532167370943745180538168965461612097037041570912365648125449804109299630958840398397721916860876687808474004391843869813396858468730877627733234832744328768443830669469345926766882446378765847334421595034470639171397587395341977453536859946410431252287203312913117023084978959318406160721042580688

$\because h \equiv f^{-1}\times g \mod q$

$\therefore g = hf +kq$

又$\because e \equiv xh +m \mod q$

$\therefore e = xh + m +kq$

$\therefore m = e-xh -kq$

构造格

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(h,q) = (, )
e = 

Ge = Matrix(ZZ,[
    [q,0,0,0,0],
    [0,q,0,0,0],
    [h,0,1,0,0],
    [0,h,0,2^1000,0],
    [0,e,0,0,2^1024]
])
for line in Ge.LLL():
    if abs(line[-1]) == 2^1024:
        m = abs(line[1])
        print(bytes.fromhex(hex(m)[2:]))
        # flag{Lattice_reduction_magic_on_NTRU#82b08b2d}

Smart

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 sage.all import *
from secret import flag

p = 75206427479775622966537995406541077245842499523456803092204668034148875719001
a = 40399280641537685263236367744605671534251002649301968428998107181223348036480
b = 34830673418515139976377184302022321848201537906033092355749226925568830384464

E = EllipticCurve(GF(p), [a, b])

d = bytes_to_long(flag)

G = E.random_element()

P = d * G

print(G)
print(P)

# (63199291976729017585116731422181573663076311513240158412108878460234764025898 : 11977959928854309700611217102917186587242105343137383979364679606977824228558 : 1)
# (75017275378438543246214954287362349176908042127439117734318700769768512624429 : 39521483276009738115474714281626894361123804837783117725653243818498259351984 : 1)

SmartAttack

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
p = 
a = 
b = 
E = EllipticCurve(GF(p), [a, b])
G = (,)
P = (,)

G = E(G)
P = E(P)
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)

d = SmartAttack(G,P,p)
print(bytes.fromhex(hex(d)[2:]))
# flag{m1nd_y0ur_p4rameter#167d}

signin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import isPrime,bytes_to_long, sieve_base
from random import choice
from secret import flag

m=bytes_to_long(flag)
def uniPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(sieve_base)
        if isPrime(n + 1):
            return n + 1


p=uniPrime(512)
q=uniPrime(512)
n=p*q
e= 196608
c=pow(m,e,n)

print("n=",n)
print("c=",c)

'''
n= 3326716005321175474866311915397401254111950808705576293932345690533263108414883877530294339294274914837424580618375346509555627578734883357652996005817766370804842161603027636393776079113035745495508839749006773483720698066943577445977551268093247748313691392265332970992500440422951173889419377779135952537088733
c= 2709336316075650177079376244796188132561250459751152184677022745551914544884517324887652368450635995644019212878543745475885906864265559139379903049221765159852922264140740839538366147411533242116915892792672736321879694956051586399594206293685750573633107354109784921229088063124404073840557026747056910514218246
'''

$p-1$光滑分解$n$

$e = 196608 = 2^{16} \times 3$

解16次rabin，再开3次根号

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

def smooth(N):
    a = 2
    n = 2
    while True:
        a = pow(a, n, N)
        res = gmpy2.gcd(a - 1, N)
        if res != 1 and res != N:
            return res
        n += 1
        
n= 
c= 
e = 196608

p = smooth(n)
# print(p)
# p = 11104262127139631006017377403513327506789883414594983803879501935187577746510780983414313264114974863256190649020310407750155332724309172387489473534782137699
q = n//p

x0=gmpy2.invert(p,q)
x1=gmpy2.invert(q,p)
cs = [c]
for i in range(16):
    ps = []
    for c2 in cs:
        r = pow(c2, (p + 1) // 4, p)
        s = pow(c2, (q + 1) // 4, q)

        x = (r * x1 * q + s * x0 * p) % n
        y = (r * x1 * q - s * x0 * p) % n
        if x not in ps:
            ps.append(x)
        if n - x not in ps:
            ps.append(n - x)
        if y not in ps:
            ps.append(y)
        if n - y not in ps:
            ps.append(n - y)
    cs = ps

for m in ps:
    mm = gmpy2.iroot(m,3)
    if mm[1]:
        flag = long_to_bytes(mm[0])
        print(flag)
        # flag{new1sstar_welcome_you}

error

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 sage.all import *
from secret import flag
import random
data = [ord(x) for x in flag]

mod = 0x42
n = 200
p = 5
q = 2**20

def E():
  return vector(ZZ, [1 - random.randint(0,p) for _ in range(n)])

def creatematrix():
  return matrix(ZZ, [[q//2 - random.randint(0,q) for _ in range(n)] for _ in range(mod)])

A, B, C= creatematrix(), creatematrix(), creatematrix()
x = vector(ZZ, data[0:mod])
y = vector(ZZ, data[mod:2*mod])
z = vector(ZZ, data[2*mod:3*mod])
e = E()
b = x*B+y*A+z*C + e
res = ""
res += "A=" + str(A) +'\n'
res += "B=" + str(B) +'\n'
res += "C=" + str(C) +'\n'
res += "b=" + str(b) +'\n'

with open("enc.out","w") as f:
  f.write(res)

格基规约 + 矩阵求解

$b = x_{1\times 66}A_{66\times 200} + y_{1\times 66}B_{66\times 200} + z_{1\times 66}C_{66\times 200} + e_{1\times 200}$

即求解矩阵方程：

但是我们缺少$e_{1\times 200}$

因为e是一个很小的向量，所以可以用LLL算法规约出e

$\because e = xA +yB +zC - b$，即构造格：

得到e之后解矩阵方程即可

这题还有一个比较烦人的点就是数据太大，建议用记事本进行替换

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
A =
B = 
C =
b =


A = Matrix(ZZ,A)
B = Matrix(ZZ,B)
C = Matrix(ZZ,C)
b = vector(b)
Ge = A.stack(B).stack(C).stack(b)
e = [int(i) for i in Ge.LLL()[0]]
print(e)
# [-4, -1, 1, 0, -1, 1, -1, -4, -1, -4, -4, -1, -1, 1, 1, -3, -2, 0, -3, -3, -4, -3, -3, -2, -1, -1, 1, 1, 0, -2, -2, -1, -3, -4, -1, -1, -2, -1, 1, -3, -4, 0, 0, 1, 0, -1, -4, -2, -3, -3, 1, 0, -1, -4, -4, -3, 0, 1, 0, -1, -1, -4, -2, -1, -4, 1, -2, 1, -2, 1, -4, 1, -2, -4, 0, 0, -1, 0, -3, -3, -1, -2, 0, -4, 1, -2, 1, 0, -3, -4, -4, -3, 0, -4, 1, 1, -4, -1, -4, -4, -4, 0, -3, -3, 0, -2, -3, -3, -4, 0, 0, -1, -1, -1, 0, 0, -4, 1, 0, -3, -2, 1, 1, 1, -2, 0, 0, -1, -2, -3, 1, -1, 1, -4, -1, 0, -2, 0, -2, -1, -2, 1, -4, 0, -1, 1, -1, 0, -1, -3, -1, -3, -3, 0, 0, 0, -2, -1, 0, 1, -3, -4, -3, -4, 1, -1, -1, -3, 1, -3, 0, -1, -3, -1, -4, -1, -2, -4, -4, -1, -3, -2, 0, 0, 1, -3, -2, -1, -1, -4, -1, 0, 1, -2, -4, -2, -1, 0, -1, -1]
e = vector(ZZ,e)

Y = A.stack(B).stack(C).stack(e)
X = Y.solve_left(b)
print(X)

flag = ""
for i in X[:-1]:
    flag += chr(i)
    
print(flag)
# congratulations, here is your flag:flag{try_lear1n_wi0h_t1e_error}congratulations, here is your flag:flag{try_lear1n_wi0h_t1e_error}congratulations, here is your flag:flag{try_lear1n_wi0h_t1e_error}

Week5

Crypto

School of CRC32

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

ROUND = 100

LENGTH = 20

print('Extreme hard CRC32 challenge')
print('ARE YOU READY')

for i in range(ROUND):
    print('ROUND', i, '!'*int(i/75 + 1))

    target = secrets.randbits(32)

    print('Here is my CRC32 value: ', hex(target))

    dat = input('Show me some data > ')
    raw = bytes.fromhex(dat)
    
    if zlib.crc32(raw) == target and len(raw) == LENGTH:
        print("GREAT")
    else:
        print("OH NO")
        exit()

print("Congratulation! Here is your flag")
print(flag)

考到了crc32的逆向（碰撞），网上找了脚本https://pypi.org/project/crcsolver/，根据例子改改即可

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import crcsolver
import zlib
from pwn import *

sh = remote("node4.buuoj.cn",28855)
for i in range(100):
    data = sh.recvuntil(b"Here is my CRC32 value:")
    c = eval(sh.recvline().decode())
    m = crcsolver.solve(b'_'*20, range(8*20), c, zlib.crc32)
    message = hex(bytes_to_long(m))[2:].zfill(40)
    sh.sendlineafter(b"Show me some data >",message)
sh.interactive()

需要注意的是，传给服务器的数据需要是16进制形式，而且，得填充满40位，否则报错

关键代码m = crcsolver.solve(b'_'*20, range(8*20), c, zlib.crc32)

last_signin

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

e = 65537
p, q = getPrime(1024), getPrime(1024)
N = p * q
gift = p&(2**923-2**101)
m = bytes_to_long(flag)
c = pow(m, e, N)

print("N = ",N)
print("gift = ",gift)
print("c = ",c)

"""
N =  12055968471523053394851394038007091122809367392467691213651520944038861796011063965460456285088011754895260428814358599592032865236006733879843493164411907032292051539754520574395252298997379020268868972160297893871261713263196092380416876697472160104980015554834798949155917292189278888914003846758687215559958506116359394743135211950575060201887025032694825084104792059271584351889134811543088404952977137809673880602946974798597506721906751835019855063462460686036567578835477249909061675845157443679947730585880392110482301750827802213877643649659069945187353987713717145709188790427572582689339643628659515017749
p0 =  70561167908564543355630347620333350122607189772353278860674786406663564556557177660954135010748189302104288155939269204559421198595262277064601483770331017282701354382190472661583444774920297367889959312517009682740631673940840597651219956142053575328811350770919852725338374144
c =  2475592349689790551418951263467994503430959303317734266333382586608208775837696436139830443942890900333873206031844146782184712381952753718848109663188245101226538043101790881285270927795075893680615586053680077455901334861085349972222680322067952811365366282026756737185263105621695146050695385626656638309577087933457566501579308954739543321367741463532413790712419879733217017821099916866490928476372772542254929459218259301608413811969763001504245717637231198848196348656878611788843380115493744125520080930068318479606464623896240289381601711908759450672519228864487153103141218567551083147171385920693325876018
"""

第一眼用了二元copper，没跑出

然后用了网上的脚本D^3CTF 官方Write Up-安全客 - 安全资讯平台 (anquanke.com)

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

N =  
p0 =  
c =  

def bivariate(pol, XX, YY, kk=4):
    N = pol.parent().characteristic()

    f = pol.change_ring(ZZ)
    PR, (x, y) = f.parent().objgens()

    idx = [(k - i, i) for k in range(kk + 1) for i in range(k + 1)]
    monomials = list(map(lambda t: PR(x ** t[0] * y ** t[1]), idx))
    # collect the shift-polynomials
    g = []
    for h, i in idx:
        if h == 0:
            g.append(y ** h * x ** i * N)
        else:
            g.append(y ** (h - 1) * x ** i * f)

    # construct lattice basis
    M = Matrix(ZZ, len(g))
    for row in range(M.nrows()):
        for col in range(M.ncols()):
            h, i = idx[col]
            M[row, col] = g[row][h, i] * XX ** h * YY ** i

    # LLL
    B = M.LLL()

    PX = PolynomialRing(ZZ, 'xs')
    xs = PX.gen()
    PY = PolynomialRing(ZZ, 'ys')
    ys = PY.gen()

    # Transform LLL-reduced vectors to polynomials
    H = [(i, PR(0)) for i in range(B.nrows())]
    H = dict(H)
    for i in range(B.nrows()):
        for j in range(B.ncols()):
            H[i] += PR((monomials[j] * B[i, j]) / monomials[j](XX, YY))

    # Find the root
    poly1 = H[0].resultant(H[1], y).subs(x=xs)
    poly2 = H[0].resultant(H[2], y).subs(x=xs)
    poly = gcd(poly1, poly2)
    x_root = poly.roots()[0][0]

    poly1 = H[0].resultant(H[1], x).subs(y=ys)
    poly2 = H[0].resultant(H[2], x).subs(y=ys)
    poly = gcd(poly1, poly2)
    y_root = poly.roots()[0][0]

    return x_root, y_root

PR = PolynomialRing(Zmod(N), names='x,y')
x, y = PR.gens()
pol = 2 ** 923 * x + y + p0

x, y = bivariate(pol, 2 ** 101, 2 ** 101)
p = 2 ** 923 * x + y + p0
q = N // p
e=65537
d = inverse(e, (p - 1)*(q - 1))
m = int(pow(c, d, N))
print(long_to_bytes(m))

PseudoHell_EASY & PseudoHell_Hard

这两道题的解题关键在于分清每一关的function1和function2的区别

challenges:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import os
def xor(a:bytes,b:bytes):
    assert len(a) == len(b)
    return bytes([i ^ j for i,j in zip(a,b)])

class PRP():
    def __init__(self, n):
        self.domain_cache = {}
        self.range_cache = {}
        self.n = n

    def tran(self, m, inverse = False):
        if not inverse:
            x = m
            if x in self.domain_cache:
                return self.domain_cache[x]
            while True:
                y = os.urandom(self.n)
                if y in self.range_cache:continue
                self.domain_cache[x] = y
                self.range_cache[y] = x    
                return y
        else:
            y = m
            if y in self.range_cache:
                return self.range_cache[y]
            while True:
                x = os.urandom(self.n)
                if x in self.domain_cache:continue
                self.domain_cache[x] = y
                self.range_cache[y] = x    
                return x

class PRF():
    def __init__(self, n):
        self.domain_cache = {}
        self.range_cache = {}
        self.n = n 

    def tran(self, x):
        if x not in self.domain_cache:
            self.domain_cache[x] = os.urandom(self.n)
        return self.domain_cache[x]

class Challenge1:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 8
        self.input_size = 2 * self.block_size
        self.RO1 = PRF(self.block_size)
        self.RO2 = PRF(self.input_size)

    def function1(self, M):
        L, R = M[:self.block_size], M[self.block_size:]
        L, R = R, xor(L, self.RO1.tran(R))
        return L+R

    def function2(self, M):
        return self.RO2.tran(M)

    def roll(self, M, inverse):
        assert inverse == False, "In Challenge1, inverse is not allowed"
        return [self.function1,self.function2][self.coin](M)

class Challenge2:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 8
        self.input_size = 2 * self.block_size
        self.RO1 = PRF(self.block_size)
        self.RO2 = PRF(self.input_size)

    def function1(self, M):
        L, R = M[:self.block_size], M[self.block_size:]
        L, R = R, xor(L, self.RO1.tran(R))
        L, R = R, xor(L, self.RO1.tran(R))
        return L+R

    def function2(self, M):
        return self.RO2.tran(M)

    def roll(self, M, inverse):
        assert inverse == False, "In Challenge2, inverse is not allowed"
        return [self.function1,self.function2][self.coin](M)

class Challenge3:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 8
        self.input_size = 2 * self.block_size
        self.RO1 = PRF(self.block_size)
        self.RO2 = PRF(self.input_size)

    def function1(self, M, inverse):
        if not inverse:
            L, R = M[:self.block_size], M[self.block_size:]
            L, R = R, xor(L, self.RO1.tran(R))
            L, R = R, xor(L, self.RO1.tran(R))
            L, R = R, xor(L, self.RO1.tran(R))
        else:
            L, R = M[:self.block_size], M[self.block_size:]
            L, R = xor(R, self.RO1.tran(L)), L
            L, R = xor(R, self.RO1.tran(L)), L
            L, R = xor(R, self.RO1.tran(L)), L
        return L+R

    def function2(self, M, inverse):
        if inverse or not inverse:        
            return self.RO2.tran(M)

    def roll(self, M, inverse):
        return [self.function1,self.function2][self.coin](M,inverse)

class Challenge4:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 8
        self.input_size = 2 * self.block_size
        self.PRP1 = PRP(self.block_size)
        self.PRP2 = PRP(self.input_size)

    def function1(self, M, inverse):
        X, T = M[:self.block_size], M[self.block_size:]
        X = xor(X, T)
        for _ in range(2):
            X = xor(self.PRP1.tran(X, inverse),T)
        return X

    def function2(self, M, inverse):
        return self.PRP2.tran(M, inverse)[:self.block_size]

    def roll(self, M, inverse):
        return [self.function1,self.function2][self.coin](M,inverse)

class Challenge5:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 1
        self.input_size = self.block_size
        self.PRP = PRP(self.block_size)
        self.PRF = PRF(self.input_size)

    def function1(self, M):
        return xor(bytes(1),self.PRP.tran(M))

    def function2(self, M):
        return xor(self.PRF.tran(M),bytes(1))

    def roll(self, M, inverse):
        assert inverse == False, "In Challenge 5, inverse is not allowed"
        return [self.function1,self.function2][self.coin](M)

problems:

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 challenge import Challenge1,Challenge2,Challenge3,Challenge4,Challenge5
from secret import flag_easy,flag_hard
roll_left = 56

def guess_coin(level, query_num):
    Ch = level()
    for _ in range(query_num):
        msg = bytes.fromhex(input("msg? > "))
        inverse = input("inverse? > ") == 'y'
        assert len(msg) == Ch.input_size
        print(Ch.roll(msg, inverse).hex())
    assert input("coin? > ") == str(Ch.coin) 

def roll_challenge(challenge_level, challenge):
    global roll_left
    print(f"[+] Challenge Level: {challenge_level}")
    roll_num = int(input(f"How many times are required to roll for solving {challenge_level}? > "))
    roll_left -= roll_num
    [guess_coin(challenge, roll_num) for _ in range(33)]

roll_challenge("1", Challenge1)
roll_challenge("2", Challenge2)
roll_challenge("3", Challenge3)

if roll_left <= 0:
    print("You passed all challenges for EASY but times limit exceeded. Try harder :(")
    exit(-1)

print("flag for easy is ", flag_easy)

roll_challenge("4", Challenge4)
roll_challenge("5", Challenge5)

if roll_left <= 0:
    print("You passed all challenges for HARD but times limit exceeded. Try harder :(")
    exit(-1)

print("flag for hard is ", flag_hard)

在此之前，先进行一些声明，希望可以帮助大家理解

我们把题目中self.domain_cache = {}称为定义域

self.range_cache = {}称为值域

tran(m,inverse)函数的意思就是，当inverse = False的时候，先判断m是否在定义域中，如果在定义域中，那么直接返回f(m)，如果不在的话，随机生成一个y与m对应，并且二者形成双射关系

当inverse = True时，判断m是否在值域中，如果在值域中，就返回$f^{-1}(m)$，如果不在，随机生成一个x，并且二者形成双射关系

Challenge1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Challenge1:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 8
        self.input_size = 2 * self.block_size
        self.RO1 = PRF(self.block_size)
        self.RO2 = PRF(self.input_size)

    def function1(self, M):
        L, R = M[:self.block_size], M[self.block_size:]
        L, R = R, xor(L, self.RO1.tran(R))
        return L+R

    def function2(self, M):
        return self.RO2.tran(M)

    def roll(self, M, inverse):
        assert inverse == False, "In Challenge1, inverse is not allowed"
        return [self.function1,self.function2][self.coin](M)

分析function1，设我们输入的数据为$M$，记$L_0,R_0$分别代表左半部分和右半部分，记RO1.tran(R)为$f(R)$

可以看到，$L_0$和$R_0$经过function1的作用后，返回的是$R_0,L_0\otimes f(R_0)$

而function2就是返回$f(M)$

因此，我们可以传入aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa，

如果执行了function1，那么服务器返回的数据的前半部分是aaaaaaaaaaaaaaaa

如果执行了function2，那么服务器返回的数据是随机的一段数据

exp:

1
2
3
4
5
6
7
8
9
10
11
12
def solve1():
    sh.sendlineafter(b"ow many times are required to roll for solving 1?",str(1).encode())
    msg = "a"*32
    for _ in trange(33):
        sh.sendlineafter(b"msg? >",msg.encode())
        sh.sendlineafter(b"inverse? >",str(0).encode())
        data = sh.recvline().decode().strip()
        if data[:16] == "a"*16:
            m = "0"
        else:
            m = "1"
        sh.sendlineafter(b"coin? >",m.encode())

Challenge2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Challenge2:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 8
        self.input_size = 2 * self.block_size
        self.RO1 = PRF(self.block_size)
        self.RO2 = PRF(self.input_size)

    def function1(self, M):
        L, R = M[:self.block_size], M[self.block_size:]
        L, R = R, xor(L, self.RO1.tran(R))
        L, R = R, xor(L, self.RO1.tran(R))
        return L+R

    def function2(self, M):
        return self.RO2.tran(M)

    def roll(self, M, inverse):
        assert inverse == False, "In Challenge2, inverse is not allowed"
        return [self.function1,self.function2][self.coin](M)

和上一关的区别在于，function1多了一步轮换加密

还是设我们输入的数据为$M$，记$L_0,R_0$分别代表左半部分和右半部分，记RO1.tran(R)为$f(R)$

经过推导可以知道

第一次加密得到的是$R_0$，$L_0\otimes f(R_0)$

第二次加密得到的是$L_0 \otimes f(R_0)$，$R_0\otimes f(L_0\otimes f(R_0))$

最后我们得到的数据的左右部分分别是：$L_0 \otimes f(R_0)$，$R_0\otimes f(L_0\otimes f(R_0))$

这关需要两次来完成

在这两次中，我们需要控制$R_0$相等，即两次$M$的右半部分一样，修改左半部分

于是我们可以将服务器两次返回的数据的左半部分进行异或

即$(L_0 \otimes f(R_0))\otimes (L_1\otimes f(R_0)) = L_0 \otimes L_1$

将两次回的数据的左半部分异或后的结果和$L_0\otimes L_1$比较，如果相等，说明执行了function1

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solve2():
    sh.sendlineafter(b"ow many times are required to roll for solving 2?",str(2).encode())
    msg1 = b"61" * 16
    msg2 = b"62" * 8 + b"61" *8
    for _ in trange(33):
        sh.sendlineafter(b"msg? >",msg1)
        sh.sendlineafter(b"inverse? >",str(0).encode())
        data1 = sh.recvline().decode().strip()
        sh.sendlineafter(b"msg? >",msg2)
        sh.sendlineafter(b"inverse? >",str(0).encode())
        data2 = sh.recvline().decode().strip()
        L1 = bytes.fromhex(data1[:16])
        L2 = bytes.fromhex(data2[:16])
        if xor(L1,L2) == xor(b"a"*8,b"b"*8):
            m = "0"
        else:
            m = "1"
        sh.sendlineafter(b"coin? >",m.encode())

Challenge3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Challenge3:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 8
        self.input_size = 2 * self.block_size
        self.RO1 = PRF(self.block_size)
        self.RO2 = PRF(self.input_size)

    def function1(self, M, inverse):
        if not inverse:
            L, R = M[:self.block_size], M[self.block_size:]
            L, R = R, xor(L, self.RO1.tran(R))
            L, R = R, xor(L, self.RO1.tran(R))
            L, R = R, xor(L, self.RO1.tran(R))
        else:
            L, R = M[:self.block_size], M[self.block_size:]
            L, R = xor(R, self.RO1.tran(L)), L
            L, R = xor(R, self.RO1.tran(L)), L
            L, R = xor(R, self.RO1.tran(L)), L
        return L+R

    def function2(self, M, inverse):
        if inverse or not inverse:        
            return self.RO2.tran(M)

在这一关，开启了inverse功能

设我们输入的数据为$M$，记$L_0,R_0$分别代表左半部分和右半部分，记RO1.tran(R)为$f(R)$

这关需要2次

先分析function1：

当inverse = False时：

经过推导可以知道

第一次加密得到的是$R_0$，$L_0\otimes f(R_0)$

第二次加密得到的是$L_0 \otimes f(R_0)$，$R_0\otimes f(L_0\otimes f(R_0))$

第三次加密得到的是$R_0\otimes f(L_0\otimes f(R_0))$，$(L_0\otimes f(R_0))\otimes f(R_0\otimes f(L_0\otimes f(R_0)))$

返回第三次加密的结果

当inverse = True时：

经过推导可以知道

第一次加密得到的是$R_0\otimes f(L_0)$，$L_0$

第二次加密得到的是$L_0\otimes f(R_0\otimes f(L_0))$，$R_0 \otimes f(L_0)$

第三次加密得到的是$(R_0\otimes f(L_0))\otimes f(L_0\otimes f(R_0\otimes f(L_0)))$，$L_0\otimes f(R_0\otimes f(L_0))$

对比两种情况下得到的左右两部分

我们只要让两次输入的左右部分互换（注意开启inverse），即可使得$L_1 = R_2$，$L_1$指第一次接受到数据的左半部分，$R_2$指第二次接收到数据的右半部分

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solve3():
    sh.sendlineafter(b"ow many times are required to roll for solving 3?",str(2).encode())
    msg1 = b"62" * 8 + b"61" * 8
    msg2 = b"61" * 8 + b"62" * 8
    for _ in trange(33):
        sh.sendlineafter(b"msg? >",msg1)
        sh.sendlineafter(b"inverse? >",str(0).encode())
        data1 = sh.recvline().decode().strip()
        sh.sendlineafter(b"msg? >",msg2)
        sh.sendlineafter(b"inverse? >","y".encode())
        data2 = sh.recvline().decode().strip()
        L1 = bytes.fromhex(data1[:16])
        R2 = bytes.fromhex(data2[16:])
        if L1 == R2: 
            m = "0"
        else:
            m = "1"
        sh.sendlineafter(b"coin? >",m.encode())

Challenge4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Challenge4:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 8
        self.input_size = 2 * self.block_size
        self.PRP1 = PRP(self.block_size)
        self.PRP2 = PRP(self.input_size)

    def function1(self, M, inverse):
        X, T = M[:self.block_size], M[self.block_size:]
        X = xor(X, T)
        for _ in range(2):
            X = xor(self.PRP1.tran(X, inverse),T)
        return X

    def function2(self, M, inverse):
        return self.PRP2.tran(M, inverse)[:self.block_size]

    def roll(self, M, inverse):
        return [self.function1,self.function2][self.coin](M,inverse)

设我们输入的数据为$M$，记$X_0,T_0$分别代表左半部分和右半部分，记RO1.tran(R)为$f(R)$，这关有inverse

这关需要2次

function1中，当inverse = False时

$X=X_0 \otimes T_0$

第一次加密后得到$X_1 = f(X) \otimes T_0$

第二次加密后得到$X_2 = f(X_1) \otimes T_0$

当inverse = True时

$X = X_0 \otimes T_0$

第一次加密后得到$X_1 = f^{-1}(X)\otimes T_0$

第二次加密后得到$X_2 = f^{-1}(X_1)\otimes T_0$

第一次在inverse = False的时候，传入$X_0,T_0$

我们只要把第一次（inverse = False时的结果）即$f(X_1) \otimes T_0$和$T_0$拼接再次传入服务器

先经过异或，得到$f(X_1)$

然后第一次加密得到$C_1 = X_1 \otimes T_0 = f(X)$

第二次加密得到$C_2 = X \otimes T_0 = X_0$

把第二次的结果和第一次传入的$X_0$对比，即可知道执行了function1还是function2

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solve4():
    sh.sendlineafter(b"ow many times are required to roll for solving 4?",str(2).encode())
    for _ in trange(33):
        msg1 = b"61" * 16
        sh.sendlineafter(b"msg? >",msg1)
        sh.sendlineafter(b"inverse? >",str(0).encode())
        data1 = sh.recvline().decode().strip()
        X1 = bytes.fromhex(data1)
        msg2 = hex(bytes_to_long(X1))[2:].zfill(16).encode() + b"61" * 8
        sh.sendlineafter(b"msg? >",msg2)
        sh.sendlineafter(b"inverse? >","y".encode())
        data2 = sh.recvline().decode().strip()
        X2 = bytes.fromhex(data2)
        if X2 == b"a"*8:
            m = "0"
        else:
            m = "1"
        sh.sendlineafter(b"coin? >",m.encode())

Challenge5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Challenge5:
    def __init__(self):
        self.coin = os.urandom(1)[0] & 1
        self.block_size = 1
        self.input_size = self.block_size
        self.PRP = PRP(self.block_size)
        self.PRF = PRF(self.input_size)

    def function1(self, M):
        return xor(bytes(1),self.PRP.tran(M))

    def function2(self, M):
        return xor(self.PRF.tran(M),bytes(1))

    def roll(self, M, inverse):
        assert inverse == False, "In Challenge 5, inverse is not allowed"
        return [self.function1,self.function2][self.coin](M)

这关没有inverse功能，而且输入的数据大小减少了

function1和function2的区别是PRP.tran(M)和PRF.tran(M)的区别

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
class PRP():
    def __init__(self, n):
        self.domain_cache = {}
        self.range_cache = {}
        self.n = n

    def tran(self, m, inverse = False):
        if not inverse:
            x = m
            if x in self.domain_cache:
                return self.domain_cache[x]
            while True:
                y = os.urandom(self.n)
                if y in self.range_cache:continue
                self.domain_cache[x] = y
                self.range_cache[y] = x    
                return y
        else:
            y = m
            if y in self.range_cache:
                return self.range_cache[y]
            while True:
                x = os.urandom(self.n)
                if x in self.domain_cache:continue
                self.domain_cache[x] = y
                self.range_cache[y] = x    
                return x

class PRF():
    def __init__(self, n):
        self.domain_cache = {}
        self.range_cache = {}
        self.n = n 

    def tran(self, x):
        if x not in self.domain_cache:
            self.domain_cache[x] = os.urandom(self.n)
        return self.domain_cache[x]

这两个区别很明显的一个点是

PRP生成的y都是不同的，就是说保证了值域的元素全部都不同，而PRF并没有这个效果

于是我们需要利用这个点

前面4关用了7次机会，我们还有48次机会

PRF里面元素都不同的概率为$t = 1\times \frac{255}{256}\times\frac{254}{256} \times…\times \frac{209}{256} = 0.009029416209217144$

这个概率算是比较低了

我们输入48个数据，判断接收到的数据是否有相等的，如果有相等的，说明执行了function2

因为$t = 0.009029416209217144$，所以我们判断失败的概率只有$0.009029416209217144$

因为要重复进行33次，所以我们通关失败的概率为$t^{33} = 3.4416696557688015\times 10^{-68}$，概率低的可怕

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solve5():
    sh.sendlineafter(b"ow many times are required to roll for solving 5?",str(48).encode())
    for _ in trange(33):
        C = []
        for i in range(48):
            msg = hex(48 + i)[2:].encode()
            sh.sendlineafter(b"msg? >",msg)
            sh.sendlineafter(b"inverse? >",str(0).encode())
            data = sh.recvline().decode().strip()
            c = bytes.fromhex(data)
            C.append(c)
        C_ = set(C)
        if len(C) != len(C_):
            m = "1"
        else:
            m = "0"
        sh.sendlineafter(b"coin? >",m.encode())

最后，值得注意的是

注意一些细节，比如服务器传给我们的是16进制的数据，我们需要转成字节

而且bytes.fromhex(a)接受的这个a的长度必须是偶数

最后的最后

星盟安全团队纳新！

欢迎师傅们加群（346014666）学习、讨论！

-------------已经到底啦！-------------