RSA算法是一种广泛使用的公开密钥加密算法。1977年由Ron Rivest、Adi Shamir和Leonard Adleman提出。2002年，他们三人共同获得了图灵奖。

RSA算法是最流行的公开密钥算法，也是最容易理解和实现的。目前还没有攻击RSA算法的可靠方式。RSA算法的安全性基于对极大整数做因数分解的难度。只要采用足够长的公钥，用RSA加密的信息实际上是不能破解的（1999年实现了512比特公钥的暴力破解）。用于快速因数分解的量子算法（Shor算法），目前还只是停留在理论阶段，具体实现还早得很。

RSA算法的流程如下：

1. 选择两个很大的质数p和q

2. 计算乘积n=pq

3. 随机选择一个小奇数e（不一定是质数），与$\phi(n)=(p-1)(q-1)$互质

4. 计算e模$\phi(n)$的乘法逆d（$ed = 1 \ mod \ \phi(n)$）

5. RSA公开密钥就是数对P=(e,n)，私钥就是数对Q=(d,n)

6. 加密 $c= m^e  \ mod \ n$ （m是明文，c是密文）

7. 解密 $m= c^d  \ mod \ n$

随便找本讲加密算法的书，都应该有这些内容，包括数学证明。也会有一些例子，例如《应用密码学》就给出了(p=47,q=71)的例子，而《量子计算和量子信息》把(p=3,q=11)作为习题（用来加密“QUANTUM”）。

最后做两个习题，算是娱乐吧。

确定公钥和私钥

p=3

q=11

p*q=33

(p-1)*(q-1)=2*10=20

e=3 与20互素

d=7

所以公钥就是(3,33)，私钥就是(7,33)

给QUANTUM编码。按照字母表的顺序，Q=17，U=21，A=1，N=14，T=20，U=21，M=13。

计算密文

明文是Q=17

17^3 (mod 33)=29

密文就是29

恢复明文

29^7 (mod 33)=17

明文就是17=Q

用类似方法，可以计算其他字母的密文并恢复其明文。

U 21 【21^3 (mod 33)=21，29^7 (mod 33)=21】

A 01 【1^3 (mod 33)=1，1^7 (mod 33)=1】

N 14 【14^3 (mod 33)=5，5^7 (mod 33)=14】

T 20 【20^3 (mod 33)=14，14^7 (mod 33)=20】

U 21 【21^3 (mod 33)=21，29^7 (mod 33)=21】

M 13 【13^3 (mod 33)=19，19^7 (mod 33)=23】

3和11太小了，没有意思。换个大一些的质数玩玩吧。

从质数表里随便找两个质数

p=1237

q=2539

计算pq

p*q=1237*2539=3140743

为选择公钥和私钥做准备

(p-1)*(q-1)=1236*2538=3136968=8*392121=8*9*43569=8*9*9*4841=8*9*9*47*103=(2^3)*(3^4)*47*103

欧拉函数是

[(2-1)*2^2]*[(3-1)*3^3)]*(47-1)*(103-1)=4*54*46*102=1013472

选择公钥

e=41

与(p-1)*(q-1)互质

计算私钥（这里利用了上面的欧拉函数值）

d=918137

因为41^1013472 (mod 3136968)=1

计算得到，41^1013471 (mod 3136968)=918137

具体计算过程（利用windows自带的科学计算器）

41^101 (mod 3136968)=391601

391601^100 (mod 3136968)=3005161

3005161^100 (mod 3136968)=3120289

41^3471 (mod 3136968)=1210985

3120289*1210985(mod 3136968)=918137

因此，公钥就是(41,3136968)，私钥就是(918137,3136968)

加密明文 Q =17

17^41 (mod 3140743)=150572

解密

150572^918137 (mod 3140743)=17

具体过程（利用windows自带的科学计算器）

150572^918 (mod 3140743)=2784875

2784875^1000(mod 3140743)=2459448

150572^137 (mod 3140743)=1787715

2459448*1787715 (mod 3140743)=17

加密明文UAN=210114（因为现在的密码很长，可以加密不止一个字符）

210114^41 (mod 3140743)=1746134

解密

1746134^918137 (mod 3140743)=210114

具体过程（利用windows自带的科学计算器）

1746134^918 (mod 3140743)=1992844

1992844^1000(mod 3140743)=1413562

1746134^137 (mod 3140743)=2909887

1413562*2909887 (mod 3140743)=202114

加密明文 TUM=202113

202113^41 (mod 3140743)=336879

解密

336879^918137 (mod 3140743)=202113

具体过程

336879^918 (mod 3140743)=1792236

1792236^1000(mod 3140743)=177322

336879^137 (mod 3140743)=299424

177322*299424 (mod 3140743)=202113

【1】《应用密码学：协议、算法与C源程序》，Bruce Schneier 著，吴世忠 祝世雄 张文政 等译，机械出版社，2000年

【2】《量子计算和量子信息（一）：量子计算部分》，Michael A. Nielsen, Isaac L. Chuang 著，赵千川 译，清华大学出版社，2003年

质数表

https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0%E8%A1%A8/7085686?fromtitle=%E7%B4%A0%E6%95%B0%E8%A1%A8&fromid=1240801&fr=aladdin

RSA算法

https://baike.baidu.com/item/RSA%E7%AE%97%E6%B3%95/263310?fromtitle=RSA&fromid=210678&fr=aladdin