Стойкость криптографических систем и алгоритмов. Лекция 7

1. ЛЕКЦИЯ 7. Стойкость криптографических систем и алгоритмов

7.1. Информационно - теоретический
анализ криптографической стойкости
7.2 Анализ криптографической стойкости
на основе теории сложности

2.

Пусть
x1 ,..., x n есть n возможных сообщений, появляющихся с вероятностями
P( x1 ),..., P( xn ) причем
n
P ( xi ) 1
i 1
Энтропия сообщения x
n
n
i 1
i 1
H ( x) P( xi ) log 2 P( xi ) P( xi ) log 2
1
P( xi )
Для заданного n величина H(x) принимает максимальное значение, равное log 2 n , при
P( x1 ) ... P( xn )
1
n
т.е. когда все сообщения равновероятны.
.
Энтропия сообщения измеряет его неопределенность в числе бит информации, которая должна быть
восстановлена, после того как сообщение было скрыто от криптоаналитика в шифротексте.
Криптосистема называется теоретически стойкой, если криптоаналитик не может уточнять
распределение вероятностей возможных открытых текстов по имеющемуся у него шифротексту, даже
если он обладает всеми необходимыми для этого средствами.
При этом предполагается, что секретный ключ используется только один раз
(т.е. сеансовый режим использование ключа).

3.

Совершенная секретность
означает, что открытый текст М и шифротекст С статистически независимы для всех возможных M и
C и, следовательно, получение шифротекста не дает криптоаналитику дополнительной информации о
посланном открытом тексте.
Если P(C/M) - условная вероятность получения шифротекста С при условии, что известно, что
зашифрован текст М некоторым неизвестным ключом, то
P(C / M )
P(k ),
k :Ek ( M ) C
где P(k) - вероятность использования ключа k ,
E k - преобразование зашифрования с использованием ключа k
Обычно существует по крайней мере один ключ k , такой что E k ( M ) C для данных М и С,
но иногда текст М может быть зашифрован в текст С при нескольких различных ключах.
Необходимым и достаточным условием совершенной секретности является то, что для каждого С и для
всех М выполнено
Р(М/С) = Р(М),
т.е. вероятности получения открытого текста М при перехвате конкретного шифра С одинаковы для всех
М.
Определение совершенной секретности можно также представить в виде
H (M / C ) H (M )
Т.к. уменьшение объема известных сведений может лишь увеличить неопределенность, т.е. энтропию,
то, рассматривая множество текстов совместно с множеством неизвестных ключей, получим:
H (M / C ) H (M , K / C ) H ( K / C ) H (M / C , K )
H (K / C) H (K )
H ( M / C, K ) 0 , т.к. при условии совместного наличия как шифртекста С, так и ключа К,
неопределенность открытого текста М, естественно, отсутствует.

4.

Неопределенность секретного ключа должна быть не меньше, т.е. больше или
равна, неопределенности шифруемого с его помощью текста.
Вывод:
размер ключа k не должен быть меньше размерности открытого
текста М (т.к. для их формирования используется один и тот же алфавит).
Пример совершенно секретной криптосистемы
Система Вернама, когда
C M K M 1 K1 ,..., M n K n
.
при случайном равновероятном выборе ключа
k k1 ,..., k n
В этом случае P(ki ) 2 n для всех i=1,…,n, откуда P(C / M ) 2 n для всех С и М,
т.е. выполняется условие совершенно секретной системы.

5.

W(n) - среднее количество работы (измеренное в удобных единицах), требуемое для нахождения ключа
k
на основе знания n знаков шифротекста с помощью наилучшего криптоаналитического алгоритма.
Криптосистемы называются практически стойкими, если они не могут быть вскрыты в течение реального времени
( W ( ) Const) всеми общедоступными методами.
Вычислительная сложность алгоритма измеряется его временной и емкостной S сложностями, в зависимости
от размера n входных данных.
Временная сложность - это время, затрачиваемое алгоритмом для решения задачи и рассматриваемое как функция
размера задачи или количества входных данных.
Емкостная сложность - это емкость необходимой машинной памяти.
Поведение этих сложностей в пределе при увеличении размера задачи называется асимптотическими сложностями.
Если при данном размере задачи в качестве меры сложности берётся наибольшая из сложностей по всем входам этого
размера, то она называется
сложностью в худшем случае.
Если в качестве меры сложности берется «средняя» сложность по всем входам данного размера, то она называется
средней сложностью.
Обычно среднюю сложность найти труднее, чем сложность в худшем случае.
Модели вычислительных машин,
отражающих основные черты реальных машин:
− машины с произвольным доступом к памяти,
− машины с произвольным доступом к памяти и хранимой программой,
− детерминированная и недетерминированная машины Тьюринга и другие.
В детерминированных машинах Тьюринга новое состояние, в которое машина переходит на очередном шаге, полностью
определяется текущим состоянием и тем символом, который обозревает головка на ленте.
В недетерминированных (вероятностных) машинах Тьюринга новое состояние может зависеть еще и от случайной
величины, которая принимает значения 0 и 1 с вероятностью ½ каждое.
Можно считать, что вероятностная машина Тьюринга имеет дополнительную «случайную» ленту, на которой
записана бесконечная двоичная случайная строка. «Случайная» лента может читаться только в одном
направлении и переход в новое состояние может зависеть от символа, обозреваемого на этой ленте.

6.

Если алгоритм обрабатывает входы размера n за время
=
cn 2 , где с - const,
то временная сложность этого алгоритма есть
o(n 2 ) (читается: порядкаn 2 ).
n0
Строго математически: неотрицательная g (n) есть O( f ( N )), если существуют постоянные с и
g (n) с f ( N ) , где n n0.
, для которых
m
m 1
Если g (n) am n am 1n ... a1n a0 ,
то
g (n)
является полиномиальной функцией степени m, т.е. g (n) O(n m )
Полиномиальным алгоритмом, или алгоритмом полиномиальной временной сложности, называется алгоритм, у
которого временная сложность равна
= O( P(n)) , где Р(n) - некоторый полином, а n - размер задачи (входа).
Алгоритмы, временная сложность которых есть
= 0(t(n)P(n)), где t(n) − некоторая функция, Р(n) - полином,
называются экспоненциальными
(если временная сложность = 0(сP(n)), где с = const, Р(n) - полином,
алгоритмы называются суперполиномиальными).
106
Класс алгоритма
Сложность
Полиномиальный
O(1)
1
1 мс.
Линейный
O(n)
106
1 сек.
Квадратичный
O(n2)
1012
10 дней.
Кубический
O(n3)
1018
27397 лет.
O(2n)
1030130
10301016 лет.
Экспоненциальный
(суперполиномиальный)
Число операций при n
Реальное время

7.

Задачи, которые решаются за полиномиальное время, называются решаемыми, так как они
обычно могут быть решены для задач достаточно большой размерности n.
Задачи, которые не могут быть систематически решаемыми за полиномиальное время,
называют нерешаемыми или просто трудными.
Классификация задач по степени сложности их решения
Класс Р (или P – TIME) состоит из всех задач, решаемых за полиномиальное время.
Класс NP (или NP – TIME) состоит из всех задач, решаемых за полиномиальное время на
недетерминированной машине Тьюринга, способной параллельно выполнять неограниченное
количество независимых вычислений.
Пример
«Задача рюкзака»:
имеется множество из n целых чисел A=(a1,…,an) и целое число S.
Требуется определить, существует ли подмножество чисел из А такое, чтобы их сумма была бы равна S.
Эта задача принадлежит к классу NP − задач, так как для любого подмножества чисел из А легко
проверить, равна ли их сумма S.
Найти же такое подмножество чисел, сумма которых равна S, гораздо труднее. Существует 2n таких
подмножеств и проверка их всех имеет временную сложность
= О(2n).

8.

Класс NP Complete (NP - полных) задач включает все самые трудные NP − задачи. Если какая - либо из
NP − полных задач окажется в классе P, то будет доказано равенство NP = P.
Класс СоNP состоит из всех задач, являющихся дополнительными для некоторых задач из NP.
Если задача в NP имеет вид: «определить, существует ли решение», то задача из CoNP имеет вид
«показать, что решений нет».
На сегодняшний день неизвестно, верно ли равенство CoNP = NP, но есть задачи, принадлежащие
пересечению классов CoNP и NP, т.е. CoNP NP.
Пример
«Задача о разложении чисел»:
Дано целое число n.
Определить, существуют ли делители p и q, такие, что n = pq.
Класс PSPACE состоит из задач, требующих полиномиальных объемов машинной памяти, но не
обязательно решаемых за полиномиальное время.
Этот класс включает классы CoNP и NP (CoNP - Complete и NP-Complete), но есть в нем задачи,
которые труднее, чем CoNP(CoNP - complete) и NP(NP - complete).
Класс PSPACE - complete (полных) задач состоит из задач, имеющих свойство, что если какаянибудь из них окажется принадлежащей классу NP, то NP = PSPACE, или если эта задача окажется в
P, то PSPACE = P.