Použitie MLDSA a MLKEM v jazyku Go

Prehľad

Pozadie

Už dosť dlho sa rýchle výpočty kvantových počítačov považujú za hrozbu pre existujúce kryptografické systémy. Existujúce systémy, ako RSA alebo ECC, by mohli byť dešifrované kvôli výpočtovým schopnostiam kvantových počítačov. Avšak, keď sa koncept kvantových počítačov pred niekoľkými rokmi začal stávať reálnejším, začali sa skúmať a vyvíjať alternatívy a NIST (National Institute of Standards and Technology) začal so štandardizáciou PQC (Post-Quantum Cryptography).

MLDSA a MLKEM

Nakoniec NIST v auguste 2024 prijal MLKEM a MLDSA založené na CRYSTALS-Kyber a CRYSTALS-Dilithium ako štandardy. Oba algoritmy fungujú na základe problému MLWE (Module Learning with Errors). Tento formát nazývame kryptografiou založenou na mriežke (lattice-based cryptography).

Kryptografia založená na mriežke je, ako už názov napovedá, kryptografický systém založený na náročnosti matematických problémov na mriežke. Nemám hlboké matematické znalosti o tejto téme, ale v jednej vete by sa to dalo zhrnúť ako problém riešenia lineárnych rovníc so šumom v modulovej mriežke. Netuším, aké je to ťažké, ale hovorí sa, že tieto problémy sú také ťažké, že ich nedokážu vyriešiť ani kvantové počítače.

MLDSA

Takže sa najprv pozrime na MLDSA.

Konfigurácia

MLDSA je, ako už názov napovedá, asymetrický podpisový algoritmus, ktorý prechádza celkovo 2 fázami.

1. Generovanie podpisu: Vygenerovanie podpisu pre správu pomocou súkromného kľúča.
2. Overenie podpisu: Overenie platnosti vygenerovaného podpisu pomocou verejného kľúča.

A MLDSA má nasledujúce 3 charakteristiky.

1. strong existential unforgeability: S jedným podpisom a verejným kľúčom nie je možné vygenerovať ďalší platný podpis.
2. chosen message attack: S podpisom pre ľubovoľnú správu nie je možné vygenerovať nový platný podpis s verejným kľúčom.
3. side-channel attack: Bezpečnosť je vysoká, pretože pri podpisovaní sa neustále používajú nové náhodné hodnoty a pseudo-náhodné hodnoty odvodené zo správy.
4. domain separation: Predchádzanie opakovaným bezpečnostným problémom používaním rôznych seedov pre rôzne parametre.

Kód

Teraz si ukážeme jednoduchý príklad kódu v jazyku Go. V tomto príklade sme použili mldsa z 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    // Vygeneruje kľúč so špecifikáciou mldsa44.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Vygeneruje podpis.
22    // Jedna vec, ktorú treba poznamenať, je, že podľa verzie z 22. decembra 2024 sa vyskytne chyba, ak to nie je 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    // Zavolá schému verejného kľúča na overenie.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Hodnota podpisu bola vynechaná, pretože je príliš dlhá. Ak si chcete pozrieť celý text, spustite ho na playground.

Hoci je zakódovaný v base64, 3228 bajtov je trochu zaťažujúce. Je trochu zaťažujúce si pomyslieť, že čoskoro budeme musieť vymieňať tieto veľkosti podpisov na ochranu pred kvantovými počítačmi.

MLKEM

Konfigurácia

MLKEM je mechanizmus zapuzdrenia kľúča (Key Encapsulation Mechanism). KEM je algoritmus, ktorý umožňuje dvom stranám vygenerovať zdieľaný kľúč pomocou šifrovania verejným kľúčom. Mechanizmus výmeny kľúčov MLKEM prechádza nasledujúcim procesom.

1. Zapuzdrenie kľúča: Odosielateľ vygeneruje šifrovanú správu (cipher text) a zdieľaný kľúč pomocou verejného kľúča príjemcu. Táto šifrovaná správa sa pôvodne odovzdáva príjemcovi na použitie.
2. Rozbalenie kľúča: Príjemca extrahuje zdieľaný kľúč zo šifrovanej správy pomocou svojho súkromného kľúča.

V MLKEM existujú celkovo 3 parametre. Existujú MLKEM-512, MLKEM-768 a MLKEM-1024. Čím menšie číslo, tým menší kľúč a šifrovací text a čím väčšie číslo, tým dlhší kľúč a šifrovací text a vyššia úroveň zabezpečenia.

Kód

MLKEM má byť pridaný do go 1.24, takže sme použili go 1.24rc1, ktorý je dostupný v súčasnosti.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Vygeneruje PrivateKey príjemcu.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // V MLKEM sa používa termín EncapsulationKey namiesto PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Jednoducho sme to naklonovali, aby sme ukázali, že kľúč je možné extrahovať a znovu použiť pomocou Bytes() a NewEncapsulationKeyX z EncapsulationKey.
20    // Samozrejme, v reálnom svete je tento proces procesom, v ktorom odosielateľ vytvára objekt z EncapsulationKey kľúča príjemcu, ktorý bol zverejnený v texte.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Odosielateľ vygeneruje šifrovací text a zdieľaný kľúč pomocou Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Úmyselne sme to naklonovali, aby sme ukázali uloženie a načítanie súkromného kľúča príjemcu.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Príjemca pomocou svojho súkromného kľúča Decapsulate šifrovací text a vygeneruje ďalší zdieľaný kľúč.
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=

Výsledkom je, že sa generujú zdieľané kľúče rovnakej veľkosti!

Tento kód si môžete pozrieť aj na playground.

Záver

Špecifikácie každého algoritmu, úroveň zabezpečenia a veľkosť súkromných kľúčov, verejných kľúčov, podpisov a šifrovacích textov sú zhrnuté nasledovne. Každý z nich sa pýši veľkými rozmermi, hodnými mena PQC.

Dúfame, že s týmito algoritmami budeme môcť používať internet, ktorý je dostatočne bezpečný aj na kvantových počítačoch, ale zdá sa, že sa nedá vyhnúť väčšiemu počtu výpočtov kvôli relatívne väčším kľúčom a podpisom/veľkostiam šifrovacích textov.

Napriek tomu, keďže každý algoritmus je efektívne implementovaný v jazyku Go, dúfame, že sa aktívne využije na ochranu vášho zabezpečenia na správnych miestach!