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
from Crypto.PublicKey import ElGamal
from Crypto.Random import get_random_bytes, random
from Crypto.Util.number import *
from random import *
from secret import flag

def generate_elgamal_keypair(bits=512):
    p = getPrime(bits)

    for _ in range(1000):
        g = getRandomRange(2, 5)
        if pow(g, (p - 1) // 2, p) != 1:
            break

    x = randrange(2, p - 1)
    y = pow(g, x, p)

    return p, g, y, x

# 生成密钥对
key = generate_elgamal_keypair(bits=512)
p, g, y, x = key

print("=== 公钥 (p, g, y) ===")
print("p =", p)
print("g =", g)
print("y =", y)
print()

# 加密
k = randrange(1, p - 2)
m = bytes_to_long(flag)
c1 = pow(g, k, p)
c2 = (m * pow(y, k, p)) % p

print("=== 密文 (c1, c2) ===")
print("c1 =", c1)
print("c2 =", c2)

# 不小心泄露了私钥
print("x =", x)


'''
p =11540963715962144951763578255357417528966715904849014985547597657698304891044841099894993117258279094910424033273299863589407477091830213468539451196239863
g = 2
y =8313424783366011287014623582773521595333285291380540689467073212212931648415580065207081449784135835711205324186662482526357834042013400765421925274271853
=== 密文 (c1, c2) ===
c1 =6652053553055645358275362259554856525976931841318251152940464543175108560132949610916012490837970851191204144757409335011811874896056430105292534244732863
c2 =2314913568081526428247981719100952331444938852399031826635475971947484663418362533363591441216570597417789120470703548843342170567039399830377459228297983
x =8010957078086554284020959664124784479610913596560035011951143269559761229114027738791440961864150225798049120582540951874956255115884539333966429021004214
'''

题目稍微有点乱乱的，不过没关系，就是很典型的 ElGamal算法（加解密看附的文章）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p =11540963715962144951763578255357417528966715904849014985547597657698304891044841099894993117258279094910424033273299863589407477091830213468539451196239863
g = 2
y =8313424783366011287014623582773521595333285291380540689467073212212931648415580065207081449784135835711205324186662482526357834042013400765421925274271853
c1 =6652053553055645358275362259554856525976931841318251152940464543175108560132949610916012490837970851191204144757409335011811874896056430105292534244732863
c2 =2314913568081526428247981719100952331444938852399031826635475971947484663418362533363591441216570597417789120470703548843342170567039399830377459228297983
x =8010957078086554284020959664124784479610913596560035011951143269559761229114027738791440961864150225798049120582540951874956255115884539333966429021004214

from Cryptodome.Util.number import long_to_bytes as l2b
from Cryptodome.Util.number import *

s=pow(c1,x,p)
s_=pow(s,-1,p)
m=(c2*s_)%p
print(long_to_bytes(m))

#b'moectf{th1s_1s_y0ur_f1rst_ElG@m@l}'

2.ez_des

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Cryptodome.Cipher import DES
import secrets
import string

flag = 'moectf{*********}'
characters = string.ascii_letters + string.digits + string.punctuation
key = 'ezdes'+''.join(secrets.choice(characters) for _ in range(3))
assert key[:5] == 'ezdes'
key = 'ezdes9br'
key = key.encode('utf-8')
l = 8

def encrypt(text, key):
    cipher = DES.new(key, DES.MODE_ECB)
    padded_text = text + (l - len(text) % l) * chr(len(text))
    #假设len=70,70%8=6,8-6=2，所以text最后补上2*‘70’
    data = cipher.encrypt(padded_text.encode('utf-8'))
    return data

c = encrypt(flag, key)
print('c =', c)

# c = b'\xe6\x8b0\xc8m\t?\x1d\xf6\x99sA>\xce \rN\x83z\xa0\xdc{\xbc\xb8X\xb2\xe2q\xa4"\xfc\x07'
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
c = b'\xe6\x8b0\xc8m\t?\x1d\xf6\x99sA>\xce \rN\x83z\xa0\xdc{\xbc\xb8X\xb2\xe2q\xa4"\xfc\x07'

from Cryptodome.Cipher import DES
import string

def decrypt(ciphertext, key):
    cipher = DES.new(key, DES.MODE_ECB)# 创建DES解密器
    padded_text = cipher.decrypt(ciphertext)# 解密密文
    pad_char = padded_text[-1]# 获取填充字符/最后一个字节
    pad_len = 8 - (pad_char % 8)# 计算填充长度（根据填充规则）
    
    if padded_text[-pad_len:] != bytes([pad_char]) * pad_len:
        # 验证填充：检查最后pad_len个字节是否都是pad_char
        #padded_text = text + (l - len(text) % l) * chr(len(text))
        #这里的验证就对应了加密算法里面的部分
        raise ValueError("填充验证失败")

    plaintext = padded_text[:-pad_len]# 移除填充，获取原始明文
    return plaintext.decode('utf-8')#意思是保留开头到倒数第pad_len位

characters = string.ascii_letters + string.digits + string.punctuation
key_prefix = 'ezdes'#密码前5位

#暴力破解
for char1 in characters:
    for char2 in characters:
        for char3 in characters:
            key = (key_prefix + char1 + char2 + char3).encode('utf-8')
            try:
                decrypted_flag = decrypt(c, key)
                if decrypted_flag.startswith('moectf{'):
                    print(f"Found key: {key.decode('utf-8')}")
                    print(f"Decrypted flag: {decrypted_flag}")
                    break
            except Exception as e:
                continue

'''
Found key: ezdes8br
Decrypted flag: moectf{_Ju5t envmEra+e.!}
Found key: ezdes8cr
Decrypted flag: moectf{_Ju5t envmEra+e.!}
Found key: ezdes9br
Decrypted flag: moectf{_Ju5t envmEra+e.!}
Found key: ezdes9cr
Decrypted flag: moectf{_Ju5t envmEra+e.!}
'''

try语句的用法

1
2
3
4
5
6
7
8
9
10
11
try:
    num = int(input("输入一个数字: "))
    result = 10 / num
except ValueError:
    print("错误：请输入数字，而不是字符串！")
except ZeroDivisionError:
    print("错误：不能除以0！")
else:
    print(f"计算结果: {result}")
finally:
    print("程序执行完毕")

try→except（如果报错，不报错则跳过）→else→finally

3.baby_next

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 Cryptodome.Util.number import *
from gmpy2 import next_prime
from functools import reduce
from secret import flag

assert len(flag) == 38
assert flag[:7] == b'moectf{'
assert flag[-1:] == b'}'

def main():
    p = getPrime(512)
    q = int(reduce(lambda res, _: next_prime(res), range(114514), p))
    '''
    更加可读的方式是
current = p
for _ in range(114514):  # 循环114514次
    current = next_prime(current)  # 计算下一个素数
q = int(current)
    '''

    n = p * q
    e = 65537

    m = bytes_to_long(flag)

    c = pow(m, e, n)

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

if __name__ == '__main__':
    main()

"""
n = 96742777571959902478849172116992100058097986518388851527052638944778038830381328778848540098201307724752598903628039482354215330671373992156290837979842156381411957754907190292238010742130674404082688791216045656050228686469536688900043735264177699512562466087275808541376525564145453954694429605944189276397
c = 17445962474813629559693587749061112782648120738023354591681532173123918523200368390246892643206880043853188835375836941118739796280111891950421612990713883817902247767311707918305107969264361136058458670735307702064189010952773013588328843994478490621886896074511809007736368751211179727573924125553940385967
"""

有点新意的rsa终于不是nss那种烂俗的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
from Cryptodome.Util.number import inverse, long_to_bytes
import gmpy2

# ---- 题面给定 ----
N = 96742777571959902478849172116992100058097986518388851527052638944778038830381328778848540098201307724752598903628039482354215330671373992156290837979842156381411957754907190292238010742130674404082688791216045656050228686469536688900043735264177699512562466087275808541376525564145453954694429605944189276397
C = 17445962474813629559693587749061112782648120738023354591681532173123918523200368390246892643206880043853188835375836941118739796280111891950421612990713883817902247767311707918305107969264361136058458670735307702064189010952773013588328843994478490621886896074511809007736368751211179727573924125553940385967
e = 65537

# ---- 费马分解：一次命中 ----
A = gmpy2.isqrt(N)
if A * A < N:
    A += 1
B2 = A * A - N
assert gmpy2.is_square(B2)
B = gmpy2.isqrt(B2)

p = int(A - B)
q = int(A + B)
assert p * q == N
print(114514*335)
print("q - p =", q - p)   # 可选：看看因子有多近

# ---- 私钥与解密 ----
phi = (p - 1) * (q - 1)
d = int(inverse(e, phi))
m = pow(C, d, N)
flag = long_to_bytes(m)
print(flag)

ai这里给了我一个“一次命中”的解法其实我是有点担心的，就是怎么就保证B2一次就变成完全平方数，所以我也有一个多次尝试（也就是利用_费马定理_）写的代码：

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
from Cryptodome.Util.number import inverse, long_to_bytes
import gmpy2

def fermat_factor_iter(n, max_steps=10_000_000, progress_every=0):
    """
    费马分解（可多次尝试）。
    - n: 奇合数（本题为 pq）
    - max_steps: 最大尝试次数（a 从 ceil(sqrt(n)) 开始递增）
    - progress_every: >0 时，每隔这么多步打印一次进度
    返回 (p, q)，保证 p <= q
    """
    # 初始 A = ceil(sqrt(n))
    A = gmpy2.isqrt(n)		#A^2是小于n的最大平方数
    if A * A < n:
        A += 1

    # 初始 B^2 = A^2 - n
    B2 = A * A - n

    for step in range(max_steps + 1):
        if gmpy2.is_square(B2):
            B = gmpy2.isqrt(B2)
            p = int(A - B)
            q = int(A + B)
            if p > q:
                p, q = q, p
            if p * q != n:
                raise ValueError("内部一致性校验失败")
            return p, q

        # 不是平方：A -> A+1，增量更新 B2
        # (A+1)^2 - n = (A^2 - n) + 2A + 1
        B2 += 2 * A + 1
        A += 1

        if progress_every and step % progress_every == 0 and step > 0:
            print(f"[fermat] tried {step} steps...")

    raise RuntimeError(f"超过最大步数 {max_steps} 仍未命中完全平方；"
                       f"说明 p,q 差距较大，不适合费马分解（或需增大 max_steps）")

# ====== 题面数值：可替换 ======
N = 96742777571959902478849172116992100058097986518388851527052638944778038830381328778848540098201307724752598903628039482354215330671373992156290837979842156381411957754907190292238010742130674404082688791216045656050228686469536688900043735264177699512562466087275808541376525564145453954694429605944189276397
C = 17445962474813629559693587749061112782648120738023354591681532173123918523200368390246892643206880043853188835375836941118739796280111891950421612990713883817902247767311707918305107969264361136058458670735307702064189010952773013588328843994478490621886896074511809007736368751211179727573924125553940385967
e = 65537

if __name__ == "__main__":
    p, q = fermat_factor_iter(N, max_steps=5_000_000, progress_every=500_000)
    print("p =", p)
    print("q =", q)
    print("q - p =", q - p)

    phi = (p - 1) * (q - 1)
    d = int(inverse(e, phi))
    m = pow(C, d, N)
    flag = long_to_bytes(m)
    print("flag =", flag)

其实与其说是定理 我更愿意理解是给暴力破解提供了一个方法。

4.bsgs

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
a = 13
c = 114514
P = 100000000000099

import math

def bsgs(a, c, P):
    # 确定互素
    assert math.gcd(a, P) == 1
    m = math.ceil(math.sqrt(P))
    step_dict = {}  # 字典

    # right_val = a^j*c % P
    right_val = c % P  # 计算幂次为0时的c对P取模的值
    for j in range(m + 1):
        step_dict[right_val] = j  # 构建字典
        right_val = right_val * a % P  # 累乘

    # left_val = a^im%p
    am = pow(a, m, P)
    for i in range(1, m + 1):
        left_val = pow(am, i, P)
        if left_val in step_dict:  # 找到了左右两边同余的i和j
            j = step_dict[left_val]
            return m * i - j
    return None  # 无解

x = bsgs(a, c, P)
assert pow(a, x, P) == c % P
print(x)

5. ez_square