Решётки – это математические структуры, напоминающие бесконечную сетку точек в пространстве. Представьте парковку, где машины паркуются строго на пересечениях линий – но линии идут не только влево-вправо и вперёд-назад, но и по диагонали под разными углами. В криптографии решётки создают задачи, которые очень трудно решить, даже для суперкомпьютеров. Ключевое свойство: легко «зашифровать» сообщение (найти ближайшую точку решётки), но невероятно сложно «расшифровать» без ключа (найти исходный вектор). Эта «нерешаемая» задача делает алгоритмы на основе решёток, такие как CRYSTALS‑Dilithium и Falcon, устойчивыми к квантовым компьютерам – и именно поэтому Cellframe использует их.
Что такое решётка простыми словами?
Решётка – это множество точек, расположенных в пространстве с регулярным, повторяющимся узором. Самый простой пример – миллиметровка или шахматная доска. Точки существуют только на пересечениях линий. Это двумерная решётка.
В криптографии мы используем решётки в высокоразмерных пространствах – десятках, сотнях или даже тысячах измерений. Визуализировать это невозможно, но математики работают с ним вполне успешно.
Основная идея: решётки связаны с двумя задачами:
- Легкая: зная точку, найти ближайшую точку решётки (это похоже на шифрование).
- Сложная (нерешаемая за разумное время): зная решётку и приближённую точку, найти исходный вектор, который был зашифрован. Эта задача называется LWE (Learning With Errors).
Почему решётки важны для постквантовой криптографии?
Задачи на решётках считаются устойчивыми к атакам квантовых компьютеров. В отличие от факторизации (RSA) или дискретного логарифма (ECDSA), для решёток нет эффективного квантового алгоритма – даже алгоритм Шора не помогает.
| Задача | Классический компьютер | Квантовый компьютер | Используется в |
|---|---|---|---|
| Факторизация (RSA) | Сложно | Легко (Шор) | Старая криптография |
| Дискретный логарифм (ECDSA) | Сложно | Легко (Шор) | Bitcoin, Ethereum |
| Ближайшая точка в решётке (LWE) | Очень сложно | Сложно | Постквантовая криптография |
Именно поэтому NIST выбрал алгоритмы на основе решёток в качестве основных стандартов постквантовой криптографии: CRYSTALS‑Dilithium (ML‑DSA), Falcon (FN‑DSA) и Kyber (ML‑KEM).
Как работает шифрование на основе решёток? (Упрощённый пример)
Представьте, что вы находитесь на огромной парковке с сеткой точек (решёткой). Вы хотите отправить секретное сообщение другу.
- Вы выбираете секретную точку (ключ) – скажем, пересечение третьей строки и пятой линии.
- Вы добавляете крошечную случайную ошибку – например, смещаетесь на 0,3 метра в сторону. Теперь у вас есть «зашумлённая» точка.
- Вы отправляете зашумлённую точку и описание решётки своему другу.
- Ваш друг, зная секретный ключ (исходную точку), может легко убрать шум и прочитать сообщение.
- Атакующий, не знающий ключ, видит только зашумлённую точку и решётку. Чтобы найти исходную точку, ему пришлось бы перебрать все возможные комбинации – больше, чем атомов во Вселенной.
Проблема LWE (Learning With Errors) формализует именно это: зная систему линейных уравнений с малыми ошибками, найти исходное решение. Это сложно даже для квантовых компьютеров.
Какие алгоритмы на основе решёток одобрил NIST?
| Стандарт NIST | Алгоритм | Тип | Размер подписи | Скорость | Использование в Cellframe |
|---|---|---|---|---|---|
| FIPS 204 | CRYSTALS‑Dilithium (ML‑DSA) | Цифровая подпись | ~2–3 КБ | Очень быстро | Основная блокировка блоков |
| FIPS 206 (ожидаемый) | Falcon (FN‑DSA) | Цифровая подпись | ~1,2 КБ | Быстро | Компактные подписи для транзакций |
| FIPS 203 | CRYSTALS‑Kyber (ML‑KEM) | Обмен ключами | ~1 КБ | Быстро | Защищённые каналы связи |
Почему Cellframe выбрал эти алгоритмы? Потому что они:
- Одобрены NIST (надёжны).
- Устойчивы к квантовым атакам (перспективны).
- Достаточно быстры для использования в блокчейне (в отличие, например, от SPHINCS+ с огромными подписями).
- Позволяют обновлять криптографию через идентификаторы алгоритмов (встроено в Cellframe).
Алгоритмы на основе решёток против традиционной криптографии: краткое сравнение
| Характеристика | ECDSA (Bitcoin) | CRYSTALS‑Dilithium (Cellframe) |
|---|---|---|
| Математическая основа | Эллиптические кривые | Решётки (LWE) |
| Устойчивость к квантам? | Нет (ломается алгоритмом Шора) | Да (нет известного квантового алгоритма) |
| Размер подписи | ~100 байт | ~2–3 КБ |
| Скорость проверки | Очень быстро | Быстро |
| Статус NIST | Не стандартизирован (ECDSA устаревает) | Стандартизирован (FIPS 204) |
Компромисс: подписи на основе решёток в 20–30 раз больше, чем ECDSA, поэтому блокчейн должен быть способен их обрабатывать. Cellframe решает эту проблему с помощью двухуровневого шардинга и ядра на C.
Что такое LWE (Learning With Errors) простыми словами?
LWE – это задача, которая звучит так: вам дана система уравнений, но каждое уравнение содержит небольшую неизвестную ошибку. Найдите исходное решение. Звучит просто? На самом деле это чрезвычайно сложно.
Аналогия: представьте, что вы подслушиваете разговор в шумном помещении. Каждое слово искажено случайным статическим шумом. Вы знаете словарь (решётку), но не знаете точно, каков шум. Восстановить исходное предложение без ключа практически невозможно.
Почему LWE считается «квантово-безопасной»? Потому что лучшие известные алгоритмы её решения (как классические, так и квантовые) требуют экспоненциального времени. Даже алгоритм Шора здесь не помогает.
Глоссарий терминов криптографии на основе решёток
| Термин | Определение |
|---|---|
| Решётка | Периодическое множество точек в многомерном пространстве. |
| LWE (Learning With Errors) | Математическая задача: найти решение системы линейных уравнений с малыми ошибками. Считается устойчивой к квантовым атакам. |
| SVP (Shortest Vector Problem) | Найти самый короткий ненулевой вектор в решётке. Лежит в основе многих криптографических систем на решётках. |
| CRYSTALS‑Dilithium | Алгоритм цифровой подписи на основе решёток, стандарт NIST (ML‑DSA). Используется в Cellframe. |
| Falcon | Компактный алгоритм цифровой подписи на основе решёток, ожидаемый стандарт NIST (FN‑DSA). Используется в Cellframe. |
| Kyber | Механизм инкапсуляции ключей на основе решёток, стандарт NIST (ML‑KEM). Используется в Cellframe. |
| Размерность решётки | Количество измерений пространства, в котором определена решётка. Более высокая размерность усложняет задачи. |
| Постквантовая безопасность | Свойство алгоритма оставаться безопасным против атак как со стороны классических, так и квантовых компьютеров. |
Итоги
Решётки – это математическая замена эллиптическим кривым в эпоху квантовых вычислений. Они позволяют строить криптографические системы, которые алгоритм Шора не может взломать. NIST выбрал алгоритмы на основе решёток CRYSTALS‑Dilithium и Falcon в качестве стандартов для постквантовых цифровых подписей.
Cellframe использует именно эти алгоритмы (плюс Kyber для шифрования каналов) и делает это с возможностью обновления криптографии без хардфорков – через идентификаторы алгоритмов. Это делает Cellframe одной из немногих платформ, уже готовой к Q‑day.
Если вы разработчик – изучайте криптографию на основе решёток. Если пользователь – просто знайте, что ваши активы в Cellframe защищены математикой, которую не могут взломать даже квантовые компьютеры.
Top comments (0)