DiceCTF @ HOPE - small-fortune

TL;DR

Goldwasser-Micali暗号
暗号化に使うビットごとの乱数の差が小さい
最初に使われた乱数の2乗は求まることから、それを利用して差分を変数とした合同方程式をsmall_roots()で解き、解が存在するビットを平文とする

Prerequisite

Goldwasser–Micali cryptosystem

Writeup

次のようなスクリプトとその実行結果が与えられる

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

flag = bytes_to_long(open("flag.txt", "rb").read())

p, q = getPrime(256), getPrime(256)
n = p * q

x = getRandomRange(0, n)
while legendre(x, p) != -1 or legendre(x, q) != -1:
    x = getRandomRange(0, n)

def gm_encrypt(msg, n, x):
    y = getRandomRange(0, n)
    enc = []
    while msg:
        bit = msg & 1
        msg >>= 1
        enc.append((pow(y, 2) * pow(x, bit)) % n)
        y += getRandomRange(1, 2**48)
    return enc

print("n =", n)
print("x =", x)
print("enc =", gm_encrypt(flag, n, x))

明らかにGoldwasser-Micali暗号が使われているが、各ビットに使う乱数yの差がnに比べて小さい。

公開鍵 $n,e$ に対して、ビット $b_i$ の暗号文を $c_i$ とおくと、暗号化に用いる乱数 $y_i$ を用いて次が成り立つ。

$c_i \equiv {y_i}^2x^{b_i} \mod n$

ここで、 $i$ がインクリメントされる度に $y_i$ は最大で $2^{48}$ 程度加算されるが、これは $n$ 比べて非常に小さい。よって、 $y_i$ と $y_0$ の差も $n$ に比べて小さくなることから次のように書き直す。

$c_i \equiv (y_0+\delta_i)^2x^{b_i} \mod n$

ここで、 $b_0$ は0か1かの2択であり、フラグがフォーマットに沿っていて改行も存在していないとすれば、ord("}") = 0x7dより奇数であるから、 $b_0=1$ としてよい。よって $y_0^2 \equiv \frac{c_i}{x} \mod n$ が成り立つ。

上記の $c_i$ に関する式を見直すと、 $(y_0+\delta_i)^2 = y_0^2+2\delta_i y_0 + \delta_i^2$ が現れ、 $y_0^2$ が既知であることから、後は $y_0$ を消去出来れば良い事になる。これは明らかに $y_0$ について解いて2乗すれば良く、最終的に次のような式が得られる。

$\left(\frac{c_i}{x^{b_i}} - y_0^2 -\delta_i^2\right)^2 - 4\delta_i y_0^2 \equiv 0 \mod n$

ここで、もし $b_i$ を正しくGuess出来たとしたら、 $\delta_i$ が $n$ に比べて小さく、更に $\delta_i$ は左辺の根の1つなのでCoppersmith's Attackで求められることが期待出来る。そして $b_i$ は0,1の高々2通りなので総当たり出来ることを利用すれば、どちらもsmall_roots()を試して解が存在したら、 $b_i$ のGuessが成功したことになる。

Code

from output import n, x, enc
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm


R = Zmod(n)
PR.<delta> = PolynomialRing(R)
# assumption: lsb of the flag is 1
y2 = inverse_mod(x, n) * enc[0] % n

flag = "1"
for c in tqdm(enc[1:]):
    found = False
    for b in [0,1]:
        lhs = (c * power_mod(x, -b, n) - y2) % n
        f = (lhs - delta**2)**2 - 4*delta**2*y2
        rs = f.small_roots(epislon=1/20)
        if len(rs) != 0:
            if found:
                print("[+] ha? (1)")
            flag = str(b) + flag
            found = True

    if not found:
        print("[+] ha? (2)")

print(flag)
flag = int(flag, 2)
print(long_to_bytes(flag))

Flag

hope{r4nd0m_sh0uld_b3_truly_r4nd0m_3v3ry_t1m3_sh0uld_1t_n0t?}