Псевдовипадкова перестановка

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Псевдовипадкова перестановка (англ. pseudorandom permutation), PRP — це функція, яку неможливо за допомогою розумних зусиль відрізнити від випадкової перестановки (тобто від перестановки обраної випадково й однорідно з сім'ї всіх перестановок на домені функції).

Сім'я випадкових перестановок — це множина псевдовипадкових перестановок, де можна обрати певну перестановку використовуючи ключ.

Ідеалізована абстракція блочного шифру є насправді випадковою перестановкою. Якщо існує алгоритм здатний розрізнити із досягненням значної переваги з меншими зусиллями ніж вказані параметром безпеки блочного шифра (це зазвичай значить, що потрібні зусилля мають бути на рівні повного перебору по простору можливих ключів шифру), тоді шифр вважається зламаним щонайменше в сенсі сертифікації, навіть якщо така вада і не призводить до негайного практичного краху безпеки.

Як приклади безпечних псевдовипадкових перестановок можна навести 3DES, AES.

Математичне визначення[ред.ред. код]

Псевдовипадкова перестановка (PRP) визначена на (K,X) це функція E: K \times  X \to X, така що:

  1. Існує дієвий детерміністичний алгоритм для обчислення E(k, x)
  2. Функція E(k, \cdot) є бієкцією (один до одного)
  3. Існує дієвий зворотний алгоритм D(k, x)

Безпечність псевдовипадкової перестановки[ред.ред. код]

Для b = 0,1 розглянемо досліди EXP(b).

b = 0 : K \to k, E(k, \cdot) \to f

b = 1 : Perms[X] \to f

Супротивник (англ. adversary) A виконує q запитів x_1, x_2, ... x_q \in X і отримує q відповідей f(x_1), f(x_2), ... f(x_q). По вивчені відповідей ціллю супротивника є вказати з якої саме множини вибрали функцію.

Отже, E є захищеною PRP, якщо для будь-якого ефективного супротивника A перевага: Adv_{PRF}[A, E] := \begin{vmatrix} Pr[EXP(0) = 1] - Pr[EXP(1) = 1] \end{vmatrix} не значима.

Див. також[ред.ред. код]

Примітки[ред.ред. код]