Anwendung von MLDSA und MLKEM in der Go-Sprache

Übersicht

Hintergrund

Schon seit geraumer Zeit wird die schnelle Rechenleistung von Quantencomputern als Bedrohung für bestehende kryptografische Systeme wahrgenommen. Dies liegt daran, dass etablierte Methoden wie RSA oder ECC aufgrund dieser Rechenfähigkeiten von Quantencomputern entschlüsselt werden könnten. Seit einigen Jahren jedoch konkretisiert sich das Konzept des Quantencomputers, und infolgedessen wurden Alternativen erforscht und entwickelt, wobei das NIST die Standardisierung von PQC (Post-Quantum Cryptography) vorangetrieben hat.

MLDSA und MLKEM

Schließlich hat das NIST im August 2024 MLKEM und MLDSA, basierend auf CRYSTALS-Kyber und CRYSTALS-Dilithium, als Standards verabschiedet. Beide Algorithmen basieren auf dem MLWE-Problem (Module Learning with Errors). Wir bezeichnen diese Form als gitterbasierte Kryptographie.

Gitterbasierte Kryptographie ist, wie der Name schon sagt, ein kryptographisches System, das auf der Schwierigkeit mathematischer Probleme auf einem Gitter basiert. Auch wenn mir keine umfassenden mathematischen Kenntnisse dazu vorliegen, lässt es sich in einem Satz zusammenfassen als „das Problem, lineare Gleichungen mit Rauschen in einem Modulgitter zu lösen“. Es ist schwer einzuschätzen, wie schwierig dies ist, aber es wird angenommen, dass solche Probleme selbst für Quantencomputer unlösbar schwer sind.

MLDSA

Lassen Sie uns zunächst MLDSA betrachten.

Aufbau

MLDSA ist, wie der Name schon andeutet, ein asymmetrisches Signaturalgorithmus, der aus den folgenden zwei Phasen besteht:

1. Signaturerstellung: Erzeugt eine Signatur für eine Nachricht unter Verwendung des privaten Schlüssels.
2. Signaturprüfung: Überprüft die Gültigkeit der erzeugten Signatur unter Verwendung des öffentlichen Schlüssels.

Des Weiteren besitzt MLDSA die folgenden drei Eigenschaften:

1. strong existential unforgeability: Es ist nicht möglich, aus einer Signatur und einem öffentlichen Schlüssel eine andere gültige Signatur zu generieren.
2. chosen message attack: Selbst mit einem öffentlichen Schlüssel kann keine neue gültige Signatur aus der Signatur einer beliebigen Nachricht generiert werden.
3. side-channel attack: Durch die kontinuierliche Verwendung neuer Zufallswerte und aus der Nachricht abgeleiteter Pseudozufallswerte bei der Signaturerstellung wird eine hohe Sicherheit gewährleistet.
4. domain separation: Durch die Verwendung unterschiedlicher Seeds für unterschiedliche Parameter werden wiederkehrende Sicherheitsprobleme vermieden.

Code

Im Folgenden finden Sie ein einfaches Go-Codebeispiel. Dieses Beispiel verwendet mldsa von 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    // Generiert einen Schlüssel gemäß der mldsa44-Spezifikation.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Erzeugt eine Signatur.
22    // Eine Anmerkung: Basierend auf der aktuellen Version vom 22. Dezember 2024, tritt ein Fehler auf, wenn crypto.Hash(0) nicht verwendet wird.
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    // Überprüft die Signatur, indem das Schema des öffentlichen Schlüssels aufgerufen wird.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Der Signaturwert wurde aufgrund seiner Länge weggelassen. Wenn Sie den vollständigen Wert sehen möchten, führen Sie ihn bitte im playground aus.

Obwohl es base64-kodiert ist, ist eine Größe von 3228 Byte möglicherweise etwas überfordernd. Es ist etwas beunruhigend zu überlegen, dass wir in naher Zukunft möglicherweise Signaturen dieser Größe austauschen müssen, um Quantencomputern standzuhalten.

MLKEM

Aufbau

MLKEM ist ein Key Encapsulation Mechanism. KEM ist ein Algorithmus, der es zwei Parteien ermöglicht, unter Verwendung eines Public-Key-Verschlüsselungsverfahrens einen gemeinsamen Schlüssel zu generieren. Der Schlüsselaustauschmechanismus von MLKEM durchläuft die folgenden Schritte:

1. Schlüsselkapselung: Der Sender erzeugt einen verschlüsselten Nachrichtentext (cipher text) und einen gemeinsamen Schlüssel (shared key) unter Verwendung des öffentlichen Schlüssels des Empfängers. Dieser verschlüsselte Nachrichtentext wird initial an den Empfänger übermittelt, um verwendet zu werden.
2. Schlüsselentkapselung: Der Empfänger extrahiert den gemeinsamen Schlüssel aus dem verschlüsselten Nachrichtentext unter Verwendung seines privaten Schlüssels.

Es gibt insgesamt drei Parameter für MLKEM: MLKEM-512, MLKEM-768 und MLKEM-1024. Kleinere Werte führen zu kleineren Schlüsseln und Chiffretexten, während größere Werte zu längeren Schlüsseln und Chiffretexten sowie einem höheren Sicherheitsniveau führen.

Code

Da MLKEM in Go 1.24 eingeführt werden soll, wurde für den aktuellen Zeitpunkt Go 1.24rc1 verwendet.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Generiert den PrivateKey des Empfängers.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM verwendet den Begriff EncapsulationKey anstelle von PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Zur Demonstration, dass der Schlüssel mit Bytes() und NewEncapsulationKeyX extrahiert und wiederverwendet werden kann, wurde er geklont.
20    // In der Realität würde dieser Vorgang bedeuten, dass der Sender den EncapsulationKey des Empfängers, der als Text veröffentlicht wurde, in ein Objekt umwandelt.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Der Sender generiert mit Encapsulate den Ciphertext und den SharedKey.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Der Empfänger wird absichtlich geklont, um das Speichern und Abrufen des privaten Schlüssels zu demonstrieren.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Der Empfänger verwendet den privaten Schlüssel, um den Ciphertext zu entschlüsseln und einen weiteren SharedKey zu generieren.
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=

Es ist ersichtlich, dass letztendlich gemeinsam genutzte Schlüssel gleicher Größe generiert werden!

Dieser Code kann auch im Playground überprüft werden.

Fazit

Die Spezifikationen, Sicherheitsniveaus, Größen von privaten und öffentlichen Schlüsseln sowie Signaturen oder Chiffretexten der einzelnen Algorithmen lassen sich wie folgt zusammenfassen. Sie alle weisen beachtliche Größen auf, was dem Namen PQC gerecht wird.

Wir hoffen, dass wir mit diesen Algorithmen ein ausreichend sicheres Internet auch auf Quantencomputern nutzen können, doch scheint es unvermeidlich, dass die relativ größeren Schlüssel- und Signatur-/Chiffretextgrößen zu mehr Rechenaufwand führen werden.

Dennoch sind die Algorithmen in der Go-Sprache effizient implementiert, und wir erwarten, dass sie aktiv eingesetzt werden, um Ihre Sicherheit an den entsprechenden Stellen zu gewährleisten!