RSA加密算法 题目描述 RSA是一种非对称加密算法，广泛应用于数据加密和数字签名。题目要求： 理解RSA的密钥生成、加密和解密过程。 给定两个质数 \( p = 5 \)，\( q = 11 \)，公钥指数 \( e = 3 \)，对明文 \( M = 9 \) 进行加密，再对密文解密还原明文。 解题过程 步骤1：密钥生成 计算模数 \( n \) \[ n = p \times q = 5 \times 11 = 55 \] \( n \) 是公钥和私钥的共用模数。 计算欧拉函数 \( \phi(n) \) \[ \phi(n) = (p-1)(q-1) = 4 \times 10 = 40 \] \( \phi(n) \) 用于生成私钥。 选择公钥指数 \( e \) 给定 \( e = 3 \)，需满足 \( 1 < e < \phi(n) \) 且 \( \gcd(e, \phi(n)) = 1 \)。 验证：\( \gcd(3, 40) = 1 \)，符合要求。 计算私钥指数 \( d \) \( d \) 是 \( e \) 模 \( \phi(n) \) 的乘法逆元，即满足： \[ e \times d \equiv 1 \pmod{\phi(n)} \] 通过扩展欧几里得算法求解： 方程：\( 3d + 40k = 1 \) 试算：\( 3 \times 27 = 81 \)，\( 81 \bmod 40 = 1 \) 解得 \( d = 27 \)（取最小正整数解）。 密钥对 ： 公钥：\( (e, n) = (3, 55) \) 私钥：\( (d, n) = (27, 55) \) 步骤2：加密过程 明文 \( M = 9 \)，加密公式为： \[ C = M^e \bmod n \] 代入计算： \[ C = 9^3 \bmod 55 = 729 \bmod 55 \] \( 55 \times 13 = 715 \) \( 729 - 715 = 14 \) 得到密文 \( C = 14 \)。 步骤3：解密过程 密文 \( C = 14 \)，解密公式为： \[ M' = C^d \bmod n \] 代入计算： \[ M' = 14^{27} \bmod 55 \] 优化计算 （模幂运算避免大数直接计算）： 分解指数：\( 27 = 16 + 8 + 2 + 1 \) 分步计算模55： \( 14^1 \bmod 55 = 14 \) \( 14^2 = 196 \bmod 55 = 31 \)（因 \( 55 \times 3 = 165 \)，\( 196 - 165 = 31 \)） \( 14^4 = (14^2)^2 = 31^2 = 961 \bmod 55 = 26 \)（\( 55 \times 17 = 935 \)，\( 961 - 935 = 26 \)） \( 14^8 = (14^4)^2 = 26^2 = 676 \bmod 55 = 16 \) \( 14^{16} = (14^8)^2 = 16^2 = 256 \bmod 55 = 36 \) 组合结果： \[ 14^{27} = 14^{16} \times 14^8 \times 14^2 \times 14^1 = 36 \times 16 \times 31 \times 14 \bmod 55 \] 分步取模： \( 36 \times 16 = 576 \bmod 55 = 26 \)（\( 55 \times 10 = 550 \)） \( 26 \times 31 = 806 \bmod 55 = 31 \)（\( 55 \times 14 = 770 \)） \( 31 \times 14 = 434 \bmod 55 = 9 \)（\( 55 \times 7 = 385 \)） 最终解密得到明文 \( M' = 9 \)，与原始明文一致。 关键点总结 RSA安全性依赖大数分解难题（已知 \( n \) 难求 \( p, q \)）。 加密/解密需用模幂运算，避免直接计算大指数。 私钥 \( d \) 必须通过 \( \phi(n) \) 计算，且保密。