Experiences Using MLDSA and MLKEM in the Go Language

Overview

Background

For quite some time, the rapid computation of quantum computers has been recognized as a threat to existing cryptographic systems. This is because traditional schemes such as RSA and ECC may be broken by the computational capabilities of quantum computers. However, as the concept of quantum computers began to materialize several years ago, alternatives began to be researched and developed, and NIST has been advancing the standardization of PQC (Post-Quantum Cryptography).

MLDSA and MLKEM

Finally, in August 2024, NIST adopted MLKEM and MLDSA, which are based on CRYSTALS-Kyber and CRYSTALS-Dilithium, as standards. Both algorithms operate on the basis of a problem called MLWE (Module Learning with Errors). We refer to this type of scheme as lattice-based cryptography.

Lattice-based cryptography is, as the name suggests, a cryptographic system based on the hardness of mathematical problems on lattices. I do not have deep mathematical knowledge of this either, but in one line it is summarized as the problem of solving noisy linear equations over a module lattice. It is difficult to get a sense of how hard this is, but this problem is said to be so difficult that it cannot be solved even by quantum computers.

MLDSA

Let us first look at MLDSA.

Structure

As the name suggests, MLDSA is an asymmetric signature algorithm and goes through the following two steps.

1. Signature generation: Generate a signature for a message using the private key
2. Signature verification: Verify the validity of the generated signature using the public key

MLDSA also has the following three properties.

1. Strong existential unforgeability: One cannot generate another valid signature from a signature and the public key.
2. Chosen message attack: Even with signatures on any messages, one cannot generate a new valid signature using the public key.
3. Side-channel attack: During signing, security is enhanced by continuously using new random values and pseudorandom values derived from the message.
4. Domain separation: By using different seeds for different parameters, repeated security issues are prevented.

Code

Now, let us look at a simple Go language example code. In this example, the mldsa package from cloudflare/circl was used.

 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    // Generate a key with the mldsa44 spec.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Generate a signature.
22    // One point to note is that as of the version on December 22, 2024, an error occurs if crypto.Hash(0) is not used.
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    // Verify by calling the scheme of the public key.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

The signature value was omitted because it is too long. If you want to see the full text, please run it at the playground.

Even though it is base64 encoded, a size of 3228 bytes is likely to be somewhat burdensome. Thinking that we may soon have to exchange signatures of this size as countermeasures against quantum computers, it does feel a bit burdensome..

MLKEM

Structure

MLKEM is a Key Encapsulation Mechanism (KEM). A KEM is an algorithm that uses public-key cryptography to enable the generation of a shared key between two parties. The key exchange mechanism of MLKEM goes through the following process.

1. Key encapsulation: The sender uses the receiver's public key to generate an encrypted message (cipher text) and a shared key (shared key). This encrypted message is initially delivered to the receiver for use.
2. Key decapsulation: The receiver uses its own private key to extract the shared key from the encrypted message.

MLKEM has a total of three parameter sets: MLKEM-512, MLKEM-768, and MLKEM-1024. The smaller the parameter, the smaller the keys and cipher text it produces, and the larger the parameter, the longer the keys and cipher text it produces, along with a higher security level.

Code

Since MLKEM is scheduled to be added in Go 1.24, go 1.24rc1, which is currently available, was used.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Generate the receiver's PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // In MLKEM, the term EncapsulationKey is used rather than PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // For simplicity, the EncapsulationKey was cloned to show that the key can be extracted with Bytes() and reused with NewEncapsulationKeyX.
20    // Of course, in practice, you can understand this process as the sender turning the receiver's EncapsulationKey, which was publicly available as text, into an object.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // The sender generates the cipher text and shared key with Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // The receiver's private key was deliberately cloned to show how it is stored and retrieved.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // The receiver uses the private key to Decapsulate the cipher text and generate another shared key.
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=

As a result, you can confirm that shared keys of the same size are generated!

This code can also be checked at the playground.

Conclusion

The specifications, security levels, and sizes of private keys, public keys, and signatures or cipher texts of each algorithm can be summarized as follows. Each of them proudly boasts large sizes, befitting the name PQC.

With these algorithms, we hope to be able to use the Internet securely even on quantum computers, but it seems unavoidable that more computation will be required due to the relatively larger keys and signature/cipher text sizes.

Nevertheless, since Go has effectively implemented each of these algorithms, we hope they will be actively utilized to protect your security in appropriate places!