在非对称算法出现之前，主流的加密方法是采用对称加密算法（Symmetric-key algorithm）的加密模式，也就是通信双方采用同种加解密规则并分享共同密钥，而密钥的保存和传输又形成了新的信息安全问题。

1976年，美国的两位计算机学家 Whitfield Diffie 和 Martin Hellman提出了一种新型加密构思一一加解密可以使用不同规则，只要这两种规则存在某种对应关系，这样可以避免关键密钥的直接传输。这种算法思想被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。

RSA 是在1977年由三个提出者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的姓氏首字母组成的。从那时起，RSA 算法一直是最广为使用的"非对称加密算法"。

图1 - Adi Shamir、Ron Rivest、Leonard Adleman

互质关系：如果两个正整数，除了 1 以外，没有其他公因子，称这两个数是互质关系。如8和9，虽然它们不是质数，但没有除1外的公因子，因此它们是互质关系。

欧拉函数：任意给定正整数n，在小于等于n的正整数之中，计算有多少个数能与n构成互质关系的函数，用φ(n)表示。如小于等于8的正整数之中，8形成互质关系的是1、3、5、7，所以φ(8) = 4。

欧拉函数推论：

① 一个因数n，其欧拉函数等于它的两个因子对应的欧拉函数值相乘。即n = p*q，那么φ(n) = φ(q) * φ(p)；

② 因为小于质数p的所有正整数都与p互质。所以根据欧拉函数定义易得质数p的欧拉函数等于质数本身减一，即 φ(p)=p – 1.

模反元素：两个正整数a和n互质，那么一定可以找到整数b，满足a*b / n = 1；那么称b是a关于n的模反元素。 

1. 设定两个不同质数p和q；

2. 使q乘p得到一个数n；

3. 求出n对应欧拉函数的值 r，因为n= p * q，根据欧拉函数的推论，n的欧拉函数值是φ(n) = φ(q) * φ(p)，又因为p和q是质数，所以φ(p)=p – 1、φ(q)=q – 1，所以φ(n) =(p-1)*(q-1)；

4. 接着求一个数e，取e大于1小于r，且 e 和 r 为互质数，那么（e, n）就是公钥。

5. 接着求e关于 r 的模反元素为d，即 d 满足 e 和 d 的乘积对 r 取模得到的余数是1，得到的（d, n）就是私钥

加密：设明文是m，根据公钥（e, n）对明文m加密，使m的e次方再对n取模得到的余数就是密文c，即c = me % n.

解密：设密文是c，根据私钥（d, n）对密文c解密，使c的d次方再对n取模得到的余数就是明文m，即m = cd % n.

公钥（e，n）是公开的，而私钥（d，n）是私密的，若要对密文进行破解，关键要知道密钥中的d。我们知道d是e关于r的模反元素，e是公开的，而 r 的取值又跟两个质数相关，所以要知道密钥就需要知道两个质数p和q，而要知道p和q就要对n进行因式分解，当p和q足够大时，以现在的技术很难在短时间内对n因式分解求出p和q，所以RSA加密算法安全性相对较高。

但如今存在基于量子计算机的量子算法--Shor算法（又称量子质因数分解演算法，Peter Williston Shor提出），其相比于传统算法对于的大整数因数分解问题是有指数级的加速效果。但由于量子计算机应用的限制该算法暂时受到局限，或许未来量子计算机发展成熟后，利用该算法会对RSA造成巨大的威胁。

图2 - Peter Williston Shor