Алгоритмы, основанные на алфавитных перестановках.

Федеральное государственное бюджетное образовательное

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

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. П. ОГАРЁВА»

Факультет электронной техники

Кафедра автоматизированных систем обработки информации и управления

КУРСОВАЯ РАБОТА

Программа на языке С

Автор курсовой работы ___________ 16.06.2012 Р.Р. Мамиев

Специальность 230100 АСОИУ

Обозначение курсовой работы КР-02069964-230100-21-12

Руководитель работы ____________ 16.06.2012 О. И. Пенин

Оценка ___________

Саранск

2012

Федеральное государственное бюджетное образовательное

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

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. П. ОГАРЁВА»

Факультет электронной техники

Кафедра автоматизированных систем обработки информации и управления

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

Студент Мамиев Ренат Рафаэлевич

1 Тема Программа на языке С

2 Срок представления работы (проекта) к защите

3 Исходные данные для научного исследования (проектирования) Написать программу шифрования текста по следующему алгоритму: задан массив S из 10 целых цифр (ключ) и файл с текстом, выполняется циклическая замена каждой буквы, стоящей на K-й позиции в строке, на букву того же регистра, расположенную в алфавите на S_K-м месте после шифруемой буквы (для K = 11 снова используется смещение S₁и т.д.). Знаки препинания и пробелы не изменять. Результирующий файл должен иметь отличное от исходного расширение.

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; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!