0x00前言

最近我翻阅了许多CTF的题目，现在密码学题目都有至少一道题与RSA有关，那RSA到底是什么？RSA为什么会受欢迎，它具有什么特点？借此文章复习下RSA有关的知识

0x01含义

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

它是非对称加密，那什么是非对称加密？我们都知道普通的加密方法称为对称加密，即一段明文通过一串密钥序列加密成密文，而密文也可以通过这串加密序列还原为明文，这就是对称加密。假设明文是M，密钥是S，密文是Q，那么M->S->Q，同样反过来Q->S->M。

而RSA也同样存在密钥，只不过把密钥分为了公钥和私钥，什么意思呢？就是在RSA算法中，明文通过公钥加密成了密文，而密文不能通过公钥还原为明文，而是通过私钥反推回明文。

RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。1983年麻省理工学院在美国为RSA算法申请了专利。

0x02算法原理

RSA的算法涉及三个参数，n、e1、e2。其中，n是两个大素数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。e1和e2是一对相关的值，e1可以任意取。

0x03过程推演

1、取较大素数p，q

2、取一个n=p*q

3、随机取加密密钥e（也就是公钥），也必须和（p-1）和（q-1）互质，用欧拉函数取得解密秘钥d（也就是私钥）

​ d=e^-1 mod (p-1)(q-1)

4、设A为明文，B为密文

​ A=B^d mod n

​ B=A^e mod n

其标准公式为：

​ c = m^e mod n

其中c为cipher密文，m为message明文，e是公钥，n是密钥长度，n=p*q

e值

最常用的三个e值：3, 17, 65537(2^16+1).

0x04Python代码实现

import gmpy2
from binascii import a2b_hex, b2a_hex

str=b'this is a rsa'
p = 4903571     #素数
q = 4903579     #素数
n = p*q         #求积
print(n)
e = 65537   #随机取加密指数

d = gmpy2.invert(e, (p - 1) * (q - 1))  #获得密钥:d=e^-1 mod (p-1)*(q-1)
c = pow(int(b2a_hex(str), 16), e, n)   #使用明文与公钥转换成密文c
print(c)

#n=24045047780609
#c=9698011943914

上述python代码中，需要用到必需库有gmpy2，a2b_hex，b2a_hex，gmpy2是一个C编码的Python扩展模块,它支持多精度算法。

其他两个库是用来将字节流转换为16进制数