Псевдослучайная функция Наора — Рейнгольда — , введённая в 1997 году и для построения различных криптографических примитивов в симметричном шифровании и криптографии с открытым ключом. Отличительными особенностями данной псевдослучайной функции являются низкая вычислительная сложность и высокая криптографическая стойкость. Данные свойства вместе с тем фактом, что распределение значений данной функции близко к равномерному, позволяют использовать ее в качестве основы для многих криптографических схем.
Постановка В криптографии под семейством псевдослучайных функций понимают набор функций (которые могут быть эффективно вычислены за полиномиальное время), обладающих следующим свойством: злоумышленник не может эффективно найти какое-либо существенное различие между поведением функции из данного семейства и истинной случайной функции. Пусть — это -битное простое число, — простое число, являющееся делителем , а , — некоторый элемент с мультипликативным порядком по модулю . Тогда функция Наора — Рейнгольда определяется некоторым -мерным вектором над полем и равна:
где — это двоичное представление целого числа , с добавлением ведущих нулей, если это необходимо.
Пример Пусть и . В качестве с мультипликативным порядком можно выбрать . Тогда при , и функция вычисляется как
Так как двоичное представление числа — это .
Вычислительная сложность Построение псевдослучайной функции Наора — Рейнгольда требует умножений по модулю и одно возведение в степень по модулю , которое может быть сделано за умножений по этому модулю.
Для данной функции было показано, что существует такой полином , что для любого , может быть реализована схемой из пороговых элементов глубины и размера, не превышающего . Это означает, что функции Наора — Рейнгольда принадлежит в терминах .
Применение Псевдослучайная функция Наора — Рейнгольда может быть использована в качестве основы многих криптографических схем, включая симметричное шифрование, аутентификацию и электронные подписи.
Также было показано, что данная функция может быть использована в:
: даже если злоумышленник может изменить распределение ключей в зависимости от значений, которые функция хеширования присвоила предыдущим ключам, он не сможет умышленно вызвать коллизии. построении схем аутентификации на основе имитовставки, которые надёжно защищены от атак. выдаче статичных идентификационных номеров, которые могут быть проверены устройствами, располагающими лишь небольшим объёмом памяти. построении систем радиолокационного опознавания.
Безопасность Псевдослучайная функция Наора — Рейнгольда имеет высокую криптографическую стойкость. Пусть злоумышленнику известны значения функции в нескольких точках: и ему необходимо вычислить . Если , то чтобы получить , злоумышленнику необходимо решить для и . Но по не существует эффективного алгоритма, способного решить данную задачу.
Поток чисел, генерируемый псевдослучайной функцией, также должен быть непредсказуемым, то есть, он должен быть неотличим от совершенно случайного набора чисел. Пусть обозначает алгоритм, имеющий доступ к оракулу, который вычисляет . Предположим, что выполняется для . Тогда для любого вероятностного полиномиального алгоритма и достаточно большого выполнено:
, где — пренебрежимо мало.
Первая вероятность равна доле наборов , на которых алгоритм выдаёт единицу, а вторая получается из случайного выбора пары и функции среди множества всех функций .
Линейная сложность Одним из естественных показателей того, насколько последовательность может быть полезной для криптографических целей, является её линейная сложность. Линейная сложность -элементной последовательности , над кольцом — это длина кратчайшего линейного рекуррентного соотношения , где . Для функции Наора — Рейнгольда было показано, что существуют такие и , что для любого и достаточно большого линейная сложность последовательности , , удовлетворяет следующему неравенству:
для всех, кроме не более чем векторов .
Равномерность распределения Статистическое распределение экспоненциально близко к равномерному распределению почти для всех векторов :
пусть — множества или, другими словами, отклонение распределения значений псевдослучайной функции от равномерного распределения. Было показано, что если — это битовая длина , тогда для всех векторов ∈ справедливо неравенство , где:
и .
Это свойство не имеет непосредственного криптографического значения, но если бы оно не было выполнено, это могло бы повлечь катастрофические последствия для применения функции.
Последовательности на эллиптической кривой Анализ этой функции на эллиптической кривой позволяет улучшить криптографическую стойкость соответствующей системы. Пусть — простое число и — эллиптическая кривая над . Тогда любой вектор определяет конечную последовательность в циклической группе , где — битовое представление , , — некоторый элемент на с мультипликативным порядком , а — это операция возведения элемента в степень относительно групповой операции в абелевой группе -рациональных точек эллиптической кривой. В таких обозначениях последовательность Наора — Рейнгольда на эллиптической кривой определяется как , где обозначает абсциссу точки .
Если предположение Диффи — Хеллмана выполнено, то индекса не достаточно для вычисления за полиномиальное время. Для эллиптической кривой Наора — Рейнгольда было показано, что существуют такие и , что для любого и достаточно большого линейная сложность последовательности удовлетворяет следующему неравенству:
для всех, кроме не более чем векторов .
См. также Симметричные криптосистемы Конечное поле Инверсный конгруэнтный метод Криптосистема с открытым ключом
Примечания
Категория:Генераторы псевдослучайных чисел Категория:Криптография