CTF_Notes

Posted on Edited on In Word count in article: 40k Reading time ≈ 37 mins.

[TOC]

0x01 Not Wiener

题目是变体的Boneh-Durfee attack, 需要在理解攻击原理后做调整。

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

p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
d = phi - getPrime(540)  # make sure it is big enough that wiener's attack doesn't work
e = pow(d, -1, phi)

flag = open("flag.txt", "rb").read().strip()
m = bytes_to_long(flag)
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

由于d = phi - D (令D为540位的随机素数)，比正常的多了个负号，故要做一些调整。

列出RSA等式： 去掉mod:

两边同时mod e:

其中，k是与D差不多大的负数。

考虑以下的二元多项式： 可得​，所以(k, s)是f 的一个小根，可以用二元copper来解。

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


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []


n = 
e = 
c = 
P = Zmod(ZZ(e))["k,s"]
k, s = P.gens()
f = 1 + k * (n - s)
rs = small_roots(f, (2**540, 2**1025), m=4, d=5)
print(rs)
k, s = map(int, rs[0])
phi = n - s
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

1.2 Boneh-Durfee的碎碎念

从上面的题也可以看出，Boneh-Durfee的核心就是Multivariate Coppersmith，也即多元Coppersmith。对于RSA公钥方程： 去掉取模符号： 同时模e: 令，则可以化成： 可得，其中(k, s)是f 的一个小根。

0x02 Not Wiener(Another)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Util.number import *
from gmpy2 import *
import random, os
from hashlib import sha1
from random import randrange
flag=b''
x = bytes_to_long(flag)

def gen_key():
    while True:
        q = getPrime(160)
        p = 2 * getPrime(1024-160) * q+1
        if isPrime(p):
            break
    h = random.randint(1, p - 1)
    g = powmod(h,(p-1)//q, p)
    y=pow(g,x,p)
    return p,q,g,y
def cry():
    a =
    p = getPrime(512)
    q = getPrime(512)
    d = getPrime(280)
    n = p * q
    e = inverse(d, (p - 1) * (q - 1))
    c = pow(a, e, n)
    return n,e,c

p,q,g,y=gen_key()
k1 = random.randint(1, q-1)
h1 = bytes_to_long(sha1(os.urandom(20)).digest())
r1 = pow(g, k1, p) % q
s1 = ((h1 + x*r1) * invert(k1, q))% q

n,e,c= cry()

a=
b= 17474742587088593627
k2 = a*k1 + b
h2 = bytes_to_long(sha1(os.urandom(20)).digest())
r2 = pow(g, k2, p) % q
s2 = ((h2 + x*r2) * invert(k2, q)) % q
print(n,e,c)
print(p,q,g,y)
print("h1:%s r1:%s s1:%s"%(h1,r1,s1))
print("h2:%s r2:%s s2:%s"%(h2,r2,s2))

题目嵌套了标准Boneh-Durfee attack 和线性DSA攻击。

由cry()函数得之用的RSA加密的a, 同时d较小，用标准Boneh-Durfee attack就能求出a。

接下来是求线性关系的步骤。已知： 一通相消得： 可以求k。得到k再带入一个式子求x，也就是flag。

exp:

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

a =     #Boneh-Durfee
p= 161310487790785086482919800040790794252181955976860261806376528825054571226885460699399582301663712128659872558133023114896223014064381772944582265101778076462675402208451386747128794418362648706087358197370036248544508513485401475977401111270352593919906650855268709958151310928767086591887892397722958234379
q= 1115861146902610160756777713087325311747309309771
g= 61073566757714587321114447684333928353300944355112378054603585955730395524359123615359185275743626350773632555967063692889668342544616165017003197599818881844811647270423070958521148291118914198811187731689123176313367399492561288350530256722898205674043032421874788802819858438796795768177550638273020791962
y= 23678147495254433946472657196764372220306841739888385605070426528738230369489739339976134564575544246606937803367113623097260181789372915552172469427842482448570540429192377881186772226796452797182435452490307834205012154495575570994963829345053331967442452842152258650027916313982835119514473311305158299360
(h1, r1, s1) = 535874494834828755542711401117152397489711233142, 117859946800380767356190121030392492081340616512, 26966646740134065096660259687229179143947213779
(h2, r2, s2) = 236574518096866758760287021848258048065293279716, 863199000523521111517835459866422731857447792677, 517924607931342012033031470185302567344725962419

b = 17474742587088593627

k = (h1*r2-h2*r1 + b*s2*r1)*inverse(s1*r2-a*s2*r1,q) % q
x = (k*s1 - h1)*inverse(r1,q) % q
print(long_to_bytes(x))

0x03 Or1cle

image-20240201233635373

目的是拿到xenny的签名。一同操作后发现hex报错能弹源码：

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
1. get_signature
2. get_flag
3. gift
4. exit
2
sign: the
An error occurred in /app/task.py at line 33 in verify: invalid literal for int() with base 16: b'the'
23: self.P = self.d*secp256k1.G
24:
25: def signature(self,msg):
26: h = int(hashlib.sha256(msg).hexdigest(),16)
27: k = h^self.d
28: r = (k*secp256k1.G).x
29: s = inverse(k,secp256k1.q) * (h + r*self.d) % secp256k1.q
30: return '%064x%064x' % (r, s)
31:
32: def verify(self,z, signature):
33: r, s = int(signature[:64], 16), int(signature[64:], 16)
34: z = int(hashlib.sha256(z).hexdigest(), 16)
35: s_inv = pow(s, secp256k1.q - 2, secp256k1.q)
36: u1 = (z * s_inv) % secp256k1.q
37: u2 = (r * s_inv) % secp256k1.q
38: point = u1 * secp256k1.G + u2 * self.P
39: return point.x == r
40:
41: banner = """
42: _  __                                       __________        ___________
43: | |/_/__ ___  ___  __ __    __              /\____;;___\      |          |
sth error

观察到r s没加非0校验，和CVE-2022-21449一样，非预期直接秒

payload:

1
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
[FR$~ZD]A3TJP23Q5CPUO

做出这道真不是纯运气，要不是之前辛苦复现，不然这道题拿不下来。

0x04 Or2cle

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
from Crypto.Util.number import *
from hashlib import *
import os
from Crypto.Cipher import AES
from Crypto.Util import Counter
from random import *
import socket
import threading
import base64

FLAG = b'fake_flag'

class Proof():
    def S(self,n):
        factors = set()
        while n % 2 == 0:
            factors.add(2)
            n //= 2
        for i in range(3, int(n**0.5) + 1, 2):
            while n % i == 0:
                factors.add(i)
                n //= i
        if n > 2:
            factors.add(n)
        
        return factors

    def Y(self,n):
        if n == 1:
            return 1

        result = n
        for p in self.S(n):
            result *= (1 - 1 / p)
        return int(result)


    def proof(self,n):
        res = 0
        for m in range(1, n+1):
            for l in range(1, m+1):
                for k in range(1, l+1):
                    for j in range(1, k+1):
                        for i in range(1, j+1):
                            for h in range(1, i+1):
                                for g in range(1, h+1):
                                    for f in range(1, g+1):
                                        for e in range(1, f+1):
                                            for d in range(1, e+1):
                                                for c in range(1, d+1):
                                                    for b in range(1, c+1):
                                                        for a in range(1, b+1):
                                                            res +=  b//a*(self.Y(a)) # Euler function 
        return res


class Harukii_Oracle:

    def __init__(self,key):
        self.k  = key

    def pad(self, plaintext):
        block_size = randint(1,len(plaintext)-1)
        if len(plaintext) <  block_size :
            return plaintext
        else:
            padding_length = len(plaintext) // 16
            padding_byets = bytes([padding_length])
            plaintext = plaintext.replace(padding_byets,b"\x00")
            p = plaintext[:16]
            for i in range(1 , padding_length+1):
                p += padding_byets + plaintext[16*i:16*(i+1)]
            return p

    def encrypt(self,plaintext):
        aes = AES.new(self.k,mode=AES.MODE_CTR,counter=Counter.new(128))
        chipertext = aes.encrypt(self.pad(plaintext))
        return chipertext
    
    def gift(self,ciphertext):
        aes = AES.new(self.k,mode=AES.MODE_CTR,counter=Counter.new(128))
        plaintext = aes.decrypt(ciphertext)
        padding_length = len(plaintext) // 16
        padding_bytes = bytes([padding_length])
        return plaintext.count(padding_bytes) == padding_length
        

Menu = """
1. get flag
2. gift
3. exit
"""

def task(client_socket):
    client_socket.settimeout(3600)
    s = str((getPrime(128)))
    client_socket.send(f"s : {s}\n".encode())
    client_socket.send("Give me a hash: ".encode())
    hash = client_socket.recv(1024)[:-1]
    hash = int(hash,16)
    '''if hash != int(sha256(str(Proof.proof(s)).encode()).hexdigest(),16):
        client_socket.send(": C".encode())
        exit(-1)'''
    key = randbytes(16)
    YSGS = Harukii_Oracle(key=key)
    while True:
        try:
            client_socket.send(Menu.encode())
            choice = client_socket.recv(1024).decode().strip()
            if choice == '1' :
                enc_flag = base64.b64encode(YSGS.encrypt(FLAG))
                client_socket.send(f"This is Your flag {enc_flag}".encode())
            elif choice == '2':
                c = client_socket.recv(1024)[:-1]
                if YSGS.gift(c):
                    client_socket.send("Dec successfully".encode())
                else:
                    client_socket.send("Dec faild".encode())

            else:
                exit(-1)
        except Exception as e:
            print(e)


def main():
    server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    server.bind(("0.0.0.0", 9999))
    server.listen(100)
    
    try:
        while True:
            client_sock, address = server.accept()
            
            print(f"Accepted connection from {address[0]}:{address[1]}")
            client_handler = threading.Thread(target=task, args=(client_sock,))
            client_handler.start()
    finally:
        server.close()

if __name__ == "__main__":
    main()

0x04.1 简化proof函数

拿到前几个序列的数不知道咋搞，上谷歌搜，居然在杨辉三角里找到了对应的数，勾起极大的兴趣，于是 pip install pascal 跑测试。其结果也很简单，就是 binomial(s+13,14)。

赛后知道可以用 https://oeis.org/ 查数列，厉害厉害。

0x04.2 CTR Oracle

CTR模式中，AES加密的是Counter，然后把加密得到的Counter与明文异或得到密文。因此，我们对输入1得到的flag密文，改变其中任意一个不是padding位置的字节，在AES解密后得到的明文中，就也只有这一个位置的字节被改变了。

而我们对这一个被改变的字节，遍历256种可能取值，当且仅当解密后的明文恰为padding字节的值时，靶机会返回给我们failed，因为这个时候padding字节多出来一个。我们将这时候的这个字节值记为t。

而padding字节的值是多少，这个我们是知道的，因为我们从输入1返回的密文中，可以知道flag的长度是42，也就自然知道了有几个分组。我们把它记为r。而CTR模式又有一个很重要的性质，也就是同一分组的明文异或等于密文异或，因此对于当前这个字节，其本身的加密值是enc的话，我们就可以由： 求出当前这个字节的明文值。因此我们就可以逐字符爆破，并求出flag的全部内容。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
from pwn import * 
from sage.functions.other import binomial 
from hashlib import sha256 


rec = remote("1.14.108.193", int(31310)) 
r = rec.recvuntil(b'Give me a hash') 
print(r) 
s = int(r.split(b'\n')[0][4:].decode(),10) 
print(s) 
hs = str(sha256(str(binomial(s+13,14)).encode()).hexdigest()).encode() 
print(hs)
rec.sendline(hs) 
rec.sendline(b"1")
rec.recvuntil(b"This is Your flag ")
enc_flag = b64decode(sh.recvline().strip().decode()[2:-1])

if(0):
    for i in range(15,16):
        for j in trange(256):
            rec.sendline(b"2")
            msg = enc_flag[:i] + long_to_bytes(j) + enc_flag[i+1:]
            rec.sendline(msg)
            rec.recvuntil(b"Dec ")
            temp = rec.recvline()
            if(b"fail" in temp):
                print(chr(j ^ enc_flag[i] ^ 2))
                break

#group2
if(0):
    for i in range(17,33):
        for j in trange(256):
            rec.sendline(b"2")
            msg = enc_flag[:i] + long_to_bytes(j) + enc_flag[i+1:]
            rec.sendline(msg)
            rec.recvuntil(b"Dec ")
            temp = rec.recvline()
            if(b"fail" in temp):
                print(chr(j ^ enc_flag[i] ^ 2))
                break

#group3
if(1):
    for i in range(41,43):
        for j in trange(256):
            rec.sendline(b"2")
            msg = enc_flag[:i] + long_to_bytes(j) + enc_flag[i+1:]
            rec.sendline(msg)
            rec.recvuntil(b"Dec ")
            temp = rec.recvline()
            if(b"fail" in temp):
                print(chr(j ^ enc_flag[i] ^ 2))
                break

rec.close()

0x05 babySPN

类DES加密

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

def bin_to_list(r, bit_len):
    list = [r >> d & 1 for d in range(bit_len)][::-1]
    return list

def list_to_int(list):
    return int("".join(str(i) for i in list), 2)

Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]

def round_func(X,r,K):
    kstart=4*r - 4 # 计算了当前轮次所使用的子密钥的起始索引。
    XX = [0] * 16
    for i in range(16):
        XX[i] = X[i] ^ K[kstart+i]
    for i in range(4): # 查找
        value = list_to_int(XX[4*i:4*i+4])
        s_value = Sbox[value]
        s_list = bin_to_list(s_value, 4)
        XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]

    Y=[0] * 16 # 置换
    for i in range(16):
        Y[Pbox[i]-1]=XX[i]
    return Y

def enc(X,K):
    Y = round_func(X,1,K)
    Y = round_func(Y,2,K)
    Y = round_func(Y,3,K)
    Y = round_func(Y,4,K)

    kstart=4*5 - 4
    for i in range(16):
        Y[i] ^= K[kstart+i]
    return Y

K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]

assert len(K) == 32
for i in K:
    assert i == 0 or i == 1

hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
assert flag[7:-1] == hash_value

XX = [0]*16
for i in range(4):
    XX[i*4] = 1
    print(enc(XX,K))
    XX[i*4] = 0

# [0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0]
# [1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1]
# [0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1]
# [1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0]

特么的K已知啊，直接跑题目得flag。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from hashlib import sha256
from Crypto.Util.number import *


def bin_to_list(r, bit_len):
    list = [r >> d & 1 for d in range(bit_len)][::-1]
    return list

def list_to_int(list):
    return int("".join(str(i) for i in list), 2)

P=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
S=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]

def round_func(X,r,K):
    kstart=4*r - 4 
    XX = [0] * 16
    for i in range(16):
        XX[i] = X[i] ^ K[kstart+i]
    for i in range(4): 
        value = list_to_int(XX[4*i:4*i+4])
        s_value = S[value]
        s_list = bin_to_list(s_value, 4)
        XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]
    Y=[0] * 16 
    for i in range(16):
        Y[P[i]-1]=XX[i]
    return Y

def enc(X,K):
    Y = round_func(X,1,K)
    Y = round_func(Y,2,K)
    Y = round_func(Y,3,K)
    Y = round_func(Y,4,K)
    kstart=4*5 - 4
    for i in range(16):
        Y[i] ^= K[kstart+i]
    return Y

K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]

assert len(K) == 32
for i in K:
    assert i == 0 or i == 1
hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
print(hash_value)

0x06 babySPN_revenge

中间相遇 yyds

0x06.1 准备工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import random
import time
from secret import flag
from hashlib import sha256
from Crypto.Util.number import *

def bin_to_list(r, bit_len):
    list = [r >> d & 1 for d in range(bit_len)][::-1]
    return list

def list_to_int(list):
    return int("".join(str(i) for i in list), 2)

Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]

def round_func(X,r,K):
    kstart=4*r - 4 # 计算了当前轮次所使用的子密钥的起始索引。
    XX = [0] * 16
    for i in range(16):
        XX[i] = X[i] ^ K[kstart+i]
    for i in range(4): # 查找
        value = list_to_int(XX[4*i:4*i+4])
        s_value = Sbox[value]
        s_list = bin_to_list(s_value, 4)
        XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]

    Y=[0] * 16 # 置换
    for i in range(16):
        Y[Pbox[i]-1]=XX[i]
    return Y

def enc(X,K):
    Y = round_func(X,1,K)
    Y = round_func(Y,2,K)
    Y = round_func(Y,3,K)
    Y = round_func(Y,4,K)

    kstart=4*5 - 4
    for i in range(16):
        Y[i] ^= K[kstart+i]
    return Y

K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]

assert len(K) == 32
for i in K:
    assert i == 0 or i == 1

hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
assert flag[7:-1] == hash_value

XX = [0]*16
for i in range(4):
    XX[i*4] = 1
    print(enc(XX,K))
    XX[i*4] = 0

# [0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0]
# [1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1]
# [0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1]
# [1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0]

刚看到题用的是差分，因为一般类DES的考法也就差分/线性，翻了几篇博客没懂就没往下想了，可能官方解法是差分吧。

逆s, p 盒

1
2
3
4
Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
rePbox = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]
reSbox=[3, 5, 4, 14, 6, 11, 15, 8, 10, 12, 9, 2, 13, 1, 0, 7]

逆加密算法

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
def round_func(X,r,K):
    kstart=4*r - 4
    XX = [0] * 16
    for i in range(16):
        XX[i] = X[i] ^ K[kstart+i]
    for i in range(4):
        value = list_to_int(XX[4*i:4*i+4])
        s_value = Sbox[value]
        s_list = bin_to_list(s_value, 4)
        XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]

    Y=[0] * 16
    for i in range(16):
        Y[Pbox[i]-1]=XX[i]
    return Y

def re_round_func4(X,K): # 第四轮
    Y = [0]*16  
    for i in range(16):
        Y[rePbox[i]]=X[i]

    for i in range(4):
        value = list_to_int(Y[4*i:4*i+4])
        s_value = reSbox[value]
        s_list = bin_to_list(s_value, 4)
        Y[4*i],Y[4*i+1],Y[4*i+2],Y[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]
    kstart =  0
    for i in range(16):
        Y[i] = Y[i] ^ K[kstart+i]
    return Y

def re_round_func3(X): # 前3轮
    Y = [0]*16  
    for i in range(16):
        Y[rePbox[i]]=X[i]

    for i in range(4):
        value = list_to_int(Y[4*i:4*i+4])
        s_value = reSbox[value]
        s_list = bin_to_list(s_value, 4)
        Y[4*i],Y[4*i+1],Y[4*i+2],Y[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]

    return Y

0x06.2 中间相遇攻击

中间相遇攻击，明文 ‘0’*16 的两轮加密结果和对应的密文

1
[0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1]

两轮解密的结果相同。把加密结果存在一个dic 里面，然后用相同的key对密文解密，在dic 里面查，如果查到的话可能就是，再用其他密文检验以下。

中间还遇到一个毛病：key只存了12 bit（因为只需要12bit ），4096个数据，如果range 设大的话就会覆盖 :( ，要再加一个循环。先构造一个key检验一下,有结果，于是开爆，花了近7h 成功出结果 :)

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import random
import time
from hashlib import sha256
from Crypto.Util.number import *
from tqdm import *
def bin_to_list(r, bit_len):
    list = [r >> d & 1 for d in range(bit_len)][::-1]
    return list

def list_to_int(list):
    return int("".join(str(i) for i in list), 2)

Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
rePbox = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]
reSbox=[3, 5, 4, 14, 6, 11, 15, 8, 10, 12, 9, 2, 13, 1, 0, 7]


def round_func(X,r,K):
    kstart=4*r - 4
    XX = [0] * 16
    for i in range(16):
        XX[i] = X[i] ^ K[kstart+i]
    for i in range(4):
        value = list_to_int(XX[4*i:4*i+4])
        s_value = Sbox[value]
        s_list = bin_to_list(s_value, 4)
        XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]

    Y=[0] * 16
    for i in range(16):
        Y[Pbox[i]-1]=XX[i]
    return Y

def re_round_func4(X,K):
    Y = [0]*16  
    for i in range(16):
        Y[rePbox[i]]=X[i]

    for i in range(4):
        value = list_to_int(Y[4*i:4*i+4])
        s_value = reSbox[value]
        s_list = bin_to_list(s_value, 4)
        Y[4*i],Y[4*i+1],Y[4*i+2],Y[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]
    kstart =  0
    for i in range(16):
        Y[i] = Y[i] ^ K[kstart+i]
    return Y

def re_round_func3(X):
    Y = [0]*16  
    for i in range(16):
        Y[rePbox[i]]=X[i]

    for i in range(4):
        value = list_to_int(Y[4*i:4*i+4])
        s_value = reSbox[value]
        s_list = bin_to_list(s_value, 4)
        Y[4*i],Y[4*i+1],Y[4*i+2],Y[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]

    return Y

def enc(X,K):
    Y = round_func(X,1,K)
    Y = round_func(Y,2,K)
    Y = round_func(Y,3,K)
    Y = round_func(Y,4,K)

    kstart=4*5 - 4
    for i in range(16):
        Y[i] ^= K[kstart+i]
    return Y




ss = [[0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
      [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0],
      [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1],
      [0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1]]


XX = [0]*16
XX[0] = 1

for start in trange(0,2**20,5000):
    FLAG = set()

    A = dict()
    

    for j in range(start,start+5000):
        K = bin_to_list(j,20)
        Y = round_func(XX,1,K)
        Y = round_func(Y,2,K)
        kstart=8
        for i in range(12):
            Y[i] = Y[i] ^ K[kstart+i]
        A[str(Y[:12])] = K 
 

    ss = [0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1]

    flag = set()
    for j in trange(2**20):
        XXX = ss.copy()
        K = bin_to_list(j,20)
        kstart = 4
        for i in range(16):
            XXX[i] = XXX[i]^K[kstart+i]

        Y = re_round_func4(XXX,K)
        Y = re_round_func3(Y)

        
        if str(Y[:12]) in A:
            tmpk = A[str(Y[:12])][:12]+K[:]
            if enc([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],tmpk) ==  [0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1] and \
                enc([0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],tmpk) == [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0] and \
                enc([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],tmpk) == [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1] and \
                enc([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],tmpk) == [0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1]:
                print("[++]",tmpk)
                exit()

0x07 guess

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import *
from Crypto.Util.Padding import pad
from hashlib import md5
from Crypto.Cipher import AES
from flag import flag
f = open('output.txt','w')

for i in range(724):
    f.write(f'{getrandbits(32)}\n')
f.close()


r = getrandbits(32)
key = bytes.fromhex(hex(r)[2:])
key = md5(key).digest()
cipher = AES.new(key,AES.MODE_CBC)
c = cipher.encrypt(pad(flag,16))
print(f'c = \'{cipher.iv.hex() + c.hex()}\'')
#c = '63948876307822aa9624af484095c5b24682e65b655e5d02245eb6ab75fd121086cc2ec870dbd2fdcfdc2271d0f92e9c9264c36c33e9d8178d5319f93a8bbfaf'

随机数预测板子题

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from randcrack import RandCrack 
rc = RandCrack()

from random import *
from Crypto.Util.Padding import pad
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.number import *
f = open(r'D:\Codes\Py_Sage\CTFs\tr3\guess\output.txt').readlines()
for i in range(624):
    rc.submit(int(f[i][:-1]))
c = 0x63948876307822aa9624af484095c5b24682e65b655e5d02245eb6ab75fd121086cc2ec870dbd2fdcfdc2271d0f92e9c9264c36c33e9d8178d5319f93a8bbfaf
r = 1502121338 
key = bytes.fromhex(hex(r)[2:])
key = md5(key).digest()
cipher = AES.new(key,AES.MODE_CBC) 
m = cipher.decrypt(long_to_bytes(c)) 
print(m)
# b'\x9b\x82\x00`l\xf5\xc8\xb9h\n\xf5<\x15\xa0f\xb2flag{97ca5b76-8a30-4df6-80cd-a4e2bad62155}\x06\x06\x06\x06\x06\x06'

0x08 babyRSA

1
2
3
('n:', 22034616002810077367213986975491254660059405267832839238660142745262533722936869262128002848007071492830566792423948764669542596674862348845018069988568386929972799963860498358532060076292090442666332244803634081932410319039049654417535288106255607272156125389093011075687983996658797091362429917761882582099891126882036275226319812950951273212778669525797252443533260358966791414451881952511213526139935019304078758161325320517695299473291202659147434843041548537463174719777262120734530482940790956181957828062067836118689134391817949968101908769390005724479538030093708384442926717939114194865171002974201607355261L)
('c:', 20469034012123404076331293515779254954797808270935072114729372287245649610121080279184065426105281406860069553866209372595886210199176717098929527014734777649004384405838825686832773250279825426103096689541863510283436407479993952428231422039491580582571501337912762476066050277566271740509880341132535061587256227820709664193802144540270571043184987859395645170779868594055385825899332262330699726043205693059288435082520728534514238010811098688960645472489760661394372464255790881986507220546567276185756688666189798660124229702494405401932248169415100020710612561978055850185228950902318953220607561069714240313412L)
('2*d*p+e*phi*2022:', 39206578702502470103641878234442024449922614797772379120404634446012419092475608084750942867787633630781021483249268279521404489069691226296374182621200579605613752522199777660971270916164047179283335404597834512872467549667378195297852090765579955918118786564094332675852752753093339707155099868363104045506937661560587121432325312939065860121168279728628228341816192327237956465619337429317327445361882052348803647505958880546289841864188870937320296098336965262516469766484226633795937493516196887683482439410493756074940283816485855110342423429694640857595914753989189028644536383252655260745430046293522349747435347332238L)

数论题。 利用pow乘e

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = 2203461600281007736721398697549125466005940526783283923866014274526253372293686926212800284800707149283566792423948764669542596674862348845018069988568386929972799963860498358532060076292090442666332244803634081932410319039049654417535288106255607272156125389093011075687983996658797091362429917761882582099891126882036275226319812950951273212778669525797252443533260358966791414451881952511213526139935019304078758161325320517695299473291202659147434843041548537463174719777262120734530482940790956181957828062067836118689134391817949968101908769390005724479538030093708384442926717939114194865171002974201607355261

c = 20469034012123404076331293515779254954797808270935072114729372287245649610121080279184065426105281406860069553866209372595886210199176717098929527014734777649004384405838825686832773250279825426103096689541863510283436407479993952428231422039491580582571501337912762476066050277566271740509880341132535061587256227820709664193802144540270571043184987859395645170779868594055385825899332262330699726043205693059288435082520728534514238010811098688960645472489760661394372464255790881986507220546567276185756688666189798660124229702494405401932248169415100020710612561978055850185228950902318953220607561069714240313412

hint = 3920657870250247010364187823444202444992261479777237912040463444601241909247560808475094286778763363078102148324926827952140448906969122629637418262120057960561375252219977766097127091616404717928333540459783451287246754966737819529785209076557995591811878656409433267585275275309333970715509986836310404550693766156058712143232531293906586012116827972862822834181619232723795646561933742931732744536188205234880364750595
88805462898418641888709373202960983369652625164697664842266337959374935161968876834824394104937560749402838
16485855110342423429694640857595914753989189028644536383252655260745430046293522349747435347332238

d = hint //2

mp = pow(c,d,n)

print(long_to_bytes(mp))
# b'flag{97847092-ed96-4962-a57e-d1e225adaa21}'

0x09 LFSR

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
from os import urandom
from Crypto.Util.number import bytes_to_long
from random import getrandbits
from flag import FLAG

class byte_lfsr:
    def __init__(self, init, msg): #urandom flag
        self.state = init
        self.mask = list(map(int, list(bin(msg)[2:])))
        while len(self.mask) % 8 != 0:
            self.mask.append(0)

    def next(self):
        nextstate = 0
        for i, s in enumerate(self.state):
            nextstate ^= self.mask[i] * s
        self.state = self.state[1:] + nextstate.to_bytes(1, byteorder = 'big')

bl = byte_lfsr(urandom(8 * len(FLAG)), bytes_to_long(FLAG))

for i in range(getrandbits(10)):
    bl.next()

leak_seq = b""
trick = 1 + getrandbits(2)
for i in range(len(FLAG) * 16):
    bl.next()
    leak_seq += (bl.state[-1] >> trick).to_bytes(1, byteorder = 'big')

with open(r"output.txt", "w") as f:
    f.write(leak_seq.hex())

解 模2 有限域内的线性矩阵方程。

exp:

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 *

n = 38
M = matrix(GF(2),8*n,6*(8*n-1))
m = long_to_bytes(0x360c2b0209350b2a3a202029300a0222292e211f203714190f1a29272c3d1610121c302819291e33051b291e352f091027031b153a350b0324022f1d390124300f0510363700360c2e063404203a193e292b0d091d2c2c1d0a2a051e2201172e3a011d2610261d0b2d1d0a140e3b0128301c13270014130d3d182e3b222c142e25081a3e38332d221b072804083a350b023c292d24063b0424331b0200211439062a3405033c3a0d083d17132134033924340c0019003b192f1e3c2e270a151c23152e0b3c201d3624373a240c0d3c1e2d16160b2a251131360e173a0c25280211153128370d08273d08272e23072d211e2a3c272b00073635060e1b111f15283c1133033f29101937343318151001383d1b3b3c26361b1a001a233d0d200d070f042d2c20323130141c21160c162a0b0a3c3e0d280e212d0e1433221709202c14140c1f3402181a17160e1a342b133439173e051a3212391d203e303a03312d2a22380b000d271702002f13371509200b273c0d18070f232a3119021e100f1d36281525282d2f27231f3136161728242d000a2b1c3b102038043f1f3f130c2b1437163a063f0e21392b2a11192a3922231c333c1f1f05222c2c1b3a11270032191035023632340f2439290f28213e001a04182c2f3522303c35273b2a0e002a1a081a3c1639290127100f110e123c04222c022137280435261e20262d2c2702101d3f0e0b361f002622153d302f3f1a1907171a1627271e200917201b3e112520130b270b3a2836041d3a0921341d361025271b3b1f391b15040f170a36303e1f300c283a28090e2c1821213d1e3213361334252d3a1d16101816370e37393f)
l = [_ for _ in m]


for i in range(8*n):
    for j in range(8*n-1):
        for k in range(6):
            M[i,j*6+k] = l[i+j] >> (5-k)
c = matrix(GF(2),1,6*(8*n-1))

for i in range(8*n-1):
    for j in range(6):
        c[0,i*6+j] = l[i+8*n+1] >> (5-j)
        
print(long_to_bytes(int(''.join([str(i) for i in M.solve_left(c)[0]]),2)))

# b'flag{ByT3_L45R_15_Just_A_w3ak3r_LFsr!}'

0x0a oppen pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime
from flag import flag
flag = bytes_to_long(flag)

p = 10890455068677885779398166920026877038566265123660591539666259433835080382866954510383603736376722259609099444600735428341177486778578366155262865032634051
q = p+1
assert flag**2 < p
a = pow(flag+p, q, p)

print(a)
"""
output
14838709304882207428416854486907460402716139083628439118906432540679357874902811904249393372522575625
"""

由二项式定理可将加密式展开： 可以看到，除第一项不含p外，其余各项都含有p及p的乘方。根据同余式的结合律，后面的项模p均为0。故原式等于

又由小费马定理： 原式还可化简为

根据条件​,直接将a开方就是flag了

exp:

1
2
3
4
5
6
import gmpy2
from Crypto.Util.number import long_to_bytes
a=14838709304882207428416854486907460402716139083628439118906432540679357874902811904249393372522575625
f=gmpy2.iroot(a,2)
print(long_to_bytes(f[0]))

0x0b Dangerous RSA

1
2
3
4
#n:  0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e:  0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?

低指数攻击：在e较小，m^e<n时，可直接对c开方得到m

exp:

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
from gmpy2 import iroot
n=0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
e=0x3
c=0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
m=iroot(c,e)
if m[1]:
    print(long_to_bytes(m[0]))
else:
    print("no ans!")
b'flag{25df8caf006ee5db94d48144c33b2c3b}'

0x0c ChildRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag

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

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

这道题有意思的地方在getPrime的方式：通过随机产生素数与之相乘，达到上限后+1得到素数。而sieve_base是个包含了前10000个素数的列表，所以设为sieve_base中的素数乘积，则。

费马小定理：为素数，则，可得推论：为素数，为整数，则

代入题目条件有是的倍数。

又因为也是的倍数，可以得到 因此求出是关键。由于复杂度过高，可以适当简化运算。经证明： 从而将直接幂运算转换为了横幂运算。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from random import choice

import gmpy2
from Crypto.Util.number import isPrime, sieve_base as primes
from Crypto.Util.number import long_to_bytes
e = 0x10001
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
t=1
for i in primes:
    t=t*i
t=gmpy2.powmod(2,t,n)
p=gmpy2.gcd(t-1,n)
q=n//p
f=(p-1)*(q-1)
d=gmpy2.invert(e,f)
m=gmpy2.powmod(c,d,n)
print(long_to_bytes(m))
# b'NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}'

0x0d bbbbbbrsa

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 base64 import b64encode as b32encode
from gmpy2 import invert,gcd,iroot
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
import random

flag = "******************************"

nbit = 128

p = getPrime(nbit)
q = getPrime(nbit)
n = p*q

print p
print n

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

e = random.randint(50000,70000)

while True:
	if gcd(e,phi) == 1:
		break;
	else:
		e -= 1;

c = pow(int(b2a_hex(flag),16),e,n)

print b32encode(str(c))[::-1]

由题：c给的base64是逆序打印的，所以要先逆回去，然后解密得到c。由于不知道e,要在给定的范围内爆破，爆破方法是求解出原文看有没有flag,ctf,{}之类的特定的字符串。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2 as gp
from Crypto.Util.number import *
c = '==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM'
c = base64.b64decode(c[::-1])
#c=2373740699529364991763589324200093466206785561836101840381622237225512234632
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
p = 177077389675257695042507998165006460849
q=n//p
f=(p-1)*(q-1)
for e in range(50000,70000):
    if gp.gcd(e, f) == 1:
        d = gp.invert(e, f)
        m = gp.powmod(c, d, n)
        flag=long_to_bytes(m)
        if b'flag' in flag or b'CTF' in flag or (b"{" in flag and b'}' in flag):
            print(flag)
# b'flag{rs4_1s_s1mpl3!#}'

0x0e babyrsa

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

def nextPrime(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n

p = getPrime(1024)
q = nextPrime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(flag.encode()), e, n)

p和q隔得很近，可以通过爆破得到。

至于如何爆破的……

由公式 以及对数运算，可得应该在到之间。

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 *
import gmpy2 as gp
e = 0x10001
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
t=e*d-1
i=2**15
while True:
    if t%i==0:
        fai = t // i
        q = gp.next_prime(gp.iroot(fai, 2)[0])
        if fai % (q - 1) == 0:
            p = (fai // (q - 1)) + 1
            if isPrime(p):
                print(long_to_bytes(gp.powmod(c, d, p * q)))
            break

    i=i+1

# b'NCTF{70u2_nn47h_14_v3ry_gOO0000000d}'

0x0f babyrsa

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
import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

r=myGetPrime()

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?

威尔逊定理求解。

求解方程,又有

可以设，则有

因为，原式还可以化简为 exp:

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

def mul(a,b):
    out = 0
    m = bin(b)[2:]
    x = len(m)
    for i in range(x):
                if (m[i:i + 1] == '1'):
                        out += a << (x - i - 1)
    return out
def solve(A,B):
    i=1
    for j in range(B+1,A-1):
        i=(i*j)%A
    x=gp.next_prime(gp.invert(i,A))
    return x

A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e=0x1001
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
p=solve(A1,B1)
q=solve(A2,B2)
r=n//(mul(p,q))
def RSA(p,q,r,e,c):
    n=p*q
    f=(p-1)*(q-1)*(r-1)
    d=gp.invert(e,f)
    m=gp.powmod(c,d,n)
    return m
print(long_to_bytes(RSA(p,q,r,e,c,)))

# b'RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}'