Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В криптографии , A псевдослучайной перестановки (ПРП) представляет собой функцию , которая не может отличить от случайной перестановки (то есть, перестановка выбирается случайным образом с равномерной вероятностью, из семейства всех перестановок на домен функции в) с практическим усилием.

Определение [ править ]

Пусть F - отображение {0,1} n × {0,1} s → {0,1} n . F является PRP, если

  • Для любого K ∈ {0,1} s , F представляет собой взаимно однозначное соответствие от {0,1} п {0,1} п .
  • Для любого K ∈ {0,1} s существует «эффективный» алгоритм вычисления F K ( x ).
  • Для всех вероятностных различителей за полиномиальное время D: ∣Pr (D F K (1 n ) = 1) - Pr ( D f n (1 n ) = 1) ∣ < ε ( s ), где K ← {0,1} n выбирается равномерно случайным образом, а f n выбирается равномерно случайным образом из набора перестановок на n- битных строках. [1]

Псевдослучайных перестановок семейство представляет собой совокупность псевдослучайных перестановок, где определенная перестановка может быть выбрана с помощью ключа.

Модель блочных шифров [ править ]

Идеализированная абстракция блочного шифра (с ключом) - это действительно случайная перестановка отображений между открытым текстом и зашифрованным текстом. Если существует алгоритм различения, который достигает значительного преимущества с меньшими усилиями, чем указано в параметре безопасности блочного шифра (это обычно означает, что требуемые усилия должны быть примерно такими же, как при поиске методом грубой силы через пространство ключей шифра), то шифр считается сломанным. по крайней мере, с точки зрения сертификации, даже если такое нарушение сразу не приводит к практическому сбою в системе безопасности . [2]

Ожидается, что современные шифры обладают суперпсевдослучайностью. То есть, шифр должен быть неотличим от случайно выбранной перестановки в том же пространстве сообщений, даже если у злоумышленника есть доступ черного ящика к прямому и обратному направлениям шифра. [3]

Связи с псевдослучайной функцией [ править ]

Майкл Луби и Чарльз Ракофф [4] показали, что «сильная» псевдослучайная перестановка может быть построена из псевдослучайной функции с использованием конструкции Луби – Рэкоффа , построенной с использованием шифра Фейстеля .

Понятия, связанные с данным [ править ]

Непредсказуемая перестановка [ править ]

Непредсказуемы перестановки ( UP ) Р к является перестановкой , чьи значения не могут быть предсказаны с помощью быстрой рандомизированного алгоритма . Непредсказуемые перестановки могут использоваться в качестве криптографического примитива , строительного блока для криптографических систем с более сложными свойствами.

Противник для непредсказуемого перестановки определяется как алгоритм , который получает доступ к оракулу для обеих прямых и обратных операций перестановки. Противнику дается входной вызов k и его просят предсказать значение F k . Разрешено сделать серию запросов к оракулу, чтобы помочь ему сделать это предсказание, но не разрешено запрашивать значение самого k . [5]

Рандомизированный алгоритм генерации перестановок генерирует непредсказуемую перестановку, если его выходы представляют собой перестановки на наборе элементов (описываемых двоичными строками длины n ), которые не могут быть предсказаны с точностью значительно лучше, чем случайная, злоумышленником, который делает многочлен (от n ) количество запросов к оракулу до начала раунда вызов, время выполнения которой многочлен в п , и чья вероятность ошибки составляет менее 1/2 всех случаев. То есть его нельзя предсказать в классе сложности PP , релятивизированном оракулом для перестановки. [5]

Свойства непредсказуемых перестановок [ править ]

Можно показать, что функция F k не является кодом аутентификации безопасного сообщения (MAC), если она удовлетворяет только требованию непредсказуемости. Также можно показать, что невозможно построить эффективный MAC с переменной входной длиной из блочного шифра, который моделируется как UP из n битов. Было показано, что результат раундовой конструкции Фейстеля с k  =  n / ω (log  λ ) с непредсказуемыми циклическими функциями может привести к утечке всех промежуточных циклических значений. [5]Даже для реалистичных непредсказуемых функций (UF) некоторая частичная информация о промежуточных значениях раунда может просочиться через выходные данные. Позже было показано, что если используется суперлогарифмическое количество раундов в конструкции Фейстеля, то результирующая конструкция UP безопасна, даже если противник получает все промежуточные значения раундов вместе с выходом перестановки. [6]

Существует также теорема, которая была доказана в этом отношении, которая утверждает, что если существует эффективный противник UP A π, который имеет существенное преимущество ε π в игре на непредсказуемость против конструкции UP ψ U, k и который составляет полиномиальное число запросы к претенденту, то также существует противник A f UF, который имеет существенное преимущество в игре на непредсказуемость против UF, взятого из семейства F UF  . Отсюда можно показать, что максимальное преимущество противника UP A π равно ε π = O ( ε f . ( Qk) 6 ). Здесь ε f обозначает максимальное преимущество противника UF, работающего за время O ( t + ( qk ) 5 ), против UF, взятого из F , где t - время работы злоумышленника PRP A ψ, а q - количество сделанных запросов. этим. [6] [7]

Кроме того, схема подписи, которая удовлетворяет свойству непредсказуемости и не обязательно псевдослучайности, по сути, является проверяемой непредсказуемой функцией (VUF). Проверяемая непредсказуемая функция определяется аналогично проверяемой псевдослучайной функции (VRF), но псевдослучайность заменяется более слабой непредсказуемостью. Проверяемые непредсказуемые перестановки являются аналогами перестановок VUF или непредсказуемыми аналогами VRP. VRP также является VUP, и на самом деле VUP может быть построен путем создания VRP с помощью конструкции Фейстеля, примененной к VRF. Но это не считается полезным, так как VUF кажутся намного проще в построении, чем VRF. [8]

Приложения [ править ]

  • DES
K x X → X ∀ X = {0,1} 64 , K = {0,1} 56
  • AES-128
K x X → X ∀ k = X = {0,1} 128.

См. Также [ править ]

  • Блочный шифр (семейства псевдослучайных перестановок, работающие с блоками битов фиксированного размера)
  • Шифрование с сохранением формата (семейства псевдослучайных перестановок, работающие с произвольными конечными наборами)

Ссылки [ править ]

  1. ^ Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы . Чепмен и Холл / CRC. ISBN 978-1584885511.
  2. ^ Mihir Bellare , Филлип Рогауэй (2005-05-11). «Глава 4: Псевдослучайные функции» (PDF) . Введение в современную криптографию . Проверено 18 мая 2020 .
  3. ^ Крейг Джентри и Зульфикар Рамзан. "Устранение оракулов случайной перестановки в шифре четного Мансура" .
  4. ^ Луби, Майкл; Рэкофф, Чарльз (1988). «Как построить псевдослучайные перестановки из псевдослучайных функций» . SIAM J. Comput . 17 (2): 373–386. DOI : 10.1137 / 0217022 .
  5. ^ a b c Пуния, Прашант (2007), Новые критерии проектирования для хэш-функций и блочных шифров (PDF) , Ph.D. диссертация, факультет компьютерных наук, Нью-Йоркский университет .
  6. ^ a b Достижения в криптологии - EUROCRYPT 2007: 26-я ежегодная международная конференция по теории и применению криптографических методов - Мони Наор, Международная ассоциация криптологических исследований
  7. ^ http://cs.nyu.edu/~puniya/papers/public_feistel.pdf
  8. ^ Микали, Сильвио ; Рабин, Майкл ; Вадхан, Салил (1999), «Проверяемые случайные функции», 40-й ежегодный симпозиум по основам компьютерных наук (Нью-Йорк, 1999) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 120–130, CiteSeerX 10.1.1.207.6638 , DOI : 10,1109 / SFFCS.1999.814584 , ISBN  978-0-7695-0409-4, Руководство по ремонту  1917552 , S2CID  221565852.