近期的一些比赛的一些题目,VMCTF2024,SEKAICTF2024,京津冀长城杯2024,ByteCTF-2024
ez_RSA
DASCTF 2024金秋十月
一道简单的RSA
1 | from Crypto.Util.number import * |
第一部分参考维纳攻击:
1 | num3 = continued_fraction(Integer(e) / Integer(n)) |
可以通过判断(素数,大小在512 bit)来筛选出分子,分母,也即num1,num2
第二部分e1,e2,比较小,half gcd 来做
exp:
1 | from Crypto.Util.number import * |
2024VMCTF
RSA
1 | from Crypto.Util.number import * |
分析
enc = M**e
,矩阵的e次方
这类题目之前见过
多维矩阵下的线性群阶
查:GL(n,Fp)群阶的研究 | Tover’s Blog
正常做法:
1 | C = Matrix(Zmod(n),c) |
这里我们并不能分解n,所以并不能这样解
1 | M = matrix(Zmod(n), [ |
将矩阵M拆成一个反对称矩阵和单位矩阵的和形式:
M = A+mE
1 | A = matrix([ |
就有 $C=M^e=(A+mE)^e$
按二项式定理展开:
测试发现 A的偶次幂是个对角矩阵,所以说C的非对角线元素都是A的奇次幂贡献的
1 | PR.<m,p,q> = PolynomialRing(ZZ) |
用A的小数次幂去factor一下非对角线元素的因子,会发现这些和式均有共同因子:
1 | PR.<m,p,q> = PolynomialRing(ZZ) |
我们再看非对角线元素其他位置上的关系:
1 | PR.<m,p,q> = PolynomialRing(ZZ) |
所以可以从中提取几组代数关系求解:
1 | (m + 2*p)*enc[1,0] == (m + p + q)*enc[2,0] |
模n下用 Groebner
解方程
exp:
1 | from Crypto.Util.number import * |
K-Cessation
描述:
1 | K-Cessation |
附件
1 | from typing import List,Union,Literal |
加密的原理我们并不难理解,但需要我们找到细节规律
密文第一个是3,说明wheel里面1,2是相同的,且与3相反,密文第二个是5,说明wheel里面 4,5,6,7是相同的,且与8相反,不是0就是1,我们只需足够多的密文来确定足够多的相同的位置,就能确定wheel
exp:
1 | ct = [2, 1, 1, 3, 1, 1, 3, 2, 1, 4, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 3, 1, 6, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 3, 2, 1, 1, 3, 1, 1, 1, 3, 4, 1, 3, 1, 2, 2, 4, 2, 5, 1, 1, 1, 3, 2, 1, 4, 2, 2, 1, 2, 1, 3, 1, 1, 1, 1, 1, 2, 3, 1, 2, 1, 1, 1, 1, 3, 4, 1, 2, 2, 4, 2, 5, 1, 2, 1, 2, 2, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 4, 3, 1, 2, 1, 3, 1, 3, 3, 2, 1, 3, 1, 6, 2, 1, 1, 2, 1, 2, 1, 3, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 2, 3, 1, 1, 4, 1, 3, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 5, 2, 4, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 3, 1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 5, 1, 1, 1, 3, 1, 1, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 1, 1, 4, 3, 1, 3, 4, 1, 1, 1, 2, 1, 3, 1, 6, 1, 2, 1, 1, 3, 2, 3, 1, 2, 2, 1, 3, 2, 1, 2, 2, 2, 3, 3, 3, 1, 1, 2, 4, 1, 1, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 2, 1, 2, 1, 1, 1, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 4, 2, 1, 4, 2, 4, 2, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 2, 1, 3, 1, 1, 2, 3, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 3, 1, 2, 3, 4, 4, 3, 2, 4, 2, 1, 4, 2, 4, 1, 2, 1, 3, 1, 2, 1, 1, 1, 3, 2, 1, 2, 2, 2, 3, 3, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 4, 2, 1, 4, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 4, 2, 1, 4, 1, 1, 1, 1, 2, 4, 4, 3, 2, 4, 2, 1, 1, 1, 1, 1, 1, 1, 4, 2, 2, 3, 1, 1, 1, 2, 1, 3, 1, 4, 1, 2, 4, 1, 2, 3, 4, 1, 3, 1, 1, 1, 2, 4, 1, 1, 1, 4, 1, 1, 4, 2, 1, 4, 2, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 4, 3, 3, 4, 4, 3, 2, 4, 2, 1, 1, 3, 2, 4, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 1, 1, 4, 3, 3, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 1, 1, 4, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 4, 3, 1, 1, 1, 1, 3, 4, 3, 1, 1, 4, 1, 6, 2, 1, 1, 1, 3, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 3, 1, 1, 5, 4, 1, 2, 2, 4, 1, 6, 1, 2, 1, 1, 3, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 4, 2, 2, 3, 1, 2, 3, 1, 3, 4, 1, 1, 3, 4, 2, 5, 1, 1, 1, 3, 2, 2, 3, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 3, 3, 3, 1, 1, 2, 1, 3, 3, 1, 1, 4, 2, 5, 2, 4, 1, 2, 4, 1, 2, 1, 2, 1, 1, 1, 2, 3, 1, 2, 4, 1, 1, 4, 4, 1, 1, 2, 3, 2, 4, 2, 5, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 2, 1, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 1, 1, 1, 2, 4, 2, 1, 1, 3, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 3, 1, 2, 3, 1, 6, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 1, 1, 2, 1] |
佩服,转换成了一个多项式矩阵解
1 | from typing import List,Union,Literal |
reference:
2024-WMCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)
2024WMCTF | DexterJie’Blog
京津冀长城杯2024
RandomRSA
1 | import gmpy2 |
next_prime ,两个数相差不大,可以采取爆破
拆开后是一个一元二次方程 (通过爆破k1,k2)
借助一下dexter师傅写的脚本,自己写的要跑两三个小时,借助多线程也要跑半个多小时🥲🥲
(多进程学习一手)
不用多线程跑全程也才10分钟,flag不到四分钟就出了,借助多线程更是秒出
exp:
1 | from tqdm import * |
Matrix
matrix.sage
1 | import random |
flag2.enc
1 | n = 10 |
LWE,这段时间出现过很多次了
看着代码复杂,但该有的条件一个不缺,decrypt 也是直接给了
注意一下 dumps 和 loads
1 | dumps 函数: |
exp:
1 | from Crypto.Util.number import * |
以下两道后面有机会再继续看,最近有点忙,先鸽了
SEKAICTF2024
*Some Trick
Bob and Alice found a futuristic version of opunssl and replaced all their needs for doofy wellmen.
Author: deut-erium
1 | import random |
ByteCTF-2024
*magic_lfsr
1 | from Crypto.Cipher import AES |