RSA 加密算法: 原理推演以及相关代码实现
2022-06-01 把之前学习算法中扩展欧几里得的部分替换了进去。
RSA 算法简介
RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特(Ron Rivest)、阿迪 · 萨莫尔(Adi Shamir)和伦纳德 · 阿德曼(Leonard Adleman)一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。
我主要参考下面两个视频以及维基百科对 RSA 的基本原理做了简单的推理。 基本就是跟着视频对路子整理下思路。 毕竟这方面我也没啥底子。
RSA 基本原理
这部分基本复刻上面第一个视频的过程。
根据数论,寻求两个大质数比较简单,而将它们的乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。[1]
计算 $3^3 \ \mathrm{mod} \ 7$ 很简单:$3^3=27$ ,$27/7=3\cdots6$。
但当 $3^x \ \mathrm{mod} \ 7$ 去求解 $x$ 时,就只能遍历获取。当数字大到一定程度,对模运算求逆基本是不可行的。
因此不妨设
即使用 $e$ 为密钥,对 $N$ 取余数,以对 $m$ 加密 求出密文 $c$。
于是也可以想到,会有一个 $d$ 作为密钥对他进行解密。即:
两式可以化为(具体过程为还不太会,以后再补充。):
通过这个式子,我们就可以通过 $e$ 和 $d$ 的选取,来对 $m$ 进行加密。
那么,如何选取呢?看到这个形式后,接下来需要引入欧拉定理。
欧拉定理是这样的一条定理:
即 $a$ 的 $\varphi(n)$ 次方 模 $n$ 的值为 $1$,其中 $\varphi(n)$ 为欧拉函数。
对上面的定理左右取 $k$ 次幂,再同乘以 $a$ ,可以化为:
这与 $\ref{1}$ 是不是有点相似?
令他们左侧指数部分相等,则易得:
因此,我们可以通过对 $k \ n \ e$ 的取值来计算解密所用的密钥 $d$ 。
对于自然数 $n$ ,欧拉函数 $\varphi(n)$ 等于其在$1,2,3\cdots n-1$ 中与 $n$ 互为质数的自然数个数。 [2]
然而,求一个数的欧拉函数值,即对 $n$ 做质因数分解,在大数上被视为计算上不可能的。
但是,对于质数 $p$ ,存在 $\varphi(p)=p-1$ 。因此我们选取一个质数时,计算就会变得容易很多。
同时我们也有,若 $p$ 与 $q$ 互质,且均为质数,则存在$\varphi(pq)=\varphi(p) \varphi(q) = (p-1)(q-1)$ 。
这样我们的计算就相对容易了很多。
整理一下我们已经有的式子:
我们自己试试[3]。 $M$ 的 ASCII 码为 $77$,我们令 $m = 77$ (message)。
任选两个质数 $p = 107 , q = 109$。 计算$n = 107 \cdot 109 = 11663$ 。 $\varphi(n) = (106)(108) = 11448$
任选整数 $e = 2345 $ 符合 $e$ 与 $\varphi(n)=11448$ 互质,$1<e<11448$ 。
将 $e, \varphi(n)$ 带入 $d = \dfrac{k(p-1)(q-1)+1}{e}$,得:
求出其的一组解即可,二元一次方程的整数解求解,采用扩展欧几里得算法(gmpy2.gcdext(2345,-11448)
)。具体流程下一部分说明。不管怎样我们求出:
于是我们就有了加密用的公钥
:$(e,n)$ 和 解密用的私钥:$(d,n)$。
加密试试:
我们得出密文 $2635$ 。
接着我们尝试解密:
得回结果。
你也可以在 这个网站 尝试一下这个过程。
扩展欧几里得算法
欧几里得算法
即辗转相除法,用于求解两个数 $a$,$b$ 的最大公因数(Greatest Common Divisor)。公式表示为:
程序的递归实现中,首先要确定好递归边界,即:$b=0$ 时代表已经除尽,程序结束,应输出 $a$,即:
1 | def gcd(a,b): |
得到最大公约数即可求解最小公倍数(Least Common Multiple),公式为:
在 C 语言等静态类型语言中,若数据类型为 int,$a*b$ 很容易超范围,因此一般调整顺序,先使用 $a/\gcd(a,b)$ 再乘以 $b$。(此处均为整除,由于 gcd 为其最大公约数,结果也必然为整数)。
Python 的 Math 库中自带 math.gcd
与 math.lcm
的实现,但是 math.lcm
是 Python 3.9
后才加入的,许多平台目前都未到达该版本。
若求多个值的 $\gcd$ 或 $\operatorname{lcm}$ ,可以先求出前两部分再作为下一个因子与后面的值进行计算。
扩展欧几里得算法
裴蜀定理
我们先引入裴蜀定理,他可以简单表示为:若 $a,b$ 为整数,一定存在 $x,y$ 满足下式(裴蜀等式):
而扩展欧几里得算法,即是在计算 $\gcd$ 的前提下,求解 $x,y$ 的算法。
我们可以简单推导一下他,前文中我们得到了:
不妨将 $b,a\%b$ 带入裴蜀等式的 $a,b$,即:
此处 $x,y$ 与原式不同,所以我们表述为:$x_0,y_0$。
又由欧几里得算法,这个式子与裴蜀等式仍然相等,所以我们有:
又有:$a\%b = a-(a/b)*b$(此处除法为整除向下取整),可得:
整理可得:
对比等号左右关系,我们有:
确定好边界情况,仍是 $b=0$ 时,这时:
此时 $x = 1$ ,为了方便,不妨让 $y = 0$。
因此,我们可以类似于前文写出他的递推函数式:
1 | def exgcd(a, b): |
由递推式可得(证明略):
其中, $x$ 的最小整数解为: $
\left(
x\% \dfrac{b}{\gcd} + \dfrac{b}{\gcd}
\right)\%\dfrac{b}{\gcd}
$
特别地,当 $\gcd(a,b)=1$,即 $ax+by=1$ 时,有:
求解 $ax+by = c$
上一部分中,我们求出了 $ax+by = gcd(a,b)$ 的解。 那么如何求解 $ax+by=c$ 呢?观察他们的区别仅在一个 $gcd(a,b)$ 。
那么我们首先假设 $ax+by = gcd(a,b)$ 有一组解 $(x_0,y_0)$。
两侧同乘以 $\dfrac{c}{\gcd}$。就可以有 $a\dfrac{c}{\gcd}x_0 + b\dfrac{c}{\gcd}y_0 = c$。
于是可以得到 $ax+by = c$ 的一组解即:
类似于上部分的原理(证明略),可以得出 $ax+by=c$ 的解:
其中, $x$ 的最小整数解为
特别地,当 $\gcd(a,b)=1$,即 $ax+by=1$ 时,有:
同余式 $ax \equiv c \pmod m$ 的求解
同余式: 若 $(a-b)\% m = 0$ 则我们称 $a$ 与 $b$ 模 $m$ 同余,记作:$a \equiv b \pmod m$。
因此 $ax \equiv c \pmod m$ 也可以表述为:$(ax-c)\%m = 0$。简单来说就是 $ax-c$ 为 m 的整数倍。
因此存在一个整数 $y$ 满足:$ax-c = my$。 移项后得 $ax-my=c$,由于 $y$ 可以为任意整数,所以也可以写为:$ax + my = c$
这样就把同余方程化为了我们前面熟悉的形式。
优化:中国剩余定理
以后有机会再写。
参考文献
- [1] 廖滨华著. 网络知识与应用[M]. 2014
- [2] (俄)波拉索洛夫著;叶思源译. 代数、数论及分析习题集[M]. 哈尔滨:哈尔滨工业大学出版社, 2017.01.
- [3] RSA 算法的加密原理是什么? https://www.zhihu.com/question/25038691/answer/388573650
- [4] https://zh.wikipedia.org/wiki/扩展欧几里得算法