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

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$ 。

接着我们尝试解密:

得回结果。

你也可以在 这个网站 尝试一下这个过程。

扩展欧几里得算法

之前学 C 语言的时候就接触了欧几里得算法,也就是辗转相除法。 是用于求解最大公约数的方法。大概思路是:以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数

既然前面提到了 C 语言,我们就用 Python 来演示下:

1
2
3
4
def gcd(a, b):
while a != 0:
a, b = b % a, a
return b

他的计算公式也可以表示为:$gcd(a,b) = gcd(b,a \ \mathrm{mod} \ b)$

那么什么是扩展欧几里得算法呢?顾名思义,他就是欧几里得算法的扩展 ,即在保留原有功能——求最大公约数的前提下,扩展了其他功能,即可以求解贝祖等式 $ax+by=gcd(a,b)$ 的一个整数解。也就是我们上式所需要计算等内容。

这里不给出他的具体细节,只给出一个 Python [4] 实现,另外,也可以直接调用gmpy2.gcdext

1
2
3
4
5
6
7
8
9
10
11
12
13
def ext_euclid(a, b):
old_s, s = 1, 0
old_t, t = 0, 1
old_r, r = a, b
if b == 0:
return 1, 0, a
else:
while(r!=0):
q = old_r // r
old_r, r = r, old_r-q*r
old_s, s = s, old_s-q*s
old_t, t = t, old_t-q*t
return old_s, old_t, old_r

优化:中国剩余定理

RSA 算法相关涉及数学知识暂时超出我的范围,以后有机会再写。

参考文献

  • [1] 廖滨华著. 网络知识与应用[M]. 2014
  • [2] (俄)波拉索洛夫著;叶思源译. 代数、数论及分析习题集[M]. 哈尔滨:哈尔滨工业大学出版社, 2017.01.
  • [3] RSA 算法的加密原理是什么? https://www.zhihu.com/question/25038691/answer/388573650
  • [4] https://zh.wikipedia.org/wiki/扩展欧几里得算法