0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: tls, ssh, криптографическая защита информации, rsa, пост-квантовая криптография, квантовый компьютер, агенство стандартизации nist, ipsec, signal, тотальный взлом, задачи на евклидовых решетках, задачи из теории кодирования, задачи на многомерных полиномах, задача вычисления изогении между абелевыми многообразиями, задача нахождения коллизий хэш-функции</p>
1
<p>Теги: tls, ssh, криптографическая защита информации, rsa, пост-квантовая криптография, квантовый компьютер, агенство стандартизации nist, ipsec, signal, тотальный взлом, задачи на евклидовых решетках, задачи из теории кодирования, задачи на многомерных полиномах, задача вычисления изогении между абелевыми многообразиями, задача нахождения коллизий хэш-функции</p>
2
<p>Наверняка, многие, кто так или иначе связан с IT, слышали о том, что квантовый компьютер легко взламывает современные методы криптографии с открытым ключом. Существует множество разрозненных мнений о том, насколько скоро появится квантовый компьютер, способный "взломать" ключи той длины, которой мы пользуемся сегодня - 4096 бит RSA модуль или 256 бит подгруппа для Диффи-Хэллмана.</p>
2
<p>Наверняка, многие, кто так или иначе связан с IT, слышали о том, что квантовый компьютер легко взламывает современные методы криптографии с открытым ключом. Существует множество разрозненных мнений о том, насколько скоро появится квантовый компьютер, способный "взломать" ключи той длины, которой мы пользуемся сегодня - 4096 бит RSA модуль или 256 бит подгруппа для Диффи-Хэллмана.</p>
3
<p>И всё же Агенство стандартизации<a>NIST</a>решило готовить сани летом и в 2018 году запустило<a>конкурс на лучшие пост-квантовые примитивы</a>. С предложенными кандидатами на пост-квантовую эру мы и познакомимся.</p>
3
<p>И всё же Агенство стандартизации<a>NIST</a>решило готовить сани летом и в 2018 году запустило<a>конкурс на лучшие пост-квантовые примитивы</a>. С предложенными кандидатами на пост-квантовую эру мы и познакомимся.</p>
4
<h2>Предисловие</h2>
4
<h2>Предисловие</h2>
5
<p>Современная криптография с открытым ключом (TLS, SSH, IpSec, Signal) основана на сложности факторизации больших чисел (RSA) и/или сложности вычисления дискретного логарифма (Диффи-Хэллман). В 1994 году Шор предложил<a>квантовый алгоритм</a>, решающий обе задачи за полиномиальное (от длины входных данных) время.</p>
5
<p>Современная криптография с открытым ключом (TLS, SSH, IpSec, Signal) основана на сложности факторизации больших чисел (RSA) и/или сложности вычисления дискретного логарифма (Диффи-Хэллман). В 1994 году Шор предложил<a>квантовый алгоритм</a>, решающий обе задачи за полиномиальное (от длины входных данных) время.</p>
6
<p>В терминологии криптоанализа такой алгоритм классифицируется как "тотальный взлом".<a>Современные квантовые компьютеры</a>не обладают мощностями, а именно количеством кубит, достаточными для решения этих задач в интересных для криптографии параметрах.</p>
6
<p>В терминологии криптоанализа такой алгоритм классифицируется как "тотальный взлом".<a>Современные квантовые компьютеры</a>не обладают мощностями, а именно количеством кубит, достаточными для решения этих задач в интересных для криптографии параметрах.</p>
7
<p>Сложно предсказать, когда мы получим квантовый компьютер, который сможет проводить вычисления с несколькими тысячами кубит. На всякий случай криптографы подготовили альтернативные криптографические примитивы, (предположительно) стойкие к атакам на квантовый компьютер.</p>
7
<p>Сложно предсказать, когда мы получим квантовый компьютер, который сможет проводить вычисления с несколькими тысячами кубит. На всякий случай криптографы подготовили альтернативные криптографические примитивы, (предположительно) стойкие к атакам на квантовый компьютер.</p>
8
<h2>Пост-квантовые решения</h2>
8
<h2>Пост-квантовые решения</h2>
9
<p>А именно, место теоретико-числовых задач (таких как факторизация, дискретный логарифм) могут занять:</p>
9
<p>А именно, место теоретико-числовых задач (таких как факторизация, дискретный логарифм) могут занять:</p>
10
<h3>I. Сложные задачи на евклидовых решетках</h3>
10
<h3>I. Сложные задачи на евклидовых решетках</h3>
11
<p>А именно, задача нахождения короткого вектора: по данному базису найти кратчайший ненулевой элемент решетки, определенной как</p>
11
<p>А именно, задача нахождения короткого вектора: по данному базису найти кратчайший ненулевой элемент решетки, определенной как</p>
12
<p>Плюсы решеток: сравнительно небольшие размеры ключей, быстрые алгоритмы генерации ключей, шифрования/дешифрования, наличие алгоритмов и для цифровой подписи, и для обмена ключами. Недостатки: плохая изученность сложности задачи короткого вектора решетки для эффективных схемах</p>
12
<p>Плюсы решеток: сравнительно небольшие размеры ключей, быстрые алгоритмы генерации ключей, шифрования/дешифрования, наличие алгоритмов и для цифровой подписи, и для обмена ключами. Недостатки: плохая изученность сложности задачи короткого вектора решетки для эффективных схемах</p>
13
<p>Примеры:<a>Frodo</a>,<a>New Hope</a>,<a>Crystals-Kyber</a>,<a>NTRU</a>(для шифрования),<a>Crypstals-Dilithium</a>,<a>Falcon</a>(для цифровой подписи)</p>
13
<p>Примеры:<a>Frodo</a>,<a>New Hope</a>,<a>Crystals-Kyber</a>,<a>NTRU</a>(для шифрования),<a>Crypstals-Dilithium</a>,<a>Falcon</a>(для цифровой подписи)</p>
14
<h3>II. Сложные задачи из теории кодирования</h3>
14
<h3>II. Сложные задачи из теории кодирования</h3>
15
<p>Задача декодирования спрашивает, по данной матрице вектору и весовому значению найти вектор e, т.ч. He = s и</p>
15
<p>Задача декодирования спрашивает, по данной матрице вектору и весовому значению найти вектор e, т.ч. He = s и</p>
16
<p>Плюсы задач теории кодирования: простота понимания, реализации; несколько десятилетий криптоанализа Недостатки: большие размеры ключа и, следовательно, более медленные операции. Отсутствие алгоритма подписи</p>
16
<p>Плюсы задач теории кодирования: простота понимания, реализации; несколько десятилетий криптоанализа Недостатки: большие размеры ключа и, следовательно, более медленные операции. Отсутствие алгоритма подписи</p>
17
<p>Примеры:<a>McEliece</a></p>
17
<p>Примеры:<a>McEliece</a></p>
18
<h3>III. Сложные задачи на многомерных полиномах</h3>
18
<h3>III. Сложные задачи на многомерных полиномах</h3>
19
<p>Найти решение (как правило, разряженное) системы уравнений от многих переменных над</p>
19
<p>Найти решение (как правило, разряженное) системы уравнений от многих переменных над</p>
20
<p><em>Рисунок взят из презентации Albrecht Petzoldt, PQCrypto 2018</em></p>
20
<p><em>Рисунок взят из презентации Albrecht Petzoldt, PQCrypto 2018</em></p>
21
<p>Плюсы: малый размер подписи Недостатки: сравнительно большой ключ, отсутствие алгоритма шифрования Примеры:<a>MQDSS</a></p>
21
<p>Плюсы: малый размер подписи Недостатки: сравнительно большой ключ, отсутствие алгоритма шифрования Примеры:<a>MQDSS</a></p>
22
<h3>IV. Задача вычисления изогении между абелевыми многообразиями</h3>
22
<h3>IV. Задача вычисления изогении между абелевыми многообразиями</h3>
23
<p>По двум (эллиптическим) кривым найти изогению определённой степени<em>Рисунок сделан W.Castryk в<a>этом</a>посте</em></p>
23
<p>По двум (эллиптическим) кривым найти изогению определённой степени<em>Рисунок сделан W.Castryk в<a>этом</a>посте</em></p>
24
<p>Плюсы: малые размеры ключей Недостатки: сравнительно мало изученная задача, длительные алгоритмы обмена ключами, подписи еще более неэффективные Примеры:<a>SIKE</a>,<a>CSIDH</a></p>
24
<p>Плюсы: малые размеры ключей Недостатки: сравнительно мало изученная задача, длительные алгоритмы обмена ключами, подписи еще более неэффективные Примеры:<a>SIKE</a>,<a>CSIDH</a></p>
25
<h3>V. Задача нахождения коллизий хэш-функции</h3>
25
<h3>V. Задача нахождения коллизий хэш-функции</h3>
26
<p>По сути, усложнение одноразовой подписи<a>Лампорта</a></p>
26
<p>По сути, усложнение одноразовой подписи<a>Лампорта</a></p>
27
<p><em>Рисунок взят из<a>презентации</a>Andreas Huelsing</em></p>
27
<p><em>Рисунок взят из<a>презентации</a>Andreas Huelsing</em></p>
28
<p>Плюсы: небольшие ключи Недостатки: только подпись, сравнительно большой размер подписи</p>
28
<p>Плюсы: небольшие ключи Недостатки: только подпись, сравнительно большой размер подписи</p>
29
<p>Примеры:<a>SHINCS</a></p>
29
<p>Примеры:<a>SHINCS</a></p>
30
<p><em>Есть вопросы? Пишите в комментариях!</em></p>
30
<p><em>Есть вопросы? Пишите в комментариях!</em></p>
31
31