公钥算法的基本数论知识

公钥密码学中大部分引用了数论的成果，所以必要在介绍RSA密码*之前，详细介绍一下所使用的几个数论的知识点

欧几里得算法

欧几里得算法主要是解决最大公约数问题，记两个正整数$r_0$和$r_1$的$gcd$表示：

\[gcd(r_0,r_1)
\]

在公钥体系中，安全性依赖于大整数的因式分解通常是不可能的。所以人们通常使用一种更有效的算法计算gcd，即欧几里得算法，此算法基于一个简单的观察：

\[gcd(r_0,r_1) = gcd(r_0 - r_1, r_1)
\]

其中，假设$r_0 > r_1$，且二者均为正整数，不难理解：

\[gcd(r_0 - r_1, r_1) = gcd(g · (x - y), g · y) = g
\]

显然地，只要满足$(r_0-mr_1) > 0$，那么可以得到：

\[gcd(r_0, r_1) = gcd(r_0 - r_1, r_1) = gcd(r_0 - 2r_1, r_1) = \cdots = gcd(r_0 - mr_1, r_1)
\]

如果m选择了最大值，则此算法可以表示为：

\[gcd(r_0, r_1) = gcd(r_0\ mod\ r_1, r_1)
\]

事实证明，最终的gcd就是原始问题的gcd，即：

\[gcd(r_0, r_1) = \cdots = gcd(r_i, 0) = r_i
\]

扩展欧几里得算法

扩展欧几里得算法可以用来计算模逆元，不难理解，上文所述的欧几里得算法就是轮询反复互减最终得到结果的，换句话说，可以将这样的反复互减看作是原始两个参数的s倍与t倍相加，即：

\[gcd(r_0, r_1) = s·r_0 + t·r_1
\]

这个等式通常也称为丢番图方程。

可以得到，扩展的欧几里得算法（EEA）：

输入：正整数$r_0$和$r_1$，且$r_0 > r_1$

输出：$gcd(r_0, r_1)$，以及满足$gcd(r_0, r_1) = s·r_0 + t·r_1$的s和t

initialize:

	s[0] = 1

	t[0] = 0

	s[1] = 0

	t[1] = 1

	i = 1

algorithm:

	do

		i = i + 1

		r[i] = r[i - 2] mod r[i - 1]

		q[i - 1] = (r[i - 2] - r[i]) / r[i - 1]

		s[i] = s[i - 2] - q[i - 1] * s[i - 1]

		t[i] = t[i - 2] - q[i - 1] * t[i - 1]

	while r[i] != 0

	return:

		gcd(r[0], r[1] = r[i - 1]

		s = s[i - 1]

		t = t[i - 1]

欧拉函数

在环$Z_m = {0,1,\cdots,m-1}$中，我们感兴趣的问题是在这个集合中，有多少个数字与m互素。

于是我们可以定义欧拉函数来进行计算：

$Z_m$内与m互素的整数个数可以表示为$\Phi(m)$

如果数值非常大的话，将集合内的元素从头到尾都处理一遍，计算每一个的gcd非常慢，对应的欧拉函数值得求解也非常困难，但是，如果m的因式分解是已知的，则存在一个更简单的计算方法：

假设m可以因式分解为一下的数的连乘：

\[m=p^{e_1}_1 \cdot p^{e_2}_2 \cdot \cdots \cdot p^{e_n}_n
\]

其中，$p_i$表示不同的素数，$e_i$表示正整数，则有：

\[\Phi(m)=\prod^n_{i=1}(p_i^{e_i} - p_i^{e_i - 1})
\]

需要强调的是，这种方法来快速计算欧拉函数，我们必须知道m的因式分解，这个特征你刚刚也是RSA公钥方案的核心。

费马小定理与欧拉函数

费马小定理如下描述：假设a为一个整数，p为一个素数，则

\[a^p \equiv a\ (mod\ p) \\ a^{p - 1} \equiv 1 \ (mod\ p)
\]

该定理在密码学中非常有用，其中一个应用就是计算有限域内某个元素的逆元。因为 $a \cdot a^{p - 2} \equiv 1\ (mod\ p)$。但请注意，只有p为素数时，这种反转方法才成立。

将费马小定理的模数推广到任何整数模，即不一定为素数的模，就可以得到欧拉定理：

假设a和m都是整数，且$gcd(a, m) = 1$，则有：

\[a^{\Phi(m)} \equiv 1\ (mod\ m)
\]

这个定理对模数m适用，也适用于整数环$Z_m$内的所有整数。

RSA密码体系

该密码体系是目前最广泛使用的一种非对称密码方案，在实际中常用于以下几个方面：

数据小片段的加密，尤其用于密钥传输
数字签名，譬如Internet上的数字证书

这里必须要注意，RSA加密并不是为了取代对称密码，因为它非常慢。利用RSA通常是用于安全地交换对称密码体系中的密钥。所以RSA通常与对称密码一起使用。

RSA加密与解密

RSA的加密与解密都是在整数环$Z_m$内完成的，模计算发挥了核心作用。

使用公钥进行加密和使用密钥进行解密的方法可以表示为如下：

加密

给定公钥$(n, e) = k_{pub}$和明文$x$，则加密函数为：

\[y = e_{k_{pub}}(x) \equiv x^e\ mod\ n
\]

其中，$x, y \in Z_n$

解密

给定私钥$d = k_{pr}$及密文$y$，则解密函数为：

\[x = d_{k_{pr}}(y) = y^d\ mod\ n
\]