Введение 3
1. Цели и задачи 6
2. Шифрование с симметричным ключом 7
3. Арифметическая сложность индексных множеств ШСК 11
4. Криптостойкость ШСК 19
Заключение 25
Список литературы

Купить

Когда в теории вычислимости возникает некоторая новая проблема, в первую очередь актуальным становится вопрос о её разрешимости. Если проблема разрешима, то перед исследователями встаёт новый вопрос: насколько сложен разрешающий алгоритм? Ответ на него помогает найти теория сложности вычислений. Если же проблема неразрешима, то необходимо будет определить её степень неразрешимости, которая может быть оценена, например, при помощи широко известной и часто применяемой арифметической иерархии (см. [1, 2, 3]).
В данной работе нам предстоит провести подробный анализ алгоритмических проблем, возникающих в информационной защите.
Прежде, чем приступить к изложению, необходимо ввести некоторые основопологающие понятия, которые будут широко использоваться в дальнейшем.
Частичная функция f(x), где x = (x,...,xn), n ^ 1, x* £ N, i = 1 , n, называется частично-вычислимой, если она вычислима на некоторой машине Тьюринга с номером e в Гёделевской нумерации всех машин Тьюринга (подробнее о нумерациях см., например, [1, 5, 6]). Такую функцию будем в дальнейшем обозначать через ^е. Через <^e,s обозначим часть функции ^е, определившуюся к шагу s.
Всюду определённая частично-вычислимая функция называется вычислимой. В этом случае на любом входном векторе x машина Ме останавливается, подавая на выход значение f(x).
Множество A С N называется вычислимо (рекурсивно) перечислимым, если оно является областью определения некоторой частично-вычислимой функции. Через We будем обозначать область определения функции tpe.

Купить