СибГУТИ Контрольная работа Защита информации скачать бесплатно
Задание:
Выполнить компьютерную реализацию протокола «Задачи о нахождении гамильтонова цикла в графе», используя пример 6.2 (стр. 124 лекций). Номер варианта Z равен последней цифре номера пароля.
Параметры, выбираемые по варианту Z:
1) Случайную нумерацию вершин, используемую в алгоритме (изначально в примере она равна 7 4 5 3 1 2 8 6), необходимо изменить по формуле ((a+Z)mod 9), где a – это цифра исходной последовательности случайных номеров вершин.
2) Необходимые в алгоритме параметры схемы RSA вычислить, используя значения P и Q по вариантам:
Для Z=8: P=11 Q=23.
Программу необходимо реализовать с помощью любой среды визуального программирования под Windows. Обязательным требованием также является вывод всех промежуточных результатов, таких как матрица смежности, гамильтонов цикл, изоморфный граф, закодированная матрица, зашифрованная матрица, посылаемые вопросы и ответы Алисы и Боба.
Решение:
Для схемы RSA с параметрами P=11 и Q=23 имеем
Пусть d = 3
Случайную нумерацию вершин, используемую в алгоритме (изначально в примере она равна 7 4 5 3 1 2 8 6), изменяем по формуле ((a+Z) mod 9), где a – это цифра исходной последовательности случайных номеров вершин. Получаем следующую нумерацию вершин (при этом вершине с номером 0 заменяем номер на 8, т.к. в задании указана не совсем корректная формула):
(6, 3, 4, 2, 8, 1, 7, 5)
Алгоритм работы программы:
1. Выводим матрицу смежности G на форму и выделяем в ней гамильтонов цикл синими прямоугольниками.
2. Получаем изоморфный граф H, переставляя элементы матрицы G в соответствии с нумерацией вершин (6, 3, 4, 2, 8, 1, 7, 5), выводим его на форму и выделяем в нем гамильтонов цикл синими прямоугольниками.
3. Создаем закодированную матрицу H2, просто приписывая к элементам матрицы H слева случайную цифру от 1 до 5, и выводим ее на форму.
4. Создаем зашифрованную матрицу F, просто возводя соответствующие элементы закодированной матрицы в куб (число d) по модулю N, и выводим ее на форму.
5. Боб получает матрицу F и задает вопрос (для этого надо нажать кнопку “Задать вопрос” на форме).
6. Если Боб просит доказать изоморфизм графов, то Алиса посылает Бобу закодированную матрицу H2 и использованную нумерацию вершин. Боб проверяет, соответствует ли матрица H2 матрице F, т.е. возводит соответствующие элементы матрицы H2 в куб (число d) по модулю N и сравнивает результат с элементами матрицы F. Далее Боб выводит сообщение, что матрица H2 соответствует или не соответствует матрице F. Если матрица H2 соответствует матрице F, то Боб из матрицы H2 получает граф H (просто отбросив старшую десятичную цифру), переставляет вершины графа G в соответствии с полученной нумерацией и сравнивает полученные графы (матрицы). Далее Боб выводит сообщение о совпадении или несовпадении графов.
7. Если Боб просит показать гамильтонов цикл, то Алиса посылает ему список закодированных ребер графа H (указаны номера начальной и конечной вершин и код ребра). Боб проверяет, соответствуют ли указанные в списке ребра матрице F (код ребра, возведенный в куб по модулю N, должен быть равен элементу матрицы F с координатами начальной и конечной вершин), и выводит соответствующее сообщение. Если указанные в списке ребра соответствуют матрице F, то Боб проверяет, проходит ли указанный в списке путь через все вершины графа по одному разу. Для этого Боб проверяет, что все начальные вершины списка имеют разные номера (от 1 до 8), и все начальные вершины списка совпадают с предыдущими конечными. После этого Боб выводит сообщение о результатах проверки.
