PAD

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 getPrime, getRandomRange, bytes_to_long
from flag import flag

assert len(flag) == 64

class RSA():
    def __init__(self, m: int):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.e = getRandomRange(1, 8)
        self.m = m
        self.n = self.p * self.q

    def Publickey(self):
        return (self.n, self.e, self.c)

    def Encrypt(self):
        pad = PAD(m=self.m, e=0)
        pad.PAD()
        self.c = (pad.e, pow(pad.M, self.e, self.n))

class PAD():
    def __init__(self, m: int, e):
        self.e, self.m, self.mbits = e, m
        self.mbits = m.bit_length() # 510
        if e == 0:
            self.e = getRandomRange(2, 7)

    def PAD(self):
        self.M = pow(self.e, self.mbits) + pow(self.m, self.e)

GIFT = bytes_to_long(flag)
with open("GIFT.txt", "w") as f:
    for i in range(40):
        rsa = RSA(m=GIFT)
        rsa.Encrypt()
        f.write(str(rsa.Publickey()) + "\n")

稍微看了一眼，发现真有 RSA.e = 1 并且 PAD.e = 2 的数据，直接减去 2^510 然后开方啊愣着干嘛：

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

f = open("GIFT.txt", "rt")

for line in f:
    n, e, c = eval(line.strip())
    pe, pc = c
    if e == 1 and pe == 2:
        m = pc - 2**510
        print(long_to_bytes(isqrt(m)).decode())
        break

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

def fakeN_list():
    puzzle_list = []

    for i in range(15):
        r = getPrime(32)
        puzzle_list.append(r)

    p = getPrime(32)
    q = getPrime(32)
    com = p*q
    puzzle_list.append(com)

    return puzzle_list

def encrypt(m, e, fake_n_list):
    fake_n = 1
    for i in range(len(fake_n_list)):
        fake_n *= fake_n_list[i]
    really_n = 1
    for i in range(len(fake_n_list)-1):
        really_n *= fake_n_list[i]

    c = pow(m, e, really_n)
    print("c =", c)
    print("fake_n =", fake_n)

if __name__ == '__main__':
    m = bytes_to_long(flag)
    e = 65537
    fake_n_list = fakeN_list()
    encrypt(m, e, fake_n_list)

'''
c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
fake_n = 178981104694777551556050210788105224912858808489844293395656882292972328450647023459180992923023126555636398409062602947287270007964052060975137318172446309766581
'''

这题中 fake_n 不难分解，至于 really_n 少了哪一个质数，全试一遍不就知道了：

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 itertools import combinations

fake_n_list = [2215221821, 2290486867, 2333428577, 2361589081, 2446301969, 2507934301, 2590663067, 3107210929, 3278987191, 3389689241, 3417707929, 3429664037, 3716624207, 3859354699, 3965529989, 4098704749, 4267348123]
c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
e = 65537

for primes in combinations(fake_n_list, len(fake_n_list)-2):
    n = 1
    for p in primes:
        n *= p
    phi = 1
    for p in primes:
        phi *= p-1
    d = inverse(e, phi)
    m = pow(c, d, n)
    try:
        print(long_to_bytes(m).decode())
    except:
        pass

baby_classic

你这辈子就是被古典密码给害了，后面我忘了。

脑子不好写不出 Decrypt，直接最笨的方法正向爆搜，每 6 个字符一组每次最多也就 29^6 = 594823321 次… 还是挺多的。不过在比赛结束前爆破出来了：

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 string import ascii_uppercase
from itertools import product
from tqdm import tqdm
import numpy as np

ls = ascii_uppercase + '_.*'

def str2mat(s):
    res = np.zeros((len(s) // 6, 6), dtype=int)
    for i in range(0, len(s)):
        res[i // 6, i % 6] = ls.index(s[i])
    return res

def linedot(a, b):
    return [sum([a[j][i] * b[i] for i in range(len(b))]) % 29 for j in range(len(a))]

if __name__ == "__main__":
    m = str2mat("VOWAS*TED.AE_UMLVFV*W*HSSSTZIZZZDAKCLXZKM_E*VR*Y")
    c = str2mat("QLOKQGUWMUTGZSDINCQVIVOLISFB_FC.IC_OSPLOBGOVSCZY")

    for x in tqdm(range(6)):
        for key in tqdm(product(range(29), repeat=6), total=len(ls)**6, leave=False):
            a = linedot(m, key)
            s = [(a[i] - c[i][x]) % 29 for i in range(8)]
            if len(set(s)) == 1:
                print('', x, key, sep="\n")
                break

服务器跑了十几个小时给我把 key1 爆出来了，手补一下 key2：

1
2
key1 = IZ_WRDE_MXGAQUQUCQZPYZFVZXSBTLW_BNWX
key2 = .FR*XZ

然后就是 ciphertext，因为是有意义的英文句子，所以可以人力配合爆搜的形式搞出来，又是好几个小时罢了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 部分内容同上一个脚本

def linedot(a, b, c):
    return [(sum([b[j][i] * a[j] for j in range(6)]) + c[i]) % 29 for i in range(len(a))]

def list2str(l):
    return ''.join([ls[x] for x in l])

if __name__ == "__main__":
    k1 = str2mat("IZ_WRDE_MXGAQUQUCQZPYZFVZXSBTLW_BNWX")
    k2 = str2mat(".FR*XZ")[0]
    ciphertext = str2mat("MHDTBJSZXLHH.Z.VWGLXUV.SDQUPAMEPNVQVQZX_CBDZHM_IBZRGLJP_YSBDXN.VACLDGCO_")

    for x in tqdm(range(12)):
        c = list(ciphertext[x, :])
        repeat = 6
        for plain in tqdm(product(range(29), repeat=repeat), total=len(ls)**repeat):
            # plain = (,) + plain
            r = linedot(plain, k1, k2)
            if sum([r[i] == c[i] for i in range(6)]) == 6:
                print(x, list2str(plain), plain)
                break

得到的明文是：

1
YOU_KNOW_THE_MYSTERY_OF_THE_MATRIX**BUT_THIS_IS_BEGINNING_OF_CRYPTOLOGY.

按题目要求求个哈希后就是 Flag 了。

Hard_ECC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from flag import flag

A = [0,
     3,
     0,
     973467756888603754244984534697613606855346504624,
     864199516181393560796053875706729531134503137794]
p = 992366950031561379255380016673152446250935173367
ec = EllipticCurve(GF(p), [A[0], A[1], A[2], A[3], A[4]])

T = ec.random_point()
secret = int.from_bytes(flag, 'little')
Q = T * secret
print(T, Q)

# (295622334572794306408950267006569138184895225554 : 739097242015870070426694048559637981600496920065 : 1)
# (282367703408904350779510132139045982196580800466 : 411950462764902930006129702137150443195710071159 : 1)

ECC 是什么我没学过啊。

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

A = [0,
     3,
     0,
     973467756888603754244984534697613606855346504624,
     864199516181393560796053875706729531134503137794]
p = 992366950031561379255380016673152446250935173367
ec = EllipticCurve(GF(p), [A[0], A[1], A[2], A[3], A[4]])

T = (295622334572794306408950267006569138184895225554,
     739097242015870070426694048559637981600496920065)
Q = (282367703408904350779510132139045982196580800466,
     411950462764902930006129702137150443195710071159)

flag = discrete_log(ec(Q), ec(T), operation='+')
print(long_to_bytes(flag)).decode()[::-1]

PAD_revenge

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

assert len(flag) == 64

class RSA():
    def __init__(self, m: int):
        self.p, self.q, self.e, self.m = getPrime(
            256), getPrime(256), getRandomRange(1, 9), m
        self.n = self.p * self.q
    def Publickey(self):
        return (self.n, self.e, self.c)
    def Encrypt(self):
        pad = PAD(m=self.m, e=0)
        pad.PAD()
        self.c = (pad.e, pow(pad.M, self.e, self.n))

class PAD():
    def __init__(self, m: int, e):
        self.e, self.m, self.mbits = e, m, m.bit_length()
        if e == 0:
            self.e = getRandomRange(1, 9)
    def PAD(self):
        self.M = pow(self.e, self.mbits) + pow(self.m, self.e)

GIFT = bytes_to_long(flag)
with open("GIFT.txt", "w") as f:
    for i in range(100):
        rsa = RSA(m=GIFT)
        rsa.Encrypt()
        data = rsa.Publickey()
        if data[1]*data[2][0] <= 2:
            continue
        f.write(str(data) + "\n")

看了一眼存在 3 组 RSA.e = 1 并且 PAD.e = 3 的数据，直接扒出来然后 CRT。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import long_to_bytes
from functools import reduce
import gmpy2

def CRT(mi: list, ai: list) -> int:
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m)
                for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

e = 3
ns=[4205338792881421548510609645647062608905484696099258750943039118994520455106270839395319116980996505132271552239717225130972438536887110724158402296232289, 7050174313884434729593139368893291621548368062755985279847850232740992709140864927641348128276777490337461431355020263819014375471971053422267553276559149, 7695312868320303154724182556869744062740975850081486948529306458791551745279043014584922518803724721857725624240269226703220670466322322864253572576548333]
cs=[590242556810530557883636062945321456666605165279521102134969558150863508014273375308372904949297413593224978273122299933502842450872249868557340596692448, 2893746834891731849952475353675823291920101887211621827992533553019484178344684430992593454765874180526901317935813716254980891868014768672217101779002964, 4853546005581242275031566639028865993927807758919394191424484984623935750674499388240409403735193793296025751636464209778684176500380928091202873126090673]

m = gmpy2.iroot(CRT(ns, cs), e)[0]
print(long_to_bytes(m))

baph

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 base64 import b64encode
from Crypto.Util.number import *
from string import ascii_letters
from flag import flag

ls = ascii_letters + '!,.? {}' + '01232456789'
assert all([i in ls for i in flag])
ba = b64encode(flag.encode())
baph, key = '', ''

for b in ba.decode():
	if b.islower():
		baph += b.upper()
		key += '0'
	else:
		baph += b.lower()
		key += '1'

baph = baph.encode()
key = long_to_bytes(int(key, 2))
enc = b''
for i in range(len(baph)):
	enc += long_to_bytes(baph[i] ^ key[i % len(key)])

f = open('flag.enc', 'wb')
f.write(enc)
f.close()

看懂代码后，从 Flag 的开头是 flag{ 入手进行人工分析：

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
8d 63 44 2e ee 6f 45 .6 .. 2. .e 2f

 1  0  0  0  1  1  0  1  0  1  1  0
f7 2e 1c 66 94 5c 11 82 8c 1c 9b 61 
 Z  m  x  h  Z  3  t              r
 f   l   a   g   {   .   .   .   .

 0  0  1  1  0  1  0  0  0  1  0  0
ce 2e 22 1e aa 18 1d ae 8a 49 e2 79 
 c  m  F  0  d  W  x              r

 0  0  1  0  1  1  1  0  1  1  1  0
cf 2d 29 66 87 1c 20 a1 bb 1c 97 7b 
 b  n  M  h  I  S  E              p

 1  1  1  0  0  1  1  0  1  1  1  1
f7 1b 36 7e ac 18 33 bc a7 49 d8 1b 
 Z  X  R  p  b  W  V              0

 0  1  0  0  0  1  0  1  .  .  .  0
ce 04 1c 78 ad 5d 09 d4 b4 5d cc 67 
 c  G  x  v  c  2  l              l

 0  1  1  0  1  1  0  .  .  .  .  0
c9 0b 36 66 97 5d 11 bc a7 49 c0 67 
 d  H  R  h  Y  2  t              l

 0  0  1  0  1  1  1  .  .  .  .  0
cf 2a 26 67 94 1c 27 aa b4 63 d4 63 
 b  i  B  i  Z  S  B              h
 n  [ ]  b   e  [ ]  .   .   .   .

 1  1  1  0  0  0  1  0  1  1  1  1
f4 50 36 7e aa 22 30 ae a7 5d c8 16
 Y  3  R  p  d  m  U              9
 c   t   i   v   e   .   .   .   }

查了个字典，最后一个单词可能是 effective，稍微试一下就能找到 Key 了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from string import ascii_letters
import base64

ls = ascii_letters + '!,.? {}' + '01232456789'

with open('flag.enc', 'rb') as f:
    enc = f.read()

key = [0x8d, 0x63, 0x44, 0x2e, 0xee, 0x6f,
       0x45, 0xe6, 0xce, 0x2e, 0xae, 0x2f]

plain = ''
for i in range(len(enc)):
    if key[i % len(key)] != 0x00:
        c = chr(enc[i] ^ key[i % len(key)])
        plain += c.upper() if c.islower() else c.lower()
    else:
        plain += ' ' + hex(enc[i])[2:].rjust(2, '0') + ' '
    if i % len(key) == len(key)-1:
        plain += '\n'

print(base64.b64decode(plain).decode())

我玩青水的

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

m = bytes_to_long(flag)
e = 2
p = getPrime(512)
c = pow(m, e, p)

print(f"p = {p}")
print(f"c = {c}")

'''
p = 7709388356791362098686964537734555579863438117190798798028727762878684782880904322549856912344789781854618283939002621383390230228555920884200579836394161
c = 5573755468949553624452023926839820294500672937008992680281196534187840615851844091682946567434189657243627735469507175898662317628420037437385814152733456
'''

二次剩余定理。没事，我也还没学过，现学的：

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import long_to_bytes
from sympy import legendre_symbol, sqrt_mod

p = 7709388356791362098686964537734555579863438117190798798028727762878684782880904322549856912344789781854618283939002621383390230228555920884200579836394161
c = 5573755468949553624452023926839820294500672937008992680281196534187840615851844091682946567434189657243627735469507175898662317628420037437385814152733456

assert legendre_symbol(c, p) == 1

m = sqrt_mod(c, p)
print(long_to_bytes(m).decode())

This article is authored by Luoingly and is licensed under CC BY-NC 4.0

Permalink: https://luoingly.top/post/beginctf-2024-crypto-writeup/