CTF密码学小结

embedded/2024/12/22 16:33:13/

感觉没啥好总结的啊

基础的永远是RSA、流密码、哈希、对称密码、古典密码那一套（密码学上过课都会），其他的就是数论的一些技巧

似乎格密码也很流行，以及一些奇奇怪怪的性质利用也很多

1、random设置种子后随机的性质：同一个种子生成同一个序列，如果把生成的序列中的某个数又作为种子，这样迭代生成的序列，只与第一条序列的种子相关

2、gcd(c,n)=gcd(c%n,n)，ab%(ac) = a*(b%c)

3、yafu工具分解质因数，78位数分解约使用3分钟，非常好的工具，集成了试除法、fmt、pollar_rho、ecm等各种各样质因数分解方法，并且做了许多并行计算的优化，相当高效。

yafu-x64 "factor(@)" -batchfile 1.txt

把数字放在1.txt中，用换行隔开就可以了，注意末尾也需要是换行

4、一些有用的python函数和Crypto.Util.number库函数

str与字节编码串互相转换：（把‘abcd’转成b‘abcd’）a = a.encode()，a.decode()

长整数与字节编码串转换：long_to_bytes和bytes_to_long

bin(x)转换为二进制串（是str类型的，前面有0b开头）（注意二进制串的+是连接操作）

int(x,r)把字符串x按照r进制换算为数值

hex(x)获取十六进制的字符串

快速幂pow、求逆元inverse、GCD这些都是常用数论函数

5、数论的一些定理

$a^{ \varphi(n)} \equiv 1(\text{mod} n)$ (a,n互质)

20200601数论总结-CSDN博客

6、gmpy2使用iroot（x,r）对x开r次方,sympy使用sqrt_mod可以求二次剩余

7、看到数据范围小的一般是可以用于枚举的

8、RSA已知n和p+q就可以算出φ（n）

9、格理论

对一组线性无关的向量，他们的整数倍的线性组合构成一个格，这组向量称为格基

SVP问题，就是求格中范数最小的向量，CVP问题，就是给定一个向量，求格中的向量离他距离的最小值。复杂的都是O(a^k)级别的（a是常数，k是格基的大小（一般和向量维数相近））

格的基本区域：格基向量线性组合时，系数只为0、1时构成的集合，大小为2^k