WikiSort.ru - Не сортированное

Неразличимость для атак на основе подобранного открытого текста (IND-CPA)

Для вероятностного алгоритма асимметричного шифрования ключей неразличимость в смысле IND-CPA^[2] определяется следующей игрой между злоумышленником и испытателем. Для систем, основанных на вычислительной безопасности, злоумышленник моделируется вероятностной полиномиальной машиной Тьюринга, что означает, что он должен завершить игру и выдать догадку за полиномиальное число временных шагов. В этом определении E(PK, M) представляет шифротекст сообщения M , полученный с использованием ключа PK:

1. Испытатель генерирует пару ключей PK, SK на основе некоторого параметра безопасности k (например, размер ключа в битах) и публикует PK злоумышленнику. Испытатель сохраняет SK.
2. Злоумышленник может выполнить полиномиально ограниченное число шифрований или других операций.
3. В конце концов, злоумышленник представляет два отдельных открытых текста ${\displaystyle \scriptstyle M_{0},M_{1}}$ испытателю.
4. Испытатель выбирает бит b ${\displaystyle \scriptstyle \in }$ {0, 1} случайным образом и посылает испытываемый шифротекст C = E(PK, ${\displaystyle \scriptstyle M_{b}}$ ) обратно злоумышленнику.
5. Злоумышленник может выполнять любое количество дополнительных вычислений или шифрований. Наконец, он выводит просто значение b.

Криптосистема надёжна в смысле IND-CPA, если любой вероятный злоумышленник за полиномиальное время имеет лишь незначительное "преимущество" в различении шифротекстов над случайным угадыванием. Злоумышленник имеет незначительное "преимущество", если он выигрывает вышеупомянутую игру с вероятностью ${\displaystyle \scriptstyle \left({\frac {1}{2}}\right)\,+\,\epsilon (k)}$ , где ${\displaystyle \scriptstyle \epsilon (k)}$ – пренебрежимо малая функция для параметра безопасности k, то есть для любой (ненулевой) полиномиальной функции ${\displaystyle \scriptstyle poly()}$ , у которой существует ${\displaystyle \scriptstyle k_{0}}$ , такой что ${\displaystyle \scriptstyle |\epsilon (k)|\;<\;\left|{\frac {1}{poly(k)}}\right|}$ для всех ${\displaystyle \scriptstyle k\;>\;k_{0}}$ .

Несмотря на то, что злоумышленник знает ${\displaystyle \scriptstyle M_{0}}$ , ${\displaystyle \scriptstyle M_{1}}$ и PK, вероятностный характер E означает, что шифротекст ${\displaystyle \scriptstyle M_{b}}$ будет лишь одним из многих допустимых шифротекстов, а, следовательно шифрование ${\displaystyle \scriptstyle M_{0}}$ , ${\displaystyle \scriptstyle M_{1}}$ и сравнение полученных шифротекстов с шифротекстом испытателя на даёт злоумышленнику какого-либо существенного преимущества.

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

Неразличимость для атак на основе подобранного шифротекста/адаптивных атак на основе подобранного шифротекста (IND-CCA1, IND-CCA2)

Безопасность в смысле IND-CCA1 и IND-CCA2^[1] определяется аналогично надёжности системы в смысле IND-CPA. Однако, в дополнение к открытому ключу (или шифрованию с оракулом, в симметричном случае), злоумышленнику предоставляется доступ к дешифрованию с оракулом, которое расшифровывает произвольные шифротексты по запросу злоумышленника, возвращая открытый текст. В определении IND-CCA1 злоумышленнику разрешено запрашивать оракула только до тех пор, пока он не получит испытываемый шифротекст. В определении IND-CCA2 злоумышленнику можно продолжать запрашивать оракула после того, как он получит испытываемый шифротекст, с оговоркой, что он не может передать его для расшифровки (в противном случае определение было бы тривиальным).

1. Испытатель генерирует пару ключей PK, SK на основе некоторого параметра безопасности k (например, размер ключа в битах) и публикует PK злоумышленнику. Испытатель сохраняет SK.
2. Злоумышленник может выполнять любое количество шифрований, вызовов дешифрования с оракулом на основе произвольных шифротекстов или других операций.
3. В конце концов, злоумышленник представляет два отдельных открытых текста ${\displaystyle \scriptstyle M_{0},\,M_{1}}$ испытателю.
4. Испытатель выбирает бит b ${\displaystyle \scriptstyle \in }$ {0, 1} случайным образом и посылает испытываемый шифротекст C = E(PK, ${\displaystyle \scriptstyle M_{b}}$ ) обратно злоумышленнику.
5. Злоумышленник может выполнять любое количество дополнительных вычислений или шифрований.
   1. В определении IND-CCA1, злоумышленник не может выполнять дальнейшие расшифрования с оракулом.
   2. В определении IND-CCA2, злоумышленник может выполнять дальнейшие вызовы оракула, но не может использовать для этого шифротекст C.
6. Наконец, злоумышленник выдает предположение о значении b.

Криптосистема надёжна в смысле IND-CCA1 или IND-CCA2, если никакой противник не имеет существенного преимущества в данной игре.

Неразличимость от случайного шума

Иногда требуются системы шифрования, в которых строка шифротекста неотличима для злоумышленника от случайной строки.^[3]

Если злоумышленник не может даже сказать, существует ли сообщение, это дает человеку, написавшему сообщение, правдоподобное отрицание.

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

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

На данный момент существуют специально разработанные криптографические алгоритмы для систем отрицаемого шифрования, в которых шифротексты неотличимы от случайных битовых строк.^[5][6][7]

Если алгоритм шифрования E может быть сконструирован таким образом, что злоумышленник (как правило, определяется как наблюдатель в течение полиномиального времени), знающий открытый текст сообщения m, не в состоянии различать E(m) и свеже-сгенерированную случайную битовую строку той же длины, что и E(m), то из этого следует, что при E(m1) такой же длины, как E(m2), эти два шифротекста будут неотличимы друг от друга для злоумышленника, даже если он знает открытый текст m1 и m2 (IND-CPA).^[8]

Большинство приложений не требуют алгоритма шифрования для создания шифротекстов, которые нельзя отличить от случайных битов. Тем не менее, некоторые авторы считают, что такие алгоритмы шифрования концептуально проще и легче работают, и более универсальны на практике – и большинство алгоритмов шифрования IND-CPA, по-видимому, действительно производят зашифрованные сообщения, которые неотличимы от случайных битов.^[9]