Опит с използването на MLDSA и MLKEM в Go

Преглед

Предистория

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

MLDSA и MLKEM

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

Криптографията, базирана на решетки, както подсказва самото название, е криптографска система, основана на трудността на математически задачи върху решетки. Нямам задълбочени математически познания по този въпрос, но накратко може да се каже, че тя представлява задачата за решаване на линейни уравнения с шум в модулна решетка: 모듈 격자에서 노이즈가 있는 선형 방정식을 푸는 문제. Трудно е да се прецени колко сложна е тази задача, но се твърди, че такива задачи са достатъчно трудни, за да не могат да бъдат решени дори от квантови компютри.

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    // Трябва да се обърне внимание, че към версията от 22 декември 2024 г. при стойност различна от 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    // Извиква scheme на публичния ключ за проверка.
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 език предлага ефективна реализация на всеки от алгоритмите, и се надяваме те да бъдат активно използвани на подходящите места за защита на вашата сигурност!