Реализация решения задачи о гамильтоновом цикле в криптографических протоколах с нулевым разглашением на языке JAVA - Курсовая работа

Криптография ведет свое начало еще с тех времен, когда только начал возникать сам язык. С большим ростом популярности письменности, сама криптография зарекомендовала себя и стала развиваться как самостоятельная наука. В свою очередь, основным предметом изучения в данной курсовой работе является задача о нахождении гамильтонова цикла в графе в криптографическом протоколе с нулевым разглашением, которая представляет собой криптографический метод защиты информации. При выполнении теоретической части данной курсовой работы, была затронута тема такой науки, как криптология, а так же ее основные направления, методы защиты информации с помощью криптографии, описаны принципы работы криптографических протоколов с нулевым разглашением. В практической части научной работы, по ходу выполнения которой был реализован алгоритм решения задачи о нахождении гамильтонова цикла в графе в криптографическом протоколе с нулевым разглашением, были использованы такие языки, как: ? Java,ввиду своей быстро действенности (за счет встроенного сборщика мусора)и распространенности, в частности при проектировании клиент-серверной архитектуры;Протоколом является некий порядок шагов, затрагивающих более чем две стороны для определенного совместного разрешения некой задачи. Помимо этого, каждый протокол предполагает участие двух сторон. Протокол обладает и иными отличительными особенностями: ? каждый его участник обязан заранее быть осведомлен о шагах, предстоящих к выполнению; ? в протоколе должны быть описаны и предусмотрены все реакции участников на разного рода ситуации, происходящие по ходу его выполнения. В обычной жизни обычный пользователь довольно часто сталкиваемся с протоколами - будь то покупки в магазинах, голосования на выборах и многое другое.Приведем основные свойства доказательства протокола с нулевым разглашением[8]:Это значит, что абонент А при любых обстоятельствах сможет показать, что владеет неким секретом, но только если он на самом деле им владеет.Следующая особенность подразумевает, что любые сведения, получаемые абонентом В (или же неким третьим лицом) он смог бы точно так же получить совершенно самостоятельно неким полиномиальным алгоритмом без участия A.Попытки атаковать протоколы могут быть направлены на криптографические алгоритмы, задействованные в них, против тех методов, которые применяются в их реализации, а так же против этих протоколов. Представим, что те алгоритмы и методы, которые мы используем, являются вполне стойкими и затронем атаки непосредственно на протоколы. К примеру, есть некий абонент, но не являющийся частью протокола, желает подслушать информацию, которой владеют его участники. Такая атака называется пассивной, потому что атакующий, назовем его абонент С, лишь копит информацию и следит за ходом действий, без возможности влиять на него. Чтобы защититься от нее, задействованы протоколы, с помощью которых предотвращается возможность неблагоприятных последствий пассивной атаки, а не только ее распознания.При выполнении протоколов доказательств с нулевым разглашением приходим к результату Подтверждения/Отказа и также создается стенограмма доказательства. Различные варианты нулевого разглашения определяется формализацией понятия и анализа распространения данных разнообразных моделей с протоколом, ниже представленными способами[8]: ? Идеальный протокол нулевого разглашения - различные рандомные величины в стенограмме доказательства являются равномерно распределенными, не завися от всех входных данных.В доказательствах с нулевым разглашением предполагается, что абонент А владеет некой тайной, идентифицирующей его личность. Такая возможность дает шанс, к примеру, совершить преступление и безнаказанно скрыться.В данном примере существует некая сторона, способная доказать обладание тайной, не обладая ей на самом деле или, другими словами, имитирует то лицо, которому на самом деле принадлежит секрет.А доказывает свою личность B, а С хочет выдать себя за B владеет рестораном, принадлежащим мафии, С - также представитель мафии, D - ювелир. В момент, когда A готов заплатить за обед и идентифицировать себя перед B, B извещает С о начале мошенничества. В это время С выбирает бриллиант, который хочет купить, и D начинает идентифицировать личность С, который выдает себя заГамильтоновым циклом (путем) называется простой путь (путь без петель), проходящий лишь один раз сквозь каждую вершину графа. Но стоит заметить, что в отличие от цикла, в гамильтоновом пути начальные и конечные точки могут не совпадать. Граф, содержащий простой путь, который проходит через каждую его вершину, называется полугамильтоновым. Гамильтонов цикл может не содержать все ребра в графе.Для гамильтоновых графов нет определенного критерия быть гамильтоновым, в отличие от эйлеровых, где имеется критерий для графа. Более того, заметим, что задача доказательства существования гамильтонова цикла является NP-полной. Большинство известных фактов имеет вид: "если граф G имеет достаточное количество ребер, то граф является гамильтоновым"

Оглавление

Введение

Глава 1. Теоретические аспекты протоколов с нулевым разглашением знания

1.1 Понятие криптографического протокола

1.2 Свойства доказательств с нулевым разглашением

1.2.1 Полнота

1.2.2 Свойство нулевого разглашения

1.2.3 Корректность

1.3 Примеры доказательств с нулевым разглашением

1.3.1 Обман с несколькими личностями

1.3.2 Проблема гроссмейстера

1.3.3 Обман, выполненный мафией

Глава 2. Криптографический протокол с нулевым разглашением знания на основе задачи о гамильтоновом цикле в графе

2.1 Понятие гамильтонова цикла

2.1.1 Условия существования гамильтонова цикла

2.2 Гамильтонов цикл в криптографических протоколах с нулевым разглашением знания

2.3 Сравнение полученных данных

2.4 Руководство пользователя

Заключение

Список использованной литературы

Список сокращений

Способы сохранения информации, путем ее преобразования, без всяческой потери смысла, предотвращая ее попадание в руки различного рода злоумышленников, терзали умы множество людей испокон веков. Криптографические методы защиты разного рода информации занимают особое место из всего многообразия способов защиты различных данных. Криптография ведет свое начало еще с тех времен, когда только начал возникать сам язык. Стоит сказать, что письменность сама по себе представляет в полной мере криптографическую системой, изза того, что в то давнее время ее мог изучить только узкий круг людей. Ярким примером этого являются письменности Индии, Месопотамии и Древнего Египта[9].

С большим ростом популярности письменности, сама криптография зарекомендовала себя и стала развиваться как самостоятельная наука.

Самым используемым образцом криптографии, встречающимся в священных книгах иудаизма (например, в книге пророка Ирмияху, жившего в VI веке до н. э.), где задействован простейший шифровальный метод. Название данного способа образовано из букв еврейского алфавита: вначале идет "алеф" - первая буква, вместе с последней: "тав". После следует вторая буква алфавита - "бет", следом за которой находится предпоследняя: "шин". Это простейший шифр подстановки в иврите, который все - называли "атбаш".

В настоящее время проблема задействования криптографических методов защиты данных стала очень актуальна.

Во-первых, увеличилось использование вычислительных сетей, в том числе и такой широко используемой сети Internet. По ним пересылаются значительные объемы данных различного характера (в том числе коммерческого, государственного, частного и военного), которые не допускают возможности пользования ей посторонними лицами.

Во-вторых, появление мощных ЭВМ, различных вычислительных технологий сетевого и нейронного направления сделало возможным дискредитирование криптографических систем, считавшихся довольно недавно почти не взламываемыми.

Базисным объектом исследования в теории протоколов с использованием криптографических шифров, являются абоненты, находящиеся удаленно друг от друга, но ведущие активное взаимодействие, зачастую, по открытым каналам связи. Решение какой-то конкретной задачи является основной целью взаимодействия таких абонентов. Довольно часто в таких случаях имеется некоторый противник со своими собственными целями. В зависимости от задачи, при всем этом, противник имеет в своем арсенале довольно разные возможности: от простого вмешательства в информационный обмен между другими абонентами до взаимодействия от имени сторонних абонентов с остальными абонентами и т. д.[3]

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

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

В практической части научной работы, по ходу выполнения которой был реализован алгоритм решения задачи о нахождении гамильтонова цикла в графе в криптографическом протоколе с нулевым разглашением, были использованы такие языки, как: ? Java,ввиду своей быстро действенности (за счет встроенного сборщика мусора)и распространенности, в частности при проектировании клиент-серверной архитектуры;

? C, в силу своей уникальности с той точки зрения, что именно он стал первым языком высокого уровня, всерьез потеснившим ассемблер в разработке системного программного обеспечения;

? C#, за его строгую статическую типизацию, поддержку полиморфизмов, перегрузку операторов, указатели на функции-члены классов, атрибуты, события, свойства и исключения;

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

? CUDA-технология, за счет разделяемой между потоками памяти размером в 16 Кб, которую возможно использовать под организованный пользователем кэш с более широкой полосой пропускания, чем при выборке из обычных текстур и ввиду более эффективные транзакции между памятью центрального процессора и видеопамятью[6];

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

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

Для достижения данной цели необходимо решить следующие задачи: ? рассмотреть методы работы и использования криптографических алгоритмов, а также алгоритм работы протокола с нулевым разглашением;

? реализовать программное решение задачи о нахождении гамильтонова цикла в криптографическом протоколе с нулевым разглашением на наиболее используемых языках программирования, таких как: Java, C, C#, PHP;

? внедрить в реализацию программного решения задачи о нахождении гамильтонова цикла в криптографическом протоколе с нулевым разглашением высокоскоростную технологию параллельных ВЫЧИСЛЕНИЙCUDA;

? провести сравнительный анализ полученных данных в ходе программной реализации задачи о нахождении гамильтонова цикла в криптографическом протоколе с нулевым разглашением и выбрать наиболее быстродейственный способ реализации данного криптографического протокола

В первой главе своей курсовой работы были затронуты общие теоретические аспекты современной криптографии, включены ключевые понятия, основные требования к ним, а также возможности ее применения с практической точки зрения.

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

В заключении был сделан вывод о проведенной работе.