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

hamayanhamayan's blog

CTFのCryptoにおける数学まとめ

Security

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

本稿は数学科の人間が書いたものではないため、雰囲気をつかむ数学娯楽読本として楽しむこと。（恥知らずにも、数学のことを書くときはなんとなく予防線張っちゃうのですが...）

Cryptoにおける数学

  • 高校数学までは完了しているものとして話を進める（CTFer、中高生もそれなりにいるけど...）
  • 数学の世界広大すぎるので基本的にはトップダウンで（問題で必要になったら）勉強するで良いと思うが、全体地図を持っていた方がイメージが付きやすいと思うので書いておく
  • 全体地図

初等整数論

モジュラー整数

  • modを外したいときはf(x)=0 mod qならばf(x)+kq = 0のようにkを使って外す
  • X mod Yでgcd(X,Y)=1であれば、X^-1 mod Yは求められる
  • 数式が与えられてmodulusを求める問題
  • x = (x * a + b) % pのような変換を何回も繰り返して結果を予測する
    • 与式を式変形してxを求めれば、計算を行っても値が変わらないような入力を用意できる（つまり、変換後の値を予測可能になる）
    • corCTF 2022 writeup - Attack All Aroundのluckyguess
  • 線形合同式を何回か通した式は、離散対数問題として通した回数が復元可能
  • 不明なパラメタが全探索できないか？
    • randとかで少ない範囲であれば全探索で候補を絞り込めるかも
  • logを取るのは一般にムズイ -> 離散対数問題
  • x mod p, x mod qが分かればx mod pqは中国剰余定理で求められる
  • 計算の高速化を要求する問題
  • 素数pの二項係数は１じゃなかったらpの倍数なので…
    • (x+y)p ≡ xp + yp (mod p)
  • ミラーラビン素数判定法でfalse positiveを出す数は作れる
    • https://gist.github.com/keltecc/b5fbd533d2f203e810b43c26ff9d17cc
    • 適当に「break millerrabin」でググる
    • 例：99597527340020670697596886062721977401836948352586238797499761849061796816245727295797460642211895009946326533856101876592304488359235447755504083536903673408562244316363452203072868521183142694959128745107323188995740668134018742165409361423628304730379121574707411453909999845745038957688998441109092021094925758212635651445626620045726265831347783805945477368631216031783484978212374792517000073275125176790602508815912876763504846656547041590967709195413101791490627310943998497788944526663960420235802025853374061708569334400472016398343229556656720912631463470998180176325607452843441554359644313713952036867
  • 未知p,qであり、N=pqとpに関する式が与えられているとき、何とかしてpに関する式から「ほにゃらら=p×なんか」を生み出すことでgcd(N,ほにゃらら)=pを求める
  • Approximate GCD Problem
  • mod 2^mテク：これで変数の下位bitの候補が全探索可能かも。m=1から初めて、最下位ビットを特定したら、m=2,3,...と増やしながら下位ビットから特定していく https://furutsuki.hatenablog.com/entry/2022/06/05/152549
    • 例えば、mod 2470するといい感じの式が出てきて変数が1個だけだったら、そこからmod21とかmod22にすることは可能なので、その変数の下位ビットから特定することができる
      • どっちもありな場合が出てきたりするが、それで進めるとすぐ矛盾するので、枝刈り全探索でいける
  • p-1がAの倍数であれば、mod pで1のA乗根が存在する
  • mod N上で割るときはpowの-1乗を使うこと / aは* pow(a, -1, N)
  • pow(-1,e,n)=n-1
  • 法の変換テク
    • mod pqの値からmod pの値を求める、つまり、因数modを計算すると元の値からのmodでちゃんと計算できる
      • m^e mod nで何度もeとnが異なるものを取得可能で、確率的にnに小さい素因数が含まれるとき、nで小さい素因数pが手に入ったら、m^e mod nからm^e mod pを計算し、どこからm mod pを計算することで、これを何度も取得し、最終的にCRTでmを求める問題があった
    • mod pqrで取ったものをmod pqと解釈して解く。なんか色々良い感じになって問題ない場合もある(?)
    • mod Nから中身は全く同じ状態でmod pにして式を変形して更にmod Nに戻しても問題ない場合がある（うまくいきそうな雰囲気も感じられるが、うまくいくかどうかはケースバイケースな気がする）
  • n乗根 c = m^n mod p
    • ms = GF(p)(c).nth_root(e, all=True)で配列で複数候補出てくるので、全部試す
    • mod(c, p).nth_root(e, all=True)
    • 違いは分からん
  • mod 合成数でのe乗根を取りたい場合は、合成数が素因数分解可能であれば、分解してそれぞれe乗根を取ってCRTする python (sagemath) m1b_ps = GF(p)(m1be).nth_root(e, all=True) m1b_qs = GF(q)(m1be).nth_root(e, all=True) for m1b_p in m1b_ps: for m1b_q in m1b_qs: m1b = crt([int(m1b_p), int(m1b_q)], [p,q]) print(f"{m1b=}")
  • 「mod 偶数」の場合は最下位ビットの情報が計算によっていい感じに保存されるかも
    • zer0pts CTF 2020 - ROR
      • m^e mod 偶数の場合、「mの最下位ビット = meの最下位ビット」になる
    • 逆に奇数の場合
      • 2倍すると、modで切り捨てされないと偶数になり、modで切り捨てされると奇数になる
  • mod 2、mod 22、mod 23、…でp,qとかを下位ビットから埋めていけないか
  • 2重modの扱い方
    • 約数とかでない場合は、補助変数kを使って展開してLLLなり頑張るのかも
      • P(x) mod m1 mod m2 = rであるなら、k1, k2を導入して、P(x) - k1*m1 - k2*m2 = rと書き直してよいかも（m1 > m2の場合のみ？）
      • このとき、k2の大きさは大体m1/m2になる
  • 分数になると数が大きくなるから違う
    • idekCTF 2025 - Catch https://giapppp.github.io/posts/idekctf-2025/
      • Fp上で行列を計算していて、計算の逆計算をしていく問題。計算過程で使われる値はpよりも格段に小さい値であるという性質がある
      • このとき、割る順番が間違っていると計算結果が分数になり、分数になるということはmod計算で整数値に変換され、[0,p)のどれかになって大きい値になる可能性が高い。もし、割る順番があっていれば分数にはならないので、計算過程の小さい値が保たれる。よって、試し割してみて、数が大きくなるかどうかで正しいもので割れているかを判定できる
  • mod計算を伝搬させていくと、不明変数とのbits差が小さくて全探索できる
    • phi mod 2**500が分かっていてp,qが512bitsならば、phi=(p-1)(q-1)なのでp+q=N-phi+1とすることでp+q mod 2**500が求められる、p,qが512bitsなのでp+qは513bitsで差が13bitsなので全探索して、方程式の計算ができれば答えが得られるという方針
      • p+q,pqに解があるかを判定するには 判別式 D = (p+q)2 - 4pq が完全平方数であるかを確認すればよい
  • modテク
  • 指数計算が重いとき
    • オイラーの定理を使って指数部を減らす a^m mod p ならa^(p-1)=1なのでm'=m%(p-1)して a^m' mod pとできる
    • mod 合成数であっても
      • 合成数が素因数分解できるなら、分解して、mod pにすれば↑のオイラーの定理テクが使えて、最終的にCRTすれば元のmod 合成数での解が得られる
      • カーマイケル関数を使って a^k mod n = 1 となるkを見つけてきて、m' = m%kするという方針もある？
  • カーマイケルの定理 https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86#%E3%82%AB%E3%83%BC%E3%83%9E%E3%82%A4%E3%82%B1%E3%83%AB%E3%81%AE%E5%AE%9A%E7%90%86
    • 全てのaに対して、am=1 mod nを満たす最小のmを求める。オイラーの定理より、m=φ(n)のときam=1 mod nであることを示しているが、この時のmが最小であるとは限らない
    • n=pqならば、am=1 mod nを満たす最小のmは、m=lcm(p-1,q-1)=(p-1)(q-1)/gcd(p-1,q-1)
  • Ong-Schnorr-Shamir digital signature
  • 「mod 乱数」が与えられるとき、乱数は2とか3とかの倍数になりやすいので、「mod 2」とかできるかも
    • 「mod 乱数」の数が大量に与えられるので、mod 2,3,5,7,11,...とかをして最頻値を取ると確率的に正しいmod 2,3,5,7,11,...が得られるのでCRTして元々の数を復元する問題がでた - CrewCTF 2025 - inverse with error only
  • 問題
  • modガチャガチャ
  • mod計算で使えるやつ

平方剰余: Quadratic Residue

  • mod上で平方根を取る
  • 素数pと判定したい値aについて、ルジャンドル記号 (a/p) = a**{(p-1)\2} mod p
    • (a/p)=1 -> 平方剰余、pを法として、x2 = aであるxが存在する
    • (a/p)=-1 -> 平方非剰余、Quadratic Non-Residueと言うらしい
    • sagemathならkronecker(a,p)でトライ可能？
    • ルジャンドル記号の性質を使って数学的には判定する？
      • 素数pではなく合成数nを法としている場合は、それぞれの素因数で確認して=1のものがあれば、平方剰余
    • ルジャンドル記号の性質
      • 上の引数の完全乗法的関数 l(ab,p) = l(a,p)l(b,p)
  • 平方剰余の関係式
    • 平方剰余 × 平方剰余, 平方非剰余 × 平方非剰余 -> 平方剰余
    • 平方剰余 × 平方非剰余 -> 平方非剰余
    • これはルジャンドル記号から分かる
    • ちなみにaが平方剰余であれば-aは平方非剰余（逆も然り）
  • 大体mod(a, p).sqrt(all=True)で計算可能q
    • pが2か2のべき乗であるときは頑張る必要がある https://zenn.dev/kurenaif/articles/400a74f51bac31
    • pが奇素数、または、そのべき乗 mod(a, p).sqrt(all=True)でok
      • p = 4k+3であれば、|x^(1/2)| = x^((p+1)/4) で簡単に計算可能。±の候補があるので注意
    • 合成数の場合は、素数のべき乗に分解して mod(a, p).sqrt(all=True)して、CRTする
      • CRTするときは、それぞれの平方根の解が複数存在するので全探索する ```python (sagemath)

        mm = m2 mod n (n = pqr)

        fs = [p, q, r] ans = [] for f in fs: ans.append(mod(mm % f, f).sqrt(all=True)) for a0 in ans[0]: for a1 in ans[1]: for a2 in ans[2]: print(long_to_bytes(int(crt([int(a0), int(a1), int(a2)], fs)))) ```

  • 解は複数存在する可能性がある
  • 平方剰余問題は難しい問題であるが、難しさは素因数分解に相当する
    • これは素因数分解が解ければ平方剰余が解けるということだけでなく、逆も言えるということ（多分）
    • 平方剰余問題を前提とした、Rabin暗号や紛失転送プロトコルと、ゴールドワッサー-ミカリ暗号などがある
  • mod上での平方根の計算アルゴリズム
  • x2 = -1 (mod p)であるxが存在するか確認したい -> オイラーの規準を使って平方剰余の存在を確認する https://b1ue.x0.com/writeup/2023zer0pts/#easy_factoring
  • sagemath F = GF(p)として
    • 平方剰余であるかを判定 F(a).is_square()
    • 平方根計算 F(a).sqrt(all=True)
      • p = 4k+1の場合は数分かかるので注意
  • Rabin暗号: mod Nで平方根を求めるのが困難な平方剰余を数学的背景としている暗号
  • Goldwasser-Micali暗号方式
    • 平方剰余であるかの判定問題の難しさを前提とした暗号方式
      • 任意の整数 N=pqに対して、整数xがNの下で平方剰余であるかどうかを判定することが難しい
      • だが、p,qに素因数分解できている状態であれば易しい
    • 鍵生成：
      • 2つの異なる大きい素数p,qを生成する -> 秘密鍵p,q
      • N=pqを計算し、また、Nの非平方剰余であるyをランダムに選択する -> 公開鍵N,y
    • 暗号化：以下に見てわかるように1bitずつ暗号化を行う
      1. 暗号化したいビットbを選ぶ
      2. rをランダムに選ぶ (1≦r<N, かつ gcd(r,N)=1)
      3. b=0なら r2 mod N、b=1なら r2y mod Nを暗号として選ぶ
    • 復号化：暗号文cに対して、p,qを用いてNを法として平方剰余か判定して0/1に復元する
    • この暗号方式は実用的ではないが、セマンティックセキュリティという暗号文から平文に関するいかなる情報も得ることができないことを保証したものであり、その点で学術的に面白く、革新的であった（らしい）

連分数展開 / 連分数近似

線形代数学

  • ベクトル空間: 次の4つの公理を満たす体F上の集合V
    1. 集合は加法のもとにアーベル群
    2. スカラー倍: 集合Vの任意の元をv, 体Fの任意の元をcとする。vのスカラー倍cvは集合Vに属する
    3. 分配則: 集合Vの任意の元をv,w, 体Fの任意の元をc,dとすると、c(u+v)=cu+cv、および、(c+d)v=cd+dv
    4. 結合則: 集合Vの任意の元をv, 体Fの任意の元をc,dとすると、(cd)v=c(dv)であり、1v=v
  • 行列のRank
    • 行ベクトルの線形独立なものの最大個数
    • 行列を吐き出し法を使って、対角線上に1を並べていったときの1の個数
    • 行フルランク = 行列の全ての行が線形独立
  • 正方行列における離散対数問題
  • 行列の逆行列
    • 正方行列、かつ正則の場合 -> sagemath M.inverse() O(n3)らしい
    • 非正方行列の場合 -> sagemath As.pseudoinverse() O(n2m+m2n)らしい
    • (AB)-1 = B-1A-1
  • 行列と乗法におけるorder
    • 例えば、正方行列Mがあり、tn=M^n t0のようにMをn乗して計算するようなものが合った場合に、Mの乗法上の位数をM.multiplicative_order()と計算することで、tn=M^(n % M.multiplicative_order()) t0のように計算を簡略化できるかも https://blog.y011d4.com/20220926-ductf-writeup#time-locked
    • A.list() 行列を配列に変換
  • 上三角行列ってe乗すると、対角成分は元の行列の対角成分をe乗した値になる
  • ベクトル計算を行列計算にしてみる - SECCON CTF 2023 Quals - RSA 4.0
  • 行列の累乗は対角化を行うことで簡潔に表現できるようになるかも
  • 行列Aが対角化可能 -> A=PBP-1
    • 対角化可能な場合
      • Aが異なる固有値をn個持てば必ず対角化可能
        • Aに固有値の重複がある場合は対角化できない場合もあるが、その場合はジョルダン標準形がある
      • sagemathならジョルダン標準形を求めて、対角行列であるかを確かめる方法もある
      • Aが対称行列、エルミート行列のとき、直交行列で対角化可能
      • 最小多項式が分かっていると簡単に判別可能
        • 行列Aの最小多項式が重解を持たないなら対角化可能
  • ジョルダン標準形: 任意の行列Aについて、P-1AP=Jと変形することで得られるJのことで、任意の正方行列に対して存在する
  • 未知変数がn個のときはn個の方程式があれば解ける
  • エルミート標準形 -> LLLでちょっと出てきた
  • LU分解 S=LU

代数学

どれがどれに属すのかよく分かってないので全部横並びで書いておく。

群 Group

  • 群 Group: 乗法あるいは加法が定義されていて、次の4つの公理を満たす集合Gを群という。＋or×が定義されていると見ることもできる
    1. 集合Gの任意の元a,bについて、ab=cとなるような元cが集合Gに存在する
    2. 結合則 集合Gの任意の元a,b,cについて、a(bc)=(ab)c
    3. 単位元のe存在 集合Gの任意の元aについて、ae=ea=aとなる単位元eが集合Gに存在する
    4. 逆元の存在 集合Gの任意の元aについて、ab=ba=eとなる元bが集合Gに存在する
  • アーベル群、可換群：群 + 交換法則が成り立つ
  • 巡回群G: 0以外のすべての元がαのべき乗で表される群。αを原始元・生成元と呼ぶ
  • 部分群: 群Gの空でない部分集合Hが、群Gと同じ二項演算によって群になっているとき、HはGの部分群と言う
  • 2つの位数 order
    • 群の位数 |G| : 群Gに含まれる元の個数。無限なら|G|=∞
      • 位数が有限の群 -> 有限群、無限の群 -> 無限群
    • 元の位数: 群Gの単位元をeとするとき、Gのとある元aに対して an=eとなる最小の正の整数nが存在するとき、nをaの位数といい、ord a = nと書く
      • 存在しない場合の位数は無限大であるといい、ord a = ∞ となる
      • 任意の群の単位元eの位数は1
      • Gのとある元aに対して、正の整数nがan=eを満たしているとする。このとき、nはord aの倍数となっている
      • 全ての元aについて ord a ≦ |G|？
  • 群G1,G2について写像f:G1→G2が準同型写像であるとは、全てのx,y∈G1に対してf(x*y)=f(x)・f(y)が成立するときを言う（*はG1の演算で、・はG2の演算）
    • 核 ker(Φ) = {g∈G1|Φ(g)=e2} G2の単位元に写るG1の元の集合
  • ラグランジュの定理 有限群 G の任意の元の位数は群 G の位数の約数になる
  • 対称群: ものの並び替え操作を写像とした群
    • 位数は要素数をnとするとn!になる。123...nでなくてもlcm(1,2,3,...,n)でも上手くいくらしい
  • 置換群 PermutationGroup
    • https://pastebin.com/RcD816vd 前半に問題、後半に答え。 Grey Cat The Flag 2025 - Not A Permutation Matrix
      • 同型変換して何かしているがさっぱり分からない
  • 平方数ではない正の整数mに対して、ペル方程式 x2-my2=1 の整数解には群構造が入る

環 Rign

  • 環 Rign: 乗法および加法が定義され、次の4つの公理を満たす集合R。逆元の存在は要求しないので、＋,ー,×が定義されていると見ることもできる
    1. 集合Rは加法のもとにアーベル環
    2. 集合Rの任意の元a,bについて、abは集合Rに属する
    3. 結合則：集合Rの任意の元a,b,cについて、a(bc)=(ab)c
    4. 配分則：集合Rの任意の元a,b,cについて、a(b+c)=ab+ac、および、(b+c)a=ba+ca
    5. 整数環：整数は環
    6. 剰余類環: mod h上整数の集合は環
    7. 標数 ch A: Aを環、0∈Aを加法単位元、1∈Aを乗法単位元とする。1をn個足し合わせたときに総和が0となる最小のnをAの標数と言う。
      • そのようなnが存在しない場合は ch A = 0 とする（例えば整数環は1をどれだけ足しても0にならないので、ch Z = 0）
      • 性質
        • A,Bを環として、これらの間に単射環準同型f:A→Bが存在するなら、chA=chBである
          • 同時に示される対偶が面白く、つまり、標数の異なる環の間には単射環準同型は存在しない。なので、写像を考えるときは標数が同じもののみをグループ化して考えることができる
          • これは体で考えると顕著で、体の間の環準同型は自動的に単射になるため、標数が異なる場合は環準同型がない。つまり、体論は標数によって分断される
  • イデアル: 以下の性質を満たすとある環Rの部分集合I
    1. 集合Iは環Rの加法に関する部分群を成す
    2. 環Rの任意の元をr, 集合Iの任意の元をiとすると、irおよびriが集合Iに属している
    3. 主イデアル: 環Rのある元の倍数によって構成されるイデアル。整数rの整数倍の全体からなるイデアルを(r)と書く
  • 多項式の剰余類環
    • a1, a2, anがある体Fの元であるとき、f(x)=anxn-1 + an-1xn-2 + ... + a2x + a1を体F上の多項式という
    • 最高次数の係数anがan!=0であるとき、多項式f(x)の次数はn-1である
    • 最高次数の係数an=1のとき、モニック多項式
    • 体Fの上の田泓式が環をなし、多項式環と言う
  • 与えられた多項式f(x)に対し、f(x)|xe+1を満たす最小のeを多項式f(x)の周期という
    • f(x)|xeは、f(x)はxeの倍数という意味
  • gcd: 既約が定義できる整域ではgcdが定義できる？ -> 整数環、多項式環？

体 Field

  • 体 Field: 乗法に関する単位元が存在し、任意の非零元に対し、乗法に関する逆元が存在する可換環。つまり、四則演算が定義されている集合
    • 実際、体というのはあまり存在しないっぽい。具体的には以下の二択らしい（？）
  • 素数 p を法とした剰余環、すなわち、位数pの体を素体、あるいはガロア体と呼び、GF(p),Fpと書く
  • 有限体 Falois Field, GF(q)
    • 四則演算ができる有限要素の集合。qの値によって、どういう集合と計算を定義するかが異なる
    • ガロア体,素体(?): qが素数の場合 GF(p) -> 素体とも呼ぶ。整数の集合 {0,1,..,p-1} を考え、mod p上での四則演算を定義することでGF(p)となる
      • 原始元 g が存在し、0以外のFpの全ての要素はg**n mod pで表現可能
    • ガロア体(?) qが素数のべき乗の場合 GF(pn) -> 多項式の集合 {0,1, ... ,p-1,x,x+1,x+2, ... ,(p-1)xn-1+(p-1)xn-2+...+(p-1)} を考え、mod 既約多項式上での四則演算を定義することでGF(pn)となる
      • 簡潔には、最大次数をnとした多項式の剰余環である
      • 特にこのような場合は（ガロア）拡大体と呼ばれる
      • nによって使える既約多項式は決まっている https://qiita.com/kerupani129/items/58f337007cefd8d94c40
        • 既約多項式を使うことで、2n-1通りの重複しない元を生成可能（これに0を加えることで位数を2nにできる）
          • 既約多項式の一部は原始多項式で n乗することで0以外の全ての元が作れる
      • 既約多項式のよって複数のGF(pn)が考えられるが、お互いに全て同型である
    • 特に暗号ではGF(2n)が使われる
      • GF(2)では加算はXORで乗算はANDとなるため、アルゴリズムを数学でモデル化する際に都合がいい
      • GF(2n)では加算は係数ごとにXOR、乗算は指数の加算になる。この時、a2n-1=1になることを利用して次数を下げて計算を進める
      • 例えば、GF(24)で既約多項式p(a)=a4+a+1=0を使ったとする
        • a3+a9はa9 mod p(a)がa3+aのため、a3+(a3+a)=aとなる
        • (a+a3)(1+a2+a3)は展開するとa+a4+a5+a6となりmod p(a)するとa3+a+1
    • 原始元 primitive element
      • sagemath: F.primitive_element()で計算可能
        • primitive_root(p)でも、Fpの原始元が得られる
      • ガロア体GF(pn)の乗法群F×は巡回群となり、α ∈ F\{0}かつF\{0}={α^0,α^1,...,α**(p**n-2)}を満たすαが存在する
      • 点の位数が体の位数-1である点でもある primitive_element.multiplicative_order() == F.multiplicative_order()-1
  • 体の拡大とは実数を拡大すると複素数になるように、小さい体から大きい体へパワーアップさせるような操作で、その拡大の中でも特に「正規性」と「分離性」の2性質を満たすものをガロア拡大という
  • 拡大体 GF(pm)
    • P(x)をGF(p)の上の多項式とする。このとき、P(x)が既約、すなわち、GF(p)上で根を有しない場合、P(x)を法とする多項式の剰余環は体を成す
    • p個の元を有する体GF(p)上の多項式P(x)の次数をmとすると、pm個の元を有する体がP(x)を法とする剰余環を考えることができ、これをpm個の元を有するガロア体と呼びGF(pm)と書く
    • GF(p)を基礎体と呼び、このガロア体の位数はpmであるが、このガロア体の標数はp
    • 暗号ではGF(2m)が多い
      • sageではF = GF((p, k), "x")とすると、pを法としたGF(pk)が定義できる
    • 例えばX3+X+1を法として導かれる拡大体GF(23)は
      • GF(23)={0,1,α,α+1,α2,α2+1,α2+α,α2+α+1}
      • ここでαと書いているのは拡大体の元であることを強調するのにXの代わりにα,β,γを使うという慣習があるため
    • 拡大体 GF(pm) で、とある元xをxpにする計算は各係数をベクトルと考えると特定の線形変換となる
      • つまり、x^p = M * xの形で書ける
      • これにより、xをx^(p+1)にする変換を考えると、これは二次変換であると言える
        • つまり、x = (a1, ..., am)をx' = (1, a1, ..., am, a1*a1, a1*a2, ..., am*am)と変換して考えた時（定数項も入れているが変換上はマストではない。他の線形計算も入れ込みたいなら1を入れる）にx'^(p+1) = M * x'と考えることができる
      • 拡大体 -> ベクトル el.polynomial().padded_list(m)
      • ベクトル -> 拡大体 F(list(lst))
        • F = GF((p, m), "x")みたいな前提
    • 何も分かっていないが、GF(p16)をGF(p2)に変換して良い感じにやるみたいな変換テクがあるっぽい
    • pを素数としてq=pnと書くと、元の個数がqの有限体が（同型を除き）一意に存在し、Fqと書く
      • このとき、体の標数はpである（1をp個足すと0になる）
      • Fp⊂Fqであり、FqはFpのn次の拡大であるという
      • Fqの代数閉包を‾Fqと書く
    • sagemath
      • P.<x> = PolynomialRing(GF(2))としてF.<x> = P.quo(x^128 + x^7 + x^2 + x + 1)とするとGF(2128)が構築可能
      • ↑と同じ別の書き方x = GF(2).polynomial_ring().gen()としてF = GF(2 ** 128, name="A", modulus=x^128+x^7+x^2+x+1)
  • 最小多項式: 基礎体GF(p)とその拡大体が与えられたとき、拡大体の任意の元をβとする。基礎体GF(p)上で既約で m(β)=0となる最小次数のモニック多項式m(x)をβの最小多項式と呼ぶ
    • 拡大体GF(23)における元αの最小多項式はh(x)=x3+x+1

数論における便利定理や分野

  • 離散対数問題 -> 別稿で解説
  • ガウス整数
  • ディオファントス問題: 方程式が与えられたとき、その方程式の整数解や有理数解を求める問題
  • p進数体 p-adic
    • ここが初手分かりやすい https://tsujimotter.hatenablog.com/entry/hensels-lemma
    • ヘンゼルの補題
      • 素数pと整数係数多項式f(x)に対して、f(x_k)=0 mod pk かつ f'(x_k)!=0 mod pであるx_kがあるなら、x(k+1)=x_k mod pkを満たすx(k+1)が存在し、f(x_(k+1))=0 mod pk+1を満たす
      • f'(x_k)!=0 mod pはk=1で満たされればx_(k+1)=x_k mod p^iより任意のkで満たされる
        • つまり、x_1が計算可能で、f'(x_1)!=0 mod pであれば、x_2, x_3, x_4, ...は無限に計算できる
        • これはkを増やしていくことで、f(x)の根をどんどん高い桁数で計算できていくことになる。
    • p進対数は計算が容易なので、そのままでは離散対数が難しい体であっても同型なp進数体に変換できればp進対数として計算できるかも
      • p進対数が計算できるのは、p進数の単元群（units）に属すものだけ
      • つまり、正確には、とあるp進数の単元群の部分群に同型変換できれば、p進対数が使えて離散対数が解ける
        • log_p(g^m) = m × log_p(g)であるため
      • log_p(1 + x) = x - x²/2 + x³/3 - x⁴/4 + ...らしい
    • p進数体
      • 精度というのを指定でき、素数pに関するp進数体で、精度3であれば、a + bp + cp2という表現になる
      • p進付値 |x|_p 特殊なノルム
    • p進数体と同型
      • (Z/pnZ)* ... Zmod(pn)上の乗法群
        • 例）Zmod(p3)上でak=bのとき、kを求めたいとする
        • f: x -> xp-1 という変換をすると、Z/p3Z -> Qp
          • 位数がp2(p-1)から p2 に変化する（これはQpと同じ） (Z/p^3Z)*は位数がp2(p-1)であることから、直積分解ができ、(Z/p^3Z)* ≅ (Z/(p-1)Z) × (Z/p^2Z)*であるため、p-1の累乗を取ると前半が消えて後半だけになるらしい。（ほんとに？）
          • 変換後の要素a'はa' = 1 mod pになる（mod p3をmod pにして(p-1)乗すると考えると分かる）ので、a' = 1 + sp であり、これはp進対数が収束する（簡単に求められる）ので、あとは対数を取って割ればkが得られる。また、p進数体の精度は mod p3 なので、3桁で取れば良い
            • つまり、FQp = Qp(p, 3)としてprint(ZZ(FQp(ct).log()/FQp(g).log()).to_bytes(43))
            • p進数体の精度が自由に取れる
              • Henselの持ち上げによるもので mod p で解が分かれば mod p2 や mod p3 に持ち上げられる
              • = 1 mod pであれば、mod p2にしても1 + sp + tp2になるので同様にp進対数が収束する
        • (p-1)乗する写像はexp: Z/pZ → U = 1 + p Z/pZで、p進対数はlog:U → Z/pZで、logについては(U,*) ≅ (Z/pZ, +)と加法群に変換できるから解けるみたいな話みたい
      • 超特異楕円曲線 #E(Fp)=pの楕円曲線 -> Smart's Attack
        • 楕円曲線は加法群なのでそのままでは適用できないが、曲線をp進数にhensel liftingすることで、形式群のp進対数が適用できる
    • zer0pts ctf - pure division
    • BKCTF 2023 - DH
    • Crypto CTF 2022 - Starter ECC
      • https://blog.maple3142.net/2022/07/18/cryptoctf-2022-writeups/
      • y^2=x^3+ax+b mod p^63*q^6*r^5でx,a,b,p,q,rが分かってるときにyを求める
      • mod p, mod q, mod rでのyの解を求めてヘンゼルリフトしてCRTする
      • mod pでsqrtしなくてもmod p63のままでもp進数に変換すればそのままsqrtできる ZZ(Qp(p, prec=63)(y2).sqrt()) % (p ^ 63)
    • Infobahn CTF 2025 - YAOL

代数幾何学

関数 / 多項式

  • 関数、写像 f: y=f(x)のように書き、集合Xの元xを集合Yの元yに対応させる規則を指す
    • 単射: 集合Xの異なる元が集合Yの異なる現に対応する。つまり、違うxを与えると必ず違うyが出てくる、一対一関係になる
    • 全射: 集合Yの全ての元に対応する集合Xの元が存在する
    • 全単射: 単射+全射。この時逆関数が存在する
  • 高次方程式の求解
  • 二次方程式を解く from sage.all import PolynomialRing
    1. 変数作る R.<x> = PolynomialRing(ZZ)
    2. 連立方程式を作る（=0にして） f = x*(x*r1+(x+i)*r)-n
    3. 解くres = f.roots()
    4. 解を得るlen(res) > 0なら解けていて、q = res[0][0]みたいにとって来る
  • 連立方程式を解く from sage.all import PolynomialRing
    1. 変数作る R.<p, q> = PolynomialRing(ZZ)
    2. 連立方程式を作る（=0にして） f1 = N - p * q f2 = q * (r + b) + (q + a) * r - p
    3. 解くrr = f1.resultant(f2).univariate_polynomial().roots()
    4. 解を得るlen(rr) > 0なら解けていて、q = rr[0][0]みたいにとって来る
  • 合同方程式を解く
    • 法が素数の場合は若干無理しても多分解ける
    • 複数答えが出てくるので全部試す。↑のものは8次式（多分）だが一瞬で正しい答えが出てきた
    • 法が2の累乗の場合
      • とりあえず2次合同方程式は直接は解けなかった。R.<p> = PolynomialRing(GF(m)); f = ap * p^2 + cp * p - n; roots = f.roots()がダメだった
        • この場合は、良い感じに分解してやれば解けた
          1. ax2+bx+c=0を(x+b/(2a))2=b2/(4a2)-c/aと変換して、mod(右辺, m).sqrt(all=True)のようにmodのsqrtを取ってx+b/(2a)の値を得る
          2. x+b/(2a)=(1の解)の1次合同方程式を解く solve_mod(2 * x == int(((-1 * cp * pow(ap, -1, m)) + root) % m), m)
    • 法が合成数の時
      • 1次なら解けるが、2次以降は素因数分解できないと厳しい
  • 合同方程式をCRTする
    • https://blog.y011d4.com/20210829-cakectf-writeup#party-ticket
    • osu!gaming CTF 2025 - please-nominate
      • 複数の法の異なる方程式をCRTで合成してmodの法を大きくして、coppersmithする
        • 自分はf1(x) mod n1, f2(x) mod n2, f3(x) mod n3をn2n3f1(x) + n1n3f2(x) + n1n2f3(x) mod n1n2n3にしてcoppersmithしたけど、CRTでうまく合成している人もいるっぽい
  • 不動点 f(x) = x を満たす xのこと
  • irreducible polynomial -> 既約多項式
    • ある既約多項式 g(x) mod p を法とした多項式環は有限体となる（用語あってるかな？）
    • 位数はpmとなり、mは既約多項式の次数
    • また、オイラーの公式のように この多項式環の任意の多項式 f(x) に対して、 f(x)pm-1 = 1 となる
    • ちなみにこの有理数体上で平方剰余問題を考えることもできる
      • 同様にa^(p-1)/2)が1であるかどうかで判定も可能
  • 128次多項式は簡単に因数分解可能
    • sagemathのfactorで可能 python (sagemath) l = list(PQ.factor()) P = l[0][0] Q = l[1][0]
  • https://github.com/tsg-ut/tsgctf2023/blob/main/crypto/complicated_function/writeup.ja.md
    • q = f(p) = isqrt(p^2 + (2^512 - 6)p + cail(sqrt(p * sin p))) + 2^1023とpがあってN=pqのNが与えられている
    • 二分探索：f(p)はpに関して単調増加している（「p*sin p」部分は振動しているが影響が小さい）ので、pを増やすとN=pqも単調増加するため、pを二分探索することでN=pqとなるpが求められる
    • f(p)-pの収束：f(p)の係数項やsqrt(p*sin p)部分はpに対して大分小さく、pを大きくしていくにつれて影響が小さくなる。つまり、支配的になるのはisqrtの中のp2部分だけとなり、f(p)はpを大きくしていくと、p+定数に近づいていくと想像できる。pが1024bitsくらいだと整数部分では既に収束していて、実際21023+2511-4であることが分かるため、q=p+Cと書くことができ、N=pq=p(p+C)となりpに関する二次方程式となるためpが求まる
  • 用語
    • 解: 方程式の答え
    • 根: 多項式に対して=0としたときの答え
  • 終結式 https://ccmath.meijo-u.ac.jp/~mumr/2015/pdf/2015_04.pdf
  • 消去式 resultant
    • 簡単に言えば、2変数多項式f(x,y),g(x,y)が線形独立かつ共通根x0,y0を持つとき、yについての消去式h=Res_y(f,g)により得られるhは1変数多項式であり、h(x0)=0を満たす
  • 多項式をもっと早く解く方法
    • idekCTF 2025 - Diamond Ticket https://giapppp.github.io/posts/idekctf-2025/
      • s**73331 + s - fc = 0 mod pを解くと時間が無茶苦茶かかるので、mod p上であることを生かし、s**p - s = 0 mod pが成立することから、gcd(s**73331 + s - fc, s**p - s)をした結果の根を取ることでs mod pを求める。格段に速くなる
  • 9次式くらいならさっと解いてくれそう https://blog.y011d4.com/20210919-acsc-writeup#swap-on-curve
  • f(x)=a0+a1x+a2x2+...+anxnのような関数があり、任意の入力mに対してf(m)の結果が得られるとき、適当に小さい素数pを使ってf(p)を取得し、pの余りを取ってa0、pで割ってpの余りを取ってa1、...みたいにして係数を特定できる
  • ラグランジュ補間
    • n次の関数 y = a_0 + a_1 x + ... a_n xn の上の点がn+1分かっていれば関数が復元できる
    • 剰余環上でも使えるが、法は素数である必要がある（ほんとに？）
  • 多項式展開するとき g(X,Y,Z).simplify_full().expand()

グレブナー基底（グラブナー）

  • 計算量 最悪ケース: 二重指数時間 (doubly exponential)
    • 変数の数 n、次数 d に対して O(d2n) またはそれ以上
      • 例えば、変数: 35個、次数: 3 (各要素が3乗)、方程式: 35個ならばd2n = 3235 ≈ 334億 という天文学的な計算量
    • 最悪では O(22n)
  • グレブナー基底を使うモチベーション：「多項式の集合を、計算しやすい形に整理するための手法」
    • 複数の多項式の集合を与えることで、より計算しやすい、簡単な、かつ、解が等しくなる方程式が得られる
    • 利用例
      • c1 = pow(m + s, e, n)とc2 = pow(m + s * t1, e, n)とc3 = pow(m * t2 + s, e, n)で、t1,t2,eが既知で、m,sが変数 -> m^17+Aが得られた
  • zer0pts CTF 2021 - NOT Mordell Primes
  • 数学的には（ChatGPTに聞いたから微妙かも）
  • グレブナー基底を計算するアルゴリズム
  • グレブナー基底が計算できる前提条件
    • 単項式順序を定義する必要がある。CTFだと、実数体R上の多項式環のイデアルを考えるだろうので、普通に辞書式順序が使われそう
      • この単項式順序に従って計算することで、グレブナー基底が一意に定まる
      • 多項式÷多項式は複数の式変換候補が生まれる場合があり、その結果を一意にするためにやってる
  • 簡約グレブナー基底というのもある
  • ​​[質問] 変数除去をするだけなら終結式の方が確実な気がするんですけど、終結式に比べたグレブナー基底のメリットみたいのってありますか?
    • 確かにグレブナー基底使った方が計算早く終わったケースもあったので次数で使い所決めてみます
  • 変数除去には他にも色々やり方があるらしい
    1. Resultant（終結式） res = f1.resultant(f2, qhi) # qhiを消去
    2. シルベスター行列、Sylvester行列 syl = f1.sylvester_matrix(f2, qhi)
    3. 代数的消去 I.elimination_ideal([qhi])
    4. 多項式の因数分解 poly.factor()
    5. イデアルの基底変換 I.transformed_basis('fglm')
    6. 代数拡大での解法 solve([f1, f2], [qhi, qlo], solution_dict=True)
  • 勉強するとき
  • シンボリック実行して、グレブナー基底
    • osu!gaming CTF 2025 - ssss
      • Fp = GF(p)でRFp.<SECRET, a, b> = Fp[]として変数用意して、c.append(evaluate_poly(poly, x) - y)それを使っていい感じに方程式を作って、I = ideal(*c, p)イデアルにしてG = I.groebner_basis()グレブナー基底取って、s = -G[0].constant_coefficient()いい感じにする
  • 「終結式はシルベスター行列の行列式と等しい。」 https://manabitimes.jp/math/1202
    • よってどこかで拾った以下の式のようにシルベスター行列にして行列式を取って色々やると終結式が計算できる

他

  • neary equalをうまく使い、式を単純化することで、求めたい変数の近似値を求め、そこから周辺を全探索して条件に合うものを探してくる
    • AHR9 RSAMPC
      • bit数が倍くらい違えば小さいbitは無視して計算を進めると出てきた結果が誤差±10くらいになったりする
        • なんでこんなに近い値が出てくるのかはよく分かってない。512bitsくらいのものを無視したら、512bitsくらいのズレか、二次関数の一部であればsqrtである256bitsくらいのズレになるならなんとなく分かるが、そんなに近い値が出てくるの？
      • 近似の式はそのままで導出できなかったりするので、二分探索とかなんかで頑張って求める
    • SECCON Beginner CTF 2025 - mathmyth https://zenn.dev/claustra01/articles/873cac6a6ad323#%5Bcrypto%2C-hard%5D-mathmyth
      • 1064bit + 1016bitで後半を無視して近似してうまいことやってた
    • Nullcon Goa HackIM 2025 CTF - next-level
      • p = number.getPrime(512)でq = nextprime(p)でr = nextprime(q)であるとき、p,q,rはとても近い値になるので、N=pqrの3乗根を取って近辺を探すと大体p,q,rになっている
    • Cyber Apocalypse CTF 2021 - Wii Phit
      • https://blog.y011d4.com/20210424-cyber-apocalypse-ctf-writeup#wii-phit
      • 全体のサイズ感にもよりそうだけど、1000離れていると結構違うと判断している
      • w(xz+yz-wy)=4xyzだとxyzで割りたくなって、全体と比較して、1/zは比較的小さいので無視して、1/(x+1)は1/xに近似していい感じにやるとうまくいく
    • SECCON CTF 2021 - CCC https://project-euphoria.dev/blog/29-seccon-2021/#ccc
      • an = (ap+b)^3 - b^3をan ≈ (ap+b)^3と近似して、三乗根を取ってその周辺を探索して解く
  • 近似をうまく使う https://yun.ng/c/ctf/2024-0xl4ugh-ctf/crypto/18-karat-gold
    • 実験すると、q≈m_qであるときqをm_qに置き換えて逆計算をするとうまくいったりする（誤差ゼロ！）
    • n=(rp-p4)(rq-q4)で、rp,rqが24bitsでp,qが256bitsだと大小差から、n≈p4q4としてしまい、pq=n1/4で完全にpqが求まった int(n ** (1 / 4)) https://blog.y011d4.com/20220629-actf-writeup#secure-connection