Go言語におけるMLDSAおよびMLKEMの利用記

概要

背景

かなり以前から、量子コンピュータの高速な演算は既存の暗号方式にとって脅威として認識されてきました。既存のRSAやECCなどは、量子コンピュータのこのような演算能力によって解読される可能性があるためです。しかし数年前から量子コンピュータという概念が現実味を帯び始めると、それに対する代替案の研究および開発が始まり、NISTではPQC(耐量子暗号)の標準化を進めてきました。

MLDSAとMLKEM

ついにNISTは2024年8月に、CRYSTALS-KyberおよびCRYSTALS-Dilithiumを基盤とするMLKEMとMLDSAを標準として採択しました。両アルゴリズムは、MLWE(Module Learning with Errors)という問題に基づいて動作します。このような形式を、私たちは格子基盤暗号と呼んでいます。

格子基盤暗号は、その名のとおり格子上の数学的問題の困難性に基づく暗号システムです。私自身もこれについて深い数学的知識はありませんが、一行で要約するとモジュール格子においてノイズのある線形方程式を解く問題だといいます。どれほど困難なのかは実感が湧きませんが、このような問題は量子コンピュータでも解けないほど難しいとされています。

MLDSA

それでは、まずMLDSAについて見ていきましょう。

構成

MLDSAは名前からも分かるように公開鍵(非対称)署名アルゴリズムであり、全体として以下の2段階を経ます。

1. 署名生成: 秘密鍵を使用してメッセージに対する署名を生成
2. 署名検証: 公開鍵を用いて、生成された署名の有効性を確認

また、MLDSAには次の4つの特性があります。

1. strong existential unforgeability: 一つの署名と公開鍵から、別の有効な署名を生成することはできません。
2. chosen message attack: 任意のメッセージに対する署名を用いても、公開鍵を使って新たな有効な署名を生成することはできません。
3. side-channel attack: 署名時に毎回新しいランダム値と、メッセージから導出された擬似ランダム値を用いるため、安全性が高くなります。
4. domain separation: 異なるパラメータに対して異なるseedを使用するようにし、反復による安全性の問題を予防します。

コード

それでは、簡単なGo言語のサンプルコードをご紹介します。
この例ではcloudflare/circlのmldsaを使用しました。

 1package main
 2
 3import (
 4	"crypto"
 5	"crypto/rand"
 6	"encoding/base64"
 7	"fmt"
 8
 9	"github.com/cloudflare/circl/sign/mldsa/mldsa44"
10)
11
12func main() {
13    // mldsa44スペックで鍵を生成します。
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // 署名を生成します。
22    // 一つ注意すべき点は、24年12月22日現在のバージョンでは、crypto.Hash(0)でない場合にエラーが発生するということです。
23	signature, err := priv.Sign(rand.Reader, message, crypto.Hash(0))
24	if err != nil {
25		panic(err)
26	}
27
28	encodedSignature := base64.URLEncoding.EncodeToString(signature)
29	fmt.Println(len(encodedSignature), encodedSignature)
30
31    // 公開鍵のschemeを呼び出して検証を行います。
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

署名の値は長すぎるため省略しました。全文を確認したい場合は、playgroundで実行してみてください。

base64でエンコードしたとはいえ、3228バイトになるのは少し負担に感じられるでしょう。
近いうちに、私たちは量子コンピュータに対抗する署名としてこのサイズをやり取りしなければならないかもしれないと考えると、少し負担に感じられますね……

MLKEM

構成

MLKEMは鍵カプセル化メカニズム(Key Encapsulation Mechanism)です。KEMは公開鍵暗号方式を用いて、二者間の共有鍵を生成できるようにするアルゴリズムです。MLKEMの鍵交換メカニズムは次の過程を経ます。

1. 鍵カプセル化: 送信者は受信者の公開鍵を用いて、暗号化されたメッセージ(cipher text)と共有鍵(shared key)を生成します。この暗号化されたメッセージを受信者に送り、利用してもらいます。
2. 鍵カプセル解除: 受信者は自身の秘密鍵を用いて、暗号化されたメッセージから共有鍵を抽出します。

MLKEMには全部で3つのパラメータが存在します。MLKEM-512、MLKEM-768、MLKEM-1024があり、数字が小さいほど小さな鍵と暗号文が生成され、大きいほど長い鍵と暗号文が生成されて、セキュリティレベルがより高くなります。

コード

MLKEMはGo 1.24に追加される予定のため、現時点で利用可能なGo 1.24rc1を使用しました。

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // 受信者のPrivateKeyを生成します。
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEMではPublicKeyではなくEncapsulationKeyという用語を使用します。
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // 簡単のため、EncapsulationKeyのBytes()とNewEncapsulationKeyXでキーを抽出して再利用できることを示すために複製しました。
20    // 実際の運用では、この過程は、テキストとして公開されていた受信者のEncapsulationKeyを送信者がオブジェクトとして生成する過程だと考えてください。
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Encapsulateにより、送信者が暗号文と共有鍵を生成します。
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // 受信者の秘密鍵を保存して取り出す過程を示すため、あえて複製しました。
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // 受信者は秘密鍵を用いて暗号文をDecapsulateし、もう一つの共有鍵を生成します。
36	sharedKeyReceiver, err := clonedReceiverKey.Decapsulate(cipherText)
37	if err != nil {
38		panic(err)
39	}
40
41	fmt.Println(base64.StdEncoding.EncodeToString(SenderSharedKey))
42	fmt.Println(base64.StdEncoding.EncodeToString(sharedKeyReceiver))
43}

1Q1ciS818WFHTK7D4MTvsQvciMTGF+dSGqMllOxW80ew=
2Q1ciS818WFHTK7D4MTvsQvciMTGF+dSGqMllOxW80ew=

その結果、同じサイズの共有鍵が生成されることを確認できます!

このコードはプレイグラウンドでも確認できます。

結論

各アルゴリズムのスペック、セキュリティレベル、秘密鍵、公開鍵、署名や暗号文のサイズは次のように整理できます。いずれもPQCという名前に恥じない大きなサイズを誇ります。

これらのアルゴリズムにより、量子コンピュータ上においても十分に安全なインターネットを利用できることを期待していますが、相対的に大きくなった鍵や署名/暗号文のサイズにより、より多くの演算が必要になることは避けられないように思われます。

それでも、Go言語では各アルゴリズムが効果的に実装されているため、適切な場面でみなさんのセキュリティを守るために積極的に活用されることを期待しています!