ностного шифрования Гольдвассер-Микэли допускала столь существенное рс1скрытие данных, что не имела большого практического значения. Поэтому мы не будем описывать ее здесь.

Тем не менее, вероятностное шифрование достигло такого состояния, что уже в настоящее время существует криптосистема даже более эффективная, чем RSA. Для обеспечения конфиденциальности (но не аутентификации - см. § 5.1) механизмы работы этой системы Блюма-Гольдвассер, которая описывается ниже, являются наилучшими из того, что наука в настоящее время может предложить. Система основана на вере в то, что возведение в квадрат по модулю целого числа Блюма - однонаправленная функция с потайным ходом (см. последний пример из § 1), и на том, что псевдослучайный битовый генератор, который был описан в § 5, является криптографически сильным. Естесгвен-но, в качестве такого генератора для получения псевдослучайного одноразового шифра необходимой длины из его собственного случайным образом выработанного исходного вектора отправителем сообщения используется BBS-генератор. Способность законного получателя вычислять квадратные корни (основанная на его личной информации о соответствующем потайном ходе) позволяет ему найти этот шифр, а затем с его помощью определить открытый текст.

Более формально, пусть р тл q - два случайно выбранных различных простых числа, сравнимых с 3 по модулю 4, которые вместе образуют секретный ключ. Их произведение п = р • q является открытым ключом. Пространство сообщений открытого текста - это множество всех конечных двоичных строк произвольной длины. Любое сообщение может в этом случае шифроваться непосредственно без разбиения на части, используя при этом один из режимов, которые были описаны в § 3.4, точно так же, как это было в случае с RSA. (Правда, это только чисто теоретически, поскольку на самом деле длина битовой строки, представляющей открытый текст не должна быть больше периода псевдослучайной последовательности, вырабатываемой BBS-генератором, хотя на практике этот период в столь большое число раз превышает размер модуля п, что позволяет фактически не ограничивать длину открытого текста.) Вероятностным пространством служит множество QRn, то есть множе-

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

Пусть т - некоторое -разрядное сообщение. И пусть также Хо - это случайный квадратичный вычет по модулю п. Предположим далее, что BBSn,t{xo) и xt определяются точно так же, как в § 5. Тогда шифрование то, использующее исходный вектор Хо и открытый ключ п, задается в виде пары чисел {xt, т ф BBSn,t{xo)), где «ф» означает поразрядное сложение по модулю 2. Здесь ВВ5„Дхо) используется в качестве одноразового шифра к открытому тексту га. Значение xt включается в шифртекст только для того, чтобы обеспечить законному получателю эффективное дешифрование, но тем самым никак не помогая в этом нарушителю. Напомним, что необходимым и достаточным условием для эффектавного вычисления примитивных квадратных корней является знание сомножителей числа п [297]. Простейший алгоритм дешифрования заключается в вычислении всей псевдослучайной последовательности, начиная с xt, в обратном порядке, и используя для этого рекуррентное уравнение Xi = Xi+i mod п. В результате такого вычисления сначала однозначно восстанавливается значение ВВ5п,г{з:о), а затем из известного шифртекста легко получается открытый текст.

Обозначим через / число разрядов модуля п. Эффективность только что описанного алгоритма шифрования полностью сопоставима с эффективностью алгоритма криптосхемы RSA, потому что в нем для каждого бита открытого текста используется одна операция модульного возведения в квадрат, в то время как в RSA для каждого {I - 1)-блока открытого текста требуется одно модульное возведение в степень, и при этом каждое возведение в степень требует / возведений в квадрат и, кроме того, I умножений (см. § 1). Простейший алгоритм дешифрования, который был предложен выше, не очень хорош, поскольку для каждого бита открытого текста он требует вычисления одного примитивного квадратного корня, а на каждое такое вычисление расходуется примерно столько же времени, сколько на одно модульное возведение в степень. К счгьстью, знание множителей п позволяет определять все отдельные биты слзгчайной последовательности

непосредственно не только в прямом порядке так, как это описано в конце § 5, но и в обратном. Такое вычисление обходится примерно во столько же, во сколько обходится одно возведение в степень (или RSA-дешифрование одного блока), и позволяет законному получателю сообщения вычислить хо непосредственно из Xt, а затем для того, чтобы получить BBSn,t(xo), проделать то же самое в прямом порядке так же эффективно, как это сделал его отправитель.

Сейчас мы представим этот эффективный алгоритм вычисления Хо из Xt при известном разложении п = р q. В качестве предварительного шага в нем сначала с помощью обобщенного алгоритма Евклида раз и навсегда вычисляются целые числа а и 6, такие что ар + bq = 1. Затем выполняются следующие операции:

а 4- expmod

Р <- expmod ( ,t,q-l

и <- expmod{(xt mod р), а,р) V <- expmod{{xt mod q), /?, q) return {bqu -\- apv) mod n .

Схема вероятностного шифрования Блюма-Гольдвассер может быть сделана даже еще быстрее. Более тщательный анализ псевдослучайного генератора BBS [349, 350, 8, 117] показывает, что в нем после каждой операции модульного возведения в квадрат можно использовать более одного значащего бита очередного квадратичного вычета ж,-. А именно, окончательная псевдослучайная последовательность не ослабится, если в нее для каждого индекса г будут выбираться (приблизительно) /052(0 первых значащих битов Х{. Благодаря такому улучшению вероятностное шифрование будет осуществляться быстрее, чем шифрование в RSA, примерно в 1од2{1) раз, причем то же самое справедливо и для дешифрования длинных сообщений (так как в этом случае достаточно проделать вычисление в обратном порядке только один раз). В заключение отметим, что криптосхе-ма вероятностного шифрования не только быстрее, чем RSA, но и также доказано, что трудность ее ргьскрытия вычислительно