2.1 Аппаратная реализация rsa

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

RSA никогда не достигнет скорости симметричных алгоритмов. Но шифрование RSA выполняется намного быстрее, если вы правильно выберете значение e. Тремя наиболее частыми вариантами являются 3, 17 и 65537 (2¹⁶ +1). Двоичное представление 65537 содержит только две единицы, поэтому для возведения в степень нужно выполнить только 17 умножений. Не существует никаких проблем безопасности, связанных с использованием в качестве е любого из этих трех значений (при условии, что вы дополняете сообщения случайными числами), даже если одно и то же значение е используется целой группой пользователей.

Операции с закрытыми ключами можно ускорить при помощи китайской теоремы об остатках, если вы сохранили значения р и q, а также дополнительные значения: d mod(p-1), d mod (q-1) и q^-1 mod p.

Эти дополнительные числа можно легко вычислить по закрытому и открытому ключам.

2.2 Безопасность rsa

Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел. Технически, это утверждение о безопасности лживо. Предполагается, что безопасность RSA зависит от проблемы разложения на множители больших чисел. Никогда не было доказано математически, что нужно разложить и на множители, чтобы восстановить т по с и е. Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел.

Также можно вскрыть RSA, угадав значение (p-1)(q-1). Это вскрытие не проще разложения п на множители.

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

Самым очевидным средством вскрытия является разложение на п множители. Любой противник сможет получить открытый ключ г и модуль п. Чтобы найти ключ дешифрования d, противник должен разложить п на множители. Но настоящие технологии разложения на множители не позволяют сделать это быстро и для больших чисел.

Конечно, криптоаналитик может перебирать все возможные d, пока он не подберет правильное значение. Но такое вскрытие грубой силой даже менее эффективно, чем попытка разложить п на множители.

Существует еще один повод для беспокойства. Большинство общепринятых алгоритмов вычисления простых чисел р и q вероятностны, что произойдет, если р и q окажется составным? Однако можно свести вероятность такого события до нужного минимума. И даже если это произойдет, скорее всего, такое событие будет сразу же обнаружено - шифрование и дешифрование не будут работать. Существует ряд чисел, называемых числами Кармайкла, которые не могут обнаружить определенные вероятностные алгоритма поиска простых чисел. Они небезопасны, но чрезвычайно редки.