Алгоритмические языки и программирование

Федеральное агентство по образованию РФ КГТУ                                                       Кафедра Вычислительной Техники                 Пояснительная записка к курсовой работе по алгоритмическим языкам и программированию.                                                                    Выполнил:                                                                      студент гр. Вт 24-7                                                           Томченко А. Г.                                                   Проверил:                                                         Шитов Ю. А.           Красноярск, 2005г.

 

Содержание:

1. Задание . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Аннотация. . . . . . . . . . . .. . . . . . . . . . . . . . . 4
3. Основные понятия. . . . . . . . . . . . . . . . . . . . . . . 5
4. Математические основы. . . . . . . . . . . . . . . . . . . . .8
5. Алгоритм RSA . . . . . . . . . . . . . . . . . . . . . . . .10
6. Словесная схема алгоритма . . . . . . . . . . . . . . . . . .12
7. Список используемых идентификаторов. . . . .  . . . . . . . .13
8. Инструкция к программе . . . . . . . . . . . . . . . . . . . 15

9. Заключение . . . . . . . . . . . . . . . . . . . . . . .. . .   16

10. Список используемой литературы. . . . . . . . . . . . . . .    17

11.Приложение . . . . . . . . . . . . . . . . . . . . . . . .. .  18

    а) Текст программы . . . . . . . . . . . . . . . . . . . . .    18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

	1. Задание:   Составить программу  на языке программирования с++, реализующую шифрование и дешифрование по алгоритму шифрования RSA. Использовать графический  режим работы  видеотерминала.
Изм	Лист	№ докум.	Подп	Дата
Разраб.		Томченко  А.Г.			Реализация  алгоритма RSA	Лит.			Лист	Листов
Пров.		Шитов Ю. А.							3
						КГТУ ВТ 24-7
Н. контр.
Утв.

 

2. Аннотация:

 

Программа написана в среде Borland C++ 3.11.

Реализовано использование графического меню.

Данная программа реализует  шифрование и дешифрование информации по алгоритму RSA.

 

3. Основные понятия:

 

Терминология.

 

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

 

Обозначим открытый текст  сообщения буквой M, а просто открытый текст – буквой P. Это может быть последовательность (поток) битов, текстовый файл, точечный рисунок, оцифрованный звук, цифровое изображение и т.д. Для компьютеров М – это просто двоичные данные. Открытый текст предназначен для хранения или передачи. В любом случае, М – это сообщение которое необходимо зашифровать.

Обозначим шифртекст  буквой С. Это тоже двоичные данные, иногда того же размера, что и М, а иногда большего. Функция зашифрования Е, оперируя с М, создает С. Или в математической форме: Е(М)=С.

В обратном процессе функция расшифрования D, оперируя с С, восстанавливаем М: D(C)=M.

Поскольку смысл зашифрования и последующего расшифрования сообщения заключается в восстановлении исходного открытого текста, справедливо следующее равенство: D(E(M))=M.

 

Алгоритмы и ключи.

 

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

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

Современная криптография решает многие проблемы с помощью ключа, обозначаемого буковой К. Такой ключ может быть любым значением,     выбранным из большого множества. Множество возможных ключей называют пространством ключей. Ключ используется в обеих операциях – как зашифрования, так и расшифрования. Таким образом функции зашифрования и расшифрования принимают следующий вид: E_K(M)=C; D_K(C)=M; D_K(E_K(M))=M.

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

 

(Зашифрование и Расшифрование с помощью ключа)

 

 

(Зашифрование  и Расшифрование с помощью  2-х различных ключей)

 

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

 

Типы алгоритмов.

 

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

 

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

 

Алгоритмы с  открытым ключом (так называемые также ассиметричными алгоритмами) устроены таким образом, что ключ, используемый для зашифрования отличается от ключа расшифрования. Более того, ключ расшифрования не может быть (по крайней мере, в течение разумного периода) вычислен из ключа зашифрования. Такие алгоритмы называют алгоритмами с открытым ключом, поскольку ключ для зашифрования может быть открытым: кто угодно может воспользоваться этим ключом для зашифрования сообщения, однако расшифровать сообщение может только конкретный человек, знающий ключ расшифрования. В таких системах ключ зашифрования обычно называют открытым ключом (Public key), а ключ расшифрования – закрытым ключом (Private key). Закрытый ключ нередко называют секретным ключом, однако во избежание путаницы с симметричными алгоритмами, здесь этот термин не используется.

Зашифрование с открытым ключом К обозначается следующим образом: Е_К(М)=С. Хотя открытый и закрытый ключ различны, расшифрование с соответствующим закрытым ключом обозначается так: D_K(C)=М.

 

 

 

 

Криптоанализ.

 

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

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

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

 

Обеспечивать безопасность зашифрованных данных должна надежность ключа (по Керкхоффсу).

 

Стойкость алгоритмов.

 

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

 

4. Математические основы:

 

Модулярная арифметика.

 

Рассмотрим переменные a,b и n; для которых , если а =+kn при некотором целом k. Если а не отрицательно, а b находиться между 0 и n, можно рассматривать b как остаток от деления a на n. Иногда b называют вычетом по модулю n, а иногда называют сравнимым с b по модулю n. Это одно и тоже.

Множество целых чисел  от 0 до n-1 образует так называемую полную систему вычетов по модулю n. Это означает, что для любого целого числа а, его вычет по модулю n равен некоторому числу от 0 до n-1.

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

 

Простые числа.

 

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

 

Наибольший общий  делитель.

 

Два числа называют взаимно простыми, если у них нет общих множителей кроме 1. Иными словами, если наибольший общий делитель чисел а и n равен 1, эти числа называются взаимно простыми: НОД(а,n)=1.

Один из способов вычисления наибольшего общего делителя двух чисел – использование алгоритма Евклида. Евклид описал этот алгоритм в своей книге «Элементы», датированной 300 годом до н.э. Однако алгоритм создан не Евклидом. Это самый древний нетривиальный алгоритм.

 

Обратные значения по модулю.

 

Общая задача состоит  в определении такого значения х, что:

1=(а*х) mod n

В общем случае, уравнение  имеет единственное решение, если a и n взаимно просты. Если они не являются взаимно простыми числами, то решений не имеет. Если n – простое число, то любое число от 1 до n-1 взаимно просто с n и имеет только одно обратное значение по модулю n.

Обратное значение по модулю n можно вычислить с помощью расширенного алгоритма Евклида.

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

Малая теорема Ферма.

 

Если m – простое число, и a не кратно m, то малая теорема Ферма утверждает, что:  .

(Пьер де Ферма, французский  математик, 1601-1665).

 

В общем случае при вычислении обратных значений алгоритм Евклида исполняется  быстрее, чем, например, обобщение Эйлера, особенно для чисел длиной порядка 500 бит. Если НОД(a,n) 1, не все потеряно. В этом случае (a*x) mod n= b может иметь или несколько решений, или ни одного.

 

 

5. Алгоритм RSA:

 

В 1979 году был создан один из первых алгоритмов с открытым ключом, который можно использовать и для шифрования и для создания цифровых подписей – алгоритм RSA. Из всех предложенных за эти годы алгоритмов с открытым ключом RSA проще всего понять и реализовать. «…RSA является самым популярным алгоритмом…» [7]. Названный в честь трех изобретателей – Рона Ривеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Адлемана (Leonard Adleman), этот  алгоритм многие годы противостоит многочисленным попыткам криптоаналитического вскрытия. «…Хотя криптоанализ ни доказал, ни опроверг безопасность алгоритма RSA, проведенная за эти годы работа, по сути, обосновывает степень доверия к алгоритму…»[7].