密码学是计算机科学中与数学关系比较密切的领域，而当今最重要最流行的加密方式当属RSA加密，其应用领域非常广泛，从银行卡密码的加密到WEB数字签名等等都有其用武之地。本文将简单讲述这方面的历史与数学背景。

相关历史

历史上，有一种加密模式曾非常流行，即对称加密。（当然目前对称加密仍是一种重要的加密方法，被应用于许多加密数据量较大的场景）

所谓“对称加密”，也就是指下面这个过程：

  1. A与B约定一种加密规则
  2. A将信息加密，将密文发给B
  3. B应用约定的规则，对密文直接解密得到明文

这里约定的规则被称为“密钥”，这种加密方式有它的优势，即加密速度快。但劣势也很显著：“密钥”需要在联络者之间进行传递，这也造成了不安全的因素，第三方若拦截了密钥，也就破译了信息。因此顺应历史潮流，1976年，一种新的加密理念诞生了：

  1. 先由B生成两把密钥，分别是公钥和私钥，公钥，如其名，是公开的，任何人都可以获取；而私钥则由B进行保管。
  2. B将公钥发送给A，A将信息用公钥进行加密，将密文发送给B。
  3. B用私钥将密文进行解密得到明文。

随意从百度拿了个图

这也被称为“非对称加密”。

当然，一个思维正常的人肯定会发问：既然密文是由公钥加密得到的，那为什么不能反过来用公钥对密文解密？

这确实是一件值得研究的事，如何设计一种算法来使公钥可以对信息进行加密但却无法解密呢？（“非对称”三字正是体现在这一点上）

在非对称加密这种理念提出的第二年，也即1977年，有三位数学家Ron Rivest、Adi Shamir 和 Leonard Adleman设计了一种算法，可以实现非对称加密，并将这种算法以他们三个人的名字命名，叫做RSA算法，这种算法目前为止被认为无解（或在不知道私钥的情况下破解时间超过可承受限度）。以下将从数学角度讲解该算法的原理。

数论基础

该算法涉及到一点基本数论知识，先简单提一下。

互素

互素是指两个正整数的一种关系，若两个正整数 $a$ 和 $b$ 除1外没有共同的因子，则称a和b有互素的关系，也记为 $a \bot b$。例如：25和15有非1的公因子5，因此它们不互素；16和7没有除1以外的公因子，因此它们互素。

欧拉函数

定义欧拉函数 $\phi(n) 为小于n$的正整数当中，与 $n$ 互素的数的个数。

例如，因为在1-9中，与10互素的数有：1,3,7,9这四个，因此 $\phi(10)=4$。

乘法逆元

若正整数 $a$ 与 $b$ 关于正整数 $n$ 满足以下条件：

那么称 $a$ 与 $b$ 互为（在 $\mathbb{Z}_n$ 中的）乘法逆元（$\mathbb{Z}_n$ 称为模 $n$ 剩余类乘群）。

欧拉定理

欧拉定理是关于欧拉函数的一个定理，它是指：

若 $n$ 与 $a$ 互素，那么：

举一个例子：取 $n=5,a=4$，那么 $\phi(5)=4,4^4=256\equiv 1 \pmod{5}$，成立，证明过程需要用到一点群论知识，简单来说就是 $\phi(n)$ 是 $\mathbb{Z}_n$ 的阶，而 $a,n$ 互素保证了 $a$ 在这个群里，那么 $a$ 自乘群的阶数次必然得到单位元也就是1。

以上是RSA算法所涉及到的全部数论基础知识。

RSA加密算法原理（二）