题目描述

设 a 以及 b 选择正整数。

扩展欧几里得算法是一种高效的整数求解方法u,v使得

a⋅u+b⋅v=总共音乐节⁡(a,b) a ⋅ u + B ⋅ v =GCD（A，B)

后来，当我们学习解密RSA密文时，将需要该算法来计算公共指数的模逆函数。

使用两个素数p=26513,q=32321，找到整数u,v使得

p⋅u+q⋅v=总共音乐节⁡(p,q) p ⋅ u + Q ⋅ v =GCD（p，q)

输入任意一个u u 以及v v 是旗帜的较低数字。

知道这一点p,q是质数，你还能指望什么呢GCD（p，q)成为？

使用扩展欧几里得算法求解整数 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) * v'

v = 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, u=1, v=0 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(f"p = {p} (素数)") print(f"q = {q} (素数)") print(f"目标: 求 u, v 使得 p*u + q*v = gcd(p,q)") # 计算扩展欧几里得 gcd_result, u, v = extended_gcd(p, q) print(f"\n计算结果:") print(f"gcd(p, q) = {gcd_result}") print(f"u = {u}") print(f"v = {v}") # 验证方程 verification = p * u + q * v print(f"\n验证方程:") print(f"p * 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(f"u = {u}, v = {v}") print(f"min(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(f"a={a}, b={b}: u={u}, v={v}, gcd={gcd}, 验证={verify==gcd}") ``` **运行结果：** ```

扩展欧几里得算法解题

题目参数:

p = 26513 (素数)

q = 32321 (素数)

目标: 求 u, v 使得 p*u + q*v = gcd(p,q)

计算结果:

gcd(p, q) = 1

u = -6407

v = 5252

验证方程:

p * u + q * v = 26513 * -6407 + 32321 * 5252

= -169544491 + 169544492

= 1

= gcd(p, q) = 1

验证结果: True

Flag (u和v中较小的数字):

u = -6407, v = 5252

min(u, v) = -6407

测试其他案例:

a=12, b=8: u=1, v=-1, gcd=4, 验证=True

a=11, b=17: u=-3, v=2, gcd=1, 验证=True

a=100, b=35: u=3, v=-8, gcd=5, 验证=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 = 5808

extended_gcd(26513, 5808)

gcd(26513, 5808) = gcd(5808, 26513 % 5808)

26513 % 5808 = 2881

extended_gcd(5808, 2881)

gcd(5808, 2881) = gcd(2881, 5808 % 2881)

5808 % 2881 = 46

extended_gcd(2881, 46)

gcd(2881, 46) = gcd(46, 2881 % 46)

2881 % 46 = 19

extended_gcd(46, 19)

gcd(46, 19) = gcd(19, 46 % 19)

46 % 19 = 8

extended_gcd(19, 8)

gcd(19, 8) = gcd(8, 19 % 8)

19 % 8 = 3

extended_gcd(8, 3)

gcd(8, 3) = gcd(3, 8 % 3)

8 % 3 = 2

extended_gcd(3, 2)

gcd(3, 2) = gcd(2, 3 % 2)

3 % 2 = 1

extended_gcd(2, 1)

gcd(2, 1) = gcd(1, 2 % 1)

2 % 1 = 0

extended_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

递归关系：u=v', v=u'-(a//b)*v'

验证方程：26513*(-6407) + 32321*5252 = 1