Обзор методов вскрытия криптосистемы RSA

При сохранении тенденции (число F7 факторизовано в 1970 г., F8 в 1980 и F9 в 1990) логично предположить, что в 2000 г. будет факторизовано число  F10 = 21024 + 1.

Возможно ли появление универсальных методов целочисленной факторизации, столь же эффективных, как алгоритм СЧР для чисел Ферма? Специалисты в области вычислительной теории чисел полагают, что возможно. Прогресс в целочисленной факторизации имеет устойчивый характер. Считалось, например, что методы линейной алгебры, играющие ключевую роль в большинстве алгоритмов факторизации и плохо поддающиеся распараллеливанию, ограничат применение распределенных вычислений. Однако факт разработки новых алгоритмов опроверг сложившееся мнение.

Для факторизации числа 129D по сравнению с факторизацией числа 45D по методу непре­рывных дробей в 1970 г. понадобилось бы в 6 х 1011 раз больше производительности и в 5 х 106 раз больше — при использовании быстрого алгоритма.

Таким образом, развитие алгоритмической базы сравнимо (по логарифмической шкале) с ростом производительности компьютеров. При условии сохранения отмеченной тенденции в 2004 г. скрытая атака позволит факторизовать 1024-битные числа (современные алгоритмы позволяют факторизовать 768-битные числа). В 2014 г. разрядность факторизуемых чисел возрастет до 1500 бит и более.

Основная причина стремительного роста разрядности надежного модуля заключается в субэкспоненциальной оценке времени работы современных алгоритмов факторизации. Для сравнения; трудоемкость силовой атаки на симметричную криптосистему, например DES, определяется объемом ключевого пространства (2n — в худшем случае и 2n-1 — в среднем, при n-разрядном ключе).

Разбалансированная RSA

Тенденция к увеличению размера модуля криптосистемы RSA вполне обоснованна — атака на основе факторизации представляет реальную угрозу. Тем более, когда речь идет о хранении долговременных секретов (например, долговременных долговых обязательств, закладных и т.д.). Однако с увеличением разрядности модуля сложность вычислений возрастает куби­чески. Таким образом, выбор разрядности модуля представляет собой компромисс между вычислительной эффективностью и криптостойкостью.

Как было отмечено в предыдущем параграфе, трудоемкость современных алгоритмов факторизации (например, ОЧР) не зависит от разрядности делителей модуля: для нахо­ждения простого делителя из одной и из пятидесяти десятичных цифр требуется одинако­вое время. Поскольку основные достижения в области факторизации получены в результате применения алгоритма ОЧР или аналогичных ему, можно предположить, что эта тенденция сохранится и впредь.

Шамир (A. Shamir) предложил новый подход к решению проблемы RSA-модуля. Криптосистема с модулем, построенным методом Шамира, получила название «разбалансированной RSA». В такой криптосистеме — разрядность модуля п = pq увеличена в десять раз (до 5000 бит), а разрядность делителя р в два раза (до 500 бит). Соответственно на дели­тель q приходится 4500 бит. Название криптосистемы отражает диспропорцию в разрядности делителей п. Такой выбор делителей, по мнению Шамира, учитывает тенденции развития методов целочисленной факторизации и обеспечит адекватную криптостойкость в течение ближайшего десятилетия.

Основная проблема заключается в том, что при таком модуле быстродействие реализации RSA — в 1000 раз ниже: теперь задержка на одну операцию модульного возведения в степень вместо одной секунды (при микропроцессорной реализации и 500-битном модуле) составит 16 минут — что неприемлемо.

При использовании RSA в процедуре установления ключевого синхронизма (метод циф­рового конверта) шифруемые сообщения (сеансовые ключи), как правило, не превышают размера модуля р: даже при использовании режима трехкратного DES-шифрования (EDE= Encode Decode Encode) на трех независимых ключах размер сообщения не превышает          168 бит ( проект NISTпо разработке нового стандарта AES предусматривает применение ключей длиной 128, 192, 256 бит).Таким образом, мож­но предположить, что шифруемый блок открытого текста в числовом отображении находится в интервале [0, р-1]. При этом чрезмерно короткие блоки могут искусственно дополняться при помощи известной техники «набивки».

Широко распространенный способ повышения вычислительной эффективности RSA при шифровании с = m (mod n) заключается в выборе малого е. Однако при заданных дели­телях выбор е< 10 не обеспечивает приведения по модулю в процессе шифрования, так как длина сообщения т составляет десятую часть от длины модуля п. При e » 20 разряд­ность me приблизительно в два раза превышает разрядность модуля n, что обеспечивает приведение по модулю в процессе шифрования. Отметим, что при таком е и вычислении me(mod п) методом последовательного возведения в квадрат большинство промежу­точных произведений не приводится по модулю и только последняя операция возведения в квадрат является модульной. Таким образом, при 20 < е < 100 быстродействие шифрования при 5000-битном модуле сравнимо с быстродействием дешифрования при 500-битном модуле (менее одной секунды).

Рассмотрим процедуру дешифрования m = (cd (mod п) при условии, что с, п и d — 5000-битные числа. Воспользовавшись Китайской теоремой об остатках , можно эффективно вычислитьm1 = cd(mod p) для 500-битного модуля р. предварительно приведя с по модулю р к d по модулю (p - 1). Однако вычисление m2 = сd(mod q) при 4500-битном модуле q требует в 93 = 729 раз больше операций.

Шамир выдвинул простое рассуждение, из которого следует, что выполнение этих сложных вычислений не является обязательным. Действительно, по определению                m1= m (modр). При этом известно, что открытый текст m меньше р и, следовательно,              m (mod p) = m. Это, в свою очередь, означает, что m1 = m и приведение m2 по модулю q приведет к тому же самому результату.

Несмотря на то, что разбалансированная и стандартная криптосистемы RSA имеют срав­нимую вычислительную трудоемкость, затраты памяти для хранения открытых ключей раэ-балансированной RSA возрастают в десять раз.

Рассмотрим последствия увеличения размера памяти с произвольным доступом (RAM) для различных приложений. Для персонального компьютера десятикратное увеличение па­мяти для хранения ключей не приводит к серьезным последствиям. (Если в памяти компью­тера хранится 100 000 ключей по 5000 бит, то необходимый объем памяти для их хранения составит 60 Мбайт.) Однако для интеллектуальных карточек (Smart Card) это не так - их стоимость прямо пропорциональна объему памяти. Кроме того, многие разработчики интеллектуальных карточек уже реализовали специализированный RSA-процессор на базе 512-битного модуля. По этой причине можно ожидать, что их реакция на увеличение разме­ра модуля будет негативной. В ряде практических приложений интеллектуальные карточки используются совместно с мощными персональными компьютерами. Таким образом, откры­вается возможность выбора технологической базы (персональный компьютер или интеллек­туальная карточка) для реализации процедур шифрования/дешифрования. Например, пер­сональный компьютер может генерировать и шифровать первичный сеансовый ключ. Затем шифротекст подается на вход последовательного интерфейса карточки и в темпе приема (по мере поступления бит шифротекста) приводится по модулю р; в ходе вычислений ис­пользуются 512-битные регистры RSA-процессора. Конечный сеансовый ключ получается путем модульного возведения в степень, также реализуемого 512-битным RSA-процессором интеллектуальной карточки. Преимущество описанного метода заключается в возможности использования вычислительных ресурсов современных интеллектуальных карточек приpar-боте с модулем переменной длины без их замены.

Еще один потенциальный недостаток связан с десятикратным увеличением памяти справочника открытых ключей. Однако разбалансированность открытых ключей позволяет устранить и эту проблему. Обозначим через G генератор псевдослучайных последователь­ностей, применяемый для отображения идентификационной информации u (имени, адреса электронной почты и т.д.) в уникальную 5000-битную псевдослучайную последовательность t. Предполагается, что G всем известно. Каждый пользователь генерирует 500-битное про­стое число р, затем генерирует q — простое число из интервала [а, а + 250], где а наименьшее целое, большее или равное t/p. Поскольку простых чисел достаточно много, такое q почти всегда существует. В результате разница в разрядности модуля n = pq и t не будет пре­вышать 550 бит. Каждый пользователь и может опубликовать число s = п-t в качестве своего открытого ключа. Тогда каждый абонент-отправитель криптосети может получить 5000-битный открытый ключ абонента-получателя, вычислив KO=G(u)+s. Необходимо отметить. что описанный метод не облегчает задачу факторизации модуля п:единственное отличие заключается в том, что стартовая точка в процедуре генерации q не просто выбирается слу­чайным образом, а задается так отношение  случайного и простого числа. Посколъку закон распределения простых чисел отличается от равномерного --

v     Количество простых, не превосходящих х, приблизительно выражается величиной p(x) ~ x/ln x (от­ношение правой и левой частей с ростом х стремится к 1), или более точно логарифмической суммой Ls(x) = 1/ln 2 + l/ln3 + ... + 1/ln x. Например, в интервале между ста миллионами и ста миллионами плюс 150 000 следует ожидать появления около 8142 простых, так как . Другое известное приближение , где z(n+1) — дзета-функция Римана.

число а также не является рав­номерно распределенным. Для сглаживания побочных эффектов неравномерности граница интервала, в котором выбирается q. задается как а + 250. Таким образом, представление модуля п в виде s ничем не хуже, и тот факт, что ( не является истинно случайным числом, не влияет на его криптостойкость.  

Необходимо также отметить, что разбалансированность может использоваться для удво­ения производительности существующих в настоящее время реализации RSA, в которых делители р иq имеют одинаковый размер. Причем для RSA-подписи такая оптимизация не подходит, так как проверяющему неизвестен делитель р. Кроме того, способ, при кото­ром опубликованный короткий открытый ключ на самом деле является длинным, является чрезвычайно полезным при ограничениях на размер модуля, аналогичных экспортным огра­ничениям на длину ключа для симметричных криптосистем.

Гилберт (Н. Gilbert), Гупта (D. Gupta), Одлыжко (A. Odiyzko) и Квискватер                     (J.-J. Quisquater) показали, что разбалансированная RSA может быть успешно атакована при помощи специального протокола взаимодействия между отправителем и получателем.

Предположим, что n и е — открытый ключ Боба. Задача Алисы — раскрытие р и q. Для этого Алиса шифрует сообщение m > р и посылает Бобу шифротекст me mod n. Боб дешифрует шифротекст и получает т. Так как т > р, то . Предположим теперь, что Алиса каким-либо образом получила доступ к сообщению , тогда она может проверить, что р | (т — т). При соблюдении ограничений 0<m, <n Китайской теоремы об остатках следует, что q † (т -). Следовательно, Алиса может восстановить р, вычислив          НОД(т -,n).

Отметим, что при определенных обстоятельствах Боб может раскрыть Алисе сообщение (например, в сообщениях типа «Что за «мусор»  ты мне прислала

Очевидный способ противодействия заключается во введении избыточности в сообщение т, например, некоторой специальной идентификационной последовательности. Сообщение  отвергается, если не содержит идентификационной последовательности.

Однако этого недостаточно. Рассмотрим пример, в котором Алиса посылает сообщение типа «Переведите на счет Боба сумму в размере 101,74 долл. с мо­его счета №123 в банке г. Замухрышина». Сообщение «набивается» до нужной длины (исходя из размера делителя р) и заверяется цифровой подписью Алисы. Если m > p, сообщение   будет отвергнуто. Если     m < р и  = m, сообщение будет принято и денежный перевод ини­циирован. Факт денежного перевода позволит Алисе узнать, что т < р. Подобная стратегия позволяет раскрывать биты р. Стоимость раскрытия одного бита р можно уменьшить, даже при условии, что сумма в 100 долл. является минимальной для инициирования денежного пе­ревода. Предположим, что Алиса сумела установить границы р, например, 6 х 2k < р < 7 х 2k. Тогда с помощью бинарного поиска Алиса могла бы приблизительно оценить т как 13 х 2k-1. Однако Алиса может попытаться раскрыть битыр методом последовательных приближений: сначала опробовав т как 111 х 2k-4, затем, если р < 111 х 2k-4, как 110 х 2k-4 и так далее. Метод позволяет раскрыть четыре бита р вместо одного при той же стоимости. Отметим, что метод требует большого числа попыток; соответственно, возросшая активность может вызвать подозрение и взаимодействие будет заблокировано.

Возможно, приведенная выше атака выглядит несколько надуманно, однако она вполне реальна в ситуациях, когда по косвенным признакам можно принять решение о соотноше­нии n и р. Например, если разбалансированная RSA используется для передачи сеансового ключа от отправителя (Алисы) к получателю (Бобу), атака может заключаться в передаче Бобу        тe mod п с последующей проверкой факта использования ключа т для шифрования сообщений сеанса.

Необходимо отметить, что данная атака не приводит к полной компрометации разбалансированной RSA, но свидетельствует о необходимости введения избыточности в открытый текст, а также гарантий того, что в ходе взаимодействия получатель никогда не раскрывает дешифрованные сообщения.

Пакетная RSA

Пакетная RSA (batch RSA) представляет собой метод, позволяющий выполнять множе­ство RSA-дешифрований (порядка n/log2 (n), где n — секретный параметр, логарифм берет­ся по основанию 2) с вычислительной эффективностью одиночного RSA-дешифрования. При этом предполагается, что используется единый модуль, но различные и попарно взаимно про­стые экспоненты шифрования е. Проблема вычислительной эффективности RSA возникает в ряде криптографических приложений с централизованным управлением. Так, например. некоторые схемы цифровой подписи предполагают наличие депозитарно-распределительного центра, генерирующего заверенные цифровой подписью квитанции для каждой транзакции. В других распространенных приложениях центральный компьютер должен обслуживать по­ток запросов в режиме on-line, например, при управлении ключами в сетях со звездообразной топологией. Таким образом, пакетная RSA позволяет минимизировать вычислительную на­грузку центра.

Рекомендуемая длина ключа

Размер ключа в алгоритме RSA связан с размером модуля n. Два числа p и q, произведением которых является модуль, должны иметь приблизительно одинаковую длину поскольку в этом случае найти сомножители (факторы) сложнее, чем в случае когда длина чисел значительно различается. Например, если предполагается использовать 768-битный модуль, то каждое число должно иметь длину приблизительно 384 бита. Обратите внимание, что если два числа чрезвычайно близки друг к другу или их разность близка к некоторому предопределенному значению, то возникает потенциальная угроза безопасности, однако такая вероятность – близость двух случайно выбранных чисел – незначительна.

1.      Возьмем 

2.      При p < q, имеем 

Поскольку ,то значения p и q можно легко найти, если разность p - q достаточно мала.

Оптимальный размер модуля определяется требованиями безопасности: модуль большего размера обеспечивает большую безопасность, но и замедляет работу алгоритма RSA. Длина модуля выбирается в первую очередь на основе значимости защищаемых данных и необходимой стойкости защищенных данных и во вторую очередь – на основе оценки возможных угроз.