[原创]GDGAlgiersCTF2022密码学复盘-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创]GDGAlgiersCTF2022密码学复盘

发表于: 2022-10-28 10:45 10339

[原创]GDGAlgiersCTF2022密码学复盘

狗敦子

2022-10-28 10:45

10339

两道矩阵相关的题，在这里整理一下。

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

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

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

AES的初始向量已知，因此需要求 $p r i v$ 。

令 $D = T d i a T^{-}$ ，有

$d i a g_{D}^{p r i v} = T^{-} P T$

设 $d i a = d i a g (,, . . .,), T^{-} P T = d i a g (,, . . .,)$ ，则

$p r i v \equiv m o d, i =,, . . .$

其中是对 $p$ 的阶。

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

由于 $\leq p r i v \leq p -$ ，猜测可以唯一确定 $p r i v$ 。

计算之后发现， $d i a = d i a g (,,,,, . . .,)$ ，不是 $p -$ 就是。

于是我选取 $λ =$ ，此时 $δ = p -, p r i v = (p -)$ 直接唯一确定。

python sln.py

CyberErudites{Di4g0n4l1zabl3_M4tric3s_d4_b3st}

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

$c = (R + m)^{e} m o d N$

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

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

考虑明文 $,$ 和矩阵 $D = []$ 与方程

$[] D = []$

其中 $m$ 是构造明文。

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

令 $f (m, R) = m R + m R$ ，从而

所以 $c = f (m, R) + R + m = (- R - m) + (- R - m) + R + m$

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

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

python sln.py

CyberErudites{Fr4nkl1n_W3_n33d_an0th3R_S3450N_A54P}

# from sage.all import *

import json

from Crypto.Hash import SHA256

from Crypto.Cipher import AES

from Crypto.Util.Padding import pad
 

p = 12143520799543738643
# def read_matrix(file_name):
#     data = open(file_name, 'r').read().strip()
#     rows = [list(eval(row)) for row in data.splitlines()]
#     return Matrix(GF(p), rows)
#
#
# D = read_matrix('matrix.txt')
# P = read_matrix('public_key.txt')
# digD ,A = D.diagonalization()
# digP = A.inverse() * P * A
# vD = [digD[i][i] for i in range(12)]
# vP = [digP[i][i] for i in range(12)]
# print(f"vD = {vD}")

vD = [37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2]
# print(f"vP = {vP}")

vP =

[6751925379844785295, 11256715989719283883, 4551561838026472495, 11383130904596697638,

8534299476177021992, 11184828239802784209, 7103104085280766875, 1622643043767580331, 

11104789109564474465, 1502559189506368871, 522368022672629021, 1590703325067650792]
# G = GF(p)
# K = discrete_log(G(vP[11]), G(vD[11]))
# print(f"K = {K}")

K = 7619698002081645976
 
# now we can decipher

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)
# CyberErudites{Di4g0n4l1zabl3_M4tric3s_d4_b3st}