соответствующем предположении он является криптографически сильным. Пусть п - целое число Блюма с неизвестным разложением на множители. Возьмем в качестве исходного числа случайным образом выбранный квадратичный вычет (для того, чтобы это сделать, выберем наугад целое х взаимно простое с п, а а;о вычислим как а;о = а; mod п). Для г О определим Xi рекурсивно по формуле = mod n и обозначим через 6,- первый значащий бит Xi. Тогда для любого целого t первые t битов, которые таким образом будут сгенерированы из xq, мы и объявим искомой псевдослучайной последовательностью BBSn,t{xo) = bobib2 ... bt-i-

Когда мы говорим, что BBS-генератор непредикативен влево, то это означает, что никто не может отгадать 6о, основываясь лишь на знании п и 6162 . - .6t-i- Если бы это было не так, то первый значащий бит неизвестного примитивного квадратного корня X любого заданного квадратичного вычета у можно было бы определить следуюпщм образом. Сначала вычислим псевдослучайную последовательность BBSn,t-i(y).T объявим, что она на самом деле является последовательностью BBSn,t{x) с удаленным первым битом. Затем отгадаем этот пропущенный бит и отметим, что по определению он и является тем самым первым значащим битом х, который мы искали. Из этого следует, что BBS-генератор должен быть непредикативен влево в предположении, что факторизация целого числа п является трудной задачей. Следовательно, по теореме Яо, такой генератор будет криптографически сильным.

Дополнительное привлекательное свойство этого генератора заключается в том, что для всех, кто знает разложение п на множители, он допускает прямое определение тех отдельных битов, которые в нем вырабатываются. Для этого заметим, что Xi = xl mod п. Но по теореме Эйлера х" = 1 (mod п), где (р{п) = (р - 1)(д - 1). Следовательно, посредством двух применений быстрого алгоритма модульного возведения в степень, все

числа Xi =?Жо " " могут быть вычислены эффективно, исходя из начального вектора хо и определяющего каждое из этих чисел индекса г.

§ 6. Вероятностное шифрование

С одной стороны, криптография с открытым ключом в значительной степени решает задачу распространения ключей, которая является довольно серьезной проблемой для криптографии с секретным ключом. А с другой, как мы указывали выше, злоумышленнику при перехвате шифртекста с = £fc(m) в любом случае становится известной некоторая информация об открытом тексте т, поскольку он всегда может без посторонней помощи вычислить значение открытой функции шифрования для любого нужного ему открытого текста. Стало быть, задаваясь по своему выбору сообщением т, он может также легко выяснить, верно ли, что m = т, так как это справедливо только, если Efe(m) = с. Даже если нахождение га из с и в самом деле было бы трудно осуществить при знании только естественного алгоритма шифрования, что пока еще не доказано, ничего нельзя сказать о том, сколь велика и в чем состоит возможная частичная утечка информации об га. Если использовать метафору Шафи Гольдвассер, то применение криптографии с открытым ключом подобно попытке прятать верблюда под одеялом: можно утаить, какой из верблюдов спрятан, но не число его горбов.

Целью вероятностного шифрования - понятия, введенного Шафи Гольдвассер и Сильвио Микэли в [197] - является такое криптографическое преобразование над открытым текстом сообщения, при котором никакое легко выполнимое вычисление на основе шифртекста не может дать какой бы то ни было информации о соответствующем открытом тексте (кроме как, быть может, с пренебрежимо малой вероятностью). Это напоминает системы, являющиеся совершенно секретными в смысле Шеннона, но с дополнительными преимуществами, которые предоставляют короткие ключи, и возможностью для каждого пользователя обнародовать свои открытые алгоритмы шифрования. Конечно, от таких систем нельзя ожидать настоящей совершенной секретности - они в принципе несекретны для криптоаналитика, обладающего неограниченной вычислительной мощностью.

Основное техническое различие между вероятностным шифрованием и системами с открытым ключом состоит в том, что

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

Формально система вероятностного шифрования состоит из пространства ключей К. и, для каждого к€/С, из пространства открытых текстов Мк сообщений, пространства шифртекстов Ск, вероятностного пространства TZk и пары функций Ек-.Мк хИк Ск и DkiCk -> Мк, таких что Dk{Ek{m,r)) = т для любого сообщения открытого текста га € Мк и случайного числа гЕТк- С помощью любого кЕ/С должны легко получаться эффективные естественные алгоритмы для вычисления как Ек, так и Dk, но построение какого-либо эффективного алгоритма вычисления Dk, на основе только естественных алгоритмов вычисления Ек, должно быть практически невозможно.

Использование системы вероятностного шифрования очень похоже на использование систем с открытым ключом.. Каждый пользователь раз и навсегда выбирает для себя ключ kSfC, который используется для получения обоих-естественных алгоритмов вычисления Ек и Dk- Он делает алгоритм шифрования Ек общедоступным, но сохраняет в секрете алгоритм дешифрования Dk- В том случае, когда другой пользователь захочет послать ему свое сообщение га, он находит Ек в справочнике, случайно выбирает некоторое г Е Itk и вычисляет шифртекст с - Ек{т, г). При этом только законный получатель, используя свою секретную лазейку, может легко определить га из с.

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