Usage of MLDSA and MLKEM in Go Language

Overview

Background

For a considerable period, the rapid computational capabilities of quantum computers have been recognized as a threat to existing cryptographic systems. This is because current systems such as RSA and ECC are susceptible to decryption due to the operational power of quantum computers. However, as the concept of quantum computing became more tangible several years ago, alternative solutions began to be researched and developed, leading NIST to pursue the standardization of PQC (Post-Quantum Cryptography).

MLDSA and MLKEM

Ultimately, NIST adopted MLKEM and MLDSA, based on CRYSTALS-Kyber and CRYSTALS-Dilithium, as standards in August 2024. Both algorithms operate based on a problem known as MLWE (Module Learning with Errors). We refer to this format as lattice-based cryptography.

Lattice-based cryptography, as its name suggests, is a cryptographic system founded on the mathematical difficulty of problems on a lattice. Although I lack profound mathematical knowledge on this subject, it can be summarized as "the problem of solving linear equations with noise in a module lattice." While the extent of its difficulty is not immediately apparent, such problems are reportedly so challenging that even quantum computers cannot solve them.

MLDSA

Next, we will examine MLDSA.

Configuration

MLDSA, as its name implies, is an asymmetric signature algorithm that involves the following two main stages:

1. Signature Generation: A signature for a message is created using a private key.
2. Signature Verification: The validity of the generated signature is confirmed using a public key.

Furthermore, MLDSA possesses the following three characteristics:

1. strong existential unforgeability: It is impossible to generate another valid signature from one signature and public key.
2. chosen message attack: With a public key, it is impossible to generate a new valid signature from a signature for any message.
3. side-channel attack: Security is enhanced by continuously using new random values and pseudo-random values derived from the message during signature generation.
4. domain separation: Different seeds are used for different parameters to prevent recurrent security issues.

Code

Here is a simple Go language example code. This example utilizes 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 point to note is that as of the current version, 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    // Calls the public key's scheme to perform verification.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

The signature value was omitted due to its length. If you wish to view the full text, please execute it on playground.

Even with base64 encoding, a signature value of 3228 bytes might be somewhat burdensome. It is somewhat concerning to consider that we might soon need to exchange data of this size as a signature against quantum computers.

MLKEM

Configuration

MLKEM is a Key Encapsulation Mechanism. KEM is an algorithm that enables the generation of a shared key between two parties using public-key cryptography. MLKEM's key exchange mechanism follows these steps:

1. Key Encapsulation: The sender uses the recipient's public key to generate an encrypted message (ciphertext) 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 three parameters in total. MLKEM-512, MLKEM-768, and MLKEM-1024 exist, where smaller numbers result in smaller keys and ciphertexts, and larger numbers result in longer keys and ciphertexts, offering higher security levels.

Code

MLKEM is slated for inclusion in Go 1.24, so 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    // Generates the receiver's PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM uses the term EncapsulationKey instead of PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // This cloning demonstrates that a key can be extracted and reused using EncapsulationKey's Bytes() and NewEncapsulationKeyX.
20    // In a real-world scenario, this process would represent the sender creating an object from the recipient's publicly available EncapsulationKey text.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // The sender generates the ciphertext and shared key using Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // This cloning is done to illustrate the process of storing and retrieving the receiver's private key.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // The receiver uses their private key to Decapsulate the ciphertext, generating 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 observed that shared keys of the same size are generated!

This code can also be viewed on playground.

Conclusion

The specifications, security levels, and sizes of private keys, public keys, signatures, or ciphertexts for each algorithm can be summarized as follows. Each boasts substantial sizes, living up to the name PQC.

Through these algorithms, we anticipate being able to utilize a sufficiently secure internet even against quantum computers. However, it appears unavoidable that the relatively larger key and signature/ciphertext sizes will necessitate more computations.

Nevertheless, given the effective implementation of each algorithm in the Go language, we anticipate their proactive utilization in appropriate contexts to safeguard your security!