Usage of MLDSA and MLKEM in Go Language

Overview

Background

For quite some time, the rapid computation of quantum computers has been recognized as a threat to existing cryptographic systems. Existing methods such as RSA and ECC, for example, can potentially be deciphered due to 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 standardizing PQC (Post-Quantum Cryptography).

MLDSA and MLKEM

Ultimately, in August 2024, NIST adopted MLKEM and MLDSA, based on CRYSTALS-Kyber and CRYSTALS-Dilithium, respectively, as standards. Both algorithms operate based on the problem of Module Learning with Errors (MLWE). This format is referred to as lattice-based cryptography.

Lattice-based cryptography, as the name suggests, is a cryptographic system based on the difficulty of mathematical problems on a lattice. While I do not possess in-depth mathematical knowledge on this subject, it can be summarized in one line as the problem of solving noisy linear equations in a module lattice. Although the level of difficulty is not intuitive, it is said that such problems are difficult to solve even with quantum computers.

MLDSA

Let us first examine MLDSA.

Composition

MLDSA, as indicated by its name, is an asymmetric signature algorithm that proceeds through the following two stages:

1. Signature Generation: Generating a signature for a message using a private key.
2. Signature Verification: Verifying the validity of the generated signature using a public key.

Additionally, MLDSA possesses the following three characteristics:

1. Strong existential unforgeability: It is impossible to generate another valid signature with one signature and a public key.
2. Chosen message attack: It is impossible to generate a new valid signature with a public key from a signature for any message.
3. Side-channel attack: It is highly secure because it continuously uses new random values and pseudo-random values derived from the message during signing.
4. Domain separation: It prevents repetitive security issues by using different seeds for different parameters.

Code

Now, let us present a simple example code in Go. In this example, we have used mldsa from cloudflare/circl.

 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    // Generates a key with mldsa44 specifications.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Generates a signature.
22    // One thing to note is that, as of the version on December 22, 2024, an error occurs if it is not 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    // Verifies 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 has been omitted because it is too long. If you wish to see the full text, please execute it on the playground.

Although encoded in base64, it may be somewhat burdensome that it produces 3228 bytes. It is slightly concerning to think that we might soon need to exchange this size as a signature against quantum computers.

MLKEM

Composition

MLKEM is a Key Encapsulation Mechanism (KEM). A KEM is an algorithm that allows the generation of a shared key between two parties using public-key cryptography. The key exchange mechanism of MLKEM proceeds through the following steps:

1. Key Encapsulation: The sender uses the recipient's public key to generate an encrypted message (cipher text) and a shared key. This encrypted message is initially transmitted to the recipient for their use.
2. Key Decapsulation: The recipient uses their private key to extract the shared key from the encrypted message.

MLKEM has a total of three parameters. MLKEM-512, MLKEM-768, and MLKEM-1024 exist; smaller parameters result in smaller keys and ciphertext, and larger parameters result in longer keys and ciphertext and a higher level of security.

Code

MLKEM is scheduled to be added in go 1.24, so we used go 1.24rc1, which is available at this time.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Generates the recipient's PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // In MLKEM, the term EncapsulationKey is used instead of PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Simply cloned to show that the key can be extracted and reused with Bytes() and NewEncapsulationKeyX of the EncapsulationKey.
20    // Of course, in reality, this process can be seen as the sender creating an object from the recipient's EncapsulationKey key, which was publicly available in text.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // The sender generates ciphertext and a shared key with Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Intentionally cloned to demonstrate the storage and retrieval of the recipient's private key.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // The recipient uses the private key to Decapsulate the ciphertext 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, it can be confirmed that shared keys of the same size are generated!

This code can also be found on the playground.

Conclusion

The specifications of each algorithm, security levels, and sizes of private keys, public keys, signatures, and ciphertexts can be summarized as follows. Each boasts a large size, befitting the name PQC.

We hope that these algorithms will enable us to use the internet safely even on quantum computers, but it seems inevitable that there will be more computations due to the relatively increased key and signature/ciphertext sizes.

Nevertheless, since each algorithm is effectively implemented in the Go language, it is expected that they will be actively utilized to protect your security in appropriate locations!