# kurenaif 2000 subscribers challenge writeup
###### tags: `writeup` `kurenaif2000` `crypto`

## 問題概要

$e=20000$ と 20 bit のランダムな素数 $p$, $q$ を用いて $b$ bit の数 $m$ を RSA 暗号で暗号化したものが 2×200 個与えられる。$m$ を解読せよ。
問題: https://github.com/kurenaif/kurenaif_2000_subscrivers_challenge

## 解法

まず、$p$ と $q$ が十分小さいので素因数分解が簡単にできる。なので、$p$ と $q$ は与えられるとして良い。
すると $m \bmod pq$ は容易に求めることができそうであるが、今回はそれをすることができない。なぜならば、$\phi(p\cdot q)=(p-1)(q-1)$ と $e$ が互いに素でないため、複数個の候補が出てきてしまうからである。しかしこの複数個の候補は十分高速に求めることができる[^1]。なので、これらから flag を復元することを考えよう。$m \bmod n_1$ と $m \bmod n_2$ が分かっているとするとき、中国剰余定理から $m \bmod n_1n_2$ を求めることができる。そのため、候補のうち正解を選ぶ組み合わせを全て試せば理論的には解読できることになる。しかし候補は 2000 個近くあるため、これではうまくいかない。しかし、$m < 2^b$ だったことを思い出せば、$2^b \le M$ ならば $(m \bmod M) < 2^b$ が成り立つことが分かる。これを用いて枝刈りをすると、そこそこの時間で $m$ を求めることができる。

[^1]: [Tonelli-Shanks のアルゴリズム](https://37zigen.com/tonelli-shanks-algorithm/)等

## スクリプト

from itertools import product
from Crypto.Util.number import long_to_bytes
from output import ns, cs, e

bit_length = 383

candslist = [mod(c, n).nth_root(e, all=True) for n, c in zip(ns, cs)]
candslist.sort(key=lambda l: len(l))
ms = [mod(0, 1)]
for cands in candslist:
    ms = [m.crt(cand) for m, cand in product(ms, cands)]
    ms = [m for m in ms if int(m).bit_length() <= bit_length]
    if len(ms) == 1 and int(ms[0]).bit_length() == bit_length:
        break

print(long_to_bytes(int(ms[0])))