第 4 章 公钥密码

4.1. 数学知识

4.1.1. 群 环 域

设 $\ast$ 是集合 $\displaystyle{ S }$ 上的运算，若对 $\forall a,b \in S$，有 $a \ast b \in S$，则称 $\displaystyle{ S }$ 对运算 $\ast$ 是封闭的。若 $\ast$ 是一元运算，对 $\forall a \in S$，有 $\ast a \in S$，则称 $\displaystyle{ S }$ 对运算 $\ast$ 是封闭的。

若对 $\forall a, b, c \in S$，有 $(a \ast b) \ast c = a \ast (b \ast c)$，则称 $\ast$ 满足结合律。

$\langle Q, +, \cdot \rangle, \langle R, +, \cdot \rangle, \langle C, +, \cdot \rangle$ 都是域，分别代表有理数集、实数集、复数集

有限域是指域中元素个数有限的域，元素的个数称为域的阶。

4.1.2. 素数和互素数

1. 因子

$a, b \in Z, b \ne 0$，若存在另一个整数 $\displaystyle{ m }$，使得 $\displaystyle{ a = mb }$，则称 $\displaystyle{ b }$ 整除 $\displaystyle{ a }$，记为 $b \mid a$

2. 素数

称素数 $\displaystyle{ p \left( p > 1 \right) }$ 是素数，如果 $\displaystyle{ p }$ 的因子只有 $\pm 1$ 和 $\pm p$

任一整数 $\displaystyle{ a \left( a > 1 \right) }$ 都能唯一的分解为以下形式

其中 $p_1 < p_2 < \cdots < p_t$ 是素数

3. 互素数

$\displaystyle{ c }$ 为 $\displaystyle{ a }$ 和 $\displaystyle{ b }$ 的最大公因子，$c=\gcd (a,b)$

要求最大公因子一般为正

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

若 $\gcd(a, b)=1$ 则称 $\displaystyle{ a }$ 与 $\displaystyle{ b }$ 互素

最小公倍数 $\text{lcm}(a,b)=\displaystyle \frac{ab}{\gcd(a, b)}$

4.1.3. 模运算

其中 $a \equiv r \bmod n$

交换律、结合律、分配率、加法单位元 0 、乘法单位元 1 此处从略

乘法逆元

记 $Z_n^\ast = \{ a \mid 0 < a < n, \gcd(a, n)=1 \}$

对 $1 \in Z_n^\ast$，存在 $x \in Z_n^\ast$，使得 $a \times x \equiv 1 \bmod n$，$\displaystyle{ x }$ 为 $\displaystyle{ a }$ 的乘法逆元，记为 $\displaystyle{ x = a ^{ \left\lbrace - 1 \right\rbrace } }$

4.1.4. 模指数运算

对给定的正整数 $\displaystyle{ m , n }$，计算 $a^m \bmod n$

例 4-5 $\displaystyle{ a = 7 , n = 19 }$，易求出

可以看出存在循环，循环周期为 3

称满足方程 $a^m \equiv 1 \bmod n$ 的最小正整数 $\displaystyle{ m }$ 为模 $\displaystyle{ n }$ 下 $\displaystyle{ a }$ 的阶，记为 $\text{ord}_n(a)$

4.1.5. 三个定理

费尔马定理

欧拉函数

设 $\displaystyle{ n }$ 是一正整数，小于 $\displaystyle{ n }$ 且与 $\displaystyle{ n }$ 互素的正整数的个数称为 $\displaystyle{ n }$ 的欧拉函数，记为 $\varphi (n)$

欧拉定理

推论 $\text{ord}_n(a) \mid \varphi(n)$

推论说明，$\text{ord}_n(a)$ 是 $\varphi(n)$ 的因子，则称 $\displaystyle{ a }$ 为 $\displaystyle{ n }$ 的本原根。如果 $\displaystyle{ a }$ 是 $\displaystyle{ n }$ 的本原根，则 $a, a^2, \cdots, a^{\varphi(n)}$ 在 $\bmod n$ 下互不相同且与 $\displaystyle{ n }$ 互素。

卡米歇尔定理

对满足 $\gcd (a,n)=1$ 的所有 $\displaystyle{ a }$，使得 $a^m \equiv 1 \bmod n$ 同时成立的最小正整数 $\displaystyle{ m }$，称为 $\displaystyle{ n }$ 的卡米歇尔函数，记为 $\lambda(n)$

似乎没说要考

4.1.6. 素性检验

爱拉托斯尼筛法

用于求一定范围内的所有素数，每次筛去某一个小于 $\sqrt{n}$ 的素数的超过 1 的整数倍。

对于 $\displaystyle{ n }$ 很大时，不可行。

Miller-Rabin 概率检测法

懒，不想写

4.1.7. 欧几里得算法

1. 求最大公因子

def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

2. 求乘法逆元

如果 $\displaystyle{ \left( a , b \right) = 1 }$，则 $\displaystyle{ b }$ 在 $\bmod a$ 下有乘法逆元（不妨设 $\displaystyle{ b < a }$），即存在一个 $\displaystyle{ x \left( x < a \right) }$，使得 $bx \equiv 1 \bmod a$。推广的欧几里得算法先求出 $\displaystyle{ \left( a , b \right) }$，当 $\displaystyle{ \left( a , b \right) = 1 }$ 时，则返回 $\displaystyle{ b }$ 的逆元。

# 扩展欧几里得算法
def extended_euclid(a, b):
    x, y, u, v = 0, 1, 1, 0
    while b != 0:
        q, r = divmod(a, b)
        a, b = b, r
        x, u = u, x - q * u
        y, v = v, y - q * v
    return x, y, a

# 求出乘法逆元
def inverse(a, m):
    x, y, q = extended_euclid(a, m)
    if x < 0:
        x += m
    return x

# 扩展欧几里得算法
def extended_euclid(a, b):
    x, y, u, v = 0, 1, 1, 0
    while b != 0:
        q, r = divmod(a, b)
        a, b = b, r
        x, u = u, x - q * u
        y, v = v, y - q * v
    return x, y, a

# 求出乘法逆元
def inverse(a, m):
    x, y, q = extended_euclid(a, m)
    if x < 0:
        x += m
    return x

4.1.8. 中国剩余定理

• 如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数
• 可将大数用小数表示、大数的运算通过小数实现

中国剩余定理提供了一个非常有用的特性，即在模 $\displaystyle{ M }$ 下可将大数 $\displaystyle{ A }$ 由一组小数 $(a_1, a_2, \cdots, a_k)$ 来表达，且大数的运算可以通过小数实现。表示为：

其中 $a_i = A \bmod m_i$，则有以下推论：

推论 如果

那么

例题 有下面的同余方程组，求 $\displaystyle{ x }$

4.1.9. 离散对数

1. 指标

设 $\displaystyle{ p }$ 是一素数，$\displaystyle{ a }$ 是 $\displaystyle{ p }$ 的本原根，则 $a, a^2, \cdots, a^{p-1}$ 产生出 $1 \sim p-1$ 之间的所有值，且每一值只出现一次。因此对任意 $b \in \{1, \cdots, p - 1\}$，都存在唯一的 $i(1 \leqslant i \leqslant p - 1)$，使得 $b \equiv a^i \bmod p$。称 $\displaystyle{ i }$ 为模 $\displaystyle{ p }$ 下以 $\displaystyle{ a }$ 为底 $\displaystyle{ b }$ 的指标，记为 $i=\text{ind}_{a, p}(b)$。指标有以下性质：

• $\text{ind}_{a, p}(1)=0$ 即 $a^0 \bmod p =1 \bmod p = 1$
• $\text{ind}_{a, p}(a)=1$ 即 $a^1 \bmod p = a$

又有两条性质

• $\text{ind}_{a, p}(xy)=[\text{ind}_{a,p}(x) + \text{ind}_{a,p}(y)] \bmod \varphi (p)$
• $\text{ind}_{a, p}(y^r)=[r \times \text{ind}_{a, p}(y)] \bmod \varphi p$

2. 离散对数

设 $\displaystyle{ p }$ 是一素数，$\displaystyle{ a }$ 是 $\displaystyle{ p }$ 的本原根，则 $a, a^2, \cdots, a^{p-1}$ 产生出 $1 \sim p-1$ 之间的所有值，且每一值只出现一次。因此对任意 $\forall b \in \{1, \cdots, p - 1\}$，都存在唯一的 $i(1 \leqslant i \leqslant p - 1)$，使得 $b \equiv a^i \bmod p$。称 $\displaystyle{ i }$ 为模 $\displaystyle{ p }$ 下以 $\displaystyle{ a }$ 为底 $\displaystyle{ b }$ 的离散对数，记为 $i \equiv \log_a(b) \bmod p$

当 $\displaystyle{ a , p , i }$ 已知，用快速指数算法可以比较容易算出 $\displaystyle{ b }$，但如果已知 $\displaystyle{ a , b , p }$，求 $\displaystyle{ i }$ 则十分困难。

4.2. 公钥密码体制的基本概念

4.2.1. 公钥密码体制的原理

采用两个相关密钥将加密和解密能力分开。一个密钥公开，用于加密数据；一个密钥为用户专用，是保密的，用于解密。

算法的特性：已知密码算法和加密密钥，求解解密密钥在计算上是不可行的

公钥密码体制的认证、保密框图

4.2.2. 公钥密码算法应满足的要求

1. 接收方 B 产生密钥对（公钥 $\displaystyle{ P K _{ B } }$ 和私钥 $\displaystyle{ S K _{ B } }$）是计算上容易的
2. 发方 A 用收方的公开钥对消息 $\displaystyle{ m }$ 加密以产生密文 $\displaystyle{ c }$，即 $c = \mathcal{E}_{PK_B}[m]$ 在计算上是容易的
3. 收方 B 用自己的秘密钥对 $\displaystyle{ c }$ 解密，即 $m=\mathcal{D}_{SK_B}[C]$ 在计算上是容易的
4. 敌手由 B 的公开钥 $\displaystyle{ P K _{ B } }$ 求秘密钥 $\displaystyle{ S K _{ B } }$ 在计算上是不可行的
5. 敌手由密文 $\displaystyle{ c }$ 和 B 的公开钥 $\displaystyle{ P K _{ B } }$ 恢复明文 $\displaystyle{ m }$ 在计算上是不可行的
6. 加解密次序可对换，即 $\mathcal{E}_{PK_B}[\mathcal{D}_{SK_B}[m]]=\mathcal{D}_{SK_B}[\mathcal{E}_{PK_B}[m]]$

4.3. RSA 算法

做过实验，基本上不考了

4.3.2. 安全性

• 加密算法是确定性算法

4.5. ElGamal 密码体制

4.5.1. 加解密算法

1. 密钥产生过程

选择一素数 $\displaystyle{ p }$ 以及小于 $\displaystyle{ p }$ 的随机数 $\displaystyle{ x }$，$\displaystyle{ g }$ 是 $\displaystyle{ p }$ 的原根，计算 $y \equiv g^x \bmod p$

$\displaystyle{ y }$ 作为公开钥，$\displaystyle{ x }$ 作为秘密钥

2. 加密过程

明文消息 $\displaystyle{ M }$ 随机选一整数 $\displaystyle{ k < p - 1 }$，计算 $C_1 \equiv g^k \bmod p, C_2 \equiv y^kM \bmod p$，密文为 $\displaystyle{ C = \left( C _{ 1 } , C _{ 2 } \right) }$

3. 解密过程

4.5.2. 安全性

• 安全性基于有限域上的离散对数难解性
• 加密算法是概率算法
• 不能抵御选择密文攻击

4.7. 椭圆曲线密码体制

4.7.5.椭圆曲线上的密码

1. Diffie-Hellman 密钥交换

首先取一个素数 $p \approx 2^{180}$ 和两个参数 $\displaystyle{ a , b }$，则得方程

表达的椭圆曲线及其上面的点构成的 Abel 群 $\displaystyle{ E _{ p } \left( a , b \right) }$。第二步，取 $\displaystyle{ E _{ p } \left( a , b \right) }$ 的一个生成元 $\displaystyle{ G \left( x _{ 1 } , y _{ 1 } \right) }$，要求 $\displaystyle{ G }$ 的阶为一个非常大的素数，$\displaystyle{ G }$ 的阶是满足 $\displaystyle{ n G = O }$ 的最小正整数 $\displaystyle{ n }$。$\displaystyle{ E _{ p } \left( a , b \right) }$ 和 $\displaystyle{ G }$ 作为公开参数。

两用户 A 和 B 之间的密钥交换如下运行：

1. A 选一个小于 $\displaystyle{ n }$ 的整数 $\displaystyle{ n _{ A } }$ 作为秘密钥，并由 $\displaystyle{ P _{ A } = n _{ A } G }$ 产生 $\displaystyle{ E _{ p } \left( a , b \right) }$ 上的一点作为公开钥
2. B 类似地选取自己的秘密钥 $\displaystyle{ n _{ B } }$ 和公开钥 $\displaystyle{ P _{ B } }$
3. A, B 分别由 $\displaystyle{ K = n _{ A } P _{ B } }$ 和 $\displaystyle{ K = n _{ B } P _{ A } }$ 产生双方共享的秘密钥

这是因为 $\displaystyle{ K = n _{ A } P _{ B } = n _{ A } \left( n _{ B } G \right) = n _{ B } \left( n _{ A } G \right) = n _{ B } P _{ A } }$

攻击者若想获取 $\displaystyle{ K }$，则必须由 $\displaystyle{ P _{ A } }$ 和 $\displaystyle{ G }$ 求出 $\displaystyle{ n _{ A } }$，或由 $\displaystyle{ P _{ B } }$ 和 $\displaystyle{ G }$ 求出 $\displaystyle{ n _{ B } }$，即需要求椭圆曲线上的离散对数，因此是不可行的。

• 已知 $\displaystyle{ n }$ 和 $\displaystyle{ P }$ 求 $\displaystyle{ K }$ 是简单的
• 已知 $\displaystyle{ P }$ 和 $\displaystyle{ K }$ 求 $\displaystyle{ n }$ 在计算上是不可行的

中间人攻击

2. ElGamal 密码体制

原理

选择一素数 $\displaystyle{ p }$ 以及小于 $\displaystyle{ p }$ 的随机数 $\displaystyle{ x }$，$\displaystyle{ g }$ 是 $\displaystyle{ p }$ 的原根，计算 $y \equiv g^x \bmod p$。$\displaystyle{ \left( y , g , p \right) }$ 作为公开钥，$\displaystyle{ x }$ 作为秘密钥。

加密过程 明文消息 $\displaystyle{ M }$ 随机选一整数 $\displaystyle{ k < p - 1 }$，计算 $C_1 \equiv g^k \bmod p, C_2 \equiv y^kM \bmod p$，密文为 $\displaystyle{ C = \left( C _{ 1 } , C _{ 2 } \right) }$

解密过程

利用椭圆曲线实现 ElGamal 密码体制

首先选取一条椭圆曲线，并得 $\displaystyle{ E _{ p } \left( a , b \right) }$ ，将明文消息 $\displaystyle{ m }$ 通过编码嵌入到曲线上得点 $\displaystyle{ P _{ m } }$，再对点 $\displaystyle{ P _{ m } }$ 做加密变换。

取 $\displaystyle{ E _{ p } \left( a , b \right) }$ 的一个点 $\displaystyle{ G }$，$\displaystyle{ E _{ p } \left( a , b \right) }$ 和 $\displaystyle{ G }$ 作为公开参数。

用户 A 选 $\displaystyle{ n _{ A } }$ 作为秘密钥，并以 $\displaystyle{ P _{ A } = n _{ A } G }$ 作为公开钥。任一用户 B 若想向 A 发送消息 $\displaystyle{ P _{ m } }$，可选取一随机正整数 $\displaystyle{ k }$，产生以下点对作为密文

A 解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点的倍乘，即

攻击者若由 $\displaystyle{ C _{ m } }$ 得到 $\displaystyle{ P _{ m } }$，就必须知道 $\displaystyle{ k }$。而要得到 $\displaystyle{ k }$，只有通过椭圆曲线上的两个已知点 $\displaystyle{ G }$ 和 $\displaystyle{ k G }$，这意味着必须求椭圆曲线上的离散对数，因此不可行。