06.12.2020 22:04
xcsmwtf 4 1500 Источник

В 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.

Конец

На этом я закончу свою статью. Спасибо большое всем, кто дочитал.

P.S. Случайности не случайны. Случайностей вообще нет, развитие вселенной было определено ещё на момент её появления. Не воспринимайте это всерьёз, пожалуйста c:

P.P.S. Кто нашёл пасхалку – большой молодец.

Материалы

How to Construct Random Functions – тык

Pseudorandom Functions: Three Decades Later – тык

Introduction to Modern Cryptography – тык

Pseudorandom Functions and Block Ciphers – тык