cryptohack-GeneralMATHEMATICS-Extended GCD--尧图网络科技

题目描述

设 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