第二篇：RSA基础加密解密与素数分解竞赛题解析
一、竞赛原题 采用标准RSA加密算法，已知参数：公钥模数 n=221 ，公钥指数 e=7 ，密文 c=35 。要求：1. 分解n的素数因子p、q；2. 计算私钥d；3. 解出原始明文m；4. 写出完整推导公式与计算过程。 二、RSA核心算法原理 RSA是现代非对称密码学核心算法，也是应用密码学竞赛重难点，核心流程分为密钥生成、加密、解密三步： 1. 密钥生成：选取两个不同大素数p、q，计算 n=pq （公钥模数），欧拉函数 φ(n)=(p-1)(q-1) ；选取公钥e<φ(n)，且gcd(e,φ(n))=1）；计算私钥d，满足  ed ≡ 1 (mod φ(n)) ；​2. 加密公式： c = m^e mod n （m为明文，c为密文）；​3. 解密公式： m = c^d mod n 。 本题为基础RSA解密题型，核心考点为素数分解、模逆元求解、模幂运算。 三、分步解题过程 步骤1：分解模数n，求解素数p、q 已知 n=221 ，对221进行素数分解：试除可得： 13×17=221 ，且13、17均为素数因此： p=13，q=17  步骤2：计算欧拉函数φ(n) 根据公式 φ(n)=(p-1)(q-1)  φ(n)=(13-1)×(17-1)=12×16=192  步骤3：验证公钥e合法性并求解私钥d 已知 e=7 ，首先验证最大公约数： gcd(7,192)=1 ，符合RSA公钥要求。私钥d为e在模φ(n)下的模逆元，满足公式： 7d ≡ 1 (mod 192) 采用扩展欧几里得算法求解：192 = 27×7 + 37 = 2×3 + 13 = 3×1 + 0 回代推导：1 = 7 - 2×3= 7 - 2×(192-27×7)= 55×7 - 2×192 可得： 55×7 ≡ 1 (mod 192) ，即私钥 d=55  步骤4：密文解密，求解明文m 解密公式： m = c^d mod n 代入参数： c=35，d=55，n=221 通过快速模幂运算计算： 35^55 mod 221=42  四、结果汇总与校验 1. 素数因子： p=13，q=17 ​2. 欧拉函数： φ(n)=192 ​3. 私钥： d=55 ​4. 原始明文： m=42  正向加密校验： 42^7 mod 221=35 ，与题目密文一致，计算结果完全正确。 五、竞赛重难点总结 1. 素数分解：小模数RSA竞赛题，核心依靠试除法分解n，是解题前提；​2. 模逆元求解：扩展欧几里得算法是RSA求私钥的核心，竞赛必考手动计算；​3. 模幂运算：大数幂运算不可直接硬算，必须使用快速幂取模，简化计算量；​4. 核心逻辑：RSA安全依赖大素数分解困难性，小模数可暴力分解，也是竞赛出题核心思路。