CTF中的RSA及攻击方法笔记总结

本文结合许多当下互联网存在的资料整理出了自己对RSA的一份笔记，本版只是初版哦，对许多东西还有待补充。CTF中的RSA及攻击方法笔记总结很多题目和解题思路相当有用。

本文所有的解题脚本都经过本人亲自尝试，环境都是Python3，用到的Python库是pycrypto和gmpy2两个。

备注：因平台检测C和4连接词，因此改为C四

数论

模运算规则:

模运算与基本四则运算有些相似，但是除法例外。其规则如下:

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a ^ b) % p = ((a % p)^b) % p

结合律：

((a+b) % p + c) % p = (a + (b+c) % p) % p
((a*b) % p * c)% p = (a *(b*c)%p) % p

交换律：

(a + b) % p = (b + a) % p
(a * b) % p = (b * a) % p

分配律：

((a +b)% p * c) % p = ((a * c) %p + (b * c) % p) % p

重要定理：

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
若a≡b (% p)，则对于任意的正整数c，都有(a * c) ≡ (b * c) (%p)