CRYPTO
作者：xinyi
一、RSA 加密基础
1. 对称加密
对称加密是最早的加密方式，核心特征是 “加密与解密使用同一规则”，具体流程如下：
甲方选择某一种加密规则，对信息进行加密；
乙方使用同一种规则，对加密后的信息进行解密。
对称加密的缺点
甲方必须将加密规则（密钥）告知乙方，否则乙方无法解密；但密钥在传输过程中可能被拦截，导致信息传输的安全性无法保证。
2. 非对称加密（RSA、ECC、DSA 等）
非对称加密解决了对称加密的密钥传输问题，核心特征是 “加密用公钥，解密用私钥”，具体流程如下：
消息接收方（如乙方）生成一对密钥：公钥（公开）和私钥（保密，仅自己留存）；
接收方将公钥发布给消息发送方（如甲方）；
发送方使用接收方的公钥对消息进行加密；
接收方使用自己的私钥对加密后的消息进行解密。
非对称加密流程示意图：
非对称加密密钥关系与使用场景：
二、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 < e < φ(n)；
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 算法），以下为相关概念与学习记录。
前置知识
学习离散对数需先掌握以下数学知识：
欧拉定理 & 费马小定理：https://oi-wiki.org/math/number-theory/fermat/
离散对数相关题目与符号说明
在数学联考中遇到的离散对数题目（题目中符号 “ⓧ” 实际表示 “mod p”，增加了理解难度）：
离散对数核心概念与定义
离散对数的本质是 “在有限域中求解指数方程”，具体定义与相关性质如下：
离散对数的计算难度与应用场景（如密码学中的安全基础）：
