【密码学】（十）公钥密码

一、 公钥密码体制的意义

在对称密码体系中，加密和解密使用的是同一个密钥。这带来了致命的管理问题：密钥分配困难。

• 在一个有 个用户的网络中，如果任意两个用户之间都要保密通信，网络中总共需要管理的共享密钥数目达到了 个。当 很大时，密钥的生成、安全分发和存储在工程上变得极其困难。

为了解决这个问题，Diffie-Hellman 提出了划时代的公钥密码思想（D-H密钥交换协议）：

• 通信双方不需要事先安全地传递密钥，而是利用公开的参数在不安全的互联网上“协商”出一个共享密钥。
• 数学实现：选择大素数 和有限域 的本原元 。发送方 A 选私密数字 ，公开 ；接收方 B 选私密数字 ，公开 。A 和 B 拿到对方的公开值后，利用指数运算的性质，各自计算出相同的共享密钥 。

二、 理论基础：单向陷门函数 (Trapdoor One-Way Function)

公钥密码的核心机制是将加密和解密分离：公开公钥 用于加密，保留私钥 用于解密。其底层的数学保障就是单向陷门函数。

1. 数学定义

• 单向函数：一个函数 ，已知输入 计算 是容易的；但已知输出 ，逆向求解 是极度困难的（不可行）。
• 陷门单向函数：在单向函数的基础上增加了一个“陷门 ”（即私钥）。给定 和公开参数，想要求解 是困难的；但是一旦掌握了陷门 ，计算 就变得极其容易。

2. 构造公钥密码的常见数学难题

密码学家们利用自然界中已被证实的数学难题来构造上述“陷门”，主要包括以下几类：

• 大整数分解问题 (FAC)：两个大素数相乘极易，但将乘积重新分解为两个素数极难（RSA的基础）。
• 离散对数问题 (DL)：已知 ，计算 极易；已知 ，反推 极难（ElGamal、ECC的基础）。
• 背包问题 (Knapsack)：给出一组特定数字和一个总和，找出哪些数字组合成了这个总和属于NP完全问题。

三、 基于大整数分解体系：RSA 算法

RSA 算法是至今为止理论上最为成熟完善的公钥体制。

1. 算法流程：从密钥生成到加解密

• 步骤1：密钥生成
  1. 随机选择两个极大的安全素数 和 。
  2. 计算模数 。此时很容易求得 的欧拉函数 。
  3. 选择一个整数 ，满足 ，并且 （即 与 互素）。
  4. 利用扩展欧几里得定理计算 在模 下的乘法逆元 ，满足 。
  5. 公开公钥为 ，保密私钥为 （同时销毁 和 ）。
• 步骤2：加密过程 将明文转换为整数 （要求分组长度 ）。密文 。
• 步骤3：解密过程 接收方用私钥 对密文进行解密： 。

2. RSA正确性的数学证明

为什么 一定等于原明文 ？

• 已知 ，所以 。
• 因为 ，所以存在整数 ，使得 。
• 代入得：。
• 根据欧拉定理（对于任意互素的 和 ，有 ），上式变为 。
• (注：当 与 不互素时，推导依然成立，因为 必然是 或 的倍数，在 和 的模域下分别推导后可得同样结论)。

3. 针对 RSA 的攻击原理与参数选择要求

RSA 的安全性完全基于“攻击者无法将 分解为 ”，一旦分解成功，就能轻易算出 并求出私钥 。

• 共模攻击：如果系统中所有用户共用一个模数 ，只是 和 不同。若同一明文用互素的 加密得到 ，攻击者由于知道 ，只需计算 即可直接恢复明文。防范：绝不要共享模数 。
• 选择密文攻击：攻击者截获密文 ，伪造 ，让受害者用私钥解密得到 ，攻击者除以 即可得原明文。
• 抗分解的参数要求：
  1. 和 必须足够大。
  2. 必须足够大。若两者太接近， 会非常接近 ，攻击者只需从 开始顺序检查，看 是否为完全平方数（即 ），由 可迅速分解得 。
  3. 解密指数 必须较大，防止遍历攻击。
     

     [!faq]- 参考答案
     

四、 基于有限域离散对数体系：ElGamal 与 椭圆曲线密码 (ECC)

1. ElGamal 算法（有限域乘法群上的对数）

ElGamal 是基于 Diffie-Hellman 密钥交换发展出的加解密算法。

• 密钥生成：选大素数 、本原根 、随机数 （作为私钥）。计算 （公开公钥为 ）。
• 加密：要发送明文 。发送者选一随机数 。计算两部分密文发送： 。
• 解密：接收方收到 ，利用私钥 解密： 。 证明： ；而公钥计算部分 。两者相等，故相除即可消去 恢复 。
• 缺点：生成的密文长度是明文的两倍（密文扩展）。

2. 椭圆曲线密码体制 (ECC) 与 国密 SM2

ECC 将离散对数问题搬到了“椭圆曲线上的点群”中，大大提升了破解难度。

• 椭圆曲线的几何/代数加法法则：
  曲线方程一般为 。 点加法 的规则是：画一条过 的直线，交曲线于一点 ，然后作关于 x 轴的对称点即为 。
  代数计算式：
  设 。计算斜率 ：

  若 $P \neq Q$：$\lambda = \frac{y_2 - y_1}{x_2 - x_1} \pmod p$。 
  若 $P = Q$ (求2P, 倍点运算)：$\lambda = \frac{3x_1^2 + a}{2y_1} \pmod p$。
  

  则新坐标为： ， 。

• ECC 加解密原理 (类ElGamal)：
  选取生成元 ，接收方私钥 ，公钥 (即 自加 次)。
  发送方将消息嵌入到曲线点 ，随机选 。发送密文对： 。
  接收方用私钥解密： 。

• 国密 SM2 的结构： SM2 是我国标准，使用固定参数的大素数域上的椭圆曲线。 它的加密不仅仅是坐标运算，还融合了密码学安全的哈希函数 (Hash) 和密钥导出函数 (KDF)。 SM2 加密流程：

  1. 计算 。
  2. 计算点 。利用 KDF 算出比特串 。
  3. 计算 (与明文按位异或)。
  4. 计算 作为完整性校验。 最终密文拼接输出 。
• ECC 的优势： 有限域离散对数有亚指数级攻击算法，但椭圆曲线离散对数目前只有指数级攻击算法 。这导致 ECC 的密钥极短：160 位的 ECC 安全性等同于 1024 位的 RSA
  

五、 基于 NP 困难体系：背包密码体制

背包密码虽然曾被破解（如Merkle-Hellman基本体制被破译），但它是密码学将 NP 困难问题应用于加密的经典尝试。

1. 核心数学问题与“陷门”构造

• 一般背包问题：给一个向量 和一个和值 ，求是否存在一个二进制向量 ，使得 。当 很大时，这是 NP 困难问题（穷举需 次）。
• 陷门（超递增背包）：如果向量满足 $aj > \sum{i=1}^{j-1} a_i$（即每一个数都大于前面所有数之和），这个背包问题就极易求解，只需从大到小用贪心算法做减法即可，处于多项式时间。

2. 加解密运行机制

• 密钥生成： 用户选取一个超递增序列 （这是极易解的，作为私钥的一部分）。 选取一个极大的模数 (必须大于 的总和) 和一个乘数 (与 互素)。 通过模乘伪装：计算 ，生成一个乱序的一般背包向量 。 公开作为公钥； 保密作为私钥。
• 加密： 将明文转为二进制序列 ，用公钥 进行点乘： 。
• 解密： 接收者收到 后，先乘上逆元解开伪装： 。 因为 ，所以 就是超递增背包 下的总和。 最后针对 和超递增背包 进行极其简单的贪心求解，即可恢复出二进制明文 。