Zastosowanie MLDSA i MLKEM w języku Go

Przegląd

Tło

Już od dłuższego czasu szybkie obliczenia komputerów kwantowych są postrzegane jako zagrożenie dla istniejących systemów szyfrowania. Istnieje bowiem możliwość, że istniejące algorytmy, takie jak RSA czy ECC, zostaną rozszyfrowane z powodu zdolności obliczeniowych komputerów kwantowych. Jednakże, gdy wiele lat temu zaczęła nabierać realnych kształtów koncepcja komputera kwantowego, rozpoczęto badania i rozwój alternatywnych rozwiązań, a NIST rozpoczął proces standaryzacji PQC (kryptografii odpornej na ataki kwantowe).

MLDSA i MLKEM

Ostatecznie w sierpniu 2024 roku NIST przyjął MLKEM i MLDSA, oparte na CRYSTALS-Kyber i CRYSTALS-Dilithium, jako standardy. Oba algorytmy działają w oparciu o problem MLWE (Module Learning with Errors). Ten format nazywamy kryptografią opartą na kratach.

Kryptografia oparta na kratach, jak sama nazwa wskazuje, jest systemem kryptograficznym opartym na trudności problemów matematycznych na kratach. Nie mam dogłębnej wiedzy matematycznej na ten temat, ale w jednym zdaniu można to podsumować jako problem rozwiązywania zaszumionych równań liniowych w module kratowym. Nie mam pojęcia, jak trudne to jest, ale mówi się, że ten problem jest tak trudny, że nie można go rozwiązać nawet za pomocą komputerów kwantowych.

MLDSA

Zacznijmy od omówienia MLDSA.

Struktura

MLDSA, jak sama nazwa wskazuje, jest algorytmem podpisu asymetrycznego, który przechodzi przez łącznie 2 etapy.

1. Generowanie podpisu: generowanie podpisu dla wiadomości przy użyciu klucza prywatnego
2. Weryfikacja podpisu: sprawdzanie ważności wygenerowanego podpisu za pomocą klucza publicznego

Ponadto MLDSA ma następujące 3 cechy:

1. strong existential unforgeability: nie można wygenerować innego ważnego podpisu z jednego podpisu i klucza publicznego.
2. chosen message attack: nie można wygenerować nowego ważnego podpisu za pomocą klucza publicznego z podpisem dla dowolnej wiadomości.
3. side-channel attack: bezpieczeństwo jest wysokie dzięki ciągłemu wykorzystywaniu nowej wartości losowej i pseudolosowej wartości pochodzącej z wiadomości podczas podpisywania.
4. domain separation: zapobiega powtarzającym się problemom z bezpieczeństwem poprzez używanie różnych seedów dla różnych parametrów.

Kod

Teraz pokażę prosty przykładowy kod w języku Go. W tym przykładzie użyłem 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    // Generowanie klucza ze specyfikacją 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    // Generowanie podpisu.
22    // Należy pamiętać, że według stanu na dzień 22 grudnia 2024 r., błąd wystąpi, jeśli nie użyje się 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    // Weryfikacja poprzez wywołanie schematu klucza publicznego.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Wartość podpisu jest zbyt długa, więc ją pominąłem. Jeśli chcesz zobaczyć całość, uruchom ją w playground.

Mimo że jest zakodowana w base64, 3228 bajtów to trochę dużo. Pomyślcie, że być może wkrótce będziemy musieli przesyłać podpisy o tej wielkości, aby chronić się przed komputerami kwantowymi.

MLKEM

Struktura

MLKEM to mechanizm hermetyzacji kluczy (Key Encapsulation Mechanism). KEM to algorytm, który umożliwia generowanie klucza wspólnego między dwiema stronami przy użyciu szyfrowania kluczem publicznym. Mechanizm wymiany kluczy MLKEM przebiega w następujący sposób:

1. Hermetyzacja klucza: nadawca używa klucza publicznego odbiorcy, aby wygenerować zaszyfrowaną wiadomość (cipher text) i klucz wspólny (shared key). Ta zaszyfrowana wiadomość jest początkowo dostarczana odbiorcy, aby mógł z niej korzystać.
2. Dehermetyzacja klucza: odbiorca używa swojego klucza prywatnego do wyodrębnienia klucza wspólnego z zaszyfrowanej wiadomości.

W MLKEM istnieją łącznie 3 parametry. Istnieją MLKEM-512, MLKEM-768 i MLKEM-1024, gdzie im mniejsza liczba, tym mniejsze klucze i tekst zaszyfrowany, a im większa, tym dłuższe klucze i tekst zaszyfrowany, a poziom bezpieczeństwa jest wyższy.

Kod

MLKEM zostanie dodany w go 1.24, więc na chwilę obecną użyłem go 1.24rc1, który jest dostępny.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Generowanie klucza prywatnego odbiorcy.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // W MLKEM używa się terminu EncapsulationKey zamiast PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Skopiowałem go, aby pokazać, że można go wyodrębnić i ponownie użyć za pomocą Bytes() i NewEncapsulationKeyX EncapsulationKey.
20    // Oczywiście w rzeczywistości ten proces to proces tworzenia obiektu przez nadawcę z EncapsulationKey odbiorcy, który był publicznie udostępniony jako tekst.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Nadawca generuje tekst zaszyfrowany i klucz wspólny za pomocą Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Specjalnie skopiowałem, aby pokazać, jak zapisać i pobrać klucz prywatny odbiorcy.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Odbiorca generuje kolejny klucz wspólny poprzez Decapsulate tekstu zaszyfrowanego przy użyciu klucza prywatnego.
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=

W rezultacie możemy zobaczyć, że generowany jest klucz wspólny o tej samej wielkości!

Ten kod można również znaleźć w playground.

Wniosek

Specyfikacje każdego algorytmu, poziom bezpieczeństwa, rozmiary kluczy prywatnych, kluczy publicznych, podpisów i szyfrogramów można podsumować w następujący sposób. Każdy z nich szczyci się dużymi rozmiarami, co nie przynosi ujmy nazwie PQC.

Mamy nadzieję, że dzięki tym algorytmom będziemy mogli korzystać z bezpiecznego Internetu nawet na komputerach kwantowych, ale wydaje się nieuniknione, że będzie więcej obliczeń ze względu na stosunkowo większe rozmiary kluczy i podpisów/szyfrogramów.

Mimo to, ponieważ w języku Go każdy algorytm jest skutecznie zaimplementowany, mamy nadzieję, że będzie aktywnie wykorzystywany do ochrony waszego bezpieczeństwa we właściwym miejscu!