题目来源CryptoHack - Public-Key Cryptography 公钥密码学模块 难度20 分 · 15714 次解题 · 26 个解决方案 知识标签RSA、模乘法逆元、欧拉函数、扩展欧几里得算法一、题目背景题目给出了 RSA 中的两个素数和公钥指数p 857504083339712752489993810777 q 1029224947942998075080348647219 e 65537要求计算对应的私钥d≡e−1(modφ(N))其中 φ(N) 是欧拉函数Eulers totient functionNpq。二、RSA 加密原理简述在进入计算之前先理一下 RSA 的整体框架理解「为什么私钥是 e−1modφ(N)」。1. 密钥生成随机选取两个大素数 p,q计算 Npq。N 是模数会公开。计算欧拉函数 φ(N)(p−1)(q−1)。这是秘密因为分解 N 困难。选取公钥指数 e要求 gcd(e,φ(N))1。常用值是 655372161。计算私钥 d≡e−1(modφ(N))即 e⋅d≡1(modφ(N))。最终公钥(N,e)私钥(N,d)2. 加密与解密加密加密cmemodN解密解密mcdmodN3. 为什么 de−1modφ(N) 能解密由欧拉定理当 gcd(m,N)1 时mφ(N)≡1(modN)若 e⋅d≡1(modφ(N))即 edkφ(N)1则cd(me)dmedmkφ(N)1(mφ(N))k⋅m≡1k⋅m≡m(modN)这就是 RSA 能正确解密的数学基础。私钥 d 之所以被称为「陷阱门trapdoor」正是因为它让我们能快速反转 m↦memodN 这个函数而没有 d也就是没有 φ(N)的攻击者只能去分解 N。三、解题步骤Step 1计算 N 和 φ(N)Np⋅qφ(N)(p−1)(q−1)由于 p,q 都是素数φ(N) 直接由公式给出这是关键只有在已知 p,q 的情况下才能快速算出 φ(N)否则需要先分解 N。Step 2求 e 模 φ(N) 的乘法逆元我们需要找到 d 使得e⋅d≡1(modφ(N))这是一个模乘法逆元问题标准解法有两种扩展欧几里得算法Extended Euclidean Algorithm在求 gcd(e,φ(N)) 的同时得到一组系数 (x,y) 满足 exφ(N)ygcd1于是 d≡x(modφ(N))。费马小定理 / 欧拉定理当模数为素数时可用 a−1≡ap−2(modp)但这里 φ(N) 不是素数不能用此法。本题用扩展欧几里得即可。四、代码实现方法一Python 内置Python 3.8Python 3.8 起的pow(a, -1, m)直接支持模乘法逆元背后用的就是扩展欧几里得p 857504083339712752489993810777 q 1029224947942998075080348647219 e 65537 N p * q phi (p - 1) * (q - 1) # 模乘法逆元d e^(-1) mod phi(N) d pow(e, -1, phi) print(N , N) print(phi , phi) print(d , d) # 验证 assert (e * d) % phi 1 print(验证 (e*d) mod phi , (e * d) % phi, OK)方法二手写扩展欧几里得算法为了更直观地理解原理可以手写一遍 EEAdef egcd(a, b): 返回 (g, x, y) 使得 a*x b*y g gcd(a, b) if b 0: return a, 1, 0 g, x1, y1 egcd(b, a % b) return g, y1, x1 - (a // b) * y1 def modinv(a, m): g, x, _ egcd(a, m) if g ! 1: raise Exception(f{a} 在模 {m} 下无逆元 (gcd{g})) return x % m d modinv(e, phi) print(d , d) 两种方法得到的结果完全一致。运行结果N 882564595536224140639625987659416029426239230804614613279163 phi 882564595536224140639625987657529300394956519977044270821168 d 121832886702415731577073962957377780195510499965398469843281 验证 (e*d) mod phi 1 OK五、结果验证为确保正确性做两个检查检查 1e⋅d≡1(modφ(N))e * d 65537 * 121832886702415731577073962957377780195510499965398469843281 7986803722695006743881348245664854549172812954392417215712469148697 (e * d) mod phi(N) 1 ✓检查 2用 (N,e) 加密一个测试明文再用 d 解密能还原python m 20260704 # 任取一个测试明文 c pow(m, e, N) # 加密 m2 pow(c, d, N) # 解密 assert m m2 print(解密还原 m , m2, OK)运行后m2 20260704验证通过说明 d 确实是正确的私钥。六、Flag121832886702415731577073962957377780195510499965398469843281七、一点拓展1. 为什么 e 通常取 65537655372161 是一个费马素数。选择它的原因是素数能提高与 φ(N) 互素的概率二进制表示为1 0000 0000 0000 0001只有两个 1模平方算法只需 17 次乘法加密速度快比早期的 e3 更安全e3 时若消息过小或相同消息发给多个接收者容易遭受 Coppersmith / Håstad 攻击。2. 实际 RSA 的安全性依赖本题直接给出了 p,q所以计算 φ(N) 是 O(1) 的。但在真实 RSA 中攻击者只能拿到公开的 (N,e)必须先分解 N才能算出 φ(N) 和 d。当 N 足够大目前推荐 2048 位以上时大整数分解是公认的困难问题这就是 RSA 安全性的基石。3. Python 3.8 以下怎么办老版本 Python 没有pow(e, -1, m)可以用gmpy2.invert(e, phi)或者直接调用上面手写的modinv。竞赛/CTF 中gmpy2几乎是标配。八、小结这道题的核心知识点私钥的本质d 是 e 在模 φ(N) 下的乘法逆元由 ed≡1(modφ(N)) 定义。欧拉函数当 Npq 且 p,q 为素数时φ(N)(p−1)(q−1)这是 RSA 的「陷阱门」信息。求解方法扩展欧几里得算法Python 中即pow(e, -1, phi)。安全前提所有这些计算都依赖于已知 p,q若只知道 N则需先分解这正是 RSA 安全性的来源。