Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Вероятностное шифрование 65
§ 6. Вероятностное шифрование
С одной стороны, криптография с открытым ключом в значительной степени решает задачу распространения ключей, которая является довольно серьезной проблемой для криптографии с секретным ключом. А с другой, как мы указывали выше, злоумышленнику при перехвате шифртекста с = Ек(т) в любом случае становится известной некоторая информация об открытом тексте то, поскольку он всегда может без посторонней помощи вычислить значение открытой функции шифрования Ек для любого нужного ему открытого текста. Стало быть, задаваясь по своему выбору сообщением т, он может также легко выяснить, верно ли, что то = 771, так как это справедливо только, если Ек{т) = с. Даже если нахождение m из с и в самом деле было бы трудно осуществить при знании только естественного алгоритма шифрования, что пока еще не доказано, ничего нельзя сказать о том, сколь велика и в чем состоит возможная частичная утечка информации об т. Если использовать метафору Шафи Гольдвассер, то применение криптографии с открытым ключом подобно попытке прятать верблюда под одеялом: можно утаить, какой из верблюдов спрятан, но не число его горбов.
Целью вероятностного шифрования — понятия, введенного Шафи Гольдвассер и Сильвио Микэли в [197] — является такое криптографическое преобразование над открытым текстом сообщения, при котором никакое легко выполнимое вычисление на основе шифртекста не может дать какой бы то ни было информации о соответствующем открытом тексте (кроме как, быть может, с пренебрежимо малой вероятностью). Это напоминает системы, являющиеся совершенно секретными в смысле Шеннона, но с дополнительными преимуществами, которые предоставляют короткие ключи, и возможностью для каждого пользователя обнародовать свои открытые алгоритмы шифрования. Конечно, от таких систем нельзя ожидать настоящей совершенной секретности — они в принципе несекретны для криптоаналитика, обладающего неограниченной вычислительной мощностью.
Основное техническое различие между вероятностным шифрованием и системами с открытым ключом состоит в том, что
66 Системы с открытым ключом
Глава 4
естественные алгоритмы шифрования являются при этом вероятностными, а не детерминированными: одно и то же сообщение открытого текста может привести к возникновению большого числа различных шифртекстов. В результате криптоаналитик, имеющий, по его предположению, истинный открытый текст, не сможет долго проверять свою догадку посредством шифрования этого открытого текста (с помощью естественного алгоритма его законного получателя) и последующего сравнения получившегося результата с перехваченным шифртекстом.
Формально система вероятностного шифрования состоит из пространства ключей К- и, для каждого kS/C, из пространства открытых текстов Лik сообщений, пространства шифртекстов С к, вероятностного пространства TZk и пары функций Ек-Mu х71к Ск и Dk-Ck —> Мк, таких что ?)fc(?fc(m,r)) = т для любого сообщения открытого текста т 6 Мк и случайного числа г 6 7Zk ¦ С помощью любого к?/С должны легко получаться эффективные естественные алгоритмы для вычисления как Ек, так и Dk, но построение какого-либо эффективного алгоритма вычисления Dk, на основе только естественных алгоритмов вычисления Ек, должно быть практически невозможно.
Использование системы вероятностного шифрования очень похоже на использование систем с открытым ключом.. Каждый пользователь раз и навсегда выбирает для себя ключ к?/С, который используется для получения обоих -естественных алгоритмов вычисления Ек и Dk- Он делает алгоритм шифрования Ек общедоступным, но сохраняет в секрете алгоритм дешифрования Dk¦ В том случае, когда другой пользователь захочет послать ему свое сообщение ш, он находит Ек в справочнике, случайно выбирает некоторое г 6 7Zk и вычисляет шифртекст с— Ек(т,г). При этом только законный получатель, используя свою секретную лазейку, может легко определить т из с.
Вследствие того, что при использовании вероятностного шифрования каждому открытому тексту соответствует довольно большое количество шифртекстов, неизбежно происходит некоторое раскрытие данных: шифртекст всегда длиннее, чем соответствующий ему открытый текст. Заметим, что для криптосистемы RSA, это было не так. Несмотря на все свои замечательные теоретические свойства, оригинальная система вероят-
Вероятностное шифрование 67
ностного шифрования Гольдвассер-Микэли допускала столь существенное раскрытие данных, что не имела большого практического значения. Поэтому мы не будем описывать ее здесь.
Тем не менее, вероятностное шифрование достигло такого состояния, что уже в настоящее время существует криптосистема даже более эффективная, чем RSA. Для обеспечения конфиденциальности (но не аутентификации — см. § 5.1) механизмы работы этой системы Блюма-Гольдвассер, которая описывается ниже, являются наилучшими из того, что наука в настоящее время может предложить. Система основана на вере в то, что возведение в квадрат по модулю целого числа Блюма — однонаправленная функция с потайным ходом (см. последний пример из § 1), и на том, что псевдослучайный битовый генератор, который был описан в § 5, является криптографически сильным. Естественно, в качестве такого генератора для получения псевдослучайного одноразового шифра необходимой длины из его собственного случайным образом выработанного исходного вектора отправителем сообщения используется BBS-генератор. Способность законного получателя вычислять квадратные корни (основанная на его личной информации о соответствующем потайном ходе) позволяет ему найти этот шифр, а затем с его помощью определить открытый текст.
