Псевдослучайные функции и их применение

Семейство псевдослучайных функций может быть построено из любого псевдослучайного генератора, используя, например, конструкцию «GGM», данную Голдрайхом, Гольдвассером и Микали. Хотя на практике блочные шифры используются большую часть времени, когда требуется псевдослучайная функция, они, как правило, не составляют семейство псевдослучайных функций, потому что блочные шифры, такие как AES, только определены. для ограниченного количества записей и размеров ключей.

Псевдослучайные функции и их применение

В 1984 году Голдрайх, Гольдвассер и Микали формализовали концепцию псевдослучайных функций и предложили реализацию PRF, основанную на псевдослучайном генераторе удвоения длины (PRG). С тех пор псевдослучайные функции оказались чрезвычайно важной абстракцией, которая нашла применение в различных областях, таких как аутентификация сообщений и доказательство теорем.

 В этой статье мы расскажем:

  • Что из себя представляют случайные функции (RF)

  • Что из себя представляют псевдослучайные функции (PRF)

  • Кто же такие эти ваши семейства

  • PRF vs. PRG

  • При чём тут блочные шифры

Случайность

Уже из названия становится понятно, что псевдослучайная функция — это нечто «выглядящее» как случайная функция. Ну а что такое случайная функция в нашем случае? Для начала ограничим нашу область рассмотрения функциями отображающими строку из нулей и единиц длиной n в строку из нулей и единиц такой же длины n, то есть

\underbrace{1110...0010}_{n} \rightarrow \underbrace{0100...0011}_{n} \Leftrightarrow \{0,1\}^n \rightarrow \{0,1\}^n

Этого, вообще говоря, можно и не делать, и рассматривать отображения строк одной длины в строки другой длины, но в этом случае придётся уделять внимание различиям в размерности. Далее введём множество всех функций, выполняющих отображение \{0,1\}^n \rightarrow \{0,1\}^nи обозначим его \text{Func}_n.

Рассмотрим мощность этого множества. Очевидно, что |{\text{Func}_n}| = 2^{n2^n}.

\text{Всего различных строк длины } n \space - \space 2^n. \text{ Чтобы хранить } 2^n \text{ строк понадобится } n2^n \text{ бит.}\text{Эти } n2^{n} \text{ бит и будут задавать искомое отображение } 2^n \text{ строк.}\text{И всего таких отображений будет } 2^{n2^n}.

Теперь мы можем определить случайную функцию. Случайная функция – это любая случайно выбранная функция из \text{Func}_n. Проще говоря, мы берём наши 2^nстрок и каждой сопоставляем какую-то из тех же 2^nстрок. Причем сопоставление происходит с равномерным распределением, то есть

P(f(x)=y_0)=2^{-n}

Где f – функция из \text{Func}_n, а y_0 – фиксированная точка.

Псевдослучайность

Интуитивно, псевдослучайность – это что-то выглядящее, как случайность. И формальное определение так и вводится, только похожесть псевдослучайной функции на случайную определяется строго.

Давайте выпишем несколько равенств, верных для случайной функции:

P(f(x) \in \{ \forall y:первый \space бит = 1 \}) = \frac{1}{2}

Почти то же самое, но для наших целей вполне сгодится:

P(f(x) \in \{ \forall y:последний \space бит = 1 \}) = \frac{1}{2}

Для чётных nможно выписать следующее:

P(f(x) \in \{ \forall y:число \space нулей= число \space единиц \}) = \frac{1}{2^n} \begin{pmatrix} n \\ n/2 \end{pmatrix}

Где \begin{pmatrix} n \\ n/2 \end{pmatrix} – число сочетаний из n по n/2 (нужно выбрать n/2 позиций из n возможных).

Подобных равенств можно выписать очень много. Скажем, к примеру, что мы придумали 20 таких равенств. Назовём их тестами и обозначим следующим образом:

P(A_i(f(x))=1)

Тогда можно определить псевдослучайною функцию, как функцию, которая удовлетворяет тестам с заданной точностью \varepsilon:

|P(A_i(f(x))=1)-P(A_i(F(x))=1)| < \varepsilon

Где f(x) – случайная функция, а F(x) – функция, которую мы тестируем.

Но у такого определения есть существенный минус. Что если у кул-хацкера, который пытается вытащить полезную информацию из результата работы псевдослучайной функции, есть тест, которого нет у нас? Вероятно, для него эта функция окажется не такой уж и случайной. Поэтому введём несколько иное определение псевдослучайной функции.

Назовём функцию F(t,\varepsilon)-псевдослучайной, если для любого теста A с полиномиальной сложностью, выполнение которого занимает времени не более чем t верно

|P(A(f(x))=1)-P(A(F(x))=1)| < \varepsilon

Семейства

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

Семейство псевдослучайных функций – это эффективно вычислимая функция двух переменных F_k(x)=F(k,x), такая, что \{0,1\}^m \times \{0,1\}^n \rightarrow \{0,1\}^l, где каждая из F_k является псевдослучайной. Переменная k называется ключом функции.

Положим далее m=l=n.

Стоит отметить, что выбор конкретного k эквивалентен выбору конкретной функции из семейства.

В начале статьи мы обсудили множество всех функций выполняющих отображение \{0,1\}^n \rightarrow \{0,1\}^n и обозначили его \text{Func}_n. Так вот, получается что семейство F_k задаёт распределение над множеством \text{Func}_n.

Определение, данное выше, можно переформулировать в более привычный вид, в котором оно в основном встречается в статьях и учебниках:

F_k называется семейством псевдослучайных функций, если для случайного k ни один эффективный алгоритм D с полиномиальной временной сложностью не сможет отличить F_k от f \in \text{Func}_n.

Наглядное пояснение

Вероятно, так будет проще осознать, что же в конечном итоге представляет из себя это семейство. Пусть есть две черных коробки, которые могут принимать на вход битовые строки и в ответ выдавать какие-то другие битовые строки. Примем, что на входе и на выходе коробок строки имеют определённую одинаковую длину. Отмечу, что выход этих коробок определяется только строкой на входе. То есть не может быть такого, что мы подали на вход какой-то коробки x_0 и на выходе получили y_0, а потом, через некоторое время, мы снова подали на вход x_0, но на выходе получили y_1 \neq y_0. Пусть также есть злой хацкер, которому позарез нужно понять, какая из этих двух коробок скрывает в себе труЪ-случайную функцию, а какая просто притворяется. Этот хацкер может делать с этими коробками всё, что угодно. То есть подавать строки и считывать. Так вот, если тот, кто придумывал F_k, сделал всё правильно, то при случайно выбранном k у хацкера ничего не выйдет (за вменяемое время).

PRF vs. PRG

PRG – это псевдослучайный генератор. Звучат названия достаточно похоже, но путать их не стоит. Эти два понятия можно связать, получив из PRG – PRF, а из PRF – PRG. Почитать подробно, что такое PRG, можно тут. Если вкратце, то PRG это эффективно вычислимая функция (алгоритм), принимающая на вход случайную битовую строку длины n (seed) и выдающая псевдослучайную битовую строку длины m>n. Почитать про то, как получить из PRG семейство псевдослучайных функций с доказательством того, что полученная конструкция действительно PRF можно в работе, упомянутой в самом начале статьи. А вот в обратную сторону всё намного проще. Достаточно положить

G(k)=F_k(0...0)|F_k(0...1)

Где | – операция конкатенации, и мы получим простейший пример получения PRG из PRF. Очевидно, что подобных примеров можно придумать очень много. Отсюда напрашивается логичный вывод, что PRF понятие более мощное, нежели PRG.

Про блочные шифры

Наделив нашу PRF F_k парой дополнительных свойств мы получим ещё одну интересную абстракцию, называемою псевдослучайными перестановками. Для того, чтобы стать семейством псевдослучайных перестановок, F_k должна быть биективной и эффективно вычислимой в обоих направлениях для всех значений k. То есть задача вычисления F^{-1}(y) должна иметь единственный верный ответ и не должна составлять для нас особого труда.

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

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

Заключение

Случайность имеет множество применений в науке, искусстве, статистике, криптографии, играх, азартных играх и других областях. Например, случайное распределение в рандомизированных контролируемых испытаниях помогает ученым проверять гипотезы, а случайные и псевдослучайные числа также используются в видеоиграх, таких как видеопокер.
Такие приложения имеют разные уровни требований, что приводит к использованию разных методов. Математически существуют различия между рандомизацией, псевдослучайным и квазирандомизационным, а также между генератором случайных чисел и генератором псевдослучайных чисел. Например, криптографические приложения, как правило, предъявляют строгие требования, в то время как другие применения (например, создание «котировок дня») могут использовать более свободный стандарт псевдослучайности.

 

 

 

Click to rate this post!
[Total: 0 Average: 0]

Leave a reply:

Your email address will not be published.