昨日参加した Hack.lu CTF 2020 で解けなかった暗号問題 Bad Primes の復習となります。CTFtime に載っている writeup を参考にしました。この writeup を見ると Stack Exchange を引用しています。

問題設定

基本的には普通の RSA と一緒です。ただし公開鍵 $n (=pq)$ を計算するための素数 $p, q$ は既知とします。また、 $e = 65537$ です。 このとき、ある平文 $m$ を暗号化した $c \equiv m^e \mod n$ が与えられており、それらを使って $m$ を復号するという問題です。

従来の RSA と異なるのは、本来ですと $\gcd(e, \phi) = 1$ となるような素数 $p, q$ を用いるのですが、この問題では $p-1 \equiv 0 \mod e$ となっており、 $\gcd(e, \phi) = e$ です。すると $ed \equiv 1 \mod \phi$ となる $d$ が存在せず、 RSA での復号方法 $m \equiv c^d \mod n$ は成立しません。これを復号するにはどうすればいいでしょうか。

実は次のことが成立しているとき、 $m$ の候補を $e$ 個に絞ることができます。

• $e$ は素数
• $p-1 \equiv 0 \mod e$ かつ $p - 1 \not\equiv 0 \mod e^2$
• $q-1 \not\equiv 0 \mod e$

復号方法

• $\lambda = (p-1)(q-1)/\gcd(p-1, q-1) = \mathrm{lcm}(p-1, q-1)$
• $L \equiv k^{\lambda/e} \mod n$ ($k$ は位数が $\lambda$ となる任意の整数)
• $d \equiv e^{-1} \mod \lambda/e$

としたとき、 $c^d L^i \mod n$ ($0\le i < e$) が $m$ の候補となります。

証明

まず、 $m' \equiv c^d L^i \mod n$ で計算される $m'$ が $(m')^e \equiv c$ を満たすことを示します。 証明には カーマイケルの定理 を使います。カーマイケルの定理より、 $\lambda(n) = \mathrm{lcm}(\lambda(p), \lambda(q)) = \mathrm{lcm}(p-1, q-1)$ となる $\lambda(n)$ を用いて、 $a^{\lambda(n)} \equiv 1 \mod n$ ($\gcd(a, n) = 1$) となります。この $\lambda(n)$ が「復号方法」で定義した $\lambda$ となります。 $d$ は法を $\lambda/e$ としたときの $e$ の逆元という定義ですが、これは $\mathrm{lcm}(p-1, q-1)$ が $e$ でちょうど1回しか割り切れないことから存在が示せます。 実際に $c^d L^i$ で求まる値を $m'$ として計算すると、

となります。これを $e$ 乗すると、 $(m')^e \equiv m^e (m^x k^i)^{\lambda} \equiv m^e$ となるため、このようにして求まる $m'$ は $(m')^e \equiv c$ を満たします。

次に $i \ne j$ のとき $L^i \ne L^j$ であることと、 $L^e \equiv 1$を示します。 これ の命題9.11 (1) を使います。再掲すると、$m$ を2以上の自然数、$a$ を $m$ と互いに素な整数、 $s$ を法 $m$ に関する $a$ の位数としたとき、 $s = uv$ ならば法 $m$ に関する $a^u$ の位数は $v$ となります。 $k^{e(\lambda/e)}$ に上記命題を適用すると、 $k^{\lambda/e} = L$ の位数は $e$ となります。位数の定義により、示せました。

以上をもって $m' \equiv c^d L^i \mod n$ について $0\le i < e$ をそれぞれ計算すれば、 $e$ 通りの解が求まります。今 $m^e = c$ となる $m$ はたかだか$e$個しかないため、この方法で計算される $m'$ のどれかが $m$ となります。

実装

Hack.lu CTF 2020 の Bad Primes について解いてみました。

from Crypto.Util.number import long_to_bytes, inverse, GCD

n = 3283820208958447696987943374117448908009765357285654693385347327161990683145362435055078968569512096812028089118865534433123727617331619214412173257331161
p = 34387544593670505224894952205499074005031928791959611454481093888481277920639
q = 95494466027181231798633086231116363926111790946014452380632032637864163116199
e = 65537
c = 2152534604028570372634288477962037445130495144236447333908131330331177601915631781056255815304219841064038378099612028528380520661613873180982330559507116
assert p * q == n

_lambda = (p - 1) * (q - 1) // GCD(p - 1, q - 1)
assert _lambda % e == 0
assert _lambda // e % e != 0
L = pow(2, _lambda // e, n)
assert L > 1
d = inverse(e, _lambda // e)
assert e * d % (_lambda // e) == 1

for i in range(e):
    tmp_flag = long_to_bytes(pow(c, d, n) * pow(L, i, n) % n)
    if b"flag" in tmp_flag:
        print(tmp_flag)

flag{thanks_so_much_for_helping_me_with_these_primitive_primes}