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

Обзор

Предпосылки

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

MLDSA и MLKEM

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

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

MLDSA

Итак, давайте сначала рассмотрим MLDSA.

Конфигурация

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

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

MLDSA имеет следующие три характеристики:

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. Декапсуляция ключа: получатель использует свой закрытый ключ для извлечения общего ключа из зашифрованного сообщения.

Существует 3 параметра MLKEM. Существуют 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() и NewEncapsulationKeyX EncapsulationKey.
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, мы надеемся, что он будет активно использоваться для защиты вашей безопасности в соответствующих местах!