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

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Ульяновский государственный университет

Факультет математики, информационных и авиационных технологий

Кафедра информационной безопасности и теории управления

10.05.01 "Компьютерная безопасность"

Специализация: "Математические методы защиты информации"

Курсовая работа

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

Оглавление

Введение

Глава 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 Руководство пользователя

Заключение

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

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

ЭВМ - электронная вычислительная машина (компьютер).

ПО - программное обеспечение.

ОС - операционная система.

CPU - центральное процессорное устройство.

GPU - графический процессор.

CUDA - программно-аппаратная архитектура параллельных вычислений.

PHP - скриптовый язык, применяемый для разработки веб-приложений.

ms- миллисекунды.

Tb - терабайт (кратная единица измерения количества информации).

Gb - гигабайт (кратная единица измерения количества информации).

Mb - мегабайт (кратная единица измерения количества информации).

Kb - килобайт (кратная единица измерения количества информации).

GHz - гигагерцы (кратная единица измерения тактовой частоты процессора).

HDD - жесткий диск.

Введение

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

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

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

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

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

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

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

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

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

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

ѕ Java,ввиду своей быстро действенности (за счет встроенного сборщика мусора)и распространенности, в частности при проектировании клиент-серверной архитектуры;

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

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

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

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

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

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

Для достижения данной цели необходимо решить следующие задачи:

ѕ рассмотреть методы работы и использования криптографических алгоритмов, а также алгоритм работы протокола с нулевым разглашением;

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

ѕ внедрить в реализацию программного решения задачи о нахождении гамильтонова цикла в криптографическом протоколе с нулевым разглашением высокоскоростную технологию параллельных вычисленийCUDA;

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

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

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

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

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

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

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

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

Протокол обладает и иными отличительными особенностями:

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

ѕ необходимо, чтобы шаги протокола были достаточно точно указаны и не допускали шанса их ошибочного понимания, а так же чтобы он допускал только однозначное, определенное понятие;

ѕ все участники должны придерживаться его правил добровольно;

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

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

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

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

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

Зачастую, во многих криптосистемах появляется задача одному абоненту A, который будет стороной доказывающей то, что он знает некоторый секрет стороне проверки (абоненту В), но это нужно сделать так, чтобы сторона проверки не имела представления о сути тайны. То есть, A показывает, что владеет некими данными без разглашения любой части этих знаний. В 1985 г. Чарльз Ракофф, совместно со своими коллегами, ввел впервые определение протоколов с нулевым разглашением знания. Эти протоколы способны избежать проблем, присущих всем методам с использованием пароля:

ѕ потребность на сервере сохранять пароль или

ѕ кража пароля третьими лицами довольно просто в исполнении, как и подслушивание процесса организации.

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

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

Приведем основные свойства доказательства протокола с нулевым разглашением[8]:

1.2.1 Полнота

Это значит, что абонент А при любых обстоятельствах сможет показать, что владеет неким секретом, но только если он на самом деле им владеет.

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

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

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

Абонент А никаким образом не покажет факт обладания секретом, если на самом деле он не обладает такими знаниями.

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

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

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

Допустим, абонент С хочет получить как можно больше сведений о действиях участников протокола и о них самих в целом. А абонент D имеет совсем другие интересы - уменьшить производительность сети, получить незаконный доступ к ее ресурсам, а так же внести изменения в базы данных. Абоненты C и D могут оказаться совсем не посторонними личностями. В их лице могут скрываться даже законные пользователи, разработчики ПО, системные и сетевые администраторы, и даже сами участники протокола, не соблюдающие данный протокол или вовсе ведущие себя крайне непорядочно. В таком случае лицо, совершающее атаку, называется мошенником.

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

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

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

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

ѕ Идеальный протокол нулевого разглашения - различные рандомные величины в стенограмме доказательства являются равномерно распределенными, не завися от всех входных данных.

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

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

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

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

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

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

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

В настоящее время Т. Бетом и И. Десмедтом найден действенный способ решения проблемы.

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

Ещё один пример, когда одна сторона выдает себя за другую. Пусть имеется 4 участника: A, B, C, D. Причём B и С сотрудничают между собой ("принадлежат одной мафии"). А доказывает свою личность B, а С хочет выдать себя за A перед D. B владеет рестораном, принадлежащим мафии, С - также представитель мафии, D - ювелир. A и D не знают о предстоящем мошенничестве. В момент, когда A готов заплатить за обед и идентифицировать себя перед B, B извещает С о начале мошенничества. Это возможно благодаря наличию радиоканала между ними. В это время С выбирает бриллиант, который хочет купить, и D начинает идентифицировать личность С, который выдает себя за A. С передаёт вопрос по протоколу B, а тот в свою очередь, задаёт его А. Ответ передаётся в обратном порядке. Таким образом А заплатит не только за обед, но и за дорогой бриллиант. Как видно из вышеописанного, существуют определённые требования для подобного мошенничества. Когда А начинает доказывать свою личность перед B, а С - перед D, B и С должны быть точно синхронизированы. То есть данное злоупотребление тоже решается. Например, если в магазине ювелира будет клетка Фарадея, то "мафиози" не смогут обмениваться сообщениями.

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

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

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

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

Замечание.

Каждый граф G можно сделать гамильтоновым, если добавить достаточное количество вершин. Для этого только достаточно к некоторым вершинам v1,…, vp графа G добавить вершины u1,…, up и множество ребер {(vi, ui)} {(ui, vi+1)}.

Степень вершины v - это число ребер d(v), которые ей инцидентны, однако петля учитывается дважды. Если же граф ориентированный, то различают степень do(v) по выходящим дугам и di(v) - по входящим.

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

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

Теорема Дирака

Если в некотором графе G (V, E) ct вершинами (t ? 3) выполняется d(v) ? t/2 для любого vV, то граф G является гамильтоновым.

Доказательство

Докажем методом от противного. Пусть граф G не является гамильтоновым. Добавим к нему минимальное количество новых вершин u1, …, ut, такое, что соединив их с остальными вершинами графа так, чтобы G':= G + u1 + … + ut стал гамильтоновым.

Предположим, что существует v, u1, w, …, v - гамильтонов цикл в графе G', такой, что vG, u1G', u1G. Поэтому wG и w{u1,…, ut}, в противном случае в вершине u1 не было бы нужды. Кроме этого, вершина v не является смежной с вершиной w, иначе и не была бы нужна вершина u1.

Затем, если существует вершина w' в цикле v, u1, w, …, u', w', …, v, которая смежна с w. Отсюда следует, что вершина v не является смежной с v', потому как иначе была бы вероятность составить гамильтонов цикл v, v', …, w, w', …, v без самой вершины u1, имея набор вершин w, …, v', расположенных в обратном порядке. Следовательно, количество вершин графа G', не являющихся смежными с v, не превышает количества вершин, смежных с w. Стоит заметить, что для каждой из вершин w в графе Gd(w) ? p/2+t по построению, так же d(v) ? p/2+t. Суммарное количество смежных и не смежных с v вершин равно t+p-1. Из этого получается:

t+p-1 = d(v)+d(V) ? d(w)+d(v) ? p/2+t+p/2+t = 2t+p.

Из этого следует, что 0 ? t+1. Видим противоречие тому, что t> 0.

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

Рассмотрим пример, придуманный и описанный Мануэлем Блюмом в одной из его работ в 1986 году. В этом протоколе абонент А будет доказывать абоненту В, что он знает гамильтонов цикл в некотором графе G так, что абонент В не получит никаких знаний о самом этом цикле (доказательство с нулевым разглашением). Стоит напомнить, что "нулевое разглашение" означает, что независимо от числа реализаций протокола доказательства абонент В будет располагать точно такими же сведениями о гамильтоновом цикле, какие он бы мог получить, просто изучая представленный ему граф G.

Пусть абонент А знает гамильтонов цикл в графе G из t вершин. Он может это доказывать абоненту В (и всем, кто имеет этот граф) с помощью описываемого ниже протокола.

Протокол доказательства состоит из следующих шагов[1]:

1. Абонент А случайно выбирает перестановку и применяет ее к номерам вершин графа G, получив при этом Понятно, что графы G и H изоморфны. Зная гамильтонов цикл графа G, абонент А знает гамильтонов цикл и в графе Н. Граф Н передается проверяющему В.

2. Абонент В, получив граф Н, случайным образом выбирает и передает а абоненту А.

3. Если а = 0, то абонент А предоставляет абоненту В перестановку (тем самым доказывая, что он знает изоморфизм графов G и H). Если а = 1, то абонент А предоставляет проверяющему гамильтонов цикл графа Н.

4. Проверяющий В проверяет, что в случае а = 0 предъявленная перестановка действительно переводит граф G в граф H, а в случае а = 1 проверяет гамильтонов цикл графа Н.

Весь протокол повторяется m раз.

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

Теорема

Вероятность обмана при m реализациях протокола не превосходит 2-m.

Доказательство

Пусть некоторый абонент А не знает гамильтонов цикл в графе G и он хочет обмануть абонента В. Тогда абоненту А необходим неизоморфный G граф G', в котором он всё-таки знает гамильтонов цикл. В каждом раунде он может передавать абоненту В либо H' - изоморфный G', либо H - изоморфный G, тем самым подготовить ответ на первый вопрос. При этом, если абонент А готовился к ответу на первый вопрос, а В задаст второй вопрос, то есть попросит доказать изоморфизм графов, то абонент А не сможет дать корректный ответ. И наоборот. Тогда обман вскроется. Поэтому вероятность обмана равна вероятности угадывания номера вопроса. В предположении, что абонент В задает вопросы с одинаковой вероятностью, получаем, что вероятность обмана равна 1/2. Вероятность же обмана при m реализациях протокола равна 1/2m.

Предположим, что абонент В не узнал гамильтонов цикл, но хочет доказать некоторому абоненту С, что абонент А его знает. Если абонент В, например, покажет все раунды протокола, абонент С едва ли ему поверит. Абонент С может предположить, что абонент В и абонент А в сговоре, и в каждом раунде абонент В заранее сообщал абоненту А свой выбор случайного а, чтобы абонент А смог передавать ему H для проверок изоморфизма и H' для проверок гамильтонова цикла. Таким образом без участия абонент А доказать, что он знает гамильтонов цикл, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные а.[5]

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

В ходе реализации криптографического протокола с нулевым разглашением, основанного на задаче поиска гамильтонова цикла в графе на различных языках программирования, были проведены скоростные тесты, основанные на изменении размера количества ребер графа (N). Как видно из диаграммы (Рис. 1), где различными цветами представлены графики зависимости времени (в миллисекундах) от количества ребер графа для различных языков программирования.

Рис. 1 - диаграмма скоростных тестов различных языков программирования.

Для рассмотрения скоростных тестов на начальном этапе обратимся к Рис. 2. Язык С, ввиду того, что является низкоуровневым, а также благодаря оптимизации при работе с разделенной памятью, показывает очень хороший результат, в сравнении с остальными языками. Стоит отметить, что язык C#, в частности сборщик мусора.NETплатформы эффективно очищает память на начальных этапах, но при достижении показателя N = 500, скорость выполнения криптографического алгоритма заметно увеличивается. Работа сборщика мусора, встроенного в язык Java, выполняется при любом значении количества ребер графа, что позволяет производить расчёты с довольно высокой скоростью.

Рис. 2 - диаграмма скоростных тестов различных языков программирования.

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

Рис. 3 - диаграмма скоростных тестов различных языков программирования и технологии CUDA.

Для рассмотрения скоростных тестов на начальном этапе обратимся к Рис. 4. Благодаря распараллеливанию процессов вычисления на GPU, технология CUDAимеет высочайшую скорость выполнения, в сравнении со всеми представленными языками программирования[7]. В ходе проведенных тестов было вычислено, что технология CUDA позволяет, в среднем, работает в 50 раз быстрее, чем самый медленный язык из представленных (PHP)и в 13 раз быстрее, чем язык C.

Рис. 4-диаграмма скоростных тестов различных языков программирования и технологии CUDA.

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

Реализованный в ходе выполнения курсовой работы протокол является автономным и не требует дополнительных действий от пользователя.

Запуск выполнения протокола производиться путем нажатия кнопки "Сгенерировать матрицу", после ввода размерности (N) в поле выше, как представлено на различных графических интерфейсах (см. Рис. 5 и Рис. 6), либо после ввода размерности количества ребер графа в консольном режиме, как показано на Рис. 7а и Рис. 7б. В автоматическом режиме протокол формирует граф с гамильтоновым циклом, перестановку , а так же смежный граф . протокол криптографический нулевой



Рис. 5-графическийинтерфейспрограммы на языке Java.

Рис. 6 -графическийинтерфейспрограммы на языке C#.

Рис. 7а-консольный интерфейспрограммы на языке C и при использовании технологии.

Рис. 7б-консольный интерфейспрограммы при использовании технологииCUDA.

Данные графы высылаются проверяющей стороне, при этом никаких сведений о перестановках абонент В не имеет.[4]Далее осуществляется проверка, посредством генерации проверяющей стороной случайного числа Ответ абонента В засылается абоненту А и далее, в зависимости от значения а, доказывающая сторона дает доступ проверяющей стороне либо к гамильтонову циклу графа G, либо к гамильтонову циклу графа H. Весь протокол повторяется m раз, по окончании которого на экран выводятся сведения об успешном его завершении (успешной аутентификацией пользователем) или об ошибке (отказе в доступе пользователю).

Технические требования:

1. Операционная система Microsoft Windows 10/8/7/Vista/2003/XP (64-bit включительно)

2. IDE (IntellijIDEA (2017.1) / PHPStorm / Rider / VS 2015)

3. CUDA Toolkit 8.0

4. Видеокарта: NVIDIA модели 9800 GT 1GB и выше

5. Оперативная память: не менее 2Gb

6. JDK 1.6 и выше

7. HDD : не менее 1 Gb свободной памяти

Обозначим за n- количество ребер в генерируемом графе. Скоростные тесты отображены в Таблице 1.

Таблица 1-Скоростные тесты, проведенные на ПК (ОС: Windows10, Видеопамять: 2 Gb, Оперативная память: 8 Gb, HDD: 1 Tb, Процессор: IntelCorei5 - 1,7GHz)

Язык	N	Время выполнения, ms
Java	50	10.9
	500	118
	1000	271.2
	1500	558
C	50	3.2
	500	83.6
	1000	262
	1500	428
C#	50	4.86
	500	159.4
	1000	1452
	1500	2931.3
PHP	50	6.25
	500	510
	1000	2123
	1500	4381
CUDA	64	0.202
	512	16.84
	1024	136.62
	2048	1072

Заключение

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

ѕ пришли к выводу, что данная задача соответствует современным методам защиты информации;

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

ѕ внедрили в реализацию программного решения задачи о нахождении гамильтонова цикла в криптографическом протоколе с нулевым разглашением высокоскоростную технологию параллельных вычисленийCUDA;

ѕ проведя сравнительный анализ полученных данных в ходе программной реализации задачи о нахождении гамильтонова цикла в криптографическом протоколе с нулевым разглашением, выяснили, что высокоскоростная технология параллельных вычисленийCUDA, позволило ускорить процесс, в среднем, в 50 раз, по сравнению с самым меленным языком из рассмотренных (PHP)и в 13 раз быстрее, в сравнении с языком C;

ѕ рассмотрев алгоритм работы протокола с нулевым разглашением, доказали, что он требует наличия интерактивных исходных данных от абонента В, как правило, в виде некой проблемы или задачи. Цель подлинного абонента А, имеющего доказательство, в этом протоколе - убедить абонента В в том, что у него есть решение, не выдав при этом даже части "секретного" доказательства. В свою очередь, цель абонента В - это удостовериться в том, что доказывающая сторона "не лжёт";

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

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

1. Рябко Б.Я. Криптографические методы защиты информации: Учебное пособие для вузов / А.Н. Фионов, Б.Я. Рябко- Москва: Горячая линия- Телеком, 2005 - 229 с.

2. Мао B. Современная криптография. Теория и практика / В. Мао - Москва: Вильямс, 2005 - 763 с.

3. Саломаа А. Криптография с открытым ключом / А. Саломаа - Москва: Мир, 1995 - 318 с.

4. Мухачев В.А. Методы практической криптографии / В.А. Мухачев, В.А. Хорошко - Москва: Полиграф - Консалтинг, 2005 - 209 с.

5. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Б. Шнайер - Москва: Триумф, 2002 - 816 с.

6. Боресков А.В. Основы работы с технологией CUDA / А. В Боресков, А.А. Харламов-Москва: ДМК Пресс, 2010- 232 с.

7. Sanders J. CUDA by Example: An Introduction to General-Purpose GPU Programming / J. Sanders, E. Kandrot- Illinois: Addison-Wesley Professional, 2010- 312 с.

8. Доказательство с нулевым разглашением [Электронный ресурс] : база данных. Режим доступа: https://ru.wikipedia.org/wiki/доказательство _с_нулевым_разглашением

9. История криптографии [Электронный ресурс] : база данных. Режим доступа: https://ru.wikipedia.org/wiki/история_криптографии

Размещено на Allbest.ru