Файл: Методы кодирования данных (позволяющие выполнять шифрование).pdf

ВВЕДЕНИЕ

Информация (данные) в общем смысле – это сведения, представленные в различной форме, которая может быть распознана человеком и/или специальными устройствами. С течением времени понятие информации, используемое в повседневной речи, претерпело значительные изменения. Главным образом это произошло из-за распространения технологий, связанных с коммуникацией. В середине XX в. появилась информатика – наука, отделившаяся от кибернетики, занимающаяся исследованиями способов получения, хранения, передачи и обработки информации. В промышленно развитых западных обществах информация стала чем-то необходимым, главным и незаменимым компонентом общества. Таким образом, актуальность использования методов передачи и обработки информации (данных) возрастает.

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

1. Представление данных произвольной структуры (числа, текст, графика) в памяти компьютера;
2. Обеспечение помехоустойчивости при передаче данных по каналам связи;
3. Шифрование данных;
4. Сжатие информации.

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

Файл данных – это компьютерный файл (именованная область внешней памяти, выделенная для хранения), в котором хранятся данные, используемые компьютерным приложением или системой, включая входные и выходные данные [3.]. Файл данных обычно не содержит инструкций или кода для выполнения (то есть компьютерной программы). Большинство компьютерных программ работают с файлами данных.

Файлы данных могут храниться двумя способами:

1. Текстовые файлы;
2. Бинарные файлы.

Текстовые файлы (часто называемые ASCII-файлами) хранят информацию в символах кодировки ASCII. Текстовый файл содержит удобочитаемые символы. Пользователь может читать содержимое текстового файла или редактировать его с помощью текстового редактора. В текстовых файлах каждая строка текста заканчивается (разделяется) специальным символов, известным от EOL (от англ. End Of Line – конец строки). Примером текстового файла может служить текстовый документ – файл с расширением .txt.

Бинарные (двоичные) файлы содержат информацию в том же формате, в котором она хранится в памяти, то есть в двоичной форме. В двоичном файле нет разделителей строк и символов перевода. Это позволяет проще и быстрее осуществлять операции чтения и записи, чем при работе с текстовыми файлами [3.]. До тех пор, пока файл не нужно переносить в другую операционную систему либо читать при помощи текстового редактора, двоичные файлы являются лучшим способом хранения информации. Примером бинарного файла может служить изображение в формате JPEG.

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

Для достижения цели в курсовой работе были поставлены следующие задачи:

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

В процессе выполнения работы все поставленные задачи были успешно выполнены.

Методы шифрования данных

Теоретические основы шифрования данных

Актуальность использования криптографических методов обусловлена быстрым развитием сетевых технологий и мощностей вычислительных устройств, а также широким использованием компьютерных сетей, в том числе и глобальной сети Интернет, по которым передаются большие объемы информации государственного, военного, коммерческого и частного характера, не допускающего возможность доступа к ней посторонних лиц. Потребность в криптографии возникла с появлением письменности. Так, например, еще до нашей эры встречались первые криптосистемы – в секретной переписке римского полководца Цезаря был использован шифр подстановки, впоследствии названный его именем. Тем не менее, до появления алгоритма RSA (аббревиатура от фамилий его создателей – Rivest, Shamir и Adleman) все существующие криптосистемы основывались на том факте, что как передающая сообщение сторона, так и принимающая его должны разбираться в принципах работы самого метода шифрования и обладать знанием о единственном ключе для декодирования шифра.

Алгоритм RSA, разработанный в 1977 году Ривестом, Шамиром и Адлеманом, предложил новую модель шифрования – шифрование с открытым ключом. Создатели алгоритма исходили из предпосылки о том, что отправитель сообщения не обязательно должен уметь его расшифровывать. В этой парадигме для шифрования используется так называемый открытый ключ, который может быть опубликован для всех, кто хочет получить доступ к результату шифрования. Для дешифрования используется закрытый ключ, доступный только получателю. Обеспечение конфиденциальности в криптосистеме с открытым ключом состоит в том, что чрезвычайно трудно получить ключ дешифрования из общедоступного ключа шифрования [6.]. Алгоритм работает, используя понятия теории чисел, в том числе теорему Ферма.

Метод Диффи-Хеллмана

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

Впервые эта проблема была решена Уитфилдом Диффи, работающим в сотрудничестве с Мартином Хеллманом [6.]. Шифр, предложенный Диффи, содержал асимметричный ключ (пару «открытый ключ, закрытый ключ»). В других криптосистемах дешифрование было просто противоположным шифрованию; эти системы использовали симметричный ключ, потому что дешифрование и шифрование симметричны. Несмотря на то, что Диффи разработал общую концепцию асимметричного шифра, у него фактически не было определенной односторонней функции, которая отвечала бы необходимым требованиям. Тем не менее, его статья, опубликованная в 1975 году, вызвала интерес среди других математиков и ученых. Диффи и Хеллман, однако, не смогли продвинуться дальше в разработке нового шифра. Это открытие было сделано группой других исследователей: Ривестом, Шамиром и Адлеманом в 1977-м году [6.].

Пример алгоритма Диффи-Хеллмана.

1 шаг: Алиса и Боб договариваются о значениях для некоторой математической односторонней функции. Значения не являются секретными. Допустим, что эти значения 9 и 14. Функция будет иметь вид 9^х (mod 14)

2 шаг: Алиса и Боб выбирают свои случайные числа, которые хранят в секрете. Пусть Алиса выбрала число 5, а Боб – 7. Эти числа обозначаются А и В соответственно.

3 шаг: Алиса и Боб подставляют свои секретные числа в функцию и вычисляют значение. 9⁵ (mod 14) = 59 049 mod 14 = 11. 9⁷ (mod 14) = 4782969 (mod 14) = 9. Эти числа обозначаются С и Е соответственно.

4 шаг: Алиса и Боб обмениваются вычисленными значениями и вычисляют значение функции со своим и полученным числом в качестве аргумента, т.е. Алиса вычисляет Е^А (mod 14), Боб, соответственно, вычисляет С^В (mod 14). 9⁵ (mod 14) = 59 049 mod 14 = 11. 11⁷ (mod 14) = 19487171 mod 14 = 11. Полученное в результате всех операций число 11 будет секретным ключом для шифрования передаваемых данных.

При работе алгоритма Диффи-Хеллмана [5.] каждая сторона:

1. Генерирует случайное натуральное число a – закрытый ключ, затем совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где p является случайным простым числом, g является первообразным корнем по модулю p
2. Вычисляет открытый ключ A, используя преобразование над закрытым ключом по формуле (1):

, (1)

1. Обменивается открытыми ключами с удалённой стороной и вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a, формула (2):

(2)

К получается равным с обоих сторон, потому что

(3)

Алгоритм [5.] проиллюстрирован на рисунке 1.

Рисунок 1. Алгоритм Диффи-Хеллмана

Алгоритм RSA

Алгоритм RSA получения открытого и закрытого ключей выглядит следующим образом [5.]:

1. Выбрать два простых числа и .
2. Найти их произведение , которое называется модулем.
3. Найти значение функции Эйлера от числа : .
4. Выбрать целое число : , взаимно простое со значением функции .
5. Найти линейное представление наибольшего общего делителя этих двух чисел: и вычислить число (например, при помощи расширенного алгоритма Евклида).

Пара чисел публикуется в качестве открытого ключа RSA.

Пара чисел играет роль закрытого ключа RSA и не публикуется. Делители и могут быть как уничтожены, так и сохранены вместе с секретным ключом.

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

Алгоритм шифрования RSA [3.]:

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

Алгоритм дешифрования [5.]:

1. Принять зашифрованное сообщение .
2. Применить закрытый ключ для расшифровки сообщения .

Одним из наиболее известных протоколов аутентификации является протокол на основе алгоритма RSA, который состоит из этапов генерации (получения открытого и закрытого ключей) и аутентификации:

• • • 1. Принимающая сторона выбирает случайное число , вычисляет и посылает отправляющей стороне;
      2. Отправляющая сторона вычисляет и отправляет принимающей стороне;
      3. Принимающая сторона проверяет соотношение : если оно истинно, то сторона принимает доказательство.