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

hamayanhamayan's blog

CTFのCryptoにおける古典暗号まとめ

Security

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

古典暗号

  • 古典暗号: 1960年代までの暗号の総称
    • エニグマまでが古典暗号っぽい？
    • サイモンシンの暗号解読はここを沢山扱っている
    • 現代暗号と古典暗号の違いは、アルゴリズムと鍵の分離、アルゴリズムの公開、オープンな場での研究・開発、民間での商用利用などがある
  • 古典暗号/換字式暗号: 文字を変換して暗号化
    • 単一換字式暗号: 暗号化の前後でアルファベットが1対1で対応
      • シーザー暗号, ROT13
      • 文字の出現頻度を計算して解析していく
      • quipquipというWebサービスで解析
    • 多表換字式暗号: アルファベットの対応表を複数作成して、何らかのルールに基づいて使う表を変えて変換する
      • ヴィジュネル暗号
      • カシスキーテスト: 繰り返し出てくるtheのような単語を探して、鍵長を推測し、サイクルを特定したら、offset毎に文字の出現頻度を解析する
  • 古典暗号/転置式暗号: 文字の場所を入れ替えて暗号化
    • レールフェンス暗号
      • 平文をジグザグにならべて、横に書き下したもの
    • シーザー暗号
  • CTFでは謎の文字列やバイト列が与えられて、暗号方式をguessして根性で解析してねと言う問題が出てくる。頻度解析などを真面目にやればいいのかもしれないのだが、知識ゲー/ガチャガチャゲーすぎて自分はあまり好きではない。推測成分が多いので、問題文や問題名にヒントが含まれていたりするので、それを元に推測したり実験したりしていく。ステガノグラフィーに似ているかもしれない。

頻度解析

  • 英文だとeが多く登場しやすいみたいな頻度を解析することで復元する問題
  • quipqiup https://quipqiup.com/ が使える
  • 例えば特定の文字が特定の暗号文やハッシュになるみたいな状況なら適当にアルファベットに当てはめて出力してやって頻度解析フェーズはquipqiupにやられるという方針も取れる

暗号やエンコード色々

ROT13、シーザー暗号、モールス信号、ヴィジュネル暗号あたりが有名。

CTFのCryptoにおける細かな話題まとめ

Security

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

その他の解法方針

ツール

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

CTFのCryptoにおける格子まとめ

Security

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

格子とLLL

LLLに関連する重要な問題

SVP: Shortest Vector Problem

  • SVP: Shortest Vector Problem, 格子Lの中で最も短い非零のベクトルを探す問題
    • 次元が4以下であれば多項式時間で解くことができる -> Gaussian Lattice Reduction
    • それ以上の場合は近似アルゴリズムを使う -> LLL（多項式時間ではある）
    • c=sum(a[i]x[i])、つまり、f(x) = a[1]x[1] + a[2]x[2] + ... + a[n]x[n] - c = 0みたいな形で、また、結果が（xの値が）小さいときに使えるかも
      • この情報だけを格子に入れ込むと、xが大きい解も出てきてしまうので、xの値を小さくするような制約を入れる必要がある
    • xの範囲は大きな値を入れると、f(x)がより小さくなるxを見つけることができるらしい
  • SVPを近似的に解くアルゴリズムがLLL
  • 似たような名前の難しい問題がいくつかあるみたい https://ctf-wiki.mahaloz.re/crypto/asymmetric/lattice/introduction/
    • γ-Approximate Shortest Vector Problem (SVP-γ)
    • Successive Minima Problem (SMP)
    • Shortest Independent Vector Problem (SIVP)
    • Unique Shortest Vector Problem (uSVP-γ)
  • 問題

CVP: Closest Vector Problem

LWE: Learning with Errors

LLLが使える問題

多変数1次方程式を解く

  • 特に解に制約が無い場合、LLLを使えば何かしらの整数解が出てくるので、それを答えとして採用できる
    • a[1] * x[1] + a[2] * x[2] + ... + a[n] * x[n] = yで、x[i]とyが不明みたいな問題が解けるが、LLLでよく出てくる、パラメタに対して答えが結構小さいことが前提としてないと厳しいそうなので注意
      • TCP1P CTF 2024 - TCP51Primeだとa51のように51乗されていたので、既知のパラメタは3225bitだったが、求めたい答えは64bitとかになっていた
  • 結構時間がかかる？
    • a[1] x[1] + a[2] x[2] = yで停止するまで2分とかかかった。気長に待つ
  • "十分に小さい"
    • 全体が512bitsのとき、7個が128bits, 1個が256bitsが変数であれば解けた SECCON 2022 Qual - insufficient
    • 「不明変数のビット数 < mod pのpのビット数」である方が良い？分からん
  • メモ
    • x[1] + x[2] + ... + a[n] * x[n] = yみたいな感じで、係数が1の変数が複数（x[1]とx[2]みたいな）あると、求まった値が不定になる。値をどう分配するかみたいな感じになって、x[1]+x[2]は固定だけど、x[1]+δ, x[2]-δでどうとってもいいみたいな状態になる
    • bit感覚
      • SECCON CTF 2020 sharsable e1 * d1 + e2 * d2 = 1 mod phi e1 * d1 + e2 * d2 = 1 + k(n - p - q + 1) この時、e1, e2はnと同じbitで、d1,d2は163bitsだったとする このとき、(n - p - q + 1)はnと同じbitなので、kは等式であるため、163bitsくらいであると見積もれる。
    • 二次元とかであっても、その部分のbit長が大丈夫ならば1変数として変換してやれば1次方程式になる
  • 特殊なLLLを使ってbytes_to_int(m) mod pが分かっているときにbytes列mを復元する
    • https://adib.au/2023/onelinecrypto/
    • bytes列mは印字可能文字で構成されているときに使えるテク。一意には定まらず、複数候補が出てくるので目grepして選別する
  • 資料
  • 問題
  • 資料 https://www.math.fsu.edu/~hoeij/spring2018/compalg/LLL.pdf

連立方程式を解くとき / Inequality Solving with CVP

ナップサック問題 / Merkle-Hellmanナップサック暗号の解読

  • Merkle-Hellmanナップサック暗号
  • 低密度攻撃
    • 密度 = 平文のビット数/暗号文の平均ビット数、平文空間と暗号文空間の大きさの違い。密度 d = n/(log2 max a[i])
    • 密度が小さい場合、部分和問題を（近似）最短ベクトル問題として解読可能
      • LO法：d < 0.64 のナップサック暗号を解読
      • CLOS法：LO法で解読できる密度を d < 0.94 まで改良
  • 高密度攻撃
    • 密度が1を超える場合。この場合は、平文空間 > 暗号文空間であり、1つの暗号文を生成する平文が複数存在し、つまり、一意に平文を復元できない

LO法

  • 改善策
    • 右端の列の各要素にsqrt(n)よりも大きな値をかける → 最後の項の非零を全体のノルムに対して支配的に影響させることで、最後の項を必ず0にしようとする
    • 全てのxの値を1-xになるようにする -> もし答えに1が多い場合、0と1が反転することでベクトルが小さくなり、正答が出やすくなるかも
  • 密度
    • 全てのナップサック問題が解けるわけではなく、入力の要素数n、要素のビット幅をbとしてn/bが0.645...未満のほとんどすべての問題が解ける

CLOS法

  • 最小化したい答えを0,1で出すのではなく、-1/2、1/2で出すように変更したもの
    • 元々の方程式を考えると答えの最後の列よりx[n+1]=-1となるため、他の列の部分はx[i]-1/2が入っていることになる
    • つまり、答えは0,1ではなく、0ならば-1/2、1ならば1/2が入ることになり、よりノルムを最小化することができる
      • 単純に考えると0,1だとノルムが1で、-1/2,1/2だとノルムが1/2になるので半分になる
  • これで密度0.9408...まで解ける

実際やってみると、x[1] + x[n+1]/2くらいの傾斜じゃうまくいかなかったので、もっと傾きを大きくするとうまくいった。

Hidden Number Problem

AGCD: Approximate Greatest Common Divisors

Hidden Subset Sum Problem

  • h=xA でxがGF(p)nであり、Aがn×m行列で値は0か1であり、h,pが与えられているときに行列Aを復元する問題
  • 解き方
    • Nguyen-Stern algorithmで解ける
      • Orthogonal Lattice Attackという格子基底簡約が出てくる
    • FastICAと呼ばれる独立主成分分析の手法でも解ける
  • 問題

他、解ける問題

  • Coppersmith's Attack 小さい解をもつ合同方程式の解法
  • truncated LCGs
  • RSA with small public exponent
  • RSA with small private exponent
  • (EC)DSA with bad nonces

格子暗号

  • 格子暗号: 格子問題の困難性を安全の根拠とする暗号方式。実際に方式を構成するときはLWE問題などを利用
    • SVP/CVPベース
      • GGH暗号（1997）: CVPの困難性に依存
      • NTRU: SVPの困難性に関連（やや複雑）
    • LWEベース: 今はこっちが主流で、NIST PQC標準候補の多くがLWEベース（Kyber, Dilithiumなど）
      • Regev暗号（2005）: LWE問題に基づく
      • 多くの現代的な格子暗号: LWEやその変種（Ring-LWE, Module-LWEなど）
      • FHE（完全準同型暗号）の多くもLWEベース
  • 様々な格子暗号
    • 公開鍵暗号
      • Regev暗号
        • LWE問題を安全性の根拠とする（ちなみに、LWE問題は格子問題を安全性の根拠としている）
        • CRYSTALS-KYBER方式の（かなり大雑把な意味で）ベースとなる暗号方式
    • ディジタル署名
    • IDベース、属性ベース暗号
    • （量子）完全準同型暗号: Fully Homomorphic Encryption, FHE
      • Gentry-Sahai-Waters FHE: LWEを安全性の根拠としている。暗号文のまま、NANDが計算可能
        • Bootstrapping: 準同型演算をすると暗号文に含まれる（多分LWEにおける）ノイズが大きくなり、暗号文を正しく復号できなくなるので、暗号文内のノイズを適宜減らす必要があり、その減らす処理のこと
          • NANDの準同型演算毎にbootstrappingすることで無制限に準同型暗号できる
    • 量子性検証、量子計算検証プロトコル
      • 典型的には，LWE問題の困難性の下で構成されるclaw-free functionを用いて構成される
      • Noisy trapdoor claw-free function (NTCF)
  • 格子暗号への平文・鍵確認オラクルを用いた鍵回復攻撃とサイドチャネル攻撃・故障利用攻撃 https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2021/11/903a57de196bb2ff6b2f45e9fb460029-1.pdf
  • https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220803_01yasuda.pdf
  • 格子暗号をベースにした準同型型暗号公式
  • 概要
    • LWE: Learning With Errors
      • (A, <A,S>+e)
        • Sは秘密要素であり、線形関数を定義する
        • eは良く既知の分布を持つ、小さいエラー
        • Aは既知の要素で<A,S>は行列AとベクタSを積を意味する
      • 特徴
        • 平文係数と暗号文係数という2つの異なる係数の下でのモジュラー演算を使用する
        • 秘密鍵はnを法とするベクトル空間の要素
        • メッセージは、エンコードされたノイズの多いメッセージを大きなドット席に追加することによって暗号化される
    • LWEを暗号化に活用する場合はエラー部分に埋め込む
      • (A,<A,S>+encoded(m,e))のようにする
      • Aはランダムな要素を持つベクトル空間で、それを秘密鍵のSと積を取って、メッセージを埋め込んだエラーと和を取る
      • Aは共有されるので（多分）、秘密鍵Sが分かっていれば、<A,S>を引いてエンコードされた平文とエラーが得られる
      • 特殊なエンコード方式によってエラーのみ削除することができるので平文のみ取得することができる
    • 方式は2つある
      • high-bitsに平文を埋め込む方式: Regev09, BFV
      • low-bitsに平文を埋め込む方式: BGV
  • 資料

NTRU, SVPをベースとした耐量子暗号

Regev暗号, LWEをベースとした暗号

  • LWE High Bits Message: こっちの方が復号がより安定し、より一般的
    • パラメタ（共有）
      • ベクトル空間の次元: n
      • 暗号文の剰余: q
      • 平文の剰余: p (平文m < pである場合に暗号化可能。RSAと同じ感じね)
      • scaling factor: Δ=round(q/p)
    • 鍵生成
      • 秘密鍵Sをqを法とした有限体の上でn元のベクトルとして作成
    • 暗号化
      1. qを法とした有限体の上でAを生成する
      2. エラーeを[-Δ/2,Δ/2]の範囲の整数として生成する
        • 離散ガウス分布上でサンプリングするのが一般的だが、一様分布でもいいらしい
      3. b = <A,S>+Δ*m+eを計算する
        • Δ*m+eがencoded部分で、パラメタを良い感じにやらないとちゃんと復元できなかったりするらしい。Δ⋅m+e<q/2である必要がある
      4. (A,b)が公開鍵
    • 復号化
      1. x = b - <A,S> mod qを計算し、xを得る（qを法として計算しているが計算後のxではmod qは無視する）
      2. m = round(x/Δ)でメッセージを取得
  • LWE Low Bits Message
    • パラメタ（共有）
      • ベクトル空間の次元: n
      • 暗号文の剰余: q
      • 平文の剰余: p (平文m < pである場合に暗号化可能)
      • p,qは互いに素
    • 鍵生成
      • 秘密鍵Sをqを法とした有限体の上でn元のベクトルとして作成
    • 暗号化
      1. qを法とした有限体の上でAを生成する
      2. エラーeを[-(q/p)/2,(q/p)/2]の範囲の整数として生成する
        • 離散ガウス分布上でサンプリングするのが一般的だが、一様分布でもいいらしい
      3. b = <A,S>+m+p*eを計算する
      4. (A,b)が公開鍵
    • 復号化
      1. x = b - <A,S>を"centered modulo qで"計算し、xを得る
        • 通常の[0,q)ではなく(−q/2,q/2]でmodを取る
      2. m = x mod pでメッセージを取得
        • m+p⋅e<q/2でないと復元できない

CTFのCryptoにおける符号まとめ [エンコーディング, CRC, リード・ソロモン]

Security

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

符号化

CRC: 巡回冗長検査

RS符号: リード・ソロモン符号

  • 符号理論における誤り訂正符号の一種
    • 情報伝達のエラーを数学的に訂正する仕組み
    • 応用例 https://www.youtube.com/watch?v=q-j1sn0PkRs
      • 衛星通信、地デジ、ADSLなどノイズの多い通信
      • QRコードに絵を重ねても読んでくれる
      • CDやDVDの表面に小さなゴミがついていても再生できる
  • アルゴリズム
    1. 送信者がメッセージmと生成行列Gを用意する
      • 生成行列は有限体上の原始元 a を用意して、メッセージの長さ k を決定し、符号語n個を作るとすると以下のようになる | a0 a0 ... a0 | | a0 a1 ... an-1 | G=| a0 a2 ... a2(n-1) | | ... | | a0 ak-1 ... ak-1(n-1) |
      • t=(N-K)/2としたとき、RS符号はt個までのシンボルの誤りを訂正することができる
    2. 送信する符号語 w = mG を作り、送信する
    3. 送信時にエラーが発生して、w + eになる
    4. 受信者が検査行列 H を使い、エラーを特定する。 シンドローム wHを計算して全て0になればエラーが無い
      • 検査行列 H は以下のように構成する | a0 a0 ... a0 | | a1 a2 ... an-k | H=| a2 a4 ... a2(n-k) | | ... | | an-1 a2(n-1) ... an-1(n-k) |
      • シンドローム wH が0でない場合は出てきた値を元にエラーを特定していく
        • ピーターソン法でエラーを特定可能
          • シンドローム行列を使うことでエラーがある場所が特定できる
          • (w + e) Hを計算しているので、wH + eHのように分解でき、また、wHは全要素0のベクトルになるため、0でないシンドロームの値はeHを指すことになる
          • よって後は吐き出し法をするなり、頑張ってeのベクトルが特定可能
    5. w+eからeを除去して、wが手に入ったら、w*G^-1をしてmを復元可能
  • https://www.youtube.com/watch?v=ZznDYmZY9e8 をまず見るとよさそう
  • https://blog.tanglee.top/2024/08/09/Reed-Solomon-code-in-McEliece-and-Niederreiter.html
  • https://blog.kroma.network/brain-fri-ed-diving-into-the-fri-protocol-and-more-85e979ee39fc
    • リードソロモンは多項式に変換していて、多項式からの逸脱を検知することで誤り訂正をする？
  • 短縮リード・ソロモン符号

符号暗号

  • Lumos Anthology Vol.1にあるmitsuさんの「HQCを実装しよう！」https://techbookfest.org/product/5hTLJywX6DXYRFJUTiEgNP?productVariantID=ryNiCXDm6MzM1uALSe2Vq が多分最強（まだ読んでないけれど、mitsuさんなので）
  • SD問題: Syndrome Decoding問題
    • 符号暗号の安全性の根拠となっている問題
    • 係数、定数項および解が0と1のみで構成される多元連立1次方程式で、解における1の個数は問題ごとに与えられている定数以下である必要がある
  • McEliece暗号 https://www.youtube.com/watch?v=ZznDYmZY9e8
    • 線形符号でのいい感じの行列をG^ = S[G|R]Pとして定めたもの
      • 送信時はcG^+eを送る。cGe=wとすると、線形符号と同じ状況。渡すのはcG^+eとS,Pの3つ
      • Sは完全ランダムな正則行列
      • Gは以下のようなk×nの行列（aはGF(p)で添え字が異なるものは互いに異なる） |1 1 .... 1 | |a1 a2 .... an | |a1^2 a2^2 | |... | |a1^k-1 a2^k-1 ... |
      • [G|R]PはGにランダムな値を持つ列ベクトルをランダムな位置に差し込んだもの
        • Rがランダムな値を持つ列ベクトルでPは列をランダムにシャッフルする行列
    • mceliece348864
      • m = 12 (体の拡大次数)
      • n = 3488 (符号長)
      • t = 64 (通常のエラー訂正能力)
      • k = n - m×t = 3488 - 12×64 = 2720 (情報ビット数)
    • エラー重みが小さい場合は脆弱っぽい OMEGA = 4（通常のt=64より大幅に小さい！）
  • 符号暗号: 誤り訂正符号に基づく暗号化
  • 資料

CTFのCryptoにおける高機能暗号まとめ [秘密分散, ゼロ知識証明, ZKP, 準同型暗号]

Security

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

高機能暗号

  • 高機能暗号: 暗号化・復号化以上のことができる暗号方式の総称
    • 秘密計算: ある暗号文から別の暗号文が作成可能であり、暗号化された平文に対する演算を暗号文のまま行える
      • 準同型暗号
    • ゼロ知識証明
    • 秘密分散
    • グループ証明
      • ユースケース: プライバシー観点から、ある権限を所有しているｋとおのみを証明できれば十分な時に使える
    • IDベース暗号
      • PKIを使った鍵運用はコストが高いので、個人の公開性の高い識別子ID（メールアドレスやユーザー名）を利用した公開鍵暗号方式
      • 楕円曲線上のペアリングが使えるらしい
      • Boneh-Franklin IDベース暗号
    • 検索可能暗号
      • NICTによるESKS(:Encrypted System with Keyword Search)
    • 低遅延暗号、ハイスループット暗号: 高速なリアルタイム通信の世界で暗号処理がボトルネックにならないように
    • 視覚的・物理的暗号技術: 産総研を中心とした研究グループが開発しているもので、視覚的に物理的に高機能暗号を示すことでアルゴリズムの「分かりやすさ」を知ってもらうための暗号（つまり、実用性を求めたものではない?）
      • カードベース暗号
    • IETF(:Internet Engineering Task Force)でも高機能暗号の標準化について議論がなされている
      • Crypto Forum, Privacy Pass WG, Privacy Preserving Measurement WGなど
    • 秘匿検索: 検索クエリは隠したまま、検索結果のみを得る
  • TEE: CPUの標準機能を使用して作成されたセキュア領域で安全に処理する仕組み
  • EAGLYSさんのQiitaに日本語解説が大量にあって助かる

秘密計算

  • 秘密計算: Secure Computation、各自の入力データは秘密にしたまま、必要な情報のみを得る技術
    • 秘密分散方式、秘密分散＋MPCベース
    • 準同型暗号方式、完全準同型暗号ベース
      • 加法準同型暗号 Enc(m) + Enc(n) = Enc(m + n)
      • 乗法準同型暗号 Enc(m) * Enc(n) = Enc(m * n)
      • 完全準同型暗号: 加法かつ乗法準同型暗号、かつ、この加法と乗法を任意の回数実行可能
  • マルチパーティ復号 / MPC: マルチパーティ計算
    • fのMPCプロトコル: n人の参加者（パーティ）P0, P1, ..., Pn-1がそれぞれ秘密情報xiを持ち、その情報の他のパーティに秘匿しながら全員で強調計算を行いf(x0, x1, ..., xn-1)を計算すること
    • 秘密計算の暗号学的なモデルのうち、一般的なもの
    • MPCにおける安全性
      • 正当性：パーティがプロトコルに正しく従った際には結果が正しく出力される
      • 秘匿性：条件Xの元で（攻撃者のシナリオらしい）攻撃者が攻撃を行った際に、プロトコルの実行によって、攻撃者でないパーティの情報が関数の出力を超えて漏れない
    • 攻撃者のシナリオについて
      • 計算能力観点：計算量的な攻撃者と情報理論歴な攻撃者に大別され、秘匿性を評価できる
        • 計算量的安全性：計算に凄い時間がかかることを前提とした安全性
        • 情報理論的安全性：無限の計算能力を持っていると仮定しても、攻撃者が得られる情報と秘密情報の確率的独立性（つまり、1/2で正解だし、1/2で不正解的なことだと思う）をもって安全性を保証できる。無条件安全性とも呼ばれる
      • 攻撃者の振る舞い：受動的な攻撃者、能動的な攻撃者
      • 攻撃者の人数：正直者多数、不正者多数
        • 正直者多数であれば、任意の関数fを情報理論的安全に構築可能であることが証明されている
        • 逆に、不正者多数だと、ある関数fは情報理論的安全に構築できない（こっちは「ある」であることに注意。一部は作れる）
    • MPCプロトコルの評価軸
      • 通信量：必要なデータ通信量
      • ラウンド数：必要な通信の回数。MPCでは「各パーティでのローカルでの計算→パーティ間の通信」の1ステップを何ラウンドか行う
      • 計算量：必要なローカルでの計算量
  • ブラインド署名 / 部分ブラインド署名

秘匿共通集合計算 PSI : Private Set Intersection

  • あるデータの2つの集合に対して、お互いに何を持っているのか秘密にしたまま共通する要素を特定する
  • ブラインド署名によって実現するアルゴリズムがある

https://qiita.com/SenK/items/a4b6191e44d2226844ec

紛失通信: Oblivious Transfer

https://qiita.com/SenK/items/f8249193d335e78d3333 https://hackmd.io/@theoldmoon0602/BJ3qRgRz_

  • OT: Oblivious Transfer, 紛失通信
    • 送信者が送信したデータのうち、受信者がどれを受信したのか、送信者が知ることができない
  • Rabin-OT
    • ラビン暗号を使い、紛失通信路をシミュレートするもので、1/2の確率で相手にメッセージが届き、残りの1/2の確率でメッセージが一切届かない
  • 1-out of-2 OT
    • 送信者が2つのメッセージを送信し、受信者はその片方のみを受信できる。送信者は、受信者がどちらのメッセージを受信したか分からないタイプのOT
    • これを拡張することでn個のメッセージのうちk個を受信するk-out of-n OTが構成できる
  • GC: Garbled Circuit

カードベース暗号

  • カードベース暗号: トランプカードのような物理的なカード組を使って秘密計算する
    • コミットメント: とある1bitの変数xを♣と♡のカードの組で表現したときこの2枚をxのコミットメントと呼ぶ
      • ♣♡ -> 0, ♡♣ -> 1
    • 形式的に表現する際の操作
      • turn i: i番目のカードをひっくり返す
      • perm (a1, a2,...): 与えられた巡回行列に従ってカードを入れ替える
        • ランダムカット: 1列に並んだカードを巡回的にシャッフルする。perm (1 2 3 ... n)
      • shuf {a, b, ..}: 与えられた巡回行列のいずれかをランダムに選択してカードを入れ替える
  • ファイブカードトリック: ANDの秘密計算
    1. 秘密にしたい入力a,bのコミットメントを裏にして2組用意して♡で挟んだa♡b、つまり??♡??を用意する
    2. 左側のコミットメントを逆にする
    3. 中央の♡を裏返す?????になる
    4. ランダムカットする
    5. 全部のカードを表にしたときに、3枚の♡が巡回的に並んでいれば結果はa and b=1であり、それ以外はa and b=0である
  • コミット型プロトコル: カードベース暗号による計算の結果がコミットメントとして得られる
    • つまり、and(a,b) = cのようにaとbのコミットメントを与えると、cのコミットメントが得られる。これにより出力されたコミットメントをまた次の計算の引数に使うことができ、コミットメントをIFとした連鎖的な計算が行える
    • コミット型ANDプロトコル
    • コミット型XORプロトコル
    • コピープロトコル: とあるコミットメントxを2つに複製可能
    • コミット型NOTプロトコル
    • コミット型ORプロトコル
  • 金持ち比べプロトコル（大小比較を秘密計算する）
    • （カードベース暗号ではないが）Yaoの金持ち比べ
    • カードベースの金持ち比べ
  • 考察
    • カードベース暗号ってどのくらい実用的なんだろう。数式を使わない（計算機がいらず、物理的に計算可能）という点で有意性はありそうだが、bit数に対して必要なカードが多そうで物理的なカードを使った実用性はあまりなさそうで、これをモデルとして計算機でやらせるとうまくいくということがある？
  • 参考

準同型暗号

  • https://nindanaoto.github.io/
  • スキームの核
    • 鍵生成
    • 暗号化
    • 評価: 暗号文に対する直接計算（暗号文のまま計算）
    • 復号
  • スキーム
    • PHE: 部分準同型暗号。足し算か掛け算のどちらかをサポート
      • 乗法準同型暗号: RSA、ElGamal
      • 加法準同型暗号: Paillier暗号、岡本・内山暗号
    • SHE: サムホワット型準同型暗号。加法ができ、乗法のみ演算回数に制限がある
      • 例：Boneh–Goh–Nissim暗号、格子暗号の一部
    • Leveled FHE: Leveled完全準同型暗号。鍵生成時に決定される一定数のオペレーションをサポート
    • FHE: 完全準同型暗号。無制限の加算と乗算をサポート
      • 秘匿マルチパーティ計算（SMPC）を促進
      • 例：Gentryによる格子暗号ベースの完全準同型暗号
  • TenSEAL: 準同型のまま計算するライブラリ

FHE: Fully Homomorphic Encryption 完全準同型暗号

  • FHE: Fully Homomorphic Encryption 完全準同型暗号
    • 暗号化されたまま無劣化で（つまり何度も）計算が可能
    • FHEは、暗号に基づく暗号と多項式演算の数学的原理に基づく
  • 「ノイズ」暗号化されたメッセージに意図的に導入されたランダムな要素
    • ノイズにより、セキュリティが保証される
    • ノイズは暗号化された値に対して計算が行われるたびに増加（加算よりも乗算の方が顕著）し、ノイズが大きくなりすぎると、平文を破損してしまう
    • ブートストラッピング: 暗号文のノイズを大幅に低減することで、FHEにおいて無限に計算できるようにするもの
      • 種類: ゲートブートストラップ、ファンクショナルブートストラップ、プログラマブルブートストラップ

  • FHEスキーム

    • 多項式の環を使う方式: RLWE: Ring Learning With Errors。R=Z[x]/(xn+1)を使う。主流
      • 現代の実装（SEAL, HElib, PALISADE など）は、ほぼ全てRLWE系を使っています
      • R=Z[x]/(xn-1)というのは、xn=-1とすることで、多項式を折り返した多項式の環のこと
      • BGV/BFV: 正確な算術演算に適した、高精度な方式
        • BFV: 整数用のFHE方式。多項式の次数、平文の法、暗号文の法を暗号化パラメタとして持つ
      • CKKS: 近似演算に最適化
        • CKKSノイズ（暗号演算に含まれる微小な丸め誤差）
        • m0leCon CTF 2026 Teaser - One More Bit
          • CKKSノイズの影響を統計的に見ることでサイドチャネル的に平文の情報が漏えいする。
    • LWE系が別であるらしい
    • 整数ベース, 初期のGentryのFHE。イデアル格子を使う。非常に遅いので使わない。
    • TFHE: Boolean circuitや小さなデータ項目に対するルックアップテーブルとして表現可能な関数に対して効率的

  • 資料

TFHE

https://qiita.com/dkawabe/items/06195c94c434106f8cc5

  • TFHE: Torus上のFHE(完全準同型暗号)
  • Torus: 0以上1未満の実数の集合、ただし、整数部分は無視する（1の加法減法は無視する）
    • 厳密には、実数体を整数環で割った商加群らしい
    • 0.1 = 1.1 = 2.1 = ... みたいな感じ
    • 0.3 + 0.8 = 1.1 = 0.1 みたいな感じ
    • 加法・減法は作れるが、乗法除法は定義できない
  • TFHEでは、f: T -> T を任意の一次関数として変換する暗号

秘密分散

https://qiita.com/SenK/items/33ce4cbf2fee23df95ec https://www.jstage.jst.go.jp/article/isciesci/63/2/63_71/_pdf

SSS: シャミアのしきい値法, Shamir's Secret Sharing

秘密分散ベースのMPC

  • BGW方式: Shamirの秘密分散に基づくMPC
    • 正確には線形秘密分散であるShamirの秘密分散に対して乗算を実現する方式
    • また、BGW方式を簡略化したGRR方式もあり、現在においてはBGW-typeと呼ばれる方式はGRRを指すことが多い
    • あまりちゃんと読めていないが、Bootstrapping（特定の復号回路を準同型演算でシミュレートするｋとおで、別の鍵の暗号文に乗り換える）というテクを使うらしい
  • 複製型秘密分散に基づく方法
    • 3パーティでしか使えないっぽい？
  • Beaver Tripleに基づく方法
    • multiplication tripleと呼ばれる事前計算されたデータを用いるほうほう
    • SPDZフレームワークを用いる方法: 加法型秘密分散に基づくMalicious安全な秘密計算手法で、準同型暗号を用いてmultiplication tripleを事前計算する
    • 補助クライアントを用いる方法: クライアントが秘密情報をn台のサーバに秘密分散して入力し、結果のシェアだけを受け取り、クライアント上で結果を復元する？

ゼロ知識証明 ZKP: Zero-Knowledge Proof

zk-SNARK, zk-STARK

  • STARK: Scalable Transparent ARguments-of-Knowledge, 以下を満たすような証明システム
    • Scalable: 証明時間がほぼ線形で、検証時間が対数の多項式時間
    • Transparet: トラステッドセットアップが存在しない（シークレットや認証局のようなtrust anchorなどが不要）
    • Arguments of Knowledge, Lean Cryptography?: 証明者の能力が確率的多項式時間チューリングマシンで実行可能
      • 安全な暗号と衝突体制のあるハッシュ関数の存在という、最小限の暗号的仮定のもと動く
        • ここに量子耐性が求められる？
    • STARKが多くのSNARK実装と比べて優れている点として、ハッシュ関数の存在以外には暗号学的な仮定を必要としないという点がある。
    • arithmetization 算術化
      • STARKプロトコルの最初のステップで、計算の検証の問題を「多項式が低次であることを確認する問題」に変換する。縮約とも言う
      • 更に2つの要素に分かれる
        • 実行トレース: 検証するのに必要な計算過程のこと
        • 多項式制約: 実行トレースが満たすべき制約を方程式の形で書き下したもの
        • つまり、実行トレース全てが多項式制約にのっとっていることを確認することで検証を行う
      • ちなみに実行トレースが複数の列になる場合は多項式制約が増えることになるが、その場合も最終的には単一の多項式に集約して、低次チェックを行うことになる
  • 分かりやすい資料

FRIプロトコル

  • FRI(Fast Reed-Solomon IOP)プロトコル、低次テスト（多項式が指定された次数以下であることを証明する）のための効率的な暗号学的プロトコル
    • 証明者: 多項式f(x)の次数がd以下である多項式を所有していることを証明したい
    • 検証者: 多項式が分からない状態で、証明者に点の値を要求することで、d以下の多項式を持っていることを証明したい
  • naiveな方法（FRIプロトコルではない）
    • 行えるクエリを「検証者が証明者にランダムな点を要求する」と定義する
    • クエリをd+2回行い、それを元に（多分ラグランジュ補間とかで）多項式を復元したときに、d次以下の多項式があるかを確認する
      • d+1次のものがあれば、d以下を満たさない
    • この方法だとクエリ複雑性はd+2
    • クエリの方法を工夫して、より効率的な方法はないだろうか
  • FRIプロトコル
    • クエリの方法をd+2からlog(d)程度に減らすために、分割統治法とクエリの工夫を行う
      • 分割統治法 -> 1つの多項式の次数がd以下である証明 → 2つの多項式の次数がd/2以下である証明 に変換
      • クエリの工夫 -> 複数の多項式の次数チェックを1度に行えるようにする。証明者支援型で低次テストするタイプ
  • 分割統治法: d未満の次数を持つ1つの多項式を、d/2未満の次数を持つ2つの多項式に変換する
    • f(x)をd未満の字図うの多項式として、dを偶数とする（奇数でもいい感じにできるっぽい）
    • f(x)=g(x2)+x・h(x2)と分割する。g(x)はf(x)の偶数係数から得られる多項式で、h(x)は奇数係数から得られる多項式
      • 具体的にはf(x)=a + bx + cx2 + dx3 + ex4 + fx5であれば以下のように分割する
        • g(x) = a + cx + ex2
        • h(x) = b + dx + fx2
  • クエリの工夫: 2つの多項式f,gがあり、両方の次数がd未満であることをテストする
    1. 検証者 -> 証明者: 体からランダムな値αを取って送る
    2. 証明者: クエリ処理の際に、h(x)=f(x)+αg(x)を結果として返すことにする（ここでMerkle木が出てくるらしい）
    3. このクエリを使って、h(x)の次数がd未満であると判定できれば、f(x)もg(x)も次数はd未満
      • 2つの多項式を足すと結果の次数は2つのうち大きいものになるので直感的には正しそう
      • αでかけて足すことで次数が最も高いxnの係数が足してゼロになる可能性があるが、これは体が十分に大きい場合は確率的に無視できるほど小さくできる
      • 他にも観点があるが、確率的には小さくできて実用上は問題無さそう
      • また、悪意ある証明者の考察もされているが、サンプル数を増やすことで見破れるらしい
  • 参考

PLONKプロトコル

Fiat-Shamir変換 フィアット・シャミール変換

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

Security

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

乱数全般

  • PRNG: 疑似乱数ジェネレータ
  • HRNG: ハードウェア乱数ジェネレータ。物理プロセス（電子ノイズ、放射性崩壊、熱ノイズなど）を利用して真の乱数を生成できる専用チップを使用する
  • 色々な性質
    • 無作為性、ランダム性: 統計的偏りがない
    • 予測不可能性: 数値の次の発生は過去のシーケンスから推測不可
    • 非再現性: 例えばシードから同じシーケンスを再現できたりしない
  • カテゴリ
    • 弱い疑似乱数 = ランダム性
    • 強い疑似乱数 = ランダム性 and 予測不可能性
      • 暗号ではこれを使う
    • 真の乱数 = ランダム性 and 予測不可能性 and 非再現性
  • PRNGの種類
  • CPRNG: 暗号学的に安全な疑似乱数ジェネレータ
    • 統計的ランダム性テスト: 特定のシーケンスにおいて、次のビットを50%を超える確率で予測できないことをテスト
    • 十分に強力な攻撃に耐えられる必要がある。生成済みのシーケンスから次の乱数が推測できないか
  • CPRNGの設計カテゴリ
  • CSPRNG: 暗号論的擬似乱数列生成器
  • Intel CPUのrdseed, rdrand命令
    • Ivy Bridge以降のIntel CPUにはrdrandという命令が追加され、CPU内部の不確かな電子状態を使うことで乱数列を生成する
      • std::random_deviceはこれをそのまま使っている
    • だが/dev/urandomはこの命令だけに依存するような作り方をしていない。仮にrdrandが疑似乱数であった場合（つまり、バックドアがあった場合）に判断が付かないためである
  • /dev/urandom Linuxで乱数が欲しくなったらとりあえずこれを使っておけばいい
  • 乱数ジェネレータのベンチマークツール dieharder
  • 探索空間が小さい secrets.randbits(17)は全探索可能
  • 数学的な（統計的な？）法則
  • 用語
    • TRNG: 真性乱数生成器
      • 熱雑音や放射性崩壊といった予測不可能な物理現象を利用して乱数を生成
      • RSAやECCなどのアルゴリズムの鍵生成など、機密性の高い暗号処理によく使用されます
      • TRNGは専用のハードウェアを必要とし、他のRNGよりも速度が遅いがち
    • PRNG: 擬似乱数生成器
      • 統計PRNG: 統計的ランダム性テストに合格する数値を生成するように設計。これはランダム性は求められるが、セキュリティは最重要ではない
      • 暗号的に安全なPRNG（CSPRNG）: ランダム性が予測不可能で攻撃に対する耐性が求められる暗号用途向けに設計されたPRNG
    • エントロピー: ランダム性または予測不可能性の大きさを表す
      • 乱数を作るときはエントロピーを考えましょう Black Hat 2010 / Defcon 18
        • セッションIDに十分なエントロピーがあるように思われて、実は条件を絞っていくと組合せがどんどん減っていき、最終的には20bitsくらいのエントロピーにまで落ちる。そこまで落ちると、候補が106通りくらいになるから、全探索しても当たってしまうという話
    • seeding: シードと呼ばれる初期値を安全な暗号関数に与え、ランダムに見える数値列を生成する。シードが同じであれば、常に同じ列を生成する
  • ランダムの和

LCG, 線形合同法

QCG: Quadratic Congruential Generator, 二次関数合同法？

FSR: フィードバックシフトレジスタ

  • 初期状態 a0, a1, ..., an-1のn個の数列を用意
  • フィードバック関数 f(ax, ax+1, ..., ax+n-1) を用意
  • フィードバック関数を使って、ax, ax+1, ..., ax+n-1からax+nを作成して、状態をax+1, ax+2, ..., ax+nに遷移させて乱数を生成していく
  • 出力される乱数
    • a0, a1, a2, ... のように乱数が出力されていく場合もあるし
    • x0 = sum_{i=0..N-1} ci*ai みたいにある種の式を使って決定される場合もある

LFSR

  • LFSRの流れ
    1. 初期状態Rと、フィードバック関数maskがある
    2. R&maskをして1各桁の総和(xor和)を取ったものを次の乱数シーケンスの出力rとする
    3. 状態をR'=R<<1 + rで更新
    4. 2-3を繰り返す
    5. 大体maskと乱数列が与えられるのでRを求める問題が出る
  • 連続するn個の出力が得られれば特定状態を再現できるので、そこから逆行列を用いて初期状態を特定する
    • これはR'の下位1ビットと乱数シーケンスの出力rが一致することから内部状態が漏洩することになるため
    • 32bitsのLFSRであれば、連続する32bitsが分かれば、その1つ前の1bitsの状態のみが変数となる方程式が得られて計算できる
      • r = mask[0]*R[0] + mask[1]*R[1] + ... + mask[31]*R[31]でrとmask全部とRの0～30が既知なのでR[31]が計算できるということ
  • 連続してなくてもサンプルが取れれば、z3である程度解けるっぽい？
  • フィードバック関数が線形であるということは行列計算に帰着させることが可能になる
    • LFSRはGF(2n)上で線形。積は普通に積で、和はxorにしたもの
    • 繰り返し二乗法も行けるし、逆行列による計算も可能
  • 20220522_LFSRの超難問を解く - Google スライド
    • LFSRへの攻撃手法まとめ。
    • これを理解できればゴールした感ある
  • Berlekamp-Masseyアルゴリズム
    • 与えられた2進出力シーケンスに対して最短のLFSRを求めるアルゴリズム
    • N次のLFSR多項式を復元するには少なくとも2Nビットの出力が必要
      • 2N～4Nくらいあると安心？
    • BCHのデコードの一部としても使われている
  • LFSRは線形で逆算可能なので非線形要素を取り入れようという考えがある
  • sagemathでLFSRの計算をするときはBooleanPolynomialRingが使える
    • PR = BooleanPolynomialRing(names = [f'x{i}' for i in range(1, 7*2+24+1)])
  • いいまとめ
  • 問題

メルセンヌツイスター, Mersenne Twister, MT, MT19937

XorShift

  • 最初にstateを定めたあと、以下の処理を1サイクルとして、次の乱数を生成していく。 state = state ^ (state << a); state = state ^ (state >> b); state = state ^ (state << b);
  • シフトパラメタa,b,cによって乱数の質が変わる。周期性が変わる。
    • 13,17,5 -> Xorshiftの論文にもあるパラメタで32ビット用。64ビットに使うには微妙らしい
    • 64ビットでは、21,35,4が良い？
    • https://www.cepstrum.co.jp/hobby/xorshift/xorshift.html
    • 17,9,18だと280が周期になって与えられている試行回数を使うと2周目に突入できて、推測できた
  • XorShiftの計算は行列計算に変換し、高速化可能
  • 派生のxoshiro256/xoshiro256+/xoshiro256++/xoshiro256**というのもある

実装