在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具有以下三个特性：

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总共有三种参数：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语言中对这些算法的有效实现，我们期望它们能在适当的场景中积极用于保护您的安全！