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には次の3つの特性があります。

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言語には各アルゴリズムが効果的に実装されているため、適切な場所で皆様のセキュリティを守るために積極的に活用されることを期待します！