一、RSA算法概述
RSA（Rivest-Shamir-Adleman）是目前最常用的非对称加密算法之一，其核心原理基于大整数分解的困难性。以下是其核心流程：
1. 密钥生成
- 选择两个大质数 $ p $ 和 $ q $
💡 示例：$ p = 61, q = 53 $ - 计算模数 $ n = p \times q $
🔢 $ n = 61 \times 53 = 3233 $ - 计算欧拉函数 $ \phi(n) = (p-1)(q-1) $
🧮 $ \phi(3233) = 60 \times 52 = 3120 $ - 选择公钥指数 $ e $（需满足 $ 1 < e < \phi(n) $ 且 $ \gcd(e, \phi(n)) = 1 $）
✅ 示例：$ e = 17 $ - 计算私钥指数 $ d $（满足 $ d \times e \equiv 1 \mod \phi(n) $）
🔍 计算过程：通过扩展欧几里得算法求得 $ d = 2753 $
RSA流程图
二、加密与解密过程
加密流程
- 将明文 $ m $ 转换为整数（$ 0 \leq m < n $）
- 计算密文 $ c = m^e \mod n $
🔐 示例：$ m = 123 $ 时，$ c = 123^{17} \mod 3233 = 855 $
解密流程
- 计算明文 $ m = c^d \mod n $
✅ 验证：$ 855^{2753} \mod 3233 = 123 $
RSA加密过程
三、数学基础
- 费马小定理：若 $ p $ 是质数且 $ a $ 不被 $ p $ 整除，则 $ a^{p-1} \equiv 1 \mod p $
- 模反元素：寻找满足 $ e \times d \equiv 1 \mod \phi(n) $ 的 $ d $
- 质数分解难题：已知 $ n $ 求 $ p $ 和 $ q $ 的计算复杂度呈指数级增长
💡 关键特性：
- 公钥（$ e, n $）可公开
- 私钥（$ d, n $）需严格保密
- 加密和解密过程互为逆运算
四、应用场景
- 安全协议（如TLS/SSL）
- 数字签名
- 密钥交换
🔗 扩展阅读：RSA算法实践教程 可通过代码实现原理验证