基于传统数论的公钥密码学和格理论的引入
加密 · · 阅读 6 分钟
Intro
「公钥密码学」，又称为「非对称密码学」，使用两个不同的金钥：一个公钥和一个私钥。公钥用于加密讯息，私钥用于解密讯息。公钥是公开的，而私钥则需保密。其主要应用包括：加密/解密（确保保密性）、数位签章（提供身份验证）、金钥交换（用于会话金钥）。
PS: 密码学的关键在于达到四个核心要素：保密性（Confidentiality）、资料完整性（Data Integrity）、身份验证（Authentication）以及不可否认性（Non-repudiation）。
与之相对的“对称密码学”中，加密和解密讯息则使用相同的密钥。
核心构造：陷门单向函数
在“公钥密码学”中，加密讯息的公钥是公开的，而我们需要设计一种结构，使得讯息解谜对持有私钥的人是简单的，而对没有私钥的人是极其困难——不可解的。
这里的核心思想也就是构造一个Trapdoor One Way Function 陷门单向函数，即：
Trapdoor One Way Function 陷门单向函数
- 单向性（One-way）：函数 f(x) = y 在正向计算非常容易，但给定 y 想要找到 x 使得 f(x) = y 在计算上是困难的。
- 陷门（Trapdoor）：存在一个特殊的秘密信息（陷门），如果知道这个秘密，就能够高效地计算反向函数，即从 y 求出 x。
传统数论的两类陷门单向函数
1. 大质数分解问题 Factorization of two primes
Given P, Q are two primes and N = P*Q
It is easy to compute N
However given N it is difficult to factorize into P and Q
用于RSA加密体系
2. 离散对数问题 Discrete Log Problem
Consider b and g are elements in a finite group and bk=g, for some k
Given b and k it is easy to compute g
Given b and g it is difficult to determine k
用于Diffie-Hellman加密体系以及变体ECC椭圆曲线加密体系
RSA Cryptosystem
基于大质数分解问题，RSA系统包含以下步骤：
密钥生成步骤：
- 选择两个不同的大质数 p, q
- 计算模数 n = p × q
- 计算欧拉函数值 φ(n) = (p - 1)(q - 1)
- 选择公钥指数 b，要求 1 < b < φ(n) 且 gcd(b, φ(n)) = 1
- 计算私钥指数 a ≡ b⁻¹ mod φ(n)
结果得到： 公钥 pk = (n, b) 私钥 sk = (p, q, a)
这里的欧拉函数 φ(n) 用于计算在 1 到 n 之间与 n 互质的数的个数。
加密和解密过程：
Elgamal Cryptosystem
基于离散对数DLP问题。它的安全性依赖于有限群中计算离散对数的困难性。
- 公钥：由群元素 g、私钥 x 和 h = gˣ 组成
- 加密：选择随机数 y，将消息 m 加密为 (c₁, c₂) = (gʸ, m·hʸ)
- 解密：利用私钥 x 计算 m = c₂/c₁ˣ
Elliptic Curve Cryptography (ECC)
属于DLP离散对数问题的变体。
椭圆曲线的定义（模运算）
解集构成阿贝儿群（Abelian group）
Elliptic Curve Discrete Logarithm Problem (ECDLP)
给定：椭圆曲线 E，基点 P，目标点 Q = kP 求解：整数 k，使得 Q = kP
为什么在 ECC 中使用有限域？
在实际的密码系统中，我们选择在有限域（Finite Field）上定义椭圆曲线，而不是在实数域上，因为
- 计算精确性：有限域使用精确的整数运算，避免实数域的计算误差。
- 存储效率：元素可用固定长度比特串表示，提高计算效率。
- 安全性：有限域使离散对数问题更难解决，避免实数域连续性带来的安全隐患。
- 运算效率：加法、乘法等运算快速，适合实际应用。
通常使用的有限域包括：
- 素数域 GF(p)：其中 p 是一个大质数
- 二元扩展域 GF(2ⁿ)：特别适用于硬件实现
基于传统数论的公钥密码学的局限
- 量子威胁：Shor量子算法可在多项式时间内破解传统数论难题
- 密钥增长：为提升安全强度需要指数级别的密钥增长，影响效率
- 结构单一：主要依赖于少数几个数论问题（质因数分解、离散对数）
- 理论瓶颈：缺乏新的可靠数学难题作为密码学基础
传统数论问题的复杂性
- 大质数分解问题 (Integer Factorization)：尚未被证明为 NP 完全问题。在经典计算机上，最佳算法具有次指数时间复杂度，但使用 Shor 量子算法可在多项式时间内解决。
- 离散对数问题 (DLP)：虽非 NP 完全问题，但被视为计算上的困难问题。在经典计算机上需要次指数时间，但同样可被 Shor 量子算法在多项式时间内解决。
- 椭圆曲线离散对数问题 (ECDLP)：较一般离散对数问题更为困难，目前最佳算法仍需指数时间复杂度。然而，此问题同样易受量子计算威胁。
格理论的引入
格理论问题的复杂性与应用
- 最短向量问题 (SVP)：在格中寻找最短的非零向量，已被证明在某些范数下是 NP-hard 问题，其近似版本同样保持困难性。
- 最近向量问题 (CVP)：在给定目标点时寻找最近的格点，这是一个 NP-hard 问题，常用作解密算法的基础。
- 学习带误差问题 (LWE)：解决线性方程组 As + e = b (mod q)，其中已知 A 和 b 求解 s。此问题具有平均情况困难性，且基于最坏情况的格问题，表现出优异的量子抗性。
- 短整数解问题 (SIS)：给定随机矩阵 A，寻找短向量 x 使得 Ax = 0 (mod q)。此问题与 LWE 相对偶，同样具有优异的量子抗性和平均情况困难性。
格理论的优势
相比传统数论，格理论中的平均情况难度可归约到最坏情况，提供更强的安全保证。这与传统密码学中平均情况归约到特殊情况的方式形成鲜明对比。同时，格理论提供了丰富的难题（如SVP、CVP、LWE、SIS等），使得密码方案设计更加灵活多样。