CTF crypto 逆引き

粗削りだけどとりあえず公開することにして、少しずつ情報を足していきたい。こういうケースがある、またこういう場合はどうすればよいのかという情報や質問をお待ちしています。

RSA
ブロック暗号
楕円曲線暗号
その他の暗号
- onetime pad
- (EC)DSA で同一のnonceが複数回用いられている

黙って Twenty Years of Attacks on the RSA Cryptosystem や Recovering cryptographic keys from partial information, by example を読んでおけば大体なんとかなる

e が 3など

Low Public Exponent Attackが適用できる。例えば、 $m^e \lt n$ であればe乗根を取ることで $m$ が手に入る

出題例

InterKosenCTF writeup - ふるつき

nが多くの素因数に分解される

いわゆるMulti-Prime RSA。 $n$ がどう素因数分解されようともオイラーのφ関数は定義できて、 $\mod n$ での位数がわかるので逆元 $d \equiv e^{-1} \mod \phi(n)$ が求められる。

出題例

Fireshell CTF 2019 Biggars - ふるつき

nがある素数と別の合成数までは素因数分解できる

実際には $n = p*q*r$ だが、 $p \lt q,r$ でnを素因数分解した結果 $n = p*c$ （ここで $c=q*r$ ）までは得られたが、 $c$ の素因数分解は難しそう、というとき。このとき $m \lt p$ であれば、 $\mod p$ の世界で考えることで $m$ を得られる。

出題例 募集中

nが同じでeが異なる複数の暗号文

Common Modulus Attackが適用できる。複数の $e$ が互いに素ではない場合には、それぞれの $e$ の最大公約数を公開鍵とした暗号文が手に入ることになる

出題例 募集中

何度でも任意の暗号文を復号でき、復号結果のうち一部が手に入る

LSB Leak Attackが適用できる。一度に手に入る平文のbit数が多い代わりに、復号の試行回数に制限がある場合もある。LSB Leak Attackには2種類のアプローチがあると思っている。

一つはよく説明されるもので、次の通り。

$(2^eC)^d \equiv 2m \mod n$ について考える。 $2m \lt n$ であれば $2m$ は2倍されているので偶数、すなわちLSBは0となる。一方で $2m \gt n$ でれば、復号結果は $2m - n$ となるから（ $2n \gt 2m \gt n$ ）偶数と奇数の減算で奇数になる*1。すなわちLSBは1となる。ということは、 $2^eC$ の復号結果のLSBが0ならば $0 \lt m \le \frac{n}{2}$ が、LSBが1ならば $\frac{n}{2} \lt m \lt n$ がわかる。次に $4^eC$ についても同様に考えて、次々と $m$ の範囲を2分探索的に縮めていき、 $m$ の値を求める。

もう一つの方法は、次のようなもの。個人的にはこちらのほうが明快。

$C \mod n$ の復号によって得られるLSB Oracleは $m$ の最下位bitである。では $2^{-e}C \mod n$ の復号結果から得られるLSB Oracleはどうか。これは $2^{-1}m \mod n$ の最下位bitであり、 $m$ の下から2番目のbitの値である。さらに $2^{-2e}C \mod n$ の復号結果か得られるLSB Oracleは $m$ の下から3番目のbitの値で……とこれを $m$ のbit数だけ繰り返すことで $m$ の全体がわかる。

出題例

$\mod 3$ でのLSB Leak Attack BambooFox CTF 2019 Oracle writeup - ふるつき

pやqに関連する値を暗号化している

うまく暗号文同士のgcdをとったり、 $\mod p$ などについて考えることによって秘密鍵を入手できる場合がある。

出題例

Harekaze mini CTF 2020 作問者writeup - ふるつき

mやp, q, dの値が一部わかっている、近似できる

LLLやCoppersmith methodを使ってmやp, q, dを求めることができる。Coppersmithも内部ではそれっぽい格子を生成してLLLをしているのでどちらでも解ける。sageに実装されているCoppersmith methodは一変数多項式に対するものだが、多変数多項式に対してはdefundさんが実装しているものが出来がよく、これを使っておけばだいたいなんとかなる。

github.com

出題例