CRYPTO2021

字数统计: 13k字   |   阅读时长≈ 68分

最近打的CTF比赛有一点多，需要好好复盘，记录一下crypto方面的题解。这篇博客简要复盘一下2021 ByteCTF初赛，2021 KQCTF，2021 L3HCTF，2021 陇原杯， 2021 西湖论剑以及2021 N1CTF密码学方向的题解。原题存档于github仓库。

 

2021 Byte CTF crypto题解

字节的比赛赛题质量还是很高的。官方writeup。

 

JustDecrypt

第一次接触到CFB模式的一个oracle，一般来说CFB和移位寄存器的长度有关。详情可以参考wiki：分组加密的模式或者这篇博客。

image-20211122164619577

本质上就是反复加密前一次的密文，生成用来异或的比特流，选取s位作为密钥流加密明文。那么b和s就是CFB最重要的两个参数。

这题中使用了python的Crypto库默认的CFB模式，所以我直接去找了Crypto库的C语言源码，确定了python中的CFB模式的加密移位寄存器的参数b和s是16和1byte，相当于字节流密钥。这意味着它的加密模式是这样的：（这是我用python经过ecb和cfb模式加密简单试出来的）

1
2
3
4
5
6
7
8
iv=b"0"*16 
plaintext=b"0"*16+b"1"
xor_key =aes.encrypt(iv)
# 第一个字节异或的比特流是：xor_key[0]
iv=iv[1:]+ xor_key[0]^plaintext[0]
xor_key =aes.encrypt(iv)
# 第一个字节异或的比特流是：xor_key[0]
# 后面类推

每进行一个byte加密之后iv都会更新。所以这个oracle每进行一次解密的返回，我们只可以设置对应位置1byte的值。

利用如下：

我们先把寄存器里面的iv设置为已知的，直接通过填充16个字节“0”即可，为了防止padding解出来出错，所以将padding设置到320个byte，这样可以正确回显。

那么padding_res[-1]^ord(‘0’)结果就是iv加密后的密钥流，再异或一个b”H”就能使得我们解密出来的该位置的byte为“H”，其实更简便的一种方法是我们将padding改为“H”*320，直接将得到明文返回，第一个字节就会变成”H“。下面是第设置第一个字节的代码：

1
2
3
4
5
target_msg=b"Hello, I'm a Bytedancer. Please give me the flag!"+b'0'*15
padding=b'0'*320
padding_res=one_exchange(io,padding)
print(padding_res)
payload=bytes([padding_res[-1]^ord('0')^ord('H')])+target_msg[1:]+padding

我在本地测试CFB模式的代码如下：

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
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor

BLOCK_SIZE=16

class AES_CFB(object):
    def __init__(self):
        self.key = b"qwertyuiop123456"
        self.iv = b'0'*16
        self.aes_encrypt = AES.new(self.key, AES.MODE_CFB, self.iv)
        self.aes_decrypt = AES.new(self.key, AES.MODE_CFB, self.iv)

    def encrypt(self, plain):
        return self.aes_encrypt.encrypt(self.pad(plain))

    def decrypt(self, cipher):
        return self.aes_decrypt.decrypt(cipher)

    @staticmethod
    def pad(s):
        num = BLOCK_SIZE - (len(s) % BLOCK_SIZE)
        return s + bytes([num] * num)

    @staticmethod
    def unpad(s):
        return s[:-s[-1]]
def pad(s):
    num = BLOCK_SIZE - (len(s) % BLOCK_SIZE)
    return s + bytes([num] * num)  
key = b"qwertyuiop123456"
iv = b'0'*16
aes_ecb=AES.new(key,AES.MODE_ECB)
aes_cfb=AES_CFB()

target_msg=b"Hello, I'm a Bytedancer. Please give me the flag!"
print(aes_cfb.decrypt(b'0'*16+target_msg))
paddings=bytearray(b'0'*16+target_msg+b'0'*16)
for i in range(len(target_msg)):
    res=aes_cfb.decrypt(paddings)
    print(res)
    paddings[16+i]=res[16+i]

实际交互我们还有考虑最后的unpadding的时候正确，最终的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
from pwn import *
from Crypto.Util.strxor import strxor
from hashlib import sha256
from itertools import product
import os

context.log_level="debug"

def set_connect_proof():
    io=remote('39.105.115.244', 30001)
    io.recvuntil(b'sha256(XXXX+')
    alphabet = string.ascii_letters + string.digits
    lattar_part=io.recv(32-4).decode('utf8')
    io.recvuntil(b'== ')
    h=io.recvline().strip().decode('utf8')
    # print(h)
    bruteforce=[''.join(prefix) + lattar_part for prefix in product(alphabet,repeat=4)]
    for proof in bruteforce:
        if sha256(proof.encode()).hexdigest()==h:
            io.sendline(proof[:4].encode())
            break
    print("proof done")
    return io

def one_exchange(io,msg):
    io.recvuntil(b'cipher in hex > ')
    print("send",bytes(msg.hex(),encoding='utf8'))
    io.sendline(bytes(msg.hex(),encoding='utf8'))
    io.recvuntil(b'Your plaintext in hex:')
    io.recvline()
    plaintext=io.recvline().decode('utf8').strip()
    return bytes.fromhex(plaintext)
    
io=set_connect_proof()

target_msg=b"Hello, I'm a Bytedancer. Please give me the flag!"+b'0'*15
padding=b'0'*320
padding_res=one_exchange(io,padding)
print(padding_res)
payload=bytes([padding_res[-1]^ord('0')^ord('H')])+target_msg[1:]+padding
payload=bytearray(payload)

for i in range(len(target_msg)-15):
    res=one_exchange(io,payload)
    print(res)
    if(i!=len(target_msg)-16):
        payload[i+1]=res[i+1]

# correct padding
# last=b'g!'+b'0'*14
payload[63]=res[63]^ord('0')^15
res=one_exchange(io,payload[:64])
print(res)
io.interactive()

 

easyxor

经典的移位异或加掩码，这种加密我最先接触是在MT19937伪随机数生成器里面，我们每次可以恢复出固定的比特，这里有讲具体怎么逆。

我们观察到key的空间很小，只有2^20，我们可以直接通过爆破得到key，但是我们不知道明文和IV怎么确定哪个是正确的key呢？注意到CBC模式，每次异或的密钥流就是前面一个分组的密文，而且我们已知最后一个分组的padding的模式和flag以}结尾。这样我们就可以用这个特征进行爆破了。

另外一个IV的获取方式是通过已知明文攻击，在获取key之后，再通过提示flag以ByteCTF{开头，我们就可以得到iv，之后就只剩下解密了：

脚本如下：

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
152
153
154
155
156
157
158
159
160
from random import randint, getrandbits
from Crypto.Util.number import bytes_to_long, long_to_bytes
import os
from string import printable
from tqdm import tqdm

cipher='89b8aca257ee2748f030e7f6599cbe0cbb5db25db6d3990d3b752eda9689e30fa2b03ee748e0da3c989da2bba657b912'

def inverse_left_values(res,shift,mask,bits=64):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp << shift & mask
    return tmp

# right shift with mask inverse
def inverse_right_values(res,shift,mask,bits=64):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp>>shift & mask
    return tmp

def convert(m, key):
    c_list = [0x37386180af9ae39e, 0xaf754e29895ee11a, 0x85e1a429a2b7030c, 0x964c5a89f6d3ae8c]
    for t in range(4):
        m = shift(m, key[t], c_list[t])
    return m

def shift(m, k, c):
    if k < 0:
        return m ^ m >> (-k) & c
    return m ^ m << k & c

def reverse_shift(m,k,c):
    if k<0:
        return inverse_right_values(m,-k,c)
    else:
        return inverse_left_values(m,k,c)

def reverse_convert(c,key):
    c_list = [0x37386180af9ae39e, 0xaf754e29895ee11a, 0x85e1a429a2b7030c, 0x964c5a89f6d3ae8c]
    for t in range(4):
        c = reverse_shift(c, key[3-t], c_list[3-t])
    return c

cipher1=cipher[:len(cipher)//2]
cipher2=cipher[len(cipher)//2:]

k = [randint(-32, 32) for _ in range(4)]
iv = getrandbits(64)
mask=getrandbits(64)

def encrypt(m, k, iv, mode='CBC'):
    assert len(m) % 8 == 0
    num = len(m) // 8
    groups = []
    for i in range(num):
        groups.append(bytes_to_long(m[i * 8: (i + 1) * 8]))
    last = iv
    cipher = []
    if mode == 'CBC':
        for eve in groups:
            cur = eve ^ last
            cur_c = convert(cur, k)
            cipher.append(cur_c)
            last = cur_c
    elif mode == 'OFB':
        for eve in groups:
            cur_c = convert(last, k)
            cipher.append(cur_c ^ eve)
            last = cur_c
    else:
        print ('Not supported now!')
    return ''.join([hex(eve)[2:].strip('L').rjust(16, '0') for eve in cipher])

def decrypt_CBC_block(key,iv,cipher):
    num = len(cipher) // 16
    groups = []
    msg=[0]*num
    for i in range(num):
        groups.append(int(cipher[16*i:16*(i+1)],16))
    print(groups)
    for i in range(num-1,-1,-1):
        cur_c=reverse_convert(groups[i],key)
        if i !=0:
            cur_c=cur_c^groups[i-1]
        else:
            cur_c=cur_c^iv
        msg[i]=cur_c
    res=b''
    for i in msg:
        res+=long_to_bytes(i,8)
    return res

def decrypt_OFB_block(key,iv,cipher):
    num = len(cipher) // 16
    groups = []
    msg=[0]*num
    for i in range(num):
        groups.append(int(cipher[16*i:16*(i+1)],16))
    print(groups)
    last= iv
    for i in range(num):
        cur_c = convert(last, key)
        msg[i]=cur_c ^groups[i]
        last = cur_c
    res=b''
    for i in msg:
        res+=long_to_bytes(i,8)
    return res
    
def brute_forcekey(cipher_of_CBC):
    brute_list=[]
    for i in range(-32,33):
        if i==0:
            continue
        for j in range(-32,33):
            if j == 0:
                continue
            for k in range(-32,33):
                if k==0:
                    continue
                for l in range(-32,33):
                    if l==0:
                        continue
                    brute_list.append([i,j,k,l])
    pre_last=int(cipher_of_CBC[-32:-16],16)
    last=int(cipher_of_CBC[-16:],16)
    keys=[]
    for key in tqdm(brute_list):
        # print(key)
        cur_c=reverse_convert(last,key)
        cur_c=cur_c^pre_last
        m=long_to_bytes(cur_c)
        # print(type(m[0]))
        if  (m[-1]==ord('}') or m[-1]==ord('$')) and all(i>=32 and i<=126 for i in m):
            print("FIND")
            print("msg is ", m)
            print("key is ", key)
            keys.append((m,key))
    for key in keys:
        m=key[0]
        i=1
        while m[-i]==m[-i-1]:
            i=i+1
        if m[-i-1]==ord('}'):
            print(key)
    return key

def get_iv(key):
    begin=bytes_to_long(b'ByteCTF{')
    c=int(cipher1[:16],16)
    return reverse_convert(c^begin,key)

# brute_forcekey(cipher2)
msg=b'5u2t}$$$'
key=[-12, 26, -3, -31]
iv= get_iv(key)
flag=decrypt_OFB_block(key,iv,cipher1)+decrypt_CBC_block(key,iv,cipher2)
# 'ByteCTF{5831a241s-f30980q535af-2156547475u2t}$$$
print(flag)

 

overhead

典型的DH密钥交换，我们可以得到Alice，Bob的公钥，并且我们有一个oracle，可以用Bob的私钥加密消息，并且泄露加密后的高p.bitlength() - 64位（MSB）。不妨记为 k = p.bitlength() - 64位 （注意不是精确的位数）

注意到下面的等式，r是我们任意生成的随机数

1
pow((pow(g, r, p) * Alice) % p, b, p) == (pow(Bob, r, p) * secret) % p

这样我们可以提交pow(g, r, p) * Alice) % p，oracle会计算上面的式子，并且返回给我们右边的高p.bitlength() - 64位，只有secret是未知的，这是一个典型的Hidden Number Problem （HNP）问题。关于HNP问题，一般可以构造格，进行格基规约，再使用Babai算法求解CVP问题。

关于HNP问题的详细解法，这里给几篇不错的参考和论文：

HNP的解法简单来说就是构造下面(d+1)*(d+1)的矩阵：

1
2
3
4
5
6
# HNP问题 alpha* t = u mod p， 给定t，oracle输出u的MSB，求alpha
[  p,  0, ... ,  0,   0 ]
[  0,  p, ... ,  0,   0 ]
[         ...           ]
[  0,  0, ... ,  p,   0 ]
[ t1, t2, ... , td, 1/p ]

其中t就是每次随机生成的输入，那么在上述矩阵的列向量张成的格内，求解Closest Vector Problem （CVP）问题，对于oracle返回的d组MSB的值U=（u1，u2，… ，ud），我们求解U离上面的格的最短向量，有极大概率使得这个最短向量就是：

1
closest_vector=(aplha*t1,alpha*t2,...,alpha*td,alpha/p)

那么closest_vector[-1]*p就是我们需要求解的alpha。

参考上面第二个链接的解法，这里给出一个本地的跑的脚本，验证解法。

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
# sage
from Crypto.Util.number import *
import sympy
from random import randint

c = 21572244511100216966799370397791432119463715616349800194229377843045443048821
p = 62606792596600834911820789765744078048692259104005438531455193685836606544743
g = 5
bits=64

a = randint(1, p - 1)
Alice = pow(g, a, p)
b = randint(1, p - 1)
Bob = pow(g, b, p)
secret = pow(Alice, b, p)
print(a,b)

def to_bob(msg):
    tmp_s = pow(msg, b, p)
    leak = tmp_s >> bits
    leak = leak << bits
    return leak
    
def build_basis(oracle_inputs,d=30):
    """Returns a basis using the HNP game parameters and inputs to our oracle
    """
    basis_vectors = []
    for i in range(d):
        p_vector = [0] * (d+1)
        p_vector[i] = p
        basis_vectors.append(p_vector)
    basis_vectors.append(list(oracle_inputs) + [QQ(1)/QQ(p)])
    return Matrix(QQ, basis_vectors)

def approximate_closest_vector(basis, v):
    """Returns an approximate CVP solution using Babai's nearest plane algorithm.
    """
    BL = basis.LLL()
    G, _ = BL.gram_schmidt()
    _, n = BL.dimensions()
    small = vector(ZZ, v)
    for i in reversed(range(n)):
        c = QQ(small * G[i]) / QQ(G[i] * G[i])
        c = c.round()
        small -= BL[i] * c
    return (v - small).coefficients()

def oracle(d=30):
    t_list=[]
    u_list=[]
    for _ in range(d):
        r= randint(1,p-1)
        for_bob=(pow(g, r, p) * Alice) % p
        u=to_bob(for_bob)
        t=pow(Bob, r, p)
        t_list.append(t)
        u_list.append(u)
    return t_list,u_list

# Hidden alpha scalar
alpha = secret

# Using terminology from the paper: inputs = `t` values, answers = `a` values
inputs, answers = oracle(30)

# Build a basis using our oracle inputs
lattice = build_basis(inputs)
print("Solving CVP using lattice with basis:\n%s\n" % str(lattice))

# The non-lattice vector based on the oracle's answers
u = vector(ZZ, list(answers) + [0])
print("Vector of MSB oracle answers:\n%s\n" % str(u))

# Solve an approximate CVP to find a vector v which is likely to reveal alpha.
v = approximate_closest_vector(lattice, u)
print("Closest lattice vector:\n%s\n" % str(v))

# Confirm the recovered value of alpha matches the expected value of alpha.
recovered_alpha = (v[-1] * p) % p

print("Recovered alpha! Alpha is %d" % recovered_alpha)
print("Secret is ",alpha)
assert recovered_alpha == alpha

最后提一嘴，这是今年USENIX上面的一篇论文提到的攻击：

https://www.usenix.org/system/files/sec21summer_merget.pdf

另外一种解法是参考Nu1l战队的writeup，居然还可以用coppersmith来解，这是原writeup：

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 pwn import remote
from pwnlib.tubes.tube import *
from hashlib import sha256
from Crypto.Util.number import *
from tqdm import tqdm
from sage.modules.free_module_integer import IntegerLattice
import itertools
r = remote('39.105.38.192', '30000')
load("coppersmith.sage")
p = 62606792596600834911820789765744078048692259104005438531455193685836606544743
g = 5
P.<x, y> = PolynomialRing(Zmod(p))
r.sendlineafter('$ ', '1')
Alice = int(r.recvline().decode())
r.sendlineafter('$ ', '2')
Bob = int(r.recvline().decode())
r.sendlineafter('$ ', '3')
r.sendlineafter('To Bob: ', str(Alice**2))
s2 = int(r.recvline().decode())
r.sendlineafter('$ ', '3')
r.sendlineafter('To Bob: ', str(Alice))
s1 = int(r.recvline().decode())
f = (s1+x)^2 - s2 - y
res = small_roots(f, bounds=(2**64, 2**64), m=4)
r.sendlineafter('$ ', '4')
r.sendlineafter('secret: ', str(s1+res[0][0]))
r.interactive()

其中coppersmith.sage可以在这个repo找到，不直接使用sage自带的small_roots方法是因为sage目前还不支持多元多项式。

上面脚本的思想就是：

1
2
发送 Alice 公钥 ---> 返回 pow(Alice,b,p)=secret 的高k位MSB s1
发送 Alice**2 ---> 返回 pow(Alice**2,b,p)=secret**2 的高k位MSB s2

有如下等式成立，其中x和y分别是secret和secret^2的低六十四位：

(s1+x)^2 - s2 - y == 0

那么我们可以考虑coppersmith算法：

对于一个有限域n上面 e 阶的多项式 f,：

  • 在模 n 意义下，快速求出 $n^{1/e}$ 以内的根
  • 给定 β，快速求出模某个 b 意义下较小的根，其中 b≥nβ，是 n 的因数。

这里我们的指数e=2，p有512比特，而根的范围在2**64以内，显然这题满足coppersmith的条件。

当然这题还有第三种解法，这里就不写了，恰好byte决赛也出现了，可以看看。

 

abusedkey

协议分析题，我ECC基础太差了，没写出来。（主要是对sage的库不太清楚）

这里放个MoMoMo的writeup：

  • 首先按照协议2流程执行协议2，拿到hint。
  • 接下来在协议2下爆破ds，爆破方式为先劫持msg23传输过程，把Qc | |Qs替换为Qc | | Rc，此时服务器端计算Yc= rt hcN(-1)^ hc Rc = rt Rc, Ys = rt hs(-1) Rc = hs(-1)Yc，在msg24中我们收到了Yc和Ys，因此可以穷举r(s)来计算ds，然后根据Ys和hsN(-1)*Yc是否相同来判断爆破出的ds是否正确。
  • 最后回到协议1，可以直接进行流氓密钥攻击，我们劫持msg13传输过程，将sid1 || Tc替换为sid1 || Pc，此时服务器端计算Kcs =(-ds - ts) Pc + ts Pc =-ds * Pc，其中ds和Pc此时均已知，我们可以直接在本地计算出Kcs，按照协议1流程生成共享密钥，解密msg14过程中收到的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
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
#!/usr/bin/env sage
import requests
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
E = EllipticCurve(GF(p), [a, b])
G = E(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
Pc = E(0xb5b1b07d251b299844d968be56284ef32dffd0baa6a0353baf10c90298dfd117,
0xea62978d102a76c3d6747e283091ac5f2b4c3ba5fc7a906fe023ee3bc61b50fe)
URL = "http://39.105.181.182:30000/"
call_msg11 = "/abusedkey/server/msg11"
call_msg13 = "/abusedkey/server/msg13"
call_msg21 = "/abusedkey/server/msg21"
call_msg23 = "/abusedkey/ttp/msg23"
call_msg25 = "/abusedkey/server/msg25"
msg21 = sid2 = os.urandom(32).hex()
msg22 = Qs_hex = requests.get(URL + call_msg21, data = msg21).text
Qs = E(bytes_to_long(bytes.fromhex(Qs_hex)[:32]),
bytes_to_long(bytes.fromhex(Qs_hex)[32:]))
rc = randint(1, p)
Rc = rc * G
hc = int(sha256(bytes.fromhex("ffff")).hexdigest(), 16)
Qc = hc * Rc
Qc_hex = hex(Qc[0])[2:].zfill(64) + hex(Qc[1])[2:].zfill(64)
msg23 = Qc_hex + Qs_hex
msg24 = requests.get(URL + call_msg23, data = msg23).text
Yc_hex = msg24[:128]
Ys_hex = msg24[128:]
Yc = E(bytes_to_long(bytes.fromhex(Yc_hex)[:32]),
bytes_to_long(bytes.fromhex(Yc_hex)[32:]))
Ys = E(bytes_to_long(bytes.fromhex(Ys_hex)[:32]),
bytes_to_long(bytes.fromhex(Ys_hex)[32:]))
msg25 = sid2 + Yc_hex
msg26 = Chint = requests.get(URL + call_msg25, data = msg25).text
Zcs = rc * Ys
sk2 = sha256(long_to_bytes(Zcs[0])).digest()
Chint_bytes = bytes.fromhex(Chint)
iv = Chint_bytes[:12]
ct_hint = Chint_bytes[12:-16]
mac = Chint_bytes[-16:]
cipher = AES.new(key = sk2, mode = AES.MODE_GCM, nonce = iv)
hint = cipher.decrypt_and_verify(ct_hint, mac)
print(hint)
Rc_hex = hex(Rc[0])[2:].zfill(64) + hex(Rc[1])[2:].zfill(64)
msg23 = Qc_hex + Rc_hex
msg24 = requests.get(URL + call_msg23, data = msg23).text
Yc_hex = msg24[:128]
Ys_hex = msg24[128:]
Yc = E(bytes_to_long(bytes.fromhex(Yc_hex)[:32]),
bytes_to_long(bytes.fromhex(Yc_hex)[32:]))
Ys = E(bytes_to_long(bytes.fromhex(Ys_hex)[:32]),
bytes_to_long(bytes.fromhex(Ys_hex)[32:]))
o = E.order()
for i in range(65538):
 print(i)
 hs = int(sha256(bytes.fromhex(hex(i)[2:].zfill(4))).hexdigest(), 16)
 hs_inverse = inverse_mod(hs, o)
 if Ys == Yc * hs_inverse:
 print((i, hs))
 break
ds = hs
sid1 = os.urandom(32).hex()
_ = requests.get(URL + call_msg11, data = sid1).text
Tc = -Pc
Tc_hex = hex(Tc[0])[2:].zfill(64) + hex(Tc[1])[2:].zfill(64)
msg13 = sid1 + Tc_hex
msg14 = Cflag = requests.get(URL + call_msg13, data = msg13).text
Kcs = -ds * Pc
sk1 = sha256(long_to_bytes(Kcs[0])).digest()
Cflag_bytes = bytes.fromhex(Cflag)
iv = Cflag_bytes[:12]
ct_flag = Cflag_bytes[12:-16]
mac = Cflag_bytes[-16:]
cipher = AES.new(key = sk1, mode = AES.MODE_GCM, nonce = iv)
FLAG = cipher.decrypt_and_verify(ct_flag, mac)

 

2021 L3HCTF Crypto 题解

官方题解可以在这里找到：L3HCTF2021官方题解。题目存库于repo。

 

EzECDSA

这是一个HNP问题，提供了oracle，在github上面能直接找到对应的仓库：lattice-attack

可以直接利用这个代码解，只需要写交互的脚本就行。wsl2本地跑的时候发现ecdsa_lib.py报错，在118行注释即可：

1
2
3
4
5
6
7
# ret = False
   # try:
   #     publickey_obj.public_key()
   #     ret = True
   # except ValueError:
   #     pass
   ret = True
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 hashlib import *
from pwn import *

import json
import string
import itertools
import subprocess

r = remote('127.0.0.1', 23333)
data = {}
info = []

r.recvuntil(b"+")
part = r.recvuntil(b")")[:-1].decode("utf-8")
# print(part)
r.recvuntil(b"= ")
suffix = r.recvline().strip().decode("utf-8")
# print(suffix)
r.recv()
pts = itertools.product(string.printable, repeat=4)
for pt in pts:
    p = "".join(list(pt)) + part
    ct = sha256(p.encode()).hexdigest()

    if ct == suffix:
        r.send(p[:4].encode())
        break
data["curve"] = "SECP256K1"
publickey = r.recvline().decode().strip('(').strip('\n').strip(')').split(', ')
publickey = list(map(eval, publickey))
data["public_key"] = publickey
data["known_type"] = "LSB"
data["known_bits"] = 8

for _ in range(100):
    r.recvline()
    r.send(b'hello\n')
    tmp = {}
    r_sig = int(r.recvline().decode().strip("r = ").strip('\n'))
    s_sig = int(r.recvline().decode().strip("s = ").strip('\n'))
    kp = int(r.recvline().decode().strip("kp = ").strip('\n'))
    hash = int(r.recvline().decode().strip("hash = ").strip('\n'))
    tmp["r"] = r_sig
    tmp["s"] = s_sig
    tmp["kp"] = kp
    tmp["hash"] = hash
    info.append(tmp)
data["signatures"] = info

with open("data.json", "w") as f:
    json.dump(data, f)

# r.interactive()
r.recvline()
res = subprocess.Popen('python3 exp/lattice_attack.py -f data.json', shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE, close_fds=True)
# https://github.com/bitlogik/lattice-attack
result = res.stdout.read().decode().split('\n')[:-2]
sKey = str(int(result[-1], 16)).encode()
r.sendline(sKey)
print(r.recv())

image-20211123130504880

 

p0o0w

难的在于逆向，rust逆向出来之后的符号实在太多了。

当时逆向的时候主要看了这个函数，应该是生成伪随机数的种子

image-20211123135300930

真正关于prng的函数在Magic函数中

image-20211123135427602

进入magic函数中：

image-20211123135523311

我们发现只有异或和移位运算，从这里就可以看出大概的PRNG算法了，是Xorshift类的算法，因为产生的是16字节的随机数，即Xorshift128，并且移位的参数是23,17,26。官方wp说可以分析算法，也可以直接用z3解，因为涉及的运算只有移位异或。具体来说，先用爆破的方式得到前面6个随机数，得到初始的state，之后就可以预测随机数了，一个可行的z3解法如下：

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
from pwn import *
from Crypto.Util.strxor import strxor
from hashlib import sha256
from itertools import product
import os
import string

context.log_level="debug"

import hashlib
from z3 import *
from pwn import *
import re
import string
import time
# Hack for mbruteforce on macos
# import multiprocessing
# multiprocessing.set_start_method('fork')

MASK = 0xFFFFFFFFFFFFFFFF
# context.terminal = ["tmux","split","-h"]
context.log_level = 'DEBUG'

start = b''
target_hash = ''

def hhash(end):
    end = end.encode()
    return hashlib.sha256(start+end).hexdigest() == target_hash

def solve_init(states):
    print(states)
    init_s0, init_s1 = BitVecs('init_s0 init_s1', 64)
    s0_ = init_s0
    s1_ = init_s1
    s = Solver()
    for i in states:
        s1 = s0_
        s0 = s1_
        s1 ^= (s1 << 23)
        s1 ^= LShR(s1, 17)
        s1 ^= s0
        s1 ^= LShR(s0, 26)
        s.add(s0+s1 == i)
        s0_ = s0
        s1_ = s1
    print(s.check())
    m = s.model()
    return m[init_s0].as_long(),m[init_s1].as_long()


class XorShift128():
    def __init__(self,s0,s1) -> None:
        self.s0 = s0
        self.s1 = s1
    def get(self):
        s0_ = self.s1
        s1_ = self.s0
        s1_ ^= (s1_ << 23) & MASK
        s1_ ^= (s1_ >> 17) & MASK
        s1_ ^= s0_
        s1_ ^= ( s0_>>26 ) & MASK
        self.s0 = s0_
        self.s1 = s1_
        return (self.s0 + self.s1) & MASK 

def set_connect_proof():
    # io=remote("121.36.201.164", 9999)
    io = process("./pow/p0o0w")
    io.recvuntil(b'sha256(')
    alphabet = string.ascii_letters + string.digits
    lattar_part=io.recv(13).decode('utf8')
    io.recvuntil(b'== ')
    h=io.recvline().strip().decode('utf8')
    # print(h)
    io.recvuntil(b'tell me the ? in sha256(?):')
    bruteforce=[ lattar_part + ''.join(prefix) for prefix in product(alphabet,repeat=3)]
    for proof in bruteforce:
        if sha256(proof.encode()).hexdigest()==h:
            io.sendline(proof.encode())
            break
    print("proof done")
    return io,int(proof,16)

def proof(io,i):
    io.recvuntil(b'sha256(')
    alphabet = "abcdef" + string.digits
    lattar_part=io.recv(16-i).decode('utf8')
    print("[+] lattar part",lattar_part)
    io.recvuntil(b'== ')
    h=io.recvline().strip().decode('utf8')
    print("[+] hash",h)
    io.recvuntil(b'tell me the ? in sha256(?):')
    bruteforce=[ lattar_part + ''.join(prefix) for prefix in product(alphabet,repeat=i)]
    for proof in bruteforce:
        if sha256(proof.encode()).hexdigest()==h:
            io.sendline(proof.encode())
            print("proof %d done"%i)
            return int(proof,16)

outs=[]
io,num=set_connect_proof()
outs.append(num)
for i in range(4,7):
    outs.append(proof(io,i))
s0,s1 = solve_init(outs)
print(s0,s1)
prng = XorShift128(s0,s1)
for _ in outs:
    print(prng.get(),_)
for i in  range(7,17):
    io.recvuntil(b'ell me the ? in sha256(?):').decode()
    ret = f'{prng.get():016x}'
    print(ret)
    io.sendline(ret.encode())

io.interactive()

 

2021 西湖论剑 Crypto题解

题目存库于repo：西湖论剑Crypto

 

unknownDSA

一开始看到有很多的未知变量，其中ul和vl给了下面的关系

1
ul[i]**2 - wl[i]* vl[i]**2==1

这个方程仔细研究发现是有名的佩尔方程 $x^2-n*y^2=1$

pell方程的sagemath解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def check_sat_pell(x, y, n):
    if x^2 - n * y ^ 2 == 1:
        return True
    else:
        return False


def solve_pell_equation(n, nums_of_solutions):
    # x^2 - n * y ^ 2 = 1
    nth_continue_fraction = continued_fraction(sqrt(n))
    count = 0
    i = 0
    while count < nums_of_solutions:
        temp_numerator = nth_continue_fraction.numerator(i)
        temp_denominator = nth_continue_fraction.denominator(i)
        if check_sat_pell(temp_numerator, temp_denominator, n):
            print(f"{i} th solution is ", temp_numerator, temp_denominator)
            count += 1
        i += 1

以及一个online的最小解网站，发现ul和vl就是给定的wl时的最小解。

解出来之后就是简单的DSA复用k的漏洞，可以直接通过同余方程解出。

如果在两次签名的过程中共享了 k，就可以进行攻击。假设签名的消息为 m1,m2，k相同，则两者的r值相同，此外

$s_1≡(H(m_1)+x_r)k^{−1}\ (mod\ q)$

$s_2≡(H(m_2)+x_r)k^{−1}\ (mod\ q)$

联立得到

$k(s_1−s_2)≡(H(m_1)−H(m_2))(modq)$

此时可解出 k，从而代入任意一个方程得到私钥x。

脚本如下

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

wl,cl1,cl2=[3912956711, 4013184893, 3260747771], [2852589223779928796266540600421678790889067284911682578924216186052590393595645322161563386615512475256726384365091711034449682791268994623758937752874750918200961888997082477100811025721898720783666868623498246219677221106227660895519058631965055790709130207760704, 21115849906180139656310664607458425637670520081983248258984166026222898753505008904136688820075720411004158264138659762101873588583686473388951744733936769732617279649797085152057880233721961, 301899179092185964785847705166950181255677272294377823045011205035318463496682788289651177635341894308537787449148199583490117059526971759804426977947952721266880757177055335088777693134693713345640206540670123872210178680306100865355059146219281124303460105424], [148052450029409767056623510365366602228778431569288407577131980435074529632715014971133452626021226944632282479312378667353792117133452069972334169386837227285924011187035671874758901028719505163887789382835770664218045743465222788859258272826217869877607314144, 1643631850318055151946938381389671039738824953272816402371095118047179758846703070931850238668262625444826564833452294807110544441537830199752050040697440948146092723713661125309994275256, 10949587016016795940445976198460149258144635366996455598605244743540728764635947061037779912661207322820180541114179612916018317600403816027703391110922112311910900034442340387304006761589708943814396303183085858356961537279163175384848010568152485779372842]

x1 = 10537190383977432819948602717449313819513015810464463348450662860435011008001132238851729268032889296600248226221086420035262540732157097949791756421026015741477785995033447663038515248071740991264311479066137102975721041822067496462240009190564238288281272874966280
y1 = 168450500310972930707208583777353845862723614274337696968629340838437927919365973736431467737825931894403582133125917579196621697175572833671789075169621831768398654909584273636143519940165648838850012943578686057625415421266321405275952938776845012046586285747

x2 = 121723653124334943327337351369224143389428692536182586690052931548156177466437320964701609590004825981378294358781446032392886186351422728173975231719924841105480990927174913175897972732532233
y2 = 1921455776649552079281304558665818887261070948261008212148121820969448652705855804423423681848341600084863078530401518931263150887409200101780191600802601105030806253998955929263882382004

x3 = 1440176324831562539183617425199117363244429114385437232965257039323873256269894716229817484088631407074328498896710966713912857642565350306252498754145253802734893404773499918668829576304890397994277568525506501428687843547083479356423917301477033624346211335450
y3 = 25220695816897075916217095856631009012504127590059436393692101250418226097323331193222730091563032067314889286051745468263446649323295355350101318199942950223572194027189199046045156046295274639977052585768365501640340023356756783359924935106074017605019787

vl=[x1,x2,x3]
ul=[y1,y2,y3]

def gen_pell_solu(min_solu,kthsolu,n):
    xnext=min_solu[0]*kthsolu[0]+n*min_solu[1]*kthsolu[1]
    ynext=min_solu[0]*kthsolu[1]+min_solu[1]*kthsolu[0]
    return [xnext,ynext]
    
#sage
x=crt(cl1,vl)
m1=x.nth_root(7)
y=crt(cl2,ul)
m2=y.nth_root(7)

print(long_to_bytes(m1))
print(long_to_bytes(m2))

# h1 = bytes_to_long(SHA.new(m1).digest())
# h2 = bytes_to_long(SHA.new(m2).digest())

h1=63998600246749767922010292163233985055258508821
h2=1121013631791355094793010532678158450130791457285

def gcd(a,b):
    while a!=0:
        a,b = b%a,a
    return b

def findModReverse(a,m):
    if gcd(a,m)!=1:
        return None
    u1,u2,u3 = 1,0,a
    v1,v2,v3 = 0,1,m
    while v3!=0:
        q = u3//v3
        v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
    return u1%m

pq, p_1dq, t=85198615386075607567070020969981777827671873654631200472078241980737834438897900146248840279191139156416537108399682874370629888207334506237040017838313558911275073904148451540255705818477581182866269413018263079858680221647341680762989080418039972704759003343616652475438155806858735982352930771244880990190318526933267455248913782297991685041187565140859, 106239950213206316301683907545763916336055243955706210944736472425965200103461421781804731678430116333702099777855279469137219165293725500887590280355973107580745212368937514070059991848948031718253804694621821734957604838125210951711527151265000736896607029198, 60132176395922896902518845244051065417143507550519860211077965501783315971109433544482411208238485135554065241864956361676878220342500208011089383751225437417049893725546176799417188875972677293680033005399883113531193705353404892141811493415079755456185858889801456386910892239869732805273879281094613329645326287205736614546311143635580051444446576104548
r1,s1,s2=498841194617327650445431051685964174399227739376, 376599166921876118994132185660203151983500670896, 187705159843973102963593151204361139335048329243
# r2,s3=620827881415493136309071302986914844220776856282, 674735360250004315267988424435741132047607535029
m=pq//p_1dq
q=m.nth_root(2)
# q=895513916279543445314258868563331268261201605181
p=pq//q
phi=(p-1)*(q-1)
d=inverse(p*q-p-q,phi)
g=pow(t,d,pq)

G=GF(p)
g=G(g)

# 验证g的阶性质
assert g^q == 1

r1,s1=r1,s1
r2,s2=r1,s2
k=(h1-h2)*findModReverse(s1-s2,q)%q
# t = powmod(g, p*q-(p+q), p*q)

x=findModReverse(r1,q)*(k*s1-h1)%q
print("find x1 ",x)
print(long_to_bytes(x))

r2,s3=620827881415493136309071302986914844220776856282, 674735360250004315267988424435741132047607535029

# s3 = (hm1 + x2*r2) * invert(k, q) % q
x2=inverse(r2,q)*(k*s3-h1)%q

print("find x2 ",x2)
print(long_to_bytes(x2))

 

FilterRandom

这题的writeup参考：SU战队

当时做这个题的时候概率算错了，现在重新估算一遍：

线性移位寄存器输出的比特流，有90%的概率来自lfsr1,10%的概率来自lfsr2，任意给定64比特，全部来自lfsr1的概率是：$0.9^{64}=0.00118$，但是我们有2048比特，有2048-64=1984个连续64比特串，加入它们都不是全部来自lfsr1，概率是：$(1-0.00118)^{1984}=0.096$，当然，这个算的也有问题，因为每个概率不是独立的，但是我们同时也注意到即使选中lfsr2，输出也很有可能与lfsr1相同因，此有我们姑且认为有很大概率可以找到连续的64比特串使它们全部来自lfsr1, 也有可能是出题人选择了一次符合条件的输出，降低了难度，通过爆破找到连续64个比特之后，只需要一直向前回溯，就能得到初始状态init1，这样我们就得到lfsr1的初始状态。

之后我们就考虑求解lfsr2的初始状态。可以用矩阵方程：$initA^{k-1}mask$ 得到第k个输出。已知100多比特的输出，完全可以求逆得到初始状态。那么就可列$xA=y$形式矩阵方程计算。

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
N = 64
class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**length-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output

def backtrace(state, mask):
    mask = ((mask & 0x7FFFFFFFFFFFFFFF) << 1) + 1
    i = state & mask
    output = 0
    while i != 0:
        output ^= (i & 1)
        i = i >> 1
    state >>= 1
    return (output << 63) + state


output = "10001011010100011000100101001011100010110111001100001110000111011011100101101101000111101100010111100011000011111111010101111100101010101100010100000111011010011110111000100000101100101010110100111100011000101010101011011111011011000001101001011000010000011110001111001111011100110011111111101000111101001010000110001110111101001001101011101101001010001101010010110000000000001001101100101011110011010110011010110110011001001111001010100011110111100100010110111100110010000000010010011110001100000011000001110001000000010000100100101100000011100000011110101001011010011010100001101000010100100000011001011001000110000000000111011101000110010110111110010101110010001010001111111000011010000011001110111001000010011000000111010111100000100010011001111101110110100100011111000111000011111101010010110011111100010000100101011000001010101111101111001000011101111000111000101011010111100110001011011100101001010110110110110011100100111100110001101110010100010111100000110000010110100010001100011011001100100110101110010100011101110110010000010011100000011100000101010011011111110000100000010001010111011011111110100111100011100011110110010001011101111001011101010110111001001000111001001111001111110111111100001111100100110011111110110101000011010111110010001100000111100010011100011010000101010111010101101000011001110011000000110110110001101100110101110010010111011100110101000110000011001010100000110000000001110010001010001001101111100001111111011010010011100110010000111010001001111111110000010101110011010100100101101100111000010110100110010001010110111110011000111011101110100010000110110110011001011111011111000000000000001110000001000011000110111000000110100110110001111011111100010010011100101010000111000011111010000001010010011101010010110011000000001111110000000010111011000010001111000100110101110001000011111001101111111100011111011001001110000101001101110100111010011011101000110010000001001000001100110001110101100001000110100100010111101100010100110011111010011100100001101111010000110110101111111001111011100001101100000001101111100100"
mask1=17638491756192425134
mask2=14623996511862197922
ans=[]


# 这里没有回溯的过程，减少穷举时间
for i in range(1984):
    gadget = int(output[i:i+64], 2)
    l1=lfsr(gadget,mask1,64)
    cnt=0    

    for j in range(i+64, 2048):
        if l1.next()==int(output[j]):
            cnt+=1
            
    total=1984-i
    # 输出为lfsr1概率
    ans.append((i, cnt / total))

ans.sort(key=lambda x:x[1], reverse=True)

ans2=[]
for i, each in ans:
    if each > 0.85:
        ans2.append((i,each))
    else:
        break
# 比例高于0.85的
ans2.sort(key=lambda x:x[0])
print(ans2)
idx = ans2[0][0]

# 从661到6669都是来自lfsr1的

init1 = output[idx:idx+64]
init1 = int(init1, 2)

# 回溯状态
for _ in range(idx):
    init1 = backtrace(init1, mask1)
# 得到初始值
for _ in range(64):
    init1 = backtrace(init1, mask1)

print(init1)

# 作者: Suers
# 链接: https://team-su.github.io/passages/2021-11-20-XHLJ/
# 来源: team-su.github.io

 

HardRSA

整体是一个离散对数求解以及RSA变种，叫做 Hensel lifting for Takagi’s scheme。具体可以参考Lazzzaro博客。这题RSA部分脚本也是取自上面的博客。先用sage自带的discrete_log求出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
from Crypto.Util.number import *
import gmpy2

y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
c1 = 78100131461872285613426244322737502147219485108799130975202429638042859488136933783498210914335741940761656137516033926418975363734194661031678516857040723532055448695928820624094400481464950181126638456234669814982411270985650209245687765595483738876975572521276963149542659187680075917322308512163904423297381635532771690434016589132876171283596320435623376283425228536157726781524870348614983116408815088257609788517986810622505961538812889953185684256469540369809863103948326444090715161351198229163190130903661874631020304481842715086104243998808382859633753938512915886223513449238733721777977175430329717970940440862059204518224126792822912141479260791232312544748301412636222498841676742208390622353022668320809201312724936862167350709823581870722831329406359010293121019764160016316259432749291142448874259446854582307626758650151607770478334719317941727680935243820313144829826081955539778570565232935463201135110049861204432285060029237229518297291679114165265808862862827211193711159152992427133176177796045981572758903474465179346029811563765283254777813433339892058322013228964103304946743888213068397672540863260883314665492088793554775674610994639537263588276076992907735153702002001005383321442974097626786699895993544581572457476437853778794888945238622869401634353220344790419326516836146140706852577748364903349138246106379954647002557091131475669295997196484548199507335421499556985949139162639560622973283109342746186994609598854386966520638338999059

# G=GF(y)
# g=G(2)
# c1=G(c1)
# x=discrete_log(c1,g)
# # var('y')
# # qe = (2019*y^2 + 2020*y^3 + 2021*y^4 - x==0)
# # p=solve(qe, y)
# n = p**4*q
e = 65537
dp = 379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473
c = 57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425
p=12131601165788024635030034921084070470053842112984866821070395281728468805072716002494427632757418621194662541766157553264889658892783635499016425528807741


b = 4
mp1 = pow(c, dp, p)
mp = pow(c, dp - 1, p)
for i in range(1, b - 2):
	x = pow(c - pow(mp1, e), 1, p**(i + 1))
	y = pow(x * mp * (gmpy2.invert(e, p)), 1, p**(i + 1))
	mp1 = mp1 + y
print(long_to_bytes(mp1))

 

SpecialCurve2

这道题比赛的时候没有解出来，题目自己设计了一个乘法群，其实就是复数域上面的乘法，对于复数域上面的乘法，模p意义上的阶是。对于题目中的，它的阶就是，那么只要求出e，类似RSA加密，求解出e关于这个乘法群的逆d，就可以任意解密了。关键在于这个e怎么求。理论上面详细的证明可以参考这篇知乎（另外一种基于CRT来求e的解法也可以参考这篇）。

我们取模发现它的乘方保持模长上同态的关系，即：$|k*G|=|G|^k$，而给了我们一组已知明文，求e就可以直接转换为求离散对数。但是这个离散对数怎么求很头疼，sage上面的许多dlp实现都不太行，直到看到Nu1l战队的writeup，发现了一个高效求离散对数的实现，调用sage上面gp库的离散对数，这是一个专门的数论库，sagemath集成了gp/PARI的接口。GP接口参考。

1
2
3
4
5
6
7
8
9
n = 92916331959725072239888159454032910975918656644816711315436128106147081837990823
# factor(n)
# 425886199617876462796191899 * 434321947632744071481092243 * 502327221194518528553936039
p,q,r=425886199617876462796191899 , 434321947632744071481092243 , 502327221194518528553936039
# discrete log
y =1225348982571480649501200428324593233958863708041772597837722864848672736148168^2*2%n
g = 2
e = int(pari(f"znlog({int(y)},Mod({int(g)},{int(n)}))"))
# 96564183954285580248216944343172776827819893296479821021220123492652817873253

求解脚本如下：

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 *
n=92916331959725072239888159454032910975918656644816711315436128106147081837990823

HINT=(1225348982571480649501200428324593233958863708041772597837722864848672736148168, 1225348982571480649501200428324593233958863708041772597837722864848672736148168)

C=(44449540438169324776115009805536158060439126505148790545560105884100348391877176, 73284708680726118305136396988078557189299357177640330968917927635171441710392723)

y=(HINT[0]**2+HINT[1]**2)%n
g = 2
e = int(pari(f"znlog({int(y)},Mod({int(g)},{int(n)}))"))
# factor(n)
# 425886199617876462796191899 * 434321947632744071481092243 * 502327221194518528553936039
p,q,r=425886199617876462796191899 , 434321947632744071481092243 , 502327221194518528553936039

def add(P1,P2):
    x1,y1=P1
    x2,y2=P2
    x3=(x1*x2-y1*y2)%n
    y3=(x1*y2+x2*y1)%n
    return (x3,y3)

def mul(P,k):
    assert k>=0
    Q=(1,0)
    while k>0:
        if k%2:
            k-=1
            Q=add(P,Q)
        else:
            k//=2
            P=add(P,P)
    return Q

phi = (p*p-1)*(q*q-1)*(r*r-1)
d = inverse(e,phi)
M = mul(C,d)
assert mul(M,e)==C
print(long_to_bytes(M[0])+long_to_bytes(M[1]))
# 47f4f203afe894ddbb1bcf6368d901cf93990354dadbc5b7794e199d4f0b59cb

 

2021 N1CTF Crypto题解

N1CTF的赛题质量还是很高，和西湖同时间打的比赛，我看自闭了，checkin都没写出来，想到了copperSmith算p，方程也列出来了，但是我没去跑，还以为差些条件。官方题解和题目存储都在Nu1l的Github上面有存档。以下writeup会参考韩国战队SupperGuesser的题解，也是本次比赛的第一名。

 

checkin

本题参考了这篇writeup：https://project-euphoria.dev/blog/26-n1ctf-2021/。

设。

这里我们为了减少运行时间，需要把q的leading bits也算出一部分，已知p的高22位和n，我们可以算出q的高21位，第22位不确定是因为可能有进位。简单的计算方法就是：$q1=n//(p0<<490),q0=q1>>491$ 。这样我们已知p的高22位和q的高21位。从而我们将x做如下分解：

前半部分记为x0，后半部分记为x1，其中x0已知，x1未知，x1的数量级大概在2**500左右，令$f(x)=x^2-hx+1$，最高次为2，根$x1<N^{1/2}$，那么我们可以用Coppersmith定理进行求解，但是需要注意epsilon值的设置，可以参考sage的文档。具体的联系我没有看论文，但是epsilon越小，解LLL的矩阵越大，耗时越长，得到解的概率越大。由X的bound的公式：

$X=ceil(\frac{1}{2}N^{β^2/δ−ϵ})$，由于N是1024比特，X的严格上界是2^505 (计算得的的解为2^502)，得到的epsilon应该小于0,009。由于是估算，可以稍微设置大一些，也能在多项式时间内得到解。这里设置epsilon为1/80可以得到解，只需要10min。

求解x1的代码如下：

1
2
3
4
5
6
7
8
9
10
def CopperSmith():
    R = Zmod(n)
    PR.<x> = PolynomialRing(R)
    _x = 2021*p0*2^490 + 1120*q0*2^491 + x
    f = (_x^2 - _x*h + 1).monic()
    # [7279473437564993427256268527891542563557232159626049883951364173102121134158423609775502464752174435483615142675582269470774951285125088232851515513237]
    # time cost 726 s
    roots = f.small_roots(X=2^505,epsilon=1/80)
    print(roots)
CopperSmith()

得到x1之后，我们就得到了的值，并且已知，直接联立解方程即可分解n，这里用z3解，脚本如下：

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
from Crypto.Util.number import *
from z3 import *
n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
p0 = 4055618
e = 65537
# x^2 -hx + 1 = 0 mod n


if __name__ == "__main__":
    q1=n//(p0<<490)
    q0=q1>>491
    x=7279473437564993427256268527891542563557232159626049883951364173102121134158423609775502464752174435483615142675582269470774951285125088232851515513237
    S=Solver()
    _p=BitVec('_p',1080)
    _q=BitVec('_q',1080)
    S.add((_p*_q)==(n*2021*1120))
    S.add((_p+_q)==(1120*q0*2**491+2021*p0*2**490+x))
    ans=S.check()
    print(S.model())
    p=S.model()[_p].as_long()//2021
    q=S.model()[_q].as_long()//1120
    assert p*q==n
    phi=(p-1)*(q-1)
    d=inverse(e,phi)
    flag=pow(c,d,n)
    print(long_to_bytes(flag))
    # n1ctf{093fd4c4-5cc9-427e-98ef-5a04914c8b4e}

 

n1token1

题目源码：

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

def gettoken(c):
    X = 0
    while ((pow(X, (p-1)//2, p)!=1) or (pow(X, (q-1)//2, q)!=1)):
        X = 1
        while X.bit_length() < 920:
            X *= random.choice(primes)
    xp = pow(X, (p + 1)//4, p)
    xq = pow(X, (q + 1)//4, q)
    # print(xp,xq)
    print(xp**2%p,xq**2%q)
    xp = random.choice([xp,-xp%p])
    xq = random.choice([xq,-xq%q])
    print(X)
    x = c * (xp*inverse(q,p)*q + xq*inverse(p,q)*p) % n
    return x

def getmyPrime(nbits):
    p = getPrime(nbits)
    while(p%4==1):
        p = getPrime(nbits)
    return p

primes = random.sample(sieve_base, 920)
p = getmyPrime(512)
q = getmyPrime(512)
e = 65537
n = p*q
c = pow(bytes_to_long(flag), e, n)
gettoken(c)

# with open("output.txt", "w")as f:
#     f.write("n = " + str(n) + "\n")
#     for i in range(920):
#         f.write("Token #"+str(i+1)+': '+str(gettoken(c))+'\n')

首先注意到：p，q都是模4余3的，$p=4k_1+3,q=4k_2+3$，这是后面取sqrt的条件。token产生的过程是关键，弄清楚结果x的表达式即可。

token产生：选择920个素数，从这920个素数产生刚好大于920比特的模p和模q的二次剩余X，即也是模n的二次剩余。那么显然有

即$x_p和x_q是X模p的1/2次和X模q的1/2次$，再者，由：

这就是最后的token在数学上的表示形式。更严格地说上式是：$+\sqrt{X}或者-\sqrt{X}$，那么：，SupperGuesser战队的writeup提出一个巧妙解法：HNP。为什么可以当成HNP问题来解呢？注意到X的比特数是稍微比920大一点，而n是1024比特，这意味着我们知道在模n意义下X的前100比特都是0。把上式换写一下：。

其中$c^{-2}$就是HNP中需要求的秘密参数，而X我们已知其大概100位的MSB。这样就可以解HNP问题了，并且我们已知的MSB都是0，因此不再需要Babai算法求CVP了。直接LLL算法得到最短向量即可求解，当然需要除去一个特殊的最短格点（0,0…，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
from Crypto.Util.number import *
f=open("/home/sage/Desktop/Extra Learning/CTF/比赛/N1CTF2021/crypto-n1-token1/output.txt","r")
n = int(f.readline()[4:])
tokens = [int(f.readline().split(": ")[1]) for _ in range(920)]
x2 = [pow(x, 2, n) for x in tokens]

def build_basis(oracle_inputs,p,d=30):
    """
    Returns a basis using the HNP game parameters and inputs to our oracle
    """
    basis_vectors = []
    for i in range(d):
        p_vector = [0] * (d+1)
        p_vector[i] = p
        basis_vectors.append(p_vector)
    basis_vectors.append(list(oracle_inputs) + [QQ(1)/QQ(p)])
    return Matrix(QQ, basis_vectors)

M = build_basis(x2[:50],n,50)

T = M.LLL()
 
c2inv=T[1][-1]*n%n
c2=inverse(c2inv, n)
print(c2)
# 45826812852445545573935979277992443457076371872089648644915475778319093098825670699151487782654163657210516482531915639455166133358119343973980849423144111072114848219032243215219360482938562035117641611780636775341778802057146053472950017702818869239750207365020007621660815809140827723451995480125236607450

现在的问题是如何求解c的RSA加密，貌似没有显示地给出其他信息，所以我们再研究一下x的产生过程，它用到了额外的p，q信息，因为任意X的二次剩余有四个（在模n=p*q意义下），不妨记为：x，y，n-x，n-y。如果我们恰好已知的是两个非加法逆的x，y，那么：$x^2-y^2=0 \ mod \ n$，即（x+y)(x-y)|n，此时 x+y 和 x-y 都不是 n 的倍数，而 (x+y)(x-y) 却是 n 的倍数，说明 x+y 和 x-y 中分别包含一个 n 的真因数。此时计算 gcd(n, x+y) 即可得到 n 的一个真因数。这样就分解了n。

但是我们不能直接求出c或者，已知条件是、x、X和$c^2$。注意到X的产生，他们都是由sievebase中的920个素数产生的。

sievebase的长度是10000，所以我们可以直接遍历把这920个素因子求出来，同时我们知道每个X，可以求出对应素因子的次数。我们就可以考虑用这920个token组合使得L个X相乘恰好是一个完全平方数，即。如此：

，其中可以直接由完全平方数开方得到，我们可以直接求nthroot，由于在生成的过程中还乘了模n意义下1的二次剩余$\sqrt1$，因此我们还有可能得到另外一个$x^2=1 \ mod \ n $的解，如果我们得到该解，就可以进行n的分解。

再考虑L的奇偶性：

  • L是偶数：那么我们可以由$C^2$计算出$C^L$,这样就可以得到$x^2=1 \ mod \ n $的一个解sqrt1，如果恰好这个解不等于1或则-1，我们就可以分解N。分解N之后其实就可以全部解c，解一次Rabin，再解一次RSA，找出有意义的解即可。
  • L是奇数：我们可以得到：$C*\sqrt{1}$。如果恰好是1或者-1，我们就能得到C。

那么如何选出合适的token使得是一个完全平方数？构造矩阵M,920*920。其中代表第i个token的primes[j]的次数。这样我们发现矩阵M的右核空间（right_kernel），即满足。

取右核空间内的向量，取对应的token，就满足是完全平方数了，经过计算得到M的右核空间维数恰好是2，并且其中1的个数恰好一奇一偶，即L一奇一偶（实际经过上面的讨论只需要有偶数L就可以解）。

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
from Crypto.Util.number import *
f=open("/home/sage/Desktop/Extra Learning/CTF/比赛/N1CTF2021/crypto-n1-token1/output.txt","r")
# f=open("./output.txt","r")
n = int(f.readline()[4:])
tokens = [int(f.readline().split(": ")[1]) for _ in range(920)]
x2 = [power_mod(x, 2, n) for x in tokens]
c2=45826812852445545573935979277992443457076371872089648644915475778319093098825670699151487782654163657210516482531915639455166133358119343973980849423144111072114848219032243215219360482938562035117641611780636775341778802057146053472950017702818869239750207365020007621660815809140827723451995480125236607450
c2inv = 52983076548811446642078416561526103296256117483454486324354864860934507167817419284299797979785979560318778718382121118437029467788929084290109421055494194638653398930615132561955251638059730256502250470596999508030459148548384745026728889238876530368915312995370308785841757845456662731412090368303339076885
X = [v * c2inv % n for v in x2]

primes = []
for p in sieve_base:
    for x in X:
        if int(x) % p == 0:
            primes.append(p)
            break
print(len(primes))

SZ = 920
mat = [[0] * SZ for _ in range(SZ)]
# mat[i][j] : number of factor primes[i] in X[j]
# token，prime矩阵构造
for i in range(920):
    v = int(X[i])
    for j in range(920):
        while v % primes[j] == 0:
            v //= primes[j]
            mat[j][i] += 1
    
M = Matrix(GF(2), mat)
basis_ = M.right_kernel().basis()
 
# Part 1 : find c
xmult = Integer(1)
Xmult = Integer(1)
cnt = 0
for i in range(920):
    cc = basis_[0][i]
    if int(cc) == 1:
        xmult = xmult * Integer(tokens[i])
        Xmult = Xmult * Integer(X[i])
        cnt += 1
        
# basis_[0]这个向量1的个数是奇数个，cnt即L
print(cnt)
v = Xmult.nth_root(2, truncate_mode=True)[0]
xmult = xmult % n 
c_cnt = (xmult * inverse(int(v % n), n)) % n 
# c * sqrt(1) mod n
c = (c_cnt * inverse(power_mod(c2, (cnt - 1) // 2, n), n)) % n 

# Part 2 : find some sqrt of 1
xmult = Integer(1)
Xmult = Integer(1)
 
cnt = 0
for i in range(920):
    cc = basis_[1][i]
    if int(cc) == 1:
        xmult = xmult * Integer(tokens[i])
        Xmult = Xmult * Integer(X[i])
        cnt += 1
 
print(cnt)
v = Xmult.nth_root(2, truncate_mode=True)[0]
xmult = xmult % n 
c_cnt = (xmult * inverse(int(v % n), n)) % n 
# sqrt(1)中一个不是1和-1的值，可以分解n
sq1 = (c_cnt * inverse(power_mod(c2, cnt // 2, n), n)) % n 

print(n)
p = GCD(sq1+1, n)
q = GCD(sq1-1, n)
assert p != 1 and q != 1 and p * q == n
 
for u in [1, -1]:
    for v in [1, -1]:
        # sqrt(1)的四个值乘以可能的c*sqrt(1),其中有一个是c
        cc = crt(u, v, p, q)
        c_real = (c * cc) % n
        phi = (p - 1) * (q - 1)
        d = inverse(65537, phi)
        print(long_to_bytes(power_mod(c_real, d, n)))
# n1ctf{b9e7d419-0df8-438a-9120-efdf3ddf155f}
# 改自writeup https://rkm0959.tistory.com/243

 

n1token2

参考官方的writeup。

源码：

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

assert FLAG.startswith('n1ctf{')
assert FLAG.endswith('}')
SECRET = bytes.fromhex(FLAG[6:-1])
assert len(SECRET) == 16

p = 251
 
e = [1, 20, 113, 149, 219]

y = b'' 
for x in range(1, p):
    coeff = [random.choice(e)] + list(SECRET)
    y += bytes([sum(c * pow(x, i, p) for i, c in enumerate(coeff)) % p])
    
print(f'Token: {y.hex()}')

已知的token值是，其中x取1到p-1的值。很自然地我们想到解线性方程组。但是问题在于e是随机的，有五个值。令 上面的方程可以改写为 ​。令$k[i] = (y(x)-e[i])/x$, 因此必定有一个i使得， $f(x)-k[i] \equiv 0 \pmod{p}$ 成立。

那么多项式恒成立。展开：

。 其中$(f(x))^i$, 是15次多项式， 这5个多项式的总未知系数是 76+61+46+31+16=230 ， 我们有 250 个 tokens, 解线性方程即可。

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
p = 251
y = bytes.fromhex('1d85d235d08dfa0f0593b1cfd41d3c98f2a542b2bf7a614c5d22ea787e326b4fd37cd6f68634d9bdf5f618605308d4bb16cb9b9190c0cb526e9b09533f19698b9be89b2e88ba00e80e44d6039d3c15555d780a6a2dbd14d8e57f1252334f16daef316ca692c02485684faee279d7bd926501c0872d01e62bc4d8baf55789b541358dfaa06d11528748534103a80c699a983c385e494a8612f4f124bd0b2747277182cec061c68197c5b105a22d9354be9e436c8393e3d2825e94f986a18bd6df9ab134168297c2e79eee5dc6ef15386b96b408b319f53b66c6e55b3b7d1a2a2930e9d34287b74799a59ab3f56a31ae3e9ffa73362e28f5751f79')
e = [1, 20, 113, 149, 219]

A = matrix(GF(p),250,230)
b = vector(GF(p),250)
PR.<f> = PolynomialRing(GF(p))
for i in range(250):
    F = 1
    for j in range(5):
        F = F*(f-GF(p)((y[i]-e[j])/(i+1)))
    for j in range(76):
        A[i,j] = F[5]*pow(i+1,j,p)
    for j in range(61):
        A[i,j+76] = F[4]*pow(i+1,j,p)
    for j in range(46):
        A[i,j+137] = F[3]*pow(i+1,j,p)
    for j in range(31):
        A[i,j+183] = F[2]*pow(i+1,j,p)
    for j in range(16):
        A[i,j+214] = F[1]*pow(i+1,j,p)
    b[i] = -F[0]
res = A.solve_right(b)
flag = 'n1ctf{' + bytes(res[214:]).hex() + '}'
print(flag)

 

n1login

一个侧信道的攻击，参考官方wp：n1login

 

2021 KQCTF crypto题解

赛题不是特别难，但是有两道比较有意思的题。一个是NTRU格密码，一个是多项式多点快速求值。题目存库于repo。

 

Polynomialtime

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
import time
import numpy as np
import random


def interpolate(l):
    for _ in range(624):
        x = random.getrandbits(32*2**4)
        print(x)
    mo = random.getrandbits(32*2**4)
    FR.<x> = PolynomialRing(IntegerModRing(mo))
    f = prod([(random.getrandbits(32*2**4)*x-1) for _ in range(1,l)])
    return f, mo

#hmm, maybe a bit slow
def evaluate(poly, points, mo):
    evaluations = []
    for point in points:
        evaluations.append(poly(point))
    return evaluations

if __name__ == "__main__":
    with open("flag.txt","r") as f:
        flag = f.read()
    
    size = 1048576
    poly, mo = interpolate(size)
    R = Integers(mo)
    points = [R(random.getrandbits(32*2**4)) for _ in range(size)]
    ans = bytearray.fromhex(hex(prod(evaluate(poly,points,mo)))[2:-10])
    
    
    ciphertext = bytearray(b"")
    for i, c in enumerate(flag):
        ciphertext.append(ord(c)^^ans[i])
    
    print(ciphertext)

解题流程很容易理清，先需要恢复一个MT19937的PRNG，这个可以直接用mt19937predictor库进行。恢复后我们需要计算次数高达1048576次的多项式的100多万个点，这个计算量相当大。因此我们需要做优化。考虑用递归分治的算法进行求解，感觉这像是一个OI题，可以参考OI的wiki：多项式多点快速求值。sagemath脚本如下：

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
# sage 

import mt19937predictor
from Crypto.Util.number import *

mt=mt19937predictor.MT19937Predictor()

data=open("./outputpt.txt","r").read().split("\n")

def evaluate(roots, points, mo):
    evaluations = []
    for point in points:
        evaluations.append(prod([ (root*point-1) for root in roots]))
        print("one point")
    return evaluations

def fast_cacl(f,points,mo):
    FR.<x> = PolynomialRing(IntegerModRing(mo))
    p_len=len(points)
    if p_len==1:
        return [f(points[0])]
    f0=prod([(x-point) for point in points[:p_len//2]])
    f1=prod([(x-point) for point in points[p_len//2:]])
    right_res=fast_cacl(f%f0,points[:p_len//2],mo)
    left_res=fast_cacl(f%f1,points[p_len//2:],mo)
    return right_res+left_res

    

# recover prng state
for i in range(624):
    mt.setrandbits(int(data[i]),32*16)

print("[+] recovered prng")
size = 1048576
mo = mt.getrandbits(32*2**4)
FR.<x> = PolynomialRing(IntegerModRing(mo))
R = Integers(mo)
f = prod([(mt.getrandbits(32*2**4)*x-1) for _ in range(1,size)])
print("[+] Poly constructed!")

points = [R(mt.getrandbits(32*2**4)) for _ in range(size)]
print("[+] Points generated!")

temp_res=prod(fast_cacl(f,points,mo))
print("[+] recover final result ",temp_res)

ans = bytearray.fromhex(hex(int(temp_res))[2:-10])    
print("[+] recover key stream ")
print(ans)

ciphertext = bytearray(b"/\xbe\x9f\x83\x8a\x9eY\xb43\x9f\xfa\xc2\x98\xe9@K\xd7r\xd7j\xde\xd5\xef,\xda\x11\x1as\x83k\x10\xb8\xaaP\x7f \xb6|\xe02\x0fr\x0b\xf8\x9c\xfep2")
flag=bytearray(b"")
for i, c in enumerate(ciphertext):
    flag.append(c^^ans[i])
print(flag)

 

KQRUEncrypt

一个NTRU格密码，可以直接参考：https://latticehacks.cr.yp.to/ntru.html

主要记录一下源码和脚本：

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
import random
from Crypto.Util.number import *

Zx.<x> = ZZ[]
d = 7

def cyclicconvolution(f,g):
    return (f * g) % (x^n-1)

def balancedmod(f,q):
    g = list( ((f[i] + q//2) % q) - q//2 for i in range(n) )
    return Zx(g)

def rpoly():
    assert d <= n
    result = n*[0]
    for j in range(d):
        while True:
                r = randrange(n)
                if not result[r]: break
        result[r] = 1-2*randrange(2)
    return Zx(result)

def invertmodprime(f,p):
    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
    return Zx(lift(1 / T(f)))


def invertmodpowerof2(f,q):
    assert q.is_power_of(2)
    g = invertmodprime(f,2)
    while True:
        r = balancedmod(cyclicconvolution(g,f),q)
        if r == 1: return g
        g = balancedmod(cyclicconvolution(g,2 - r),q)

def keypair():
    while True:
        try:
            f = rpoly()
            fp = invertmodprime(f, p)
            fq = invertmodpowerof2(f, q)
            break
        except:
            pass
    g = rpoly()
    publickey = balancedmod(p * cyclicconvolution(fq, g), q)
    secretkey = (f, fp)
    return (publickey, secretkey)

def encrypt(message, publickey):
    r = rpoly()
    return balancedmod(cyclicconvolution(publickey, r) + message, q)

def decrypt(cipher,f,fp):
    # cipher=Zx(cipher)
    a=balancedmod(cyclicconvolution(f, cipher), q)
    m=balancedmod(cyclicconvolution(fp, a),p)
    bin_str=''.join([str(i) for i in m.coefficients(sparse=False)])
    while '-1' in bin_str:
        bin_str=bin_str.replace('-1','1')
    flag=int(bin_str,2)
    print(long_to_bytes(flag))
    flag=int(bin_str[::-1],2)
    print(long_to_bytes(flag))
    return m

def genMessage(message):
    m = Zx([
        (1 if random.random() <= 0.5 else -1)*int(c) for c in ''.join(format(ord(x), 'b').zfill(8) for x in message)
    ])
    return m

# hx public key
# ex secret key
def LLL_ATTACK(hx,r=0):
    N =161
    p =3
    q =128
    p_dq=43
    Q.<x> = Zmod(q)[]
    P.<y> = Zmod(p)[] 
    print('-------decrypt------')
    qq = x^N-1
    pp = y^N-1
    hn = [(int(x)*p_dq+q//2)%q-q//2 for x in hx]
    n = len(hn)
    A1 = matrix.identity(n)*q
    A0 = matrix.zero(n)
    Aq = matrix.identity(n)
    Ah = matrix(ZZ, [hn[-i:] + hn[:-i] for i in range(n)])
    M = block_matrix([A1,Ah,A0,Aq],nrows=2)
    # hn = [(int(x)*p_dq+q//2)%q-q//2 for x in hx]
    # n = len(hn)
    # A1 = matrix.identity(n)*q
    # A0 = matrix.zero(n)
    # Aq = matrix.identity(n)
    # Ah = matrix(ZZ, [hn[-i:] + hn[:-i] for i in range(n)])
    # M = block_matrix([A1,Ah,A0,Aq],nrows=2)
    # L = M.transpose().LLL()
    # for i in range(r):
    #     for j in range(2*n):
    #         M[j,n+i]=M[j,n+i]*10
    # print(M[0])
    # L = M.LLL()
    L = M.transpose().LLL()
    # L=M.BKZ()
    for i in range(n):
        v=list(L[i])
        if v.count(1)+v.count(-1)==14:
            print(v[:n])
            print(v[n:])
            print("valid")
            break
    # v=list(L[0])
    # print(v[:n])
    # print(v[n:])
    
def attack(publickey):
    recip3 = lift(1/Integers(q)(3))
    publickeyover3 = balancedmod(recip3 * publickey, q)
    M = matrix(2 * n)
    for i in range(n):
        M[i, i] = q
    for i in range(n):
        M[i+n, i+n] = 1
        c = convolution(list(x ^ i), list(publickeyover3))
        # c.reverse()
        for j in range(n):
            M[i+n, j] = c[j]
    M = M.LLL()
    print(M[0])
    print(M[1])
    for i in range(2*n):
        v=list(M[i])
        if v.count(1)+v.count(-1)==14:
            print("valid")
            print(v)
            break
        
    for j in range(2 * n):
        try:
            f = Zx(list(M[j][n:]))
            f3 = invertmodprime(f, 3)
            return (f, f3)
        except:
            pass
    return (f, f)

n = 161
p = 3
q = 128

# with open("flag.txt","r") as f:
#     m = genMessage(f.readline())
m = genMessage("f"*20)

(publickey, secretkey) = keypair()
c = encrypt(m, publickey)
r_m=decrypt(c,secretkey[0],secretkey[1])

print("secret key f",secretkey[0])
print("secret key fp",secretkey[1])
# hx = [43, -62, -28, 60, -54, -36, 53, -21, 19, 24, 33, 22, 12, 11, -11, -4, -16, -53, -20, -10, 9, 24, -14, 50, 51, 34, -10, -46, 21, -36, -30, 13, -57, -38, 40, 62, 6, -63, 59, -34, 8, -18, 26, 56, -36, 23, 19, -59, 10, 48, 41, -33, 5, -57, -13, 5, 46, 23, -49, 10, -19, 35, -20, 26, -37, -54, 16, 46, 11, 38, -22, 17, -6, -8, -38, -34, 50, 48, -48, -52, -47, -58, -35, 7, 8, -48, -59, -17, -9, -32, 46, -38, -22, -54, -43, -43, -21, 24, -55, 44, -56, -58, -37, 55, -42, -1, 4, 6, -47, -56, -52, 26, 41, 53, 48, 44, -9, -21, 59, -20, -41, 27, 60, 30, -52, -18, -23, 9, -6, -49, -37, -44, 22, 32, 51, -29, -8, 5, 60, -16, 20, -24, -17, 63, 53, 58, -9, 48, -19, 45, 7, -30, -36, 10, 48, -33, 25, 6, -62, 58, -57]
# hx.reverse()
# LLL_ATTACK(hx)
hx=list(publickey)
print(len(hx))
hx.reverse()
LLL_ATTACK(list(publickey))
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
#Sage 
#多项式
from Crypto.Util.number import long_to_bytes
N =161
p =3
q =128
Q.<x> = Zmod(q)[]
P.<y> = Zmod(p)[]
Zx.<z> = ZZ[]

cipher = [-3, -34, -33, -31, 59, 34, 50, -56, -46, 0, -19, 6, 55, 18, -20, 2, 57, -36, -61, 32, -33, 13, -27, -25, -29, 5, 36, -37, 11, -19, -10, -15, -7, -8, 63, 21, 51, -30, -64, -15, -54, -28, -23, -6, -28, 35, 21, -24, -11, 62, 21, 51, -4, -11, -21, -10, 60, -53, -28, 12, 0, 4, 36, 9, 44, -19, -53, -57, 28, -15, 33, 58, -10, 32, 25, 46, 2, -11, -19, 6, -9, 0, -8, 32, -25, 31, -62, -7, 16, -13, 33, 54, 24, -48, -57, 37, -62, 13, 46, 39, 5, 44, 30, 10, -6, -17, -2, 22, -23, -14, 5, -53, -13, -46, 22, -32, -8, -16, -34, 55, 56, -5, -29, 0, 42, 23, 40, -47, -62, 59, 47, 18, -61, -14, -56, 29, -61, -52, 47, -49, 22, 18, 15, 60, -12, 11, -46, 1, 8, -58, -6, -7, 41, -58, 44, -22, -15, -56, -3, -29]
pubkey = [43, -62, -28, 60, -54, -36, 53, -21, 19, 24, 33, 22, 12, 11, -11, -4, -16, -53, -20, -10, 9, 24, -14, 50, 51, 34, -10, -46, 21, -36, -30, 13, -57, -38, 40, 62, 6, -63, 59, -34, 8, -18, 26, 56, -36, 23, 19, -59, 10, 48, 41, -33, 5, -57, -13, 5, 46, 23, -49, 10, -19, 35, -20, 26, -37, -54, 16, 46, 11, 38, -22, 17, -6, -8, -38, -34, 50, 48, -48, -52, -47, -58, -35, 7, 8, -48, -59, -17, -9, -32, 46, -38, -22, -54, -43, -43, -21, 24, -55, 44, -56, -58, -37, 55, -42, -1, 4, 6, -47, -56, -52, 26, 41, 53, 48, 44, -9, -21, 59, -20, -41, 27, 60, 30, -52, -18, -23, 9, -6, -49, -37, -44, 22, 32, 51, -29, -8, 5, 60, -16, 20, -24, -17, 63, 53, 58, -9, 48, -19, 45, 7, -30, -36, 10, 48, -33, 25, 6, -62, 58, -57]


def cyclicconvolution(f,g):
    return (f * g) % (x^n-1)

def balancedmod(f,q):
    g = list( ((f[i] + q//2) % q) - q//2 for i in range(n) )
    return Zx(g)

def invertmodprime(f,p):
    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
    return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,q):
    assert q.is_power_of(2)
    g = invertmodprime(f,2)
    while True:
        r = balancedmod(cyclicconvolution(g,f),q)
        if r == 1: return g
        g = balancedmod(cyclicconvolution(g,2 - r),q)


N =161
p =3
q =128
p_dq=43
Q.<x> = Zmod(q)[]
P.<y> = Zmod(p)[]
# ex = 
# hx = 
ex = [-3, -34, -33, -31, 59, 34, 50, -56, -46, 0, -19, 6, 55, 18, -20, 2, 57, -36, -61, 32, -33, 13, -27, -25, -29, 5, 36, -37, 11, -19, -10, -15, -7, -8, 63, 21, 51, -30, -64, -15, -54, -28, -23, -6, -28, 35, 21, -24, -11, 62, 21, 51, -4, -11, -21, -10, 60, -53, -28, 12, 0, 4, 36, 9, 44, -19, -53, -57, 28, -15, 33, 58, -10, 32, 25, 46, 2, -11, -19, 6, -9, 0, -8, 32, -25, 31, -62, -7, 16, -13, 33, 54, 24, -48, -57, 37, -62, 13, 46, 39, 5, 44, 30, 10, -6, -17, -2, 22, -23, -14, 5, -53, -13, -46, 22, -32, -8, -16, -34, 55, 56, -5, -29, 0, 42, 23, 40, -47, -62, 59, 47, 18, -61, -14, -56, 29, -61, -52, 47, -49, 22, 18, 15, 60, -12, 11, -46, 1, 8, -58, -6, -7, 41, -58, 44, -22, -15, -56, -3, -29]
hx = [43, -62, -28, 60, -54, -36, 53, -21, 19, 24, 33, 22, 12, 11, -11, -4, -16, -53, -20, -10, 9, 24, -14, 50, 51, 34, -10, -46, 21, -36, -30, 13, -57, -38, 40, 62, 6, -63, 59, -34, 8, -18, 26, 56, -36, 23, 19, -59, 10, 48, 41, -33, 5, -57, -13, 5, 46, 23, -49, 10, -19, 35, -20, 26, -37, -54, 16, 46, 11, 38, -22, 17, -6, -8, -38, -34, 50, 48, -48, -52, -47, -58, -35, 7, 8, -48, -59, -17, -9, -32, 46, -38, -22, -54, -43, -43, -21, 24, -55, 44, -56, -58, -37, 55, -42, -1, 4, 6, -47, -56, -52, 26, 41, 53, 48, 44, -9, -21, 59, -20, -41, 27, 60, 30, -52, -18, -23, 9, -6, -49, -37, -44, 22, 32, 51, -29, -8, 5, 60, -16, 20, -24, -17, 63, 53, 58, -9, 48, -19, 45, 7, -30, -36, 10, 48, -33, 25, 6, -62, 58, -57]
hx.reverse()
ex.reverse()

print('-------decrypt------')
qq = x^N-1
pp = y^N-1
hn = [(int(x)*p_dq+q//2)%q-q//2 for x in hx]
n = len(hn)
A1 = matrix.identity(n)*q
A0 = matrix.zero(n)
Aq = matrix.identity(n)
Ah = matrix(ZZ, [hn[-i:] + hn[:-i] for i in range(n)])
M = block_matrix([A1,Ah,A0,Aq],nrows=2)
L = M.transpose().LLL()
# L = M.LLL()
for i in range(n):
    v=list(L[i])
    print(v)
    if v.count(1)+v.count(-1)==14:
        print("valid")
        break
v=list(L[0])
print(v)
# v.reverse()
for i in range(len(v)):
    if v[i]==3 or v[i]==-3:
        v[i]=v[i]//3
print(v)


f = (list(v)[:n])
g = (list(v)[n:])
fx = Q(f)
fy = P(f)
gx = Q(g)
Fqx = fx.inverse_mod(qq)
Fpy = fy.inverse_mod(pp)

#hxx = (Fqx*gx).mod(x^N-1)
#print(hxx==hx)

c=Q(ex)
ax = (fx*c).mod(qq)
an = [int(x) for x in ax.coefficients()]
#中心提升(centerlift)，使域范围从[0,q)变换到(-q/2,q/2)
for i in range(len(an)):
    if an[i] > q//2:
        an[i] -= q
ax = P(an)
print(ax)
out = (Fpy * ax).mod(pp)
print(out)

bin_str=''.join([str(i) for i in out.coefficients(sparse=False)])
while '2' in bin_str:
    bin_str=bin_str.replace('2','1')
print(bin_str)
flag1=int(bin_str,2)
flag2=int(bin_str[::-1],2)
v=[0, -1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
print(long_to_bytes(flag1))
print(long_to_bytes(flag2))

 

2021 陇原杯 crypto题解

比较简单，也是记录一下脚本。

 

easytask

原来以为是LWE，其实是GGH，之后在详细了解一下。不过按照LWE的格构造来解其实也是差不多的。GGH加密可以参考这个。或者我们认为它是没有取模的 LWE 问题，格直接取输出的M矩阵即可，不需要再构造额外的对角q矩阵，LLL格基规约后用 Babai算法解CVP问题，可以得到 r-e ，我们再确认 error 的范围和源代码一致即可： [-3,3] ,之后解线 性方程组即可得到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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# Sage
from sage.modules.free_module_integer import IntegerLattice
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

res = [151991736758354 ,115130361237591,  58905390613532 ,130965235357066 , 74614897867998  ,48099459442369 , 45894485782943   ,7933340009592   ,  25794185638]
ma =[[-10150241248 ,-11679953514  ,-8802490385, -12260198788 ,-10290571893   ,-334269043 ,-11669932300 , -2158827458  ,   -7021995],
[ 52255960212,  48054224859  ,28230779201  ,43264260760  ,20836572799   ,8191198018  ,14000400181  , 4370731005    , 14251110],
[  2274129180  ,-1678741826  ,-1009050115  , 1858488045   , 978763435   ,4717368685   ,-561197285 , -1999440633     ,-6540190],
[ 45454841384  ,34351838833  ,19058600591 , 39744104894  ,21481706222 , 14785555279  ,13193105539  , 2306952916     , 7501297],
[-16804706629 ,-13041485360  ,-8292982763 ,-16801260566  ,-9211427035  ,-4808377155  ,-6530124040  ,-2572433293    , -8393737],
[ 28223439540  ,19293284310   ,5217202426  ,27179839904  ,23182044384  ,10788207024  ,18495479452   ,4007452688   ,  13046387],
[   968256091 , -1507028552  , 1677187853   ,8685590653   ,9696793863   ,2942265602  ,10534454095   ,2668834317   ,   8694828],
[ 33556338459  ,26577210571 , 16558795385  ,28327066095  ,10684900266   ,9113388576  , 2446282316   ,-173705548  ,    -577070],
[ 35404775180  ,32321129676,  15071970630  ,24947264815 , 14402999486   ,5857384379 , 10620159241   ,2408185012 ,     7841686],
]

W = matrix(ZZ, ma)
cc = vector(ZZ, res)

# Babai's Nearest Plane algorithm
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(5):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -=  M[i] * c
    return target - small

lattice = IntegerLattice(W, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()
gram=gram[0]
target = cc
re = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(re))
e = re - cc  # error vector
print("error sum ",e.norm()^2)
# e全为-3,3之间说明正确恢复
print(e)

# R = ZZ
M = Matrix(ZZ, ma)
# ingredients全为素数说明恢复完全正确
ingredients = list(M.solve_left(re))
print("Ingredients: {}".format(ingredients))

key = hashlib.sha256(str(ingredients).encode()).digest()
enc_flag =long_to_bytes(0x1070260d8986d5e3c4b7e672a6f1ef2c185c7fff682f99cc4a8e49cfce168aa0)
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(enc_flag)
print(flag)
# flag{be5152d04a49234a251956a32b}'

 

 

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true


Hi, this is tl2cents
Currently Ph.D at IIE of UCAS
Graduated from USTC (2018-2022)

CTFer
Focus on blockchain, crypto and reversing
Team member of NeSE and Nebula

Research
Blockchain | ETH | FHE
PQC | Cryptography | Android

Contact Me
echo Y2F4dWxhc2FlbGFAb3V0bG9vay5jb20K | base64 -d

Thanks for JoeyBling and Litten