Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Криптография с открытым ключом
Криптография с открытым ключом
Изучение основных методов и алгоритмов криптографии с открытым ключом и их практического использования. Анализ и практическое применение алгоритмов криптографии с открытым ключом: шифрование данных, конфиденциальность, генерация и управление ключами.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 20.06.2011 |
| Размер файла | 1,2 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
2
ОГЛАВЛЕНИЕ
ОБЩИЕ ПОЛОЖЕНИЯ
ОСОБЕННОСТИ ИЗУЧЕНИЯ И ВЫПОЛНЕНИЯ ЦИКЛА ЛАБОРАТОРНЫХ РАБОТ
1. ЛАБОРАТОРНАЯ РАБОТА 1. КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ И ИЗУЧЕНИЕ НЕОБХОДИМЫХ АЛГОРИТМОВ
1.1 Задание 1. Поиск наибольшего общего делителя ? алгоритм Евклида
1.1.1 Теория, основные понятия и определения
1.1.2 Алгоритм Евклида ? нахождения наибольшего общего делителя
1.1.3 Инструкция по выполнению задания 1
1.1.4 Алгоритм выполнения задания 1
1.2 Задание 2. Расширенный алгоритм Евклида для вычисления мультипликативного обратного
1.2.1 Теория
1.2.2 Расширенный алгоритм Евклида для вычисления мультипликативного обратного
1.2.3 Инструкция по выполнению задания 2
1.2.4 Алгоритм выполнения задания 2
1.3. Задание 3. Алгоритм быстрого возведения в степень для ab mod n при больших значениях b
1.3.1 Теория
1.3.2 Алгоритм быстрого возведения в степень для ab mod n при больших значениях b
1.3.3 Инструкция по выполнению задания 3
1.3.4 Алгоритм выполнения задания 3
1.4 Общий алгоритм выполнения лабораторной работы по криптографическим системам с открытым ключом
ГЛОССАРИЙ
2. ЛАБОРАТОРНАЯ РАБОТА 2. КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ. АЛГОРИТМ ВЫЧИСЛЕНИЯ СТЕПЕНЕЙ ЦЕЛОГО ЧИСЛА AM ПО МОДУЛЮ P И ЦЕЛЫХ ЧИСЕЛ, ПРИНАДЛЕЖАЩИХ ПОКАЗАТЕЛЮ ?(P), ? ПЕРВООБРАЗНЫХ КОРНЕЙ ПО МОДУЛЮ P. ОБМЕН КЛЮЧАМИ ПО СХЕМЕ ДИФФИ-ХЕЛЛМАНА
2.1 Задание 1. Алгоритм вычисления степеней целого числа am по модулю p и целых чисел, принадлежащих показателю ?(p) ? первообразных корней по модулю p
2.1.1 Теория
2.1.2 Алгоритм определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней
2.1.3 Инструкция по выполнению задания 1
2.1.4 Алгоритм выполнения задания 1. Вычисление степеней целого числа am
по модулю p и целых чисел, принадлежащих показателю (p) (первообразных корней по модулю p)
2.2 Задание 2. Генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети
2.2.1 Теория
2.2.2 Инструкция по выполнению задания 2
2.2.3 Общее положение по выполнению задания 2 ? генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети
ГЛОССАРИЙ
3. ЛАБОРАТОРНАЯ РАБОТА 3. КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ. МЕТОД ЗАШИФРОВАНИЯ С ОТКРЫТЫМ КЛЮЧОМ RSA
3.1 Теория, криптография с открытым ключом. Метод зашифрования с открытым ключом RSA
3.2 Алгоритм RSA
3.3 Общее положение по выполнению лабораторной работы. Метод зашифрования RSA
3.3.1 Задание 1 ? RSA-0 ? подготовка для выполнения алгоритма зашифрования открытого сообщения открытым ключом RSA-1
3.3.2 Задание 2 ? RSA-1 - выполнение алгоритма зашифрования открытого сообщения открытым ключом RSA-1
3.3.3 Задание 3 ? RSA-2 - выполнение алгоритма расшифрования зашифрованного сообщения секретным ключом RSA-1
3.4 Общий алгоритм выполнения лабораторной работы 3 по криптографическим системам с открытым ключом
ГЛОССАРИЙ
СПИСОК УТВЕРЖДЕНИЙ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЯ
алгоритм криптография открытый ключ
ОБЩИЕ ПОЛОЖЕНИЯ
Современные методы накопления, обработки и передачи информации способствовали появлению угроз, связанных с возможностью потери, раскрытия, модификации данных, принадлежащих конечным пользователям.
Под информационной безопасностью понимается состояние защищенности обрабатываемых, хранимых и передаваемых в информационно-телекоммуникационных системах данных от незаконного ознакомления, преобразования и уничтожения, а также состояние защищённости информационных ресурсов от воздействий, направленных на нарушение их работоспособностиНесмотря на все возрастающие усилия по созданию технологий защиты данных, их уязвимость не только не уменьшается, но и постоянно возрастает. Поэтому актуальность проблем, связанных с защитой потоков данных и обеспечением информационной безопасности их обработки и передачи, все более усиливается. Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с древних времен.
Как известно, одним из ключевых вопросов обеспечения безопасности информации, хранимой и обрабатываемой в информационных системах, а также передаваемой по линиям связи (для простоты далее по тексту будем говорить просто об информации), является защита ее от несанкционированного доступа. Для защиты информации применяются различные меры и способы, начиная с организационно-режимных и кончая применением сложных программно-аппаратных комплексов.
Одним из путей решения проблемы защиты информации, а точнее - решения небольшой части вопросов из всего спектра мер защиты, является криптографическое преобразование информации, или шифрование.
В случае применения шифрования легальный пользователь получает доступ к закрытым данным только путем их расшифровывания. Получение доступа к зашифрованным данным полностью теряет смысл, если алгоритм и способы осуществления шифрования неизвестны.
Широк круг применения криптографических методов в различных областях, связанных с обработкой, хранением, передачей, приемом, использованием данных и т.д.
Данная выпускная квалифицированная работа посвящена изучению основных вопросов, связанных с криптографией с открытым ключом.
Целью работы является освоение основных методов и алгоритмов криптографии с открытым ключом и тем самым закрепить знания практическими навыками использования криптографических методов с открытым ключом.
К основным задачам, стоящим перед написанием работы «Криптография с открытым ключом» относятся:
? изучение криптографических алгоритмов с открытым ключом;
? использование алгоритмов криптографии с открытым ключом (зашифрование/расшифрование данных, генерация и управление ключами, использование электронных цифровых подписей, обеспечение конфиденциальности, целостности и достоверности передаваемой информации и др.).
В результате выполнения данного выпускной квалификационной работы:
Освоил математические основы и наиболее распространенные алгоритмы криптографии с открытым ключом;
изучил основные области применения методов криптографии с открытым ключом;
приобрел навыки практического применения расчетные схемы определения ключей;
использование метода открытого обмена ключами по схеме Диффи-Хеллмана и алгоритм зашифрования и расшифрования RSA.
1. Криптография с открытым ключом. Теоретические сведения
и изучение необходимых алгоритмов
1.1 Проблемы традиционных методов шифрования
Традиционные методы шифрования имеют ряд проблем, которые решаются путем применения криптографических методов шифрования с открытым ключом.
Первая проблема состоит в генерации и распределении ключей шифрования, применяемых при традиционном шифровании.
Вторая проблема, очевидно не связанная с первой, это проблема «цифровых подписей». Иными словами, можно ли разработать метод, с помощью которого обе стороны могли бы убедиться в том, что цифровое сообщение было отправлено данным конкретным лицом?
Алгоритмы шифрования с открытым ключом зависят от двух ключей: одного ключа для зашифрования и другого ключа, связанного с первым, для расшифрования (рис. 1.1). С точки зрения вычислений нереально определить ключ расшифрования, зная только используемый криптографический алгоритм и ключ зашифрования. В некоторых алгоритмах любой из этих ключей может применяться для зашифрования, а другой для расшифрования.
Криптографические системы с открытым ключом зависят от некоторой обратимой математической функции со специальными свойствами. Сложность вычисления такого рода функций может зависеть не линейно от числа битов в ключе, а расти более быстро. Поэтому длина ключа должна быть достаточно большой. Однако чем длиннее ключи, тем больше времени требуется для выполнения процессов зашифрования/расшифрования. Поэтому алгоритмы криптографии с открытым ключом в настоящее время, в основном, применяются в управлении ключами и приложениями цифровой подписи.
Рис. 1.1. Криптографическая система с открытым ключом
Сложности вычислений, в основном, состоят из сложностей практической реализации некоторых операций из теории чисел. Понятия и методы теории чисел являются абстрактными, и их часто довольно трудно понять интуитивно без использования примеров. Поэтому и предлагается настоящая лабораторная работа, после выполнения которой в дальнейшем более эффективно можно будет понимать и осваивать рассматриваемые конкретные наиболее распространенные криптографические методы с открытым ключом.
1.2 Алгоритм Евклида нахождения наибольшего общего делителя
Алгоритм Евклида нахождения наибольшего общего делителя основывается на следующей теореме (приводим без доказательства).
Для любого неотрицательного числа X и любого положительного числа Y справедливо следующее:
gcd (X, Y) = gcd (Y, X mod Y),
где XY0.
Чтобы определить наибольший общий делитель, приведенное выше равенство (1) необходимо использовать многократно (до получения значения Y = 0). Ниже приводится раскрытая запись
gcd (X, Y) = gcd (Y, X mod Y) = gcd (Y, X - (X/Y целое частное) Y)).
Пример: gcd (18, 12) = gcd (12, 18 mod 12) = gcd (12, 18 - 1 12) = gcd (12, 6). gcd (12, 6) = gcd (6, 12 mod 6) = gcd (6, 12 - 2 6) = gcd (6, 0).
Ответ: gcd (18, 12) = 6.
Блок-схема алгоритма Евклида приводится на рис.1.2. (слайд 1.3.).
Рис. 1.2. Блок-схема алгоритма нахождения наибольшего общего делителя
Рассмотрим конкретный пример и решим поставленную задачу согласно приведенному алгоритму вычисления EUCLID (d, f) [1]. В алгоритме d f 0 и достаточно рассмотреть только положительные целые числа, так как gcd (a, b) = gcd (a, b).
Пример Е: Найти EUCLID (d, f) для d = 1970, f = 1066.
EUCLID (1970, 1066) = ?
Ответ: gcd (1970, 1066) = 2.
dc
1.1.3 Инструкция по выполнению задания 1
Проанализировать приведенный пример Е. Выбрать два числа d и f, таких, что d f и d200, а f100. Определить по заданному алгоритму Евклида вручную, с использованием калькулятора (или составив программу на любом языке программирования), наибольший общий делитель чисел d и f Ї EUCLID (d, f).
Полученный ответ и исходные данные d и f ввести в компьютер (ПРОГРАММА 1 алгоритм Евклида для нахождения наибольшего общего делителя).
(Если будет составлена программа, то она должна вводится в систему при помощи представленного учебным менеджером пароля для студента (ему она неизвестна), после правильного выполнения задания эта программа должна быть доступна студенту и в дальнейшем).
Если ответ окажется правильным, то компьютер зачтет Вам введенный ответ, зафиксирует его (исходные данные d и f, и наибольший общий делитель) в специальном МАССИВЕ РЕЗУЛЬТАТОВ и разрешит перейти к выполнению следующего задания. При этом данный МАССИВ РЕЗУЛЬТАТОВ будет ЗАШИФРОВАН И НЕДОСТУПЕН для использования студентами. Он заполняется постепенно, по мере выполнения соответствующих заданий, остается неизменным и при определенных условиях используется программой для заполнения соответствующих полей окон соответствующих заданий.
Если ответ студента окажется неверным, то необходимо будет выполнить все расчеты заново, закрыв и повторно запустив программу.
1.1.4 Алгоритм выполнения задания 1
При запуске программы открыта вкладка задания 1 лабораторной работы 1.
Задание 1 нахождение наибольшего общего делителя. В полях ввода «Число 1 (d)» и «Число 2 (f)» сгенерированы соответственно числа d и f. Требуется найти наибольший общий делитель этих чисел по алгоритму Евклида. Полученное значение надо ввести в поле ввода "Наибольший общий делитель” (Euclid(d, f)).
Для проверки расчетов студента необходимо нажать кнопку с надписью «Проверка корректности». Поля ввода со значениями чисел d и f для редактирования изначально недоступны. В ходе проверки программой верности расчетов студента все верные вычисления будут выведены в большом текстовом поле, которое находится под вышеназванными полями ввода.
Анализируя весь ход выполнения алгоритма, студент может закрепить полученные знания и одновременно обнаружить пропущенные им ошибки.
Если студент ввел неверный ответ, то ему придется ввести новые входные данные. В случае верного решения поставленной задачи соответствующая информация об этом будет выведена в большом текстовом поле, и студенту отныне станут доступны для ввода поля ввода задания 2 данной лабораторной работы. Студенту также станет доступно текущее задание, то есть поля окна задания 1. Иначе, если он один раз выполнил текущее задание правильно, то отныне ему становятся доступны для ввода ВСЕ поля ввода данного задания. При этом, в последствии, при вводе в качестве ответа неверного значения, студенту больше не придется выполнять все задание лабораторной работы с начала. Следовательно, возникает возможность коррекции вводимых данных при их подборе (данная возможность в программе реализована с целью упрощения труда студента, то есть создается условие для использования этой программы в дальнейшем в процессе выполнения ряда последующих работ). При выводе программой расчетов, она добавляет к ранее выполненным расчетам новые, не стирая первых.
1.2 Задание 2. Расширенный алгоритм Евклида для вычисления
мультипликативного обратного
1.2.1. Теория
Если gcd (d, f) = 1, то d имеет мультипликативное обратное по модулю f [1]. То есть, для положительного целого числа d f существует такое d -1 f, что d d -1 = 1 mod f. По алгоритму Евклида нахождения наибольшего общего делителя чисел d и f, для случаев, когда делитель оказывается равным 1, естественно, можно получить и мультипликативное обратное d.
1.2.2 Расширенный алгоритм Евклида для вычисления мультипликативного обратного
На рис.1.3 (слайд 1.4) приводится общая блок-схема расширенного алгоритма Евклида.
Рис. 1.3. Расширенный алгоритм Евклида для вычисления мультипликативного обратного
Пример МОБ: gcd (d, f) = gcd (550, 1769). Вычислить мультипликативное обратное числа 550 по модулю 1769.
1. X1 = 1, X2 = 0, X3 = f = 1769;
Y1 = 0, Y2 = 1, Y3 = d = 550.
Q = X3/Y3 = 1769/550 = 3.
T1 = X1 - Q Y1 = 1 - 3 0 = 1;
T2 = X2 - Q Y2 = 0 - 3 1 = - 3;
T3 = X3 - Q Y3 = 1769 - 3 550 = 119.
X1 = Y1 = 0;
X2 = Y2 = 1;
X3 = Y3 = 550.
Y1 = T1 = 1;
Y2 = T2 = -3;
Y3 = T3 = 119.
Соотношения:
f T1 + d T2 = 1769 1 + 550 (-3) = 119 = T3;
f X1 + d X2 = 1769 0 + 550 1 =550 = X3;
f Y1+ d Y2= 1769 1+ 550 (-3) = 119 = Y3.
2. Y3 0; Y3 1.
Q = X3/Y3 = 550/119 = 4.
T1 = X1 - Q Y1 = 0 - 4 1 = -4;
T2 = X2 - Q Y2 = 1 - 4 (-3) = 13;
T3 = X3 - Q Y3 = 550 - 4 119 = 74.
X1 = Y1 = 1;
X2 = Y2 = -3;
X3 = Y3 = 119.
Y1 = T1 = -4;
Y2 = T2 = 13;
Y3 = T3 = 74.
Соотношения:
f T1 + d T2 = 1769 (-4) + 550 13 = 7070 + 7150 = 74 = T3;
f X1 + d X2 = 1769 1 + 550 (-3) = 1769 - 1650 = 119 = X3;
f Y1+ d Y2= 1769 1+ 550 (-3) = 1769 - 1650 = 119 = Y3.
3. Y3 0; Y3 1.
Q = X3/Y3 = 119/74 = 1.
T1 = X1 - Q Y1 = 1 - 1 (-4) = 5;
T2 = X2 - Q Y2 = -3 - 1 (13) = -16;
T3 = X3 - Q Y3 = 119 - 1 74 = 45.
X1 = Y1 = -4;
X2 = Y2 = 13;
X3 = Y3 = 74.
Y1 = T1 = 5;
Y2 = T2 = -16;
Y3 = T3 = 45.
Соотношения:
f T1 + d T2 = 1769 5 + 550 (-16) = 8845 + 8800 = 45 = T3;
f X1 + d X2 = 1769 (-4) + 550 (13) = -7076 + 7150 = 74 = X3;
f Y1+ d Y2= 1769 5+ 550 (-16) = 8845 - 8800 = 45 = Y3.
4. Y3 0; Y3 1.
Q = X3/Y3 = 74/45 = 1.
T1 = X1 - Q Y1 = (-4) - 1 5 = -9;
T2 = X2 - Q Y2 = 13 - 1 (-16) = 29;
T3 = X3 - Q Y3 = 74 - 1 45 = 29.
X1 = Y1 = 5;
X2 = Y2 = -16;
X3 = Y3 = 45.
Y1 = T1 = -9;
Y2 = T2 = 29;
Y3 = T3 = 29.
Соотношения:
f T1 + d T2 = 1769 (-9) + 550 29 = -15927 + 15950 = 29 = T3;
f X1 + d X2 = 1769 5 + 550 (-16) = 8845 - 8800 = 45 = X3;
f Y1+ d Y2= 1769 (-9)+ 550 29 = -15921 + 15950 = 29 = Y3.
5. Y3 0; Y3 1.
Q = X3/Y3 = 45/29 = 1.
T1 = X1 - Q Y1 = 5 - 1 (-9) = 14;
T2 = X2 - Q Y2 = (-16) - 1 29 = -45;
T3 = X3 - Q Y3 = 45 - 1 29 = 16.
X1 = Y1 = -9;
X2 = Y2 = 29;
X3 = Y3 = 29.
Y1 = T1 = 14;
Y2 = T2 = -45;
Y3 = T3 = 16.
Соотношения:
f T1 + d T2 = 1769 14 + 550 (-45) = 24766 - 24750 = 16 = T3;
f X1 + d X2 = 1769 (-9) + 550 29 = -15921 + 15950 = 29 = X3;
f Y1+ d Y2= 1769 14 + 550 (-45) = 24766 - 24750 = 16 = Y3.
6. Y3 0; Y3 1.
Q = X3/Y3 = 29/16 = 1.
T1 = X1 - Q Y1 = (-9) - 1 14 = -23;
T2 = X2 - Q Y2 = 29 - 1 (-45) = 74;
T3 = X3 - Q Y3 = 29 - 1 16 = 13.
X1 = Y1 = 14;
X2 = Y2 = -45;
X3 = Y3 = 16.
Y1 = T1 = -23;
Y2 = T2 = 74;
Y3 = T3 = 13.
Соотношения:
f T1 + d T2 = 1769 (-23) + 550 74 = -40687 + 40700= 13 = T3;
f X1 + d X2 = 1769 14 + 550 (-45) = 24766 - 24750 = 16 = X3;
f Y1+ d Y2= 1769 (-29) + 550 74 = -40687 + 40700 = 13 = Y3.
7. Y3 0; Y3 1.
Q = X3/Y3 = 16/13 = 1.
T1 = X1 - Q Y1 = 14 - 1 (-23) = 37;
T2 = X2 - Q Y2 = (-45) - 1 74 = -119;
T3 = X3 - Q Y3 = 16 - 1 13 = 3.
X1 = Y1 = -23;
X2 = Y2 = 74;
X3 = Y3 = 13.
Y1 = T1 = 37;
Y2 = T2 = -119;
Y3 = T3 = 3.
Соотношения:
f T1 + d T2 = 1769 37 + 550 (-119) = 65453 - 65450= 3 = T3;
f X1 + d X2 = 1769 (-23) + 550 74 = -40687 + 40700 = 13 = X3;
f Y1+ d Y2= 1769 37 + 550 (-119) = 65453 - 65450 = 3 = Y3.
8. Y3 0; Y3 1.
Q = X3/Y3 = 13/3 = 4.
T1 = X1 - Q Y1 = (-23) - 4 37 = -171;
T2 = X2 - Q Y2 = 74 - 4 (-119) = 550;
T3 = X3 - Q Y3 = 13 - 4 3 = 1.
X1 = Y1 = 37;
X2 = Y2 = -119;
X3 = Y3 = 3.
Y1 = T1 = -171;
Y2 = T2 = 550;
Y3 = T3 = 1.
Соотношения:
f T1 + d T2 = 1769 (-171) + 550 550 = -302499 + 302500= 1 = T3;
f X1 + d X2 = 1769 37 + 550 (-119) = 65453 - 65450 = 3 = X3;
f Y1+ d Y2= 1769 (-171) + 550 550 = -302499 + 302500 = 1 = Y3.
9. Y3 = 1.
Q = X3/Y3 = 1/1 = 1.
T1 = X1 - Q Y1 = -171 - 1 (-171) = 0;
T2 = X2 - Q Y2 = 550 - 1 550 = 0;
T3 = X3 - Q Y3 = 1 - 1 1 = 0.
X1 = Y1 = -171;
X2 = Y2 = 550;
X3 = Y3 = 1.
Y1 = T1 = 0;
Y2 = T2 = 0;
Y3 = T3 = 0.
Соотношения:
f T1 + d T2 = 1769 0 + 550 0 = 0 = T3;
f X1 + d X2 = 1769 (-171) + 550 550 = - 302499 + 302500= 1 = X3;
f Y1+ d Y2= 1769 0 + 550 0 = 0 = Y3.
Так как на предыдущем (на восьмом) этапе
f Y1+ d Y2= 1769 (-171) + 550 550 = -302499 + 302500 = 1 = Y3,
и d Y2 = 1 + f (-Y1), то d Y2 1 mod 1769.
Основные параметры вычислений занесены в таблицу (табл. 1.1).
Таблица 1.1 Параметры вычислений gcd (550, 1769) = 1
|
Этапы |
Q |
X1 |
X2 |
X3 |
Y1 |
Y2 |
Y3 |
|
|
0 |
- |
1 |
0 |
1769 |
0 |
1 |
550 |
|
|
1 |
3 |
0 |
1 |
550 |
1 |
-3 |
119 |
|
|
2 |
4 |
1 |
-3 |
119 |
-4 |
13 |
74 |
|
|
3 |
1 |
-4 |
13 |
74 |
5 |
-16 |
45 |
|
|
4 |
1 |
5 |
-16 |
45 |
-9 |
29 |
29 |
|
|
5 |
1 |
-9 |
29 |
29 |
14 |
-45 |
16 |
|
|
6 |
1 |
14 |
-45 |
16 |
-23 |
74 |
13 |
|
|
7 |
1 |
-23 |
74 |
13 |
37 |
1119 |
3 |
|
|
8 |
4 |
37 |
-119 |
3 |
-171 |
550 |
1 |
|
|
9 |
1 |
-117 |
550 |
1 |
0 |
0 |
0 |
Ответ: gcd (550, 1769) = 1 и 550 550 1 mod 1769.
1.2.3 Инструкция по выполнению задания 2
Проанализировать пример МОБ. Из таблицы простых чисел (табл. 1) подобрать пару взаимно простых чисел d и f, таких, что d f. С использованием программы предыдущего задания (ПРОГРАММА 1 алгоритм Евклида нахождение наибольшего общего делителя) проверить действительно ли подобранные числа являются взаимно простыми?
ВРУЧНУЮ, С ИСПОЛЬЗОВАНИЕМ КАЛЬКУЛЯТОРА, определить мультипликативное обратное для d по модулю f (то есть такое d -1 f, что ff -1 = 1).
(Здесь также может быть использована студенческая программа на основаниях, указанных в предыдущем задании 1).
Ввести в компьютер полученный ответ и выбранные числа d и f и запустить ПРОГРАММУ 2 расширенный алгоритм Евклида для вычисления мультипликативного обратного.
Если результат окажется верным, то программа зачтет Вашу работу, зафиксирует исходные данные и значение ответа в специальном массиве аналогично предыдущему заданию и позволит перейти к выполнению следующего задания 3. В противном случае придется повторно выполнить данное задание 2 с испытанием новой пары чисел (введенные предыдущие исходные данные программой не воспринимаются).
1.2.4 Алгоритм выполнения задания 2
Задание 2 расширенный алгоритм Евклида для вычисления мультипликативного обратного. Выбираются два числа d и f (взаимно простые). Они вводятся соответственно в поля ввода «Число(d)» и «Модуль(f)». С использованием алгоритма Евклида необходимо подтвердить тот факт, что данные числа являются взаимно простыми. Для этого переходим в окно задания 1, вводим исходные числа в соответствующие поля окна задания 1 и проверяем эти числа являются ли они взаимно простыми (их наибольший общий делитель должен быть равен 1). При этом исходные данные окна задания 2 не должны меняться.
Возвращаемся к окну задания 2, вручную (или с использованием составленной студентом программы) вычисляем значение требуемого мультипликативного обратного.
Полученный ответ необходимо ввести в поле ввода под названием «Мультипликативное обратное числа d по модулю f». Для проверки программой расчетов студента нажать кнопку с надписью «Проверка корректности». Поля ввода со значениями чисел d и f для редактирования уже недоступны. В ходе проверки программой верности расчетов студента все верные расчеты будут выведены в большом текстовом поле, которое находится под выше названными полями ввода.
Анализируя весь ход выполнения алгоритма в этом поле, студент может закрепить полученные знания и одновременно обнаружить пропущенные им ошибки.
Если студент ввел неверный ответ, то ему придется ввести новые входные данные.
В случае верного решения студентом поставленной задачи информация о верности решения будет выведена в большом текстовом поле, и студенту станут доступны для ввода поля ввода задания 3.
Студенту также станут доступны поля текущего задания, то есть задания 2. Иначе, если студент один раз выполнил данное задание верно, то отныне ему становятся доступны для ввода ВСЕ поля ввода окна этого задания. При этом при вводе в качестве ответа неверного значения, больше не придется выполнить все задание 2 данной лабораторной работы с начала (данная возможность в программе реализована с целью упрощения труда студента в ходе ряда последующих работ).
1.3 Задание 3. Алгоритм быстрого возведения в степень для ab mod n при больших значениях b
1.3.1 Теория
Во многих криптографических алгоритмах приходится выполнять операции возведения в большую целую степень другого целого числа (тоже большого) по модулю n. Если операцию возведения в степень выполнять непосредственно целыми числами и только потом проводить сравнение по модулю n, то промежуточные значения окажутся просто огромными.
Вспомним следующее свойство арифметики в классах вычетов:
[(a1 mod n) (a2 mod n)] mod n = (a1 a2) mod n.
Значит, мы можем рассматривать промежуточные результаты по модулю n. Это намного облегчает вычисления. Будем вычислять ab mod n.
Будем пользоваться следующим алгоритмом.
Степень b представляется в двоичной системе счисления. Через k будем обозначать номера разрядов полученного двоичного числа, начиная с нуля справа налево. Через bi будем обозначать значение i-го разряда двоичного числа. Значение c в конце выполнения алгоритма будет соответствовать значению вычисленной степени.
1.3.2 Алгоритм быстрого возведения в степень для ab mod n при больших значениях b
На рис. 1.4 (слайд 1. 5) приводится блок-схема алгоритма быстрого возведения в степень для ab mod n при больших значениях b.
Далее приводятся два примера, поясняющие работу данного алгоритма.
Рис. 1.4. Блок-схема алгоритма быстрого вычисления ab mod n
Пример БВОЗ 1: Вычислить ab mod n, где a = 19, b = 5 и n = 119. Иначе, 195 mod 119 = ?
b = 510 = 101, k = 2, c = 0, d = 1, a = 19, n = 119.
1. k 0, k = 2;
c = 2 c = 2 0 = 0;
d = (d d) mod n = (1 1) mod 119 = 1 mod 119 = 1;
bk = b2 = 1;
c = c + 1 = 0 + 1 = 1;
d = (d a) mod n = (1 19) mod 119 = 19 mod 119 = 19 - 19 / 119 119 = 19 - 0 119 = 19.
k = k - 1 = 2 - 1 = 1.
2. k 0, k = 1;
c = 2 c = 2 1 = 2;
d = (d d) mod n = (19 19) mod 119 = 361 mod 119 = 361 - 361 / 119 119 = 361 - 3 119 = 361 - 357 = 4;
bk = b1 = 0;
k = k - 1 = 1 - 1 = 0.
3. k 0, k = 0;
c = 2 c = 2 2 = 4;
d = (d d) mod n = (4 4) mod 119 = 16 mod 119 = 16 - 16 / 119 119 = 16 - 0 119 = 16;
bk = b0= 1;
c = c + 1 = 4 + 1 = 5;
d = (d a) mod n = (16 19) mod 119 = 304 mod 119 = 304 - 304 / 119 119 = 304 - 2 119 = =66.
k = k - 1 = 0 - 1 = -1.
Ответ: 195 mod 119 = 66.
Пример БВОЗ 2: Вычислить ab mod n, где a = 66, b = 77 и n = 119. Иначе, 6677 mod 119 = ?
b = 7710 = 10011012, k = 6, c = 0, d = 1, a = 66, n = 119.
1. k 0, k = 6;
c = 2 c = 2 0 = 0;
d = (d d) mod n = (1 1) mod 119 = 1 mod 119 = 1;
bk = b6 = 1;
c = c + 1 = 0 + 1 = 1;
d = (d a) mod n = (1 66) mod 119 = 66 mod 119 = 66 - 66 / 119 119 = 66 - 0 119 = 66.
k = k - 1 = 6 - 1 = 5.
2. k 0, k = 5; b5 = 0;
c = 2 c = 2 1 = 2;
d = (d d) mod n = (66 66) mod 119 = 4356 mod 119 = 4356 - 4356 /119 119 = 4356 - (36 119) = 4356 - 4284 = 72;
k = k - 1 = 4;
bk = b4 = 0;
c = c 1 = 2 2 = 4;
d = (d d) mod n = (72 72) mod 119 = 5184 mod 119 = 5184 - 5184 / 119 119 = 5184 - (43119) = 5184 - 5117 = 67.
k = k - 1 = 4 - 1 = 3.
3. k 0, k = 3; b3 = 1;
c = 2 c = 2 4 = 8;
d = (d d) mod n = (67 67) mod 119 = 4489 mod 119 = 4489 - 4489 /119 119 = 4489 - (37 119) = 4489 - 4403 = 86;
c = c + 1 = 8 + 1 = 9;
d = (d a) mod n = (86 66) mod 119 = 5676 mod 119 = 5676 - 5676 / 119 119 = 5676 - (47 119) = 5676 - 5593 = 83.
k = k - 1 = 3 - 1 = 2; b2 = 1.
4. k 0, k = 2; b2 = 1;
c = 2 c = 2 9 = 18;
d = (d d) mod n = (83 83) mod 119 = 6889 mod 119 = 6889 - 6889 /119 119 = 6889 - (57 119) = 6889 - 6783 = 106;
c = c + 1 = 18 + 1 = 19;
d = (d a) mod n = (106 66) mod 119 = 6996 mod 119 = 6996 - 6996 / 119 119 = 6996 - (58 119) = 6996 - 6902 = 94.
k = k - 1 = 2 - 1 = 1; b1 = 0.
5. k 0, k = 1; b1 = 0;
c = 2 c = 2 19 = 38;
d = (d d) mod n = (94 94) mod 119 = 8836 mod 119 = 8836 - 8836 /119 119 = 8836 - (74 119) = 8836 - 8806 = 30;
b1 = 0;
6. k 0, k = 0; b0 = 1;
c = 2 c = 2 38 = 76;
d = (d d) mod n = (30 30) mod 119 = 900 mod 119 = 900 - 900 /119 119 = 900 - (7 119 = = 900 - 833 = 67;
c = c + 1 = 76 + 1 = 77;
d = (d a) mod n = (67 66) mod 119 = 4422 mod 119 = 4422 - 4422 / 119 119 = 4422 - (37 119) = 4422 - 4403 = 19.
k = k - 1 = 0 - 1 = -1.
Так как k 0, то получен следующий ответ.
Ответ: 6677 mod 119 = 19.
1.3.3 Инструкция по выполнению задания 3
Проанализировать приведенный алгоритм быстрого вычисления ab mod n по рассмотренным выше примерам БВОЗ 1 и БВОЗ 2. Из таблицы простых чисел подобрать два простых числа a и b, таких, что ab и 30a40, а 10b20. Числа могут быть любыми положительными целыми числами. Мы, с целью дальнейшего использования, в качестве примера рассматриваем простые малоразрядные числа (на практике в действительности эти числа очень большие).
вручную выполнить вычисление ab mod n, где 10 n 30. a, b, n и полученный результат ввести в ПРОГАММУ 3 быстрого возведения в степень для ab mod n при больших значениях b данного задания и запустить ее.
(Здесь также может быть использована студенческая программа, как и при выполнении предыдущих заданий данной лабораторной работы).
Если результат окажется верным, тогда выполнение данной лабораторной работы будет Вам зачтен. Исходные данные и верный ответ будут зафиксированы в МАССИВЕ РЕЗУЛЬТАТОВ.
В противном случае, если результат окажется неверным, то задание 3 данной лабораторной работы, как и ранее, должно выполняться повторно с использованием только новых исходных данных. Все остальное происходит так, как это было при выполнении предыдущих заданий.
1.3.4 Алгоритм выполнения задания 3
Задание 3 алгоритм быстрого вычисления ab mod n. Выбираются числа a, b и n. Их значения вводятся соответственно в поля ввода «Основание (а)», «Показатель (b)» и «Модуль (n)». Требуется вычислить число ab mod n. Полученный ответ необходимо ввести в поле ввода под названием «Ответ (а в степени b по модулю n)». Для проверки программой расчетов студента необходимо нажать на с надписью «Проверка корректности». Поля ввода окна задания 3 со значениями чисел a, b и n для редактирования уже недоступны. В ходе проверки программой верности расчетов студента все правильные расчеты будут выведены в большом текстовом поле, которое находится под выше названными полями ввода.
Если студент ввел неверный ответ, то ему придется ввести новые входные данные. При этом могут снова вводится только новые входные данные, исходя из которых, студент должен выполнить задание 3 данной лабораторной работы с начала.
В случае правильного решения студентом поставленной задачи соответствующая информация о верности решения будет выведена в большом текстовом поле. Студенту также станет, доступна текущее задание данной работы, то есть если студент один раз выполнил данное задание, верно, то отныне ему становятся доступны для ввода и коррекции ВСЕ поля ввода окна задания 3. Тогда, при вводе в качестве ответа неверного значения, студенту больше не придется выполнять задание с начала, а процесс правильного решения будет отображен (данная возможность в программе реализована с целью упрощения труда студента в ходе ряда последующих работ).
1.4 Общий алгоритм выполнения лабораторной работы
по криптографическим системам с открытым ключом
На рис. 1.5 (слайд 1.6) приводится общая блок-схема алгоритма выполнения лабораторной работы 1. Алгоритм построен с поэтапным контролем успеваемости исполнителя. Все задания должны быть выполнены последовательно успешно, чтобы в конце получить соответствующую оценку успеваемости.
Рис. 1.5. Общая блок-схема алгоритма выполнения лабораторной работы (главная программа)
ГЛОССАРИЙ
1. Безопасная система. Система считается безопасной, если она, используя соответ-ствующие аппаратные и программные средства, управляет доступом к информации так, что только должным образом авторизованные лица или же действующие от их имени процессы получают право читать, писать, создавать и удалять информацию.
2. Блок данных. Это последовательность битов, имеющая фиксированную длину и используемая для представления данных в памяти или для их пересылки.
3. Взаимно простые целые числа a и b. Целые числа a и b являются взаимно простыми, если они не имеют общих простых делителей, то есть если их единственным общим делителем является 1 (иначе, gcd(a, b) = 1).
4. Дискретный логарифм. Для любого целого числа b и любого первообразного корня a простого числа p однозначно определяется показатель степени i, при котором b = ai mod p, где
0 i (p-1). Этот показатель степени и есть дискретный логарифм.
5. Зашифрование данных. Процесс преобразования открытых данных в зашифрованные при помощи шифра.
6. Криптоанализ. Анализ криптографической системы и/или чувствительности данных, включая открытый текст.
7. Криптографическая защита. Это защита данных при помощи криптографического преобразования данных.
8. Криптографический алгоритм. Это алгоритм, который трансформирует данные с целью закрыть (скрыть) содержащуюся в них информацию и который при этом использует, по крайней мере, один секретный параметр.
9. Криптографический протокол. Установленный порядок действий абонентов при решении некоторой криптографической задачи (передача секретного сообщения, обмен ключами и др.).
10. Криптографическое контрольное значение. Это информация, получаемая в результате выполнения криптографического преобразования блока данных. Примечание. Контрольное значение может быть получено путем выполнения одного или нескольких шагов и является результатом математической функции ключа и блока данных. Оно обычно используется для проверки целостности блока данных.
11. Криптографическое преобразование. Это преобразование данных при помощи шифро-вания и (или) выработки имитосвязи.
12. Криптография. Дисциплина, охватывающая принципы, средства и методы преобра-зования данных для сокрытия их информационного содержимого, предотвращения их от необнаруживаемой модификации и/или их несанкционированного использования.
13. Криптология. В общем виде криптологию называют наукой о шифрах. Криптология (образовано из греческих слов: «cryptos» -- тайный и «logos» -- слово) -- это наука о создании и анализе систем безопасной связи, хотя тут скорее всего имеется в виду не безопасная, а секретная связь (секретность, как известно, является только одним из элементов безопасности или целостности информации).
14. Наибольший общий делитель чисел a и b. Наибольшим общим делителем чисел a и b является положительное целое число c, если: c является делителем a и b; любой делитель a и b является делителем c. Это записывается так: c = gcd(a, b).
15. Обратимость. Это важное и необходимое свойство преобразований шифра, которое позволяет однозначно восстанавливать “читаемость” информации, защищенной шифром.
16. Открытый ключ. Это открытая (несекретная) половина криптографической пары, используемая при шифровании с применением открытых ключей. Открытые ключи обычно используются при шифровании ключей сеансов, проверке цифровых подписей и шифровании данных, предназначенных для расшифровки соответствующим закрытым ключом.
17. Открытый текст. Это смысловые данные, семантическое содержание которых доступно, или это исходное сообщение (или исходная информация), которое должно быть преобразовано с целью защиты.
18. Пароль. 1) Это конфиденциальная информация аутентификации, обычно состоящая из строки знаков; 2) идентификатор субъекта доступа, который является его (субъекта) секретом.
19. Первообразный корень простого числа p. Это такое число a, что все числа a mod p, a2 mod p, …,a p-1 mod p являются разными и представляют все целые числа от 1 до (p-1) в некоторой перестановке.
20. Преобразование замены. Замещение каждого элемента открытого текста (бита, буквы, группы битов или группы букв) некоторым другим элементом.
21. Преобразование перестановки. Изменение порядка следования элементов открытого текста (при этом главным требованием является отсутствие потерь информации, то есть обратимость всех операций).
22. Продукционные шифры. Шифры, в которых применяются комбинации нескольких операций замены и перестановки.
23. Простые числа. Целое число p 1 называется простым, если его делителями являются только числа 1 и p.
24. Расшифрование данных. Это процесс преобразования зашифрованных данных в открытые данные при помощи шифра.
25. Симметричная криптографическая система (криптосистема с секретным ключом). Отправитель и получатель используют один и тот же ключ для зашифрования и для расши-фрования. Эти ключи либо совпадают, либо обладают некоторой симметрией.
26. Стойкость криптосистемы. Это способность противостоять попыткам криптоаналитика дешифровать зашифрованное сообщение (при этом предполагается, что криптоаналитик хорошо вооружен современными знаниями и различными средствами, а целью попытки является раскрыть ключи или нарушить целостность и (или) подлинность сообщения).
27. Цифровая подпись. Это шифрованная электронная подпись, формируемая с использованием цифрового сертификата, которая подтверждает подлинность макроса или документа, то есть наличие подписи говорит о том, что макрос или документ получен от владельца подписи, и он не был изменен.
28. Шифр. Это совокупность обратимых преобразований множества возможных открытых данных на множество возможных зашифрованных данных, осуществляемых по определенным правилам с применением ключей.
29. Шифрование. Процесс зашифрования или расшифрования;- криптографическое преобразование данных для получения шифротекста. Примечание. Шифрование может быть необратимым процессом, в связи с чем соответствующий процесс дешифрования невозможно реализовать.
30. Электронная цифрованная подпись. Это последовательность символов, полученная в результате криптографического преобразования исходной информации с использованием закрытого ключа электронной цифровой подписи, которая позволяет лицу, владеющему открытым ключом электронной цифровой подписи, установить целостность и неизменность этой информации, а также владельца закрытого ключа электронной цифровой подписи.
2. Лабораторная работа 2. Криптография с открытым ключом. Алгоритм вычисления степеней целого числа am по модулю p
и целых чисел, принадлежащих показателю (p), первообразных корней по модулю p. Обмен ключами по схеме Диффи-Хеллмана
В данной лабораторной работе, с частичным использованием уже освоенных математических методов и алгоритмов, вычисляются первообразные корни по модулю. Далее определяются и рассчитываются открытый и секретный ключи абонентов, производится обмен открытыми ключами абонентов, вычисляются каждой стороной общий секретный сеансовый ключ. Затем производятся зашифрование определенного открытого текста и его расшифрование с использованием этого общего сеансового ключа.
Работа состоит из двух заданий.
Задание 1. Алгоритм вычисления степеней целого числа am по модулю p и целых чисел, принадлежащих показателю (p) первообразных корней по модулю p.
Задание 2. Генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети.
2.1 Задание 1. Алгоритм вычисления степеней целого числа am
по модулю p и целых чисел, принадлежащих показателю
(p) первообразных корней по модулю p
2.1.1 Теория
В начале напомним некоторые важные понятия из теории чисел.
Число положительных целых значений, которые меньше n и являются взаимно простыми с n, обозначается через (n) и называется функцией Эйлера. Для простого числа p
(p) = p - 1.
Если имеется два простых числа p и q, тогда для n = pq получим (n) = (pq) = (p) (q) = (p-1) (q-1).
Теорема Эйлера утверждает, что для любых взаимно простых чисел a и n a(n) 1 mod n. Пример: a = 3, n = 10, (n) = (pq) = (p) (q) = (p-1) (q-1) = (5-1) (2-1) = 4. Следовательно, 34 = 81 1 mod 10.
Важным является следующее.
Если a и n являются взаимно простыми, то существует, по крайней мере, одно целое число m, удовлетворяющее соотношению am 1 mod n, где m = (n). Для наименьшего из положительных m, при которых выполняется указанное условие, используются следующие названия:
Ё порядок числа a по модулю n;
Ё показатель, которому принадлежит a по модулю n;
Ё длина периода последовательности, генерируемой степенями a.
Подобные документы
Краткие сведения о истории криптографии. Симметричные криптосистемы (системы с секретным ключом) и системы с открытым ключом. Аутентификация и идентификация, электронная цифровая подпись. Управление ключами, их архивирование, хранение и восстановление.
доклад [458,9 K], добавлен 08.11.2013Появление шифров, история эволюции криптографии. Способ приложения знаний особенностей естественного текста для нужд шифрования. Критерии определения естественности. Способ построения алгоритмов симметричного шифрования. Криптосистема с открытым ключом.
реферат [452,2 K], добавлен 31.05.2013Разновидности защиты компьютерной информации. Особенности алгоритмов и шрифтов, применяемых в криптографии. Специфика использования криптосистем с открытым ключом. Структура вредоносного программного обеспечения. Обеспечение безопасности баз данных.
презентация [393,2 K], добавлен 05.04.2012Понятие и история изобретения криптосистемы с открытым ключом. Свойства односторонней функции и сложность раскрытия шифра. Описание алгоритма RSA: шифрование и дешифрование. Возможные атаки, способы взлома, обоснование и практическая реализация RSA.
курсовая работа [45,9 K], добавлен 24.12.2011Принципы криптографии, история ее развития. Шифры с секретным и с открытым ключом. Криптография как оружие, угрозы данным, их раскрытие. Ужесточчение мер в отношении использования криптоалгоритмов. Раскрытие криптосистемы и стойкость системы к раскрытию.
доклад [35,8 K], добавлен 09.11.2009Изучение, освоение на примере симметричных шифров элементы практической криптографии. Использование расширенного алгоритма Евклида для нахождения обратного по модулю числа. Ознакомление с демо-версией программы симметричного шифрования с секретным ключом.
лабораторная работа [97,5 K], добавлен 18.04.2015Особенности шифрования данных, предназначение шифрования. Понятие криптографии как науки, основные задачи. Анализ метода гаммирования, подстановки и метода перестановки. Симметрические методы шифрования с закрытым ключом: достоинства и недостатки.
курсовая работа [564,3 K], добавлен 09.05.2012Актуальность и предыстория проблемы построения систем связи с открытым ключом. Алгоритм кодирования, перевода из десятичного числа в двоичное, быстрого возведения числа в степень, поиска взаимно простых чисел. Дешифрование сообщения по криптоалгоритму.
курсовая работа [140,3 K], добавлен 20.06.2017Обмен информации, защищенной от фальсификаций и незаконных пользователей. Распределение секретных ключей с помощью системы с открытым ключом. Разработка модулей системы генерации ключей и обмена конфиденциальной информацией для группы пользователей.
курсовая работа [2,0 M], добавлен 17.11.2011Основные программы стеганографии. Программно-аппаратные средства криптографической защиты информации с закрытым ключом. Требования к используемым криптографическим средствам за рубежом и в России. Отечественные системы шифрования с открытым ключом.
отчет по практике [64,6 K], добавлен 18.09.2013
