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是一种非对称签名算法，共分为以下两个步骤。

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    // 需要注意的一点是，截至2024年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中使用的术语是EncapsulationKey，而不是PublicKey。
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=

由此可以确认，生成了相同大小的共享密钥！

该代码也可以在playground中查看。

结论

各算法的规范、安全级别以及私钥、公钥、签名或密文的大小可整理如下。它们各自都不负"PQC"之名，体积颇为可观。

借助这些算法，我们期待在量子计算机环境下也能使用足够安全的互联网，但相对增大的密钥和签名/密文尺寸，显然不可避免地会带来更多的运算开销。

尽管如此，Go语言已经对各算法进行了高效实现，因此我们期待它能在合适的场景中被积极应用，守护各位的安全！