[原创]GDG Algiers CTF两道矩阵题wp

[原创]GDG Algiers CTF两道矩阵题wp
2022-10-28 23:48:18 Author: bbs.pediy.com(查看原文) 阅读量:21 收藏

[原创]GDG Algiers CTF两道矩阵题wp

2天前 1082

[原创]GDG Algiers CTF两道矩阵题wp

两道矩阵相关的题，感觉可以整理一下下 :)

the_matrix

首先选定一个大素数 $p$ ，生成 $(1,p-1)$ 内的随机值 $priv$ 。

$priv$ 经过SHA256的处理得到key，再用AES通过key加密明文。

题目给定了两个12x12矩阵 $D, P$ ，满足 $D^{priv}=P$ 。

AES的初始向量已知，因此需要求 $priv$ 。

令 $D=Tdiag_DT^{-1}$ ，有

$diag_D^{priv}=T^{-1}PT$

设 $diag_D=diag(\lambda_1,\lambda_2,...,\lambda_{12}),\ T^{-1}PT=diag(\alpha_1,\alpha_2,...,\alpha_{12})$ ，则

$priv\equiv\log_{\lambda_i}\alpha_i\mod \delta_i,i=1,2,...12$

其中 $\delta_i$ 是 $\lambda_i$ 对 $p$ 的阶。

先求离散对数，然后求解同余方程组即可。

由于 $1\leq{priv}\leq{p-1}$ ，猜测可以唯一确定 $priv$ 。

计算之后发现， $diag_D=diag(37,31,29,23,19,...,2)$ ， $\delta_i$ 不是 $p-1$ 就是 $\frac{p-1}{2}$ 。

于是我选取 $\lambda=37$ ，此时 $\delta=p-1,\ priv=\log_{37}{(p-1)}$ 直接唯一确定。

python sln.py

CyberErudites{Di4g0n4l1zabl3_M4tric3s_d4_b3st}

import json

from Crypto.Hash import SHA256

from Crypto.Cipher import AES

from Crypto.Util.Padding import pad

p = 12143520799543738643

vD = [37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2]

vP = [6751925379844785295, 11256715989719283883, 4551561838026472495, 11383130904596697638, 8534299476177021992, 11184828239802784209, 7103104085280766875, 1622643043767580331, 11104789109564474465, 1502559189506368871, 522368022672629021, 1590703325067650792]

K = 7619698002081645976

key = SHA256.new(data=str(K).encode()).digest()[:2**8]

with open("encrypted_flag.txt", "r") as ff:

data_dict = json.load(ff)

iv = bytes.fromhex(data_dict["iv"])

ciphertext = bytes.fromhex(data_dict["ciphertext"])

cipher = AES.new(key, AES.MODE_CBC, iv)

flag = cipher.decrypt(ciphertext).decode()[:46]

print(flag)

franklin-last-words

选取大质数 $p,q,N=pq$ 和一个大随机数 $R$ ，公钥 $e$ ， $\gcd(e,(p-1)(q-1))=1$ ，加密

$c=(R+m^3)^e\mod{N}$

$e,R^e$ 和密文都已知，但难以求出 $R^{e-1},...,R$ 。

注意到题中所给 $e=3$ 太小，如果知道至少2个明文密文对，猜测可以构造出其他的多项式值（flag以CyberErudites开头）。

考虑明文 $m_1,m_2$ 和矩阵 $D=\begin{bmatrix}3m_1^3&3m_1^6\\3m_2^3&3m_2^6\\\end{bmatrix}$ 与方程

$\begin{bmatrix}\lambda_1&\lambda_2\end{bmatrix}D=\begin{bmatrix}3m^3&3m^6\end{bmatrix}$

其中 $m$ 是构造明文。

如果 $D$ 有模 $N$ 意义的逆 $D^{-1}$ ，就可以求出 $\lambda_1,\lambda_2$ 。

令 $f(m,R)=3m^3R^2+3m^6R^3$ ，从而

$\begin{aligned} f(m,R)&=3m^3R^2+3m^6R\\ &=(3\lambda_1m_1^3+3\lambda_2m_2^3)R^2+(3\lambda_1m_1^6+3\lambda_2m_2^6)R\\ &=\lambda_1(3m_1^3R^2+3m_1^6R)+\lambda_2(3m_2^3R^2+3m_2^6R)\\ &=\lambda_1f(m_1,R)+\lambda_2f(m_2,R)\\ f(m_i,R)&=(R+m_i^3)^3-R^3-m_i^9=c_i-R^3-m_i^9,i=1,2 \end{aligned}$

所以 $c=f(m,R)+R^3+m^9=\lambda_1(c_1-R^3-m_1^9)+\lambda_2(c_2-R^3-m_2^9)+R^3+m^9$

由于 $p,q$ 都很大， $\det{D}$ 较小（明文是ASCII），于是 $\det{D}$ 应当总是有模 $N$ 逆元，可以大胆求 $D^{-1}$ 。

我选取明文即为'C','y'，然后打表对照输出解密。

python sln.py

CyberErudites{Fr4nkl1n_W3_n33d_an0th3R_S3450N_A54P}

from sage.all import Matrix, IntegerModRing

from message import N, e, ct

def poly(num):

return [(3*pow(num, 3, N)) % N, (3*pow(num, 6, N)) % N]

def v2polyv(v, num):

return (v - R_3 - pow(num, 9, N)) % N

def polyv2v(v, num):

return (v + R_3 + pow(num, 9, N)) % N

def gen(num):

V2 = Matrix(IntegerModRing(N), [poly(num)])

V1 = V2 * T_

v = (poly_C*V1[0][0] + poly_y*V1[0][1]) % N

table[polyv2v(v, num)] = chr(num)

table = {}

R_3 = ct[0]

prefix = b"CyberErudites{}"

T = Matrix(IntegerModRing(N), [poly(int(prefix[0])), poly(int(prefix[1]))])

T_ = T.inverse()

poly_C = v2polyv(ct[1], ord('C'))

poly_y = v2polyv(ct[2], ord('y'))

for num in range(32, 126):

gen(num)

print("".join([table[v] for v in ct[1:]]))

[2022冬季班]《安卓高级研修班(网课)》月薪三万班招生中～

最后于 2小时前被狗敦子编辑，原因：出现了莫名其妙的附件问题

上传的附件：

the_matrix.zip （3.94kb，0次下载）
franklin-last-words.zip （5.91kb，0次下载）

文章来源: https://bbs.pediy.com/thread-274904.htm
如有侵权请联系:admin#unsafe.sh