公钥密码数学基础

整数概论¶

整除性¶

整除：设\(a,b,m\)均为整数，若存在某个\(m\)使得\(a=mb\)成立，则称非零数b整除a。b整除a通常用b|a表示。

因子：若\(b|a\)，并且\(a\)为正整数，我们说\(b\)是\(a\)的一个因子。

最大公因子¶

两个正整数\(a,b\)的最大公因子，记为\(c=gcd⁡(a,b)\)

\(c\)是满足\(c|a\)且\(c|b\)的最大整数，即\(c\)能整除\(a\),也能整除\(b\)。

对于任何正整数\(a\), \(gcd⁡(a,0)=a\)

如果\(a,b\)是互素的(relatively prime)，则\(gcd⁡(a,b)=1\)

素数¶

整数\(p>1\)是素数，当且仅当它只有因子\(1\)和\(p\)。
基本定理：任何整数a>1都可以唯一地因式分解为

\[a=p_1^{e_1}\times p_2^{e_2}\times \cdots p_k^{e_k}\]

其中\(p_i\)是素数，\(e_i\)是\(p_i\)在\(a\)中出现的次数。

模运算¶

\(a \pmod{n}\)将整数a映射到集合\(\{0,1,⋯,n−1\}\)，在这个限制集合上进行的算术运算，称为模运算

定义\(Z_n\)为比\(n\)小的非负整数组成的集合：

\[Z_n={0,1,⋯,(n−1)}\]

这个集合称为剩余类集，或模n的剩余类(residue classes mod n)。

离散对数¶

本原根¶

如果\(a\)是\(n\)的本原根，则\(a^1,a^2,…,a^φ(n)\)是各不相同的，且均与\(n\)互素。即\(a\)模\(n\)的整数幂\(a^1,a^2,…,a^φ(n)\)能产生模\(n\)的非零整数集

离散对数¶

对于素数\(p\)，\(a\)的1到(p-1)的各次幂恰好可以产生1到p-1的整数，对任何一个整数b，有唯一的幂i使得

\[b\equiv a^i\pmod{p}\quad (1\leq i\leq p-1)\]

该指数i称为\(a\)在模\(p\)下的离散对数，记作\(dlog_{a,p}(b)\)。

离散对数问题(DLP)¶

给定\(b∈Z_p^∗\), 本原根a, 素数p, 计算i使得\(b≡a^i (mod p)\)是非常困难的(尤其p很大时)。

\(a^i≡b(mod p)\)是一个单向函数(one-way function)

经典算法¶

欧几里得算法¶

设𝑎,𝑏是任意两个正整数，则有\(gcd(a,b)=gcd(b,a \pmod{b})\)

扩展欧几里得算法¶

在公钥密钥学中有着重要应用，可以用于计算乘法逆

不仅可以可以计算出最大公因子d，而且可以计算出两个整数\(x,y\)，使得\(ax+by=d=gcd(a,b)\)

x和y一定具有相反的正负号

素性检测（Miller-Rabin算法）¶

TEST(n)算法流程：

输入整数\(k,q\)，其中\(k>0\)，q为奇数，使得\((n-1=2^kq)\)
选择\(a\)，\(1\leq a\leq n-1\)
计算\(a^q\pmod{n}\)
如果\(a^q\pmod{n}=1\)，则输出“n可能是素数”
否则For j=0,1,2,…,k-1，如果\(a^((2^j)*q)\pmod{n}=n-1\)，则输出“n可能是素数”
返回合数

MR算法的概率性：如果n通过素性检测，n也有可能不是素数

关键定理¶

费马小定理¶

如果\(p\)是素数，\(a\)是正整数并且不能被\(p\)整除，则

\[a^{p-1}\equiv 1\pmod{p}\]

另一种表示形式为

\[a^p\equiv a\pmod{p}\]

该形式不要求a和p互素

欧拉定理¶

若\(a\)与\(n\)互素，则

\[a^{\varphi(n)}\equiv 1\pmod{n}\]

中国剩余定理¶

《孙子算经》的“物不知数”问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

该问题用方程组表示为：

\[\begin{cases} A\equiv 2\pmod{3}\\ A\equiv 3\pmod{5}\\ A\equiv 2\pmod{7} \end{cases}\]

中国剩余定理(CRT)：设\(m_1,\dots m_k\)是两两互素的正整数，\(M=\prod_{i=1}^k m_i\)，求一次同余方程组

\[\begin{cases} a_1\pmod{m_1}\equiv A\\ a_2\pmod{m_2}\equiv A\\ \dots\\ a_k\pmod{m_k}\equiv A \end{cases}\]

对模M有唯一解，令\(M_i=M/m_i\)，则

\[A=\sum_{i=1}^k M_ie_ia_i\pmod{M} \equiv(M_1e_1a_1+M_2e_2a_2+\dots+M_ke_ka_k)\pmod{M}\]

其中\(e_i\)满足\(M_ie_i\equiv 1\pmod{m_i}\)