Användning av MLDSA och MLKEM i Go-språket

Översikt

Bakgrund

Sedan en längre tid tillbaka har den snabba beräkningsförmågan hos kvantdatorer ansetts vara ett hot mot befintliga krypteringssystem. Befintliga system som RSA och ECC kan potentiellt dechiffreras på grund av kvantdatorers beräkningskapacitet. Men i och med att konceptet med kvantdatorer började bli mer konkret för några år sedan, påbörjades forskning och utveckling av alternativ. NIST har sedan dess arbetat med standardisering av PQC (Post-Quantum Cryptography).

MLDSA och MLKEM

Slutligen antog NIST i augusti 2024 MLKEM och MLDSA som standarder, vilka är baserade på CRYSTALS-Kyber respektive CRYSTALS-Dilithium. Båda algoritmerna fungerar utifrån problemet MLWE (Module Learning with Errors). Denna typ av system benämns som gitterbaserad kryptografi.

Gitterbaserad kryptografi är, som namnet antyder, ett krypteringssystem baserat på svårigheten i matematiska problem på gitter. Jag har inte heller någon djupare matematisk kunskap om detta, men sammanfattningsvis handlar det om problemet att lösa linjära ekvationer med brus i ett modulärt gitter. Hur svårt det är är svårt att greppa, men det sägs vara så svårt att det inte ens kan lösas av kvantdatorer.

MLDSA

Låt oss först undersöka MLDSA.

Struktur

MLDSA är, som namnet antyder, en asymmetrisk signaturalgoritm som genomgår totalt två steg.

1. Signaturskapande: Skapar en signatur för meddelandet med hjälp av den privata nyckeln.
2. Signaturverifiering: Verifierar giltigheten av den skapade signaturen med hjälp av den publika nyckeln.

MLDSA har även följande tre egenskaper:

1. strong existential unforgeability: Det är inte möjligt att skapa en annan giltig signatur med en signatur och en publik nyckel.
2. chosen message attack: Det är inte möjligt att skapa en ny giltig signatur med en publik nyckel, även med en signatur för ett visst meddelande.
3. side-channel attack: Säkerheten är hög eftersom nya slumpmässiga värden och pseudorandoma värden härledda från meddelandet används kontinuerligt vid signering.
4. domain separation: Genom att använda olika seeds för olika parametrar, förhindras återkommande säkerhetsproblem.

Kod

Låt mig visa ett enkelt exempel i Go.
I det här exemplet användes mldsa från 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    // Skapar nycklar med mldsa44 specifikationen.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Skapar en signatur.
22    // En sak att notera är att som av den 22 december 2024 så uppstår ett fel om det inte är 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    // Verifierar genom att anropa den publika nyckelns scheme.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Signaturvärdet är för långt och har utelämnats. Om du vill se hela värdet, prova att köra det på playground.

Även om det är base64-kodat så är det lite betungande att 3228 byte genereras.
Jag antar att det är lite betungande att tänka på att vi kanske snart måste utbyta den här storleken på signaturer som skydd mot kvantdatorer...

MLKEM

Struktur

MLKEM är en nyckelinkapslingsmekanism (Key Encapsulation Mechanism). KEM är en algoritm som möjliggör skapandet av en delad nyckel mellan två parter med hjälp av publik nyckelkryptering. MLKEM:s nyckelutbytesmekanism genomgår följande steg:

1. Nyckelinkapsling: Avsändaren skapar ett krypterat meddelande (cipher text) och en delad nyckel med hjälp av mottagarens publika nyckel. Det krypterade meddelandet överförs initialt till mottagaren för användning.
2. Nyckeldekapsling: Mottagaren extraherar den delade nyckeln från det krypterade meddelandet med hjälp av sin privata nyckel.

Det finns totalt tre parametrar för MLKEM. Det finns MLKEM-512, MLKEM-768 och MLKEM-1024, där lägre siffror ger kortare nycklar och krypterad text, och högre siffror ger längre nycklar och krypterad text, samt en högre säkerhetsnivå.

Kod

MLKEM kommer att läggas till i go 1.24, så vi har använt go 1.24rc1 som är tillgängligt för tillfället.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Skapar mottagarens PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM använder termen EncapsulationKey istället för PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // För att enkelt visa att nycklar kan extraheras och återanvändas med Bytes() och NewEncapsulationKeyX, har vi duplicerat den.
20    // I praktiken kan man se det som att avsändaren konverterar den offentliga EncapsulationKey som mottagaren publicerat till ett objekt.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Med Encapsulate skapar avsändaren krypterad text och delad nyckel.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // För att visa hur mottagarens privata nyckel lagras och hämtas, har vi avsiktligen duplicerat den.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Mottagaren använder den privata nyckeln för att dekapsulera den krypterade texten och generera en annan delad nyckel.
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=

Som vi kan se genereras en delad nyckel av samma storlek!

Den här koden kan även kontrolleras på playground.

Slutsats

Specifikationerna, säkerhetsnivåerna och storleken på privata nycklar, publika nycklar, signaturer och chiffertext för varje algoritm kan sammanfattas enligt följande. Varje algoritm har en betydande storlek, vilket är passande för namnet PQC.

Med dessa algoritmer hoppas vi att vi kan använda internet på ett säkert sätt även med kvantdatorer. Det är dock oundvikligt att det kommer att krävas mer beräkning på grund av de relativt stora nyckel- och signatur-/chiffertextstorlekarna.

Ändå är varje algoritm effektivt implementerad i Go, så jag hoppas att den aktivt kommer att användas för att skydda er säkerhet på lämpliga platser!