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

Федеральное агентство связи

Федеральное государственное образовательное учреждение

высшего профессионального образования

«Сибирский государственный университет

телекоммуникаций и информатики»

(ФГОБУ ВПО «СибГУТИ»)

Кафедра Прикладной математики и кибернетики

090106.65 Информационная безопасность телекоммуникационных систем (очная форма обучения)

Курсовой проект

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

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

Новосибирск 2015



Оглавление

• Введение
• 1. Разработка программного обеспечения, которое выполняет шифрование по алгоритму RC6
• 1.1 Алгоритм RC6
• 1.2 Исходный код программы
• 1.3 Вывод
• 2. Разработка программного обеспечения, которое выполняет электронную подпись на базе шифра Эль-Гамаля
• 2.1 Электронная подпись на базе шифра Эль-Гамаля
• 2.2 Исходный код программы
• 2.3 Вывод
• 3. Задача о нахождении гамильтонова цикла в графе
• 3.1 Алгоритм реализации гамильтонова цикла
• 3.2 Исходный код программы
• 3.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 раундов (такой шифр исследовался в качестве кандидата на стандарт США).

В шифре используются следующие операции:

+, -сложение и вычитание слов по модулю 2^w;

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

побитовое сложение по модулю 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: .

В алгоритме используется «магические» числа: P_w - первые w бит служат двоичного разложения числа e-1, где e - число Эйлера, служащее основанием натурального алгоритма, и Q_w - первые w бит двоичного разложения числа f, где - «золотое сечение». При w = 32 P_w = b7e15163, Q_w = 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.2 Исходный код программы

#include <iostream>

#include <fstream>

#include <windows.h>

#include <math.h>

#include <cmath>

#include <time.h>

#include <string>

#include <map>

#include <ctime>

#include <stdlib.h>

#include <functional>

unsigned int RightShift2(unsigned int z_value, int z_shift, int w) {

return ((z_value >> z_shift) | (z_value << (w - z_shift)));

}

unsigned int LeftShift2(unsigned int z_value, int z_shift, int w) {

return ((z_value << z_shift) | (z_value >> (w - z_shift)));

}

void main() {

int i, j, w = 32;

unsigned int r = 20, a = 0, b = 0, c = 0, d = 0, t, u, pw, qw, k, ksb = 4, buf;

unsigned int *W = new unsigned int[2 * r + 4];

unsigned int *K = new unsigned int[ksb];

unsigned long long buf2 = 1;

long double f = 1.6180339887498948482045868343656381177203;

long double e = 2.7182818284590452353602874713526624977572;

buf2 <<= w;

qw = (unsigned int)((f - 1)*buf2);

if (qw % 2 == 0)

qw++;

pw = (unsigned int)((e - 2)*buf2);

if (pw % 2 == 0)

pw++;

cout << "w = " << w << " pw = " << pw << " " << hex << pw << " qw = " << dec << qw << hex << " " << qw << dec << endl;

cout << "Ключ пользователя" << endl;

for (int f = 0; f<ksb; f++){

K[f] = rand();

cout << "K[" << f << "] = " << K[f] << endl;

}

// Формирование раундового ключа

W[0] = pw;

for (int i = 1; i <= 2 * r + 3; i++)

W[i] = W[i - 1] + qw;

a = 0; b = 0; i = 0; j = 0;

k = 3 * max(ksb, 2 * r + 4);

while (k) {

W[i] = LeftShift2(W[i] + a + b, 3, w);

a = W[i];

K[j] = LeftShift2(K[j] + a + b, a + b, w);

b = K[j];

i = (i + 1) % (2 * r + 4);

j = (j + 1) % ksb;

k--;

}

cout << "Раундовый ключ " << endl;

for (int i = 1; i <= 2 * r + 4; i++)

cout << "W[" << i << "] = " << W[i] <<endl;

//Шифрование блока данных

a = 4;

b = 8;

c = 15;

d = 16;

cout << "a = " << a << " b = " << b << " c = " << c << " d = " << d << endl;

b = b + W[0];

d = d + W[1];

for (int i = 1; i <= r; i++)

{

t = LeftShift2(b * (2 * b + 1), (int)log2(w), w);

u = LeftShift2(d * (2 * d + 1), (int)log2(w), w);

a = LeftShift2(a^t, u, w) + W[2*i];

c = LeftShift2(c^u, t, w) + W[2 * i + 1];

buf = a;

a = b;

b = c;

c = d;

d = buf;

}

a = a + W[2 * r + 2];

c = c + W[2 * r + 3];

cout << "Шифрованный блок данных" << endl;

cout << "a = " << a << " b = " << b << " c = " << c << " d = " << d << endl;

//Дешифрование блока данных

c = c - W[2 * r + 3];

a = a - W[2 * r + 2];

for (int i = r; i >= 1; i--) {

buf = d;

d = c;

c = b;

b = a;

a = buf;

t = LeftShift2(b * (2 * b + 1), (int)log2(w), w);

u = LeftShift2(d * (2 * d + 1), (int)log2(w), w);

a = RightShift2(a - W[2 * i], u, w) ^ t;

c = RightShift2(c - W[2 * i + 1], t, w) ^ u;

}

d = d - W[1];

b = b - W[0];

cout << "Расшифрованный блок данных" << endl;

cout << "a = " << a << " b = " << b << " c = " << c << " d = " << d << endl;

}

1.3 Вывод

В результате выполнения программы, слова, содержащиеся в блоке данных, зашифровывались по алгоритму 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}. Получатель подписанного сообщения, прежде всего, заново вычисляет хеш-функции . Затем он проверяет подпись, используя равенство .
• 2.2 Исходный код программы
• #include <iostream>
• #include <fstream>
• #include <windows.h>
• #include <math.h>
• #include <cmath>
• #include <time.h>
• #include <string>
• #include <map>
• #include <ctime>
• #include <stdlib.h>
• #include <functional>
• bool simpleChecker(long long p){
• for (long long i = 2; i * i <= p; i++){
• if (p%i == 0)
• return false;
• }
• return true;
• };
• long long codeMod(long long a, long long x, long long p){ //быстрое возведение в степень
• long long rez = 1;
• for (long long aCurr = a%p; x>0; x >>= 1, aCurr = aCurr*aCurr%p)
• if (x & 1)
• rez = rez*aCurr%p;
• return rez;
• }
• void Evklid(long long a, long long b, long long &nod, long long &x, long long &y) //обощенный алгоритм Евклида
• {
• long long c, q;
• int i;
• long long u[3];
• long long v[3];
• long long t[3];
• if (a<b) { c = a; a = b; b = c; }
• u[0] = a; u[1] = 1; u[2] = 0;
• v[0] = b; v[1] = 0; v[2] = 1;
• while (v[0] != 0)
• {
• q = u[0] / v[0];
• for (i = 0; i <= 2; i++)
• {
• t[i] = u[i] - q*v[i];
• }
• memcpy(u, v, sizeof(v)); memcpy(v, t, sizeof(t));
• }
• nod = u[0]; x = u[1]; y = u[2];
• }
• void main() {
• long long m, p, q, g, x, y, k, nod, b, v, r, u, s, ko;
• ifstream A;//объявление потока
• A.open("message.txt", ios::in);
• A >> m;
• do {
• p = rand();
• q = (p - 1) / 2;
• } while (simpleChecker(p) != 1 || simpleChecker(q) != 1);
• cout << "p = " << p << endl;
• cout << "q = " << q << endl;
• do {
• g = rand();
• } while (g > (p - 1) || codeMod(g, q, p) == 1);
• cout << "g = " << g << endl;
• x = rand() % (p - 1); //секретный ключ Алисы
• cout << "Секретный ключ Алисы x = " << x << endl;
• y = codeMod(g, x, p);//открытый ключ Алисы
• cout << "Открытый ключ Алисы y = " << y << endl;
• long long h = m;
• std::hash<long long> e;
• size_t h_hash = e(m);
• cout << "Хэш w = " << h_hash << endl;
• do {
• k = rand();
• Evklid(k, (p - 1), nod, b, v);
• } while (k >= (p - 1) || nod != 1);
• cout << "Алиса выбрала случайно число k, взаимно простое с p-1 = " << k << endl;
• r = codeMod(g, k, p);
• u = (h - (x * r) % (p - 1) + p - 1) % (p - 1);
• do {
• ko = rand();
• } while (ko*k%(p-1) != 1);
• cout << "k^-1 = " << ko << endl;
• s = (ko * u) % (p - 1);
• cout << "подписанное сообщение:" << endl;
• cout << m << "; " << r << ", " << s << endl;
• //как бы отправляем подписанное сообщение другому пользователю
• long long rez = codeMod(y, r, p);// y ^ r
• long long rez1 = codeMod(r, s, p);// r ^ s
• long long rezult = rez * rez1 % p;// y ^ r * r ^ s
• if (rezult == codeMod(g, h, p))//если (y ^ r * r ^ s) = G ^ h mod P
• cout << rezult << " = " << codeMod(g, h, p) << endl << "Подпись подлинная" << endl << endl << endl;
• else
• cout << "Подпись неподлинная" << endl;
• }
• 2.3 Вывод
• В результате содержимое файла 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. Алиса кодирует матрицу Н, приписывая к первоначально содержащимся в ней нулям и единицам случайные числа r_ij по схеме . Затем она шифрует элементы матрицы, получая зашифрованную матрицу F, . Матрицу F Алиса передает Бобу.

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

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

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

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

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

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

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

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

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

#include <iostream>

#include <fstream>

#include <windows.h>

#include <math.h>

#include <cmath>

#include <time.h>

#include <string>

#include <map>

#include <ctime>

#include <stdlib.h>

#include <functional>

using namespace std;

int prov(long long lim, long long mas[], long long digit)

{

int i;

for (i = 0; i<lim; i++)

if (mas[i] == digit)

return 1;

return 0;

}

long long concatenate(long long first, long long second) {

if (!second) {

return first * 10;

}

long long temp = second;

while (temp) {

first *= 10;

temp /= 10;

}

return first + second;

}

const int n = 8;

int c[n]; // номер хода, на котором посещается вершина

int path[n];// номера посещаемых вершин

int v0 = 2; // начальная вершина

//Матрица смежности G

int G[n][n] =

{

0, 0, 1, 0, 0, 1, 1, 1,

0, 0, 1, 1, 0, 0, 0, 1,

1, 1, 0, 0, 1, 1, 1, 0,

0, 1, 0, 0, 0, 1, 0, 0,

0, 0, 1, 0, 0, 0, 1, 1,

1, 0, 1, 1, 0, 0, 0, 0,

1, 0, 1, 0, 1, 0, 0, 0,

1, 1, 0, 0, 1, 0, 0, 0,

};

int gamilton(int k)

{

int v, q1 = 0;

for (v = 0; v<n && !q1; v++)

{

if (G[v][path[k - 1]] || G[path[k - 1]][v])

{

if (k == n && v == v0) q1 = 1;

else if (c[v] == -1)

{

c[v] = k; path[k] = v;

q1 = gamilton(k + 1);

if (!q1) c[v] = -1;

}

else continue;

}

} return q1;

}

void main() {

long long P, Q, N = 0, D = 0, C = 0, s = 0, w = 0, f = 0, m, nod;

const int n = 8;

long long i, j, SP1[8], buf, buf1, buf2, buf3, buf4, buf5, buf6, buf7, VB;

int H[n][n], H2[n][n], F[n][n], MB1[n][n], MB2[n][n], MB3[n][n]; //MB - матрица Боба

do {

P = rand();

} while (simpleChecker(P) != 1);

do {

Q = rand();

} while (simpleChecker(Q) != 1);

N = Q*P;

f = (P - 1)*(Q - 1);

cout << "P = " << P << " Q = " << Q << endl << "Открытый ключ N = " << N << endl;

D = f + 1;

while (D >= f || nod != 1) {

D = (rand() % 100000) * 10000 + (rand() % 10000);

Evklid(D, f, nod, m, C);

}

if (C < 0) C = C + f;

cout << "Открытый ключ D = " << D << endl;

//Матрица смежности G

int G[n][n] =

{

0, 0, 1, 0, 0, 1, 1, 1,

0, 0, 1, 1, 0, 0, 0, 1,

1, 1, 0, 0, 1, 1, 1, 0,

0, 1, 0, 0, 0, 1, 0, 0,

0, 0, 1, 0, 0, 0, 1, 1,

1, 0, 1, 1, 0, 0, 0, 0,

1, 0, 1, 0, 1, 0, 0, 0,

1, 1, 0, 0, 1, 0, 0, 0,

};

cout << endl << "Матрица смежности G " << endl;

for (i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++)

cout << G[i][j] << " ";

cout << endl;

}

cout << endl;

cout << "Гамильтонов цикл графа G" << endl;

for (j = 0; j<n; j++) c[j] = -1;

path[0] = v0;

c[v0] = v0;

if (gamilton(1)) {

int p;

for (p = 0; p<n; p++)

cout << path[p] << " ";

cout << path[0];

cout << endl << endl;

}

else cout << "У данного графа нет гамильтонова цикла" << endl;

int G0[n] = { G[path[0]][path[1]], G[path[1]][path[2]], G[path[2]][path[3]], G[path[3]][path[4]], G[path[4]][path[5]], G[path[5]][path[6]], G[path[6]][path[7]], G[path[7]][path[0]] };

int gcg0[3] = { path[0], path[1], G0[0] };

int gcg1[3] = { path[1], path[2], G0[1] };

int gcg2[3] = { path[2], path[3], G0[2] };

int gcg3[3] = { path[3], path[4], G0[3] };

int gcg4[3] = { path[4], path[5], G0[4] };

int gcg5[3] = { path[5], path[6], G0[5] };

int gcg6[3] = { path[6], path[7], G0[6] };

int gcg7[3] = { path[7], path[0], G0[7] };

cout << "gcg0 = ";for (i = 0; i < 3; i++)cout << gcg0[i] << " ";cout << endl;

cout << "gcg1 = ";for (i = 0; i < 3; i++)cout << gcg1[i] << " ";cout << endl;

cout << "gcg2 = ";for (i = 0; i < 3; i++)cout << gcg2[i] << " ";cout << endl;

cout << "gcg3 = ";for (i = 0; i < 3; i++)cout << gcg3[i] << " ";cout << endl;

cout << "gcg4 = ";for (i = 0; i < 3; i++)cout << gcg4[i] << " ";cout << endl;

cout << "gcg5 = ";for (i = 0; i < 3; i++)cout << gcg5[i] << " ";cout << endl;

cout << "gcg6 = ";for (i = 0; i < 3; i++)cout << gcg6[i] << " ";cout << endl;

cout << "gcg7 = ";for (i = 0; i < 3; i++)cout << gcg7[i] << " ";cout << endl;

cout << endl << "Случайная последовательность из 8-ми вершин" << endl;

for (int f = 0; f < 8; f++) {

do {

SP1[f] = rand() % 8;

} while (prov(f, SP1, SP1[f]));

cout << SP1[f] << " ";

}

cout << endl << endl;

buf = SP1[0]; buf1 = SP1[1]; buf2 = SP1[2]; buf3 = SP1[3]; buf4 = SP1[4]; buf5 = SP1[5]; buf6 = SP1[6]; buf7 = SP1[7];

buf = 6; buf1 = 3; buf2 = 4; buf3 = 2; buf4 = 0; buf5 = 1; buf6 = 7; buf7 = 5;

int bufgl[n] = {buf, buf1, buf2, buf3, buf4, buf5, buf6, buf7};

for (i = 0; i < 8; i++) {

for (j = 0; j < 8; j++) {

H[i][j] = G[bufgl[i]][bufgl[j]];

}

}

cout << "Матрица смежности H" << endl;

for (i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++)

cout << H[i][j] << " ";

cout << endl;

}

cout << endl;

int h0[n] = { H[buf1][buf2], H[buf2][buf6], H[buf6][buf5], H[buf5][buf7], H[buf7][buf], H[buf][buf3], H[buf3][buf4], H[buf4][buf1] };

int gch0[3] = { buf1, buf2, h0[0] };

int gch1[3] = { buf2, buf6, h0[1] };

int gch2[3] = { buf6, buf5, h0[2] };

int gch3[3] = { buf5, buf7, h0[3] };

int gch4[3] = { buf7, buf, h0[4] };

int gch5[3] = { buf, buf3, h0[5] };

int gch6[3] = { buf3, buf4, h0[6] };

int gch7[3] = { buf4, buf1, h0[7] };

cout << "Гамильтон цикл для матрицы H" << endl;

cout << "gch0 = ";for (i = 0; i < 3; i++)cout << gch0[i] << " ";cout << endl;

cout << "gch1 = ";for (i = 0; i < 3; i++)cout << gch1[i] << " ";cout << endl;

cout << "gch2 = ";for (i = 0; i < 3; i++)cout << gch2[i] << " ";cout << endl;

cout << "gch3 = ";for (i = 0; i < 3; i++)cout << gch3[i] << " ";cout << endl;

cout << "gch4 = ";for (i = 0; i < 3; i++)cout << gch4[i] << " ";cout << endl;

cout << "gch5 = ";for (i = 0; i < 3; i++)cout << gch5[i] << " ";cout << endl;

cout << "gch6 = ";for (i = 0; i < 3; i++)cout << gch6[i] << " ";cout << endl;

cout << "gch7 = ";for (i = 0; i < 3; i++)cout << gch7[i] << " ";cout << endl;

for (i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++)

H2[i][j] = concatenate(rand() % 5 + 1, H[i][j]);

}

cout << endl << "Матрица смежности H2" << endl;

for (i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++)

cout << H2[i][j] << " ";

cout << endl;

}

int h20[n] = { H2[buf1][buf2], H2[buf2][buf6], H2[buf6][buf5], H2[buf5][buf7], H2[buf7][buf], H2[buf][buf3], H2[buf3][buf4], H2[buf4][buf1] };

int gch20[3] = { buf1, buf2, h20[0] };

int gch21[3] = { buf2, buf6, h20[1] };

int gch22[3] = { buf6, buf5, h20[2] };

int gch23[3] = { buf5, buf7, h20[3] };

int gch24[3] = { buf7, buf, h20[4] };

int gch25[3] = { buf, buf3, h20[5] };

int gch26[3] = { buf3, buf4, h20[6] };

int gch27[3] = { buf4, buf1, h20[7] };

cout << endl << "Гамильтон цикл для матрицы H2" << endl;

cout << "gch20 = ";for (i = 0; i < 3; i++)cout << gch20[i] << " "; cout << endl;

cout << "gch21 = ";for (i = 0; i < 3; i++)cout << gch21[i] << " "; cout << endl;

cout << "gch22 = ";for (i = 0; i < 3; i++)cout << gch22[i] << " "; cout << endl;

cout << "gch23 = ";for (i = 0; i < 3; i++)cout << gch23[i] << " "; cout << endl;

cout << "gch24 = ";for (i = 0; i < 3; i++)cout << gch24[i] << " "; cout << endl;

cout << "gch25 = ";for (i = 0; i < 3; i++) cout << gch25[i] << " "; cout << endl;

cout << "gch26 = ";for (i = 0; i < 3; i++)cout << gch26[i] << " "; cout << endl;

cout << "gch27 = ";for (i = 0; i < 3; i++)cout << gch27[i] << " "; cout << endl;

cout << endl << "N = " << N << " D = " << D << endl;

for (i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++)

F[i][j] = codeMod(H2[i][j], D, N);

}

cout << endl;

cout << "Матрица смежности F" << endl;

for (i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++)

cout << F[i][j] << " ";

cout << endl;

}

int fp[n] = { F[buf1][buf2], F[buf2][buf6], F[buf6][buf5], F[buf5][buf7], F[buf7][buf], F[buf][buf3], F[buf3][buf4], F[buf4][buf1] };

int gcf0[3] = { buf1, buf2, fp[0] };

int gcf1[3] = { buf2, buf6, fp[1] };

int gcf2[3] = { buf6, buf5, fp[2] };

int gcf3[3] = { buf5, buf7, fp[3] };

int gcf4[3] = { buf7, buf, fp[4] };

int gcf5[3] = { buf, buf3, fp[5] };

int gcf6[3] = { buf3, buf4, fp[6] };

int gcf7[3] = { buf4, buf1, fp[7] };

cout << endl << "Гамильтон цикл для матрицы F" << endl;

cout << "gcf0 = ";for (i = 0; i < 3; i++)cout << gcf0[i] << " ";cout << endl;

cout << "gcf1 = ";for (i = 0; i < 3; i++)cout << gcf1[i] << " ";cout << endl;

cout << "gcf2 = ";for (i = 0; i < 3; i++)cout << gcf2[i] << " ";cout << endl;

cout << "gcf3 = ";for (i = 0; i < 3; i++)cout << gcf3[i] << " ";cout << endl;

cout << "gcf4 = ";for (i = 0; i < 3; i++)cout << gcf4[i] << " ";cout << endl;

cout << "gcf5 = ";for (i = 0; i < 3; i++)cout << gcf5[i] << " ";cout << endl;

cout << "gcf6 = ";for (i = 0; i < 3; i++)cout << gcf6[i] << " ";cout << endl;

cout << "gcf7 = ";for (i = 0; i < 3; i++)cout << gcf7[i] << " ";cout << endl;

VB = rand() % 2 + 1;

cout << endl << "Какой из двух вопросов будет задавать Боб VB = " << VB << endl;

if (VB == 1) {

cout << endl << "Боб выбрал первый вопрос:\nДействительно ли граф H изоморфен G?\n\nТогда Алиса отправляет Бобу матрицу H2 и\nиспользованную последовательность bufgl[n]" << endl;

for (i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++)

MB1[i][j] = codeMod(H2[i][j], D, N);

}

j = 0;

if (MB1[i][j] == F[i][j]) {

cout << endl << "Полученная матрица Бобом MB1 после проверки равна матрице F - правильно" << endl;

}

else {

cout << endl << "Полученная матрица Бобом MB1 после проверки не равна матрице F - неправильно" << endl;

}

for (i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++)

MB2[i][j] = H2[i][j] % 10;

}

if (MB2[i][j] == H[i][j]) {

cout << endl << "Полученная матрица Бобом MB2 после отброса старшей десятичной цифры\nравна матрице H - правильно" << endl;

}

else {

cout << endl << "Полученная матрица Бобом MB2 после отброса старшей десятичной цифры\nне равна матрице H - неправильно" << endl;

}

for (i = 0; i < 8; i++) {

for (j = 0; j < 8; j++) {

MB3[i][j] = MB2[bufgl[i]][bufgl[j]];

}

}

if (MB3[i][j] == G[i][j]) {

cout << endl << "Полученная матрица Бобом MB3 после перестановки вершин\nравна матрице G - правильно" << endl;

}

else {

cout << endl << "Полученная матрица Бобом MB3 после перестановки вершин\nне равна матрице G - неправильно" << endl;

}

cout << endl << "На этом реализация первого вопроса заканчивается" << endl;

}

if (VB == 2) {

cout << endl << "Боб выбрал второй вопрос:\nКаков гамильтонов цикл для графа H?\n\nТогда Алиса отправляет Бобу\nсоответствующий список (закодированных) ребер графа H2" << endl << endl;

cout << "Проверка соответствия Бобом ребер матрицы H2 матрице F" << endl;

int PB[n];

for (i = 0; i < 8; i++) {

PB[i] = codeMod(h20[i], D, N);

}

if (PB[i] == fp[i]) {

cout << endl << "Полученные результаты соответвствуют кодам ребер матрицы F - правильно" << endl;

}

else {

cout << endl << "Полученные результаты не соответвствуют кодам ребер матрицы F - неправильно" << endl;

}

cout << endl << "На этом реализация второго вопроса заканчивается" << endl;

}

}

3.3 Вывод

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



Рисунок 3 -результат выполнения программы «Шаг младенца шаг великана»

Заключение

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

1. шифрование по алгоритму RC6;

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

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



Библиография

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

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

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