Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Первый шаг к обоснованию криптографически сильных генераторов был сделан Эди Шамиром [316]. Впоследствии Мануэлем Блюмом и Сильвио Микэли в [57] было введено ключевое понятие псевдослучайных генераторов — так называемая непре-дикативностъ влево — когда криптоаналитик, который знает, как работает генератор, но не знает, какой исходный вектор используется при его работе, для того чтобы угадать первый бит, выработанный генератором, не может найти ничего лучшего, чем после анализа всей сгенерированной в результате последовательности, подбросить жребий (если, конечно, ему при этом анализе не слишком повезет, или если он не окажется в состоянии проделать практически невыполнимые вычисления). Как и обычно,
Генерац.ия1гсевдоелучайных чисел 63
мы не знаем, существуют ли подобные генераторы, но первый кандидат на такой генератор был предложен Блюмом и Мик-эли [57}, которые доказали, что их генератор является непредикативным влево в предположении, что вычисление дискретных логарифмов является практически трудноосуществимым. То, что введение понятия непредикативности генераторов влево было вполне уместно, установил Эндрю Яо, доказав, что любой такой генератор является криптографически сильным [364]. Наконец, Леонид Левин дал необходимые и достаточные условия для существования подобных генераторов [250]. См. также [219, 211].
Сейчас мы приведем описание более простого и в вычислительном отношении более эффективного кандидата на криптографически сильный псевдослучайный генератор, который известен как BBS-генератор, названный так в честь Леоноры Блюм, Мануэля Блюма и Майка Шуба [49]. Он основывается на нашем втором кандидате на однонаправленную функцию с потайным ходом, который был преставлен в § 1. Напомним, что п называется целым числом Блюма, если оно является произведением двух различных простых чисел р и q, оба из которых сравнимы с числом 3 по модулю 4. Напомним также, что в данном случае функция возведения в квадрат по модулю п является перестановкой квадратичных вычетов по модулю числа п, и считается, что она является однонаправленной функцией с потайным ходом, так как было доказано, что трудность ее обращения (то есть вычисления примитивных квадратных корней по модулю тг) вычислительно эквивалентна разложению п на множители. В предположении, что факторизация числа п является трудной задачей, может быть доказана даже более сильная теорема: для почти всех квадратичных вычетов у по модулю п, то есть у = х2 mod гг, к наилучшей (из всех возможных) выполнимой оценке того, каким должен быть первый значащий разряд х, приводит лишь подбрасывание жребия [349, 350, 8, 117]. Другими словами, оказывается, что практически трудно не только вычислить сам примитивный квадратный корень, но даже получить вероятностную информацию о его первом значащем бите (наподобие следующей: «Я не убежден, но мне все-таки кажется, что этот бит больше похож на нуль, чем на единицу»).
Теперь мы готовы описать BBS-генератор и доказать, что при
64 Системы с открытым ключом
Глава 4
соответствующем предположении он является криптографически сильным. Пусть тг — целое число Блюма с неизвестным разложением на множители. Возьмем в качестве исходного числа случайным образом выбранный квадратичный вычет х0 (для того, чтобы это сделать, выберем наугад целое х взаимно простое с п, а хо вычислим как хо = х2 mod п). Для г 0 определим Х{ рекурсивно по формуле x,-+i = х2 mod п и обозначим через 6,- первый значащий бит а;,-. Тогда для любого целого t первые t битов, которые таким образом будут сгенерированы из xq , мы и объявим искомой псевдослучайной последовательностью BBSnit{xо) = 60&1&2 • • -bt-1-
Когда мы говорим, что BBS-генератор непредикативен влево, то это означает, что никто не может отгадать 6о, основываясь лишь на знании п и 6162 .. Если бы это было не так,
то первый значащий бит неизвестного примитивного квадратного корня х любого заданного квадратичного вычета у можно было бы определить следующим образом. Сначала вычислим псевдослучайную последовательность BBSn:t-i{y).n объявим, что она на самом деле является последовательностью BBSntt(x) с удаленным первым битом. Затем отгадаем этот пропущенный бит и отметим, что по определению он и является тем самым первым значащим битом х, который мы искали. Из этого следует, что BBS-генератор должен быть непредикативен влево в предположении, что факторизация целого числа п является трудной задачей. Следовательно, по теореме Яо, такой генератор будет криптографически сильным.
Дополнительное привлекательное свойство этого генератора заключается в том, что для всех, кто знает разложение п на множители, он допускает прямое определение тех отдельных битов, которые в нем вырабатываются. Для этого заметим, что х,- = Xq mod п. Но по теореме Эйлера
__ 1 (mod п), где
<р(п) — (р — 1)(<7 — 1). Следовательно, посредством двух применений быстрого алгоритма модульного возведения в степень, все числа Xi =? хq mod mod п могут быть вычислены эффективно, исходя из начального вектора хо и определяющего каждое из этих чисел индекса г.
