Použití MLDSA a MLKEM v jazyce Go

Přehled

Pozadí

Již poměrně dlouho je rychlý výpočet kvantových počítačů vnímán jako hrozba pro stávající kryptografické systémy. Stávající systémy jako RSA nebo ECC mohou být kvůli výpočetním schopnostem kvantových počítačů dešifrovány. Nicméně, s postupnou vizualizací konceptu kvantových počítačů před několika lety, začaly být zkoumány a vyvíjeny alternativy, a NIST provedl standardizaci PQC (Post-Quantum Cryptography).

MLDSA a MLKEM

Nakonec NIST v srpnu 2024 schválil jako standardy MLKEM a MLDSA, které jsou založeny na CRYSTALS-Kyber a CRYSTALS-Dilithium. Oba algoritmy fungují na základě problému MLWE (Module Learning with Errors). Tento formát se označuje jako kryptografie založená na mřížkách.

Kryptografie založená na mřížkách je, jak název napovídá, kryptografický systém založený na obtížnosti matematických problémů na mřížce. Nemám hluboké matematické znalosti o této problematice, ale v jedné větě to lze shrnout jako problém řešení lineárních rovnic s šumem v modulární mřížce. Jak obtížné to je, si nedovedu představit, ale říká se, že tyto problémy jsou natolik obtížné, že je nelze vyřešit ani pomocí kvantových počítačů.

MLDSA

Nejprve se tedy podívejme na MLDSA.

Struktura

MLDSA je, jak název napovídá, asymetrický podpisový algoritmus, který se skládá ze dvou kroků:

1. Vytvoření podpisu: Vytvoření podpisu pro zprávu pomocí soukromého klíče.
2. Ověření podpisu: Ověření platnosti vytvořeného podpisu pomocí veřejného klíče.

A MLDSA má následující 4 charakteristiky:

1. silná existenční nepadělatelnost (strong existential unforgeability): Z jednoho podpisu a veřejného klíče nelze vytvořit jiný platný podpis.
2. útok zvolenou zprávou (chosen message attack): Pomocí podpisu pro libovolnou zprávu a veřejného klíče nelze vytvořit nový platný podpis.
3. útok postranním kanálem (side-channel attack): Je vysoce zabezpečený, protože při podepisování se neustále používají nové náhodné hodnoty a pseudo-náhodné hodnoty odvozené ze zprávy.
4. oddělení domény (domain separation): Zabraňuje opakovaným bezpečnostním problémům tím, že používá různá semena pro různé parametry.

Kód

Nyní vám ukážu jednoduchý příklad kódu v jazyce Go.
V tomto příkladu jsem použil 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 klíče pomocí specifikace 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    // Je třeba poznamenat, že k 22. prosinci 2024 se na základě aktuální verze objeví chyba, pokud crypto.Hash(0) není použito.
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    // Ověří pomocí schématu veřejného klíče.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Hodnota podpisu je příliš dlouhá, proto byla vynechána. Pokud chcete vidět celý text, zkuste jej spustit v playground.

I když je zakódován pomocí base64, 3228 bajtů je trochu obtížné.
Je trochu zatěžující si myslet, že brzy budeme muset vyměňovat podpisy této velikosti, které budou odolávat kvantovým počítačům.

MLKEM

Struktura

MLKEM je mechanismus zapouzdření klíčů (Key Encapsulation Mechanism). KEM je algoritmus, který umožňuje dvěma stranám generovat sdílený klíč pomocí kryptografie s veřejným klíčem. Mechanismus výměny klíčů MLKEM probíhá následujícím způsobem:

1. Zapouzdření klíče: Odesílatel vygeneruje šifrovanou zprávu (cipher text) a sdílený klíč pomocí veřejného klíče příjemce. Tato šifrovaná zpráva je zpočátku doručena příjemci k použití.
2. Dekapsulace klíče: Příjemce extrahuje sdílený klíč ze šifrované zprávy pomocí svého soukromého klíče.

MLKEM má celkem 3 parametry. Existují MLKEM-512, MLKEM-768 a MLKEM-1024. Čím menší číslo, tím menší klíč a šifrovací text a čím větší číslo, tím delší klíč a šifrovací text a tím vyšší úroveň zabezpečení.

Kód

MLKEM bude přidán v go 1.24, takže jsme použili go 1.24rc1, který je k dispozici v současné době.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Vygeneruje PrivateKey příjemce.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM používá termín EncapsulationKey místo PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Jednoduše jsem zkopíroval, abych ukázal, že klíč lze extrahovat a znovu použít pomocí EncapsulationKey.Bytes() a NewEncapsulationKeyX.
20    // Samozřejmě, pokud se používá v praxi, lze tento proces považovat za proces, kdy odesílatel vytváří objekt z EncapsulationKey klíče příjemce, který byl dříve zveřejněn v textové podobě.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Encapsulate vygeneruje šifrovací text a sdílený klíč pro odesílatele.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Úmyslně jsem ho zkopíroval, abych ukázal, jak uložit a načíst soukromý klíč příjemce.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Příjemce dekapituluje šifrovací text pomocí soukromého klíče a vygeneruje další sdílený klíč.
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ýsledkem je, že můžeme vidět, že se generuje sdílený klíč stejné velikosti!

Tento kód si můžete prohlédnout také v playground.

Závěr

Specifikace, úroveň zabezpečení a velikost soukromého klíče, veřejného klíče, podpisu nebo šifrovacího textu jednotlivých algoritmů lze shrnout následovně. Každý z nich se může pochlubit velkými rozměry, které odpovídají jejich označení PQC.

Doufáme, že s těmito algoritmy budeme moci používat internet, který je dostatečně bezpečný i na kvantových počítačích, ale zdá se nevyhnutelné, že bude zapotřebí více výpočtů kvůli relativně větším klíčům a velikosti podpisu/šifrovacího textu.

I přesto doufám, že Go jazyk, ve kterém jsou jednotlivé algoritmy efektivně implementovány, bude aktivně využíván k ochraně vaší bezpečnosti na příslušných místech!