Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Итак, можно предположить, что вычисление функции в этой задаче порождает п разных и равновероятных точек. Эти вычисления можно отождествить с извлечением шара из урны, содержащей п разноцветных шаров, после чего цвет записывается, и шар возвращается в урну. Следовательно, задача заключается в поиске такого числа к, при котором какой-нибудь цвет повторялся бы с вероятностью е.
На цвет первого шара не налагаются никакие ограничения. Пусть у$ — цвет шара, извлеченного при г-й попытке. Цвет второго шара не должен совпадать с цветом первого шара, поэтому вероятность того, что у2 ф уъ равна 1 — вероятность того, что уз ф у\ и уз ф уг, равна 1 — ^ и т.д. При извлечении /с-го шара вероятность того, что до этого не возникнет коллизия, равна
(* п) (* п) "" {} п ) '
При достаточно большом числе п и относительно малом числе х выполняется следующее соотношение.
или
п
Итак,
Полученное число представляет собой вероятность извлечь к шаров без коллизии. Следовательно, вероятность возникновения по крайней мере одной коллизии равна
Приравнивая эту величину к числу е, получаем
108
Часть II. Математические основы
или
к2 — к Ft 2п log
1
1-е
Иначе говоря,
km л/2nlog
1
(3.6.1)
1-е
Итак, для случайной функции, отображающей множество X на множество Y,
наружить коллизию с заданной вероятностью е. Из соотношения (3.6.1) вытекает, что даже если число е достаточно велико (т.е. очень близко к единице), величина
Зависимость числа к от величины п, продемонстрированная формулами (3.6.1) и (3.6.2), означает, что для случайной функции, пространство исходов которой состоит из п точек, чтобы обнаружить коллизию со значимой вероятностью, необходимо выполнить всего у/п вычислений.
Этот факт оказал значительное влияние на разработку криптосистем и криптографических протоколов. Например, если квадратный корень, извлеченный из размера фрагмента данных (скажем, криптографического ключа или сообщения), скрытого в качестве прообраза криптографической функции (которая, как правило, является случайной), не является достаточно большой величиной, данные можно расшифровать с помощью случайных вычислений значений функции. Такая атака получила название атака по методу квадратного корня (square-root attack), или атака на основе "парадокса дней рождений" (birthday attack). Второе название возникло из-за внешне парадоксального явления: положив п = 365 в формуле (3.6.5), мы получим к и 22,49. Иначе говоря, для того, чтобы с вероятностью более 50% обнаружить двух людей, родившихся в один и тот же день и находящихся в комнате, заполненной случайными людьми, достаточно, чтобы в комнате было всего лишь 23 человека. Эта величина кажется слишком маленькой по сравнению с интуитивно ожидаемой.
3.6.1 Применение парадокса дней рождений: алгоритм кенгуру Полларда для индексных вычислений
Пусть р — простое число. При определенных условиях (которые станут очевидными в главе 5), функция возведения в степень по модулю (modulo exponentiation) f(x) = ^(modp) является, по существу, случайной. Иначе говоря, для чисел а; = 1,2, ...,р— 1 значения f(x) случайным образом разбросаны по всему
необходимо выполнить по крайней мере к
вычислений, чтобы об-
Глава 3. Теория вероятностей и теория информации
109
интервалу [1,р — 1]. Эта функция широко применяется в криптографии, поскольку она является однонаправленной: вычислить у = f(x) очень легко (используя алгоритм 4.3), однако найти обратную функцию, т.е. вычислить х = /_1(у), чрезвычайно трудно для практически всех значений у 6 [1,р — 1].
Иногда для значения у = f(x) известно, что х 6 [а, Ь] при некоторых значениях а и Ь. Очевидно, что, вычисляя значения /(а), /(а + 1), можно найти число х не более чем за Ь — а шагов. Если число Ь — а слишком велико, то такой метод перебора является непрактичным. Однако, если число л/Ъ — а не слишком велико (например, если Ь — а rs 2100, то л/Ъ — а 250, что является вполне разумной величиной), то при обращении функции f(x) за Ъ — а шагов проявляется парадокс дней рождений. Используя этот факт, Поллард изобрел метод индексных вычислений [238], получивший название А-метод или метод кенгуру (kangaroo method). Смысл этих названий станет ясен позднее.
Поллард описал свой алгоритм, используя в качестве персонажей двух кенгуру — домашнего, Т, и дикого, W. Задача вычисления индекса х с помощью функции у = ^(modp) сводилась к ловле кенгуру W с помощью кенгуру Т. Эту задачу можно решить, позволив обоим кенгуру прыгать вокруг по определенным траекториям. Пусть S — множество целых чисел, состоящее из J элементов (J = Llog2(6 — a)J, а значит, является достаточно малым числом):
S = {в(0), s(l), e(2), ...,s(J— 1)} = {2°, 2\.. -, 2-7-1}.
Каждый раз один из кенгуру прыгает на расстояние, которое случайным образом извлекается из множества S, причем общее расстояние, пройденное каждым из кенгуру, регистрируется с помощью счетчика.
Кенгуру Т начинает свой путь из известной точки to = g6(modp). Поскольку кенгуру Т является домашним, в качестве его дома можно рассматривать точку Ь. Его путь описывается следующей формулой.
