Заказать работу


Тип работы:
Предмет:
Язык работы:


АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ В ИНФОРМАЦИОННОЙ ЗАЩИТЕ

Работа №33418
Тип работыДипломные работы
Предметматематика
Объем работы26
Год сдачи2019
Стоимость3700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 8
Не подходит работа?

Узнай цену на написание
Введение 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.
Таким образом, в работе нами были подробно рассмотрены введённые индексные множества шифрования с симметричным ключом С и Ci, показана их неразрешимость, а также «оценена» арифметическая сложность данных множеств, определены их положения в арифметической иерархии.
Относительно криптостойкости этих множеств было доказано, что не существует вычислимой или хотя бы вычислимой по Тьюрингу относительно скачка пустого множества функции f (при условии всюду определённости функции ), которая удовлетворяла бы условию:
Ve (e е Ci ^ е С).
Однако, если усилить накладываемые на функцию f требования, то для f 0''' задача нахождения «дешифратора» становится выполнимой.
Открытым остаётся вопрос о том, что же будет происходить в случае, если функция f 0''. Станет ли поиск «дешифратора» осуществимым, как в случае f 0''', или всё же найдётся некоторое число e е С1, для
которого < e, f (e) > е С.
] Соар, Р.И. Вычислимо перечислимые множества и степени /
Р.И. Соар. Пер. с англ. - Казань: Казанское математическое общество, 2000. - 576 с., ил.
[2] Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость / Х. Роджерс. Пер. с англ. В.А. Душского, М.И. Кановича, Е.Ю. Ногиной. - М.: Издательство «Мир», 1972. - 624 с.
[3] Odifreddi, P.G. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1 / P.G. Odifreddi. - University of Turin, Italy, 1989. - 668 p.
[4] Катленд, Н. Вычислимость. Введение в теорию рекурсивных функций / Н. Катленд. Пер. с англ. - М.: «Мир», 1983. - 256 с., ил.
[5] Cooper, S.B. Computability Theory / S.B. Cooper. - Chapman & Hall/CRC, USA, 2004. - 409 p.
[6] Мальцев, А.И. Алгоритмы и рекурсивные функции, 2-е изд. /
А.И. Мальцев. - М.: «Наука», 1986. - 368 с.
[7] Барвайс, Дж. Справочная книга по математической логике в четырёх частях. Часть III. Теория рекурсии / Дж. Барвайс. Пер. с англ. - М.: «Наука», 1982. - 360 с.
[8] Шенфилд, Дж. Степени неразрешимости / Дж. Шенфилд. Пер. с англ. И.А. Лаврова. - М.: Издательство «Наука», 1977. - 192 с., ил.

Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!




Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!



Когда в теории вычислимости возникает некоторая новая проблема, в первую очередь актуальным становится вопрос о её разрешимости. Если проблема разрешима, то перед исследователями встаёт новый вопрос: насколько сложен разрешающий алгоритм? Ответ на него помогает найти теория сложности вычислений. Если же проблема неразрешима, то необходимо будет определить её степень неразрешимости, которая может быть оценена, например, при помощи широко известной и часто применяемой арифметической иерархии (см. [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.


Таким образом, в работе нами были подробно рассмотрены введённые индексные множества шифрования с симметричным ключом С и Ci, показана их неразрешимость, а также «оценена» арифметическая сложность данных множеств, определены их положения в арифметической иерархии.
Относительно криптостойкости этих множеств было доказано, что не существует вычислимой или хотя бы вычислимой по Тьюрингу относительно скачка пустого множества функции f (при условии всюду определённости функции ), которая удовлетворяла бы условию:
Ve (e е Ci ^ е С).
Однако, если усилить накладываемые на функцию f требования, то для f 0''' задача нахождения «дешифратора» становится выполнимой.
Открытым остаётся вопрос о том, что же будет происходить в случае, если функция f 0''. Станет ли поиск «дешифратора» осуществимым, как в случае f 0''', или всё же найдётся некоторое число e е С1, для
которого < e, f (e) > е С.



] Соар, Р.И. Вычислимо перечислимые множества и степени /
Р.И. Соар. Пер. с англ. - Казань: Казанское математическое общество, 2000. - 576 с., ил.
[2] Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость / Х. Роджерс. Пер. с англ. В.А. Душского, М.И. Кановича, Е.Ю. Ногиной. - М.: Издательство «Мир», 1972. - 624 с.
[3] Odifreddi, P.G. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1 / P.G. Odifreddi. - University of Turin, Italy, 1989. - 668 p.
[4] Катленд, Н. Вычислимость. Введение в теорию рекурсивных функций / Н. Катленд. Пер. с англ. - М.: «Мир», 1983. - 256 с., ил.
[5] Cooper, S.B. Computability Theory / S.B. Cooper. - Chapman & Hall/CRC, USA, 2004. - 409 p.
[6] Мальцев, А.И. Алгоритмы и рекурсивные функции, 2-е изд. /
А.И. Мальцев. - М.: «Наука», 1986. - 368 с.
[7] Барвайс, Дж. Справочная книга по математической логике в четырёх частях. Часть III. Теория рекурсии / Дж. Барвайс. Пер. с англ. - М.: «Наука», 1982. - 360 с.
[8] Шенфилд, Дж. Степени неразрешимости / Дж. Шенфилд. Пер. с англ. И.А. Лаврова. - М.: Издательство «Наука», 1977. - 192 с., ил.


Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!



© 2008-2018 Сервис продажи готовых курсовых работ, дипломных проектов, рефератов, контрольных и прочих студенческих работ.