Użycie MLDSA i MLKEM w języku Go

Przegląd

Tło

Od dłuższego czasu szybkie obliczenia komputerów kwantowych są postrzegane jako zagrożenie dla istniejących systemów kryptograficznych. Wynika to z faktu, że obecne systemy, takie jak RSA czy ECC, mogą zostać złamane przez zdolności obliczeniowe komputerów kwantowych. Jednak od kilku lat, wraz z urealnieniem się koncepcji komputera kwantowego, rozpoczęto badania i rozwój alternatywnych rozwiązań, a NIST prowadził standaryzację PQC (Post-Quantum Cryptography).

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 typ szyfrowania 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. Chociaż nie posiadam obszernej wiedzy matematycznej w tym zakresie, można to podsumować jako problem rozwiązywania równań liniowych z szumem w kratach modułowych. Trudno ocenić, jak trudne to jest, ale mówi się, że problemy te są na tyle skomplikowane, że nawet komputery kwantowe nie są w stanie ich rozwiązać.

MLDSA

Teraz przyjrzymy się MLDSA.

Struktura

MLDSA, jak sugeruje nazwa, jest asymetrycznym algorytmem podpisu, który składa się z następujących 2 etapów:

1. Generowanie podpisu: Użycie klucza prywatnego do wygenerowania podpisu dla wiadomości.
2. Weryfikacja podpisu: Sprawdzenie ważności wygenerowanego podpisu za pomocą klucza publicznego.

MLDSA posiada również 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 z kluczem publicznym, nawet z podpisem dla dowolnej wiadomości.
3. side-channel attack: Bezpieczeństwo jest wysokie dzięki ciągłemu używaniu nowych losowych wartości i pseudolosowych wartości pochodzących z wiadomości podczas podpisywania.
4. domain separation: Zapobiega powtarzającym się problemom bezpieczeństwa poprzez używanie różnych seedów dla różnych parametrów.

Kod

Poniżej przedstawiam prosty przykład kodu w języku Go. W tym przykładzie użyto 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    // Generuje klucze zgodnie 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    // Generuje podpis.
22    // Należy zauważyć, że w obecnej wersji (stan na 22 grudnia 2024 r.) wystąpi błąd, jeśli nie jest to 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    // Wywołuje schemat klucza publicznego w celu weryfikacji.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Wartość podpisu została pominięta ze względu na jej długość. Jeśli chcesz zobaczyć pełny podpis, uruchom kod w playground.

Nawet po zakodowaniu w base64, 3228 bajtów może być nieco uciążliwe. Trochę martwi mnie myśl, że wkrótce będziemy musieli wymieniać się podpisami o takiej wielkości, aby stawić czoła komputerom kwantowym.

MLKEM

Struktura

MLKEM to mechanizm enkapsulacji klucza (Key Encapsulation Mechanism). KEM to algorytm, który umożliwia dwóm stronom wygenerowanie wspólnego klucza przy użyciu kryptografii klucza publicznego. Mechanizm wymiany kluczy MLKEM przebiega w następujący sposób:

1. Enkapsulacja klucza: Nadawca używa klucza publicznego odbiorcy do wygenerowania zaszyfrowanej wiadomości (cipher text) i klucza współdzielonego (shared key). Ta zaszyfrowana wiadomość jest początkowo przekazywana odbiorcy do użycia.
2. Dekapsulacja klucza: Odbiorca używa swojego klucza prywatnego do wyodrębnienia klucza współdzielonego z zaszyfrowanej wiadomości.

MLKEM posiada łącznie 3 parametry. Istnieją MLKEM-512, MLKEM-768, MLKEM-1024. Im mniejsza liczba, tym mniejszy klucz i tekst zaszyfrowany; im większa, tym dłuższy klucz i tekst zaszyfrowany, a także wyższy poziom bezpieczeństwa.

Kod

MLKEM ma zostać dodany w go 1.24, dlatego w obecnej chwili użyto 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    // Generuje PrivateKey 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    // Skopiowano, aby pokazać, że można wyodrębnić i ponownie użyć klucza za pomocą Bytes() i NewEncapsulationKeyX z EncapsulationKey.
20    // Oczywiście w rzeczywistości ten proces polegałby na tym, że nadawca tworzyłby obiekt z klucza EncapsulationKey odbiorcy, który byłby publicznie dostępny 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ółdzielony za pomocą Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Celowo sklonowano klucz prywatny odbiorcy, aby pokazać jego zapisywanie i pobieranie.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Odbiorca używa klucza prywatnego do Decapsulate tekstu zaszyfrowanego, generując kolejny klucz współdzielony.
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 zauważyć, że generowane są klucze współdzielone o tej samej wielkości!

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

Wnioski

Specyfikacje każdego algorytmu, poziomy bezpieczeństwa, rozmiary kluczy prywatnych, kluczy publicznych, podpisów lub tekstów zaszyfrowanych można podsumować następująco. Każdy z nich, zgodnie z nazwą PQC, charakteryzuje się znacznymi rozmiarami.

Dzięki tym algorytmom spodziewamy się, że będziemy mogli korzystać z bezpiecznego Internetu nawet w obliczu komputerów kwantowych, jednak wydaje się, że nieuniknione będzie zwiększenie liczby operacji ze względu na stosunkowo większe rozmiary kluczy i podpisów/tekstów zaszyfrowanych.

Niemniej jednak, w języku Go, algorytmy te są efektywnie zaimplementowane, dlatego mamy nadzieję, że będą aktywnie wykorzystywane w odpowiednich miejscach do ochrony Państwa bezpieczeństwa!