Алгоритмы, основанные на алфавитных перестановках.
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. П. ОГАРЁВА»
Факультет электронной техники
Кафедра автоматизированных систем обработки информации и управления
КУРСОВАЯ РАБОТА
Программа на языке С
Автор курсовой работы ___________ 16.06.2012 Р.Р. Мамиев
Специальность 230100 АСОИУ
Обозначение курсовой работы КР-02069964-230100-21-12
Руководитель работы ____________ 16.06.2012 О. И. Пенин
Оценка ___________
Саранск
2012
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. П. ОГАРЁВА»
Факультет электронной техники
Кафедра автоматизированных систем обработки информации и управления
ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ
Студент Мамиев Ренат Рафаэлевич
1 Тема Программа на языке С
2 Срок представления работы (проекта) к защите
|
|
3 Исходные данные для научного исследования (проектирования) Написать программу шифрования текста по следующему алгоритму: задан массив S из 10 целых цифр (ключ) и файл с текстом, выполняется циклическая замена каждой буквы, стоящей на K-й позиции в строке, на букву того же регистра, расположенную в алфавите на SK-м месте после шифруемой буквы (для K = 11 снова используется смещение S1 и т.д.). Знаки препинания и пробелы не изменять. Результирующий файл должен иметь отличное от исходного расширение.
4 Содержание курсовой работы (проекта)
4.1 Простейшие алгоритмы шифрования
4.2Алгоритмы, основанные на операции «исключающее или» (XOR).
4.3 Алгоритмы, основанные на алфавитных перестановках.
4.4 Постановка задачи
4.5 Описание алгоритма
|
|
4.6 Исходный код
4.7 Пример выполнения
4.8 Пример выполнения
Руководитель работы (проекта) _________________ О.И.Пенин
подпись, дата инициалы, фамилия
Задание принял к исполнению ___________________________
дата, подпись
Реферат
Курсовая работа содержит 13 страниц, 5 использованных источника.
Объектом исследования являются возможности программирования на С.
Цель работы – на практике освоить язык программирования, используемый в курсовой работе, его особенности. Ознакомиться с основными функциями, объектами и их свойствами. Научиться применять полученные знания.
В процессе работы была написана программа «Шифрование», которая производит шифровку заданного текста. Программу можно применять в целях защиты необходимой информации.
|
|
Простейшие алгоритмы шифрования
Шифрованием называют процесс преобразования открытых данных в зашифрованные (шифротекст) или зашифрованных данных в открытые по определенным правилам с применением ключей.
С помощью криптографических методов возможно:
– шифрование информации;
– реализация электронной подписи;
– распределение ключей шифрования;
– защита от случайного или умышленного изменения информации.
К современным алгоритмам шифрования предъявляются определенные требования:
– высокий уровень защиты данных против дешифрования и возможной модификации;
– защищенность информации должна основываться только на знании ключа и не зависеть от того, известен алгоритм или нет (правило Киркхоффа);
– малое изменение исходного текста или ключа должно приводить к значительному изменению шифрованного текста (эффект "обвала");
– область значений ключа должна исключать возможность дешифрования данных путем перебора значений ключа;
|
|
– экономичность реализации алгоритма при достаточном быстродействии;
– стоимость дешифрования данных без знания ключа должна превышать стоимость данных.
Разумеется, при знакомстве с данной областью следует начинать с базовых понятий и элементарных алгоритмов, которые ввиду своей простоты не обладают большинством из выше перечисленных свойств, но позволяют понять базовые принципы и проблематику задачи шифрования.
Алгоритмы, основанные на операции «исключающее или» (XOR).
Побитовая операция XOR (в Си обозначается знаком ^), как известно, дает следующий результат:
– 0^0 = 1^1 = 0
– 0^1 = 1^0 = 1
Замечательное свойство операции XOR:
,
т.е. будучи дважды примененной, операция XOR восстанавливает исходное значение аргумента. На этом свойстве строится одно из простейших семейств методов шифрования.
Пусть есть последовательность исходных открытых данных (текст) , состоящая из элементарных единиц данных (например, символов) – . И пусть имеется ключ – символ, с помощью которого необходимо зашифровать данные.
Алгоритм шифрования:
– каждый символ заменяем на .
Алгоритм дешифрования:
– каждый символ заменяем на .
Как видим, алгоритмы шифрования и дешифрования совпадают.
Поскольку ключ состоит лишь из единственного символа, то его очень просто подобрать. Более того, даже если взять ключ из N символов и последовательно применять их к каждому символу текста:
Это будет эквивалентно применению 1 операции :
Таким образом, длина ключа в данном алгоритме не влияет на сложность расшифровывания путем подбора, т.к. ключ любой длины эквивалентен ключу длины 1.
Впрочем, можно разработать нескончаемое множество различных усложненных вариаций шифрования XOR-ом.
Например, имея ключ длиной 10 символов, каждый десятый символ текста шифруем первым символом ключа, следующий каждый десятый символ текста – вторым символом ключа и т.д.
Покажем данный алгоритм на примере. Пусть ключом является слово «ключ» и необходимо зашифровать фразу «Мама мыла раму.»:
XOR | М | а | м | а | м | ы | л | а | р | а | м | у | . | ||
к | л | ю | ч | к | л | ю | ч | к | л | ю | ч | к | л | ю | |
Результат: | & | ♂ | ↕ | ↕ | К | ♣ | ∟ | 0x0D | 0x0A | Л | ♫ | ↨ | ♠ | ↑ | Р |
Реализация данного алгоритма на языке Си довольно проста:
char* xorcode(const char *s, const char *key)
{
int i;
int n = strlen(s);
int m = strlen(key);
char *result = strdup(s);
for(i = 0; i < n; ++i) result[i] ^= key[i % m];
return result;
}
Ключевым моментом, в котором и происходит шифрование, является операция:
result[i] ^= key[i % m];
При помощи которой исходный ый символ заменяется на него же, но «сксоренного» с ым символом ключа. Обратим внимание на применение операции взятия остатка от деления при вычислении номера символа в ключе. В нашем тестовом случае (длина ключа). Тогда операция i%4 будет выдавать результат:
0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, ...
Что собственно и необходимо. Т.е. с помощью остатка от деления мы циклически проходим по ключу.
Более сложные вариации алгоритмов шифрования на основе XOR используют случайные числа, различные сдвиги, зависимость шифрования последующих символов от предыдущих и т.д. Но в любом случае, подобные приемы не применимы на практике в современном мире из-за легкости их взлома. Тем не менее, они дают базовые знания о методах шифрования.
Алгоритмы, основанные на алфавитных перестановках.
Другим простейшим семейством алгоритмов шифрования являются алгоритмы, построенные на алфавитных преобразованиях. Подобные методы шифрования часто применялись в древности.
Например, часть священных писаний на иврите была зашифрована методом Ат-Баш, по которому первой букве алфавита ставилась в соответствие последняя буква, второй – предпоследняя и т.д. Как видим, данный алгоритм не имеет ключа вовсе. Достаточно угадать способ шифрования и любые тексты, зашифрованные им, могут быть расшифрованы.
Другой известный алгоритм – шифр Цезаря. В исходном виде данного метода каждая буква текста заменялась на букву, отстоящую от нее в алфавите на позиций. – в данном случае и есть ключ. Сам Цезарь использовал . Т.е. например, литера A заменялась на литеру D, B – на E, Z – на C, и т.д.
Разумеется, число можно варьировать как угодно. Более того, можно использовать ключ из произвольного количества чисел:
,
смещая первую букву текста на , вторую – на , третью – на и т.д. Дойдя до , разумеется, возвращаемся снова к .
Именно этот алгоритм и реализован далее в практической части.
Постановка задачи
Написать программу шифрования текста по следующему алгоритму. Задан ключ key (массив из 10 целых цифр) и файл с текстом. Каждый k-ый символ текста заменяется на символ в том же регистре, расположенный на key[k] позиций правее в алфавите (при k=10 снова переходим к key[0] и т.д.).
Знаки препинания и пробелы не изменять. Результирующий файл должен иметь отличное от исходного расширение.
Описание алгоритма
Запрашиваем имя входного файла, открываем его. В случае ошибки завершаем программу.
Далее необходимо подготовить имя выходного файла, заменив в нем расширение (например, на .out). Для этого ищем в имени файла первую точку с конца функцией strrchr. Функция возвращает указатель на искомый символ или NULL в случае его отсутствия (в этом случае устанавливаем символ в конец строки, чтобы приписать расширение). Начиная с возвращенного указателя записываем в следующие 5 символов строки символы «.out\0».
Открываем выходной файл с новым именем. В случае ошибки завершаем программу.
Посимвольно читаем файл и, если очередной прочитанный символ является символом латинского алфавита, то шифруем его:
– если это большая буква, то отнимаем от нее символ «A», тем самым получаем номер буквы в алфавите (от 0 до 25);
– прибавляем к этому смещению key[k], получив номер шифрованной буквы;
– получаем остаток от деления на 26, т.к. номер шифрованной буквы может оказаться больше 25;
– прибавляем к полученному номеру символ «A» что и будет зашифрованным символом;
– аналогичным образом шифруем и прописные символы, с той разницей, что отнимается и прибавляется символ «a»;
– для остальных символов, не входящих в латиницу, ничего не предпринимаем;
– записываем символ в выходной файл;
– увеличиваем k, чтобы следующий символ шифровать следующим числом ключа;
– если k превысило 9, то сбрасываем его в ноль (возвращаемся в начало ключа).
Исходный код
#include <stdio.h>
#include <string.h>
// файлы, буферы ввода, счетчики
FILE *f1, *f2;
char s[105], *pos;
int code, k = 0;
// ключ шифрования
const int key[10] = { 5, 20, 3, 24, 22, 12, 13, 1, 2, 9 };
int main()
{
// ввод имени входного файла
printf("Enter file name: ");
scanf("%100s", s);
// открытие входного файла
if((f1 = fopen(s, "r")) == NULL)
{
printf("Can't open input file!\n");
return -1;
}
// поиск точки в имени файла (с конца)
pos = strrchr(s, '.');
if(pos == NULL) pos = s + strlen(s);
// замена/добавление нового расширения
pos[0] = '.';
pos[1] = 'o';
pos[2] = 'u';
pos[3] = 't';
pos[4] = '\0';
// открытие выходного файла
if((f2 = fopen(s, "w")) == NULL)
{
printf("Can't create/open output file!\n");
return -1;
}
// читаем посимвольно входной файл
while((code = fgetc(f1)) != EOF)
{
if(code >= 'A' && code <= 'Z')
{
// шифрование большой буквы
code = 'A' + ((code - 'A' + key[k]) % 26);
}
else if(code >= 'a' && code <= 'z')
{
// шифрование прописной буквы
code = 'a' + ((code - 'a' + key[k]) % 26);
}
// выводим результат в файл
fputc(code, f2);
// увеличиваем k
++k;
if(k >= 10) k = 0;
}
// закрываем файлы, выводим сообщение о завершении
printf("Work finished! Look file %s\n", s);
fcloseall();
return 0;
}
Пример выполнения
Ключ:
const int key[10] = { 5, 20, 3, 24, 22, 12, 13, 1, 2, 9 };
Исходный текст (text.txt):
Запуск программы:
Зашифрованный текст (text.out):
Список литературы:
1. Б.Керниган, Д.Ритчи, А.Фьюер. Язык программирования Си. Задачи по языку Си. М.: Финансы и статистика, 1985.
2. М.Уэйт, С.Прата, Д.Мартин. Язык Си. Руководство для начинающих. - М.: Мир, 1988.
3. М.Болски. Язык программирования Си. Справочник. - М.: Радио и связь, 1988.
4. Л.Хэнкок, М.Кригер. Введение в программирование на языке Си. - М.: Радио и связь, 1986.
5. М.Дансмур, Г.Дейвис. ОС UNIX и программирование на языке Си. - М.: Радио и связь, 1989.
Дата добавления: 2021-03-18; просмотров: 130; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!