О стойкости

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

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

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

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

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

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

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

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