Writeup: CryptoHack/Adrien's Signs

ルジャンドル記号あたりで学びを得たのでまとめておきます。

Source

source.py

from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b'crypto{????????????????????}'


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext


print(encrypt_flag(FLAG))

FLAG のビット列に対して、1 ビットずつ以下の処理をしています。

1. $1 \le e \le p$ を満たす整数 $e$ をランダムに選択
2. $n = a^e \bmod p$
3. ビットが 1 であれば $n$ の符号を反転

Point

ルジャンドル記号は乗法性をもつ ( $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ ) ので、ビットが 0 の場合、

$$
\left(\frac{-n}{p}\right) = \left(\frac{-1}{p}\right) \left(\frac{n}{p}\right)
$$

この $\left(\frac{-1}{p}\right)$ がポイントです。

ルジャンドル記号には第 1 補充法則というものがあります。

$$
\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} =
\begin{cases}
1 & \mbox{ if }p \equiv 1\pmod{4} \\
-1 & \mbox{ if }p \equiv 3\pmod{4}
\end{cases}
$$

この問題は $p \equiv 3 \pmod 4$ を満たす（ぜひご自身で計算してみてください）ので、

$$
\left(\frac{-1}{p}\right) = -1
$$

したがって、

$$
\left(\frac{-n}{p}\right) = - \left(\frac{n}{p}\right)
$$

$\left(\frac{a}{p}\right) = 1$ であり、かつ平方剰余な数はその冪も平方剰余なので、$n = a^e \bmod p$ は平方剰余だといえます。

結論として、ビットが 1 の場合は $\left(\frac{n}{p}\right) = 1$ 、0 の場合は $\left(\frac{n}{p}\right) = -1$ です。

Solution

a = 288260533169915
p = 1007621497415251

ciphertext = [...]  # output.txtを参照

plaintext = ''.join(['1' if pow(c, (p - 1) // 2, p) == 1 else '0' for c in ciphertext])
flag = ''.join([chr(int(plaintext[i:i+8], 2)) for i in range(0, len(plaintext), 8)])

print(flag)