数论初探--从同余到 RSA

数论初探—从同余到 RSA

secondary

致谢

  • 感谢李老师指出本文关于欧拉函数积性的说明中 $\varphi(ab)=\varphi(a)\cdot\varphi(b)$ 缺少了该性质成立的前提条件 $\gcd(a,b)=1$.
  • 感谢 ajian2002 指出本文的一个 typo.

本文中,将混合出现「C 语言表达式」与数学公式,「C 语言表达式」将使用「特殊的格式」标注.
本文的内容以「乘法逆元」的计算与「RSA」算法的推导为核心.
部分符号说明:

  • 整除 $\mid$
    $\forall a,b\in\mathbb{Z},b\ne0, \exists{c}\in \mathbb{Z},a=bc$ 或者说 a%b==0,则记作 $b\mid a$
  • 最大公因数 $\gcd(a,b)$
    $\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公因数

其余符号将在本文文中说明.

模意义下的运算

模余运算

$\forall a,b,n\in\mathbb{Z}$时,有 $a \bmod n=b \bmod n$ 或者说 a%n==b%n,则称「整数 $a$ 与整数 $b$ 对模 $n$ 同余」 ,记作 $a\equiv b\pmod{n}$

同余还可定义为:$\forall a,b,n\in\mathbb{Z}$ ,若 $n\mid a-b$,则「整数 $a$ 与整数 $b$ 对模 $n$ 同余」 ,记作 $a\equiv b\pmod{n}$

若 「整数 $a$ 与整数 $b$ 对模 $n$ 不同余」,记作 $a\not\equiv b\pmod{n}$

$e.g.$

$3\equiv (-9)\mod 12$

同余的性质

  • $a\equiv a\pmod{n}$

  • $b\equiv a\pmod{n}$

  • 若 $a\equiv b\pmod{n}$ 且 $b\equiv c\pmod{n}$,则 $a\equiv c\pmod{n}$

  • 若 $a\equiv b\pmod{n}$ 且 $c\equiv d\pmod{n}$,则 $a+c\equiv b+d\pmod{n}$

  • 若 $a\equiv b\pmod{n}$ 且 $c\equiv d\pmod{n}$,则 $ac\equiv bd\pmod{n}$

  • 若 $ac\equiv bc\pmod{n}$ 且 $c\neq0$,则 $a\equiv b\pmod{\frac{n}{\gcd(c,n)}}$

  • 若 $a\equiv b\pmod{n}$ ,则 $a^m\equiv b^m\pmod{n}$

    模意义下的乘法逆元

    在有理数乘法中,乘一个数,继续乘这个数的倒数,那么最终的结果就是最初的数.
    $e.g.$

    可以直观的感受出乘 $5$ 和乘 $\frac{1}{5}$ 是相反的两种运算.
    而 $5\times \frac{1}{5}=1$ 也是理所当然的. $\frac{1}{5}$ 便可以理解为 $5$ 的在有理数乘法中的逆元;当然,$5$ 也是 $\frac{1}{5}$ 在有理数乘法中的逆元.
    这个例子并不严谨,但笔者相信,通过这个例子能很好的理解逆元的含义.

此时,考察模意义下的乘法逆元.
和上面一样,在模意义下乘一个数 $a$ 后,如果继续乘另一个 $x$,就能抵消乘 $a$ 所带来的影响,那么 $x$ 就是 $a$ 在模意义下的乘法逆元.
也就能得到 $ax\equiv 1\pmod{n}$ 时,$x$ 就是 $a$ 在模 $n$ 下的乘法逆元.

如何求解乘法逆元将在后文予以说明.

快速幂

为了快速求解 $a^b$ 的问题,降低其时间复杂度,可以通过快速幂的方式进行求解.
根据任何一个数都可用二进制的方式进行表示,那么

又 $\because$

tip
例如:

据此,为了求解 $a^b$ 的值,(假设数据不会溢出)可写出如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
unsigned long long quickPower(unsigned long long a, unsigned long long b)
{
unsigned long long result = 1;
while (b > 0)
{
if (b & 1U)
result *= a;
a *= a;
b >>= 1U;
}
return result;
}

使用快速幂的方式求 $a^b$ 的值,时间复杂度为 $\log_2b$.

快速幂并取余

有些情况下,题目中为了避免数据移除或处理高精度的大数,会只要求幂运算的结果以某个数为模的余数,此时求出最终的结果不是必要的.
在快速幂的运算中,可提前在每步运算中取余,根据同余的性质,易得:

据此,为了求解 $a^b\bmod{n}$,可写下如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
unsigned long long quickPower(unsigned long long a, unsigned long long b, unsigned long long n)
{
unsigned long long result = 1;
while (b > 0)
{
if (b & 1U)
{
result *= a;
result %= n;
}
a *= a;
a %= n;
b >>= 1U;
}
return result % n;
}

快速幂还可通过二分的思路使用递归实现,时间复杂度也为 $\log_2b$ ,但因同规模的数据量下递归实现相较循环实现在函数调用期间开销较大,运行速度较慢性能较差,故此本文不做介绍.

裴蜀定理

定理: $\forall a,b\in\mathbb{Z},ab\ne0$ ,则 $\exists x,y\in\mathbb{Z}$, 使得 $ax+by=\gcd(a,b)$.

线性同余方程

形如 $ax \equiv c \pmod b$ 的方程被称为 线性同余方程.

定理:方程 $ax+by=c$ 与方程 $ax \equiv c \pmod b$ 等价

因此,当求解 $ax \equiv c \pmod b$ 时,常常转化成 二元一次不定方程 $ax+by=c$ 进行求解.

定理:方程 $ax+by=c$ 与二元一次不定方程 $ax \equiv c \pmod b$ 是等价的,有整数解的充要条件为 $\gcd(a,b) \mid c$.

二元一次不定方程

info
$ax+by=c$ 有整数解的充要条件是 $\gcd(a,b)\mid c$.
证明:

  • 充分性
    设 $\gcd(a,b)\mid c$ ,由 裴蜀定理 ,$ax+by=\gcd(a,b)$ 有整数解.设 $c=k\cdot\gcd(a,b),k\in\mathbb{Z},k\neq0$ 则则有
  • 必要性

二元一次不定方程的通解

  • 若 $ax+by=c$ 有解 $(x_0,y_0)$,则其通解为:当 $t$ 为任意整数时,其为 $ax+by=c$ 整数通解.

其中

二元一次不定方程的特解

裴蜀定理 中知,下式有整数解.

对比 $ax_1+by_1=\gcd(a,b)$ 与 $ax+by=c$,易知:

故此,只需出 $ax_1+by_1=\gcd(a,b)$ 的一个特解,即可得 $ax+by=c$ 的一个特解.

扩展欧几里德算法(exgcd)

根据欧几里德算法知:

又 $\because$

$\therefore$

$\therefore$

这便是扩展欧几里德算法的核心.扩展欧几里德算法提供了计算 $ax_1+by_1=\gcd(a,b)$ 的一个特解的一种方式.

扩展欧几里德算法的一种 C 语言描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
int exgcd(int a, int b, int *x, int *y)
{
if (b == 0)
{
*x = 1;
*y = 0;
return a;
}
int gcd = exgcd(b, a % b, y, x);
*y -= a / b * *x;
return gcd;
}

至此,求解线性同余方程的方式描述完毕.

回顾一下,求解线性方程 $ax+by=c$ 的步骤:

  1. 先利用扩展欧几里德算法求解 $ax_1+by_1=\gcd(a,b)$ 的一个特解.
  2. 根据 $ax_1+by_1=\gcd(a,b)$ 与 $ax+by=c$ 的关系,求解 $ax+by=c$ 的一个特解.
  3. 求解 $ax+by=c$ 的通解.

费马小定理

  • 若 $p$ 为素数,$\gcd(a, p) = 1$,则 $a^{p - 1} \equiv 1 \pmod{p}$.

  • $\forall a\in\mathbb{Z}$,有 $a^p \equiv a \pmod{p}$.

当 $p$ 为素数时,常用来求解乘法逆元.
经过十分简单的变换,便可发现:
$\gcd(a, p) = 1$,则 $a\cdot a^{p - 2}\equiv 1 \pmod{p}$.
所以 $a^{p - 2}$ 就是 $a$ 在模 $p$ 下的乘法逆元.
而 $a^{p - 2}$ 的求值,可通过快速幂算法完成.此处不必赘述.

欧拉函数

欧拉函数 $\varphi (n)$ 是小于或等于n的正整数中与n互质的数的数目.[4]

  • 积性
    当 $\gcd(a,b)=1$ 时,

欧拉定理

欧拉定理是费马小定理的推广.
若 $a,n\in\mathbb{Z^+},\gcd(a,n)$,则

欧拉定理也可以用来求乘法逆元.
经过与 费马小定理 类似的变换,即可得到:
若 $a,n\in\mathbb{Z^+},\gcd(a,n)$,则

所以,$a^{\varphi (n)-1}$ 是 $a$ 在 模$n$ 下的乘法逆元.
如何求解 $\varphi (n)$ 本文不做介绍.

RSA 算法

在 RSA 中,密钥对的生成过程中完成了以下步骤:

  • 生成随机数去其中的素数 $p$ 、$q$

  • 记 $n=pq$ 计算 $\varphi(n)$

  • 生成随机数 $e\in(0,\varphi(n))$

  • 根据 $ed\equiv 1\pmod{\varphi(n)}$ 计算 $e$ 的乘法逆元 $d$.

$\varphi(n)$ 如何计算?回顾一下,$\varphi(n)$ 具有积性,也就是说当 $\gcd(a,b)=1$ 时,$\varphi(ab)=\varphi(a)\cdot\varphi(b)$.还有,若 $m$ 为素数,则有 $\varphi(m)=m-1$ .

所以

RSA 算法如何实现加密解密?

众所周知,任何信息或者说数据在计算机中都是以二进制数据的形式存储,当然这也包含欲传递的消息和将其加密后的密文.

根据欧拉定理,当 $n,a\in \mathbb{Z^+}$ 且 $\gcd(n,a)=1$ 时,

一般在简化幂的模运算的时候,当$a$和$n$互素时,可对$a$的指数取模$\varphi(n)$,当$x\equiv y \pmod {\varphi(n)}$

根据上式,有

所以

根据同余的传递性,可知

又根据同余式幂运算的法则可知:

这便实现了消息的加密与解密.

参考资料

1:NickelAngel’s nest. [数学]乘法逆元[G/OL].洛谷. https://www.luogu.com.cn/blog/1239004072Angel/post-shuo-xue-sheng-fa-ni-yuan.
2:维基百科编者. 费马小定理[G/OL]. 维基百科. https://zh.wikipedia.org/zh-cn/费马小定理.
3:维基百科编者. 欧拉定理 (数论)[G/OL]. 维基百科. https://zh.wikipedia.org/zh-cn/欧拉定理
(数论).
4:维基百科编者. 欧拉函数[G/OL]. 维基百科. https://zh.wikipedia.org/zh-hans/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0.
5:oi-wiki编者. 欧拉定理 & 费马小定理[G/OL]. oi-wiki. https://next.oi-wiki.org/math/fermat.
6:oi-wiki编者. 线性同余方程[G/OL]. oi-wiki.https://next.oi-wiki.org/math/linear-equation.
7:oi-wiki编者. 最大公约数[G/OL]. oi-wiki.https://next.oi-wiki.org/math/gcd.
8:oi-wiki编者. 欧拉函数[G/OL]. oi-wiki.https://next.oi-wiki.org/math/euler.
9:oi-wiki编者. 裴蜀定理[G/OL]. oi-wiki.https://next.oi-wiki.org/math/bezouts.

「GKCTF X DASCTF应急挑战杯」 Random

Random

解压题目提供的压缩包,得到了出题人给出的 Python 脚本.其中使用写打开 Random.txt 文件并在其中填充由 Python 的 Random 模块生成的随机数据.

众所周知,在编程中通常使用的是伪随机数, Python 的 Random 模块生成的伪随机数可通过一定方式进行预测或重现.

info
INFO

将随机数的性质分为以下三类:[1]

  • 随机性——不存在统计学偏差,是完全杂乱的数列.
  • 不可预测性——不能从过去的数列推测出下一个出现的数.
  • 不可重现性——除非将数列本身保存下来,否则不能重复相同的数列.

当时笔者想到了两种思路:

  • 根据文件创建时间推测作为 Random 模块默认种子的系统时间的大致范围,并将其可能的取值区间进行遍历.试图找出其使用的随机数种子,并重现其生成的伪随机数.
  • 根据已有输出预测新的随机数.

很明显这两条思路分别利用了不可重现性和不可预测性这两个真随机数应当具有的性质,或者说 Python 的 Random 模块生成的伪随机数具有的缺陷.

由于笔者查找了很久也没弄明白作为默认种子的时间格式,于是尝试思路 2.

通过查找发现 RandCrack 能通过读取前 624 次 random.getrandbits(32) 的结果来预测下一次 random.getrandbits(32) 的结果.

可以看到,出题人给出的脚本中进行 104 次循环,每次循环生成 一个 32 bits 随机数,一个 64 bits 随机数,一个 96 bits 的随机数.如果「1 个 64 bits 的随机数」可以拆成 「2 个 32 bits 的随机数」、「1 个 96 bits 的随机数」可以拆成 「3 个 32 bits 的随机数」.如果假设成立,一个循环也就是生成 6 个 32 bits 的随机数,那么 104 次循环也就是生成 624 个随机数.完美符合 RandCrack 的需求.

完美的像是出题人仿佛为此工具定制的题目一样.这样的巧合,让笔者觉得这绝非偶然,便尝试进行验证.

首先考虑如何拆分数字:
那么最方便的方式就是将字符串转换为 int 后,做位运算进行进行拆分.
笔者以 96 bits 的随机数拆分成低 32 bits 的随机数、中 32 bits 的随机数、高 32 bits 的随机数为例说明:
取 96 bits 的低 32 bits 仅需:

1
n & 0xffffffff

取 96 bits 的中 32 bits 仅需:

1
(n >> 32) & 0xffffffff

取 96 bits 的高 32 bits 仅需:

1
n >> 64

笔者在做题时,写出这段代码远没有此时写 WriteUp 这般自信.因为在 C 语言中,若对 整形变量 n 执行左移或右移操作,如果操作数大于等于 sizeof(n) * 8,那么便会对操作数取 sizeof(n) * 8 的模.

虽然笔者是在用 Python 解题,但 Python 是否允许对一个 int 右移 32 / 64 位,笔者并不确定.
当然最终的测试说明笔者的担心是多余的.

尝试时,会遇到新的问题:
64 bits 的随机数拆成 2 个 32 bits 的随机数,那么自然是高 32 bits 作为一个随机数、低 32 bits 作为另一个随机数.但 RandCrack 每次只能提交一个 32 bits 的随机数,该先提交高 32 bits 的随机数,还是低 32 bits 的随机数? 当然,96 bits 的随机数也同理.

这确实令人感到困惑.

但好在只有两种可能性.尝试后发现需要先提交低 32 bits 的随机数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from randcrack import RandCrack
import io
from hashlib import md5


rc = RandCrack()
file = io.open('random.txt', 'r')


def conversion(x: str):
return int(x[:-1])


def getNumber():
n1 = file.readline()
rc.submit(conversion(n1))
n2 = file.readline()
n2 = conversion(n2)
rc.submit(n2 & 0xffffffff)
rc.submit(n2 >> 32)
n3 = file.readline()
n3 = conversion(n3)
rc.submit(n3 & 0xffffffff)
rc.submit((n3 >> 32) & 0xffffffff)
rc.submit(n3 >> 64)
return


for i in range(104):
getNumber()

value = rc.predict_randrange(0, 4294967295)
value = str(value)
flag = md5(value.encode()).hexdigest()
print(flag)

参考资料

1. 结成浩.图解密码技术[M].第3版.周自恒,译.北京:人民邮电出版社.

在 GNU/Linux 中用 C语言计算文件的 Hash

在 GNU/Linux 中用 C语言计算文件的 Hash

在今日之前,笔者从未想到使用 C/C++GNU/Linux 计算文件的 Hash (例如:SHA-1MD5SHA-256 等)会这样的麻烦.

笔者以为会有 char * sha256sum(int fd)char * sha256sum(FILE *stream) 类似的函数来轻松的获取文件的 Hash .但事实并非如此,获取文件的 Hash 的方法远比笔者想象中的做法要复杂.

方案1 自行实现Hash函数

这种方案是最为麻烦的,但有着不依赖第三方库和程序的优点.至于如何实现 Hash 函数不是本文重点,笔者对此也不做说明.

方案2 调用Openssl

笔者的 openssl 版本为1.1.1i 8 Dec 2020/usr/include/openssl 中提供的头文件可点击下方的小三角查看.

点此查看更多信息aes.h asn1err.h asn1.h asn1_mac.h asn1t.h asyncerr.h async.h bioerr.h bio.h blowfish.h bnerr.h bn.h buffererr.h buffer.h camellia.h cast.h cmac.h cmserr.h cms.h comperr.h comp.h conf_api.h conferr.h conf.h cryptoerr.h crypto.h cterr.h ct.h des.h dherr.h dh.h dsaerr.h dsa.h dtls1.h ebcdic.h ecdh.h ecdsa.h ecerr.h ec.h engineerr.h engine.h e_os2.h err.h evperr.h evp.h hmac.h idea.h kdferr.h kdf.h lhash.h md2.h md4.h md5.h mdc2.h modes.h objectserr.h objects.h obj_mac.h ocsperr.h ocsp.h opensslconf.h opensslv.h ossl_typ.h pem2.h pemerr.h pem.h pkcs12err.h pkcs12.h pkcs7err.h pkcs7.h rand_drbg.h randerr.h rand.h rc2.h rc4.h rc5.h ripemd.h rsaerr.h rsa.h safestack.h seed.h sha.h srp.h srtp.h ssl2.h ssl3.h sslerr.h ssl.h stack.h storeerr.h store.h symhacks.h tls1.h tserr.h ts.h txt_db.h uierr.h ui.h whrlpool.h x509err.h x509.h x509v3err.h x509v3.h x509_vfy.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <openssl/sha.h>
#include <stdio.h>

int main(void)
{
unsigned char result[SHA256_DIGEST_LENGTH];
char *filename = "README.md";

FILE *file = fopen(filename, "rb");
SHA256_CTX hash;

if (file == NULL)
{
perror("fopen");
return 1;
}
SHA256_Init(&hash);

ssize_t size;
unsigned char buf[4096];

while ((size = fread(buf, 1, 4096, file)) != 0)
{
SHA256_Update(&hash, buf, size);
}
SHA256_Final(result, &hash);
for (size_t i = 0; i < SHA256_DIGEST_LENGTH; i++)
{
printf("%02x", result[i]);
}
fclose(file);
return 0;
}

本方案调用了 openssl 提供的 sha.h 比自行实现 Hash函数 能方便一点点.使用本方案的程序在编译时需要使用 -lssl-lcrypto 参数链接相关的库.

方案3 进程间通信调用其他程序

GNU/Linux 中通常含有 sha256sumsha512summd5sum 等程序,并支持以类似 sha256sum <path> 的格式直接调用.那么,就可以使用 popen 函数完成进程间通信,直接获取文件的 Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main(void)
{
FILE *target;
target = popen("sha256sum ~/README.md", "r");
if (target == NULL)
{
perror("popen");
}
char hash[65];
fscanf(target, "%64s", hash);
printf("%s\n", hash);
pclose(target);
return 0;
}

这种方式的好处显而易见「方便」,这种方法是也最容易理解的.

值得多说一句的是:Hash 函数生成的 Hash 是一个由函数决定的常数(例如:SHA-256的结果以字符串输出有 64可打印字符 ),这个特性使得 数组的长度读取的输出长度 是确定的.

测试环境

OS : Arch Linux

Kernel : 5.9.14-arch1-1

openssl : 1.1.1i 8 Dec 2020

gcc : 10.2.0

参考资料

1. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社