Разработка криптографического программного обеспечения - Курсовая работа

Разработка программного обеспечения, которое выполняет электронную подпись на базе шифра Эль-ГамаляЗадача о нахождении гамильтонова цикла в графе#include #include #include #include #include unsigned int RIGHTSHIFT2(unsigned int z_value, int z_shift, int w) {return ((z_value >> z_shift) | (z_value << (w - z_shift)));В результате выполнения программы, слова, содержащиеся в блоке данных, зашифровывались по алгоритму RC6, затем расшифровывались и результат расшифровки выводится на экран. Результат работы программы представлен на рисунке 1.1. Разработка программного обеспечения, которое выполняет электронную подпись на базе шифра Эль-Гамаля Описание варианта подписи, основанный на задаче дискретного логарифмирования. Алиса выбирает большое просто число p и число g, такие, что различные степени g суть различные числа по модулю p.#include #include #include #include #includeБлюм (Manuel Blum) показал, что, выражаясь неформально, любое математическое утверждение может быть представлено в виде графа, причем доказательство этого утверждения соответствует гамильтонову циклу в этом графе. Поэтому наличие протокола доказательства с нулевым значением для гамильтонова цикла означает, что доказательство любого математического утверждения может быть представлено в форме доказательства с нулевым значением. Гамильтоновым циклом в графе называется непрерывный путь, проходящие через все вершины графа ровно по одному разу. Допустим, что Алиса знает гамильтонов цикл в графе G. На языке теории графов говорят, что граф Н изоморфен графу G.#include #include #include #include #includeВ ходе выполнения программы была решена задача.В результате выполнения данного проекта было разработано криптографическое программное обеспечение, решающее следующие задачи: 1.

Оглавление

Введение

1. Разработка программного обеспечения, которое выполняет шифрование по алгоритму RC6

1.1 Алгоритм RC6

1.2 Исходный код программы

1.3 Вывод

3. Задача о нахождении гамильтонова цикла в графе

3.1 Алгоритм реализации гамильтонова циклаВ результате выполнения программы, слова, содержащиеся в блоке данных, зашифровывались по алгоритму RC6, затем расшифровывались и результат расшифровки выводится на экран. Результат работы программы представлен на рисунке 1.1.

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

2. Разработка программного обеспечения, которое выполняет электронную подпись на базе шифра Эль-Гамаля

2.1 Электронная подпись на базе шифра Эль-Гамаля программный криптографический шифрование гамильтонов

Описание варианта подписи, основанный на задаче дискретного логарифмирования.

Алиса собирается подписывать документы. Алиса выбирает большое просто число p и число g, такие, что различные степени g суть различные числа по модулю p. Эти числа передаются или хранятся в открытом виде и могут быть общими для целой группы пользователей. Алиса выбирает случайное число x, 1 < x < p-1, которое она держит в секрете. Это ее секретный ключ. Затем она вычисляет .

Это число y Алиса публикует в качестве своего открытого ключа. Заметим, что при больших p, зная y, невозможно найти x (это задача дискретного логарифмирования).

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

Вначале Алиса вычисляет значение хэш-функции , которое должно удовлетворять неравенству 1 < h < p. Затем Алиса выбирает случайно число k (1 < k < p-1), взаимно простое с p-1, и вычисляет число . Далее Алиса вычисляет числа , .

Под k-1 подразумевается число, удовлетворяющее уравнению .

Такое существует, так как k и p-1 взаимно просты, и может быть найдено по обобщенному алгоритму Евклида. Наконец, Алиса формирует подписанное сообщение { , r, s}. Получатель подписанного сообщения, прежде всего, заново вычисляет хеш-функции . Затем он проверяет подпись, используя равенство .В результате содержимое файла message.txt было зашифровано при помощи электронной подписи на база Эль-Гамаля. Результат выполнения программы представлен на рисунке 2.1.

Рисунок 2.1 -Результат выполнения программы

3. Задача о нахождении гамильтонова цикла в графе

3.1 Алгоритм реализации гамильтонова цикла

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

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

Допустим, что Алиса знает гамильтонов цикл в графе G. Теперь она может это доказать Бобу и всем, кто имел граф G, с помощью описываемого ниже протокола. Алиса может использовать это доказательство, например, для идентификации своей личности. Но прежде чем мы перейдем к описанию протокола, договоримся о некоторых обозначениях.

Мы будем обозначать графы буквами G, H, F, понимая под этим одновременно соответствующие матрицы смежности. Элемент матрицы , если в графе есть ребро, соединяющее вершины i и j; - в противном случае. Символом || будем обозначать конкатенацию (сцепление) двух чисел, точнее двоичных слов, им соответствующих. Нам понадобится шифр с открытым ключом. Вообще говоря, это может быть любой шифр, но для определенности будем использовать шифр RSA. Будем считать, что Алиса сформировала систему RSA с открытыми параметрами N и d. Важно, что зашифрованные в этой системе сообщения может расшифровать только Алиса и больше никто.

Протокол доказательства состоит из следующих четырех шагов.

Шаг 1. Алиса получает граф Н, являющийся копией исходного графа G, где у всех вершин новые, случайно выбранные номера. На языке теории графов говорят, что граф Н изоморфен графу G. Иными словами, граф Н получается путем некоторой перестановки номеров вершин в графе G. Алиса кодирует матрицу Н, приписывая к первоначально содержащимся в ней нулям и единицам случайные числа rij по схеме . Затем она шифрует элементы матрицы , получая зашифрованную матрицу F, . Матрицу F Алиса передает Бобу.

Шаг 2. Боб, получив зашифрованный граф F, задает Алисе один из двух вопросов.

1. Каков гамильтонов цикл для графа H?

2. Действительно ли граф H изоморфен G?

Шаг 3. Алиса отвечает на соответствующий вопрос Боба.

1. Она расшифровывает в F ребра, образующие гамильтонов цикл.

2. Она расшифровывает F полностью (фактически передает Бобу граф ) и предъявляет перестановки, с помощью которых граф H был получен из графа G.

Шаг4. Получив ответ, Боб проверяет правильность расшифровки путем повторного шифрования и сравнения с F и убеждается либо в том, что показанные ребра действительно образуют гамильтонов цикл, либо в том, что предъявленные перестановки действительно переводят граф G в граф H.

Весь протокол повторяется t раз.В ходе выполнения программы была решена задача. Результат выполнения программы представлен на рисунке 3.1.

Рисунок 3 -результат выполнения программы «Шаг младенца шаг великана»В результате выполнения данного проекта было разработано криптографическое программное обеспечение, решающее следующие задачи: 1. шифрование по алгоритму RC6;

2. электронная подпись на основе шифра Эль-Гамаля;

3. задача гамильтонов цикл.

Введение

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

2. электронная подпись на основе шифра Эль-Гамаля;

3. задача гамильтонов цикл.

В качестве языка программирования был выбран C .

1. Разработка программного обеспечения, которое выполняет шифрование по алгоритму RC6

1.1 Алгоритм RC6

Это один из новейших шифров, предложенный Ривертом (Ronald Rivest) в 1998 году. Это шифр принимал участие в конкурсе на новый стандарт блокового шифра США, проводимом в 1999-2001 годах, прошел в финал, но по совокупности таких показателей, как быстродействие, удобство использования и т.п., уступил первое место другому шифру (Rijdael). Тем не менее, активные исследования RC6 в ходе проведения конкурса не выявили в нем каких-либо слабых мест, и данный шифр высоко оценивается многими специалистами.

В RC6 пользователь задает размер слова (w) 16, 32 или 64 бита, количество раундов (r), длину ключа (l) от 0 до 255 байт. Размер блока всегда составляет четыре слова. Конкретный вариант шифра обозначается по схеме RC6-32/20/16 - размер блока 128 бит, длина ключа 128 бит, 20 раундов (такой шифр исследовался в качестве кандидата на стандарт США).

В шифре используются следующие операции: , -сложение и вычитание слов по модулю 2w;

*умножение по модулю 2w;

побитовое сложение по модулю 2 или, что то же самое, «исключающее или» двух слов;

циклические сдвиги слова влево и вправо на указанное число бит (заметим, что при длине слова w бит величина циклического сдвига фактически приводится по модулю w, причем, как правило, это приведение выполняется автоматически на машинном уровне, т.е. не требует дополнительных вычислений - процесс просто использует младшие log w бит числа, задающего величину сдвига).

Шифрование и дешифрование блока данных приводится с использованием одного и того же раундового ключа W длиной 2r 4 слова (нумерация слов с нуля), получаемого из секретного ключа K.

RC6: шифрование блока данных.

Вход: блок из четырех слов (a, b, c, d), раундовый ключ.

Выход: зашифрованный блок (a, b, c, d).

1. , ;

2. FOR i = 1, 2, …, r DO

3. , 4. , 5. , 6. , 7. (a, b, c, d) = (b, c, d, a);

8. , ;

9. RETURN (a, b, c, d).

Для дешифрования просто «прокручиваем» процесс в обратном порядке.

RC6: дешифрование блока данных.

Вход: блок из четырех слов (a, b, c, d), раундовый ключ W.

Выход: дешифрованный блок (a, b, c, d).

1. , ;

2. FOR i = r, r-1, …, 1 DO

3. (a, b, c, d) = (d, a, b, c), 4. , 5. , 6. , 7. ;

8. , ;

9. RETURN (a, b, c, d).

Расписание раундового ключа в RC6 более сложно, чем в ГОСТ 28147-89, что характерно для большинства современных шифров. По сути дела речь идет о развертывании секретного ключа K в более длинную псевдослучайную последовательность W с целью затруднить криптоанализ шифра.

Обозначим через c число слов в ключе . Посредством нижеприведенного алгоритма секретный ключ K разворачивается в раундовый ключ W: .

В алгоритме используется «магические» числа: Pw - первые w бит служат двоичного разложения числа e-1, где e - число Эйлера, служащее основанием натурального алгоритма, и Qw - первые w бит двоичного разложения числа f, где - «золотое сечение». При w = 32 Pw = b7e15163, Qw = 9e3779b9.

RC6: формирование раундового ключа.

Вход: секретный ключ K.

Выход: раундовый ключ W.

1. ;

2. FOR i = 1, 2, …, 2r 3 DO ;

3. a = 0, b = 0, i = 0, j = 0;

4. ;

5. DO k раз 6. , , 7. , b = K[j], 8. , ;

9. RETURN W.

Рассмотрим кратко основные идеи построения алгоритма шифрования RC6. Заметим, прежде всего, что, как и в шифрах DES и ГОСТ 28147-89, в каждом раунде RC6 одна половина блока используется для шифрования другой. Действительно, значение переменных t и u (строки 3-4) определяется только словами b и d соответственно. Затем эти переменные используются для модификации слов a и c перед сложением с элементами ключа (строки 5-6). Таким образом, в a и c вносится зависимость от b и d. В следующем раунде пары a, c и b, d меняются ролями, причем b и d переставляются между собой (строка 7). Вследствие такой структуры шифра количество раундов должно быть четным.

Рекомендуемое количество раундов r = 20 связанно с результатами исследования стойкости шифра по отношению к дифференциальному и линейному криптоанализу.

В ходе исследований шифра слабых ключей не обнаружено, т.е. любой ключ, даже нулевой, обеспечивает заявляемую высокую стойкость шифра. Предполагается, что для RC6 не существует алгоритма взлома, лучшего, чем перебор ключей.1 Рябко, Б.Я. Криптографические методы защиты информации / Б.Я. Рябко, А.Н. Фионов. - Москва: Горячая линия - телеком, 2005. - 229с.

2 Конспект лекций по предмету криптографические методы защиты информации

Размещено на