この記事はCTF Advent Calendar 2021の14日目の記事です。1つ前の記事はkeymoonさんが時間跳躍してSECCON CTF 2021 参加記/Writeup - 雑記を書いてくれました。

(時間跳躍前はネコチャンminaminao/ctf-blockchain: Summary of CTF Blockchain Challengesでした。)

今年取り組んだCrypto問題は妙にRSA暗号に対する攻撃を一般化して他でも使えるような問題が多かったので、RSAに対する有名な攻撃を一般化して他でも使えたような例を幾つか紹介します。

Table of Contents §

はじめに §

英語が読める方は各攻撃の英語版WikipediaとTwenty years of attacks on the RSA cryptosystemを読めばこの記事は不要です。ここまでのご閲覧ありがとうございました。

また、タイトルはかの有名な資料であるRSA暗号運用でやってはいけない n のこと #ssmjpをリスペクトしました(勝手に使ってごめんなさい)。

Prerequisite §

この記事を読むにあたって次の知識が必要になります。

  • RSA暗号
  • 扱う攻撃のRSA暗号に対する利用方法
    • 後述の「RSA暗号運用でやってはいけない n のこと」等を参照
  • Coppersmith's Attack
    • Coppersmith's Attack自体が多変数の場合も含めて強力なソルバになる事は有名なので今回は扱いません
  • 終結式
    • Coppersmith's Short Pad Attackで利用

Fermat's Method §

RSA暗号運用でやってはいけない n のこと、では「その3」で紹介されている素因数分解方法です。

よく知られているフェルマー法の適用条件は2つの素因数「の差が小さい」というものですが、これは近い2数の積が整数と小さい整数を利用してと表す事が出来る事が出来る事を利用しています。割と「2つの素因数」に対する特効として流通しているようなイメージですが、アルゴリズムを見ればわかるように特に素数である事を利用しているわけではありません。というわけで「2つの差が小さい合成数」の積の因数分解にも拡張出来ます。

これがRSA暗号の問題で特に効く場合はの近似整数比がわかっている場合です。次のように2つの素数の近似整数比をおいてみます。RSAの例では当然ですがとします。

$$ \frac cd \approx \frac pq $$

これによってという近似が成り立ちます。よってであることから、は2つの近い因数を持ちます。よってに対してフェルマー法を適用することでが求められるので、あとはこれを既知ので割れば無事にの素因数分解が出来ます。

問題例 §

Håstad's Broadcast Attack §

RSA暗号運用でやってはいけない n のこと、では「その9」で紹介されている攻撃です。

異なる法で公開鍵の指数回暗号化された場合に中国剰余定理を使えば復号出来るという攻撃です。

余談ですが、これは平文のサイズに関わらず復号可能な回数が回ということであり、平文のサイズが小さければこれより小さい数の暗号文を持ってくることで復号出来る可能性があります(Triplet Luna - TSG Live CTF)。これについても正確に書こうと思いましたが、下記一般化に比べれば、攻撃アルゴリズムを読むだけでわかるほぼ自明な事実なので軽く述べるに留まります。

さて、肝心の一般化ですがこれはの異なるにおける連立方程式とみなす事が出来るので、を一般の次以下のモニック多項式に拡張し、連立方程式を解きます。

これを添字を用いて定式化すると、共通根を持つ高々次のモニック多項式 個与えられた状況でを求める問題になります。もちろんとします。

また、はどのような2つを持ってきても互いに素であるとします。そうでなければ2つので最大公約数を求めることで素因数分解が出来るので、そので復号すれば問題は解決します。

この問題は個の多項式を、中国剰余定理を上手く使って係数を求めて線形結合するとを法としたモニック多項式が得られ、これはの線形結合であることから高々次であり、しかもが根の1つであることから、Coppersmith's Attackを使って解く事が出来ます。

ではそんな都合の良いをどうやって導出するかですが、まず次のような係数を定義します。

$$ T_i = \begin{cases} 1 \mod n_i \cr 0 \mod n_j \ (j \neq i) \end{cases} $$

これは中国剰余定理を用いる事で求める事が出来ます。

続いてこの係数を用いてを構成します。この多項式はモニック多項式であり、を満たします。以下で本当でそうであるかを証明しますが、結果だけ欲しい人はCoppersmith's Attackを使うステップまで飛ばしてください。

まずモニック多項式である事を示します。次(つまり最高次数)の係数をとおくと、各がモニック多項式であることから、を満たします。の構成方法から、が各に対して成立します。

ここでを総和を用いた定義でなく、を法とした連立方程式を中国剰余定理を使って解くことで法の下で求める事を考えます。この連立方程式は実は自明でという整数を持ってくれば各方程式を満たすことがわかります。そして、中国剰余定理より、法の下で解は一意であることから、が成り立ちます。つまり、はモニック多項式になります。

では続いてを満たす事を示します。はその構成方法から次を満たします。

$$ T_i \equiv 0 \mod \prod_{j=1, j \neq i}^e n_j $$

また、であるので、この2つから次のような整数が存在します。

$$ \begin{aligned} T_i &= k_0 \times \prod_{j=1, j \neq i}^e n_j \cr g_i(m) &= k_1 n_i \end{aligned} $$

よって両式を掛けることでが成り立ちます。これはつまりを意味します。

したがって、これを各に対して総和をとると次のようになり、が示されます。

$$ G(m) \equiv \sum_{i=1}^e T_ig_i(m) \equiv 0 \times e \equiv 0 \mod N $$

これで根がである次の多項式が得られ、であることから、Coppersmith's Attackを利用してを求める事が出来ます。

問題例 §

RSA暗号運用でやってはいけない n のこと、では「その11」で紹介されている攻撃です。パディング方法が既知のような状況で2つの平文が線形の関係にある場合にを消去してが根となる多項式を2つ用意して公約式を求めるという攻撃です。

具体的には次のような場合を考えます。

$$ \begin{aligned} c_1 &\equiv m_1^{e_1} \mod n \cr c_2 &\equiv m_2^{e_2} \equiv (am_1 + b)^{e_2} \mod n \end{aligned} $$

この時、という2式を用意すると、となるので、Euclid互除法の要領で公約式を求めるとという多項式が出てきてくれます。

もうこの説明の時点で気付いたかもしれませんが、の線形変換である必要もRSAの形である必要もありません。法が同じで共通根を有していればどんな2つの多項式でもこの攻撃を適用出来ます。

なお、多項式の次数が大きくなると単純なEuclid互除法で求めるのは遅くなります。特にRSAで良く使われるでは単純なSageの実装で数十分はかかります。そこで多項式の除算と余りの導出の計算量を抑えたものを用いるHalf GCDという手法もあるのですが、筆者があまり理解していないので名前を紹介するのに留めます。興味がある人はググってください。

問題例 §

Coppersmith's Short Pad Attack §

RSA暗号運用でやってはいけない n のこと、では紹介されていませんが、後半に名前だけは載っている攻撃です。

前述のFranklin-Reiter Related Message Attackではパディングの形式等が既知で、2つの多項式はだけが未知数であったため合同式を用いて解く事が出来ました。そこで未知数が増える事を考えます。

平文に対してを既知とする次のような線形パディングを考えます。但しは未知の比較的小さい数とします。

$$ \begin{aligned} m_1 \coloneqq Am + r_1 \mod N \cr m_2 \coloneqq Am + r_2 \mod N \end{aligned} $$

この関係からである事がわかります。が小さかった事からも小さくなります。

本来のRSA暗号であればとおくことになり、が解になります。

ここで、終結式を用いてを消去した式を得るとについての多項式となるのでCoppersmith's Attackを用いてを求め(が求解可能なレベルで小さい事が条件)、それをに代入することでFranklin-Reiter Related Message Attackへ帰着させるという攻撃になりますが、特にこの形の多項式に限定した攻撃では無いため、に一般性を持たせる事が出来ます。

やや話題が逸れますが終結式自体も「変数を減らす」という点ではかなり強力な概念で、手計算だと骨が折れる式変形を終結式に投げる事で簡単に求める事が出来ることもあります(example: Madras - ASIS CTF 2021)。同様の概念にグレブナー基底というものもあります。どちらも有用でCTFでの応用例もありますが、本ブログの趣旨を超える為、紹介だけに留めます。

問題例 §

ここまで書いて、前半2つはそれなりに「日本語記事としての」新規性がありそうな気がしますが、後半2つは手法自体の解説に「多項式が一般化出来る、自明だよね?」みたいな事を言って問題例を挙げているだけな気がしてなりません。まあいいや。

あとがき §

ここまで読んで頂きありがとうございました。この記事が、「RSA暗号運用でやってはいけない n のこと」を読んだ人が次に読んで得るものが多く、楽しめる記事になっていると嬉しいです(もちろん既知の人も再確認等で楽しめるともっと嬉しいです)。

本当は問題例に載せた問題を解くコードも交えて解説しようと思いましたが、面倒な上に時間も無かったのでやめました。Writeupリンクを載せたのでそちらを御覧ください。

なお、問題例をあまり挙げられていないので、今後参加したCTFに類似の問題があったらそれを追加していくかもしれません。もし、良い例がありましたら@Xornet_Euphoriaまでリプライを飛ばしていただけると幸いです(定型文ですが、スパム対策のためフォロー外へのDMは解放していません。怪しく無ければDMリクエストは承認します)。

ところで、私が問題作成で携わったSECCON CTF 2021に参加してくださった皆様、ありがとうございました。本当は昨日の12/13に自分の作った問題のWriteupを投稿しようと思ったのですが、諸事情で22日に投稿する予定に変更した(これもまた変更されるかもしれない)ので、私の問題を解いた皆さんはこの間に「作者が書くだろうから」なんて言わず投稿してください。CTF中に解いて無くても復習や途中までの過程でも「解けねえよ、作問者出てこい」みたいな苦情も大歓迎です(現時点で思ったより少なくて泣いています)。

CTF Advent Calendarの明日の担当は...いません。というわけでSECCON CTF 2021に出た皆さんはWriteupを書くチャンスですよ!! そうでない方もWriteupでも何でもいいので何か書いて皆で強くなってCTFプレイヤー全員でCTF全クリしましょう。

それが無ければ1日飛んでDiKOさんが

LLL入門してみます

という内容で書いてくれるそうです。投稿されたら、その記事をきっかけにCTFプレイヤー全員でLLLを習得しましょう。これは蛇足なんですが、SECCON CTF 2021のCryptoでは3/6が格子を使う問題だったらしいですね。記事が公開されたら読んで格子完全理解して解きましょう。

参考資料 §

  1. RSA暗号運用でやってはいけない n のこと #ssmjp
  2. Twenty years of attacks on the RSA cryptosystem
  3. Fermat's factorization method - Wikipedia: Multiplier improvementの節
  4. Coppersmith's attack - Wikipedia
  5. SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー
  6. CryptoHack – RSA challenges