NKCTF2023
笔者以星盟安全团队成员的身份参与了本次比赛，在队内师傅们的共同努力下队伍取得了不错的成绩
队伍排名：4
文章仅就密码方向进行分享。
Crypto
完成度：12/13
一血数：6
baby_RSA
题目
1 | from Crypto.Util.number import * |
题解
dp泄漏分解P、Q
coppersmith解m
$P = m^p \mod n = m \mod p = m+k_1p$
$Q = m^q \mod n = m \mod q = m+k_2q$
$P \cdot Q=m^2+m(k_1p+k_2q)+k_1k_2n=m^2+m(P-m+Q-m) \mod n$
1 | import gmpy2 as gp |
ez_math
题目
1 | from Crypto.Util.number import getPrime, bytes_to_long |
题解
找到合适数据求出Kphi
$6^{2B}≡6^A \mod n, 2B!=A$，则$2B ≡ A \mod phi, 2B-A=kphi $
Kphi当phi解出明文m
1 | import gmpy2 |
ezRSA
题目
1 | from Crypto.Util.number import * |
题解
- 已知phi分解n,常规rsa求解flag1
- 通过m1确定m2比特位，最后用baby_RSA的coppersmith解法再解一次m2
已知phi分解n
1 | from math import gcd |
coppersmith解法再解一次m2
1 | import gmpy2 |
real_MT
题目
1 | import random |
题解
MT19937相关的经典内容大杂烩，参考badmonkey师傅博客
1 | import gmpy2 |
fake_MT
题目
基本如上，差别是用的py2
题解
出题人预期的非预期解是利用py2的input能当eval用。
如下是非预期的预期解：
1 | import gmpy2 |
ez_polynomial
题目
1 | #sage |
题解
常规的多项式rsa。
没了解过的话，可以去lazzaro师傅博客里翻一翻
1 | import gmpy2, libnum |
eZ_Bl⊕ck
题目
1 | from Crypto.Util.strxor import strxor as xor |
题解
手动浅推一下，会发现r加密和flag加密后的“格式”是一致的，所以两者对应分段异或能消去key
在不具体推理其余变量的情况下，可以直接尝试异或所有可能分段，即解
1 | from Crypto.Util.strxor import strxor as xor |
easy_high
题目
1 | from Crypto.Util.number import * |
题解
通过p0能得到p高位以及p低444位数据，设p中间位，coppersmith求解后即可rsa解密得到flag
1 | import libnum, gmpy2 |
eZ_LargeCG
题目
1 | from gmpy2 import next_prime |
题解
原题，参考https://blog.csdn.net/m0_51507437/article/details/124205732
- p-1/p+1光滑分解n
- 矩阵快速幂
1 | import libnum |
complex_matrix
题目
1 | from Crypto.Util.number import * |
题解
西湖论剑2021原题，参考https://www.ctfer.vip/note/set/51
1 | import gmpy2 |
baby_classical
题目
1 | import string |
题解
矩阵逆运算（chatgpt写的）恢复key，然后再恢复flag
1 | import string |
Raven
题目
1 | #!/usr/bin/env sage |
题解
起初见到这题，一直在想是否存在不用格的巧妙解法，有些本能的回避格了。
最后无可奈何了才想着用格来解决这类似门限方案的问题。
问题核心如下:
定义函数：$f(x) = ax^3+bx^2+cx+d \mod p$
记getPrime(256)为t，题目给出p、四组x以及对应的$f(x_i)^2+t_i \mod p$， 即：
$$
\begin{aligned} y_i &= f(x_i)^2+t_i \\ &= a^2x_i^6+2abx_i^5+(b^2+2ac)x_i^4+(2bcd+2ad)x_i^3+(c^2+2bd)x_i^2+2cdx_i + d^2 + t_i \mod p \end{aligned}
$$
也即：
$$
\begin{aligned} a^2x_i^6+2abx_i^5+(b^2+2ac)x_i^4+(2bcd+2ad)x_i^3+(c^2+2bd)x_i^2+2cdx_i + d^2 -y_i +kp &= -t_i \end{aligned}
$$
起初如下构造了格：
$$
\begin{bmatrix} d^2 & 2cd & c^2+2bd & 2bcd+2ad & b^2+2ac & 2ab & a^2 & 1 &k_1 & \cdots & k_4 \end{bmatrix} \begin{bmatrix} x_1^0 & \cdots & x_4^0 \\ x_1^1 & \cdots & x_4^1 \\ \vdots & \cdots & \vdots \\ x_1^6 & \cdots & x_4^6 \\ -y_1 & \cdots & -y_4 \\ p \\ & \ddots \\ & & p \end{bmatrix} = \begin{bmatrix} -t_1 & -t_2 & -t_3 & -t_4 \end{bmatrix}
$$
格构造的特别狭长，结果当然是规约失败了。
现想来这种非满秩的矩阵，LLL规约效果等效于用0填充成方阵后的效果。
赛时来不及细想，想起之前赛事第一次遇见门限方案时，我是用crt解的，其后看到hash师傅的格解法，没细究。
这次卡住了便再去学习了格的构造，最后得到：
$$
\begin{bmatrix} d^2 & 2cd & \cdots & b^2+2ac & 2ab & a^2 & 1 &k_1 & \cdots & k_4 \end{bmatrix}
\begin{bmatrix} 1 & & & & x_1^0 & \cdots & x_4^0 \\ & \ddots & & & \vdots & \vdots & \vdots \\ & & 1 & & x_1^6 & \cdots & x_4^6 \\ & & & 2^{256} & -y_1 & \cdots & -y_4 \\ &&&&p \\ &&&&& \ddots \\ & &&&&& p \end{bmatrix}
=
\begin{bmatrix} d^2 & 2cd & \cdots & b^2+2ac & 2ab & a^2 & 2^{256} &-t_1 & \cdots & -t_4 \end{bmatrix}
$$
（还是生疏，说来就是一开始的格忘记加单位矩阵了…）
本地实际测试，发现得到的$d^2$不太准确。
但$a^2,2ab,2cd$都是准确的，那么就可以间接求出d了。
再接下来就是常规的AES解密，总exp如下：
1 | import libnum, gmpy2 |
PsychoRandom (Unsolved)
题目
task.py
1 | #!/usr/bin/env python |
utils.py
1 | class ToyGen: |
题解
差这道AK密码也因此队伍无缘总分第一，有些遗憾。
但反思起来，无论是平日知识学习还是赛事训练确实都或有意无意的回避流密码。
也没啥好回避的，学！
比赛的最后阶段，瞪了这题四小时，赛时也发现了如下这点
$$
out = \sum\limits^{n} _ {i=1} (s_i \oplus b_i) \& a_i = (\sum\limits^{n} _ {i=1} s_i \& a_i) \oplus (\sum\limits^{n} _ {i=1} b_i \& a_i)
$$
($\sum \limits^{n} _ {i=1} (s_i \oplus b_i) \& a_i$表示 s的第i位 与 b的第i位 异或 后再与 a的第i位进行 与运算 再把i从1到n的结果在GF(2)上求和)
记$\sum\limits^{n} _ {i=1} s_i \& a_i$为out’，则:
$$
out’ = \sum\limits^{n} _ {i=1} s_i \& a_i = out \oplus (\sum\limits^{n} _ {i=1} b_i \& a_i) = out \oplus 1
$$
(题目中a, b固定，能计算确定$\sum\limits^{n} _ {i=1} b_i \& a_i=1$)
赛时到这一步便卡死了，确实发现异或beta的效果等效于不异或的结果取反，但不知道如何用多组 每刷新37次状态再给出的out 来恢复某一时刻的状态。
看到官方wp思路用的是矩阵，也释然了。
其实能想到要用矩阵、多项式来描述、求解问题，但平时只做理论学习没怎么实际训练，赛时会不敢想、不敢用。
实际代码编写，再学习Van1sh师傅博客相关内容就行。
求解所有可能seed（初始状态）
1 | # SageMath |
求解flag
1 | import os, utils |
写在最后
星盟安全团队纳新！
欢迎师傅们加群（346014666）学习、讨论！
