数论基础
Dan Boneh课程中数论基础笔记，该部分内容用于构建以下密码学相关部分：
- Key Exchange Protocols
- Digital Signatures
- Public-Key Encryption
- 数论基础
Notation (Greek times)
本文中，\(N\) 指代一个正整数，\(p\) 指代一个质数。
\[\mathbb{Z}_N = \lbrace 0,1,2,\dots,N-1 \rbrace \]Greatest Common Divisor 最大公约数
\(\gcd(x,y)\) 是 \(x\) 与 \(y\) 的最大公约数。
存在如下事实：
对于所有的整数 \(x,y\) ，总存在整数 \(a,b\) 使得：
\[a \cdot x + b \cdot y = \gcd (x,y) \]在已知 \(x,y\) 的前提下，我们可以通过扩展欧几里得算法(Extended Euclidean Algorithm)高效地找出 \(a,b\) 的值。
Relatively Prime 互质
如果 \(\gcd(x,y)=1\) ，我们称 \(x\) 和 \(y\) 是互质(relatively prime)的。
Modular Arithmetic 模运算
在 \(\mathbb{Z}_n\) 中，模运算加法和乘法的基本性质仍然满足。
Modular Inversion 模逆元
Definition：
\(x\) 在集合 \(\mathbb{Z}_N\) 中的逆元是集合 \(\mathbb{Z}_N\) 中的一个元素 \(y\)，满足 \(x \cdot y \equiv 1 \pmod N\)，\(y\) 记作 \(x^{-1}\)。
例如假设 \(N\) 是一个奇数，则集合 \(\mathbb{Z}_N\) 中 \(2\) 的逆元是 \(\frac{N+1}{2}\)。
Lemma：
\(\mathbb{Z}_N\) 中的元素 \(x\) 有逆元，当且仅当 \(\gcd(x,N)=1\) 。
Proof：
\[\begin{align*} \gcd(x,N)=1 &\Rightarrow \exists a,b:a\cdot x + b \cdot N=1 \\ &\Rightarrow a \cdot x \equiv 1 \pmod N \\ &\Rightarrow x^{-1} \equiv a \pmod N \\ \gcd(x,N)>1 &\Rightarrow \forall a: \gcd(a\cdot x, N)>1 \\ &\Rightarrow a \cdot x \not \equiv 1 \pmod N \end{align*} \]\(\mathbb{Z}_N^\ast\)
Definition:
\[\begin{align*} \mathbb{Z}_N^\ast &= \lbrace set\ of\ invertible\ elements\ in\ \mathbb{Z}_N \rbrace \\ &= \lbrace x \in \mathbb{Z}_N:\gcd (x,N)=1 \rbrace \end{align*} \]对于 \(\mathbb{Z}_N^\ast\) 中的元素 \(x\)，能够通过扩展欧几里得算法(extended Euclid. Algorithm)找出 \(x^{-1}\)。
Modular Linear Equation 线性同余方程
求解线性同余方程：
\[a \cdot x + b \equiv 0 \pmod N \]解为：
\[x \equiv -b \cdot a^{-1} \pmod N \]其中在 \(\mathbb{Z}_N\) 中寻找 \(a^{-1}\) 利用扩展欧几里得，时间复杂度为 \(O(\log^2N)\)，也可用 \(O(n^2)\) 表示，其中 \(n\) 即为 \(N\) 的二进制位数。
Fermat‘s little theorem 费马小定理(1640)
假设 \(p\) 是一个质数，则：
\[\forall x \in \mathbb{Z}_p^*:x^{p-1} \equiv 1 \pmod{p} \]利用费马小定理可以计算模质数的逆，但相比于欧几里得算法有两点不足之处：
- 费马小定理限制必须是质数模，欧几里得算法可以工作在合数模上。
- 运行时间较慢，计算模指数的时间是 \(p\) 长度的立方, \(O(\log^3 p)\)，而欧几里得算法为 \(O(\log^2 p)\)
费马小定理的应用：随机生成质数，Miller Rabin质数判定算法（not the best），由于假质数的集合很小很小（Carmichael数的分布密度指数级衰减），随机选择的情况下不太可能选到假质数。迭代次数的期望是 \(1024\ln 2\)，约为710次（质数定理）。
The structure of \(\mathbb{Z}_p^\ast\)
定理（Euler）：
\(\mathbb{Z}_p^\ast\)是一个循环群（cyclic group）：
\[\exists g \in \mathbb{Z}_p^\ast, \lbrace1,g,g^2,g^3,\dots,g^{p-2}\rbrace=\mathbb{Z}_p^\ast \]（幂次达到 \(g^{p-1}\) 由费马小定理可知模 \(p\) 同余1，所以又从头开始循环）
此时 \(g\) 被称为该群的生成元，通过 \(g\) 的幂次能够扩展出整个群。
Order 阶
对于 \(g \in \mathbb{Z}_p^\ast\)，\(\lbrace1,g,g^2,g^3,\dots,g^{p-2}\rbrace\) 称为 \(g\) 的生成群（group generated by g)，记作\(<g>\)，生成群的大小叫做 \(g\) 在 \(\mathbb{Z}_p^\ast\) 里的阶(order)。
\[ord_p(g)=\vert<g>\vert=smallest \quad a>0\quad s.t. \quad g^a \equiv 1 \pmod p \]Examples:
\(ord_7(3)=6\); \(ord_p7(2)=3\); \(ord_p7(1)=1\)
Thm(Lagrange):(19C)
\[\forall g \in \mathbb{Z}_p^\ast: ord_p(g)\ divides\ (p-1) \]广义的Lagrange定理：群A是B的子群，则A的阶整除B的阶，此处 \(<g>\) 是 \(\mathbb{Z}_p^\ast\) 的子群。
Euler's theorem 欧拉定理(1736)
Definition:
对于一个整数 \(N\)，定义 \(\varphi(N)=|\mathbb{Z}_N^\ast|\) (Euler's \(\varphi\) function)
- 如果 \(p\) 是一个质数，则 \(\varphi(p) = p-1\)
- 如果 \(p,q\) 均为质数，\(N=p \cdot q\)，则 \(\varphi(N) = N-p-q+1 = (p-1)(q-1)\)
Thm(Euler):
\[\forall x \in \mathbb{Z}_N^\ast: x^{\varphi(N)}\equiv 1 \pmod N \]欧拉定理实际上是费马小定理的推广，对于质数而言 \(\varphi(p) = p-1\)，换句话说，如果 \(N\) 是质数，则 \(x^{p-1} \equiv 1 \pmod N\)。欧拉定理将适用范围推广至合数而不仅仅质数。欧拉定理是RSA加密系统的基础。
Modular e's roots 模e次方根
Definition：
\[x \in \mathbb{Z}_p\ s.t.\ x^e \equiv c \pmod p \]\(x\) 被称为 \(c\) 模 \(p\) 的 \(e\) 次根。
什么时候 \(c\) 模 \(p\) 的 \(e\) 次方根存在？
Case1：e与p-1互质：
假设 \(\gcd(e,p-1)=1\)，则对于集合 \(\mathbb{Z}_p^\ast\) 中的所有元素 \(c\)，总是存在 \(c^{1/e}\) 在集合 \(\mathbb{Z}_p\) 中并且很容易找到。证明如下：
令 \(d \equiv e^{-1} \pmod {p-1}\)，则 \(c^{1/e} \equiv c^d \pmod p\)
\(d\cdot e \equiv 1 \pmod {p-1} \Rightarrow \exists k \in \mathbb{Z}:d \cdot e = k\cdot (p-1) + 1 \Rightarrow (c^d)^e = c^{d\cdot e}=c^{k\cdot(p-1)+1}=(c^{p-1})^k\cdot c\)
由费马小定理可知 \(c \in \mathbb{Z}_p^\ast\)，则 \(c^{p-1} \equiv 1 \pmod p\)，进一步有 \((c^{p-1})^k \equiv 1 \pmod 1\)
则推出 \((c^d)^e \equiv c \pmod p\)
证毕
Case2: e与p-1不互质(e=2)：
若 \(p\) 是一个奇质数（除2以外的质数均为奇数），易知p-1是偶数，则 \(\gcd(2,p-1) \neq 1\)
当工作在奇质数模下，平方函数实际上是2-to-1 function(群同态)，即它把 \(x\) 和 \(-x\) 映射到了同一个值
graph TB -x --> id[x^2] x --> id[x^2]Definition：
若集合 \(\mathbb{Z}_p\) 中的元素 \(x\) 在 \(\mathbb{Z}_p\) 中有一个平方根，则称 \(x\) 是一个二次剩余(quadratic residue, Q.R.)
若 \(p\) 是奇质数 \(\Rightarrow\) 则 \(\mathbb{Z}_p\) 中二次剩余的个数为 \(\frac{p-1}{2}+1\)，由于平方函数是2到1的映射，这就意味着 \(\mathbb{Z}_p\) 中有一半的元素在这个映射中没有原像，此外在 \(\mathbb{Z}_p\) 中 \(0\) 也是二次剩余的。
Euler's theorem:
假设 \(p\) 是一个奇质数，则：
\(x\) in \(\mathbb{Z}_p^\ast\) is a Q.R. \(\Leftrightarrow\) \(x^{(p-1)/2} \equiv 1 \pmod p\)
注意：
我们任取一个 \(x \neq 0\)，利用费马小定理 \(\Rightarrow x^{(p-1)/2} \equiv (x^{p-1})^{1/2} \equiv 1^{1/2} \in \lbrace 1,-1 \rbrace \pmod p\)
Def(1798):
\(x^{(p-1)/2}\) 被称为勒让德符号(Legendre Symbol) (x/p)
欧拉定理的不足之处是只为我们提供了判断二次剩余的方法，而没有告诉我们如何计算我们想要的平方根。
计算模 \(p\) 的二次方根:
假设 \(p\equiv 3 \pmod 4\)
Lemma：
如果 \(c \in \mathbb{Z}_p^\ast\) 是一个二次剩余，则 \(\sqrt{c} \equiv c^{(p+1)/4} \pmod p\)
Proof:
\[[c^{(p+1)/4}]^2 \equiv c^{(p+1)/2} \equiv c^{(p-1)/2}\cdot c \equiv 1 \cdot c \equiv c \pmod p \]当 \(p \equiv 1 \pmod 4\) ，也有随机算法能够高效计算出二次方根，较复杂，运行时间约为 \(O(\log^3 p)\)。
Solving quadratic equations mod p
求解：\(a \cdot x^2 + b \cdot x + c \equiv 0 \pmod p\)
利用中学的二次方程公式解：\(x \equiv \frac{-b \pm \sqrt{b^2 -4ac}}{2a} \pmod p\)
- 利用扩展欧几里得求出 \((2a)^{-1}\ in\ \mathbb{Z}_p\)
- 利用平方根算法求出 \(b^2-4ac\) 的平方根
扩展到合数模的e次方根，何时存在？这个问题的难度和大数的质因数分解相同，因为一旦分解出质因数，则利用前面描述的质数模求e次方根的方法，便容易得到合数模的e次方根。
Compute Modular Large Integers 大整数模运算
计算机如何表示大整数?
给定两个n-bit的整数：
- 加法与减法：线性时间 \(T_+=O(n)\)
- 乘法
- 自然计算情况下为 \(T_\times=O(n^2)\)
- Karatsuba于1960年提出一种 \(O(n^{1.585})\) 的算法
- 基本思路： \((2^bx_2+x_1)\times(2^by_2+y_1)\) with 3 mults
- 最优（渐进asymptotic）算法为 \(O(n\log n)\)
- 带余数的除法：\(O(n^2)\)
- 求幂：（快速幂）反复平方法:
- \(O((\log x)\cdot T_\times) \leq O((\log x)\times n^2) \leq O(n^3)\)
Intractable Problems
Discrete Logarithm Problem 离散对数问题
质数模困难问题
对于一个质数 \(p>2\)，并且 \(\mathbb{Z}_p^\ast\) 中的元素 \(g\) 的阶是 \(q\)。
考虑如下函数：
\[x \mapsto g^x \pmod p \]给定 \(x\) 计算 \(g^x\) 是容易的，我们可以利用之前提到的快速幂算法。但是考虑该函数的逆过程，即给定 \(g\) ，求出 \(x\) ，此时便是对数函数的定义，该问题也被称为离散对数问题：
\[D\log_g(g^x) = x, x\in \lbrace0,\dots,q-2 \rbrace \]更加通用型的描述为：
\(G\) 是一个有限循环群，并且 \(g\) 是 \(G\) 的一个生成元，\(q\) 是 \(G\) 的阶
\[G = \lbrace 1, g, g^2, g^3, \dots,g^{q-1} \rbrace \]Def: 如果对于所有的算法 \(A\)，概率 \(Pr_{g\leftarrow G,x\leftarrow \mathbb{Z}_q}[A(G,q,g,g^x)=x]\) 是可以忽略的话，则称在 群 \(G\) 上，离散对数问题(DLOG)是困难的。
例如在群 \(\mathbb{Z}_p^\ast\) （p很大时）上，或者在椭圆曲线群上，离散对数问题都是困难的。并且假设两个问题规模一样的情况下，椭圆曲线群上的离散对数问题较之前者困难得多，这就意味着在椭圆曲线群上我们可以采用更小的参数获得同等的安全性。
计算群 \(\mathbb{Z}_p^\ast\) (n-bit质数 \(p\))上的离散对数问题已知的最好的算法是亚指数算法(GNFS)，运行时间 \(\exp(\tilde{O}(\sqrt[3]{n}))\)，可以看出我们需要较大的 \(n\) 才能确保安全性，而在椭圆曲线群上的离散对数问题的最优算法运行时间为 \(2^{n/2}\)，即说明了对于一个规模是 \(n\) 的问题，其运行时间大约是 \(e\) 的 \(n\) 次方，为 \(n\) 次指数，而不是 \(n\) 的立方根的指数，所以我们选择较小的质数也能获得比较好的安全性。顺带一提的是，椭圆曲线大小(质数模的大小)是对称密钥大小两倍的原因是指数中的因子 \(2\)，
质因数分解问题
合数模困难问题
考虑如下集合：
\[\mathbb{Z}_{(2)}(n) := \lbrace N=p\cdot q\ \text{where $p,q$ are n-bit primes} \rbrace \]-
Problem 1: 随机选择 \(\mathbb{Z}_{(2)}(n)\) 中的一个整数 \(N\)，如何对其进行分解？(e.g. for n=2048)
-
Problem 2: 提供一个非线性多项式 \(f(x)\)，如果多项式次数大于1，随机选择 \(\mathbb{Z}_{(2)}(n)\) 中的一个整数 \(N\)，在 \(\mathbb{Z}_N\) 中找到一个 \(x\) ，\(s.t.\ f(x) \equiv 0 \pmod N\)