Crypto

1.ez_math

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from sage.all import *
from Crypto.Util.number import *

flag = b'LILCTF{test_flag}'[7:-1]
lambda1 = bytes_to_long(flag[:len(flag)//2])
lambda2 = bytes_to_long(flag[len(flag)//2:])
p = getPrime(512)
def mul(vector, c):
    return [vector[0]*c, vector[1]*c]

v1 = [getPrime(128), getPrime(128)]
v2 = [getPrime(128), getPrime(128)]

A = matrix(GF(p), [v1, v2])
B = matrix(GF(p), [mul(v1,lambda1), mul(v2,lambda2)])
C = A.inverse() * B

print(f'p = {p}')
print(f'C = {str(C).replace(" ", ",").replace("\n", ",").replace("[,", "[")}')

# p = 9620154777088870694266521670168986508003314866222315790126552504304846236696183733266828489404860276326158191906907396234236947215466295418632056113826161
# C = [7062910478232783138765983170626687981202937184255408287607971780139482616525215270216675887321965798418829038273232695370210503086491228434856538620699645,7096268905956462643320137667780334763649635657732499491108171622164208662688609295607684620630301031789132814209784948222802930089030287484015336757787801],[7341430053606172329602911405905754386729224669425325419124733847060694853483825396200841609125574923525535532184467150746385826443392039086079562905059808,2557244298856087555500538499542298526800377681966907502518580724165363620170968463050152602083665991230143669519866828587671059318627542153367879596260872]

v1，v2是随机的向量 \[ A = \begin{pmatrix}v_1 \\ v_2\end{pmatrix} \\ B = \begin{pmatrix}\lambda_1v_1 \\ \lambda_2v_2\end{pmatrix} \]

\[ C = A^{-1}B \]

给了我们p和C，要求lambda1和lambda2

我们注意到 \[ \begin{pmatrix}\lambda_1 & 0\\ 0 & \lambda_2 \end{pmatrix}\begin{pmatrix}v_1 \\ v_2\end{pmatrix} = \begin{pmatrix}\lambda_1v_1 \\ \lambda_2v_2\end{pmatrix} \] 不妨记 \[ D =\begin{pmatrix}\lambda_1 & 0\\ 0 & \lambda_2 \end{pmatrix} \] 那么有 \[ B=AC=DA \] 于是 \[ C= A^{-1}DA \] 于是C相似于D，那么特征值相等

很显然lambda就是提示特征值，求C的特征值就行了

exp

1
2
3
4
5
6
7
8
9
10
11
12
from sage.all import *
from Crypto.Util.number import *
p = 
C = 
C = Matrix(GF(p),C) #这里用Zmod会报错
lam1,lam2 = C.eigenvalues()
flag1 = b'LILCTF{'+long_to_bytes(int(lam1))+long_to_bytes(int(lam2))+b'}'
flag2 = b'LILCTF{'+long_to_bytes(int(lam2))+long_to_bytes(int(lam1))+b'}'
print(flag1)
print(flag2)
b'LILCTF{It_w4s_the_be5t_of_times_1t_wa5_the_w0rst_of_t1me5}'
b'LILCTF{1t_wa5_the_w0rst_of_t1me5It_w4s_the_be5t_of_times_}'

2.mid_math

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
from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

flag = b'LILCTF{test_flag}'

p = getPrime(64)
P = GF(p)

key = randint(2**62, p)

def mul(vector, c):
    return [vector[0]*c, vector[1]*c, vector[2]*c, vector[3]*c, vector[4]*c]

v1 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v2 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v3 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v4 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v5 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
a, b, c, d, e = getPrime(64), getPrime(64), getPrime(64), getPrime(64),  0

A = matrix(P, [v1, v2, v3, v4, v5])
B = matrix(P, [mul(v1,a), mul(v2,b), mul(v3, c), mul(v4, d), mul(v5, e)])
C = A.inverse() * B
D = C**key

key = pad(long_to_bytes(key), 16)
aes = AES.new(key,AES.MODE_ECB)
msg = aes.encrypt(pad(flag, 64))

print(f"p = {p}")
print(f'C = {[i for i in C]}'.replace('(', '[').replace(')', ']'))
print(f'D = {[i for i in D]}'.replace('(', '[').replace(')', ']'))
print(f"msg = {msg}")

#p = 14668080038311483271
#C = [[11315841881544731102, 2283439871732792326, 6800685968958241983, 6426158106328779372, 9681186993951502212], [4729583429936371197, 9934441408437898498, 12454838789798706101, 1137624354220162514, 8961427323294527914], [12212265161975165517, 8264257544674837561, 10531819068765930248, 4088354401871232602, 14653951889442072670], [6045978019175462652, 11202714988272207073, 13562937263226951112, 6648446245634067896, 13902820281072641413], [1046075193917103481, 3617988773170202613, 3590111338369894405, 2646640112163975771, 5966864698750134707]]
#D = [[1785348659555163021, 3612773974290420260, 8587341808081935796, 4393730037042586815, 10490463205723658044], [10457678631610076741, 1645527195687648140, 13013316081830726847, 12925223531522879912, 5478687620744215372], [9878636900393157276, 13274969755872629366, 3231582918568068174, 7045188483430589163, 5126509884591016427], [4914941908205759200, 7480989013464904670, 5860406622199128154, 8016615177615097542, 13266674393818320551], [3005316032591310201, 6624508725257625760, 7972954954270186094, 5331046349070112118, 6127026494304272395]]
#msg = b"\xcc]B:\xe8\xbc\x91\xe2\x93\xaa\x88\x17\xc4\xe5\x97\x87@\x0fd\xb5p\x81\x1e\x98,Z\xe1n`\xaf\xe0%:\xb7\x8aD\x03\xd2Wu5\xcd\xc4#m'\xa7\xa4\x80\x0b\xf7\xda8\x1b\x82k#\xc1gP\xbd/\xb5j"

就是上一题变难了一点 \[ A = \begin{pmatrix}v_1\\v_2\\v_3\\v_4\\v_5\end{pmatrix},B= \begin{pmatrix}av_1\\bv_2\\cv_3\\dv_4\\ev_5\end{pmatrix} \]

然后C还是一样 \[ C= A^{-1}B,D=C^{k} \] 已知，C，D，求k，还是和上一题一样 \[ \begin{pmatrix}a & &\\&b&\\&&c\\&&&d\\&&&&e\end{pmatrix}A=B=AC \] 则 \[ C = A^{-1}MA \] 于是 \[ D=C^{k}=A^{-1}M^{k}A \] 所以D相似于M的k次方，把D对角化之后，就是DLP了

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
C = matrix(GF(p),C)
D = matrix(GF(p),D)
M,P = C.eigenmatrix_right()
Mk,Pk = D.eigenmatrix_right()
g = M[1][1]
for i in range(len(D[0])):
    h = Mk[i][i]
    Q = GF(p)
    g = Q(g)
    h = Q(h)
    try:
        k = discrete_log(h,g)
        print(k)
        key = pad(long_to_bytes(k), 16)
        aes = AES.new(key,AES.MODE_ECB)
        flag = aes.decrypt(msg)
        print(flag)
    except:
        pass

由于对角矩阵顺序可以换，所以要遍历一下

3.linear

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import os
import random
import signal

signal.alarm(10)

flag = os.getenv("LILCTF_FLAG", "LILCTF{default}")

nrows = 16
ncols = 32

A = [[random.randint(1, 1919810) for _ in range(ncols)] for _ in range(nrows)]
x = [random.randint(1, 114514) for _ in range(ncols)]

b = [sum(A[i][j] * x[j] for j in range(ncols)) for i in range(nrows)]
print(A)
print(b)

xx = list(map(int, input("Enter your solution: ").strip().split()))
if xx != x:
    print("Oh, your linear algebra needs to be practiced.")
else:
    print("Bravo! Here is your flag:")
    print(flag)

给了一个A \[ A\in Z^{16\times32},x\in Z^{32},b\in Z^{16} \] 然后 \[ Ax=b \] 显然A不满秩，不可能有唯一解，但是x的范围是限定的，考虑造格，将解变为短向量

x还是比较大的，所以我们可以考虑 \[ PAx = Pb \] 如果按照一般的情况的话，b是格中的向量，但是我们要求的是x，所以应该这样造格子 \[ \begin{pmatrix}A &b\\ E & O\end{pmatrix}\begin{pmatrix}x \\-1 \end{pmatrix}=(0,..,0,x_1,x_2,..x_{32}) \]

1
2
3
4
5
6
7
b = [2^100*i for i in b]
M =2^100* Matrix(ZZ,A)
M = M.stack(identity_matrix(32))
r = b + 32*[0]
M = M.augment(vector(ZZ,r)).T
x = M.BKZ(block_size=80)[0][16:]
print(-x)

为了使得它成为短向量，配一个系数就行了 \[ \begin{pmatrix}2^{100}A &2^{100}b\\ E & O\end{pmatrix}\begin{pmatrix}x \\-1 \end{pmatrix}=(0,..,0,x_1,x_2,..x_{32}) \]