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

hamayanhamayan's blog

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より大幅に小さい！）
  • 符号暗号: 誤り訂正符号に基づく暗号化
  • 資料