Опыт использования MLDSA и MLKEM в языке Go

Обзор

Предпосылки

Довольно долгое время высокая вычислительная мощность квантовых компьютеров воспринималась как угроза существующим криптографическим системам. Это связано с тем, что такие существующие системы, как RSA или ECC, могут быть взломаны из-за вычислительных возможностей квантовых компьютеров. Однако несколько лет назад концепция квантовых компьютеров стала более осязаемой, и начались исследования и разработка альтернативных решений, а NIST приступил к стандартизации PQC (постквантовой криптографии).

MLDSA и MLKEM

В конечном итоге NIST в августе 2024 года принял 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    // Вызываем схему публичного ключа для проверки.
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 вместо PublicKey используется термин EncapsulationKey.
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, мы ожидаем, что он будет активно использоваться для защиты вашей безопасности в соответствующих местах!