問題

RBG stands for RSA + SBG + LCG! To learn about them, please check out lecture1.mp4.

from Crypto.Util.number import *

PBITS, NDAT = 137, 13

with open("flag.txt", "rb") as f:
    m = int.from_bytes(f.read())

N = getPrime(PBITS) * getPrime(PBITS)
e = getRandomRange(731, N)
print(f"{N = }")

lcg = lambda s: (s * 3 + 1337) % N

for i in range(NDAT):
    print(pow(m, e := lcg(e), N))

• output.txt

解法

$e$の更新部分を式に表す。

$e_{i+1} \equiv 3e_i + 1337 \pmod N$

$\Leftrightarrow e_{i+1} = 3e_i + 1337 - k_i N$

e = getRandomRange(731, N)であるから、

$k_i ∈ {0,1,2,3}$

候補が少ないので後の計算で出てきても総当たりに使える。

これを用いて暗号文$c_{i+1}$は次のように変形できる。

$c_{i+1} \equiv m^{e_{i+1}} \equiv c_i^3 * m^{1337} * (m^N)^{-k_i} \pmod N$

$m$を含む項を

$A = m^{1337}$

$B = m^N$　とおくと、

$d_i = c_{i+1} * (c_i^3)^{-1} = A * B^{-k_i}$　となり、$d_i$も高々4種類であることが分かる。

$k=3$の場合は稀なので$k \in {0,1,2}$で考えると、