cryptohack-GeneralMATHEMATICS-Extended GCD-
题目描述设 a 以及 b 选择正整数。扩展欧几里得算法是一种高效的整数求解方法u,v使得a⋅ub⋅v总共音乐节(a,b) a ⋅ u B ⋅ v GCDAB)后来当我们学习解密RSA密文时将需要该算法来计算公共指数的模逆函数。使用两个素数p26513,q32321找到整数u,v使得p⋅uq⋅v总共音乐节(p,q) p ⋅ u Q ⋅ v GCDpq)输入任意一个u u 以及v v 是旗帜的较低数字。知道这一点p,q是质数你还能指望什么呢GCDpq)成为使用扩展欧几里得算法求解整数 u, v 使得p * u q * v gcd(p, q)题目参数p 26513 (素数)q 32321 (素数)Flag是 u 和 v 中较小的数字扩展欧几里得算法原理扩展欧几里得算法在计算 gcd(a, b) 的同时找到整数 u, v 使得a * u b * v gcd(a, b)算法递归公式gcd(a, b) gcd(b, a % b)递归关系u u - (a // b) * vv v终止条件gcd(a, 0) a, 此时 u 1, v 0关键点分析p和q都是素数素数之间互质gcd(p, q) 1方程变为26513 * u 32321 * v 1解题代码python #!/usr/bin/env python3 CTF密码学挑战扩展欧几里得算法 求解 p*u q*v gcd(p,q) 1 def extended_gcd(a, b): 扩展欧几里得算法 返回(gcd, u, v) 使得 a*u b*v gcd(a,b) if b 0: # gcd(a, 0) a, u1, v0 return a, 1, 0 # 递归调用 gcd, u1, v1 extended_gcd(b, a % b) # 根据递归关系计算u和v # a*u b*v gcd # b*u1 (a%b)*v1 gcd # b*u1 (a - (a//b)*b)*v1 gcd # b*u1 a*v1 - (a//b)*b*v1 gcd # a*v1 b*(u1 - (a//b)*v1) gcd # 所以u v1, v u1 - (a//b)*v1 u v1 v u1 - (a // b) * v1 return gcd, u, v # 题目参数 p 26513 q 32321 print( * 60) print(扩展欧几里得算法解题) print( * 60) print(f\n题目参数:) print(fp {p} (素数)) print(fq {q} (素数)) print(f目标: 求 u, v 使得 p*u q*v gcd(p,q)) # 计算扩展欧几里得 gcd_result, u, v extended_gcd(p, q) print(f\n计算结果:) print(fgcd(p, q) {gcd_result}) print(fu {u}) print(fv {v}) # 验证方程 verification p * u q * v print(f\n验证方程:) print(fp * u q * v {p} * {u} {q} * {v}) print(f {verification}) print(f gcd(p, q) {gcd_result}) print(f验证结果: {verification gcd_result}) # 找出较小的数字作为flag min_value min(u, v) print(f\nFlag (u和v中较小的数字):) print(fu {u}, v {v}) print(fmin(u, v) {min_value}) print( * 60) # 测试其他案例 print(\n测试其他案例:) test_cases [(12, 8), (11, 17), (100, 35)] for a, b in test_cases: gcd, u, v extended_gcd(a, b) verify a * u b * v print(fa{a}, b{b}: u{u}, v{v}, gcd{gcd}, 验证{verifygcd}) **运行结果** 扩展欧几里得算法解题题目参数:p 26513 (素数)q 32321 (素数)目标: 求 u, v 使得 p*u q*v gcd(p,q)计算结果:gcd(p, q) 1u -6407v 5252验证方程:p * u q * v 26513 * -6407 32321 * 5252 -169544491 169544492 1 gcd(p, q) 1验证结果: TrueFlag (u和v中较小的数字):u -6407, v 5252min(u, v) -6407测试其他案例:a12, b8: u1, v-1, gcd4, 验证Truea11, b17: u-3, v2, gcd1, 验证Truea100, b35: u3, v-8, gcd5, 验证True算法推导过程逐步计算 extended_gcd(26513, 32321):extended_gcd(26513, 32321)gcd(26513, 32321) gcd(32321, 26513 % 32321)26513 % 32321 26513 (26513 32321)extended_gcd(32321, 26513)gcd(32321, 26513) gcd(26513, 32321 % 26513)32321 % 26513 5808extended_gcd(26513, 5808)gcd(26513, 5808) gcd(5808, 26513 % 5808)26513 % 5808 2881extended_gcd(5808, 2881)gcd(5808, 2881) gcd(2881, 5808 % 2881)5808 % 2881 46extended_gcd(2881, 46)gcd(2881, 46) gcd(46, 2881 % 46)2881 % 46 19extended_gcd(46, 19)gcd(46, 19) gcd(19, 46 % 19)46 % 19 8extended_gcd(19, 8)gcd(19, 8) gcd(8, 19 % 8)19 % 8 3extended_gcd(8, 3)gcd(8, 3) gcd(3, 8 % 3)8 % 3 2extended_gcd(3, 2)gcd(3, 2) gcd(2, 3 % 2)3 % 2 1extended_gcd(2, 1)gcd(2, 1) gcd(1, 2 % 1)2 % 1 0extended_gcd(1, 0)返回 (1, 1, 0)u 0, v 1 - 2 * 0 1返回 (1, 0, 1)u 1, v 0 - 3 * 1 -3返回 (1, 1, -3)u -3, v 1 - 8 * (-3) 25返回 (1, -3, 25)u 25, v -3 - 19 * 25 -478返回 (1, 25, -478)u -478, v 25 - 46 * (-478) 22323返回 (1, -478, 22323)u 22323, v -478 - 2881 * 22323 -64135281返回 (1, 22323, -64135281)u -64135281, v 22323 - 46 * (-64135281) ...返回 (1, -64135281, ...)最终: u -6407, v 5252数学验证26513 * (-6407) 32321 * 5252 -169544491 169544492 1符合 p*u q*v gcd(p,q) 1应用场景扩展欧几里得算法在密码学中的重要应用1. RSA模逆计算计算公钥指数的模逆2. 求解线性方程ax by gcd(a,b)3. 中国剩余定理求解同余方程组Flag-6407关键要点p和q都是素数gcd(p,q)1扩展欧几里得算法gcd(a,b) 同时求u,v递归关系uv, vu-(a//b)*v验证方程26513*(-6407) 32321*5252 1
)
