この記事は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つの素因数「p,qp,qの差が小さい」というものですが、これは近い2数の積が整数aaと小さい整数bbを利用してN=(a+b)×(a−b)N = (a+b) \times (a-b)と表す事が出来る事が出来る事を利用しています。割と「2つの素因数」に対する特効として流通しているようなイメージですが、アルゴリズムを見ればわかるように特に素数である事を利用しているわけではありません。というわけで「2つの差が小さい合成数」の積の因数分解にも拡張出来ます。

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

cd≈pq \frac cd \approx \frac pq

これによってcq≈dpcq \approx dpという近似が成り立ちます。よって(cq)×(dp)=cdN(cq) \times (dp) = cdNであることから、cdNcdNは2つの近い因数cq,dpcq, dpを持ちます。よってcdNcdNに対してフェルマー法を適用することでcq,dpcq, dpが求められるので、あとはこれを既知のc,dc,dで割れば無事にNNの素因数分解が出来ます。

問題例 §

Håstad's Broadcast Attack §

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

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

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

さて、肝心の一般化ですがこれはf(x)≔xe−c≡0mod  Nf(x) \coloneqq x^e - c \equiv 0 \mod Nの異なるNNにおける連立方程式とみなす事が出来るので、ffを一般のee次以下のモニック多項式に拡張し、連立方程式を解きます。

これを添字を用いて定式化すると、共通根mmを持つ高々ee次のモニック多項式 gi(x)mod  nig_i(x) \mod n_i がee個与えられた状況でmmを求める問題になります。もちろんm<min⁡i(ni)m \lt \min_i(n_i)とします。

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

この問題はee個の多項式を、中国剰余定理を上手く使って係数を求めて線形結合するとN=∏ini>meN = \prod_i n_i \gt m^eを法としたモニック多項式G(x)G(x)が得られ、これはgi(x)g_i(x)の線形結合であることから高々ee次であり、しかもx=mx=mが根の1つであることから、Coppersmith's Attackを使って解く事が出来ます。

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

Ti={1mod  ni0mod  nj (j≠i) T_i = \begin{cases} 1 \mod n_i \cr 0 \mod n_j \ (j \neq i) \end{cases}

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

続いてこの係数を用いてG(x)=∑i=1eTigi(x)G(x) = \sum_{i=1}^e T_ig_i(x)を構成します。この多項式はモニック多項式であり、G(m)≡0mod  NG(m) \equiv 0 \mod Nを満たします。以下で本当でそうであるかを証明しますが、結果だけ欲しい人はCoppersmith's Attackを使うステップまで飛ばしてください。

まずモニック多項式である事を示します。G(x)G(x)のee次(つまり最高次数)の係数をTTとおくと、各gig_iがモニック多項式であることから、T=∑i=1eTiT = \sum_{i=1}^e T_iを満たします。TiT_iの構成方法から、T≡1mod  niT \equiv 1 \mod n_iが各nin_iに対して成立します。

ここでTTを総和を用いた定義でなく、nin_iを法とした連立方程式を中国剰余定理を使って解くことで法NNの下で求める事を考えます。この連立方程式は実は自明でT=1+kNT = 1+kNという整数を持ってくれば各方程式を満たすことがわかります。そして、中国剰余定理より、法NNの下で解は一意であることから、T≡1mod  NT \equiv 1 \mod Nが成り立ちます。つまり、G(x)G(x)はモニック多項式になります。

では続いてG(m)≡0mod  NG(m) \equiv 0 \mod Nを満たす事を示します。TiT_iはその構成方法から次を満たします。

Ti≡0mod  ∏j=1,j≠ienj T_i \equiv 0 \mod \prod_{j=1, j \neq i}^e n_j

また、gi(m)≡0mod  nig_i(m) \equiv 0 \mod n_iであるので、この2つから次のような整数k0,k1k_0, k_1が存在します。

Ti=k0×∏j=1,j≠ienjgi(m)=k1ni \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}

よって両式を掛けることでTigi(m)=k0k1NT_i g_i(m) = k_0k_1 Nが成り立ちます。これはつまりTigi(m)≡0mod  NT_ig_i(m) \equiv 0 \mod Nを意味します。

したがって、これを各iiに対して総和をとると次のようになり、G(m)≡0mod  NG(m) \equiv 0 \mod Nが示されます。

G(m)≡∑i=1eTigi(m)≡0×e≡0mod  N G(m) \equiv \sum_{i=1}^e T_ig_i(m) \equiv 0 \times e \equiv 0 \mod N

これで根がmmであるee次の多項式G(x)G(x)が得られ、m<min⁡(n1,…,ne)<N1em \lt \min(n_1, \dots, n_e) \lt N^{\frac 1e}であることから、Coppersmith's Attackを利用してmmを求める事が出来ます。

問題例 §

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

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

c1≡m1e1mod  nc2≡m2e2≡(am1+b)e2mod  n \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}

この時、g1(x)≔xe1−c1mod  Ng_1(x) \coloneqq x^{e_1} - c_1 \mod Nとg2(x)≔(ax+b)e2−c2mod  Ng_2(x) \coloneqq (ax+b)^{e_2} - c_2 \mod Nという2式を用意すると、g1(m1)≡g2(m1)≡0mod  Ng_1(m_1) \equiv g_2(m_1) \equiv 0 \mod Nとなるので、Euclid互除法の要領で公約式を求めるとx−m1mod  Nx-m_1 \mod Nという多項式が出てきてくれます。

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

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

問題例 §

Coppersmith's Short Pad Attack §

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

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

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

m1≔Am+r1mod  Nm2≔Am+r2mod  N \begin{aligned} m_1 \coloneqq Am + r_1 \mod N \cr m_2 \coloneqq Am + r_2 \mod N \end{aligned}

この関係からm2=m1+δ (δ≔r2−r1)m_2 = m_1 + \delta \ (\delta \coloneqq r_2 - r_1)である事がわかります。r1,r2r_1, r_2が小さかった事からδ\deltaも小さくなります。

本来のRSA暗号であればf1(x)≔xe1−c1mod  N,f2(x,y)≔(x+y)e2−c2mod  Nf_1(x) \coloneqq x^{e_1} - c_1 \mod N, f_2(x, y) \coloneqq (x+y)^{e_2} - c_2 \mod Nとおくことになり、x=m1,y=δx=m_1, y = \deltaが解になります。

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

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

問題例 §

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

あとがき §

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

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

なお、問題例をあまり挙げられていないので、今後参加したCTFに類似の問題があったらそれを追加していくかもしれません。もし、良い例がありましたら@Xornet_までリプライを飛ばしていただけると幸いです。

ところで、私が問題作成で携わった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