什么是RSA

RSA算法是应用最广泛的公钥密码算法。

1977年，RSA算法由MIT的罗纳德 · 李维斯特（Ron Rivest）、阿迪 · 萨莫尔（Adi Shamir）和伦纳德 · 阿德曼（Leonard Adleman）共同设计，于1978年正式发布，以他们三人的首字母命名。

在这之前所用的对称加密方式只采用一个密钥，知道加密密钥就可以知道解密密钥。但是由于双方需要事先约定加密的规则，就导致没有办法安全地交换密钥，建立安全的传递通道。

但是1976年出现的非对称加密算法的思想就可以解决密钥的交换和存放问题。它使用两个密钥，一个用来加密消息和验证签名，叫公钥，另一个用来解密，叫私钥，加解密双方是不平等的。这种新的构思是由美国计算机科学家Whitfield Diffie和Martin Hellman提出的，被称为Diffie-Hellman密钥交换算法，RSA算法就是受到它的启发产生的，是这种构思的具体实现方式，既可以用来加密，解密，也可以用于密钥交换。

RSA主要使用大整数分解这个数学难题进行设计，巧妙地利用了数论的概念，如今，只有短的 RSA 密钥才有可能被强力方式解破。

算法步骤

可以通过以下步骤生成一个公钥/私钥对：

1.随计选择两个不相等的质数p，q
2.计算它们的乘积N=p*q
3.计算欧拉函数φ(N)=(p-1)(q-1)，N的二进制长度作为密钥的长度，
4.随机选择一个加密密钥e,这里1<e<φ(N),gcd(e,φ(N))=1
5.根据以下公式求解得到解密密钥d
ed=1 mod φ(N)，0≤d≤N
6.发布加密密钥：(e,N)
7.保密解密密钥：(d,N)

实例

在实际应用中e和N都是大整数，为了方便理解，下面选取非常小的整数来实现一次密钥生成过程。

1.随机选择两个质数

p=17 ，q=11

2.计算它们的乘积

N=p*q=17×11=187

3.计算欧拉函数

φ(N)=(p-1)(q-1)=16×10=160

4.选择e，e是与φ(N)互质的整数，且1<e<φ(N)

e=7

5.决定d

d*e=1 mod φ(N)且d<φ(N)
23×7=160+1
d=23

6.得到公钥(7,187)

7.得到私钥(23,187)

用途

生成了公钥和私钥，就可以用来加密和解密了。

1.发送方加密消息M
拿到对方的公钥e和N后，计算C = M^e mod N,这里0≤M<N,将C作为密文发送给接收方；
例如M=88，C=88^7 mod 187=11

2.接收方解密密文C
拿出自己的私钥d和N，计算M=C^d mod N， 得到原消息M=11^23 mod 187=88