Daily AlpacaHack: RBG Writeup

RBG

authored by soon-haari

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))

解法

今回出力されている暗号文について考えてみましょう。$i$番目の暗号文は以下のように表されます。
$$
c_i \equiv m^{e_i} \pmod N
$$
さて、$i+1$番目を考えると
$$
c_{i+1} \equiv m^{e_{i+1}} \pmod N
$$
となります。ここで、$e_{i+1}$は
$$
e_{i+1} \equiv 3e_i + 1337 \pmod N
$$
と表せます。さらに、整式として表すと
$$
e_{i+1} \equiv 3e_i + 1337 -k_iN
$$
表せます($k \in ${$0,\cdots, 3$})。
よって、
$$
c_{i+1} \equiv m^{e_{i+1}} \equiv m^{3e_i + 1337 -k_iN}　\equiv (m^{e_i})^3 \cdot m^{1337} \cdot (m^N)^{-k_i} \pmod N
$$
と考えられます。
簡単のために、$X = m^{1337}, Y =m ^N $とします。そして、$m^{e_i} \equiv c_i$より、
$$
c_{i+1} \cdot c_{i}^{-3} \equiv X \cdot Y^{-k_i} \pmod N
$$
と表せます。
ここで、$k_i$の範囲を考えてみましょう。
$0 \leq e_i \leq N-1, 0 \leq e_{i+1} \leq N-1$より、
$$
3e_i + 1337 \leq 3(N-1) + 1337 = 3N + 1334
$$
となります。
このとき$k_i \geq 4$とすると
$$
3e_i + 1337 -4N \leq -N + 1334 < 0
$$
といったように負の値になってしまいます。以上より、$k_i$は$0 \sim 3$のいずれかの数字であることがわかります。

さて、このまま計算をしていきたいのですが、現状$X$の値はわかっていません。そのため、$X$を消去することを考えましょう。右辺の$i$番目と$i+1$番目の比を取る、すなわち、
$$
\frac{XY^{-k_i} }{XY^{-k_{i+1}}} \equiv Y^{k_{i+1} - k_i} \pmod N
$$
と考えるとよいでしょう。そうすれば、先ほどの式を変形し、
$$
c_{i+1} \cdot c_{i}^{-3} \equiv X \cdot Y^{-k_i} \pmod N
$$
から
$$
X \equiv c_{i+1} \cdot c_{i}^{-3} \cdot Y^{k_i} \pmod N
$$
となり、$X$の候補を求めることができます。
では、この$X$が正しいかはどのようにして求めたらよいのでしょうか？
先ほどの$X, Y$の定義を思い出しましょう。
$X = m^{1337}, Y =m ^N $となっており、baseは同じです。つまり、$X^N = m^{1337N}, Y^{1337} =m^{1337N} $と考えることができ、$X^N = Y^{1337}$を満たすことができればよいでしょう。

こうして、$X, Y$を求めることができたら、一度$X,Y$で掛け算をしてみましょう。
$$
XY \equiv m^{1337}m^N \equiv m^{1337+N} \pmod N
$$
このままだと、$m^{1337}$となってしまい、このまま求めることができません。
つまり、$X,Y$にそれぞれ$a, b$乗をしてあげると
$$
X^a Y^b \equiv m^{1337a+Nb} \pmod N
$$
となり、
$$
1337a + Nb = 1
$$
を満たすような$a,b$を求めてあげることで$m$をゲットできます。

from gmpy2 import powmod, gcdext
from Cryptodome.Util.number import inverse, long_to_bytes

N = 9288011389664837847963670837039196937548434573294469245501561784245642854634445047
cts = [
    7827437377925724428078233147899924081225364249930858942421079276821876942757073519,
    8887391738833944793881713037947023989163050343070393147424888589467627754249865604,
    8081548039727189478984198619032683177557008617453299085364096689176320484341697433,
    2275794279542811986322743644529192750108107184530803067791576158460846098638595919,
    6253142316263707598596838911072529989608774170182629190175128689020135811837569575,
    4733751513227945548879795301848782446340444473234631092994528819564169644364997232,
    7059294752711247585748476830322929650455626597483726834273561488576645863895400850,
    3416115616735235302679100710807631760495960686259891905227746706138654756842094326,
    8925820570540264143648581237815478995705636946118008059750128065916255778832895553,
    2892105289971843001930724217759034130633547138605066058109243908372747042621581984,
    314392853155476706788704773868088966795343394149871206877830575819199838027511362,
    4327945167964771727885647567828770187834470062965467452997985192630056416939883267,
    5004179351047061632898561578033712835850283897910028694457603173176131447102750100,
]

def powmod_signed(base, e, mod):
    if e >= 0:
        return powmod(base % mod, e, mod)
    inv_base = inverse(base, mod)
    return powmod(inv_base, -e, mod)

def solve():
    A = []
    for i in range(len(cts) - 1):
        A.append((cts[i + 1] * inverse(powmod(cts[i], 3, N), N)))

    B = []
    for i in range(len(A) - 1):
        B.append((A[i] * inverse(A[i + 1], N)))

    for Y in B:
        for i in range(4):
            for k in range(4):
                X = (A[i] * powmod(Y, k, N))
                if pow(X, N, N) != pow(Y, 1337, N):
                    continue
                g, a, b = gcdext(1337, N)
                m = (powmod_signed(X, int(a), N) * powmod_signed(Y, int(b), N)) % N
                print(long_to_bytes(m).decode())
                return 

solve()

Flag: Alpaca{Thanks_SuperBeetleGamer!}