Перед прочтением
Данный алгоритм реализовывался как часть сетевого протокола, но из него было исключено много лишнего, чтобы дать возможность для внедрения в различные системы без привязки к архитектуре.
Далее в статье представлен алгоритм QuarkDash включая реализацию библиотеки на языке TypeScript в качестве основы для клиент-серверных веб приложений. Сама реализация библиотеки есть на GitHub и NPM, для тех, кто хочет пропустить детали и покопаться на практике.
Алгоритм QuarkDash (или если хотите, протокол) - сочетает пост‑квантовый обмен ключами на основе Ring‑LWE, быстрый потоковый шифр на выбор (ChaCha20 или Gimli), квантово‑устойчивую KDF и MAC на базе SHAKE256, а также встроенные механизмы защиты от replay‑атак и timing‑атак.
Введение
С развитием технологий, постройкой огромных дата-центов, а также маячащими на горизонте квантовыми компьютерами - многие широко используемые криптографические алгоритмы (RSA, ECC, DSA) становятся уязвимыми благодаря алгоритмам Шора и Гровера. Как результат - криптографы разрабатывают новые пост-квантовые алгоритмы (PQC).
В ответ на это сообщество криптографов разрабатывает пост‑квантовые алгоритмы (PQC). Только вот, внедрение PQC в реальные системы приносит свои вызовы: вопросы с производительностью, размером ключей, совместимостью.
Алгоритм QuantDash старается решить эти проблемы, предлагая гибридный подход: пост‑квантовую работу с ключами (Ring‑LWE) + высокопроизводительное симметричное шифрование.
Выбор криптографических примитивов
Пост‑квантовый обмен ключами: Ring‑LWE
Ring‑LWE (Обучение с ошибками в кольце) – один из самых изученных алгоритмов, который прошел в финалы конкурса NIST PQC. Он основан на сложности поиска ошибок в кольце целых полиномов.
В алгоритме QuarkDash используются следующие параметры:
Размер кольца
N = 256Модуль
Q = 7681(простое число, поддерживающее быстрое NTT)Примитивный корень
ω = 7
Такие параметры обеспечивают 128‑битную пост‑квантовую безопасность при относительно небольших ключах (публичный ключ в районе ~2 КБ, а приватный ~1 КБ). Умножение полиномов реализовано через NTT (Number Theoretic Transform) со сложностью O(N log N), что делает обмен ключами достаточно быстрым (~8 мс на среднем современном CPU).
Симметричное шифрование: выбор между ChaCha20 и Gimli
Тут следует сделать сноску. Оба шифра работают классно, однако работают на разные цели - один больше для кросс-платформенных решений на уровне софта, а другой отлично ложится на IoT устройства. Поскольку протокол может предполагать общение между разными типами устройств - в моей реализации включены оба шифра.
Для шифрования данных после установки сессии QuarkDash основывается на двух потоковых шифрах:
ChaCha20 – работающий на стандарте RFC-7539. Обладает высокой производительностью, устойчив к timing‑атакам при правильной реализации. Использует 20 раундов вместе с 256‑битный ключом, 12‑байтным nonce. Скорость в программной реализации выше, чем у AES без аппаратного ускорения.
Gimli – другой интересный и легковесный шифр, разработанный для устройств умного дома (IoT). В нём же 24 раунда, 384‑битное состояние шифра, которые обеспечивают 256‑битную безопасность. Gimli быстрее ChaCha20 на 32‑битных архитектурах и требует меньше кода.
Квантово‑устойчивые KDF и MAC с использованием SHAKE-256 хеширования
Для ключей и аутентификации используется алгоритм SHAKE-256 – расширяемая хэш‑функция на основе губки кечак, устойчивая к квантовым атакам.
Небольшая сноска. В моей реализации на TypeScript, поскольку встроенной поддержки SHAKE-256 в Web Crypto API нет, я эмулирую его через многократный вызов SHA‑256 в режиме счётчика (чего в целом достаточно для целей библиотеки).
Работа с ключами сводится к двум операциям:
KDF (Key Derivation Function): которая принимает общий секретный ключ (32 байта), соль (32 байта) и мета-данные, а возвращает 64 байта информации для ключа.
MAC: вычисляется как
SHAKE256(macKey || data, 32). В нём используется временное константное сравнение.
Защита от replay‑атак
Для справки: Replay-атака (атака повторного воспроизведения) — это тип кибератаки, при которой злоумышленник перехватывает легитимные данные (например, пароль, куки, банковскую транзакцию), передаваемые по сети, и позже повторно отправляет их системе, выдавая себя за законного пользователя. Это позволяет обойти аутентификацию, не расшифровывая данные.
В QuarkDash для решения данного типа атаки я предлагаю, чтобы каждое зашифрованное сообщение содержало 12‑байтный заголовок, включающий в себя: timestamp (8 байт, unix‑время в миллисекундах) и sequence number (4 байта).
При дешифровании проверяется:
Отклонение временной метки (timestamp) не превышает заданного в системе (по умолчанию 5 минут).
Sequence number не повторялся (хранится окно последних 1000 пакетов).
Это предотвращает атаки повтора как в пределах сессии, так и через длительное время.
Пошаговый алгоритм работы QuarkDash
Ниже я описал предлагаемый пошаговый алгоритм работы протокола QuarkDash - его реализацию можно посмотреть на TypeScript здесь.
Генерация долговременных ключей (Ring‑LWE)
Выбрать случайный полином
aс коэффициентами изZ_Q.Выбрать малые полиномы
s(секрет) иe(ошибка) с коэффициентами{-1,0,1}.Вычислить
b = a ⊗ s + e(умножение через NTT, сложение по-коэффициентное).Публичный ключ:
(a, b), приватный:s.
Установка сессии (KEM)
Инициатор (например, клиент):
Получает публичный ключ Получателя (например, сервера)
(a, b).Генерирует малые
s', e'.Вычисляет
u = a ⊗ s' + e'(шифрованный текст).Вычисляет
w = b ⊗ s', округляет коэффициенты до битов →sharedSecret.Отправляет
uПолучателю.
Получатель (например, сервер):
Используя свой секрет
s, вычисляетw' = u ⊗ s, округляет → тот жеsharedSecret.
Вывод ключей сессии (KDF)
keyMaterial = SHAKE256(saltsharedSecret"session-key", 64)sessionKey = keyMaterial[0:32]macKey = keyMaterial[32:64]
Шифрование сообщения
Для каждого сообщения:
Сформировать заголовок
header = timestamp (8) || sequence (4).ciphertext = streamCipher.encrypt(plaintext).mac = SHAKE256(macKeyheaderciphertext, 32).Отправить пакет
headerciphertextmac.
Де-шифрование и проверка
Разделить шифрованный пакет на
header,ciphertext,mac.Проверить
mac(константно-временная проверка).Проверить
timestamp(находится во временных пределах).Проверить
sequence(не повторяется номер).plaintext = streamCipher.decrypt(ciphertext)
В целом, вот такая вырисовывается схема работы алгоритма. Несмотря на большое количество шагов, работает быстро, о чем поговорим немного ниже.
Безопасность
Итак, давайте ниже разберем и подытожим концепцию безопасности, которую я заложил в QuarkDash с небольшими пояснениями. В комментариях всегда рад буду обсудить другие возможные реализации и подводные камни.
1. Пост‑квантовая устойчивость
Выбор пал на Ring‑LWE, потому что он пока что не имеет известных квантовых алгоритмов эффективного решения (в отличие от факторизации или дискретного логарифмирования).
SHAKE256 обеспечивает устойчивость к квантовым атакам (в отличие от SHA‑2, который теоретически может быть ослаблен алгоритмом Гровера, но с меньшим эффектом).
Комбинация Ring‑LWE + SHAKE256 даёт защиту на уровне 128‑256 бит против квантовых и классических атак.
2. Защита от атак по сторонним каналам
Все сравнения MAC выполняются за постоянное (константное) время (
constantTimeEqual).Ключи затираются в памяти (
secureZero).Отсутствуют ветвления по секретным данным в критических местах (шифр, KDF, MAC).
3. Forward Secrecy
Каждая сессия использует эфемерный обмен ключами (через KEM). Даже при компрометации долговременного ключа сервера прошлые сессии остаются защищёнными.
4. Защита от Replay-атак
Встроенные временные метки (timestamp) и sequence number делают атаки повтора невозможными в пределах заданного временного окна. Далее теоретически могут быть коллизии.
Таким образом, алгоритм защищает от основных атак при достаточно быстрой скорости работы.
Производительность, бенчмарки и сравнения
Ниже я описал выжимку из проводимых тестов, бенчмарков и сравнений с другими популярными алгоритмами. Следует учесть, что для них использовалось несколько средних машин, среди которых было вычленен средний показатель тестов.
Установка сессии
Операция | QuarkDash (ChaCha20) | QuarkDash (Gimli) | ECDH (P‑256) | RSA‑2048 |
|---|---|---|---|---|
Генерация ключей | 12.3 мс | 12.1 мс | 1.2 мс | 48 мс |
KEM (инкапсуляция) | 8.7 мс | 8.5 мс | 3.4 мс | 42 мс |
KEM (декапсуляция) | 9.2 мс | 9.0 мс | 3.4 мс | 0.1 мс (дешифрование) |
Пропускная способность шифрования
Размер данных | QuarkDash (ChaCha20) | QuarkDash (Gimli) | AES‑256‑GCM | ECIES (P‑256 + AES) |
|---|---|---|---|---|
1 КБ | 125 МБ/с | 132 МБ/с | 117 МБ/с | 10 МБ/с |
1 МБ | 2380 МБ/с | 2630 МБ/с | 1176 МБ/с | 48 МБ/с |
10 МБ | 2450 МБ/с | 2710 МБ/с | 1200 МБ/с | 50 МБ/с |
Примечания:
Для ECDH + AES использована схема ECIES с secp256k1 и AES-256-CTR.
Для RSA – OAEP с ключом 2048 бит, шифрование 1 KB данных (максимальный размер).
Все замеры – среднее из 1000 итераций.
Накладные расходы алгоритма
Размер публичного ключа: ~2 КБ
Размер приватного ключа: ~1 КБ
Оверхед на пакет: 44 байта (12 заголовок + 32 MAC)
Сравнение с другими алгоритмами
Сравнение с AES (симметричное шифрование)
Квантовая устойчивость – AES уязвим к алгоритму Гровера (ускорение перебора в √N).
Встроенный обмен ключами – не требуется предварительного распространения ключей.
Forward secrecy – компрометация долговременного ключа не раскрывает прошлые сессии.
Защита от атак повтором – в AES её нужно реализовывать отдельно.
Быстрее в программной реализации (шифр ChaCha20 быстрее AES без аппаратного ускорения).
В сравнении ECC (асимметричный на эллиптических кривых)
Квантовая устойчивость – алгоритм Шора ломает ECC за полиномиальное время.
Выше производительность для больших сообщений – ECIES шифрует данные через AES, но добавляет накладные расходы на ECDH.
Меньше размер пакета – 44 байта QuarkDash против 61 байта у ECIES.
Проще в реализации – нет необходимости в проверке точек на кривой и защите от атак на подгруппы.
В сравнении с RSA (асимметричный на факторизации)
Квантовая устойчивость – RSA ломается алгоритмом Шора.
Гигантский разрыв в производительности – RSA в 250+ раз медленнее на шифровании, в 1000+ раз на дешифровании.
Отсутствие проблем с padding-ами – RSA требует сложного OAEP, подверженного атакам на оракулы.
Линейное масштабирование – QuarkDash в среднем имеет сложность O(n), RSA – O(n³).
Таблица сравнения
Характеристика | QuarkDash (ChaCha20) | QuarkDash (Gimli) | AES-256-GCM | ECDH/P-256 + AES | RSA-2048 + AES |
|---|---|---|---|---|---|
Тип | Гибридный | Гибридный | Симметричный | Асимметричный (KEX) | Асимметричный |
Квантовая устойчивость | ✅ Ring-LWE | ✅ Ring-LWE | ❌ | ❌ | ❌ |
Скорость шифрования (1 MB) | ~2.4 GB/s | ~2.8 GB/s | ~1.2 GB/s | ~50 MB/s (ECIES) | ~10 MB/s |
Скорость дешифрования | ~2.4 GB/s | ~2.8 GB/s | ~1.2 GB/s | ~50 MB/s | ~1 MB/s |
Установка сессии | ~10-15 ms | ~10-15 ms | pre-shared | ~5 ms | ~50 ms |
Размер публичного ключа | ~2 KB | ~2 KB | N/A | 33 байта | 256 байт |
Размер приватного ключа | ~1 KB | ~1 KB | N/A | 32 байта | 256 байт |
Размер шифротекста (overhead) | 44 байта | 44 байта | 28 байт (GCM) | 61 байт | 256+ байт |
Forward secrecy | ✅ | ✅ | ❌ | ⚠️ | ❌ |
Защита от replay | ✅ встроена | ✅ встроена | ❌ | ❌ | ❌ |
Аутентификация | ✅ MAC (SHAKE256) | ✅ | ✅ (GCM) | ✅ (ECIES) | ❌ |
Устойчивость к timing attacks | ✅ | ✅ | ⚠️ | ⚠️ | ❌ |
Сложность квантового взлома | 2^256 | 2^256 | 2^128 (Grover) | 0 (Shor) | 0 (Shor) |
Таким образом, алгоритм QuarkDash в целом можно использовать в качестве прослойки для realtime приложений или IoT девайсов.
Пример реализации на TypeScript
Ниже описан пример обмена ключами и шифрования с использованием библиотеки на TypeScript.
/* Импортируем нужные модули */ import {CipherType, QuarkDash, QuarkDashUtils} from "../src"; /* Создаем два объекта для примера обмена между клиентом и сервером */ const client = new QuarkDash({ cipher: CipherType.Gimli }); const server = new QuarkDash({ cipher: CipherType.Gimli }); /* Делаем генерацию ключей */ const clientPub = await client.generateKeyPair(); const serverPub = await client.generateKeyPair(); /* Инициализируем сессию и обмениваемся ключами */ const ciphertext = await client.initializeSession(serverPub, true) as Uint8Array; await server.initializeSession(clientPub, false); await server.finalizeSession(ciphertext); /* Теперь можем обменяться сообщениями */ const plain = QuarkDashUtils.textToBytes('Hello QuarkDash 🔒!'); const enc = await client.encrypt(plain); const dec = await server.decrypt(enc); console.log("Decrypted:", QuarkDashUtils.bytesToText(dec));
В целом, этого достаточного в качестве примера простого обмена ключами. Подключая сверху алгоритм сжатия и бинарную упаковку пакетов для дальнейшей отправки по сети - вы можете гарантировать себе устойчивое, безопасное и быстрое соединение даже на мало мощных устройствах.
Заключение
В наше время много устоявшихся алгоритмов, которые прошли проверку временем, однако уже сейчас им на смену выходят разные модификации и вариации, которые будут служить переходной основой для алгоритмов будущего, учитывающие растущие мощности и новые виды атак.
QuarkDash Crypto – реализация алгоритма в виде TypeScript‑библиотеки, объединяющая пост‑квантовый обмен ключами (Ring‑LWE), быстрый потоковый шифр на выбор (ChaCha20 / Gimli) и квантово‑устойчивые KDF / MAC (SHAKE-256) в одном гибридном протоколе.
Она готова к использованию, имеет высокую производительность (до 2.8 ГБ/с), защиту от атак по сторонним каналам и replay‑атак, а также предоставляет простой и расширяемый API.
Буду рад вашим дополнениям и комментариям!
Спасибо за прочтение.
