RSA 算法算是比较常见的加密算法了。 一直以来对他的了解不算完全。 借着研究 CTF 的机会,仔细梳理一遍。顺便写写相关代码和推理下过程。

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
2
3
def gcd(a,b):
if(b==0): return a
return gcd(b,a%b)

得到最大公约数即可求解最小公倍数(Least Common Multiple),公式为:

在 C 语言等静态类型语言中,若数据类型为 int,$a*b$ 很容易超范围,因此一般调整顺序,先使用 $a/\gcd(a,b)$ 再乘以 $b$。(此处均为整除,由于 gcd 为其最大公约数,结果也必然为整数)。

Python 的 Math 库中自带 math.gcdmath.lcm 的实现,但是 math.lcmPython 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
2
3
4
5
6
7
def exgcd(a, b):
if b == 0:
return 1, 0, a
else:
x, y, q = exgcd(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y, q

由递推式可得(证明略):

其中, $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/扩展欧几里得算法