из той информации, которая доступна нарушителю, быть может еше остается какой-нибудь способ получить эффективно некоторую частичную информацию об открытом тексте, например, такую, как половина битов сообшения га. Все эти возможные слабости снимает применение вероятностного шифрования, которое мы рассмотрим в § 6, при единственном предположении, что разложение на множители является действительно трудной задачей.

Пользователи криптосистемы RSA должны знать о том, что эта криптосхема является слабой при некоторых видах атак на основе выбранного шифртекста [134, 143]. Предпо.пожим, например, что нарушитель перехватил некоторое с = т mod п, где е и п - открытая информация. Ему хотелось бы определить т. При атаке на основе выбранного шифртекста ему предоставляется возможность передать некоторое с законному получателю, с тем чтобы получить в ответ соответствующее га, такое, что c = nf mod п. Разумно ожидать, что получатель может уклониться от ответа, если нарушите.пь попытается использовать непосредственно с=с (в противном случае никакая криптосистема, скорее всего, не должна быть надежной). Однако нарушитель в состоянии замаскировать свой вопрос, выбрав случайным образом некоторое х из и вычислив с= [х) с mod п. Исходный открытый текст т может быть тогда получен эффективно (при использовании обобщенного алгоритма Евклида), поскольку m = rh х~ mod п. Неизвестно, существует ли более хитроумная атака на основе выбранного шифртекста, действительно способная раскрыть RSA в том смысле, что позволит нарушителю вычислить множители п или, хотя бы, секретную экспоненту дешифрования d. Если бы это было так, то все последующие шифртексты можно было бы расшифровывать без какого бы то ни было обращения к законному получателю. Для первого знакомства в связи с этим смотрите [149].

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

Так, например, на вентильной матрице Кочанского [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 секунд, или, при разбиении записи открытого текста на отдельные

блоки, со скоростью около 57 бит в секувду! Фактически же, т.к. это гибридная система, то за достаточно большой промежуток времени она работает намного быстрее (см. § 7).

Относительно реализации RSA в университете Ватерлоо (Канада), в которой используется арифметика в полях характеристики 2 и скорость шифрования и дешифрования достигает 300 килобит в секунду, см. [5].

§ 5. Генерация псевдослучайных чисел

Двоичная последовательность назывсются псевдослучайной, если она выглядит как бессистемная и вероятностная, хотя на самом деле создавалась посредством вполне детерминированного процесса, который Нс1зывается псевдослучайным генератором. Такие генераторы начинают свою работу с действительно случайной исходной последовательностью, называемой начальной, и детерминировано вырабатывают с ее помощью гораздо более длинную псевдослучайную последовательность. В этом смысле псевдослучайные генераторы можно рассматривать как своего рода распространителей случайности. В качестве энциклопедии по классической генерации псевдослучайных последовательностей и тестам, цель которых заключгьется в том, чтобы с их помощью иметь возможность отличать псевдослучайные последовательности от истинно случайных, мы рекомендуем [236].

Случайность и криптография вообще очень сильно взаимосвязаны. Ведь основная цель криптографических систем состоит в том, чтобы преобразовать неслучайные осмысленные открытые тексты в кажущуюся случайной беспорядочную мешанину символов. Эта способность криптосистем может быть использована для генерации псевдослучайных последовательностей следующим образом. Пусть Ек - некоторый алгоритм шифрования, и пусть аго - произвольный открытый текст. Рассмотрим последовательность, которая определяется как Xiji - £fe(ar,) для i > 0. Если Ek вполне подходит для криптографических целей, то по всей видимости последовательность хх, х, ... - является последовательностью без явных признаков системности (хотя совершенно очевидно, что она обязательно дблжна згщикливать-ся). Может быть, для того чтобы уменьшить корреляцию в этой