粗削りだけどとりあえず公開することにして、少しずつ情報を足していきたい。こういうケースがある、またこういう場合はどうすればよいのかという情報や質問をお待ちしています。
黙って Twenty Years of Attacks on the RSA Cryptosystem や Recovering cryptographic keys from partial information, by example を読んでおけば大体なんとかなる
e が 3など
Low Public Exponent Attackが適用できる。例えば、 であればe乗根を取ることでが手に入る
出題例
nが多くの素因数に分解される
いわゆるMulti-Prime RSA。がどう素因数分解されようともオイラーのφ関数は定義できて、での位数がわかるので逆元が求められる。
出題例
nがある素数と別の合成数までは素因数分解できる
実際には だが、 でnを素因数分解した結果 (ここで)までは得られたが、の素因数分解は難しそう、というとき。このときであれば、の世界で考えることでを得られる。
出題例 募集中
nが同じでeが異なる複数の暗号文
Common Modulus Attackが適用できる。複数のが互いに素ではない場合には、それぞれのの最大公約数を公開鍵とした暗号文が手に入ることになる
出題例 募集中
何度でも任意の暗号文を復号でき、復号結果のうち一部が手に入る
LSB Leak Attackが適用できる。一度に手に入る平文のbit数が多い代わりに、復号の試行回数に制限がある場合もある。LSB Leak Attackには2種類のアプローチがあると思っている。
一つはよく説明されるもので、次の通り。
について考える。 であればは2倍されているので偶数、すなわちLSBは0となる。一方ででれば、復号結果は となるから( )偶数と奇数の減算で奇数になる*1。すなわちLSBは1となる。ということは、の復号結果のLSBが0ならばが、LSBが1ならばがわかる。次に についても同様に考えて、次々との範囲を2分探索的に縮めていき、の値を求める。
もう一つの方法は、次のようなもの。個人的にはこちらのほうが明快。
の復号によって得られるLSB Oracleはの最下位bitである。ではの復号結果から得られるLSB Oracleはどうか。これはの最下位bitであり、の下から2番目のbitの値である。さらにの復号結果か得られるLSB Oracleはの下から3番目のbitの値で……とこれをのbit数だけ繰り返すことでの全体がわかる。
出題例
- でのLSB Leak Attack BambooFox CTF 2019 Oracle writeup - ふるつき
pやqに関連する値を暗号化している
うまく暗号文同士のgcdをとったり、などについて考えることによって秘密鍵を入手できる場合がある。
出題例
mやp, q, dの値が一部わかっている、近似できる
LLLやCoppersmith methodを使ってmやp, q, dを求めることができる。Coppersmithも内部ではそれっぽい格子を生成してLLLをしているのでどちらでも解ける。sageに実装されているCoppersmith methodは一変数多項式に対するものだが、多変数多項式に対してはdefundさんが実装しているものが出来がよく、これを使っておけばだいたいなんとかなる。
出題例
- mの一部がわかっている例 [InterKosenCTF 2019] E_S_P - HackMD
- p, q がそれぞれ一部わかっている例 pwn2win 2020 writeup - ふるつき
dが同じでnやeが異なる暗号文
かつ、dがある程度小さければSmall Common Private Exponent Attackができる。
出題例
2つの平文の間にm1 = a*m2 + bという関係がある
かつ、 既知のとき、Franklin-Reiter's Related Message Attackが使える
出題例
ECBモードで、任意の平文+フラグが暗号化される
いわゆるChosen Plaintext Attackができる。
出題例
- CSA Capture The Flag 2019 Writeup - よっちんのブログ(Flag Server)
CBCモードで平文の先頭1ブロック程度を変更できれば良い
Bit Flipping Attackで十分
出題例
CBCモードで復号の成否がわかる
Padding Oracle (Encryption) Attackができる。
出題例
2段や3段の暗号化で、使われている鍵が短い
Meet in the Middle Attackができる。
出題例
独自のS-BOXが使われている
Differential / Linear Cryptoanalysis だろうけど理解してないのでかけない
基本的な事項はだいたいすべて yoshi-gcc log - ふるつき にあります
onetime pad
絶対にmany time padなので頻度解析をしながら鍵を当てていくとだんだん解けます。
出題例
(EC)DSA で同一のnonceが複数回用いられている
いわゆるnonce-reuse attack
出題例
*1:すなわちが素因数に2を含んでいる時にはこの攻撃は成立しない、と思う