Разработка программы шифрования с помощью шифра Виженера
Правительство Российской Федерации
Пермский
филиал федерального государственного автономного образовательного учреждения
высшего профессионального образования Национальный исследовательский
университет ''Высшая школа экономики''
Кафедра
информационных технологий в бизнесе
информация
шифрование виженер кодирование
Курсовая
работа
Разработка
программы шифрования с помощью шифра Виженера
Работу
выполнила
студентка
группы БИ-12-1
курса
факультета бизнес-информатики
Ерохина Дарья
Григорьевна
Научный руководитель:
к.ф.-м.н.,
доцент кафедры информационных технологий в бизнесе
Морозенко
Владимир Викторович
Пермь 2013
Оглавление
Введение
Глава 1.
Шифрование при помощи шифра Виженера
1.1 История
создания шифра
1.2 Процесс
шифрования (алгоритм)
Глава 2. Разработка
программы для реализации поставленной задачи
.1 Результат
работы программы с точки зрения пользователя
2.2
Разработка приложения
Глава 3.
Тестирование программы
.1 Тест №1
3.2 Тест №2
3.3 Тест №3
3.4 Тест №4
Заключение
Библиографический
список
Приложение
№1. Таблица. Пример квадрата Виженера
Приложение №
2. Квадрат Виженера в программе
Приложение №
3. Блок - схема программы
Приложение №
4. Исходный код программы
Приложение №
5. Результат тестирования № 3 - Шаг 1
Приложение №
6. Результат тестирования № 3 - Шаг 2
Приложение №
7. Результат тестирования № 3 - Шаг 3
Приложение №
8. Результат тестирования № 3 - Шаг 4
Приложение №
9. Результат тестирования № 3 - Шаг 5
Приложение №
10. Результат тестирования № 4 - Шаг 1
Приложение №
11. Результат тестирования № 4 - Шаг 2
Приложение №
12. Результат тестирования № 4 - Шаг 3
Приложение №
13. Результат тестирования № 4 - Шаг 4
Приложение №
14. Результат тестирования № 4 - Шаг 5
Приложение №
15. Результат тестирования № 4 - Шаг 6
Приложение №
16. Результат тестирования № 4 - Шаг 7
Приложение №
17. Результат тестирования № 4 - Шаг 8
Приложение №
18. Результат тестирования № 4 - Шаг 9
Приложение №
19. Результат тестирования № 4 - Шаг 10
Приложение №
20. Результат тестирования № 4 - Шаг 11
Приложение №
21. Адаптация программы под латинский язык
Приложение №
22. Тесты программы (адаптации) под латинский язык
Приложение №
23. Диаграмма 1
Введение
В современном конкурентном мире наблюдается тенденция постоянного
увеличения стоимости информации и, соответственно, возникает необходимость её
скрытия и защиты от несанкционированного использования. Шифрование информации -
единственное надёжное решение данной задачи. В связи с этим постоянно
увеличивается число подходов к шифрованию. Таким образом, цель данной работы напрямую
связана с актуальностью проблемы скрытия и защиты информации.
Цель:
Разработать программу шифрования при помощи шифра Виженера для
преобразования текста на кириллице в зашифрованный текст.
Задачи:
. Изучить метод шифрования при помощи шифра Виженера.
. Разработать алгоритм, связывающий идею шифрования и особенности языка
программирования.
. Разработать консольное приложение, которое преобразует текст на русском
языке в зашифрованный текст.
. Подготовить набор тестов и протестировать полученное приложение.
Под объектом исследования понимается шифрование и кодирование данных.
Предмет исследования представляет собой метод шифрования при помощи шифра
Виженера.
Глава 1. Шифрование при помощи шифра Виженера
1.1 История создания шифра
Первое точное документированное описание многоалфавитного шифра было
сформулировано Леоном Батиста Альберти в 1467 году, для переключения между
алфавитами использовался металлический шифровальный диск. Система Альберти
переключает алфавиты после нескольких зашифрованных слов. Позднее, в 1518 году,
Иоганн Трисемус в своей работе "Полиграфия" изобрел tabula recta -
центральный компонент шифра Виженера (таблица Виженера) [1].
То, что сейчас известно под шифром Виженера, впервые описал Джованни
Батиста Беллазо в своей книге La cifra del. Sig. Giovan Battista Bellasо. Он
использовал идею tabula recta Трисемуса, но добавил ключ для переключения
алфавитов шифра через каждую букву.
Блез Виженер представил своё описание простого, но стойкого шифра перед
комиссией Генриха III во Франции в 1586 году, и позднее изобретение шифра было
присвоено именно ему. Давид Кан в своей книге "Взломщики кодов"
отозвался об этом осуждающе, написав, что история "проигнорировала важный
факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал
для его создания".
Шифр Виженера имел репутацию исключительно стойкого к "ручному"
взлому. Известный писатель и математик Чарльз Лютвидж Доджсон (Льюис
Кэрроллназвал шифр Виженера невзламываемым в своей статье "Алфавитный
шифр", опубликованной в детском журнале в 1868 году. В 1917 году
Scientific American также отозвался о шифре Виженера, как о неподдающемся
взлому. Это представление было опровергнуто после того, как Касиски полностью
взломал шифр в XIX веке, хотя известны случаи взлома этого шифра некоторыми
опытными криптоаналитиками ещё в XVI веке.
Шифр Виженера достаточно прост для использования в полевых условиях,
особенно если применяются шифровальные диски. Например, "конфедераты"
использовали медный шифровальный диск для шифра Виженера в ходе Гражданской
войны.
.2 Процесс шифрования (алгоритм)
Будем считать, что исходный текст представляет собой строку
,
образованную символами алфавита
.
Длина текста - L символов.
При шифровании текста используется секретный ключ - символьная строка
длиной l:
.
Чем больше длина ключевого слова (или фразы), тем сложнее взломать шифр,
а, значит, тем надежнее защищен текст.
Для шифрования используется таблица Виженера (Квадрат Виженера), который
строится следующим образом: сверху и по левому краю квадрата выписывается
исходный алфавит. В первую строку квадрата заносится перестановка из букв
алфавита. Во второй строке та же перестановка циклически сдвигается на одну
позицию влево, в третьей - на две и т.д. Таким образом, квадрат состоит из N
перестановок, и каждой из них соответствует та буква исходного алфавита,
которая записана слева от нее. В приложении № 1 представлен пример квадрата
Виженера.
Часто в качестве первой строки таблицы используется не перемешанный, а
исходный алфавит. Это значительно упрощает процесс криптоанализа.
Шифрование исходного текста с помощью данного ключа и квадрата Виженера
осуществляется следующим образом. Ключевое слово многократно записывается под
исходным текстом. Каждая буква исходного текста шифруется при помощи буквенной
перестановки, соответствующей той букве ключевого слова, которая стоит под
данной буквой исходного текста. Таким образом, k-я буква шифрованного текста
находится в квадрате Виженера на пересечении i-й строки и j-го столбца, где i -
строка, соответствующая k-й букве исходного текста, а j - строка,
соответствующая букве ключевого слова с номером k (mod n), где n - длина
ключевого слова.
Ниже представлен пример шифрования фразы "Белый медведь - самый
крупный хищник" при помощи ключевого слова "квадрат" и квадрата
Виженера:
БЕЛЫЙ МЕДВЕДЬ САМЫЙ КРУПНЫЙ ХИЩНИК
КВАДР АТКВАДР АТКВА ДРАТКВА ДРАТКВ
ЛЭЛПО ЧНЯЖЗМЧ ДЙУРЩ ЯЕЬШНРЩ ОСОПЙЧ
Для того чтобы получить первую букву зашифрованного текста - Л,
нам необходимо в первой строке таблицы Виженера (Приложение №1) найти букву - Б,
которая является первой буквой в строке, которую требуется зашифровать. Буква Б
определяет нужный столбец в таблице. В первом столбце таблицы ищется буква - К,
которая является первой буквой в строке с повторениями ключа. Буква К
определяет в таблице нужную строку. На пересечении столбца - Б, и строки
-К, находится искомая буква - Л. Все остальные буквы шифруются
аналогично.
Расшифровать текст, зашифрованный с помощью шифра Виженера, зная
секретный ключ и квадрат Виженера, несложно. Поскольку шифр Виженера является
симметричным, для расшифровки необходимо выполнить действия, обратные тем,
которые применялись при шифровании текста.
Существует
несколько методов криптоанализа. Криптоанализ - наука о методах получения
исходного значения зашифрованной информации, не имея доступа к секретной
информации (ключу
<#"656668.files/image004.gif">
Рисунок 1. Результат работы программы 1
3.2 Тест №2
Файл сформирован неверно, т.е. не удовлетворяет правилам (Кириллица,
пробелы, знаки препинания).
Пример входной строки, сформированной неверно (см. Рисунок 2. Результат
работы программы 2):
Привет, mama!
Рисунок 2. Результат работы программы 2
3.3 Тест №3
Проверка правильности шифрования (строка без знаков препинания).
Поэтапный результат работы программы представлен в приложениях №5 - №9. Таким
образом, убеждаемся, что шифрование происходит верно.
3.4 Тест №4
Тест для проверки правильности шифрования (строка, в которой есть знаки
препинания). Поэтапный результат работы программы представлен в приложениях №10
- №20. Таким образом, убеждаемся, что шифрование происходит верно.
Заключение
Цель данной работы заключалась в разработке приложения для решения задачи
шифрования текста при помощи шифра Виженера. В ходе разработки приложения были
изучены особенности шифрования при помощи данного метода, а именно алгоритм
шифрования (Приложение №3 - Блок схема). Консольное приложение, решающее
поставленную задачу, написано на языке программирования C#.
В ходе разработки был освоен новый класс регулярных выражений RegEx, который содержит методы поиска и
сравнения для выполнения сопоставления шаблона с текстом. Этот метод в
программе использовался при поиске латинских символов в строке. Также
неоднократно использовался при написании адаптационного кода для латинского
алфавита. Использовать методы класса RegEx намного проще и быстрее, чем, например, задавать диапазон чисел
латинского алфавита и кириллицы, используя таблицу кодировки ACSII.
Данное приложение было протестировано при помощи ряда тестов. Первые два
теста связаны с неправильным формированием входной строки. При помощи первого
теста выявляется реакция программы на нулевую размерность строки. Второй тест
показывает результат работы программы, если строка сформирована неверно, то
есть содержит символы латинского алфавита. В третьем тесте использовалась строка,
состоящая только из пяти символов латинского алфавита. В четвертом тесте
использовалась строка, содержащая пробелы и знаки препинания. При описании
тестов была представлена побуквенная реализация.
Данный метод шифрования можно использовать и для других алфавитов. В
приложении №21 представлен измененный программный код, который позволяет
шифровать подобным методом строки на латинском алфавите. В приложении №22
показан результат работы программы.
В ходе тестирования был проведен анализ работы программы, а именно
выявлена зависимость времени выполнения программы от длины входной строки.
Результаты анализа представлены на диаграмме (Приложение № 23).
Библиографический список
Академик
[электронный ресурс] [режим доступа:
#"656668.files/image006.gif">
Рисунок 3. Квадрат Виженера в программе
Приложение № 3. Блок -
схема программы
Рисунок 4. Блок - схема программы
Приложение № 4. Исходный код
программы
using System;System.Collections.Generic;System.Linq;System.Text;System.IO;
//класс для работы с файламиSystem.Text.RegularExpressions; //Подключаем новый
класс для класс для RegexКурсовая_работа
{Program
{static void Sdvig(ref char[] mas) //функция сдвигает строку на еденицу
влево
{j;temp = mas[0];(j = 0; j < 30; j++)
{[j] = mas[j + 1];
}[30] = temp;
} void Main(string[] args)
{
{start = DateTime.Now;enpath = @"E:\Курсовая работа\Курсовая
работа_new\bin\Debug\Encrypt.txt";repath = @"E:\Курсовая
работа\Курсовая работа_new\bin\Debug\Result.txt";
//строка считывается из файла. Проверка условий праивльного формирования
входной строки.s = ""; //строка шифрования= File.ReadAllText(enpath,
Encoding.Default);(s.Length == 0)
{
Console.WriteLine("Файл пуст! Пожалуйста, введите строку в файл.
");
return;
}
//проверка на наличие символов латинского алфавитаi;pattern2 =
@"^[A-Za-z]+$";//регулярное выражение, задающее заглавные и строчные
символы латинского алфавитаrgx2 = new Regex(pattern2);//объявлеие нового класса
для регулярного выражения(i = 0; i < s.Length; i++)
{
//Если символ латинского алфавита
if (rgx2.IsMatch(Convert.ToString(s[i])))
{
Console.WriteLine("Строка в файле сформирована неверно. Строка может
содержать только символы кириллицы, пробелы и знаки припенания. ");
return;
}
}
//КВАДРАТ ВИЖЕНЕРА - ГЕНЕРАЦИЯ
//описание переменныхj, k = 0; //счетчики[,] kv_Viginer = new char[32,
32]; //матрица квадрата Виженераalfavit =
"абвгдежзиклмнопрстуфхцчшщьыъэюя"; //Строка алфавита кириллицы
//генерация первой строки и первого столбца, т.е. буквы следуют в
алфавитном порядке(i = 0; i < 1; i++) //генерация первой строки
{
for (j = 1; j < 32; j++)
{
kv_Viginer[i, j] = alfavit[k];
k++;
k = 0;
}(i = 1; i < 32; i++) //генерация первого столбца
for (j = 0; j < 1; j++)
{
kv_Viginer[i, j] = alfavit[k];
k++;
}
//заполняем оставшиеся строки и столбцы[] arr = new char[31]; //создаем
массив с переставленным алфавитомint a = 37;int b = 31;= 1;(j = 0; j < 31;
j++)
{
arr[j] = alfavit[(a * k) % b];
k++;
}
// заполним оставшиеся строки и столбцы, циклическим сдвигом на одну
еденицу влево= 0;(i = 1; i < 32; i++)
{
Sdvig(ref arr); //функция сдвигает строку на еденицу влево
for (j = 1; j < 32; j++)
{
kv_Viginer[i, j] = arr[k];
k++;
}
k = 0;
}
//ВВОД КЛЮЧЕВОГО СЛОВАkey = "";.WriteLine("Введите
ключевое слово шифра");.Write(">");flag = false; //проверка
правильности введенных данных(flag != true)
{
flag = true;
key = Console.ReadLine();
//Цикл по каждому элементу ключа
for (i = 0; i < key.Length; i++)
{
if ((Convert.ToInt16(key[i]) < 1072) || (Convert.ToInt16(key[i]) >
1103)) //если буква не принадлежит алфавиту
flag = false;
}
//Сообщение об ошибке
if (flag == false)
Console.WriteLine("Ключевое слово имеет запрещенные символы,
повторите ввод");
}
//ПРОЦЕСС ШИФРОВАНИЯx = 0, y = 0; //координаты новой буквы в таблице
Вижинераdublicat; //переменная для строчных и заглавных буквregistr = 0; buf =
""; //строка с повторяющимся ключемresult = ""; //строка с
результатомnew_key = ""; //строка с повторяющимся ключем, но учтены
знаки припинания и пробелы.WriteLine("Строка читается из файла... ");
//Формирование строки, длиной шифруемой, состоящей из повторений ключа (i
= 0; i < s.Length; i++)
{
buf += key[i % key.Length];
}
//формирование строки, состоящей из повторений ключа, но пропускающей
знаки не кириллицыv = 0;(i = 0; i < s.Length; i++)
{
//Если не кириллица
if (((int)(s[i]) < 1040) || ((int)(s[i]) > 1103))
{
new_key += " ";
}
else
{
new_key += buf[v];
v++;
}
}
//ШИФРОВАНИЕ(i = 0; i < s.Length; i++)
{
//Если не кириллица
if (((int)(s[i]) < 1040) || ((int)(s[i]) > 1103))
{
result += s[i];
}
else
{
//Поиск в первом столбце строки, начинающейся с символа ключа
int l = 0;
flag = false;
//Пока не найден символ
while ((l < 32) && (flag == false))
{
//Если символ найден
{
//Запоминаем в х номер строки
x = l;
flag = true;
}
l++;
}
//Уменьшаем временно регистр прописной буквы в шифровальной строке
if ((Convert.ToInt16(s[i]) < 1072) && (Convert.ToInt16(s[i])
>= 1040)) //диапозон заглавных букв
{
dublicat = Convert.ToChar(Convert.ToInt16(s[i]) + 32);
registr = 1;
}
else
{
registr = 0;
dublicat = s[i];
}
l = 0;
flag = false;
//Пока не найден столбец в первой строке с символом строки
while ((l < 32) && (flag == false))
{
//Проверка совпадения
if (dublicat == kv_Viginer[0, l])
{
//Запоминаем номер столбца
y = l;
flag = true;
}
l++;
}
// Увеличиваем регистр буквы до прописной
if (registr == 1)
{
//Изменяем символ на первоначальный регистр
dublicat = Convert.ToChar(Convert.ToInt16(kv_Viginer[x, y]) - 32);
result += dublicat;
}
else
{
result += kv_Viginer[x, y];
}
}
}
//Вывод зашифрованной строки.WriteLine("Строка успешно
зашифрована!"); .WriteAllText(repath, result); //Вывод результата в
файлrezult1 = DateTime.Now - start;.WriteLine("Вермя выполнения программы
" + rezult1.ToString());.WriteLine("Длина входной строки = {0}
",s.Length);
}(Exception e)
{.WriteLine("Ошибка " + e.Message);
}
}
}
}
Приложение №5. Результат тестирования
№ 3 - Шаг 1
Рисунок 5. Шаг 1
Приложение №6. Результат тестирования
№ 3 - Шаг 2
Рисунок 6. Шаг 2.
Приложение №7. Результат тестирования №3 - Шаг 3
Рисунок 7. Шаг 3
Приложение №8. Результат тестирования №3 - Шаг 4
Рисунок 8. Шаг 4
Приложение №9. Результат тестирования
№3 - Шаг 5
Рисунок 9. Шаг 5
Приложение №10. Результат тестирования №4 - Шаг 1
Рисунок 10. Шаг 1
Приложение №11. Результат
тестирования №4 - Шаг 2
Рисунок 11. Шаг 2
Рисунок 12. Шаг 3
Приложение №13. Результат тестирования №4 - Шаг 4
Рисунок 13. Шаг 4
Приложение № 14. Результат
тестирования №4 - Шаг 5
Рисунок 14. Шаг 5
Приложение № 15. Результат
тестирования №4 - Шаг 6
Рисунок 15. Шаг 6
Приложение №16. Результат
тестирования №4 - Шаг 7
Рисунок 16. Шаг 7
Приложение №17. Результат
тестирования №4 - Шаг 8
Рисунок 17. Шаг 8
Приложение №18. Результат
тестирования №4 - Шаг 9
Рисунок 18. Шаг 9
Приложение №19. Результат
тестирования №4 - Шаг 10
Рисунок 19. Шаг 10
Приложение №20. Результат
тестирования №4 - Шаг 11
Рисунок 20. Шаг 11
Приложение №21. Адаптация программы
под латинский язык
Исходный код:
System;System.Collections.Generic;System.Linq;System.Text;System.IO;System.Text.RegularExpressions;
//Подключаем новый класс для класс для RegexКурсовая_работа
{Program
{static void Sdvig(ref char[] mas) //функция сдвигает строку
на еденицу влево
{j;temp = mas[0];(j = 0; j <25 ; j++)
{[j] = mas[j + 1];
}[25] = temp;
} void Main(string[] args)
{enpath = @"D:\ВШЭ ДАША\Курсовая работа\Курсовая
работа_адаптация\bin\Debug\Encrypt.txt";repath = @"D:\ВШЭ
ДАША\Курсовая работа\Курсовая работа_адаптация\bin\Debug\Result.txt";
//КВАДРАТ ВИЖЕНЕРА - ГЕНЕРАЦИЯ
//описание переменныхi, j, k = 0; //счетчики[,] kv_Viginer
= new char[27, 27]; //матрица квадрата Виженераalfavit =
"abcdefghijklmnopqrstuvwxyz"; //Строка алфавита латинского алфавита
//генерация первой строки и первого столбца, т.е. буквы
следуют в алфавитном порядке(i = 0; i < 1; i++) //генерация первой строки
{(j = 1; j < 27; j++)
{
kv_Viginer[i, j] = alfavit[k];
k++;
}= 0;
}(i = 1; i < 27; i++) //генерация первого столбца(j = 0; j
< 1; j++)
{
kv_Viginer[i, j] = alfavit[k];
k++;
}
//заполняем оставшиеся строки и столбцы[] arr = new char[26];
//создаем массив с переставленным алфавитомint a = 31;int b = 26;= 1;(j = 0; j
< 26; j++)
{[j] = alfavit[(a * k) % b];++;
}
// заполним оставшиеся строки и столбцы, циклическим сдвигом
на одну еденицу влево= 0;(i = 1; i < 27; i++)
{(ref arr);(j = 1; j < 27; j++)
{
kv_Viginer[i, j] = arr[k];
k++;
}= 0;
}
//ВВОД КЛЮЧЕВОГО СЛОВАpattern = @"^[a-z]+$";
//ограничение символов для ввода ключевого словаrgx = new Regex(pattern);key =
"";.WriteLine("Введите ключевое слово шифра");flag = false;
//проверка правильности введенных данных(flag != true)
{= true;= Console.ReadLine();
//Цикл по каждому элементу ключа(i = 0; i < key.Length;
i++)
{
if (rgx.IsMatch(Convert.ToString(key[i]))) flag = true;
else flag = false;
if (flag == false)
{
Console.WriteLine("Ключевое слово имеет запрещенные
символы, повторите ввод");//Сообщение об ошибке
break;
}
}
}
//ПРОЦЕСС ШИФРОВАНИЯx = 0, y = 0; //координаты новой буквы в
таблице Вижинера s = ""; //строка шифрованияbuf = "";
//строка с повторяющимся ключемresult = ""; //строка с
результатомnew_key = "";//строка с повторяющимся ключем, но учтены
знаки припинания и пробелы
.WriteLine("Строка читается из файла... ");=
File.ReadAllText(enpath, Encoding.Default);
//Формирование строки, длиной шифруемой, состоящей из
повторений ключа (i = 0; i < s.Length; i++)
{+= key[i % key.Length];
}
//формирование строки, состоящей из повторений ключа, но
пропускающей знаки не латинского алфавитаv = 0;(i = 0; i < s.Length; i++)
{pattern3 = @"^[A-Za-z]+$";rgx3 = new
Regex(pattern3);
{
new_key += buf[v];
v++;
}
{
new_key += " ";
}
}.WriteLine(s+" <= строка из
файла");.WriteLine(new_key+" <= строка из повторений ключа");
//Шифрование (i = 0; i < s.Length; i++)
{pattern2 = @"^[A-Za-z]+$";rgx2 = new
Regex(pattern2);(i = 0; i < s.Length; i++)
{
//Если латинский алфавит
if (rgx2.IsMatch(Convert.ToString(s[i])))
{
//Поиск в первом столбце строки, начинающейся с символа ключа
int l = 0;
flag = false;
//Пока не найден символ
while ((l < 26) && (flag == false))
{
//Если символ найден
if (new_key[i] == kv_Viginer[l, 0])
{
//Запоминаем в х номер строки
x = l;
flag = true;
}
l++;
}
flag = false;
l = 0;
//Пока не найден столбец в первой строке с символом строки
while ((l < 32) && (flag == false))
{
//Если символ найден
if (s[i] == kv_Viginer[0, l])
{
//Запоминаем в х номер строки
y = l;
flag = true;
}
l++;
}
result += kv_Viginer[x, y];
Console.Write(kv_Viginer[x, y]);
}
else
{
result += s[i];
Console.Write(s[i]);
}
}
}
//Вывод на экран зашифрованной
строки.WriteLine();.WriteLine("Строка успешно зашифрована!");
.WriteAllText(repath, result); //Вывод результата в файл
}
}
}
Приложение №22. Тесты программы
(адаптации) под латинский язык
Рисунок 22. Результат работы программы - без знаков препинания и пробелов
Рисунок 23. Результат работы программы - без знаков препинания и пробелов
Приложение №23. Диаграмма 1
Рисунок 24. Зависимость времени работы программы от длины входной строки.