Decrypt Shop - AlpacaHack

コード

from Crypto.Util.number import bytes_to_long, getPrime, inverse
import os

flag = os.environ.get("FLAG", "Alpaca{REDACTED}").encode()

p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = inverse(e, phi)

c = pow(bytes_to_long(flag), e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
print("Give me a ciphertext. I will decrypt it, unless it is the flag ciphertext.")

while True:
    try:
        x = int(input("> "))
    except:
        print("invalid")
        exit(0)

    if not 0 <= x < n:
        print("out of range")
        exit(0)

    if x == c:
        print("no")
        exit(0)

    m = pow(x, d, n)
    print(m)

I don’t like math 🤔

以降、flag を $m$ とおく。また法を $n$ とする(以降、可能な限り省略する)

プログラムより以下がわかる。

• $n$, $e$, $c$ は既知である。
• 任意の $x$ ($x=c$ を除く) に対して $x^d$ を求められるので、$f(x) = x^d$ を計算できる。
• $c \equiv m^e \pmod{n}$ である。

ここで、(オイラーの法則) $ed \equiv 1 \pmod{\varphi(n)}$ であることをなんとか利用して $m$ を求めたい。 このために、$f(x) = x^d$ の $x$ を工夫して、$x$ に ${}^e$ をつけることで ${}^d$ を排除したい。 また $x$ には $m$ を入れ込みたい。

制約上 $x = m^e$ ($= c$) は使えないが、 例えば $x \equiv c\cdot 2^e \pmod{n}$ は求められる。 定義から $c \equiv m^e \pmod{n}$ より、

$$ x \equiv m^e\cdot 2^e \pmod{n} $$

と変形できる。この $x$ を入れると得られる値は

$$ \begin{aligned} f(x) &= x^d \\ &\equiv \left(m^e\cdot 2^e\right)^d \pmod{n} \\ &= (m\cdot 2)^{ed} \\ &\equiv m\cdot 2 \pmod{n} \\ &= 2m \end{aligned} $$

である。 よって、$m$ (flag) は $2m$ を2で割れば求められる(法を $n$ とした2の逆元をかければよい)。

プログラムには

$$ x = c\cdot 2^e \% n $$

を入力する。