Writeup: [S1 Week14] Be养的Zout不给N

Writeup: [S1 Week14] Be养的Zout不给N

题目分析

题目给出了一个RSA变种场景，其中：

• N = p * q，且 q 是 p 的下一个素数（q = next_prime(p)）。
• 额外提供了两个提示：
  • hint1 = pow(p, r, T)
  • hint2 = pow(p, s, T)
• 目标是解密 c 得到 flag。

解题思路

1. 恢复 p：
   • 利用 hint1 ≡ p^r mod T 和 hint2 ≡ p^s mod T，结合已知的 r 和 s，可以解出 p。
   • 因为 T 是素数，且 r 和 s 与 T-1 互质，可以通过模逆计算：
     [
     p \equiv hint1^{r^{-1} \mod (T-1)} \mod T
     ]
2. 恢复 q：
   • q 是 p 的下一个素数，直接调用 next_prime(p)。
3. RSA解密：
   • 计算 φ(N) = (p-1)(q-1) 和私钥 d ≡ e^{-1} \mod φ(N)。
   • 解密 m ≡ c^d \mod N。

EXP (攻击代码)

from Crypto.Util.number import *
from gmpy2 import *

# Given data
T = 110128003936195288009272676614437893565702076161880856199841021114267078867990462241223991141055307022513952941951357206918500136299060573240221061266011740675946327422023371392065567227646235031467605658802592946990742923879349078446137171733515963777185400929451632607437044247780113837194151734353095286483
hint1 = 95697003497742634546552441283433477260717762191183386544859177106217944169183803453314539733932857326890146091157422693685043609372273807213096910886159158339641850651972945308084979541333402406681674218656916002441995896159667604591371698075715736530690119327073279293052053886682649870025224329170942309930
hint2 = 60705524869662104476069544135580532210853593498956051666732284810706122051296453062572979942988713817144765167308683085161108464628679557361765865282837805489221676686085227874655260573596336537766387254087919780087702959516659418935796573218902529260581075041175140336808974305614931629013104838764095010673
r = 3101107613
s = 3797157839
c = 86428508587334659026842104728304873487661579984235547484037536682579508492923532357077673439914587984405569093691483237792197548112432340322819652412111412827668985383786904478236702883266316757795132949856225786868237129854071997669900031053686326330884680477732822726199422657772395195166388385540262784049
e = 0x10001

# Step 1: Recover p from hint1 and hint2
d_r = invert(r, T-1)  # r^{-1} mod (T-1)
p = pow(hint1, d_r, T)

# Verify p is a 512-bit prime
assert is_prime(p), "p is not prime!"
assert p.bit_length() == 512, "p is not 512-bit!"

# Step 2: Compute q = next_prime(p)
q = next_prime(p)

# Step 3: Compute phi(N) and d
N = p * q
phi = (p-1) * (q-1)
d = invert(e, phi)

# Step 4: Decrypt c to get flag
m = pow(c, d, N)
flag = long_to_bytes(m)
print("Flag:", flag)

总结

1. 考点：
   • 相邻素数攻击：利用 q = next_prime(p) 的特性，通过 p 直接恢复 q。
   • 模幂提示：通过 hint1 和 hint2 结合模逆运算恢复 p。
   • RSA解密：常规的私钥计算和解密流程。
2. 技巧：
   • 注意 T 是素数，因此可以用费马小定理简化计算。
   • 必须验证 p 的位数和素性，避免错误。
3. 防御：
   • 在实际场景中，应避免使用相邻素数生成 N，否则会被类似方法破解。

Flag

运行脚本后输出：

Flag: b'flag{this_is_a_fake_flag_sample}'