👏

Pythonで追うML-KEM：liboqsによる鍵生成と暗号処理の内部実装

2025/10/07に公開

はじめに

私はPQC（耐量子計算機暗号）やQKD（量子鍵配送）などの最先端暗号技術に強い関心を持つ大学3年生です。将来的には大学院で研究を深め、より安全なデジタル社会の構築に貢献したいと考えています。独学で得た知識を体系的に整理し、分かりやすく情報発信することを目標にしています。

前回の記事である簡易実装から本番実装へ：Pythonで学ぶML-KEMとliboqsではliboqs、liboqs-pythonを使ったML-KEMの簡単な動作フローを紹介しました。それに対し、本記事では、ML-KEMの鍵生成、カプセル化、デカプセル化がライブラリの内部で具体的にどのように実装されているか、特にPythonの呼び出しがC言語の最適化された暗号コアにどう繋がるかに焦点を当てています。

前提

本記事は、前回の記事と併せて読むことで、より深く理解できるように構成されています。また、ML-KEMの鍵生成、カプセル化、デカプセル化といった手順について、基本的な知識があることを前提とします。

ML-KEM-512 テストコード

次に、Python での簡単な動作例を示します。

test_pqc.py

import oqs

def main():
    ALG_NAME = "ML-KEM-512" 

    # 1. Aliceのセットアップ (withブロックで安全にリソースを管理)
    with oqs.KeyEncapsulation(ALG_NAME) as alice:
        
        print(f"--- Algorithm: {ALG_NAME} (NIST PQC Level 1) ---")
        
        # 2. 鍵ペア生成 (KeyGen)
        # # Pythonのラッパーが、liboqs C言語の OQS_KEM_keypair() を呼び出す。
        public_key = alice.generate_keypair()

        # [データサイズの表示]
        pk_len, sk_len = len(public_key), len(alice.export_secret_key())
        print(f"  > 公開鍵 (ek) サイズ: {pk_len} bytes")
        print(f"  > 秘密鍵 (dk) サイズ: {sk_len} bytes")
        
        # --- 公開鍵の送信（Alice -> Bob） ---

        # 3. Bob(鍵をカプセル化する側)の処理（鍵カプセル化 (Encaps)）
        with oqs.KeyEncapsulation(ALG_NAME) as bob:
            # C言語の OQS_KEM_encaps() が実行され、格子上の暗号文(ct)と共通鍵(ss)を生成。
            ciphertext, shared_secret_bob = bob.encap_secret(public_key)

            print(f"  > 暗号文 (ct) サイズ: {len(ciphertext)} bytes")
            print(f"  > Bobの共有秘密鍵 (ss_b) [先頭8B]: {shared_secret_bob[:8].hex()}...")


        # --- 暗号文 (ct) の送信（Bob -> Alice） ---

        # 4. Aliceの処理（秘密鍵を使って鍵復元 (Decaps)）
        # C言語の OQS_KEM_decaps() が実行され、秘密鍵と暗号文から共通鍵を復元。
        shared_secret_alice = alice.decap_secret(ciphertext)
        
        print(f"  > Aliceの復元鍵 (ss_a) [先頭8B]: {shared_secret_alice[:8].hex()}...")

        # 4. 鍵の一致確認
        is_match = shared_secret_alice == shared_secret_bob
        print("\n=== 最終検証: 共有秘密鍵の一致確認 ===")
        print(f"結果: {is_match}")
        print("SUCCESS: 共有秘密鍵が正常に確立されました。" if is_match else "FAILURE")


if __name__ == "__main__":
    main()

実行方法

python3 [test_pqc.pyのパス]

期待される出力

--- Algorithm: ML-KEM-512 (NIST PQC Level 1) ---
> 公開鍵 (ek) サイズ: 800 bytes
> 秘密鍵 (dk) サイズ: 1632 bytes
> 暗号文 (ct) サイズ: 768 bytes
> Bobの共有秘密鍵 (ss_b) [先頭8B]: 5cc98e193723ea33...
> Aliceの復元鍵 (ss_a) [先頭8B]: 5cc98e193723ea33...

=== 最終検証: 共有秘密鍵の一致確認 ===
結果: True
SUCCESS: 共有秘密鍵が正常に確立されました。

ML-KEM 512 の鍵生成フロー

1.Python層：C言語への処理依頼

ここでは、Pythonで実行するpublic_key = alice.generate_keypair()の一行が、C言語のliboqs内部でどのように処理され、ML-KEMの鍵が生成されるかを追跡します。

 # 鍵ペア生成 (KeyGen)
 # Pythonのラッパーが、liboqs Cライブラリの OQS_KEM_keypair() を呼び出す。
 public_key = alice.generate_keypair()

KeyEncapsulationクラスのインスタンス alice で generate_keypair() が呼び出されると、処理はまずPythonラッパー内に移ります。

Pythonコードの役割(oqs.py)
Python側では、C言語が計算結果を書き込むための準備をします。

バッファの確保：インスタンス時に取得した鍵サイズの情報(self._kem.contents.length_public_keyなど)に基づき、公開鍵と秘密鍵のバイト列を受け取るための空のメモリの領域(バッファ)　を確保します。
C関数呼び出し：Python標準のctypesを使い、C言語の汎用APIであるOQS_KEM_keypairを呼び出し、確保したバッファを引数として渡します。

oqs.py(一部)

def generate_keypair(self) -> bytes:
      # 1. C言語に渡すための空のバッファを確保
      public_key = ct.create_string_buffer(self._kem.contents.length_public_key)
      self.secret_key = ct.create_string_buffer(self._kem.contents.length_secret_key)
      
      # 2. C言語の汎用APIを呼び出し、バッファのアドレスを渡す
      rv = native().OQS_KEM_keypair(
          self._kem,
          ct.byref(public_key), 
          ct.byref(self.secret_key),
      )
      # ... (成功時、結果をPythonのbytesとして返す)

2.C言語API層：アルゴリズムの実装への振り分け

OQS_KEM_keypair関数は、liboqs/src/kems/kem.cで定義されている、アルゴリズム非依存の汎用ラッパーです。
この関数自体は、鍵生成アルゴリズムの詳細を知りませんが、KEMコンテキスト(kem)に登録された関数を呼び出す役割を持っています。
具体的には、引数として受け取った kem に格納されている関数ポインタを通じて、正しいアルゴリズムの実装に処理を振り分けます。
ML-KEM-512用のコンテキストでは、kem->keypair に OQS_KEM_ml_kem_512_keypair がセットされており、呼び出すと自動的にML-KEM-512専用の鍵生成処理が実行されます。

kem.c(一部)

OQS_API OQS_STATUS OQS_KEM_keypair(const OQS_KEM *kem, uint8_t *public_key, uint8_t *secret_key) {
     	// ... (NULLチェックなど)
     // 実行時にセットされた関数ポインタを通じて、アルゴリズム固有の鍵生成を実行
 	return kem->keypair(public_key, secret_key);
   }

3.C言語実装層：最適化関数の選択

さらに処理は、liboqs/src/kems/ml-kem/kem_ml_kem_512.c に定義された アルゴリズム固有レイヤー に進みます。
ここでは、実行環境のCPU拡張機能に応じて、最も高速な実装を自動選択する仕組みが組み込まれています。そして、どの環境でも最高のパフォーマンスで鍵生成を実行することを実現しています。

自動ディスパッチ：CPUが特定の拡張命令（例：x86_64向けのSIMDなど）に対応している場合は、最適化された関数 PQCP_MLKEM_NATIVE_MLKEM512_X86_64_keypair が自動的に選ばれます。
フォールバック：CPU拡張が使えない場合は、標準実装である PQCP_MLKEM_NATIVE_MLKEM512_C_keypair が呼ばれます。

4.暗号コア層：ML-KEM計算の実行

選択された最適化関数は、IND-CCA2セキュリティを保証するラッパー関数から呼び出されます。ここで、実際の多項式演算や乱数サンプリングなど、暗号学的要件を満たすための最終的な低レイヤ処理が実行されます。

IND-CPA（選択平文攻撃に対する安全性）

IND-CPA とは、攻撃者が任意に選んだ二つの平文のうちどちらが暗号化されたかを、得られた暗号文から判別できないことを意味します。すなわち、攻撃者がどんな平文ペアを投げても、暗号文だけからは「どちらが暗号化されたか」を当てられない、という保証です。

ML-KEM の実装では、まずこの IND-CPA 安全性を持つ基礎的な公開鍵暗号（ここでは K-PKE：鍵ベースの公開鍵暗号）を構築します。mlk_indcpa_* 系の関数はこのレベルに相当し、LWE ベースの多項式計算で $b = A・s + e$ を作る処理がここで行われます。

IND-CCA（選択暗号文攻撃に対する安全性）

IND-CCA は IND-CPA より強い条件です。攻撃者は公開鍵を知った上で、任意の（ターゲット以外の）暗号文を復号する「復号オラクル」へ問い合わせできるという強い能力を持ちます。そのような条件下でも、攻撃者が特定のターゲット暗号文の中身を推定できないことが IND-CCA の意味です。要するに「復号の助けがあっても、そのターゲット暗号文だけは解けない」保証です。

ML-KEM では、先ほどの IND-CPA レベルのコア（K-PKE）を上位層で拡張／変換して IND-CCA 安全性を実現します。具体的には、IND-CPA を与えた上で公開鍵を秘密鍵に埋め込んだり、ハッシュや PCT（ペアワイズ一貫性テスト）などを組み合わせることで、IND-CCA を満たす設計になっています（crypto_kem_keypair_derand や crypto_kem_enc/dec 系の処理がこの役割を担います）。

4-1.C言語ラッパー(kem.c)の実行

まず、crypto_kem_keypair 関数が実行されます。この関数の役割は、鍵生成に必要な乱数を安全に取得しつつ、IND-CCA2 の安全性を確保して鍵ペアを生成することです。

crypto_kem_keypair の実行手順

乱数シードの取得：mlk_randombytes(coins, ...) を呼び出して、鍵生成に必要な一意の乱数シード（coins）を OS から安全に取得します。この乱数シードは、ML-KEM の鍵生成で使う二つの乱数（ $d$ , $z$ ）をまとめて管理・生成する必要があるため、2 * MLKEM_SYMBYTES のサイズが使われます。
ML-KEM 鍵生成の実行：crypto_kem_keypair_derand(pk, sk, coins); を呼び出し、鍵ペア生成の本体処理を実行します。生成された公開鍵はpkに、秘密鍵はskに格納されます。
メモリの消去：処理完了後、mlk_zeroize(coins, sizeof(coins)); によって、鍵生成に使われた乱数シードをメモリから確実に消去し、秘密情報の残留を防ぎます。

kem.c(一部)

MLK_EXTERNAL_API
int crypto_kem_keypair(uint8_t pk[MLKEM_INDCCA_PUBLICKEYBYTES],
                    uint8_t sk[MLKEM_INDCCA_SECRETKEYBYTES]) {

    // 入力：公開鍵と秘密鍵格納用バッファ
    // 出力：鍵生成処理の結果ステータス

    int res; // 鍵生成処理の結果ステータス
    MLK_ALIGN uint8_t coins[2 * MLKEM_SYMBYTES]; // 乱数シード用バッファ
 
    // --- 1.乱数シードの生成 --- 
    mlk_randombytes(coins, 2 * MLKEM_SYMBYTES);

    // --- 乱数シードは「秘密である」とマーク(サイドチャネル攻撃対策) ---
    MLK_CT_TESTING_SECRET(coins, sizeof(coins)); 

    // --- 2.ML-KEM鍵生成 ---   
    res = crypto_kem_keypair_derand(pk, sk, coins);
 
    // --- 3.メモリ消去 ---
    mlk_zeroize(coins, sizeof(coins));
    return res;
}

4-2.ML-KEMの公開鍵と秘密鍵生成

crypto_kem_keypair_derand関数は、最終的なML-KEM(IND-CCA2)の鍵ペア構造を生成します。

crypto_kem_keypair_derandの実行手順
1. K-PKE鍵ペアを生成：mlk_indcpa_keypair_derand(pk, sk, coins)を呼び出し、K-PKE鍵ペアを生成します。
2. 秘密鍵に公開鍵を格納：KEM(Key Encapsulation Mechanism)の復号処理を高速化するために、公開鍵pkのバイト列を秘密鍵skの末尾にコピーして埋め込みます。
3. 公開鍵のハッシュを保存：公開鍵pkをハッシュ化し、秘密鍵skに格納します。これは再暗号化や整合性チェックに利用されます。
4. 秘密鍵に疑似乱数用zを格納：鍵生成使用された乱数シードcoinsの後半部分を抽出し、秘密鍵の最末尾にコピーします。これはデカプセル化失敗時にランダム値を返すために用いられ、失敗を外部に悟らせない耐故障化の仕組みです。
5. ペアワイズ一貫性テスト(PCT)：鍵が実際に暗号化・復号に使えるかを検証します。失敗した場合は -1 を返します。

kem.c(一部)

MLK_EXTERNAL_API
int crypto_kem_keypair_derand(uint8_t pk[MLKEM_INDCCA_PUBLICKEYBYTES],
                           uint8_t sk[MLKEM_INDCCA_SECRETKEYBYTES],
                           const uint8_t coins[2 * MLKEM_SYMBYTES]) {

   // 入力：乱数シード
   // 出力：公開鍵、秘密鍵

   // --- 1.K-PKE鍵ペアを生成 ---
   mlk_indcpa_keypair_derand(pk, sk, coins);
 
   // --- 2.秘密鍵に公開鍵を追加で格納 ---
   memcpy(sk + MLKEM_INDCPA_SECRETKEYBYTES, pk, MLKEM_INDCCA_PUBLICKEYBYTES);
 
   // --- 3.ハッシュ h(pk) を秘密鍵に追加 ---
   mlk_hash_h(sk + MLKEM_INDCCA_SECRETKEYBYTES - 2 * MLKEM_SYMBYTES, pk,
              MLKEM_INDCCA_PUBLICKEYBYTES);
 
   // --- 4.擬似乱数用の z を秘密鍵に追加 ---
   memcpy(sk + MLKEM_INDCCA_SECRETKEYBYTES - MLKEM_SYMBYTES,
          coins + MLKEM_SYMBYTES, MLKEM_SYMBYTES);
 
   // --- 公開鍵は「秘密ではない」とマーク---
   MLK_CT_TESTING_DECLASSIFY(pk, MLKEM_INDCCA_PUBLICKEYBYTES);
 
   // --- 5.FIPS 140-3 に準拠した「ペアワイズ一貫性テスト」---
   if (mlk_check_pct(pk, sk)) {
     return -1;
   }
 
   return 0;
}

4-3.K-PKE鍵生成の本体(mlk_indcpa_keypair_derand)の実行

mlk_indcpa_keypair_derand は、ML-KEM の基盤であるK-PKE(Key-based Public Key Encryption)の鍵ペア生成を担う中心的な関数です。この関数は、格子暗号のLWE(Learning With Errors)構造に基づき、以下の関係を満たす公開鍵ベクトル $b$ と秘密ベクトル $s$ を生成します。

$b = A・s + e$

ここで、 $A$ は公開鍵行列、 $s$ は秘密ベクトル、 $e$ はノイズ(誤差ベクトル)です。

mlk_indcpa_keypair_derandの実行手順
1. 乱数シードの導出：入力シードcoinsから、必要な2種類のシードを導出します。coinsにドメイン分離子( $k=2$ )を加えてハッシュ化することで、公開鍵行列 $A$ 生成用乱数publicseedと秘密ベクトル $s$ と誤差ベクトル $e$ のサンプリング用乱数noiseseedを生成します。
2. 公開鍵行列 $A$ の生成：1で生成した乱数publicseedを使用して生成されます。 $A$ は、k x k 行列であり、各要素はn次元多項式です。
3. 秘密ベクトル $s$ と誤差ベクトル $e$ のサンプリング：1で生成した乱数noiseseedを用いて、 $η_1$ の小さな係数を持つ多項式ベクトルとして秘密ベクトル $s$ (skpv) と誤差ベクトル $e$ (e) をサンプリングします。（ $k=2$ の時、2個ずつの多項式を効率的に生成しています。）
4. NTT変換の適用：行列積 $A・s$ の計算を高速化するために秘密ベクトル $s$ (skpv) と誤差ベクトル $e$ (e) のNTT変換を行います。
5. LWE関係式の生成( $b = A・s + e$ )：公開鍵の中核となるベクトル $b$ (pkpv) を計算します。
6. 正規化処理と鍵のパッキング：値を mod q に収めます（多項式環上の計算）。秘密鍵には秘密ベクトル $s$ (skpv) 、公開鍵には公開鍵ベクトル $b$ (pkpv)と、行列 A のシード (publicseed) を連結し、バイト列としてpkに格納します。
7. 一時データのゼロ化：計算中に使ったバッファや行列をゼロ化し、秘密情報の残留を防ぎます。

ingcpa.c(一部)

void mlk_indcpa_keypair_derand(uint8_t pk[MLKEM_INDCPA_PUBLICKEYBYTES],
                               uint8_t sk[MLKEM_INDCPA_SECRETKEYBYTES],
                               const uint8_t coins[MLKEM_SYMBYTES]) {

  // 入力：乱数シード
  // 出力：公開鍵、秘密鍵
  uint8_t buf[2 * MLKEM_SYMBYTES]; // 乱数シードの格納用バッファ
  const uint8_t *publicseed = buf; // 公開鍵行列A生成用乱数
  const uint8_t *noiseseed = buf + MLKEM_SYMBYTES; // ノイズベクトルサンプリング用乱数

  mlk_polymat a;          // 公開鍵行列A(k x k)
  mlk_polyvec e, pkpv, skpv;  // 誤差ベクトル e , 公開鍵ベクトル p , 秘密鍵ベクトル s
  mlk_polyvec_mulcache skpv_cache; // NTT変換における中間計算結果の保存領域

  // --- 1. 乱数生成 ---
  uint8_t coins_with_domain_separator[MLKEM_SYMBYTES + 1];
  memcpy(coins_with_domain_separator, coins, MLKEM_SYMBYTES);
  coins_with_domain_separator[MLKEM_SYMBYTES] = MLKEM_K;
  mlk_hash_g(buf, coins_with_domain_separator, MLKEM_SYMBYTES + 1);

  // 公開鍵生成用シードは「公開してよい」ものとして扱う
  MLK_CT_TESTING_DECLASSIFY(publicseed, MLKEM_SYMBYTES);

  // --- 2. 公開鍵行列Aの生成 ---
  mlk_gen_matrix(a, publicseed, 0 /* 転置しない */);

  // --- 3. 秘密鍵ベクトルskpvと誤差ベクトルeサンプリング ---
#if MLKEM_K == 2
  mlk_poly_getnoise_eta1_4x(&skpv[0], &skpv[1], &e[0], &e[1], noiseseed, 0, 1, 2, 3);
#endif

  // --- 4. NTT変換の適用 ---
  mlk_polyvec_ntt(skpv);
  mlk_polyvec_ntt(e);

  // --- 5. LWE関係式の生成 ---
  mlk_polyvec_mulcache_compute(skpv_cache, skpv);
  mlk_matvec_mul(pkpv, a, skpv, skpv_cache);
  mlk_polyvec_tomont(pkpv);

  // 誤差ベクトルを加算 → b = A·s + e
  mlk_polyvec_add(pkpv, e);

  // --- 6. 正規化処理と鍵のパッキング ---
  mlk_polyvec_reduce(pkpv);
  mlk_polyvec_reduce(skpv);

  mlk_pack_sk(sk, skpv);             // 秘密鍵にsを格納
  mlk_pack_pk(pk, pkpv, publicseed); // 公開鍵に(b, publicseed)を格納

  // --- 7. 一時データのゼロ化 ---
  mlk_zeroize(buf, sizeof(buf));
  mlk_zeroize(&a, sizeof(a));
  mlk_zeroize(&e, sizeof(e));
  mlk_zeroize(&pkpv, sizeof(pkpv));
  mlk_zeroize(&skpv, sizeof(skpv));
  mlk_zeroize(&skpv_cache, sizeof(skpv_cache));
}

ML-KEM 512 の鍵カプセル化フロー

1.Python層：C言語への処理依頼

ここでは、Pythonで実行するciphertext, shared_secret_bob = bob.encap_secret(public_key)の一行が、C言語のliboqs内部でどのように処理され、ML-KEMの鍵が生成されるかを追跡します。

# Bobによる鍵カプセル化処理
with oqs.KeyEncapsulation(ALG_NAME) as bob:
    # C言語レベルでは OQS_KEM_encaps() が実行される
    # 暗号文 (ciphertext) と共通鍵 (shared_secret_bob) を生成
    ciphertext, shared_secret_bob = bob.encap_secret(public_key)

KeyEncapsulationクラスのインスタンス bob で encap_secret(public_key) が呼び出されると、処理はまずPythonラッパー内に移ります。

Pythonコードの役割(oqs.py)
Python側では、公開鍵や出力領域をC言語が扱える形式に変換し、C言語を呼び出す準備をします。

公開鍵のバッファ変換：C言語が扱えるように、受け取った公開鍵public_keyをctypes経由でCバッファに変換します。
出力用のバッファの確保：暗号文 (ciphertext) と共通鍵 (shared_secret_bob)を格納するための空メモリ領域を確保します。
C関数呼び出し：ctypes を使って C関数 OQS_KEM_encaps() を呼び出し、確保したバッファのアドレスを渡します。

oqs.py(一部)

def encap_secret(self, public_key: Union[int, bytes]) -> tuple[bytes, bytes]:
    # 1. 公開鍵のバッファ変換
    c_public_key = ct.create_string_buffer(
        public_key,
        self._kem.contents.length_public_key,
    )
    # 2. 出力バッファの確保
    ciphertext: ct.Array[ct.c_char] = ct.create_string_buffer(
        self._kem.contents.length_ciphertext,
    )
    shared_secret: ct.Array[ct.c_char] = ct.create_string_buffer(
        self._kem.contents.length_shared_secret,
    )
    # 3. C言語の汎用APIを呼び出し、確保したバッファのアドレスを渡す
    rv = native().OQS_KEM_encaps(
        self._kem,
        ct.byref(ciphertext),
        ct.byref(shared_secret),
        c_public_key,
    )
    # ... (成功時、結果をPythonのbytesとして返す)

2.C言語API層：アルゴリズムの実装への振り分け

OQS_KEM_encaps関数は、liboqs/src/kems/kem.cで定義されている、アルゴリズム非依存の汎用ラッパーです。

この関数自体は、鍵生成アルゴリズムの詳細を知りませんが、KEMコンテキスト(kem)に登録された関数を呼び出す役割を持っています。

ML-KEM-512用のコンテキストでは、kem->keypair に OQS_KEM_ml_kem_512_encaps がセットされており、呼び出すと自動的にML-KEM-512専用の鍵カプセル化が実行されます。

kem.c(一部)

OQS_API OQS_STATUS OQS_KEM_encaps(const OQS_KEM *kem, uint8_t *ciphertext, uint8_t *shared_secret, const uint8_t *public_key) {
        // ... (NULLチェックなど)
     // 実行時にセットされた、ML-KEM 512専用の関数ポインタを呼び出す
    return kem->encaps(ciphertext, shared_secret, public_key);
}

3.C言語実装層：最適化関数の選択

さらに処理は、liboqs/src/kems/ml-kem/kem_ml_kem_512.c に定義されたアルゴリズム固有レイヤーに進みます。

ここでは、実行環境のCPU拡張機能に応じて、最も高速な実装を自動選択する仕組みが組み込まれています。そして、どの環境でも最高のパフォーマンスで鍵カプセル化を実行することを実現しています。

自動ディスパッチ：CPUが特定の拡張命令（例：x86_64向けのSIMDなど）に対応している場合は、最適化された関数 PQCP_MLKEM_NATIVE_MLKEM512_X86_64_enc が自動的に選ばれます。
フォールバック：CPU拡張が使えない場合は、標準実装である PQCP_MLKEM_NATIVE_MLKEM512_C_enc が呼ばれます。

4.暗号コア層：鍵カプセル化処理(暗号文と共通鍵の生成)

選択された最適化関数は、IND-CCA2セキュリティを保証するラッパー関数から呼び出されます。ここでは、最適化された低レイヤ関数が呼び出され、実際の多項式演算や乱数サンプリングが行われます。

4-1.C言語ラッパー(kem.c)の実行

まず、crypto_kem_enc関数が実行されます。この関数の役割は、暗号文と共通鍵の生成に必要な初期乱数を安全に取得・管理し、コアの決定論的関数を呼び出すことです。

crypto_kem_encの実行手順
1. 乱数シードの取得：mlk_randombytes(coins,...)を呼び出し、共通鍵生成に必要な一意の乱数シード(coins)をOSから安全に取得します。
2. K-PKE暗号化の実行：crypto_kem_enc_derand(ct, ss, pk, coins);を呼び出し、共通鍵と暗号文の生成処理に移ります。生成された暗号文はctに、共通鍵はssに格納されます。
3. メモリの消去：処理完了後、mlk_zeroize(coins, sizeof(coins));により、使われた乱数シードをメモリから確実に消去し、秘密情報の残留を防ぎます。

kem.c(一部)

MLK_EXTERNAL_API
int crypto_kem_enc(uint8_t ct[MLKEM_INDCCA_CIPHERTEXTBYTES],
                   uint8_t ss[MLKEM_SSBYTES],
                   const uint8_t pk[MLKEM_INDCCA_PUBLICKEYBYTES]){

      // 入力：Aliceの公開鍵
      // 出力：暗号文、共通鍵を格納するバッファ

      int res; //処理の結果ステータス(成功で0、エラーで非0)
      MLK_ALIGN uint8_t coins[MLKEM_SYMBYTES]; //乱数シード格納用バッファ
    
      // --- 1.乱数シードの生成 ---
      mlk_randombytes(coins, MLKEM_SYMBYTES);

      // --- 乱数シードは「秘密である」とマーク(サイドチャネル攻撃対策) ---
      MLK_CT_TESTING_SECRET(coins, sizeof(coins));

      // --- 2.ML-KEM鍵カプセル化 ---    
      res = crypto_kem_enc_derand(ct, ss, pk, coins);

      // --- 3.メモリ消去 ---
      mlk_zeroize(coins, sizeof(coins));
      return res;
}

4-2.ML-KEMの共通鍵と暗号文生成(mlk_indcpa_encの呼び出し)

crypto_kem_enc_derand関数では、ML-KEMの鍵カプセル化を行います。

crypto_kem_enc_derandの実行手順
1. 中間バッファの用意：ハッシュ関数の入力シードを構成するための一時バッファと、共通鍵 $K$ (ss)と、暗号化に使用する乱数 $r$ のシードを格納するためのバッファ、を定義します。
2. 公開鍵の形式チェック：mlk_check_pk(pk) により、公開鍵の多項式係数が
  ML-KEMの定義範囲を逸脱していないか検証します。不正な値が含まれる場合は即座にエラーを返し、
  プロトコルの頑健性（FIPS 203準拠）を確保します。
3. セッション鍵シード $m$ の作成：乱数 coins を buf の前半にコピー、公開鍵 $b$ (pk)をハッシュ化したものをbuf の後半に追加します。
4. 共通鍵 $K$ と暗号化用乱数 $r$ の生成：3で構成されたbuf全体に対して、ハッシュ関数を適用し、乱数krを生成します。krは、共通鍵 $K$ とK-PKE暗号化に必要な乱数 $r$ を含みます。
5. K-PKE暗号化の実行と共通鍵の格納：mlk_indcpa_enc(ct, buf, pk, kr + MLKEM_SYMBYTES)が呼び出され、結果の暗号文ctは出力バッファに書き込まれます。krの前半部分を共通鍵バッファssにコピーします。
6. メモリの消去：すべての計算終了後、buf と kr の内容を安全にゼロ化します。

kem.c(一部)

MLK_EXTERNAL_API
int crypto_kem_enc_derand(uint8_t ct[MLKEM_INDCCA_CIPHERTEXTBYTES],
                          uint8_t ss[MLKEM_SSBYTES],
                          const uint8_t pk[MLKEM_INDCCA_PUBLICKEYBYTES],
                          const uint8_t coins[MLKEM_SYMBYTES]){

      // 入力：Aliceの公開鍵、乱数シード
      // 出力：暗号文、共通鍵

　　　　// --- 1. 中間バッファの定義 ---
      MLK_ALIGN uint8_t buf[2 * MLKEM_SYMBYTES];
      MLK_ALIGN uint8_t kr[2 * MLKEM_SYMBYTES];

      // --- 2. 公開鍵の形式チェック ---
      if (mlk_check_pk(pk))
      {
        return -1;
      }

      // --- 3. セッション鍵シードの作成 ---   
      memcpy(buf, coins, MLKEM_SYMBYTES);
      mlk_hash_h(buf + MLKEM_SYMBYTES, pk, MLKEM_INDCCA_PUBLICKEYBYTES);

      // --- 4. 共通鍵と乱数の生成 ---
      mlk_hash_g(kr, buf, 2 * MLKEM_SYMBYTES);

      // --- 5. K-PKE暗号化と共通鍵の格納 ---
      mlk_indcpa_enc(ct, buf, pk, kr + MLKEM_SYMBYTES);
      memcpy(ss, kr, MLKEM_SYMBYTES);
    
      // --- 6.メモリの消去 ----
      mlk_zeroize(buf, sizeof(buf));
      mlk_zeroize(kr, sizeof(kr));
    
      return 0;
}

4-3.K-PKE暗号化の本体(mlk_indcpa_enc)の実行

mlk_indcpa_enc は、、ML-KEMの基礎となるIND-CPA安全な暗号化（K-PKE）を実行する中心的な関数です。この関数は、格子暗号の LWE (Learning With Errors) 構造に基づき、メッセージ(セッション鍵シード) m を暗号文 c=(u,v) に変換します。

ここで、暗号文の各パート $u$ と $v$ は、以下の行列・ベクトル演算によって生成されます。

$u=A^T・y+e_1$
$v=b^T・y+e_2+μ$

ここで、 $A$ は公開鍵行列、 $b$ は公開鍵ベクトル、 $y$ は一時乱数ベクトル、 $e_1$ ・ $e_2$ は誤差ベクトル(ノイズ)、 $μ$ はメッセージ(セッション鍵シード) $m$ を多項式化したものです。

mlk_indcpa_encの実行手順
1. 公開鍵のデコード：公開鍵pkをデコードし、公開鍵ベクトル $b$ (pkpv)と、行列Aの生成に使われたシード $p$ (publicseed)を復元します。
2. メッセージ $m$ の多項式化：メッセージ(セッション鍵シード) $m$ は、 mlk_poly_frommsg() により多項式形式に変換され、暗号化に組み込まれる準備が行われます。
3. 公開鍵行列Aの復元：公開鍵生成時と同じ手順で、mlk_gen_matrix() を使って行列 $A$ の転置 $A^T$ （転置行列）を生成します。
4. ノイズ多項式のサンプリング：格子暗号の安全性を支える「ノイズ」ベクトルをサンプリングします。一時乱数ベクトル $y$ (sp)、誤差ベクトル $e_1$ (ep)、誤差多項式 $e_2$ (epp)は coins から生成され、秘密保持のために外部には公開されません。
5. NTT変換の適用：多項式の掛け算を高速化するために、 $y$ にNTT変換を行います。
6. 暗号文の前半 $u = A^T・y + e_1$ の計算：暗号文の前半パート $u$ (b)を生成します。
7. 暗号文の後半 $v = b^T・y + e_2 + μ$ の計算：暗号文の後半パート $v$ (v)を生成します。
8. 正規化：得られた $u,v$ の係数を有限体上で正規化し、指定範囲（mod q）に収めます。格子上での誤差伝搬を抑え、復号時の整合性を保証します。
9. 暗号文のパッキング：多項式形式の $u,v$ をバイト列に圧縮し、最終的な暗号文 $c$ (c) を生成します。
10. 一時データのゼロ化（セキュリティ対策）：計算に使用したシード、ノイズ、多項式などの全ての秘密情報を mlk_zeroize() でメモリ上から安全にに消去し、秘密情報の残留を防ぎます。

indcpa.c(一部)

MLK_INTERNAL_API
void mlk_indcpa_enc(uint8_t c[MLKEM_INDCPA_BYTES],
                    const uint8_t m[MLKEM_INDCPA_MSGBYTES],
                    const uint8_t pk[MLKEM_INDCPA_PUBLICKEYBYTES],
                    const uint8_t coins[MLKEM_SYMBYTES]){

  //入力：暗号化対象のメッセージ(セッション鍵シード) m 、Aliceの公開鍵、 暗号化に必要なノイズや乱数ベクトルをサンプリングするための乱数 coins
  //出力：暗号文

  MLK_ALIGN uint8_t seed[MLKEM_SYMBYTES]; //公開鍵に含まれているシード格納用バッファ
  mlk_polymat at; 
  mlk_polyvec sp, pkpv, ep, b;
  mlk_poly v, k, epp;
  mlk_polyvec_mulcache sp_cache;

  // --- 1.公開鍵のデコード ---
  mlk_unpack_pk(pkpv, seed, pk);

  // --- 2.メッセージの多項式化 ---
  mlk_poly_frommsg(&k, m);

  // 公開鍵生成用シードは「公開してよい」ものとして扱う
  MLK_CT_TESTING_DECLASSIFY(seed, MLKEM_SYMBYTES);

  // --- 3.公開鍵行列Aの復元 ---
  mlk_gen_matrix(at, seed, 1 /* 転置する */);

// --- 4.ノイズ多項式のサンプリング ---
#if MLKEM_K == 2
  mlk_poly_getnoise_eta1122_4x(&sp[0], &sp[1], &ep[0], &ep[1], coins, 0, 1, 2,3);
  mlk_poly_getnoise_eta2(&epp, coins, 4);
#endif

  // --- 5.NTT変換 ---
  mlk_polyvec_ntt(sp);

  // --- 6. 暗号文パート u = A^T y + e_1 の計算
  mlk_polyvec_mulcache_compute(sp_cache, sp);
  mlk_matvec_mul(b, at, sp, sp_cache);

  // --- 7. 暗号文パート v = b^T y + e_2 + μ の計算
  mlk_polyvec_basemul_acc_montgomery_cached(&v, pkpv, sp, sp_cache);
  mlk_polyvec_invntt_tomont(b);
  mlk_poly_invntt_tomont(&v);
  mlk_polyvec_add(b, ep);
  mlk_poly_add(&v, &epp);
  mlk_poly_add(&v, &k);

  // --- 8. 正規化 ---
  mlk_polyvec_reduce(b);
  mlk_poly_reduce(&v);

  // ---9. 暗号文の生成 --
  mlk_pack_ciphertext(c, b, &v);

  // --- 10. メモリの消去 ----
  mlk_zeroize(seed, sizeof(seed));
  mlk_zeroize(&sp, sizeof(sp));
  mlk_zeroize(&sp_cache, sizeof(sp_cache));
  mlk_zeroize(&b, sizeof(b));
  mlk_zeroize(&v, sizeof(v));
  mlk_zeroize(at, sizeof(at));
  mlk_zeroize(&k, sizeof(k));
  mlk_zeroize(&ep, sizeof(ep));
  mlk_zeroize(&epp, sizeof(epp));
}

ML-KEM 512 の鍵デカプセル化フロー

1.Python層：c言語への処理依頼

# Aliceによる鍵デカプセル化処理
# C言語レベルでは OQS_KEM_decaps() が実行される
# 秘密鍵と暗号文から共通鍵を復元。
shared_secret_alice = alice.decap_secret(ciphertext)

KeyEncapsulationクラスのインスタンス Alice で encap_secret(public_key) が呼び出されると、処理はまずPythonラッパー内に移ります。

Pythonコードの役割(oqs.py)
Python側では、受け取った暗号文から共有鍵を復号するための準備をします。

1.暗号文のバッファ変換：Pythonのbyteで受け取った暗号文 $c$ (ciphertext) を、C言語が扱えるようにC文字列バッファ(char[])に変換します。self._kem.contents.length_ciphertextは、暗号文の固定長を示します。
2.共有鍵の格納用バッファ作成：C言語が扱える形式のバッファを用意します。長さはKEM定義に基づく固定値(32byte)です。
3.C関数呼び出し：ctypesを使って C関数OQS_KEM_decapsを呼び出し、復号結果を受け取るバッファのアドレス、暗号文、秘密鍵を渡します。
4.復号結果の処理：復号成功時は共有鍵をPythonのbyte型に変換して呼び出し元に返し、失敗時は例外を投げて通知します。

oqs.py(一部)

def decap_secret(self, ciphertext: Union[int, bytes]) -> bytes:
    # 1. 暗号文のバッファ変換
    c_ciphertext = ct.create_string_buffer(
        ciphertext,
        self._kem.contents.length_ciphertext,
    )
    # 2. 共有鍵の格納用バッファを作成
    shared_secret: ct.Array[ct.c_char] = ct.create_string_buffer(
        self._kem.contents.length_shared_secret,
    )
    # 3. C言語の汎用APIを呼び出し、復号結果を受け取るバッファのアドレス、暗号文、秘密鍵を渡す
    rv = native().OQS_KEM_decaps(
        self._kem,
        ct.byref(shared_secret),
        c_ciphertext,
        self.secret_key,
    )
    # 4. 復号結果
    if rv == OQS_SUCCESS:
        return bytes(shared_secret)
    msg = "Can not decapsulate secret"
    raise RuntimeError(msg)

2.C言語API層：アルゴリズム実装への振り分け

OQS_KEM_decaps関数は、liboqs/src/kems/kem.cで定義されている、アルゴリズム非依存の汎用ラッパーです。
この関数自体は、鍵生成アルゴリズムの詳細を知りませんが、KEMコンテキスト(kem)に登録された関数を呼び出す役割を持っています。
ML-KEM-512用のコンテキストでは、kem->keypair に OQS_KEM_ml_kem_512_decaps がセットされており、呼び出すと自動的にML-KEM-512専用の鍵生成処理が実行されます。

kem.c(一部)

OQS_API OQS_STATUS OQS_KEM_decaps(const OQS_KEM *kem, uint8_t *shared_secret, const uint8_t *ciphertext, const uint8_t *secret_key) {
        // ... (NULLチェックなど)
    // 実行時にセットされた、ML-KEM 512専用の関数ポインタを呼び出す
    return kem->decaps(shared_secret, ciphertext, secret_key);
}

3.C言語実装層：最適化関数の選択

さらに処理は、liboqs/src/kems/ml-kem/kem_ml_kem_512.c に定義されたアルゴリズム固有レイヤーに進みます。
ここでは、実行環境のCPU拡張機能に応じて、最も高速な実装を自動選択する仕組みが組み込まれています。そして、どの環境でも最高のパフォーマンスで鍵生成を実行することを実現しています。

自動ディスパッチ：CPUが特定の拡張命令（例：x86_64向けのSIMDなど）に対応している場合は、最適化された関数 PQCP_MLKEM_NATIVE_MLKEM512_X86_64_dec が自動的に選ばれます。
フォールバック：CPU拡張が使えない場合は、標準実装である PQCP_MLKEM_NATIVE_MLKEM512_C_dec が呼ばれます。

4.暗号コア層：共有鍵の復元

c言語ラッパー(kem.c)の実行

まず、crypto_kem_dec関数が実行されます。この関数の役割は、IND-CCA2安全性を確保しつつ、Bobと共有する共通鍵を復元するための処理全体を統括することです。

crypto_kem_decの実行手順
1. 秘密鍵の整合性チェック：秘密鍵が破損、不正でないかチェックします。不正の場合は、直ちに処理を中止して-1を返します。
2. K-PKE復号：mlk_indcpa_dec(buf, ct, sk)を呼び出し、暗号文を秘密鍵で復号します。復号結果(セッション鍵シード $m$ の候補)はbufの前半に書き込まれます。
3. 共通鍵候補と再暗号化乱数の生成：2で得られた $m$ の候補(bufの前半)と秘密鍵に格納されている公開鍵のハッシュを結合し、ハッシュ化することでkrを生成します。krの前半は共有鍵候補、後半は再暗号化用の $r$ のシードです。
4. 暗号文の再暗号化・検証(K-PKE暗号化)：mlk_indcpa_enc(tmp, buf, pk, kr + MLKEM_SYMBYTES)を呼び出して、暗号文を再生成し、tmpに格納します。元の暗号文c(ct) と比較します。結果（一致/不一致）は fail フラグに格納されます。
5. 失敗時用の共通鍵生成：検証失敗時に使用される共通鍵を生成します。すなわち、検証失敗時には、秘密鍵に埋め込まれた疑似乱数シード $z$ と、入力された暗号文 $c$ を連結し、ハッシュ化することで得られるものを共通鍵とします。
6. 共通鍵の決定：検証成功時は3で生成された共通鍵候補を共通鍵とし、失敗時は5で生成された偽の共通鍵(ランダムな鍵)を共通鍵とします。mlk_ct_cmov_zeroは一定時間実行で行われているため、復号結果の情報が処理時間を通じて外部に漏れるのを防ぎます。
7. メモリの消去：復号結果や中間値がメモリに残らないようにゼロ化します。

kem.c

MLK_EXTERNAL_API
int crypto_kem_dec(uint8_t ss[MLKEM_SSBYTES],
                   const uint8_t ct[MLKEM_INDCCA_CIPHERTEXTBYTES],
                   const uint8_t sk[MLKEM_INDCCA_SECRETKEYBYTES]){

  // 入力：暗号文、Aliceの秘密鍵
  // 出力：共通鍵

  uint8_t fail;
  MLK_ALIGN uint8_t buf[2 * MLKEM_SYMBYTES]; //乱数シード格納用バッファ
  MLK_ALIGN uint8_t kr[2 * MLKEM_SYMBYTES]; 
  MLK_ALIGN uint8_t tmp[MLKEM_SYMBYTES + MLKEM_INDCCA_CIPHERTEXTBYTES];

  const uint8_t *pk = sk + MLKEM_INDCPA_SECRETKEYBYTES;

  // --- 1.秘密鍵の整合性チェック ---
  if (mlk_check_sk(sk))
  {
    return -1;
  }

  // --- 2.K-PKE復号 ---
  mlk_indcpa_dec(buf, ct, sk);

  // --- 3.共通鍵候補と再暗号化乱数の生成 ---
  memcpy(buf + MLKEM_SYMBYTES,
         sk + MLKEM_INDCCA_SECRETKEYBYTES - 2 * MLKEM_SYMBYTES, MLKEM_SYMBYTES);
  mlk_hash_g(kr, buf, 2 * MLKEM_SYMBYTES);

  // ---  4.暗号文の再暗号化・検証(K-PKE暗号化) ---
  mlk_indcpa_enc(tmp, buf, pk, kr + MLKEM_SYMBYTES);
  fail = mlk_ct_memcmp(ct, tmp, MLKEM_INDCCA_CIPHERTEXTBYTES);

  // --- 5.失敗時用の共通鍵生成 ---
  memcpy(tmp, sk + MLKEM_INDCCA_SECRETKEYBYTES - MLKEM_SYMBYTES,
         MLKEM_SYMBYTES);
  memcpy(tmp + MLKEM_SYMBYTES, ct, MLKEM_INDCCA_CIPHERTEXTBYTES);
  mlk_hash_j(ss, tmp, sizeof(tmp));

  // --- 6.共通鍵の決定 ---
  mlk_ct_cmov_zero(ss, kr, MLKEM_SYMBYTES, fail);

  # --- 7. メモリの消去 ---
  mlk_zeroize(buf, sizeof(buf));
  mlk_zeroize(kr, sizeof(kr));
  mlk_zeroize(tmp, sizeof(tmp));

  return 0;
}

はじめに

前提

ML-KEM-512 テストコード

ML-KEM 512 の鍵生成フロー

1.Python層：C言語への処理依頼

2.C言語API層：アルゴリズムの実装への振り分け

3.C言語実装層：最適化関数の選択

4.暗号コア層：ML-KEM計算の実行

ML-KEM 512 の鍵カプセル化フロー

1.Python層：C言語への処理依頼

2.C言語API層：アルゴリズムの実装への振り分け

3.C言語実装層：最適化関数の選択

4.暗号コア層：鍵カプセル化処理(暗号文と共通鍵の生成)

ML-KEM 512 の鍵デカプセル化フロー

1.Python層：c言語への処理依頼

2.C言語API層：アルゴリズム実装への振り分け

3.C言語実装層：最適化関数の選択

4.暗号コア層：共有鍵の復元

Discussion