密码学是计算机科学中与数学关系比较密切的领域,而当今最重要最流行的加密方式当属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加密算法原理(二)