八重神子与白水之谜：解开一场关于“不可能”的美味冒险

打开文件后发现给了n,m,c的值n 2**512 m 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075 c 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499并暗示存在一个flag使得c≡me(mod)那么目标就很明确了求出e从而还原flag初步观察加密类型我们注意到模数不是常见的两个大素数乘积如 RSA进一步检查m和c的奇偶性两者都 ≡ 3(mod

说明它们都是奇数但非1mod 4模 2**k乘法群的结构对于 k≥3 模 2**k的乘法群 (Z/2**kZ)× 是一个阶为 2**k−1的阿贝尔群且同构于(Z/2Z)×(Z/**2k−2Z)更关键的是所有 ≡ 1 (mod

的奇数构成一个循环子群由 5 生成阶为 2**k−2 。

而 ≡ 3 (mod

的数不在该循环子群中但满足x≡3(mod

⇒−x≡1(mod

因此我们可以将问题“转化”到由 5 生成的循环子群中 m % 4 3 c % 4 3推算演练设m≡3(mod

⇒−m≡1(mod

c≡3(mod

⇒−c≡1(mod

于是存在整数 b,db,d使得5b≡−m(mod2**

5d≡−c(mod2**

原方程 c≡me(mod2**

可改写为(−c)≡(−m)**e(mod2**

由于e必须是奇数否则 (−m)**e≡−me!≡-c因为左边 ≡ 1 mod 4右边 ≡ 3 mod 4 会矛盾所以有(−c)≡(−

**e⋅m**e−m**e⇒−c≡−m**e⇒c≡m**e成立当且仅当 e为奇数。

于是有5**d≡(−c)≡(−m)**e≡(5**b)**e5**(be)(mod2**

由于 5 的阶是 2**510故b⋅e≡d(mod2**

现在问题转化为已知b,d求e。

求解离散对数 log⁡5(x)mod2**512我们需要一个函数输入 x≡1(mod

x≡1(mod

输出t使得 5**t≡x(mod2**

这可以通过Hensel 引理式的提升算法实现先在模 8 下确定初始值5^01, 5^15 mod 8。

逐步从 2**323 提升到 2**512每次根据当前误差修正指数。

具体实现如下def discrete_log(x, k

: if x % 4 ! 1: raise ValueError(x must be 1 mod

# 初始化 b based on x mod 8 b 0 if x % 8 1 else 1 for i in range(4, k

: power 1 i current pow(5, b, power) diff (current - x) % power if diff % (1 (i -

) ! 0: raise Exception(Not divisible!) t (diff // (1 (i -

)) 1 b t * (1 (i -

) return b求解线性同余方程得到 blog⁡5(−m) , dlog⁡5(−c)后解b⋅e≡d(mod2**

由于b可能是偶数需先提取因子2**v设 b2**v⋅b′其中b′为奇数若 d!≡0(mod2**v) 则无解否则令 d′d/2**v模数变为 M2**(510−v)解 e≡d′⋅(b′)**(−

(modM)由于b′是奇数在模 2**M下一定有逆元。

完整脚本如下from Crypto.Util.number import long_to_bytes def discrete_log(x, k

: if x % 4 ! 1: raise ValueError(x must be 1 mod

b 0 if (x %

1 else 1 for i in range(4, k

: mod 1 i cur pow(5, b, mod) diff (cur - x) % mod if diff % (1 (i -

) ! 0: raise ValueError(No solution) t (diff // (1 (i -

)) 1 b t * (1 (i -

) return b n 2**512 m 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075 c 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499 neg_m (n - m) % n neg_c (n - c) % n b discrete_log(neg_m) d discrete_log(neg_c) # Solve b * e ≡ d (mod 2^

v 0 b_temp b while b_temp % 2 0: v 1 b_temp // 2 if d % (2**v) ! 0: raise Exception(No solution) d_new d // (2**v) mod 2**(510 - v) inv_b pow(b_temp, -1, mod) e (d_new * inv_b) % mod print(Flag:, long_to_bytes(e).decode())解得flagflag{5f95ca

d-ed0b-a9139692cb4a}

一起看c17c13-一起看应用