密码学中的数论

Author Avatar
source. 12月 16, 2020
  • 在其它设备中阅读本文章

一群人找呀找,突然发现:最初等的数论很适合用于设计密码。

费马小定理

Fermat’s little theorem

若 $a$ 是一个整数,$p$ 是一个素数,那么:

若 $a$ 不是 $p$ 的倍数,即满足 $\gcd(a,p)=1$,那么:

欧拉函数

Euler’s totient function

欧拉函数 $\varphi(n)$ 是小于等于 $n$ 的正整数中,与 $n$ 互素的数的个数。

希腊字母 $\varphi$ 读作 phi

  • $\varphi(1) = 1$
  • 若 $p$ 为素数,则 $\varphi(p)=p-1$
  • 若 $p$ 为素数,则 $\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}$
  • 若 $\gcd(m,n)=1$,则 $\varphi(m\times n)=\varphi(m)\times\varphi(n)$

一般公式:

  • 若 $n=p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{r}^{k_{r}}$,
  • 则 $\varphi(n)=\prod_{i=1}^{r} p_{i}^{k_{i}-1}\left(p_{i}-1\right)$ 。

推导:

  • 欧拉函数 $\varphi(n)$ 是小于等于$n$的正整数中,与 $n$ 互素的数的个数。
  • 若 $n=1$,小于等于它的正整数只有 $1$,且 $\gcd(1,1)=1$,所以 $\varphi(1)=1$。
  • 若 $n$ 为素数,因为 $n$ 与小于它的任何正整数都是互素的,所以 $\varphi(n)=n-1$。
  • 若 $n=p^k$,其中 $p$ 为素数,此时当一个数不是 $p$ 的倍数时,它与 $n$ 互素。$[1,n]$ 中共有 $n=p^k$ 个正整数,其中 $p$ 的倍数有 $p,2\cdot p,\dots,p^{k-1}\cdot p$,共 $p^{k-1}$ 个,所以 $\varphi(n)=p^k-p^{k-1}=p^{k-1}(p-1)$。
  • 若 $\gcd(m,n)=1$,根据中国剩余定理,$\mathbb{Z}_n^{\ast}$ 和 $\mathbb{Z}_p^{\ast}\times \mathbb{Z}_q^{\ast}$ 构成一一映射,所以 $\varphi(m\times n)=\varphi(m)\cdot \varphi(n)$。

所以,对于 $n=p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{r}^{k_{r}}$,其中 $p_1,p_2,\dots p_r$ 为互不相同的素数,由以上推导可知,$\varphi(n)=\prod_{i=1}^{r} p_{i}^{k_{i}-1}\left(p_{i}-1\right)$。

实际上就是 $n$ 的简化剩余系(也称既约剩余系缩系,reduced residue system,符号为 $\mathbb{Z}_n^{\ast}$)中的元素个数。

欧拉定理

Euler’s theorem

若正整数 $n,a$ 互素(即 $\gcd(n,a)=1$),那么:

其中,$\varphi(n)$ 为欧拉函数。

素性检验

常用 Miller-Rabin 算法。

米勒-拉宾素性检验 - 维基百科

两个基础理论:

  • 费马小定理:若 $p$ 为素数,$\gcd(a,p)=1$,则 $a^{p-1}\equiv 1\pmod{p}$ 。
  • 二次探测定理:若 $p$ 是一个素数,$0<x<p$,则方程 $x^2\equiv 1\pmod{p}$ 的解为 $x\equiv 1\pmod p$ 或 $x\equiv p-1\pmod{p}$ 。

二次探测定理的证明

若 $p$ 为素数,那么 $p\mid (x+1)$ 或 $p\mid (x-1)$ 成立。所以 $x\equiv 1\pmod{p}$ 或 $x\equiv p-1\pmod{p}$ 。

若 $p$ 不是素数,则不一定成立(可能因数会被拆到两项中)。

Miller-Rabin算法

要测试一个奇数 $n\ge 3$,可将 $n-1$ 表示为:

其中,$s$ 和 $d$ 都是正整数,且 $d$ 是奇数。

在每次测试开始时,随机选一个整数 $a$ ,$1<a<n-1$。

若满足以下条件的一种,则判定 $n$ 有可能是素数:

其中,$r=0,~1,\dots,~s-1$。(注意:只要其中有一个 $r$ 使得②式成立,则判定 $n$ 有可能是素数)

Q: 你说它有可能是素数,具体的概率是多大?

A: 一次测试判定为有可能是素数的概率是小于 $1/4$ 的,那么通过 $t$ 次测试($a$ 取不同值)都判定为有可能是素数的概率是小于 $(1/4)^t$ 的。因此,通过多次测试,则有很大把握说 $n$ 是素数。

原理

将 $n-1$ 分解为 $2^sd$,其中 $d$ 为奇数。

根据费马小定理,若 $n$ 为素数,则 $a^{n-1}\equiv a^{2^sd} \equiv 1\pmod{n}$ 成立。

根据二次探测定理,若 $n$ 为素数,则对于以下数列:

最后一个数要为 $1$,且每一个数都是前一个数的平方,因此下面两条必有一条是正确的:

  • 数列的第一个数为 $1$,那么其后的所有数都为 $1$。
  • 数列中($a^{2^s d}$之前)有一数为 $n-1$,那么其后的所有数都为 $1$。

Q: 直接检测 $a^{2^s d}\bmod n=1$ 是否成立不香吗?干嘛还要这么麻烦?

A: 少年,我们要的是效率!你想想看是不是计算低次幂比高次幂更快。

伪代码

MR(n)
    分解n-1 = 2^{s}d
    随机选择整数a,1<a<n-1
    if a^{d} mod n = 1
        return 有可能是素数
    for j = 0 to s-1
        if a^{2^{j}d} mod n = n-1
            return 有可能是素数
    return 是合数

例子:判断29是不是素数

对于一个素数 $n=29$,有 $n-1=28=2^2\cdot 7=2^s d$,得到 $s=2,~d=7$ 。

第一次测试,选择一个数 $a=10$。

计算$10^7\bmod 29=17$,既不为$1$也不为$28$。

计算$(10^7)^2\bmod 29=28$,因此返回「有可能是素数」。

第二次测试,选择一个数$a=2$。

计算$2^7\bmod 29=12$,既不为$1$也不为$28$。

计算$(2^7)^2\bmod 29=28$,因此返回「有可能是素数」。

扩展欧几里得算法求模逆

TODO

计算复杂度:$O(\log^3 n)$

Python 3.8+ 可原生求模逆:

pow(9, -1, 29)

中国剩余定理

Chinese Remainder Theorem, CRT

有一同余方程组:

有解的条件:若模数 $m_1,~m_2,\dots,~m_n$ 两两互素,则该同余方程组有解。

Q: 不满足两两互素怎么办?

A: 想办法让它们两两互素!

令 $M$ 为所有模数的乘积,即 $M=m_1\times m_2\times\cdots\times m_n$,设 $M_i=M/m_i$。

设 $M_i^{\prime}$ 为 $M_i$ 模 $m_i$ 的乘法逆元,即$M_i^{\prime}=(M_i^{-1}\bmod m_i)$。

在模 $M$ 的意义下,方程组只有一个解:

注意,最后解出来是在模 $M$ 的意义下!

CRT 可用于提高 RSA 解密速度,因为解密指数 $d$ 通常很大,要计算 $m=c^d\bmod n$,可以把模数 $n$ 拆为 $p\times q$,结合欧拉定理可以较快计算 $c^d\bmod p$ 和 $c^d\bmod p$,然后 CRT 回去就是 $m$ 了。

原根、离散对数问题

原根、生成元、本原根,都是一个意思。

Primitive root modulo $n$

若 $a$ 是 $n$ 的本原根,则 $a$ 的 $1$ 到 $(n-1)$ 各次幂(模 $n$)恰能生成 $1$ 到 $(n-1)$ 的每个数。且每个数仅出现一次。

形象地说,假设 $a$ 是 $n$ 的一个本原根,那么:

是:

的一种排列。

因此,(在模 $n$ 下)对任意整数 $b$ 和 $n$ 的本原根 $a$,有唯一的幂 $i$ ($0\le i\le p-1$)使得:

那么指数 $i$ 称为以 $a$ 为底(模 $n$)的离散对数,记为 $\operatorname{dlog}_{a,p}(b)$ 。

  • $\operatorname{dlog}_{a,p}(1)=0$
  • $\operatorname{dlog}_{a,p}(a)=1$

只有形如 $2,~4,~p^l$ 或 $2p^l$ 的数才有原根,其中 $p$ 为任意奇素数,$l$ 是正整数。$34$ 以内的数的原根列表:

$n$ $n$ 的原根 周期$=\varphi(n)$
2 1 1
3 2 2
4 3 2
5 2, 3 4
6 5 2
7 3, 5 6
9 2, 5 6
10 3, 7 4
11 2, 6, 7, 8 10
13 2, 6, 7, 11 12
14 3, 5 6
17 3, 5, 6, 7, 10, 11, 12, 14 16
18 5, 11 6
19 2, 3, 10, 13, 14, 15 18
22 7, 13, 17, 19 10
23 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 22
25 2, 3, 8, 12, 13, 17, 22, 23 20
26 7, 11, 15, 19 12
27 2, 5, 11, 14, 20, 23 18
29 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 28
31 3, 11, 12, 13, 17, 21, 22, 24 30
34 3, 5, 7, 11, 23, 27, 29, 31 16

离散对数表举例:要求以 $2$ 为底,模为 $19$ 的离散对数表。

先打出下表:

$i$ $2^i\bmod 19$
1 2
2 4
3 8
4 16
5 13
6 7
7 14
8 9
9 18
10 17
11 15
12 11
13 3
14 6
15 12
16 5
17 10
18 1

交换两列,以 $a$ 升序排列,可以得到以 $2$ 为底,模为 $19$ 的离散对数表:

$a$ $\operatorname{dlog}_{2,19}(a)$
1 18
2 1
3 13
4 2
5 16
6 14
7 6
8 3
9 8
10 17
11 12
12 15
13 5
14 7
15 11
16 4
17 10
18 9

考虑方程:

给定 $g,~x$ 和 $p$,可直接计算出 $y$,换句话说,正向过程是容易计算的。

但是,给定 $y,~g$ 和 $p$,计算 $x$ 非常困难,即「离散对数」困难问题。

应用:

  • Diffie-Hellman
  • ElGamal

再度

image

(失踪人口回归)

小学的时候,老师总和我们说:好记性不如烂笔头

教员曾说过:实践是检验真理的唯一标准。

经过十多年的求学生涯的实践检验,我可以推断这句话没毛病。

因为对密码学中的基础知识有做一定记录,所以即使忘了,还可以翻翻博客和笔记温习。

不过对于数论,我就基本没留下什么痕迹,故可以说我也在试图通过本文弥补这方面遗憾吧。

本科时候学的很浅的《信息安全数学基础》让我一度有数论学得很好的自信。不过好像其他学校信安也没多学什么。

然而随着时间的推移,以前很熟悉的知识都忘了或不太熟练了。反映了写笔记的重要性。

对于素性检验中最常用的 Miller-Rabin 算法,之前把算法背过,但对原理比较模糊,于是花了好长时间重新学习,弄清原理。我原来觉得很一般的书(主要是觉得中文版带一股翻译腔,且缺失很多重要内容)《密码编码学与网络安全——原理与实践》竟发挥了重要作用。

将笔记写在博客上,有什么好处呢?我想了想,主要有三个:

  • 只要能联网,就能查看之前的笔记;
  • 方便他人学习,同时受到他人检验;
  • 留下痕迹,积攒回忆。

感谢来自熟悉或是陌生的人的鼓励。

8AC193CFD4FC7E73506F223FA47F19A7

IMG 5211(20201216 231005)

image

D596316F5A41D41C937729D0EAF6C548

37B77222915D57CFF70B53E15BB7E83E

7B32FC42E3069ADBBFF8E5E036052CDB

image

从2018年4月本站上线到现在(2020年12月16日),一共积攒了12k+的浏览量:

image

(数据看起来还不错呀)

随手翻阅以前做的笔记,感觉以前对知识的理解确实要比现在要好。

这离不开反复搜寻资料和推导加深理解,更离不开老师的循循善诱。

真的觉得我现在的文字能力变弱了。(怀古伤今)

但是,要相信,会越来越好哒!要以乐观主义的心态面对生活,要相信明天一定比今天更好。

就让时间去检验一切吧!(很巧的是实践恰好与时间谐音)

I’m an old physicist. I’m not afraid of death. I’m afraid of time.

禁止商业用途,非商业分享转载请注明来源。
本文链接:http://comydream.github.io/2020/12/16/num-theory-crypto/