RSA 加密算法原理（一）

密码学是计算机科学中与数学关系比较密切的领域，而当今最重要最流行的加密方式当属 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\mathrm{\perp }b$。例如：25 和 15 有非 1 的公因子 5，因此它们不互素；16 和 7 没有除 1 以外的公因子，因此它们互素。

欧拉函数

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

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

乘法逆元

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

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

欧拉定理

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

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

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

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

RSA 加密算法原理（二）