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

Обзор

Предпосылки

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

MLDSA и MLKEM

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

Криптография на основе решёток, как следует из названия, представляет собой криптографическую систему, основанную на трудности математических задач на решётках. Я также не обладаю глубокими математическими знаниями в этой области, но, если кратко, это называется задача решения линейных уравнений с шумом в модульной решётке. Насколько она сложна, мне трудно себе представить, но, как говорят, такие задачи настолько трудны, что их не могут решить даже квантовые компьютеры.

MLDSA

Итак, сначала давайте разберём MLDSA.

Структура

Как видно из названия, MLDSA является алгоритмом асимметричной подписи и включает в себя следующие два этапа.

1. Создание подписи: создание подписи для сообщения с использованием закрытого ключа
2. Проверка подписи: подтверждение действительности созданной подписи с помощью открытого ключа

Кроме того, MLDSA обладает следующими 4 свойствами.

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    // Для простоты ключ EncapsulationKey извлекается через Bytes() и восстанавливается через 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 каждый алгоритм эффективно реализован, мы надеемся, что он будет активно использоваться в подходящих местах для защиты вашей безопасности!