はまやんはまやんはまやん

hamayanhamayan's blog

CTFのCryptoにおけるRSAまとめ [RSA, Coppersmith]

Security

CTFにおけるCrypto入門とまとめの1つです。

RSA

  • RSA: 素因数分解が困難であることを安全性の根拠とした公開鍵暗号
    • 鍵生成 素数p,qを作り、phi=(p-1)(q-1)を計算し、phiと互いに素なeを選択し、d=e-1 mod phiでdを計算する。(N,e)が公開鍵で、dが秘密鍵
    • 暗号化 c = m^e (mod n)で暗号化。Pythonだとc = pow(m, e, n)
    • 復号化 m = c^d (mod n)で復号化。Pythonだとm = pow(c, d, n)
  • 前提となってる数学的なことや性質
    • オイラーの定理
      • aとnが互いに素であり、φ(n)をオイラーのφ関数とするとき、a^φ(n) ≡ 1 mod nが成り立つ
    • phi: オイラーのφ(n), nに対してnと互いに素である1～nの自然数の個数
      • φ(n)=φ(pq)=(p-1)(q-1)である
      • 他にもφ(pqr)=(p-1)(q-1)(r-1)、φ(ppqq)=p(p-1)q(q-1)、φ(p^n)=p^(n-1)(p-1)、φ(ppp)=pp(p-1)、φ(pp)=p(p-1)、φ(p^rq)=(p-1)*p**(r-1)*(q-1)みたいな感じ
    • 乗法準同型性: RSAの暗号化処理をfとした場合に平文a,bに対してf(ab)=f(a)f(b)が成立
      • つまり、任意の平文から暗号文が作れるときに、暗号化したまま既存の平文に乗算できるということ
      • これを使って、適応的選択暗号文攻撃が可能
    • ちなみに、累乗計算は繰り返し二乗法（バイナリ法）で高速計算している
  • 簡単なRSA問題はRsaCtfToolで解けたりする setodaNote CTF Writeup (Crypto) - Tahoo!!
  • nが素数のとき（ポーリック・ヘルマン暗号）
    • gcd(n-1,e)=1のとき
      • d = inverse(e,n-1) dをこんな感じで計算する。
        • つまり ed = 1 mod (n-1) なので ed = k(n-1) + 1
      • m = pow(c,d,n) 復号化は普通
        • (me)d = med = m^{k(n-1) + 1} = m
          • 最後の部分はm^(n-1) = 1 mod nなのでm^{k(n-1)} = 1となるため
    • gcd((n-1)/2,e/2)=1のとき
      • d = inverse(e//2,(n-1)//2) そのままじゃ逆数計算できないので、2で割って無理矢理やる
        • つまり ed/2 = 1 mod {(n-1)/2}なのでed/2 = k{(n-1)/2} + 1でed = k(n-1) + 2
      • mm = pow(c,d,n)とする
        • mm = (me)d = med = m^{k(n-1) + 2} = m2
      • Cipollaのアルゴリズムを使って m2 = x (mod n) でx,nが既知の状態からmを求める
  • eとphiは互いに素である必要がある
  • Nが分からないとき
    • (-1)eが計算できると、N-1(mod N)が得られるので、+1すればNが得られる
    • eが既知で平文と暗号文の組がいくつか得られるときは、gcd(平文1^e-暗号文1, 平文2^e-暗号文2, 平文3^e-暗号文3, ...)をすればNが得られる
  • ed = 1 mod phiであるので、ed = 1 + k * phiということになるが、このときのkはそれほど大きくないので全探索可能だったりする（理屈はよくわかっていないが、min(e,d)くらいの大きさ？）
  • RSA-CRT m = c^d mod Nの計算をCRTを使って高速化する手法
    • Nを素因数分解してN=p1*p2*...*pnであるとする
    • di = d mod (pi-1)をしてdiを求め、mi = c^di mod piでmiをそれぞれ求める
    • こうすると、mi = m mod piになっているので、CRTでp1～pnをまとめるとm mod Nが求まる
    • Fault Attack https://hackmd.io/@Xornet/ryoP8VxUw

攻撃手法

nの素因数分解が出来てしまう

Low Public-Exponent Attack

Håstad's Broadcast Attack（同報通信、同一平文の問題, Hastad Broadcast Attack）

  • m,eが同じでNが異なるメッセージがいくつかある場合、Hastad's broadcast attackという攻撃が可能
  • c1 = m^e (mod N1) c2 = m^e (mod N2) ...というのが与えられているので、中国剰余定理を使うことでmod N1N2...におけるmeが得られて、後はe乗根を取れば平文に戻せる
  • m<Nであるはずなので、N1,N2とかのbit数を見れば何個のサンプルを使ってcrtしてやればいいか分かる
    • 例えば、eが3とかであれば、サンプルを3つ集めればmodがN1*N2*N3のようになるので、N-1を3乗してもちゃんと収まって解ける。ゴミデータが混ざっていてもサンプル3つを全探索で集めてやればよいという問題であった。
  • Wikipediaにある一般化
    • https://en.wikipedia.org/wiki/Coppersmith%27s_attack#H%C3%A5stad's_broadcast_attack
    • 互いに素な合成数を法とする一変数方程式系 g_i(M)=0 mod Ni が十分な数与えられると解ける
    • CakeCTF 2021 Party Ticket https://blog.y011d4.com/20210829-cakectf-writeup#party-ticket
      • c=m(m+b) mod nでn,b,cが異なるものが2組与えられるので、共通するmを求める
      • 最終的にはCoppersmithで解くが、そのためには個々の方程式だとmが十分小さくならないので、方程式を合成してmを十分小さくすることでCoppersmithする（ということだと思う。多分）
      • gi(m)=m(m+b)-c mod niとして構成したg1(m)=0 mod n1とg2(m)=0 mod n2から合成した、G(m)=0 mod n1n2 を作る
        • そのために、G(m)=(n1の倍数でなく、n2の倍数)*g1(m) + (n2の倍数でなくn1の倍数)*g2(m)mod n1n2を構成することを考える
          • これならmod n1、mod n2にすると元の方程式になる
        • この倍数を特定するのにCRTを使う(n2の倍数)=CRT([1, 0], [n1, n2])とすると、n2の倍数だが、n1の倍数ではない数が得られる
          • y011d4さんのブログにあるように、つまりは、クロネッカーのデルタδijを使って、Ti=δij mod nj for all jとなるTiをmod n1n2で求めて使うことになる
      • あとはCoppersmith
  • plain RSAに対する攻撃手法を実装してみる - ももいろテクノロジーが単純で読みやすい実装
  • 問題

Common Modulus Attack

  • Nと平文mが一緒で異なるeで暗号化した暗号文cの組がある場合、拡張ユークリッド互除法を用いて平文mを復号可能
  • mp+qが分かっている場合、mp-1(q-1)=1であることを使うと、mp+q=mN+1になり、meと合わせるとCommon Modulus Attackができる。gcd(N+1,e)=1
  • gcd(e1, e2) > 10の場合は攻撃が難しいらしい

Wiener's Attack

  • 1989年にWienerが提唱した、dが小さいことを利用した攻撃
  • 求め方
    • de=k(p-1)(q-1)+1 を近似していくと de≈knなので、e/n ≈ k/dと変形できる
    • e/nを連分数近似していくと、何処かの近似値がk/dと一致するようになり、k,dが求められる
      • とあるk,dが正しいかどうかはde=k(p-1)(q-1)+1から(p-1)(q-1)を求め、n=pqからp,qを求めてp,qが素数であるかを検証すればいい
  • だが、Coppersmith法を使ったBoneh-Durfee Attackというのがあり、d < n^0.292を満たすときに使える上位互換
    • 詳しくはCoppersmithの中で説明
  • 一般的な形
    • 無知：平文m1, m2
    • 既知：e, N, 暗号文c1, c2, 関数f(x)
      • このときm2 = f(m1)であることが分かっている
    • この時に、m1を高速に計算可能
  • 理屈
    • 関数f(x)=2x+1であるとする。以下は全部mod Nを省略する
    • m1e = c1 であるから g1(x) = xe - c1 とすると g1(m1) = 0
    • (2m2+1)e = c2であるから g2(x) = (2x+1)e - c2 とすると g2(m1) = 0
    • g1もg2も同じx=m1を根として持つので、
      • g1(x) = (x - m1) h1(x)
      • g2(x) = (x - m1) h2(x)
      • のように共通の多項式を持つ
    • よって、g1とg2の公約式を求めることでx - m1の式を得ることができ、m1の値が得られる
  • どうやって公約式を求めるか
  • https://project-euphoria.dev/blog/27-rsa-attacks/#franklin-reiter-related-message-attack
    • 関数f(x)は線形変換である必要はないし、eも共有している必要はない（e1, e2でそれぞれ違っていても良い）
  • より一般的には、無知である要素が平文部分のみである方程式が2つ手に入れば良い
    • SECCON 2020 CTF - urara https://jsur.in/posts/2020-10-12-seccon-2020-ctf#urara
      • EC上の点P(m, 乱数)に対して2P(Qx,Qy)が分かっている状態であれば、(3m^2+a)^2+4(m^3+am+b)(Qm+2m) = 0であることが分かる
      • もう一つ(m+t)^e-c = 0というのが分かっているので、mをxにしてf(x),g(x)を用意してgcdすれば(x-m)という項が出てくるはず
  • e,Nが共有で、2つの平文m, m+dがあったとする。つまり、2つの平文の差が判明している場合
  • https://www.yumpu.com/en/document/read/54527505/ctf-crypto-matome
    • ここによると、「e,nが同じ、かつ、enc(m)とenc(am+b)であれば攻撃可能らしい」
  • m1=m+d1, m2=m+d2でc1=(m+d1)eとc2=(m+d2)e mod Nとなっていて、c1,c2,e,N,d1,d2が既知である状態でも、m'=m+d1とすれば元の形にできるので解ける

Fermat's Method

  • 2つの素数に対して N=pq=(a+b)(a-b) と表現できる
    • p,qの間が小さい場合、aはNのおおよその平方数となり、bは小さくなる
    • よって、Nの平方数周りをaとして採用して、bを全探索すれば素因数分解可能
  • フェルマー法 https://tex2e.github.io/blog/crypto/fermat-factorization-method の実装が一番良い
    • p,qはnの平方根付近になるので、そのあたりで探索
    • nが4092bitsで、pとqの差が512bitsくらいなら直ぐ出てきた
  • (a+b)(a-b)と表現できて、aが比較的簡単に計算できて、bが全探索可能な大きさであれば何でも適用可能
    • 2つの合成数に対しても適用可能 https://project-euphoria.dev/blog/19-ccc-2021/#no-stone-left-unturned
      • 11q = 7p + 11xということが分かっていて、11xが520bitsくらいで小さいため11q ≈ 7pであることが分かる
      • また、11qと7pはどちらも奇数であるため、(a+b)(a-b)と表現可能
      • そして、pとqの積であるNは既知であるため、11*7*Nに対してフェルマー法が適用でき、11q, 7pが得られたら、それぞれ割り算すればp,qが求まる
  • (a+b+1)(a-b)の場合で作問できそうでは？
  • 3乗での応用例 SECCON CTF 2022 - CCC
    • 式をこねくり回すと、aN = s^3 - b^3という式が出てくる。条件は以下
      • a, Nは既知で、s = ap+b
      • 大きさはaが23なので5bits, pが1024bits, bが691bits、よってsは1029bits, Nは2058bitsということで
        • 3082bits = 1029bits^3 - 691bits^3という感じなので、b3は半分ほどの大きさしかないため、無視できるほど小さいと見る
    • 以上の情報から aN ≈ s^3であると言えるため、sの値はaNの3乗根にとても近い所にあると推測される
    • よって、aNの3乗根を取り、+0,+1,+2,...+10000をsの値として、s^3-aNが立方数になるものを探していく
      • 立方数となれば、a3-aNの3乗根がbとなり、sも既知であるため、pを求めることができる（よって、qも求まり、RSAが解ける）
  • 問題

Multi-prime RSA: 3つ以上の素因数からなるRSA

  • n=pqrであれば、φ(n)=(p-1)(q-1)(r-1)が分かれば良い
    • ちなみに、(p-1)(q-1)(r-1) = n+(pq+qr+rp)+(p+q+r)-1なので、そっちが分かるのでも良い
  • Fireshell CTF 2019 Biggars writeup - ふるつき
  • sagemathで素因数分解したら3つ以上の素因数へ分解でき、かつ、個数が多い場合はCRTを使って復元していく

復号化時間を正確に取得できる場合はタイミング攻撃が成立するかも

LSB Decryption Oracle Attack / LSB Oracle Attack

Coppersmith's Method/Attack

Coppersmithは「整数方程式」の絶対値の小さな整数解を多項式時間で求める手法。RSA問題の部分問題としてこのような問題がでてくるので、CoppersmithがRSA問題を解くのに使える。RSA問題以外でも良く出てくる。

Coppersmithの歴史

  • 1996年 Coppersmithが提案した手法
    1. 2変数「整数方程式」の絶対値の小さな整数解を多項式時間で求める手法 - Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known
      • RSAの秘密鍵導出攻撃ができる。N=pqのpとqの上位半分のビットp',q'が分かっているときに、(p'+x)(q'+y)-N=0がx,yがN1/4程度なので解ける
      • 非常に難解なため、Coronによって再定式化された以下の論文での理解がオススメ
        • 2004 Finding Small Roots of Bivariate Integer Polynomial Equations Revisited
          • Coppersmithの手法より少し劣っていた
        • 2007 Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach
          • Coppersmithの手法と同等に
      • https://www.jstage.jst.go.jp/article/bjsiam/18/3/18_KJ00005033174/_pdf 他にも研究が続けられていることが分かる
    2. 1変数整数係数合同方程式の絶対値の小さな整数解を多項式時間で求める手法 - Finding a Small Root of a Univariate Modular Equation
      • RSAの平文回復攻撃ができる。平文mの |m-m'|<N1/e上位ビットm'
      • 非常に難解のため、Howgrave-Grahamによって再定式化されたより簡潔な手法による説明が一般的らしい
        • 1997 Finding Small Roots of Univariate Modular Equations Revisited
  • 有名問題とCoppersmith: 有名問題をCoppersmithで解くという観点で攻撃に名前がついていたりする

最強のCoppersmith's Method Solver - cuso

https://yu212.hatenablog.com/entry/2025/07/27/163347

1変数の場合

  • 1変数の合同方程式に関する最も汎用的な形
    • Nを既知の整数, モニックな1変数δ次多項式f(x)の答えを知りたい
      • モニックとは最高次係数が1であるような多項式
    • 0＜β≦1を決める
      • β=1とすると mod Nでのみ考えることになる
      • β<1とすると N^β≦b かつ b|N である mod bでも答えを導くことができる
        • これが非常に重要でRSAだとmod Nの合同式が得られることが多いと思うが、βを調整することでmod pでの根が得られたりする
    • このとき、f(x') = 0 (mod b) かつ |x'|≦Nβ2/δ を満たすx'を求めることができる
      • 計算量はlogN,δの多項式時間
        • 計算時間はβの値には依存しない
    • 以上のことを考えると、Nは別に大きくてもよさそうだが、式変形などを頑張ってδをなるべく小さくする（多項式の次数を下げる）ことで、計算可能なx'の範囲も広がるし、計算時間も短くなるので嬉しい
    • この手法がSagemathのsmall_roots関数やPari/GPのzncoppersmith関数で採用されている
  • sagemathのsmall_roots関数
    • 使い方 python PR.<x> = PolynomialRing(Zmod(n)) f = e * (s + 2**470 * x) - 1 - k * (-1) * (rq - 1) # 多項式を用意 f = f.monic() # モニック多項式である必要があるので変換 roots = f.small_roots() # 解く ans = int(roots[0]) # intでキャストしないとバグるので注意
    • small_roots(self, X=None, beta=1.0, epsilon=None) https://github.com/sagemath/sage/blob/e7477f887968f0f133e15618ad5444473aa8fb4b/src/sage/rings/polynomial/polynomial_modn_dense_ntl.pyx#L471
      • X: 根の上界。つまり、|x'| < Xを満たすXのこと
        • 省略されるとX = ceil(1/2 N^{\beta^2/\delta - \epsilon})で計算される
        • 省略せずに2^Kbitsみたいにギリギリでちゃんと指定したほうが良さそう
        • X < N^(1/degree)
      • beta: 上で説明しているβ。mod Nで計算したい場合はβ=1とする（つまり省略）。Nの約数modにしたい場合は、ギリギリまで調整する
      • epsilon: 「根の近似度」や「誤差」の量を制御するためのパラメータ
        • 多変数の多項式の解の近似を求める際に重要です。特に、RSAのような大きな整数問題を扱う場合、ϵ の選び方によって、解がどれだけ正確に求まるか、または計算が成功するかに影響を与えます
        • 小さい根を求める場合（小さな公開鍵の因数分解など）：ϵ は比較的小さく設定される傾向があります。これは、多項式の小さな根を近似的に求める場合に高い精度が必要であるためです。
        • より大きな問題に対する攻撃の場合：ϵ は問題のスケールに応じて調整されることがあります。例えば、整数のサイズが大きくなるほど、適切な近似のために大きめのϵ が必要になることがありますが、攻撃の成功率を維持するためには、依然として小さめに設定することが多いです。
        • 一般的には、ϵ は logN （NはRSA modulus）の一部に比例する形で選ばれることが多いです。
        • デフォルトはepsilon = beta/8。epsilon = beta^2/7としているものもある
      • パラメタ色々
      • sageのsmall_rootsはbetaを適当な値にしたら法nの代わりにnの約数を法とした式をそのまま法nで突っ込んでも正しい答えが得られることがあるっぽい
        • nとpののbit数がかなり離れている必要がある？
    • パラメタガチャ py for i in trange(1, 101): cur_sol = f.small_roots(X=2**(8*flag_len), beta=i/100)
  • テク
    • 未知変数は全体に対して小さくないといけないし、次数はある程度小さくないと計算できない。終結式とかグレブナー基底で簡単にするとうまくいくかも？
    • 法は約数modとして考えて答えを出すこともできる
    • 約数modで計算できることを利用して、元々の法の値が分からなくても、因数が共通なら計算できちゃう
      • Full Weak Engineer CTF 2025 Multi ﾊﾟﾜｰ RSA
        • A+d=0 mod p^(r-1)(p-1)(q-1)を計算したいのだが法は分かってない状態で、A+d=0 mod NでCoppersmithして計算するとdが求められる。これは、A+d=0 mod p^(r-1)(p-1)(q-1)であるならばA+d=0 mod p^(r-1)であると言えて、またN=pr qであるならば、mod Nでcoppersmithするとmod pr-1での答えが求められるためである。d < p^(r-1)なら正確な値が出せる。
        • 元問題をPrime-Power RSA(Takagi RSA)と呼ぶみたい？
    • 2乗や3乗のものは扱えないのだが、2乗や3乗してもまだ小さければそれを1つの変数として扱ってしまえる
    • Coppersmithの高速化テクがある？ Codegate 2024 FactorGame https://blog.y011d4.com/20240602-codegate-writeup#factorgame
  • Coppersmithに祈りの要素はあまりなさそう

多変数の場合

  • 一般に変数の数が増えれば増えるほど解くための条件が厳しくなるため、なるべく変数の数を減らす方向で考察する必要がある
  • 多変数の方程式を解くときはdefundのライブラリを使うのが良い
  • （あまり理解してない。ガチャ）

初めて勉強する人が読むべき資料

  • shihoさんの https://elliptic-shiho.github.io/slide/katagaitai_winter_2018.pdf
    • 必ず最初に読むべき。ちゃんと飛ばさずに読むこと
    • 特に「方程式を増やすパート」についてはこれ以上分かりやすい説明は多分なく、実際に計算できる問題も付いている
  • 2つ目の資料として本「暗号の理論と技術」が良い
    • 多変数の場合の話が書いてあるのと、LLLにどんな格子を投げるかについて色々書いてある
  • （偉そうに書いているけど、全然理解できてません。cusoでブラックボックス的に解けてしまうので、背景の理論を定期的に忘れる）
  • （あと、ちゃんと原論文を読めないとダメなんだと思います）

Coppersmithで解ける問題などなど

RSA署名：RSAで公開鍵署名をするとき（秘密鍵で暗号化して、公開鍵で復号化して検証するとき）

https://www.jnsa.org/active/topics/rsa_doc.pdf

  • 公開鍵(N,e)で秘密鍵dであったとする
    • mを署名するとき、md mod Nを計算して渡す
    • もらったmdに対して(md)e mod Nを計算することで復号化して検証する
  • パディングについて
    • RSAは復号ができても、それが正しく元のメッセージになっているとは限らない
    • つまり、メッセージの真正性を検証する必要があり、その用途のためにパディングが用いられる
    • パディングをつけて暗号化し、復号化した後にパディングが正しいかを検証することになる
  • 署名enc関数のブラックボックス実行環境が与えられているとき、公開鍵Nを特定する方法
    • gcd(enc(2)^2 - enc(4), enc(3)^2 - enc(9))が公開鍵N
    • これはenc(2)^2 - enc(4)がmodNだと0にはなるが、2部分はmodNがかかからないので、ちょうどNの倍数になっている
    • よって、こういう例をいくつか用意してgcdを取るとNが特定できる
  • RSA署名には乗法性がある。f(m)=md mod Nとすると、f(a)f(b)=ad*bd=(ab)d=f(ab) mod N
    • 小素数法 f(m) のmが素因数分解可能な場合に、その素因数pを署名したf(p)が得られればその情報でf(m)が得られる
  • RSA-FDH署名: RSA署名にハッシュ関数を組み合わせた方式
    • 安全性は向上しているが、効率はあまりよくないらしい

RSA-OAEP

PKCS #1 v1.5