Криптография с открытым ключом

 

ОГЛАВЛЕНИЕ


ОБЩИЕ ПОЛОЖЕНИЯ

ОСОБЕННОСТИ ИЗУЧЕНИЯ И ВЫПОЛНЕНИЯ ЦИКЛА ЛАБОРАТОРНЫХ РАБОТ

. ЛАБОРАТОРНАЯ РАБОТА 1. КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ И ИЗУЧЕНИЕ НЕОБХОДИМЫХ АЛГОРИТМОВ

.1 Задание 1. Поиск наибольшего общего делителя ? алгоритм Евклида

.1.1 Теория, основные понятия и определения

.1.2 Алгоритм Евклида ? нахождения наибольшего общего делителя

.1.3 Инструкция по выполнению задания 1

.1.4 Алгоритм выполнения задания 1

.2 Задание 2. Расширенный алгоритм Евклида для вычисления мультипликативного обратного

.2.1 Теория

.2.2 Расширенный алгоритм Евклида для вычисления мультипликативного обратного

.2.3 Инструкция по выполнению задания 2

.2.4 Алгоритм выполнения задания 2

.3. Задание 3. Алгоритм быстрого возведения в степень для ab mod n при больших значениях b

.3.1 Теория

.3.2 Алгоритм быстрого возведения в степень для ab mod n при больших значениях b

.3.3 Инструкция по выполнению задания 3

.3.4 Алгоритм выполнения задания 3

.4 Общий алгоритм выполнения лабораторной работы по криптографическим системам с открытым ключом

ГЛОССАРИЙ

. ЛАБОРАТОРНАЯ РАБОТА 2. КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ. АЛГОРИТМ ВЫЧИСЛЕНИЯ СТЕПЕНЕЙ ЦЕЛОГО ЧИСЛА AM ПО МОДУЛЮ P И ЦЕЛЫХ ЧИСЕЛ, ПРИНАДЛЕЖАЩИХ ПОКАЗАТЕЛЮ ?(P), ? ПЕРВООБРАЗНЫХ КОРНЕЙ ПО МОДУЛЮ P. ОБМЕН КЛЮЧАМИ ПО СХЕМЕ ДИФФИ-ХЕЛЛМАНА

.1 Задание 1. Алгоритм вычисления степеней целого числа am по модулю p и целых чисел, принадлежащих показателю ?(p) ? первообразных корней по модулю p

.1.1 Теория

.1.2 Алгоритм определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней

.1.3 Инструкция по выполнению задания 1

.1.4 Алгоритм выполнения задания 1. Вычисление степеней целого числа am

по модулю p и целых чисел, принадлежащих показателю (p) (первообразных корней по модулю p)

.2 Задание 2. Генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети

.2.1 Теория

.2.2 Инструкция по выполнению задания 2

.2.3 Общее положение по выполнению задания 2 ? генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети

ГЛОССАРИЙ

. ЛАБОРАТОРНАЯ РАБОТА 3. КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ. МЕТОД ЗАШИФРОВАНИЯ С ОТКРЫТЫМ КЛЮЧОМ RSA

.1 Теория, криптография с открытым ключом. Метод зашифрования с открытым ключом RSA

.2 Алгоритм RSA

.3 Общее положение по выполнению лабораторной работы. Метод зашифрования RSA

.3.1 Задание 1 ? RSA-0 ? подготовка для выполнения алгоритма зашифрования открытого сообщения открытым ключом RSA-1

.3.2 Задание 2 ? RSA-1 - выполнение алгоритма зашифрования открытого сообщения открытым ключом RSA-1

.3.3 Задание 3 ? RSA-2 - выполнение алгоритма расшифрования зашифрованного сообщения секретным ключом RSA-1

.4 Общий алгоритм выполнения лабораторной работы 3 по криптографическим системам с открытым ключом

ГЛОССАРИЙ

СПИСОК УТВЕРЖДЕНИЙ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЯ

алгоритм криптография открытый ключ


ОБЩИЕ ПОЛОЖЕНИЯ


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

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

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

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

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

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

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

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

К основным задачам, стоящим перед написанием работы «Криптография с открытым ключом» относятся:

? изучение криптографических алгоритмов с открытым ключом;

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

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

Освоил математические основы и наиболее распространенные алгоритмы криптографии с открытым ключом;

изучил основные области применения методов криптографии с открытым ключом;

приобрел навыки практического применения расчетные схемы определения ключей;

использование метода открытого обмена ключами по схеме Диффи-Хеллмана и алгоритм зашифрования и расшифрования RSA.


1. Криптография с открытым ключом. Теоретические сведения
и изучение необходимых алгоритмов

1.1 Проблемы традиционных методов шифрования


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

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

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

Алгоритмы шифрования с открытым ключом зависят от двух ключей: одного ключа для зашифрования и другого ключа, связанного с первым, для расшифрования (рис. 1.1). С точки зрения вычислений нереально определить ключ расшифрования, зная только используемый криптографический алгоритм и ключ зашифрования. В некоторых алгоритмах любой из этих ключей может применяться для зашифрования, а другой - для расшифрования.

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

Рис. 1.1. Криптографическая система с открытым ключом


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


1.2 Алгоритм Евклида - нахождения наибольшего общего делителя


Алгоритм Евклида нахождения наибольшего общего делителя основывается на следующей теореме (приводим без доказательства).

Для любого неотрицательного числа X и любого положительного числа Y справедливо следующее:


gcd (X, Y) = gcd (Y, X mod Y),

где X>Y>0.

Чтобы определить наибольший общий делитель, приведенное выше равенство (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 и d>200, а f>100. Определить по заданному алгоритму Евклида вручную, с использованием калькулятора (или составив программу на любом языке программирования), наибольший общий делитель чисел 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;= 0, Y2 = 1, Y3 = d = 550.

Q = ëX3/Y3û = ë1769/550û = 3.= X1 - Q ´ Y1 = 1 - 3 ´ 0 = 1; = X2 - Q ´ Y2 = 0 - 3 ´ 1 = - 3;= X3 - Q ´ Y3 = 1769 - 3 ´ 550 = 119.= Y1 = 0;= Y2 = 1;= Y3 = 550.= T1 = 1;= T2 = -3;= T3 = 119.

Соотношения:´ T1 + d ´ T2 = 1769 ´ 1 + 550 ´ (-3) = 119 = T3;´ X1 + d ´ X2 = 1769 ´ 0 + 550 ´ 1 =550 = X3;´ Y1+ d ´ Y2= 1769 ´ 1+ 550 ´ (-3) = 119 = Y3.

2. Y3 ¹ 0; Y3 ¹ 1.= ëX3/Y3û = ë550/119û = 4.= X1 - Q ´ Y1 = 0 - 4 ´ 1 = -4; = X2 - Q ´ Y2 = 1 - 4 ´ (-3) = 13;= X3 - Q ´ Y3 = 550 - 4 ´ 119 = 74.= Y1 = 1;= Y2 = -3;= Y3 = 119.= T1 = -4;= T2 = 13;= T3 = 74.

Соотношения:´ T1 + d ´ T2 = 1769 ´ (-4) + 550 ´ 13 = 7070 + 7150 = 74 = T3;´ X1 + d ´ X2 = 1769 ´ 1 + 550 ´ (-3) = 1769 - 1650 = 119 = X3;´ Y1+ d ´ Y2= 1769 ´ 1+ 550 ´ (-3) = 1769 - 1650 = 119 = Y3.

3. Y3 ¹ 0; Y3 ¹ 1.= ëX3/Y3û = ë119/74û = 1.= X1 - Q ´ Y1 = 1 - 1 ´ (-4) = 5; = X2 - Q ´ Y2 = -3 - 1 ´ (13) = -16;= X3 - Q ´ Y3 = 119 - 1 ´ 74 = 45.= Y1 = -4;= Y2 = 13;= Y3 = 74.= T1 = 5;= T2 = -16;= T3 = 45.

Соотношения:´ T1 + d ´ T2 = 1769 ´ 5 + 550 ´ (-16) = 8845 + 8800 = 45 = T3;´ X1 + d ´ X2 = 1769 ´ (-4) + 550 ´ (13) = -7076 + 7150 = 74 = X3;´ Y1+ d ´ Y2= 1769 ´ 5+ 550 ´ (-16) = 8845 - 8800 = 45 = Y3.

4. Y3 ¹ 0; Y3 ¹ 1.= ëX3/Y3û = ë74/45û = 1. = X1 - Q ´ Y1 = (-4) - 1 ´ 5 = -9; = X2 - Q ´ Y2 = 13 - 1 ´ (-16) = 29;= X3 - Q ´ Y3 = 74 - 1 ´ 45 = 29.= Y1 = 5;= Y2 = -16;= Y3 = 45.= T1 = -9;= T2 = 29;= T3 = 29.

Соотношения:´ T1 + d ´ T2 = 1769 ´ (-9) + 550 ´ 29 = -15927 + 15950 = 29 = T3;´ X1 + d ´ X2 = 1769 ´ 5 + 550 ´ (-16) = 8845 - 8800 = 45 = X3;´ Y1+ d ´ Y2= 1769 ´ (-9)+ 550 ´ 29 = -15921 + 15950 = 29 = Y3.

5. Y3 ¹ 0; Y3 ¹ 1.= ëX3/Y3û = ë45/29û = 1.= X1 - Q ´ Y1 = 5 - 1 ´ (-9) = 14; = X2 - Q ´ Y2 = (-16) - 1 ´ 29 = -45;= X3 - Q ´ Y3 = 45 - 1 ´ 29 = 16.= Y1 = -9;= Y2 = 29;= Y3 = 29.= T1 = 14;= T2 = -45;= T3 = 16.

Соотношения:´ T1 + d ´ T2 = 1769 ´ 14 + 550 ´ (-45) = 24766 - 24750 = 16 = T3;´ X1 + d ´ X2 = 1769 ´ (-9) + 550 ´ 29 = -15921 + 15950 = 29 = X3;´ Y1+ d ´ Y2= 1769 ´ 14 + 550 ´ (-45) = 24766 - 24750 = 16 = Y3.

6. Y3 ¹ 0; Y3 ¹ 1.= ëX3/Y3û = ë29/16û = 1.= X1 - Q ´ Y1 = (-9) - 1 ´ 14 = -23;

T2 = X2 - Q ´ Y2 = 29 - 1 ´ (-45) = 74;= X3 - Q ´ Y3 = 29 - 1 ´ 16 = 13.

X1 = Y1 = 14;= Y2 = -45;= Y3 = 16.= T1 = -23;= T2 = 74;= T3 = 13.

Соотношения:´ T1 + d ´ T2 = 1769 ´ (-23) + 550 ´ 74 = -40687 + 40700= 13 = T3;´ X1 + d ´ X2 = 1769 ´ 14 + 550 ´ (-45) = 24766 - 24750 = 16 = X3;´ Y1+ d ´ Y2= 1769 ´ (-29) + 550 ´ 74 = -40687 + 40700 = 13 = Y3.

7. Y3 ¹ 0; Y3 ¹ 1.= ëX3/Y3û = ë16/13û = 1.= X1 - Q ´ Y1 = 14 - 1 ´ (-23) = 37; = X2 - Q ´ Y2 = (-45) - 1 ´ 74 = -119;= X3 - Q ´ Y3 = 16 - 1 ´ 13 = 3.= Y1 = -23;= Y2 = 74;= Y3 = 13.= T1 = 37;= T2 = -119;= T3 = 3.

Соотношения:´ T1 + d ´ T2 = 1769 ´ 37 + 550 ´ (-119) = 65453 - 65450= 3 = T3;´ X1 + d ´ X2 = 1769 ´ (-23) + 550 ´ 74 = -40687 + 40700 = 13 = X3;´ Y1+ d ´ Y2= 1769 ´ 37 + 550 ´ (-119) = 65453 - 65450 = 3 = Y3.

8. Y3 ¹ 0; Y3 ¹ 1.= ëX3/Y3û = ë13/3û = 4.= X1 - Q ´ Y1 = (-23) - 4 ´ 37 = -171;

T2 = X2 - Q ´ Y2 = 74 - 4 ´ (-119) = 550;= X3 - Q ´ Y3 = 13 - 4 ´ 3 = 1.= Y1 = 37;= Y2 = -119;= Y3 = 3.= T1 = -171;= T2 = 550;= T3 = 1.

Соотношения:´ T1 + d ´ T2 = 1769 ´ (-171) + 550 ´ 550 = -302499 + 302500= 1 = T3;´ X1 + d ´ X2 = 1769 ´ 37 + 550 ´ (-119) = 65453 - 65450 = 3 = X3;´ Y1+ d ´ Y2= 1769 ´ (-171) + 550 ´ 550 = -302499 + 302500 = 1 = Y3.

9. Y3 = 1.

Q = ëX3/Y3û = ë1/1û = 1.= X1 - Q ´ Y1 = -171 - 1 ´ (-171) = 0; = X2 - Q ´ Y2 = 550 - 1 ´ 550 = 0;= X3 - Q ´ Y3 = 1 - 1 ´ 1 = 0.= Y1 = -171;

X2 = Y2 = 550;= Y3 = 1.

Y1 = T1 = 0;= T2 = 0;= T3 = 0.


Соотношения:´ T1 + d ´ T2 = 1769 ´ 0 + 550 ´ 0 = 0 = T3;´ X1 + d ´ X2 = 1769 ´ (-171) + 550 ´ 550 = - 302499 + 302500= 1 = X3; ´ 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

ЭтапыQX1X2X3Y1Y2Y30-1017690155013015501-3119241-3119-4137431-413745-1645415-1645-9292951-9292914-45166114-4516-23741371-23741337111938437-1193-171550191-1175501000

Ответ: gcd (550, 1769) = 1 и 550 ´ 550 º 1 mod 1769.


1.2.3 Инструкция по выполнению задания 2

Проанализировать пример МОБ. Из таблицы простых чисел (табл. 1) подобрать пару взаимно простых чисел d и f, таких, что d < f. С использованием программы предыдущего задания (ПРОГРАММА 1 - алгоритм Евклида нахождение наибольшего общего делителя) проверить - действительно ли подобранные числа являются взаимно простыми?

ВРУЧНУЮ, С ИСПОЛЬЗОВАНИЕМ КАЛЬКУЛЯТОРА, определить мультипликативное обратное для d по модулю f (то есть такое d -1< f, что f´f -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) mod n = (1 ´ 1) mod 119 = 1 mod 119 = 1;k = b2 = 1;= c + 1 = 0 + 1 = 1; = (d ´ a) mod n = (1 ´ 19) mod 119 = 19 mod 119 = 19 - ë19 / 119û ´ 119 = 19 - 0 ´119 = 19.= k - 1 = 2 - 1 = 1.

2. k > 0, k = 1;= 2 ´ c = 2 ´ 1 = 2;= (d ´ d) mod n = (19 ´ 19) mod 119 = 361 mod 119 = 361 - ë361 / 119û ´ 119 = 361 - 3 ´ 119 = 361 - 357 = 4;k = b1 = 0;= k - 1 = 1 - 1 = 0.

3. k > 0, k = 0;= 2 ´ c = 2 ´ 2 = 4;= (d ´ d) mod n = (4 ´ 4) mod 119 = 16 mod 119 = 16 - ë16 / 119û ´ 119 = 16 - 0 ´ 119 = 16;k = b0= 1;= c + 1 = 4 + 1 = 5; = (d ´ a) mod n = (16 ´ 19) mod 119 = 304 mod 119 = 304 - ë304 / 119û ´ 119 = 304 - 2 ´119 = =66.= k - 1 = 0 - 1 = -1.

Ответ: 195 mod 119 = 66.

Пример БВОЗ 2: Вычислить ab mod n, где a = 66, b = 77 и n = 119. Иначе, 6677 mod 119 = ?= 7710 = 10011012, k = 6, c = 0, d = 1, a = 66, n = 119.

1. k > 0, k = 6;= 2 ´ c = 2 ´ 0 = 0;= (d ´ d) mod n = (1 ´ 1) mod 119 = 1 mod 119 = 1;k = b6 = 1;= c + 1 = 0 + 1 = 1; = (d ´ a) mod n = (1 ´ 66) mod 119 = 66 mod 119 = 66 - ë66 / 119û ´ 119 = 66 - 0 ´119 = 66.= k - 1 = 6 - 1 = 5.

2. k > 0, k = 5; b5 = 0;= 2 ´ c = 2 ´ 1 = 2;= (d ´ d) mod n = (66 ´ 66) mod 119 = 4356 mod 119 = 4356 - ë4356 /119û ´ 119 = 4356 - (36´ ´ 119) = 4356 - 4284 = 72;= k - 1 = 4;k = b4 = 0;= c ´ 1 = 2 ´ 2 = 4; = (d ´ d) mod n = (72 ´ 72) mod 119 = 5184 mod 119 = 5184 - ë5184 / 119û ´ 119 = 5184 - (43´119) = 5184 - 5117 = 67.= k - 1 = 4 - 1 = 3.

3. k > 0, k = 3; b3 = 1;= 2 ´ c = 2 ´ 4 = 8;= (d ´ d) mod n = (67 ´ 67) mod 119 = 4489 mod 119 = 4489 - ë4489 /119û ´ 119 = 4489 - (37 ´ ´119) = 4489 - 4403 = 86;= c + 1 = 8 + 1 = 9; = (d ´ a) mod n = (86 ´ 66) mod 119 = 5676 mod 119 = 5676 - ë5676 / 119û ´ 119 = 5676 - (47´ ´119) = 5676 - 5593 = 83.= k - 1 = 3 - 1 = 2; b2 = 1.

4. k > 0, k = 2; b2 = 1;= 2 ´ c = 2 ´ 9 = 18;= (d ´ d) mod n = (83 ´ 83) mod 119 = 6889 mod 119 = 6889 - ë6889 /119û ´ 119 = 6889 - (57 ´ ´ 119) = 6889 - 6783 = 106;= c + 1 = 18 + 1 = 19; = (d ´ a) mod n = (106 ´ 66) mod 119 = 6996 mod 119 = 6996 - ë6996 / 119û ´ 119 = 6996 - (58 ´119) = 6996 - 6902 = 94.= k - 1 = 2 - 1 = 1; b1 = 0.

5. k > 0, k = 1; b1 = 0;= 2 ´ c = 2 ´ 19 = 38;= (d ´ d) mod n = (94 ´ 94) mod 119 = 8836 mod 119 = 8836 - ë8836 /119û ´ 119 = 8836 - (74 ´ ´119) = 8836 - 8806 = 30;1 = 0;

6. k > 0, k = 0; b0 = 1;= 2 ´ c = 2 ´ 38 = 76;= (d ´ d) mod n = (30 ´ 30) mod 119 = 900 mod 119 = 900 - ë900 /119û ´ 119 = 900 - (7 ´ 119 = = 900 - 833 = 67; = c + 1 = 76 + 1 = 77; = (d ´ a) mod n = (67 ´ 66) mod 119 = 4422 mod 119 = 4422 - ë4422 / 119û ´ 119 = 4422 - (37´ ´119) = 4422 - 4403 = 19. = k - 1 = 0 - 1 = -1.

Так как k < 0, то получен следующий ответ.

Ответ: 6677 mod 119 = 19.


1.3.3 Инструкция по выполнению задания 3

Проанализировать приведенный алгоритм быстрого вычисления ab mod n по рассмотренным выше примерам БВОЗ 1 и БВОЗ 2. Из таблицы простых чисел подобрать два простых числа a и b, таких, что a>b и 30<a<40, а 10<b<20. Числа могут быть любыми положительными целыми числами. Мы, с целью дальнейшего использования, в качестве примера рассматриваем простые малоразрядные числа (на практике в действительности эти числа очень большие).

вручную выполнить вычисление 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
и целых чисел, принадлежащих показателю f(p), - первообразных корней по модулю p. Обмен ключами по схеме Диффи-Хеллмана

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

Работа состоит из двух заданий.

Задание 1. Алгоритм вычисления степеней целого числа am по модулю p и целых чисел, принадлежащих показателю f(p) - первообразных корней по модулю p.

Задание 2. Генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети.


2.1 Задание 1. Алгоритм вычисления степеней целого числа am
по модулю p и целых чисел, принадлежащих показателю
f(p) - первообразных корней по модулю p

2.1.1 Теория

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

Число положительных целых значений, которые меньше n и являются взаимно простыми с n, обозначается через f(n) и называется функцией Эйлера. Для простого числа p

f(p) = p - 1.


Если имеется два простых числа p и q, тогда для n = pq получим f(n) = f(pq) = f(p) ´ f(q) = (p-1) ´ (q-1).

Теорема Эйлера утверждает, что для любых взаимно простых чисел a и n af(n) º 1 mod n. Пример: a = 3, n = 10, f(n) = f(pq) = f(p) ´ f(q) = (p-1) ´ (q-1) = (5-1) ´ (2-1) = 4. Следовательно, 34 = 81 º 1 mod 10.

Важным является следующее.

Если a и n являются взаимно простыми, то существует, по крайней мере, одно целое число m, удовлетворяющее соотношению am º 1 mod n, где m = f(n). Для наименьшего из положительных m, при которых выполняется указанное условие, используются следующие названия:

¨порядок числа a по модулю n;

¨показатель, которому принадлежит a по модулю n;

¨длина периода последовательности, генерируемой степенями a.

Пример СТЕП 1. Рассмотрим степени числа 5 по модулю 19:


Поэтому в нашем примере, любые две степени числа 5, показатели которых отличаются на 9 (или на число, кратное 9), сравнимы по модулю 19. Иначе, последовательность является периодической с периодом, равным наименьшему положительному показателю m, при котором 5m = 1 mod 19.

В общем случае можно сказать, что наивысшим из показателей, которому может принадлежать число a по модулю n, является f(n). Числа, принадлежащие показателю f(n), называются первообразными корнями по модулю n.

В таблице (табл. 2.1), в продолжение примера, приводятся степени целых чисел по модулю 19 (первая выделенная строка соответствует степеням; затемненные части строк соответствуют конкретным периодам).

Как видно, все последовательности заканчиваются числом 1.

В нашем примере длина последовательности является делителем f(19) = 18. Некоторые последовательности для a < 19 будут иметь длину 18. В таком случае говорят, что целое число a генерирует (своими степенями) множество всех ненулевых вычетов по модулю 19.

Любое из этих чисел называют первообразным корнем по модулю 19.

Важность этого понятия подтверждается тем, что если a является первообразным корнем n, его степени a1, a2,…,af(n) оказываются различными по модулю n и взаимно простыми с n.

В частности, для простого числа p, если a является первообразным корнем p, то a1, a2,…,ap-1 оказываются различными по модулю n и взаимно простыми с n.

Как видно из таблицы, для простого числа 19 его первообразными корнями являются числа 2, 3, 10, 13, 14 и 15.

Не все целые числа имеют первообразные корни. Этими числами могут быть числа 2, 4, pa и 2pa, где p - любое нечетное простое число.

Таблица 2.1 Степени целых чисел по модулю 19


2.1.2 Алгоритм определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней

На рисунке 2.1, слайд 2.3 приводится общая блок-схема алгоритма определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней.


Рис. 2.1. Блок-схема алгоритма вычисления степеней целого числа am
по модулю p и целых чисел, принадлежащих показателю f(p)

2.1.3 Инструкция по выполнению задания 1

Проанализировать приведенный пример СТЕП 1 совместно с данными таблицы 2.1.

С использованием «ПРОГРАММЫ 1 -алгоритм Евклида нахождения наибольшего общего делителя», подобрать два взаимно простых числа a<50, p<40 (должно быть gcd (a, p) = 1).

С использованием «ПРОГРАММЫ 2 - расширенный алгоритм Евклида для вычисления мультипликативного обратного», проверить подобранные числа - действительно ли они являются взаимно простыми? Если они взаимно простые, то имеется мультипликативное обратное.

2.1.4 Алгоритм выполнения задания 1. Вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю f(p)
(первообразных корней по модулю p)
В соответствии с подобранными взаимно простыми числами a и p необходимо вручную (или с использованием составленной студентом программы) вычислить для всех положительных целых a<p степени по модулю p. В результате получим последовательности (см. таблицу 2.1) Необходимо из них выделить последовательности с длиной f(p) = p-1. В таком случае говорят, что каждое целое число a гененрирует (своими степенями) множество всех ненулевых вычетов по модулю p. Эти соответствующие целые a и являются первообразными корнями по модулю p. Таблицу можно построить, используя возможности программы. Так, введя значение целого числа а в одноименное поле ввода, степени числа а по модулю p можно вычислить, нажав соответствующую кнопку. При этом, если при данном значении числа а число итераций на единицу меньше модуля р, то данное простое число а - первообразный корень, иначе - нет.

Ввести полученные результаты (первообразные корни) и исходные данные в программу (ПРОГРАММА 4 - вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю f(p), - первообразных корней по модулю p).

Если Ваши результаты совпадут с результатами программы, то они будут зачтены. Иначе все задание 1 необходимо будет выполнить повторно с подбором новых исходных данных. Далее приводится более подробное описание действий.

Подобранные значения исходных данных вводятся в поля ввода с соответствующими названиями «Целое число (а)» и «Взаимно простой с a модуль (p)». Найти все степени числа a по модулю p и выделить первообразные корни. Полученные ответы ввести в большое поле «Первообразные корни по модулю p». Каждое число необходимо записать на новой строке. Начинать следует с первой строки. Если на следующей строке после пустой строки введены какие-либо значения, то это будет расценено программой как ошибка вводящего. Для проверки программой расчетов студента необходимо нажать кнопку с надписью «Проверка корректности». В ходе проверки программой верности расчетов студента все верные расчеты будут выведены в большом текстовом поле, находящимся в левой части экрана. Если студент ввел хотя бы один неверный ответ, то ему придется выполнить задание с новыми входными данными.

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

Ответы и исходные данные фиксируются в соответствующем МАССИВЕ РЕЗУЛЬТАТОВ.


2.2 Задание 2. Генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети


2.2.1 Теория

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


y º gx mod p,


вычисление y при заданных g, x и p является относительно простой задачей даже при очень больших значениях x (имеются соответствующие эффективные алгоритмы). Однако если заданы y, g и p, то вычисление x (дискретное логорифмирование) является, вообще говоря, очень непростой задачей. Согласно [1], до недавного времени сложность асимптотически наиболее быстрого из известных алгоритмов вычисления дискретных логарифмов по модулю простого числа оценивалась величиной порядка

ez, где z = ((ln p)1/3ln (ln p))2/3.

Теперь рассмотрим схему Диффи-Хеллмана по обмену ключами [1, 2] (рис. 2.2, слайд 2.4).


Рис. 2.2. Обмен ключами по схеме Диффи-Хеллмана


Глобальные открытые элементы:

простое число p;

первообразный корень простого числа p Þ a, где a < p.

Вычисление ключа пользователем А:

Пользователь А выбирает случайное целое число XA < p и вычисляет YA = aXA mod p.

XA < p - секретная величина (закрытый ключ пользователя А);

YA - открытая величина (открытый ключ пользователя А).

Вычисление ключа пользователем В:

Пользователь В выбирает случайное целое число XВ < p и вычисляет YВ = a XВ mod p.

XВ < p - секретная величина (закрытый ключ пользователя В);

YВ - открытая величина (открытый ключ пользователя B).

Производится обмен открытыми ключами.

Пользователь А вычисляет общий секретный сеансовый ключ

K = (YB) XA mod p.

Пользователь B вычисляет общий секретный сеансовый ключ

K = (YA) XB mod p.

Эти последние формулы дают одинаковые результаты:

K = (YB )XA mod p = (a XВ mod p) XA mod p = (a XВ) XA mod p = a XВ XA mod p = (aXA) XB mod p = (aXA mod p) XB mod p = (YA) XB mod p.

Злоумышленнику могут быть известны величины p, a, YA и YB.

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

XВ = Inda, p (YB), иначе YВ = a XВ mod p.

Только после этого он может определить общий секретный ключ K. Вычисление XВ из последнего соотношения (дискретного логарифма) является, вообще говоря, очень непростой задачей.

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

Пример ДХ 1: Произвести обмен ключами между двумя пользователями А и В и сгенерировать общий сеансовый секретный ключ по схеме Диффи-Хеллмана.

Примечание. Описание примера дается для процесса информационного обмена между двумя абонентами. Однако интерфейс задания 2 данной лабораторной работы приводится общий (смотри далее). Это сделано для удобства выполнения лабораторной работы автономно одним студентом на одном рабочем месте.

1. Определение общих открытых элементов (в начале данный пункт задания выполняется пользователем А (условно) и полученные результаты в открытом виде передаются (условно) пользователю В). Для экономии времени одновременно пользователь В аналогичную работу выполняет с другими значениями p и a.

Это простое число p и его первообразный корень a.

Простое число выбирается из приведенной в приложении таблицы (таблица 1). Рекомендуется в качестве p выбрать двухразрядное число, равное или меньшее по значению 97. Для рассматриваемого примера, ради обеспечения простоты, мы выберем p=19.

Первообразный корень для выбранного p может быть определен двояко.

В первом случае (именно рекомендуется пойти по этому пути) первообразный корень выбирается из множества первообразных корней, полученных в результате выполнения расчетов по ПРОГРАММЕ 4 - «Вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю f(p), - первообразных корней по модулю p». При этом значение p берется из предыдущей программы, где определялись первообразные корни.

Во втором случае первообразный корень для выбранного p подбирается из условия, что целыми числами с первообразными корнями могут быть только числа 2, 4, na и 2na (где n - любое нечетное простое число). Естественно, выбранный в данном случае первообразный корень a < p.

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

Для нашего примера p=19 и a=10 (см. таблица 2.1., примера СТЕП 1).

2. Выбор секретных ключей пользователей А и В (соответственно XA и XB).

В соответствии с выбранным значением p определяются секретные ключи по условиям XA < p и XB < p. Выбираем XA=5 и XB=7.

3. Вычисление в соответствии с найденным a и выбранному p открытых ключей YA и YB (соответственно пользователями А и В) для пользователей А и В на основе XA и XB (при этом используется ниже указанная программа)

YA = aXA mod p = 105 mod 19.

YB = aXB mod p = 107 mod 19.

В действительности целые числа, используемые в приведенных соотношениях очень большие и выполнить данные расчеты не так легко. Поэтому необходимо эти расчеты производить в соответствии с ПРОГАММОЙ 3 - «Быстрое возведение в степень для ab mod n при больших значениях b» (см. лабораторную работу 1 - «Алогритм быстрого возведения в степень для ab mod n при больших значениях , примеры БВОЗ 1 и БВОЗ 2, и задание 3, не путать p с n; в алгоритме n выбранное простое число).

В нашем примере YA = aXA mod p = 105 mod 19 = 3, то есть . YA = 3.

YB = aXB mod p = 107 mod 19 = 15, то есть, YB = 15.

4. Выполнение процесса обмена открытыми ключами (условно).

Пользователь А получает в свое распоряжение открытый ключ пользователя В - YB.

Пользователь B получает в свое распоряжение открытый ключ пользователя A - YA.

5. Вычисление каждой стороной значения своего сеансового ключа (эти ключи K будут одинаковыми и используются пользователями как общий сеансовый ключ) на базе полученных открытых ключей противоположных сторон.

Пользователь A вычисляет свой сеансовый секретный ключ K ?

K = (YB)XA mod p.

Пользователь B вычисляет свой сеансовый секретный ключ K ?

K = (YA)XB mod p.

При этом обе стороны используют ПРОГАММУ 3 - «Быстрое возведение в степень для ab mod n при больших значениях b».

Для нашего примера

Пользователь A: K = (YB)XA mod p = 155mod19 = 2; K= 2.

Пользователь B: K = (YA)XB mod p = 37mod19 = 2; K= 2.

6. Посылка (условно) определенного сообщения пользователем A пользователю B.

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

Сообщение (А) -....З В Е З Д А

Шестнадцатиричный (таблица 2 приложения)

код 866 (A).…... 87 82 85 87 84 80

Двоичный код.1000 0111 1000 0010 1000 0101 1000 0111 1000 0100 1000 0000

Гамма K (A).…1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010

Å mod 2………0010 1101 0010 1000 0010 1111 0010 1101 0010 1110 0010 1010

Гамма К (B).....1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010

Двоичный код 1000 0111 1000 0010 1000 0101 1000 0111 1000 0100 1000 0000

Шестнадцатиричный

код 866 (B)…..……87 82 85 87 84 80

Сообщение (B) -.... З В Е З Д А

7. С целью проверки совместной работы пользователей необходимо расшифрованное пользователем В сообщение переслать (условно) в открытом виде пользователю А.

. Необходимо такую же работу, одновременно с пользователем А, произвести и пользователю В (условно) согласно п. 1 для передачи другого слова пользователем В пользователю А.


2.2.2 Инструкция по выполнению задания 2

Проанализировать процесс выполнения примера ДХ 1 по приведенному алгоритму. Задание 2 выполняется двумя пользователями взаимосвязанно (условно их, как и в примере, назовем соответственно, пользователями A и B). Задание выполняется поэтапно так, как показано в примере 2.

. Выбор из таблицы 1 приложения простого числа p. С использованием ПРОГРАММЫ 4 - «Вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю f(p), - первообразных корней по модулю p» определить соответствующий конкретный первообразный корень a (где a<p).

. В соответствии с выбранным значением p определить секретные ключи по условиям XA < p и X B< p.

. Вычислить в соответствии с найденным a и конкретным p открытые ключи YA и YB для пользователей А и В на основе их секретных ключей XA и XB. При этом используется ПРОГАММА 3 - «Быстрое возведение в степень для ab mod n при больших значениях b»..

. Выполнение процесса обмена открытыми ключами пользователей по открытой сети (условно).

. Вычисление каждой стороной значения своего секретного сеансового ключа (эти ключи K будут одинаковыми и используются пользователями как общий сеансовый ключ) на базе полученных открытых ключей противоположных сторон. При этом опять используется ПРОГАММА 3 - «Быстрое возведение в степень для ab mod n при больших значениях b».

. Посылка (условно) определенного короткого - однословного сообщения пользователем A пользователю B и, наоборот. При этом необходимо пользоваться соответствующей кодовой таблицей (например, таблица 2 приложения или таблица, применяемая в соответствующем Windows-е).

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


2.2.3 Общее положение по выполнению задания 2 - генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети

Как видно, в данной работе значения первообразного корня (а), простого числа (р) и секретных ключей (XА и XВ) соответствующим образом выбираются и вводятся в соответствующие поля ввода окна задания 2. Все, что требуется от студента - рассчитать открытые ключи(YА и YВ) и общий секретный сеансовый ключ К, значения которых затем нужно ввести в соответствующие поля. Для проверки программой расчетов студента необходимо нажать кнопку с надписью «Контроль расчета К». В ходе проверки все верные расчеты будут выведены в большом текстовом поле, которое находится в нижней части экрана.

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

В случае правильного решения студентом поставленной задачи информация о верности решения будет выведена в большом текстовом поле. В зависимости от того, желает ли студент зашифровывать открытое слово (открытый текст) или расшифровывать зашифрованный текст, он заполняет поля ввода "Слово для зашифрования" или "Зашифрованное слово (текст) для расшифровывания". Далее необходимо нажать кнопку "зашифрование/расшифрование", после чего в текстовом поле "Ход расчетов программы" появятся все действия программы по зашифрованию/расшифрованию. Далее студент может сохранить все расчеты в специиальном файле, нажав кнопку "Сохранить в файле". Студенты могут обмениваться кодами посредством, например, электронной почты, и расшифровывать сообщения друг друга, зная общий секретный сеансовый ключ.

Необходимо все исходные данные и результаты зашифрования и расшифрования сохранить в файле РЕЗУЛЬТАТОВ.


ГЛОССАРИЙ


1.Алгоритм Диффи-Хеллмана. Алгоритм Диффи-Хеллмана основывается на трудностях вычисления дискретных логарифмов. Злоумышленнику могут быть известны величины Q (простое число), a (первообразный корень простого числа Q), YA и YB (открытые ключи, соответственно абонентов А и В). Злоумышленнику для определения, например, секретного ключа пользователя В необходимо вычислить XВ = Inda, Q (YB), иначе YВ = a mod Q.

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

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

4.Индекс b по основанию a, рассматриваемому по модулю p (иначе дискретный логарифм). Ind a,p (b) или показатель степени i, при котором b = aimod p, где 0 £ i £ (p-1).


3. Лабораторная работа 3. КриптографиЯ с открытым ключом.
Метод зашифрования с открытым ключом RSA

В этой лабораторной работе определяются параметры преобразования, необходимые для выполнения алгоритма RSA (выбирается соответствующим образом открытый ключ e, вычисляется соответствующий закрытый ключ d как мультипликативное обратное к e). Далее с использованием этих параметров производятся зашифрование открытого текста (конкретного двухразрядного десятичного числа) и расшифрование этого зашифрованного текста.

Работа состоит из трех заданий.

Задание 1. RSA-0 - подготовка к выполнению алгоритма зашифрования открытого сообщения открытым ключом RSA-1.

Задание 2. RSA-1 - выполнение алгоритма зашифрования открытого сообщения открытым ключом RSA-1.

Задание 3. RSA-2 - выполнение алгоритма расшифрования зашифрованного сообщения секретным ключом RSA-1.


3.1 Теория, криптография с открытым ключом. Метод зашифрования с открытым ключом RSA


Алгоритмы шифрования с открытым ключом зависят от двух ключей: одного ключа для зашифрования и другого ключа, связанного с первым, для расшифрования (слайд 3.2). С точки зрения вычислений, нереально определить ключ расшифрования, зная только используемый крипто-графический алгоритм и ключ зашифрования. В некоторых алгоритмах любой из этих ключей может применяться для зашифрования, а другой - для расшифрования.

Криптографические системы с открытым ключом зависят от некоторой обратимой математической функции со специальными свойствами. Сложность вычисления такого рода функций может зависеть не линейно от числа битов в ключе, а расти более быстро. Поэтому длина ключа должна быть достаточно большой. Однако чем длиннее ключи, тем больше времени требуется для выполнения процессов зашифрования/расшифрования. Поэтому алгоритмы криптографии с открытым ключом в настоящее время, в основном, применяются в управлении ключами и приложениями цифровой подписи. Однако схема Райвеста-Шамира-Адлемана (RSA) стала единственной получившей широкое признание и практически применяемой схемой шифрования с открытым ключом [1]. Эта схема представляет собой блочный шифр, в котором и открытый текст, и шифрованный текст представляются целыми числами из диапазона от 0 до (n-1) для некоторого n.

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

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

Обобщенная блок-схема генерации ключей, необходимых для алгоритма RSA приводится на рис. 3.1 (слайд 3.3).


Рис. 3.1. Генерация ключей для RSA

На рис. 3.2 (слайд 3.4) приводится блок-схема алгоритмов зашифрования и расшифрования для RSA.


Рис. 3.2. Блок-схема алгоритмов зашифровки и расшифровки для RSA


3.2 Алгоритм RSA


Далее приводятся два примера, поясняющие работу алгоритма RSA.

Пример RSA-0. Выбор целого e, взаимно простого с f(n) и меньшего, чем f(n). А также определение такого d, что de = 1 mod f(n) и d < f(n).

Это подготовительный этап для выполнения алгоритма RSA.

Из таблицы 1 приложения выбираем два простых числа p = 7 и q = 17.

Вычисляем n = p ´ q = 7 ´ 17 = 119.

Вычисляем f(n) = (p-1) ´ (q-1) = 6 ´16 = 96.

Выбираем e по условию, что gcd (e, f(n)) = 1 и 1<e<f(n) Для этого будем пользоваться расширенным алгоритмом Евклида для нахождения наибольшего общего делителя двух чисел, который при определении и уточнении, что таким делителем является 1, выдает и мультипликативное обратное для e по модулю f(n).

gcd (d, f) = gcd (e =5, f(n) = 96) = 1.

Выполняем алгоритм:

X1 = 1, X2 = 0, X3 = 96.

Y1 = 0, Y2 = 1, Y3 = 5.

Y3 ¹ 0,

Y3 ¹ 1.

Q = ëX3/Y3û = ë96/5û = 19.

T1 = X1 - Q ´ Y1 = 1 - 19 ´ 0 = 1,

T2 = X2 - Q ´ Y2 = 0 - 19 ´ 1 = -19,

T3 = X3 - Q ´ Y3 = 96 - 19 ´ 5 = 1.

X1 = Y1 = 0,

X2 = Y2 = 1,

X3 = Y3 = 5.

Y1 = T1 = 1,

Y2 = T2 = -19,

Y3 = T3 = 1.

Соотношения:

f ´ T1 + d ´ T2 = 96 ´ 1 + 5 ´ (-19) = 1 = T3,´ X1 + d ´ X2 = 96 ´ 0 + 5 ´ 1 = 5 = X3,´ Y1 + d ´ Y2 = 96 ´ 1 + 5 ´ (-19) = 1 = Y3.

Так как Y3 = 1, то Y3 gcd (5, 96) = 1 наибольший общий делитель.

Тогда Y2 = d-1 mod 96 = -19. Так как Y2 отрицательное целое, то мультипликативное обратное будет 96-19 = 77.

Таким образом, для нашего примера e = 5 и d = 77.

Пример RSA-1: Вычислить ab mod n (см. раздел 1.4. - «Алгоритм быстрого возведения в степень для ab mod n при больших значениях b», рис. 1.5. и слайд 7), где a = M = 19, b = e = 5 (открытый ключ) и n = (p ´ q) = 119, С - зашифрованный текст.

Иначе

195 mod 119 = C ?

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.

Ответ: C = 195 mod 119 = 66.

Далее рассмотрим пример для обратного преобразования

Пример RSA-2: Вычислить ab mod n, где a = C = 66, b = d = 77 (закрытый ключ) и n = 119.

Иначе

M = 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 - (43 ´119) = 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, то получен следующий ответ.

Ответ: M = 6677 mod 119 = 19.


3.3 Общее положение по выполнению лабораторной работы. Метод зашифрования RSA


Необходимо выбрать из таблицы 1 приложения новые значения простых чисел p и q, и выполнить все примеры аналогично RSA-0, RSA-1 и RSA-2.

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


3.3.1 Задание 1 - RSA-0 - подготовка для выполнения алгоритма зашифрования открытого сообщения открытым ключом RSA-1

1. Выбираем из таблицы 1 приложения два взаимно простых числа p и q. 2. С использованием вкладки «Лабораторная работа 1, задание 1» испытываем выбранные числа на взаимную простату. Вводим эти числа в поля «Число 1 (d)» и «Число 2 (f)». В качестве ответа должны получить значение наибольшего общего делителя 1. 3. Вводим выбранные числа в поля «Простое число 1 (p)» и «Простое число 2 (q), взаимно простое с числом p» окна RSA-0 данной лабораторной работы. 4. Рассчитываем значение n = p ´ q. Нажав кнопку «Расчет f(n)» вычислим f(n) = (p-1) ´ (q-1).

. Для подбора соответствующего значения открытого ключа e (взаимно простого с f(n)) используем вкладку «Лабораторная работа 1, задание 1». В окне этой вкладки в поле «Число 1 (d)» вводим выбранное значение e (где 1<e<f(n)), а в поле «Число 2 (f)» вводим значение f(n). Так как эти поля уже доступны студенту, то подбор производится относительно легко (подбирается значение e). Подобранное значение e вводится в поле «Значение открытого ключа e, взаимно простое с f(n)» окна RSA-0 данной лабораторной работы.

. Подбираем значение закрытого ключа d, мультипликативного обратного для e по модулю f(n) в поле «Значение закрытого ключа d, мультипликативного обратного для e по модулю f(n)» в поле RSA-0 данной лабораторной работы. При заполненных полях этого окна в большом среднем поле отражается правильный процесс вычисления и полученный верный ответ (используется кнопка «Проверка корректности»). Правильный ответ получается в результате коррекции ответа (если это необходимо) в процессе подбора. Этим подготовительная работа завершается.


3.3.2 Задание 2 - RSA-1 - выполнение алгоритма зашифрования открытого сообщения открытым ключом RSA-1

По результатам RSA-0 заполняются поля «Открытое сообщение (a)», «Открытый ключ (b = e)», «Значение n (n = p ´ q)».

Вычисляется ab mod n и в результате получается соответствующий зашифрованный текст. При этом используется вкладка «Задание 3 лабораторной работы 1». Правильный процесс расчетов отображается в большом поле окна задания RSA-1 данной лабораторной работы.


3.3.3 Задание 3 - RSA-2 - выполнение алгоритма расшифрования зашифрованного сообщения секретным ключом RSA-1

Обратный процесс можно проследить в окне RSA-2 данной лабораторной работы. Этот процесс выполняется аналогично процессу RSA-1. Соответствующие ответы и исходные данные фиксируются в МАССИВЕ РЕЗУЛЬТАТОВ.


3.4. Общий алгоритм выполнения лабораторной работы 3
по криптографическим системам с открытым ключом

Рис. 3.3. Общий алгоритм выполнения лабораторной работы

ГЛОССАРИЙ


1.Алгоритм RSA. Алгоритм RSA основан на выражениях со степенями. Эта система основана на трудностях разложения очень больших целых чисел по степеням простых чисел.

2.Канал связи. Естественный или искусственный материальный объект (среда), обеспечивающий передачу сигнала от передатчика к приемнику. Основными каналами распространения информации в настоящее время являются, в первую очередь, Интернет, а также другие специализированные системы государственного и межгосударственного уровня.
В перспективе на эту роль претендуют цифровые информационно-телекоммуникационные сети интегрального обслуживания.
3.Ключ. Это конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования данных, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразований; последовательность символов, управляющая операциями шифрования и дешифрования.


Список утверждений


1. Алгоритмы шифрования с открытым ключом зависят от двух ключей: одного ключа для зашифрования и другого ключа, связанного с первым, для расшифрования. С точки зрения вычислений, нереально определить ключ расшифрования, зная только используемый криптографический алгоритм и ключ зашифрования.

. c, отличное от нуля, делит a, если a = m ´ c для некоторого m, где c, a и m являются целыми числами. c делит a, если деление выполняется без остатка. Это пишется так: c|a. c называют делителем a.

. Целое число p>1 называется простым, если его делителями являются только числа ± 1 и ± p.

. Положительное целое число c является наибольшим общим делителем чисел a и b (НОД, запись gcd (a, b)), если: c является делителем a и b; любой делитель a и b является делителем c. gcd (a, b) = max [k таких, что k|a и k|b].

. Числа a и b являются взаимно простыми, если gcd (a, b) = 1.

. Если a является целым, а z - положительным целым, то a mod z определяется как остаток от деления a на z.

. Два целых числа a и b являются сравнимыми по модулю n, если (a mod n) = (b mod n). Это записывается так: a º b mod n.

. Если gcd (d, f) = 1, то d имеет мультипликативное обратное по модулю f. То есть, для положительного целого числа d< f существует такое d -1< f, что d d -1= 1 mod f.

9. [(a1 mod n) ´ (a2 mod n)] mod n = (a1 ´ a2) mod n.

10. Число положительных целых значений, которые меньше n и являются взаимно простыми с n, обозначается через f(n) и называется функцией Эйлера. Для простого числа p это будет f(p) = = p - 1.

. Теорема Эйлера утверждает, что для любых взаимно простых чисел a и n

af(n) º 1 mod n.

12. Если a и n являются взаимно простыми, то существует, по крайней мере, одно целое число m, удовлетворяющее соотношению am º 1 mod n, где m = f(n). Для наименьшего из положительных m, при которых выполняется указанное условие, используются названия или порядок числа a по модулю n, или показатель, которому принадлежит a по модулю n, или длина периода последовательности, генерируемой степенями a.

13. Числа, принадлежащие показателю f(n), называются первообразными корнями по модулю n.


Заключение


Из всего изложенного следует, что надежная криптографическая система должна удовлетворять таким требованиям:

процедуры зашифровывания и расшифровывания должны быть "прозрачны" для пользователя;

дешифрование закрытой информации должно быть максимально затруднено;

содержание передаваемой информации не должно сказываться на эффективности криптографического алгоритма;

надежность криптозащиты не должна зависеть от содержания в секрете самого алгоритма шифрования (примерами этого являются как алгоритм DES, так и алгоритм ГОСТ 28147-89).


Литература


1. Аскеров Т.М. Защита информации и информационная безопасность: Учебное пособие / Под общей редакцией К.И. Курбакова. - М.: Рос. экон. акад., 2001. 387 с.

. Diffie, W., and Hellman, M. «Multiuser CryptographicTechniques». Proceedingsof the AFIPS National Computer Conference, June 1976.

3. Партыка Т.Л., Попов И.И. Информационная безопасность: Учебное пособие для студентов учреждений среднего профессионального образования. - М.: ФОРУМ: ИНФРА-М, 2002. - 368 с.: ил. - (Серия «Профессиональное образование»).

. Столингс Вильям. Криптография и защита сетей / Пер. с анг. - 2-е изд. - М.: Издательский дом «Вильямс», 2001. - 672 с.: ил. - Парал. Тит. анг.

. Толковый словарь по вычислительной технике / Пер. с англ. - М.: Издательский отдел «Русская Редакция» ТОО «Channel Trading Ltd.», 1995. - 496 с.: ил.


ПРИЛОЖЕНИЯ


Таблица 1 Простые числа, не превышающие 1000 [1]


Таблица 2 Коды символов по Windows 1251 и 866 [5]


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

Дешифрование - процесс преобразования закрытых данных в открытые при неизвестных ключе и алгоритме.

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

Криптостойкость - характеристика шифра, определяющая его стойкость к дешифрованию.

Расшифровывание - преобразование по криптографическому алгоритму зашифрованного текста в открытый с использованием известного криптографического ключа.

Шифрование - процесс зашифровывания или расшифровывания.

криптографическая атака (cryptoanalitic attack) - попытка криптоаналитика вызвать отклонения от нормального проведения процесса конфиденциального обмена информацией. Соответственно взлом или вскрытие, дешифрование шифра или шифросистемы - это успешное применение криптографической атаки;

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

дешифрование (deciphering) и расшифрование (decryption) - соответственно методы извлечения информации без знания криптографического ключа и со знанием оного. Термин "дешифрование" обычно применяют по отношению к процессу криптоанализа шифротекста (криптоанализ сам по себе, вообще говоря, может заключаться и в анализе шифросистемы, а не только зашифрованного ею открытого сообщения);

криптографический ключ (cryptographic key, cryptokey, иногда просто key) - в случае классических криптосистем секретная компонента шифра. Должен быть известен только законным пользователям процесса обмена информации;

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

аутентичность данных и систем (authenticity of information) - для данных аутентичность можно определить как факт подтверждения подлинности информации, содержащейся в этих данных, а для систем - способность обеспечивать процедуру соответствующей проверки - аутентификации данных;

аутентификация (authentication) - процедура проверки подлинности данных, то есть того, что эти данные были созданы легитимными (законными) участниками процесса обмена информации;

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

гаммирование (gamma xoring) - процесс "наложения" гамма-последовательности на открытые данные. Обычно это суммирование в каком-либо конечном поле (например, в поле GF(2) (см. [4, 6 и 9]) такое суммирование принимает вид обычного "исключающего ИЛИ" суммирования);

имитозащита - это защита данных в системах их передачи и хранения от навязывания ложной информации. Имитозащита достигается обычно за счет включения в пакет передаваемых данных имитовставки;

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

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

криптографическая стойкость, криптостойкость (cryptographic strength) - устойчивость шифросистемы по отношению ко всем известным видам криптоанализа;

принцип Керкхоффа (Kerchkoff) - принцип изобретения и распространения криптографических алгоритмов, в соответствии с которым в секрете держится только определенный набор параметров шифра (и в обязательном порядке криптографический ключ), а все остальное может быть открытым без снижения криптостойкости алгоритма. Этот принцип был впервые сформулирован в работе голландского криптографа Керкхоффа "Военная криптография" вместе с дюжиной других, не менее известных (например, о том, что шифр должен быть удобным в эксплуатации, а также о том, что шифр должен быть легко запоминаемым);

развертывание или разворачивание ключа (key shedule) - процедура вычисления последовательности подключей шифра из основного ключа шифрования;

раунд или цикл шифрования (round) - один комплексный шаг алгоритма, в процессе которого преобразовываются данные;

подключ шифрования (round key, subkey) - криптографический ключ, вычисляемый и используемый только на этапе шифрования из основного ключа шифрования. Обычно применяется в качестве входа функций усложнения на различных раундах шифрования;

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



ОГЛАВЛЕНИЕ ОБЩИЕ ПОЛОЖЕНИЯ ОСОБЕННОСТИ ИЗУЧЕНИЯ И ВЫПОЛНЕНИЯ ЦИКЛА ЛАБОРАТОРНЫХ РАБОТ . ЛАБОРАТОРНАЯ РАБОТА 1. КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ. ТЕОР

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ