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

стойкости

7.2 Анализ криптографической стойкости на основе теории сложности

n величина H(x) принимает максимальное значение, равное

, при

т.е. когда все сообщения равновероятны.

Энтропия сообщения измеряет его неопределенность в числе бит информации, которая должна быть восстановлена, после того как сообщение было скрыто от криптоаналитика в шифротексте.

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

При этом предполагается, что секретный ключ используется только один раз
(т.е. сеансовый режим использование ключа).

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

Если P(C/M) - условная вероятность получения шифротекста С при условии, что известно, что зашифрован текст М некоторым неизвестным ключом, то

где P(k) - вероятность использования ключа ,

- преобразование зашифрования с использованием ключа

Обычно существует по крайней мере один ключ

, такой что

но иногда текст М может быть зашифрован в текст С при нескольких различных ключах.

для данных М и С,

Необходимым и достаточным условием совершенной секретности является то, что для каждого С и для всех М выполнено
Р(М/С) = Р(М),
т.е. вероятности получения открытого текста М при перехвате конкретного шифра С одинаковы для всех М.
Определение совершенной секретности можно также представить в виде

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

неопределенность открытого текста М, естественно, отсутствует.

, т.к. при условии совместного наличия как шифртекста С, так и ключа К,

неопределенности шифруемого с его помощью текста.

Вывод:

размер ключа

текста М (т.к. для их формирования используется один и тот же алфавит).

не должен быть меньше размерности открытого

Пример совершенно секретной криптосистемы

Система Вернама, когда

при случайном равновероятном выборе ключа

.

В этом случае

для всех i=1,…,n, откуда

для всех С и М,

т.е. выполняется условие совершенно секретной системы.

нахождения ключа

на основе знания n знаков шифротекста с помощью наилучшего криптоаналитического алгоритма.

Криптосистемы называются практически стойкими, если они не могут быть вскрыты в течение реального времени
(

) всеми общедоступными методами.

Вычислительная сложность алгоритма измеряется его временной τ и емкостной S сложностями, в зависимости от размера n входных данных.

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

Поведение этих сложностей в пределе при увеличении размера задачи называется асимптотическими сложностями.
Если при данном размере задачи в качестве меры сложности берётся наибольшая из сложностей по всем входам этого размера, то она называется
сложностью в худшем случае.
Если в качестве меры сложности берется «средняя» сложность по всем входам данного размера, то она называется
средней сложностью.
Обычно среднюю сложность найти труднее, чем сложность в худшем случае.

Модели вычислительных машин,
отражающих основные черты реальных машин:
− машины с произвольным доступом к памяти,
− машины с произвольным доступом к памяти и хранимой программой,
− детерминированная и недетерминированная машины Тьюринга и другие.

В детерминированных машинах Тьюринга новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состоянием и тем символом, который обозревает головка на ленте.
В недетерминированных (вероятностных) машинах Тьюринга новое состояние может зависеть еще и от случайной величины, которая принимает значения 0 и 1 с вероятностью ½ каждое.

Можно считать, что вероятностная машина Тьюринга имеет дополнительную «случайную» ленту, на которой записана бесконечная двоичная случайная строка. «Случайная» лента может читаться только в одном направлении и переход в новое состояние может зависеть от символа, обозреваемого на этой ленте.

этого алгоритма есть

Полиномиальным алгоритмом, или алгоритмом полиномиальной временной сложности, называется алгоритм, у которого временная сложность равна

Алгоритмы, временная сложность которых есть
τ = 0(t(n)P(n)), где t(n) − некоторая функция, Р(n) - полином,
называются экспоненциальными
(если временная сложность τ = 0(сP(n)), где с = const, Р(n) - полином,
алгоритмы называются суперполиномиальными).

обычно могут быть решены для задач достаточно большой размерности n.
Задачи, которые не могут быть систематически решаемыми за полиномиальное время, называют нерешаемыми или просто трудными.

Классификация задач по степени сложности их решения

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

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.