Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
58 Системы с открытым ключом
Глава 4
из той информации, которая доступна нарушителю, быть может еще остается какой-нибудь способ получить эффективно некоторую частичную информацию об открытом тексте, например, такую, как половина битов сообщения т. Все эти возможные слабости снимает применение вероятностного шифрования, которое мы рассмотрим в § 6, при единственном предположении, что разложение на множители является действительно трудной задачей.
Пользователи криптосистемы RSA должны знать о том, что эта криптосхема является слабой при некоторых видах атак на основе выбранного шифртекста [134, 143]. Предположим, например, что нарушитель перехватил некоторое с = те mod п, где е и п — открытая информация. Ему хотелось бы определить т. При атаке на основе выбранного шифртекста ему предоставляется возможность передать некоторое с законному получателю, с тем чтобы получить в ответ соответствующее т, такое, что с = me mod п. Разумно ожидать, что получатель может уклониться от ответа, если нарушитель попытается использовать непосредственно с = с (в противном случае никакая криптосистема, скорее всего, не должна быть надежной). Однако нарушитель в состоянии замаскировать свой вопрос, выбрав случайным образом некоторое х из Z’* и вычислив с = (же) • с mod п. Исходный открытый текст т может быть тогда получен эффективно (при использовании обобщенного алгоритма Евклида), поскольку т = т ¦ х~1 mod п. Неизвестно, существует ли более хитроумная атака на основе выбранного шифртекста, действительно способная раскрыть RSA в том смысле, что позволит нарушителю вычислить множители п или, хотя бы, секретную экспоненту дешифрования d. Если бы это было так, то все последующие шифртексты можно было бы расшифровывать без какого бы то ни было обращения к законному получателю. Для первого знакомства в связи с этим смотрите [149].
Несмотря на все свои преимущества перед криптографическими системами с секретным ключом, RSA все же значительно медленнее, чем DES. Напомним, что аппаратная реализация DES в настоящее время способна достигать скорости 90 мегабит в секунду. Это заставляет рассматривать перспективу коммерческой применимости даже самых быстрых RSA устройств для шифрования скорее как не совсем удовлетворительную.
Криптосистема RSA 59
Так, например, на вентильной матрице Кочанского [238, 338] можно достичь примерно .5 килобит в секунду с 512-ти битовым ключом (что являетсй безусловно самым нижним пределом на размер ключа, который вообще имеет смысл рассматривать). Было сообщение, опубликованное в [280] о более быстрой реализации, которая принадлежит Джиму Омуре, но и она (на время ее разработки была) более чем в тысячу раз медленнее, чем DES. Существовала также знаменитая «микросхема Ривеста», которая так никогда и не была отлажена [304, 305] и проект Брикелла, который в случае его реализации теоретически смог бы достичь 25 килобит в секунду. Об еще более быстрой разработке для практических применений сообщалось в [314]. Читайте также [282]. Обзор этих и некоторых других аппаратных реализаций RSA дан Эрнестом Брикеллом в [91]: Консультируйтесь также в [156, 279].
Под руководством Джина Виллемина была разработана очень быстрая микросхема, в которой скорость шифрования Достигала 225 килобит в секунду при длине ключа в 508 бит [322]. В ней существенно использовалось знание сомножителей, составляющих модуль.
Необходимо отметить только, что чисто программные версии алгоритма RSA гораздо медленнее аппаратных. Наиболее быстрая (соответствующая) программная реализация RSA-шифрования, имевшая коммерческое применение, шифрует со скоростью 20 килобит в секунду (при длине модуля в 1024 бита) и 40 килобит в секунду (при длине модуля в 512 бит). Кроме того, интересна описанная в [160] программно-аппаратная реализация RSA, в которой используются возможности арифметики сигнального процессора Motorola DSP56000.
Следует упомянуть также о шифраторе CryptoCom компании Algorithmic Research, который был спроектирован для работы на IBM PC. Он шифрует очень быстро, так как в экспоненте у него в качестве открытого ключа всегда использует е = 3, но при этом RSA (поскольку CryptoCom — это гибридная система) применяется только при смене DES-ключей шифрования. Обычно использование малых экспонент в RSA очень опасно [210], хотя в приведенной ситуации и не слишком. По поводу криптоанализа RSA при использовании коротких секретных экспонент см. [356]. Один 512-битовый блок CryptoCom дешифрует примерно за 9 секунд, или, при разбиении записи открытого текста на отдельные
60 Системы с открытый'ключом
Глава 4
блоки, со скоростью около 57 бит в секунду! Фактически же, т.к. это гибридная система, то за достаточно большой промежуток времени она работает намного быстрее (см. § 7).
Относительно реализации RSA в университете Ватерлоо (Канада), в которой используется арифметика в полях характеристики 2 и скорость шифрования и дешифрования достигает 300 килобит в секунду, см. [5].
§ 5. Генерация псевдослучайных чисел
