О стойкости

Как известно, криптографическая стойкость RSA основывается на сложности факторизации целых чисел. Для полной компрометации систем типа RSA-l достаточно разложить на множители общедоступное l-битовое число, которое называют модулем. Модуль, как правило, является произведением двух различных простых.

Решето числового поля (Number Field Sieve, NFS) является самым эффективным на сегодняшний день методом факторизации целых чисел. NFS – субэкспоненциальный метод. С его помощью можно достаточно  быстро факторизовывать 512-битовые модули, которые использовались в системах защиты информации еще совсем недавно. Действующий рекорд – факторизация модуля RSA-768 – также установлен с помощью NFS.

Стойкость алгоритмов электронной цифровой подписи, определенных в СТБ 1176.2-99, основывается на сложности дискретного логарифмирования в подгруппах мультипликативных групп простых полей. Поле задается l-битовым модулем p, порядок подгруппы является r-битовым числом q.

Для логарифмирования могут применяться либо универсальные методы (они годятся для любой циклической группы), либо снова метод решета числового поля. Сложность универсальных методов определяется величиной q, лучшие из них выполняются за экспоненциальное время порядка 2r/2. Сложность NFS определяется длиной l модуля p и близка к сложности факторизации l-битового модуля RSA.

Числа r и l выбирают так, чтобы обеспечить паритет сложности универсальных методов и метода NFS. Если мы хотим, чтобы дискретное логарифмирование требовало порядка 2k операций, то r должно быть близко к 2k, однако l должно быть существенно больше. Преобладание l над r является платой за существование субэкспоненциального метода NFS.

Следующая таблица взята из СТБ 1776.2-99. Таблица задает 10 разрешенных сочетаний r и l. Мы добавили в таблицу столбец k = [r / 2], который характеризует «чистую» битовую стойкость.

уровень стойкости k r l
1 72 143 638
2 77 154 766
3 87 175 1022
4 91 182 1118
5 97 195 1310
6 104 208 1534
7 111 222 1790
8 117 235 2046
9 124 249 2334
10 128 257 2462

Таблицу можно использовать для определения связей между длиной модуля RSA и уровнем стойкости СТБ 1176.2. Например, RSA-1024 примерно соответствует третьему уровню СТБ, а RSA-2048 – примерно восьмому.

Отметим, что десятый (максимальный) уровень СТБ 1176.2 по стойкости соответствует первому (минимальному) уровню СТБ 34.101.45-2013, но существенно проигрывает ему по быстродействию. Стойкость алгоритмов СТБ 34.101.45 также основывается на сложности дискретного логарифмирования, но уже в группах точек эллиптических кривых. Эллиптическая кривая строится над простым полем из p элементов. Группа точек выбирается так, чтобы защититься от специальных (не универсальных) методов, в том числе от субэкспоненциальных методов типа NFS. Такая защита позволяет вести вычисления по модулю p, близкому к порядку группы q. Этим и объясняется выигрыш в быстродействии.

Новости
21.10.2024
Создание сектора КБ
07.05.2024
Защита диссертации
07.03.2024
План семинара весна 2024
12.02.2024
Единый день голосования
24.10.2023
II Международная научная конференция
26.05.2023
XХVIII научно-практическая конференция
28.04.2023
TIBO 2023
02.01.2023
Программный комплекс ЭАДП
27.12.2022
С Новым годом!