Използване на MLDSA и MLKEM в езика Go

Общ преглед

Предистория

От доста време бързата изчислителна мощ на квантовите компютри се възприема като заплаха за съществуващите криптографски системи. Това е така, защото съществуващите системи като RSA или ECC могат да бъдат дешифрирани поради тази изчислителна способност на квантовите компютри. Въпреки това, тъй като концепцията за квантовите компютри започна да става видима преди няколко години, започнаха да се проучват и разработват алтернативи, а NIST провежда стандартизация на PQC (Quantum-Resistant Cryptography).

MLDSA и MLKEM

В крайна сметка NIST прие MLKEM и MLDSA, базирани на CRYSTALS-Kyber и CRYSTALS-Dilithium, като стандарти през август 2024 г. Двата алгоритъма функционират въз основа на проблема MLWE (Module Learning with Errors). Ние наричаме този формат криптография, базирана на решетки (lattice-based cryptography).

Криптографията, базирана на решетки, както подсказва името, е криптографска система, основана на трудността на математически проблем върху решетка. Аз също нямам задълбочени математически познания по този въпрос, но обобщено в едно изречение, това е проблемът за решаване на линейни уравнения с шум в модулната решетка. Не е ясно колко е трудно, но се твърди, че този проблем е толкова труден, че не може да бъде решен дори от квантови компютри.

MLDSA

Сега нека разгледаме MLDSA.

Структура

MLDSA, както може да се види от името, е асиметричен алгоритъм за подписване, който преминава през следните 2 етапа:

1. Генериране на подпис: Използване на частния ключ за генериране на подпис за съобщението
2. Проверка на подпис: Използване на публичния ключ за потвърждаване на валидността на генерирания подпис

И MLDSA има следните 3 характеристики:

1. strong existential unforgeability (силна екзистенциална неподправяемост): Не може да бъде генериран друг валиден подпис с един подпис и публичен ключ.
2. chosen message attack (атака с избрано съобщение): Не може да бъде генериран нов валиден подпис с публичния ключ, дори и със подпис за което и да е съобщение.
3. side-channel attack (атака по страничен канал): Сигурността е висока чрез постоянно използване на нови случайни стойности и псевдослучайни стойности, получени от съобщението, по време на подписването.
4. domain separation (разделяне на домейна): Предотвратява повтарящи се проблеми със сигурността, като изисква използването на различни seed-ове за различни параметри.

Код

Сега ще ви покажа прост примерен код на езика Go. В този пример е използван mldsa от 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    // Генерира ключове със спецификацията 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    // Генерира подпис.
22    // Едно нещо, което трябва да се отбележи, е, че ако не е crypto.Hash(0) с текущата версия към 22 декември 2024 г., възниква грешка.
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    // Извиква схемата на публичния ключ, за да извърши проверката.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Стойността на подписа е съкратена, тъй като е твърде дълга. Ако искате да видите пълния текст, изпълнете го в playground.

Дори и да е кодирано с base64, получаването на 3228 байта може да е малко обременяващо. Малко е притеснително да мислим, че може да се наложи да обменяме този размер на подпис, за да се противопоставим на квантовите компютри в близко бъдеще.

MLKEM

Структура

MLKEM е Механизъм за капсулиране на ключ (Key Encapsulation Mechanism). KEM е алгоритъм, който позволява генерирането на споделен ключ между две страни, използвайки криптография с публичен ключ. Механизмът за обмен на ключове на MLKEM преминава през следния процес:

1. Капсулиране на ключ: Подателят използва публичния ключ на получателя, за да генерира криптирано съобщение (cipher text) и споделен ключ (shared key). Това криптирано съобщение първоначално се предава на получателя за използване.
2. Декапсулиране на ключ: Получателят използва своя частен ключ, за да извлече споделения ключ от криптираното съобщение.

В MLKEM има общо 3 параметъра. Съществуват MLKEM-512, MLKEM-768, MLKEM-1024, като по-малкият параметър води до по-малък ключ и криптиран текст, а по-големият води до по-дълъг ключ и криптиран текст, както и по-високо ниво на сигурност.

Код

Тъй като MLKEM се очаква да бъде добавен в Go 1.24, е използван Go 1.24rc1, който може да се използва към момента.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Генерира PrivateKey на получателя.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // В MLKEM се използва терминът EncapsulationKey, а не PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Клонирахме ключа, за да покажем, че може да бъде извлечен и използван отново с Bytes() на EncapsulationKey и NewEncapsulationKeyX.
20    // Разбира се, ако се използва в реалността, този процес може да се разглежда като процес, при който подателят създава обект от EncapsulationKey на получателя, който е бил публично достъпен като текст.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Подателят генерира криптиран текст и споделен ключ чрез Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Умишлено клонирахме ключа на получателя, за да покажем запазването и извличането на частния ключ.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Получателят използва частния си ключ, за да Decapsulate криптирания текст и генерира друг споделен ключ.
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=

В резултат на това можем да потвърдим, че се генерират споделени ключове с еднакъв размер!

Този код може да бъде проверен и в playground.

Заключение

Спецификациите на всеки алгоритъм, нивото на сигурност и размерите на частния ключ, публичния ключ, подписа или криптирания текст могат да бъдат обобщени по следния начин. Всеки от тях може да се похвали със значителен размер, който е достоен за името PQC.

Очакваме, че чрез тези алгоритми ще можем да използваме интернет, който е достатъчно сигурен дори срещу квантови компютри, но изглежда неизбежно, че ще има повече изчисления поради относително увеличения размер на ключовете и подписите/криптираните текстове.

Въпреки това, тъй като езикът Go ефективно имплементира всеки алгоритъм, очакваме те да бъдат активно използвани за защита на вашата сигурност на подходящи места!