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

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

格子とLLL

• 格子とLLLがどういうものかは入門記事が沢山ある
  • y011d4さん https://blog.y011d4.com/20210102-lll-basic
  • mitsuさん LLLを理解するぞ
  • LLLでCrypto問題を解く - Project Euphoria
  • kusanoさん https://qiita.com/kusano_k/items/5509bff6e426e5043591#lll
  • DiKOさん https://hackmd.io/@dikosec/S1Tp3uN5F
  • CryptoHackのLatticesをやるのもオススメ
• 書籍なら「格子暗号解読のための数学的基礎」https://www.kindaikagaku.co.jp/math/kd0598.htm (y011d4さん紹介)
• LLL: LLL基底簡約
  • 格子 M に対し、行ベクトル a を b=aM のノルムが"いい感じに小さく"なるようにとったときの b の値を求めることができる
    • これは与えられた格子Mの基底を計算していることになる
    • より具体的には格子の中で原点を除いて原点から最も近い格子ベクトルのトップ数個を出力する。つまり、原点に近いものから出てくる
    • ノルムはユークリッドノルムでよい？（よくわからん）
  • 計算量は重めの多項式時間で、行列のサイズが 200×200 くらいまでなら動く
    • chatgptに聞くとO(n^4B2)らしい。nは格子の次元、Bは基底ベクトルのビット長
  • sagemathのlllには| x1 x2 x3 x4 | × MとなるMを食わせて、res=xMを満たす最小のresが帰ってくる。
  • 簡約パラメータ δ デルタ
    • 1/4 < δ < 1であり、1に近い方がより短いパラメタを見つけることができるが、計算に時間がかかる
  • より高速な基底簡約アルゴリズム
    • DeepLLL基底簡約
    • HKZ基底簡約
    • BKZ基底簡約 https://blog.maple3142.net/2024/09/15/alpacahack-round-3-writeups/
      • 現状最強？
      • https://www.maths.ox.ac.uk/system/files/attachments/lattice-reduction-and-attacks.pdf
      • sagemathだと.LLL()の代わりに.BKZ()するだけ
        • L.BKZ(block_size=20) ブロックサイズが指定可能。なんだこれ
  • 各行のノルムと出てくるベクトルのノルムを確認すると簡約によって解けるか分かるみたい
    • 各行のノルムが256bits以上で、出てくるベクトルのノルムが128bitsならいけそう
  • 何個の方程式を組み込めば良いのか
    • https://project-euphoria.dev/blog/29-seccon-2021/#sign-wars
      • 「この基底の体積(full-rankなので行列式と同じ)は～n個の署名で試した結果)。」あたりが分かると良いと思う。まだ分かってない
      • 全部使う必要はない。多すぎると困ることはあるかな？計算量が大きくなるくらい？
• HNF: Hermite Normal Form エルミート標準形
  • LLLする前にM = M.dense_matrix()として密行列にした方がいい感じの結果になる？
  • LLLする前にエルミート標準形に変換するメリット(from Claude)
    1. 数値的安定性: 非常に大きな値や小さな値が混在してもならされるので良い
    2. 計算効率の向上: 上三角構造にできて、色々早くなる
  • なぜエルミート標準形にしても計算結果は同じになるのか
    • HNF変換は可逆な整数行列変換であり、計算方法も同じ
    • また、格子の線形性から、格子の行列の一部分の行列に対してのみエルミート標準形にしても問題ない
  • B_HNF = B.hermite_form(include_zero_rows=False)
• テク
  • 方程式の解として誤差を許容することができる
    • LLLとしては最小のものを持って来るだけなので、LLLの計算結果の最後の列の値が0ではなく、誤差が出てくるだけ
    • Harekaze mini CTF 2020: Wilhelmina Says https://furutsuki.hatenablog.com/entry/2020/12/27/160652#Crypto-Wilhelmina-Says
      • 誤差は他の値の大きさにもよりそうだが2³⁵⁰くらいあっても大丈夫っぽい
      • 面倒な変数部分を誤差として丸めこませることで変数を減らす
  • modとは親和性が悪いので、k*modをうまく使って回避すること
  • 数が極端に小さいものは係数をかけて小さい値を強制させる
    • 例えば、xMの値が、[ [0,2^350] [0,2^512] [-1,-1] ]みたいな分布だったら、3項目が特に小さくなる必要があるため、3項目に2³⁵⁰を書けることで、バランスをとる
  • 格子変換色々
    • CakeCTF 2022 Rock Door k = (z + xr)s^-1 mod q https://blog.y011d4.com/20220904-cakectf-writeup#rock-door
      • [xr 1 l] × [[1 0 s^-1], [0 1 s^-1 z],[0 0 -1]] -> [xr 1 k]
      • [xr+z l] × [[1 s^-1],[0 -q]] -> [xr+z k]
  • "十分に小さい"
    • 全体がN bitsであるとき、未知変数がN/2 bitsくらいなら余裕
    • どれくらい小さいと大丈夫かについてはやってみるしかなさそう。だが、LLLもcoppersmithも実用上は結構うまくいくらしいので、無理そうでもやってみる姿勢が多分大事（パラメタをガチャガチャしながら）
• 記事
  • https://github.com/hyunsikjeong/LLL
  • https://github.com/hyunsikjeong/LLL/issues/2
  • https://magicfrank00.github.io/writeups/writeups/alpacahack2024/hat-trick/
    • 良くまとまっている。とても良い
    • LLLにかける前に全体を対角行列でかけてLLLして割っている。なぜ
  • https://www.cryptrec.go.jp/exreport/cryptrec-ex-2404-2014.pdf
  • https://yoshiking.hatenablog.jp/entry/2020/03/12/233320
  • https://ptr-yudai.hatenablog.com/entry/2020/03/12/223338
  • https://furutsuki.hatenablog.com/entry/2020/05/05/112207#picoCTF-2017-ECC2
  • https://www2.iisec.ac.jp/proc/vol0006/arita14.pdf
  • https://qiita.com/kenmaro/items/f2d4fb84833c308a4d29
  • https://www.cryptrec.go.jp/exreport/cryptrec-ex-2404-2014.pdf
  • https://eprint.iacr.org/2023/032.pdf これが一番まとまっていそう？
  • https://hackmd.io/@Giapppp/BJ4wfpZST
  • https://triodelzx.github.io/2025/03/31/%E6%A0%BC%E5%AF%86%E7%A0%81/

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-γ)
• 問題
  • 入門 PlaidCTF CTF 2015: Lazy https://kmyk.github.io/blog/writeups/ctf-2015-plaidctf-2015-lazy/
  • Tokyo Westerns/MMA CTF 2016 Backpacker's cipher easy mode, extra mode

CVP: Closest Vector Problem

• とある点が与えられたときに、格子が構成する点の集合の中で最も近い点を求める問題
  • 格子を作るときに一次独立になっている（つまり、倍数が一致しない）必要がある
• Babaiの最近平面アルゴリズム: CVPを近似的に効率的に解くアルゴリズム
  • LLLで得られた簡約基底を使って、CVPを近似的に解いている
• 埋め込み法: CVPの別解法
  • 埋め込み法(embedded technique)と呼ばれる形のSVPを解くことでCVPを解いています https://furutsuki.hatenablog.com/entry/2021/03/21/101039
• LLLで連立方程式を機械的に解くフレームワーク https://crypto-writeup-public.hatenablog.com/entry/Inequality_Solving_with_CVP
• c=m^TB+r でcとBが既知で、十分に小さいrが未知のときmを求めたい
  • B = matrix(ZZ, B)とc = vector(ZZ, c)で用意
  • C = Babai_CVP(B, c) CVPしてcに最近の格子の点を持って来る。これがm^TBになっている。Babai_CVPはhttps://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage
  • m = B.solve_left(C)でC=m^TBからmを持って来る
• CVPの方がSVPより難しい問題らしい
• CVP
  • CVP - CTF Wiki EN
  • Merry CryptoMath !!!!! - みつみつみつですか？
  • CakeCTF 2021 Writeup | y011d4.log
• 問題
  • CakeCTF 2021 Matrix Cipher https://blog.y011d4.com/20210829-cakectf-writeup#matrix-cipher
  • Harekaze mini CTF 2020: Wilhelmina Says https://furutsuki.hatenablog.com/entry/2020/12/27/160652#Crypto-Wilhelmina-Says
  • https://github.com/rkm0959/Inequality_Solving_with_CVP?tab=readme-ov-file
    • PBCTF 2020 LeaK
    • N1CTF easyRSA
    • HITCON CTF 2019 Quals - not so hard RSA
    • AeroCTF 2021 - horcrux
    • GoogleCTF 2021 - H1
    • ACSC Share The Flag
  • BCTF 2018 - guess_number https://ctf-wiki.mahaloz.re/crypto/asymmetric/lattice/cvp/#bctf-2018-guess_number
  • AeroCTF 2020 - Magic II https://hackmd.io/@hakatashi/B1OM7HFVI

LWE: Learning with Errors

• LWE: As+e=bという式があり、Aとbが既知であるときにsを求めるのが難しいという問題
  • sは秘密ベクトルで、eは小さな誤差ベクトル
• 秘密ベクトル s=(s1,s2,s3,...,sn)に関して連立線形近似方程式が与えられるので、秘密ベクトルsを求める問題
  • 連立線形近似方程式とはs=(s1,s2,s3)とすると
    • 14s1 + 4s2 + 5s3 ≈ 10 (mod 17)みたいなものの連立方程式
    • 近似は「±1以内」みたいなレベルで、近似が無いとガウスの消去法とかで解けてしまうので、誤差の大きさが問題の難しさになる
    • 一般に誤差は平均0, 標準偏差σ>0から生成された離散ガウス分布χ=D_Z,σから生成される
• LWE格子暗号：LWE問題を解く難しさを利用した格子暗号
  • 格子暗号に関するいいサイト https://cseweb.ucsd.edu/~daniele/LatticeLinks/index.html
  • 素数qを法とする有限体上での演算のもとでの格子を考える
  • 準同型暗号（暗号文のまま演算可能）、耐量子コンピュータ暗号
  • 共通パラメタ
    • n: 格子の次元、3桁以上の整数値が安全で、nの値が小さいとLWEは簡単に解けてしまう
    • q: 法とする素数、4桁程度の整数が安全。素数qの値が大きくなるほど、解候補となる格子点の数が減るらしい
    • A: 格子の基底行列 n×n
    • σ: 誤差の大きさに関連するパラメタ、1.5よりも大きな実数。この値が小さいと、秘密鍵のeが小さくなってしまい、公開鍵Tに近い格子点Gが容易に探索できる
  • 秘密鍵（LWE問題の答え）mは平文のビット数
    • s: 係数 n×m
    • e: 誤差 n×m、各成分が0,1だけにならないようにすること
  • 公開鍵（LWE問題の入力）mは平文のビット数
    • T: 格子点に誤差を加えた点 n×m
  • 攻撃方法 https://cseweb.ucsd.edu/~daniele/LatticeLinks/attacks.html
    1. Primal Lattice Attack
       • Bounded Distance DecodingかUnique Shortest Vectorの問題に帰着させる
       • https://hackmd.io/@Giapppp/BJ4wfpZST
    2. Dual Lattice
       • 決定的LWE問題を双対格子におけるSIS問題に帰着させる
    3. Combinatorial Techniques
       • BKWアルゴリズム https://hackmd.io/@Giapppp/BJ4wfpZST
• Ring-LWE格子暗号：LWE格子暗号では公開鍵の鍵長がO(n²)で大きく、暗号文の長さは平文のn倍になってしまうので、改善アルゴリズムとしてRing-LWE格子暗号がある
  • https://lazzzaro.github.io/2020/11/07/crypto-%E6%A0%BC%E5%AF%86%E7%A0%81/
• 攻撃テク
  • Arora-Ge attack
    • https://github.com/jvdsn/crypto-attacks/blob/master/attacks/lwe/arora_ge.py
    • https://people.csail.mit.edu/vinodv/6876-Fall2018/lecture2.pdf
  • Blum-Kalai-Wasserman attack
  • Lattice reduction attack
    • CVPに帰着させたり、LLLでも解ける
• 資料
  • https://inaz2.hatenablog.com/entry/2017/05/27/003343
  • https://github.com/dikosec/CTF/blob/main/tea_party/LWE%E6%9A%97%E5%8F%B7%E5%85%A5%E9%96%80.pdf
  • CTFtime.org / Hack.lu CTF 2021 / lwsr / Writeup
  • https://eprint.iacr.org/2023/777.pdf
  • https://www.maths.ox.ac.uk/system/files/attachments/lattice-reduction-and-attacks.pdf
• 問題
  • https://github.com/sh1k4ku/ctf-challenge/tree/main/0CTF2024/Signin
  • TSG CTF 2023 - Learning with Exploitation https://chocorusk.hatenablog.com/entry/2023/11/11/035738#crypto-Learning-with-Exploitation
  • https://11dimensions.moe/archives/267
  • TFC CTF 2025 - Deez Errors https://github.com/thefewchosen/tfcctf-2025-challs/blob/main/crypto/deez%20errors/deliverable/source.sage
    • eが[97491, 14061, 55776]からランダムに取った3択で全部埋まってる
    • 97491=55776+41715で14061=55776-41715なので、いい感じに変形して-1,0,+1が不明みたいな感じに帰着でき、LLLすれば解ける
  • https://triodelzx.github.io/2025/07/07/LWE/

LLLが使える問題

多変数1次方程式を解く

• 特に解に制約が無い場合、LLLを使えば何かしらの整数解が出てくるので、それを答えとして採用できる
  • a[1] * x[1] + a[2] * x[2] + ... + a[n] * x[n] = yで、x[i]とyが不明みたいな問題が解けるが、LLLでよく出てくる、パラメタに対して答えが結構小さいことが前提としてないと厳しいそうなので注意
    • TCP1P CTF 2024 - TCP51Primeだとa⁵¹のように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]-δでどうとってもいいみたいな状態になる
    • この場合は、x[1],x[2]を複数とって引き算して打ち消して、頑張るみたいなことをする https://blog.y011d4.com/20221113-seccon-ctf-writeup#insufficient
  • 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://magicfrank00.github.io/writeups/posts/lll-to-solve-linear-equations/
• 問題
  • SECCOC CTF 2022 insufficient https://blog.y011d4.com/20221113-seccon-ctf-writeup#insufficient
  • TCP1P CTF 2024 - TCP51Prime
• 資料 https://www.math.fsu.edu/~hoeij/spring2018/compalg/LLL.pdf

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

• rkm0959さんのInequality Solving with CVPを使って機械的に導出する方法がある
  • https://crypto-writeup-public.hatenablog.com/entry/Inequality_Solving_with_CVP ここを見ながら頑張る
  • https://pro.twitter.com/fwarashi/status/1863626211374874675/photo/1
  • これを使うとなぜいいかというと自動でいい感じにスケーリングをしてくれる。格子の構築は自分でやらないといけないが、機械的にやれる
  • cvp_result, applied_weights, solution = solve(mat, lb, ub)のように格子と下限と上限を与えると自動でいい感じに加えたスケール用の重み applied_weights がかけられたCVPの結果 cvp_result が返ってくる。最後のsolutionにはcvp_resultの各項 / applied_weightsの対応の項をしたものが入っているので、結果としてはsolutionのみを使えば良い
• 資料
  • rkm0959/Inequality_Solving_with_CVP: CVP "trick" for CTF challenges
  • https://imp.ress.me/blog/2022-11-13/seccon-ctf-2022/#this_is_not_lsb
  • https://github.com/project-sekai-ctf/sekaictf-2022/tree/main/crypto/ezmaze
  • https://github.com/DownUnderCTF/Challenges_2022_Public#crypto の rsa interval oracle
• 問題
  • AHR12: Flag Sharing
• 他のソルバ https://connor-mccartney.github.io/cryptography/other/idekCTF2025

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

• Merkle-Hellmanナップサック暗号
  • 一方向性関数としてナップサック問題を使った暗号 https://tex2e.github.io/blog/crypto/knapsack-cryptosystem
  • 簡単に復号可能な「トラップドア」が存在する https://www.slideshare.net/trmr105/katagaitai-workshop-7-crypto
  • LLL（CLOS法など）でも解ける
  • 問題
    • TW CTF 2nd 2016 Crypto Backpacker's cipher easy mode -> トラップドア
    • Plaid CTF 2015 Crypto Lazy -> 低密度攻撃 (LLL)
    • TW CTF 2nd 2016 Crypto Backpacker's cipher extra mode -> 高密度攻撃 (LLL)
    • srdnlenctf 2022 Give Me A Bag https://github.com/srdnlen/srdnlenctf-2022_public/tree/main/crypto_givemeabag
• 低密度攻撃
  • 密度 = 平文のビット数/暗号文の平均ビット数、平文空間と暗号文空間の大きさの違い。密度 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

• HNP: Hidden Number Problem
  • x[i] - T[i] y + A[i] = 0 mod PでありT[i], A[i]が既知であるものが複数与えられるときに、x[i],yを計算する問題
    • 求めたいx[i],yが全体に対してある程度小さい必要がある
    • 式変形するとx[i] = T[i] y - A[i]なので無知[i] = 既知[i] × 無知 - 既知[i]
  • 不明A = 既知 * 不明B + 既知みたいに変換できて、左辺が右辺の各項に対して小さいならできる
    • SECCON CTF - XXX https://blog.y011d4.com/20211212-seccon-writeup#xxx
      • 全体が2.5nビットで、不明が2nビットならいけた。やっぱり、LLLはとりあえずやってみることが大事だな
  • ECDSAのBiased Nonce Attack等に使える
• HNP-SUM: Hidden Number Problem with Small Unknown Multipliers
  • https://eprint.iacr.org/2022/914.pdf 原点
  • https://iacr.org/submit/files/slides/2023/pkc/pkc2023/136/slides.pdf
• Hidden Subset Sum Problemも一緒？ https://triodelzx.github.io/2025/08/27/%E9%9A%90%E5%AD%90%E9%9B%86%E5%92%8C%E9%97%AE%E9%A2%98-Hidden-Subset-Sum-Problem/
  • zer0pts - karen
  • https://tover.xyz/p/HSSP-note/
• EHNP: Extended Hidden Number Problem
  • https://dl.acm.org/doi/abs/10.1007/978-3-031-17433-9_25
  • https://github.com/jvdsn/crypto-attacks/blob/master/attacks/hnp/extended_hnp.py
• 連立方程式を解くのと変わりないので、Inequality Solving with CVPで解いてもいい
• HNP-2H: Hidden Number Problem with 2 Holes
  • https://triodelzx.github.io/2024/11/30/%E9%80%9A%E8%BF%87%E7%8B%84%E5%88%A9%E5%85%8B%E9%9B%B7%E8%BF%91%E4%BC%BC%E8%A7%A3%E5%86%B3HNP-2H/
  • リクトン近似処理によって、HNP-2HをHNPに変換できる？

AGCD: Approximate Greatest Common Divisors

• AGCDが使える問題
  • `x[i] = q[i] p + r[i]が与えられていてx[i]が既知である場合に、pを求める問題
  • （？）r[i]≈2^λのとき、p≈2^λ+logλ, p[i]≈2^λ+logλ
  • この場合、AGCDが解決する問題は比較的小さい誤差部分r[i]を無視したgcd(x[1], x[2], ..., x[n])を計算することでpを取得する
    • このr[i]を無視してgcdするということで、Approximate-GCD
  • 原論文ではApproximate Common Divisor Problem(ACDP)と呼ばれている
• 使えるアルゴリズム
  • （主力？）LLLで解く
    • https://furutsuki.hatenablog.com/entry/2021/09/23/122340
  • Multivariate polynomial attack https://eprint.iacr.org/2016/215.pdf Section 5
    • https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/mp.py
  • Orthogonal based attack https://eprint.iacr.org/2016/215.pdf Section 4
    • https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/ol.py
  • Simultaneous Diophantine approximation attack https://eprint.iacr.org/2016/215.pdf Section 3
    • https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/sda.py
• https://koba-e964.hatenablog.com/entry/2024/11/03/120213
  • サンプル数が少なすぎると正しい答えが出ない確率が高いが、多いと時間がかかってしまう
  • 1個ずつ増やしながらやっていけばいい？
• Kをどう決めるか
  • K=1 https://zenn.dev/hk_ilohas/articles/wani2024-writeup#easy-calc-%5Beasy%5D
  • K = 2²⁵⁶ 多分最小化したいノルムの各項のサイズ感が同じくらいだとよさそうで、他はqi*riなので、Kをriの大きさにそろえるために、riが256bitsだったら2²⁵⁶している？
    • 計算前のq0x1-q1x0ではなく計算後のq0r1-q1r0で勘定することが大切
• 問題
  • WaniCTF 2024 - uf https://github.com/wani-hackase/wanictf2024-writeup/tree/main/cry/uf
  • RCTF 2021 Uncommon Factor 2 https://furutsuki.hatenablog.com/entry/2021/09/23/122340
  • Midnightsun CTF 2021 Finals Flåarb.tar.xz https://furutsuki.hatenablog.com/entry/2021/09/23/122340
  • ImaginaryCTF 2025 bigger-rsa https://github.com/ImaginaryCTF/ImaginaryCTF-2025-Challenges/tree/main/Crypto/bigger-rsa
• 資料
  • https://koba-e964.hatenablog.com/entry/2024/11/03/120213
  • https://eprint.iacr.org/2016/215.pdf

Hidden Subset Sum Problem

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

他、解ける問題

• 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
• 格子暗号をベースにした準同型型暗号公式
  • 準同型暗号プロ https://nindanaoto.github.io/
    • HECCONは準同型暗号A&D
  • https://hazm.at/mox/security/homomorphic-encryption/index.html
  • https://qiita.com/0917laplace/items/a3ba76a889a80662fddc
  • BFV
  • CKKS
  • TFHE
• 概要
  • 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
• 資料
  • https://qiita.com/kenmaro/items/b6a31574ca94c5470ed6

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

• NTRU: SVPをベースとした耐量子暗号
• https://qiita.com/potyamaaaa/items/3398962093539ad3a141
• https://triodelzx.github.io/2025/04/09/NTRU/

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でないと復元できない