企业官网建设流程全解析

打开文件后发现给了n,m,c的值

n = 2**512 m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075 c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

并暗示存在一个flag，使得c≡me(mod)

那么目标就很明确了

求出e，从而还原flag

初步观察加密类型

我们注意到模数不是常见的两个大素数乘积（如 RSA）

进一步检查m和c的奇偶性

两者都 ≡ 3(mod4)，说明它们都是奇数但非1mod 4

模 2**k乘法群的结构

对于 k≥3 ，模 2**k的乘法群 (Z/2**kZ)× 是一个阶为 2**k−1的阿贝尔群，且同构于：

(Z/2Z)×(Z/**2k−2Z)

更关键的是：所有 ≡ 1 (mod 4) 的奇数构成一个循环子群，由 5 生成，阶为 2**k−2 。

而 ≡ 3 (mod 4) 的数不在该循环子群中，但满足：

x≡3(mod4)⇒−x≡1(mod4)

因此，我们可以将问题“转化”到由 5 生成的循环子群中

>>> m % 4 3 >>> c % 4 3

推算演练

设：

• m≡3(mod4)⇒−m≡1(mod4)
• c≡3(mod4)⇒−c≡1(mod4)

于是存在整数 b,db,d

使得：

5b≡−m(mod2**512)

5d≡−c(mod2**512)

原方程 c≡me(mod2**512)可改写为

(−c)≡(−m)**e(mod2**512)

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

所以有：

(−c)≡(−1)**e⋅m**e=−m**e⇒−c≡−m**e⇒c≡m**e

成立当且仅当 e为奇数。

于是有：

5**d≡(−c)≡(−m)**e≡(5**b)**e=5**(be)(mod2**512)

由于 5 的阶是 2**510

故：

b⋅e≡d(mod2**510)

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

求解离散对数 log⁡5(x)mod2**512

我们需要一个函数，输入 x≡1(mod4)x≡1(mod4) ，输出t使得 5**t≡x(mod2**512)

这可以通过Hensel 引理式的提升算法实现：

1. 先在模 8 下确定初始值（5^0=1, 5^1=5 mod 8）。
2. 逐步从 2**323 提升到 2**512，每次根据当前误差修正指数。

具体实现如下：

def discrete_log(x, k=512): if x % 4 != 1: raise ValueError("x must be 1 mod 4") # 初始化 b based on x mod 8 b = 0 if x % 8 == 1 else 1 for i in range(4, k + 1): power = 1 << i current = pow(5, b, power) diff = (current - x) % power if diff % (1 << (i - 1)) != 0: raise Exception("Not divisible!") t = (diff // (1 << (i - 1))) & 1 b += t * (1 << (i - 3)) return b

求解线性同余方程

得到 b=log⁡5(−m) , d=log⁡5(−c)后，解：

b⋅e≡d(mod2**510)

由于b可能是偶数，需先提取因子2**v：

• 设 b=2**v⋅b′，其中b′为奇数
• 若 d!≡0(mod2**v) ，则无解
• 否则令 d′=d/2**v，模数变为 M=2**(510−v)
• 解： e≡d′⋅(b′)**(−1)(modM)

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

完整脚本如下

from Crypto.Util.number import long_to_bytes def discrete_log(x, k=512): if x % 4 != 1: raise ValueError("x must be 1 mod 4") b = 0 if (x % 8) == 1 else 1 for i in range(4, k + 1): mod = 1 << i cur = pow(5, b, mod) diff = (cur - x) % mod if diff % (1 << (i - 1)) != 0: raise ValueError("No solution") t = (diff // (1 << (i - 1))) & 1 b += t * (1 << (i - 3)) 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^510) 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())

解得flag

flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}