RSA简介

RSA是一种算法，并且广泛应用于现代，用于保密通信。

基本原理为单向陷门函数，即满足如下的三个条件：

  1. 正向计算容易。
  2. 在不知道私钥的情况下，反向计算不可行。
  3. 在知道私钥的情况下，反向计算容易。

具体加密算法：

  1. 选取两个大素数p和q，两个数位数接近且相差较大。
  2. 计算n = p*q，φ(n) = (p-1)(q-1)。
  3. 随机选取整数e，满足gcd(e,φ(n)) = 1，作为公钥。
  4. 计算私钥d，满足d*e ≡ 1 (mod φ(n))，即d是e模φ(n)的逆元。CTF的角度看就是，d是由e,p,q可以求解出的。

一般CTF就是把我们想要获得的flag作为明文，RSA中表示为m。然后通过c = pow(m,e,n)加密，得到密文，RSA中表示为c。
如果知道私钥d，则可以通过m = pow(c,d,n)进行解密。

在实际应用中，n，e是公开的，但是由于n一般是两个大素数的乘积，所以我们很难求解出d，所以RSA加密就是利用现代无法快速实现大素数的分解，所存在的一种安全的非对称加密。

加解密程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import gmpy2
from Crypto.Util.number import *


def encode():
    m = bytes_to_long(b'flag{XXXXXXXXXX}')
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001    # 视具体题目而定
    c = pow(m, e, n)
    print("p =", p)    # 一般保密
    print("q =", q)    # 一般保密
    print("n =", n)
    print("e =", e)
    print("c =", c)


def decode(p, q, n, e, c):
    phi = (p - 1) * (q - 1)
    d = gmpy2.invert(e, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print(flag)


通过上面的内容我们可以知道要想解密一段密文，我们需要c，d，n三个值。其中c我们是知道的，而n和d都可以通过p，q，e算出来，e我们一般也是知道的，也就是说常规的rsa题目我们的解题思路就是想想怎样把p和q求出来，并以此进行解密。

攻击方法

已知p、q

略。

分解n得到p、q

适用情况：n已知且可因式分解

既然n = p*q，那么最常规的想法就是把n因式分解得到p，q，上面说n很难分解，但对于一些不太大的n，我们可以借助 在线因式分解网站 或 yafu 去分解它。
如果密钥的长度小于等于256位,一台较快的电脑可以在几个小时内成功分解其因子。

解密程序见上文。

低加密指数攻击

适用情况：n很大但是e很小，一般e=3

n很大时我们就不能因式分解了，但是当e很小时，比如e=3，有c = m^e+kn，我们可以对k进行爆破，直到c-kn可以开根，借此得到m。

维护中，未完待续…

参考资料

https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_theory/
https://blog.csdn.net/qq_46145027/article/details/125047313
https://www.freesion.com/article/8945408137/
https://www.freebuf.com/vuls/257835.html
https://skysec.top/2018/09/15/浅析RSA-Padding-Attack/
https://www.iacr.org/archive/pkc2005/33860001/33860001.pdf
https://www.cnblogs.com/nLesxw/p/learn_math_rsa.html

篇幅有限，不完全列举。如以上文章作者认为此博客有侵权行为或不合理的引用之处，请联系我修改。