2024RCTF

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

2024RCTF——Crypto

SignSystem

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
from random import getrandbits, randint
from Crypto.Util.number import getPrime, isPrime, inverse
from hashlib import sha1
import signal


def gen(l, n):
    q = getPrime(l)
    while True:
        t = getrandbits(n - l)
        p = t * q + 1
        if isPrime(p):
            break
    h = randint(1, p - 1)
    g = pow(h, t, p)
    x = randint(1, q)
    y = pow(g, x, p)
    return (p, q, g, y), x


def gen_ephemeral_key(k, lsb, msb):
    return msb << (k + lsb.bit_length()) | getrandbits(k) << lsb.bit_length() | lsb


def sign(pubkey, x, msg, lsb, msb):
    p, q, g, y = pubkey
    k = gen_ephemeral_key(150, lsb, msb)
    r = pow(g, k, p) % q
    Hm = int(sha1(msg).hexdigest(), 16)
    s = (Hm + x * r) * inverse(k, q) % q
    return (r, s)


def verify(pubkey, sig, msg):
    p, q, g, y = pubkey
    r, s = sig
    if not 0 < r < q or not 0 < s < q:
        return False
    w = inverse(s, q)
    Hm = int(sha1(msg).hexdigest(), 16)
    u1 = Hm * w % q
    u2 = r * w % q
    v = pow(g, u1, p) * pow(y, u2, p) % p % q
    return v == r


signal.alarm(900)
with open("flag.txt", "r") as f:
    flag = f.read()

l, n = 160, 1024
pub, x = gen(l, n)
print("your pubKey: {}".format(pub))
msb = getrandbits(8)
lsb = getrandbits(2)

menu = """
[1] sign message
[2] verify signature
"""

for i in range(20):
    print(menu)
    op = int(input(">").strip())
    if op == 1:
        msg = input("Which message to sign?: ").strip().encode()
        if msg == b"get flag":
            print("I'm afraid I can't do that.")
            break
        else:
            sig = sign(pub, x, msg, lsb, msb)
            print(f"Signature: {sig}")
    elif op == 2:
        msg = input("Which message to verify?: ").strip().encode()
        r = int(input("r:").strip())
        s = int(input("s:").strip())
        v = verify(pub, (r, s), msg)
        if v and msg == b"get flag":
            print(flag)
        else:
            print(v)
    else:
        print("Invalid option")

审计代码可以发现，这题有点类似0xGame2023的LLL-ThirdBlood

当时那道题的考点是每个k都不一样，但是k的大小为128bit。

这里的每个k的高8位和低2位是一样的。

这里详细说明一下解题过程

初始的尝试

在DSA中有

$$
s \equiv k^{-1}(h + dr) \mod q
$$

$$
\therefore k \equiv s^{-1}h + s^{-1}dr \mod q
$$

$$
令A = s^{-1}r,B = s^{-1}h
$$

$$
\therefore k_i \equiv A_id + B_i \mod q
$$

于是
$$
k_i = A_id + B_i +t_iq
$$
这里我们把$k_i$写成高位和低位的形式
$$
k_{ihigh} + k_{unknown}+ k_{ilow} = A_id + B_i + t_iq
$$

$$
k_{unknown} = A_id + B_i + t_iq - tmp
$$

$$
tmp = k_{high} + k_{low}
$$

于是可以构造这样的格

这样的格，只能规约出152bit的值，这也是为什么要把$k_i$写成高位加低位的形式，就可以把规约$k_i$变成规约更小的$k_{unknown}$。但是此时目标向量还是存在d(160bit)这个相对偏大的值。所以我们接下来转变思路，就不规约d，具体做法是通过两组等式把d消去，可以参考:春哥的博客。

解法

对于本题来说我们把$k$写成$k_{hgih}2^{152}+k_{unknown}2^{2} + k_{low}$

因为有
$$
s_ik_i \equiv h_i + dr_i \mod q
$$
此时为了消去d，我们用另外一组数据
$$
s_jk_j \equiv h_j + dr_j \mod q
$$
上式乘$r_j$，下式乘$r_i$
$$
r_js_ik_i \equiv h_ir_j + dr_ir_j \mod q
$$

$$
r_is_jk_j \equiv h_jr_i + dr_ir_j \mod q
$$

然后作差消去d，得到
$$
r_js_ik_i - r_is_jk_j \equiv h_ir_j - h_jr_i \mod q
$$
把已知量加个括号，并且把j设为0，简化等式
$$
(r_0s_i)k_i - (r_is_0)k_0 \equiv (h_ir_0-h_0r_i) \mod q
$$
把k的形式，代入进去得到

我们是要求$k_{iunknown}$，所以为了把$k_{iunknwon}$的系数变成1，我们乘上$(4r_0s_i)^{-1}$。这步没看春哥博客是打死我都想不到

记$A_i \equiv (4r_is_0)(4r_0s_i)^{-1} \mod q$

$B_i \equiv (r_0h_i-r_ih_0+r_is_0(k_{0high}2^{152}+k_{0low})+r_0s_i(k_{ihigh}2^{152}+k_{ilow}))(4r_0s_i)^{-1} \mod q$

于是
$$
k_{iunknown} -A_ik_{0unknown} \equiv B_i \mod q
$$
所以有
$$
k_{iunknown} = A_ik_{0unknwon} + B_i + t_iq
$$
构造格

这里K是$2^{150}$，有个小细节，$k_{unknown}$乘的不一定是4，而是根据low的值来确定的。

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
from random import choices
from hashlib import sha1
from Crypto.Util.number import *
import string
from pwn import *
from sage.all import *
from tqdm import *
import gmpy2
import time

table = string.ascii_lowercase

host = '121.37.182.7'                  #ip地址
port =  10089                              #端口

sh = remote(host,port)                  #建立连接  
sh.recvuntil(b"your pubKey:")

pub = eval(sh.recvline().decode().strip())

p,q,g,y = pub

R = []
S = []
H = []
for i in range(19):
    sh.recvuntil(b">")
    sh.sendline(b"1")
    sh.recvuntil(b"Which message to sign?: ")
    m = "".join(choices(table,k=16))
    msg = m.encode()
    h = bytes_to_long(sha1(msg).digest())
    sh.sendline(msg)
    sh.recvuntil(b"Signature:")
    data1 = eval(sh.recvline().decode().strip())
    r,s = data1
    S.append(s)
    R.append(r)
    H.append(h)


n = len(S)
r0 = R[0]
s0 = S[0]
h0 = H[0]

def sign(pubkey, x, msg, k):
    p, q, g, y = pubkey
    r = pow(g, k, p) % q
    Hm = int(sha1(msg).hexdigest(), 16)
    s = (Hm + x * r) * inverse(k, q) % q
    return (r, s)

for high in trange(256):
    for low in range(4):
        lowbit = low.bit_length()
        A = []
        B = []
        tt = 2**lowbit
        for i in range(1,len(R)):
            a = tt*R[i]*s0 * gmpy2.invert(tt*r0*S[i],q) % q
            b = (r0*H[i] - R[i]*h0 + R[i]*s0*(high*2**152+low) - r0*S[i]*(high*2**152+low)) * gmpy2.invert(tt*r0*S[i],q) % q
            A.append(a)
            B.append(b)
        
        n = len(A)
        Ge = Matrix(ZZ,n+2,n+2)
        for i in range(n):
            Ge[i,i] = q
            Ge[-2,i] = A[i]
            Ge[-1,i] = B[i]
            
        K = 2**150
        Ge[-2,-2] = 1
        Ge[-1,-1] = K
        for line in Ge.BKZ(block_size=30):
            if abs(line[-1]) == K:
                k0_unknown = line[-2]
                k0 = high*2**152 + k0_unknown*tt + low
                d = (k0 * s0 - h0) * gmpy2.invert(r0,q) % q
                if pow(g,d,p) == y:
                    print(1)
                    sig = sign(pub,d,b"get flag",k0)
                    r,s = sig
                    sh.recvuntil(b">")
                    sh.sendline(b"2")
                    sh.recvuntil(b"Which message to verify?: ")
                    sh.sendline(b"get flag")
                    sh.sendlineafter(b"r:",str(r).encode())
                    sh.sendlineafter(b"s:",str(s).encode())
                    print(sh.recvline())

# RCTF{Ev3ry_fighter_h@s_their_signature_style}

Hello,XCTF!

task.py

1
2
3
4
5
6
7
from Crypto.Util.number import bytes_to_long as b2l, isPrime

p, hello = int(input("p = ")), input("hello = ")
assert p.bit_length() == 100 and isPrime(p)
assert b2l(f"{hello}$".encode()) % p == b2l(b"hello")
assert len(hello) == 64 and all(x.upper() in "XCTF" for x in hello)
print(f'Hello XCTFer! Take your spoils: {open("flag.txt", "r").read()}')

相当于求解
$$
c \equiv 448378203247 \mod p
$$
题目的意思相当于告诉我们hello是由X,C,T,F,x,c,t,f组成的长度为64的字符串，而且以$结尾，求解这个同余式

用鸡块师傅ezmod系列的思路

我们可以写成
$$
c \equiv m_0256^{64} + m_1256^{63} + … + m_{63}256^1 +36 \mod p
$$
36是ord('$')

接下来的想法就是构造格

接下来的问题在于，这个格的只能规约出很小的值，想要把$m_i$的ASCII码直接构造出来是不现实的。于是就要利用合适的值对字符进行代替。

选取点X(88),f(102）,t(116)来求a,b使得
$$
a\times 88 + b \equiv -1 \mod p
$$

$$
a\times 102 + b \equiv 0 \mod p
$$

$$
a\times 116 +b\equiv 1 \mod p
$$

$am_i + b \equiv x_i \mod p$

$m_i \equiv a^{-1}(x_i - b)$

这个时候，对于求解
$$
c \equiv m_0256^{64} +m_1256^{63} + …+ m_{63}256^1 + 36 \mod p
$$

即
$$
c \equiv (a^{-1}(x_0-b))256^{64} + (a^{-1}(x_1-b))256^{63} + … + (a^{-1}(x_{63}-b))256^1 + 36
$$

先对c减去36,有
$$
c - 36 \equiv (a^{-1}(x_0-b))256^{64} + (a^{-1}(x_1-b))256^{63} + … + (a^{-1}(x_{63}-b))256^1 \mod p
$$
乘上a，有
$$
(c-36)a \equiv (x_0-b)256^{64} + (x_1-b)256^{63} +…+(x_{63}-b)256^1 \mod p
$$
再依次加上$b_i\times 256^{64-i}$
$$
(c-36)a + \sum_{i=0}^{63}b_i\times 256^{64-i} \equiv x_0256^{64} + x_1256^{63} + … + x_{63}256^1 \mod p
$$
把左边这个当成一个大的C

构造格

然后$x_i \in {0,-1,1}$，由此把目标向量降到很小

exp.sage

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

for _ in trange(100000):
    p = getPrime(100)
    
    c = bytes_to_long(b"hello")
    
    lenth = 64
    c = (c - 36) % p
    for i in range(64):
        c -= 102 * 256^(64-i)
        c %= p
    
    Ge = Matrix(ZZ,lenth+2,lenth+2)
    T = 2**100
    for i in range(lenth):
        Ge[i,i] = 1
        Ge[i,-1] = 14 * 256**(lenth - i)

    Ge[-2,-2] = 1
    Ge[-2,-1] = -c
    Ge[-1,-1] = p
    Ge[:,-1:] *= T

    for line in Ge.BKZ(block_size=30):
        tm = b""
        if line[-1] == 0:
            for i in line[:-2]:
                if i == -1:
                    tm += b"X"
                if i == 0:
                    tm += b"f"
                if i == 1:
                    tm += b"t"
        if len(tm) == 64:
            print(tm.decode())
            print(p)
            sh = remote("121.37.167.239",10089)
            sh.sendlineafter(b"p = ",str(p).encode())
            sh.sendlineafter(b"hello = ",tm)
            print(sh.recvall())

在具体实现的过程中会发现，在尝试3个小时LLL算法的爆破之后，发现LLL不够精确，规约的结果会出现除了0,-1,1之外的数

然后再采取BKZ算法，发现T取值过大，会导致BKZ算法很慢，进行降低之后，BKZ算法也很快，最后为了精确高一点，选择了block_size=30

得到的结果，可能出现f,X相反的情况。于是我多试了几组

或者把数据打印出来手动连靶机

D^3——复现

参考文章：RCTF2024 Crypto-CSDN博客

main.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Util.number import isPrime, getRandomNBitInteger, GCD
from hashlib import sha256
from D3 import arbiter

e = 3
P_SIZE = 1024
DIFFICULTY = 8

is_lucky_prime = (
    lambda num: isPrime(num)
    and num.bit_length() == P_SIZE
    and bin(int.from_bytes(sha256(str(num).encode()).digest(), "big")).endswith(
        "0" * DIFFICULTY
    )
    and GCD(num - 1, e) == 1
)
is_lucky_modulus = lambda p, q: p != q and is_lucky_prime(p) and is_lucky_prime(q)


def task():
    print("[RCTF2024] Give me a lucky modulus to break me! 🤯")
    p, q = [int(input(f"{num} ({P_SIZE}-bit lucky prime): ")) for num in "pq"]
    if is_lucky_modulus(p, q):
        output = arbiter(msg=getRandomNBitInteger(1997), e=e, p=p, q=q)
        print(f"[ARBITER OUTPUT] {output}")
    else:
        print("[RCTF2024] DO NOT TRICK ME! 🤬")


if __name__ == "__main__":
    task()

main函数要求我们输入两个符合is_lucky_prime的素数。

D^3.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from math import lcm
from datetime import datetime
import random


def rctf_pow(base, exp, modulus):
    rctf = datetime(2024, 5, 25)
    rctf_exp = int((rctf.year * "1")[::2] + bin(rctf.day // rctf.month)[2:], base=2)
    return pow(base, rctf_exp, modulus)


RSA_encrypt = pow


def RSA_decrypt(c, e, p, q):
    work_state = random.choices(
        population=["Functional-State", "Garbled-State-1", "Garbled-State-2"],
        weights=[19, 9, 7],
        k=1,
    )[0]
    d = None
    match work_state:
        case "Functional-State":
            φ = (p - 1) * (q - 1)
            d = pow(e, -1, φ) + 2024 * φ
        case "Garbled-State-1":
            φ = (p - 1) * (q - 1)
            d = rctf_pow(e, -1, φ)
        case "Garbled-State-2":
            φ = lcm(p - 1, q - 1)
            d = rctf_pow(e, -1, φ)
    m = pow(c, d, p * q)
    return m, d


def arbiter(msg, e, p, q):
    c = RSA_encrypt(msg, e, p * q)
    while True:
        ms, ds = zip(
            *[RSA_decrypt(c, e, p, q) for chip in ["chip-1", "chip-2", "chip-3"]]
        )
        if len(set(ms + (msg,))) == 1:
            Δ = len(set(ds)) - 1
            match Δ:
                case 0:
                    return "😄 My arbiter works perfectly!"
                case 1:
                    return "😅 Something doesn't look right..."
                case 2:
                    return f'🚨 Error detected! Take your spoils: {open("flag.txt", "r").read()}'

case “Functional-State”

$$
ed \equiv ee^{-1} + 2024e\phi(n) \equiv 1 \mod \phi(n)
$$

这个情况和普通的情况没区别，最后返回的$m \equiv m^{ed} \equiv m \mod n$

case “Garbled-State-1”

rctf-pow()这个函数，指数是固定的。所以$d \equiv e^{exp} \mod (p-1)(q-1)$
$$
\therefore ed \equiv e^{exp+1} \mod \phi(n)
$$
返回的$m \equiv m^{ed} \equiv m^{e^{exp+1} \mod (p-1)(q-1)} \mod n$

case “Garbled-State-2”

最后返回的$m \equiv m^{ed}\equiv m^{e^{exp+1} \mod lcm(p-1.q-1)} \mod n$

arbiter(msg,e,p,q)函数就是对上面3种情况进行解密，要求成功恢复m，而且3个d要不同。

思路就是让p,q同时满足下面两个式子
$$
m^{e^{exp +1} \mod (p-1)(q-1)} \mod n = m
$$

$$
m^{e^{exp+1}\mod lcm(p-1,q-1)} \mod n = m
$$

即$e^{exp + 1} \equiv 1 \mod (p-1)(q-1)$，$e^{exp + 1} \equiv 1 \mod lcm(p-1,q-1)$

很显然，满足$e^{exp + 1}\equiv 1 \mod lcm(p-1,q-1)$就能满足$e^{exp + 1}\equiv 1 \mod (p-1)(q-1)$

所以要让$\lambda(lcm(p-1,q-1)) | exp + 1$，简单来说就是要让$exp + 1$是$\lambda(lcm(p-1,q-1))$的倍数，$\lambda$是Carmichael函数。

根据Carmichael函数的性质

等价于$lcm(\lambda(p-1),\lambda(q-1)) | exp + 1$

就是说，$exp + 1$即是$\lambda(p-1)$的倍数，也是$\lambda(q-1)$的倍数

则$exp + 1$中某些因子乘起来，就刚好等于$\lambda(p-1)$。然后用$\lambda(p-1)$求p。同理求q

问题就是怎么通过$\lambda(p-1)$构造出p,我们要想着如何方便构造出p

我们假设$p-1 = q_1q_2…q_k$，$q_i$是一些素数并且不重复

然后我们假设$exp + 1$的因子为$r_1,r_2,…,r_k$

我们想办法让$q_i$是若干个$r_i$相乘再加上1生成的

即$q_i = prod(r_1…r_i) + 1$(这样做的目的是为了方便计算lambda(p-1))

由这样的$q$相乘得到p-1,这个时候计算$\lambda(p-1) = \lambda(q_1q_2…q_k) = r_1r_2…r_k$

所以我们解题思路是，先通过$exp + 1$的因子，构造出一些素数，再通过这些素数来构造p，最后从中筛选出满足题目要求的p

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

rctf = datetime(2024, 5, 25)
rctf_exp = int((rctf.year * "1")[::2] + bin(rctf.day // rctf.month)[2:], base=2)

factors = [2,7,9,79,2731,4057,8191,121369,22366891,6740339310641,10030854869257,4929910764223610387,4966300248405749059,18526238646011086732742614043,3340762283952395329506327023033,167510000247425697384594847173622455701743569339841261429683667,8342680841093063014359532631803433656669591074421858694040109486076573471951766107416262860801]
C = []

for factor in powerset(factors):            # 遍历factors的所有子集,并构造出素数
    tmp = prod(factor) + 1
    if isPrime(tmp):
        C.append(tmp)

C.remove(2)                 # p-1中肯定存在2,后面手动乘上
C.remove(3)                 # 因为e=3,所以3不能作为p-1的因子

e = 3
P_SIZE = 1024
DIFFICULTY = 8
is_lucky_prime = (
    lambda num: isPrime(num)
    and num.bit_length() == P_SIZE
    and bin(int.from_bytes(sha256(str(num).encode()).digest(), "big")).endswith(
        "0" * DIFFICULTY
    )
    and GCD(num - 1, e) == 1
)
is_lucky_modulus = lambda p, q: p != q and is_lucky_prime(p) and is_lucky_prime(q)

dit = {}
# 把bit长度和值生成字典
for i in C:
    length = i.bit_length()
    if length in dit:
        dit[length].append(i)
    else:
        dit[length] = [i]

# 构造p,此时C的长度为581,如果遍历子集的话,时间复杂度太大了
while 1:
    tmp = random.choices(C,k=random.randint(2,5))
    temp = prod(tmp)
    if temp.bit_length() > 1024:
        # 当选取的数乘起来之后大于1024bit,就pass
        continue
    else:
        # 当选取的数没有大于1024bit,就计算一下他距离1024bit还差多少bit,再去早先生成的字典中挑选数字乘起来
        low,high = 1023 - temp.bit_length(),1024 - temp.bit_length()
        for i in range(low,high+1):
            if i in dit:
                for j in dit[i]:
                    tmp_p = temp * j
                    if is_lucky_prime(2*tmp_p+1):
                        print(2*tmp_p + 1)
                        # 99808733088025423735367302913919292332624879209823241096619951264779076314964508835382045490246656610115067062557039427933624133821803288246286260920164944849827667604002103449618302400641472985028015368226504096003539734000631401462750252105434060533132952016920438671638495976301219646029181876625593322127
                        # 114646006656292125053497251928052801989078712930560926674637900674113781713082625129537371564947821100314415002579529546508986694345674458070114377067046140570051545959713138126325448574083897520071340448482058241549915092716033746022683111606180586173817261455283926003513270503834002559099878337322020800199

RCTF{___Euler's_phi_where_secrets_twirl___Numbers_dance_in_cyclic_groups_swirl___}

得到的p,q不一定能让3个d不同，多试几组。

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