CRYPTO

作者：xinyi

一、RSA 加密基础

1. 对称加密

对称加密是最早的加密方式，核心特征是 “加密与解密使用同一规则”，具体流程如下：

1. 甲方选择某一种加密规则，对信息进行加密；

1. 乙方使用同一种规则，对加密后的信息进行解密。

对称加密的缺点

甲方必须将加密规则（密钥）告知乙方，否则乙方无法解密；但密钥在传输过程中可能被拦截，导致信息传输的安全性无法保证。

2. 非对称加密（RSA、ECC、DSA 等）

非对称加密解决了对称加密的密钥传输问题，核心特征是 “加密用公钥，解密用私钥”，具体流程如下：

1. 消息接收方（如乙方）生成一对密钥：公钥（公开）和私钥（保密，仅自己留存）；

1. 接收方将公钥发布给消息发送方（如甲方）；

1. 发送方使用接收方的公钥对消息进行加密；

1. 接收方使用自己的私钥对加密后的消息进行解密。

非对称加密流程示意图：

非对称加密密钥关系与使用场景：

二、RSA 加密解密完整步骤

RSA 是应用最广泛的非对称加密算法，其加密解密过程基于大数分解难题，具体步骤如下：

第一步：随机选择两个不相等的质数 p 和 q

• 示例：爱丽丝选择质数 p=61 和 q=53（实际应用中，p 和 q 需为极大质数，密钥安全性才更高）。

第二步：计算 p 和 q 的乘积 n（密钥长度依据）

• 公式：n = p × q

• 示例：n = 61 × 53 = 3233

• 密钥长度：n 的二进制位数即为密钥长度，3233 的二进制为110010100001（12 位），故为 12 位密钥；实际应用中，RSA 密钥常用 1024 位或 2048 位（重要场景）。

第三步：计算 n 的欧拉函数 φ(n)

欧拉函数 φ(n) 表示 “小于 n 且与 n 互质的正整数个数”，对于两个质数 p 和 q 的乘积 n，有固定公式：

• 若 n = p × q（p、q 为不相等质数），则 φ(n) = (p-1) × (q-1)

• 示例：φ(3233) = (61-1) × (53-1) = 60 × 52 = 3120

第四步：随机选择整数 e（公钥组成部分）

e 需满足两个条件：

1. 1 < e < φ(n)；

1. e 与 φ(n) 互质（即 gcd (e, φ(n)) = 1）。

• 示例：爱丽丝选择 e=17（实际应用中，常选择65537作为 e，兼顾安全性与计算效率）。

第五步：计算 e 的模反元素 d（私钥组成部分）

模反元素 d 的定义：存在整数 d，使得 e×d ≡ 1 (mod φ(n))（即 e×d 除以 φ(n) 的余数为 1）。

• 等价方程：e×d - k×φ(n) = 1（k 为整数，可通过扩展欧几里得算法求解）；

• 示例：已知 e=17、φ(n)=3120，解方程17x + 3120y = 1，得到一组解x=2753（即 d=2753）、y=-15。

最终密钥

• 公钥：(e, n) → 示例：(17, 3233)（公开，用于加密）；

• 私钥：(d, n) → 示例：(2753, 3233)（保密，用于解密）。

三、离散对数

离散对数是密码学中的重要数学基础，常用于设计非对称加密算法（如 ElGamal 算法），以下为相关概念与学习记录。

前置知识

学习离散对数需先掌握以下数学知识：

1. 欧拉定理 & 费马小定理：https://oi-wiki.org/math/number-theory/fermat/

1. 同余方程：https://oi-wiki.org/math/number-theory/congruence-equation/

离散对数相关题目与符号说明

在数学联考中遇到的离散对数题目（题目中符号 “ⓧ” 实际表示 “mod p”，增加了理解难度）：

离散对数核心概念与定义

离散对数的本质是 “在有限域中求解指数方程”，具体定义与相关性质如下：

离散对数的计算难度与应用场景（如密码学中的安全基础）：