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