О стойкости

Как известно, криптографическая стойкость 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. Этим и объясняется выигрыш в быстродействии.

Новости
23.05.2017
XХII научно-практическая конференция «Комплексная защита информации»
31.03.2017
ITSecurity-2017
22.02.2017
Ввод в действие новой редакции СТБ 34.101.47
21.02.2017
План семинара весна 2017
20.01.2017
Итоги NSUCRYPTO-2016
24.10.2016
План семинара осень 2016
29.08.2016
Ввод в действие СТБ 34.101.77
15.06.2016
CTCrypt-2016
19.04.2016
Криптографические стандарты: планы на 2016 год