Шифр Цезаря

2

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Новокузнецкий филиал-институт Кемеровского государственного университета

Факультет информационных технологий

Кафедра общей и прикладной информатики

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

по курсу: “Языки программирования и методы трансляции”

на тему: “Шифр Цезаря”

Выполнил:

ст. гр. ПМИ-052

Веселков В.И.

Проверил:

ст. преп. Веслов К.Н.

Новокузнецк, 2007

РЕФЕРАТ

Отчет содержит 19 страниц, 10 рисунков, 4 источника, 2 приложения.

ШИФРОВАНИЕ, ДЕШИФРОВАНИЕ, АЛГОРИТМ, РЕЖИМ, ПЕРЕБОР, КЛЮЧ.

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

Была разработана программа "Шифр Цезаря". Программа позволяет зашифровывать тексты методом Юлия Цезаря и дешифровать тексты, закодированные данным способом. Имеет возможность как автоматического нахождения или выбора ключа (в зависимости от выбранного режима работы программы), так и самостоятельного ввода ключа пользователем . Программа имеет 2 режима работы: «Шифрование» и «Дешифрование».

ЗАДАНИЕ НА ПРОЕКТИРОВАНИЕ

Юлий Цезарь был, якобы первым, кто придумал собственно шифр. Алфавит размещается по кругу на его часах (при этом в русском алфавите, после А идет Б, a после Я - А). Для зашифровки буквы текста заменяются буквами, отстоящими по кругу на заданное число букв дальше по ходу часовой стрелки. Если, скажем, сдвиг на 3, то вместо i-й используется (i+3)-я буква, например, вместо А пишется Г, а вместо Я пишется В. При расшифровке, наоборот, берут букву на заданное число букв ближе, т. е. двигаясь против часовой стрелки.

Написать и испытать программу для шифрования и взлома кода Цезаря.

СОДЕРЖАНИЕ

Введение

1. Основная часть

1.1 Анализ задачи

1.2 Описание алгоритма

1.3 Описание программы

Заключение

Список литературы

Приложение А. Листинг программы

Приложение Б. Контрольные примеры

ВВЕДЕНИЕ

Основная цель данной курсовой работы - обучение. Студент учится формировать постановку задач, составлять алгоритмы их решения и формализовать эти алгоритмы в популярной среде программирования. В ходе написания программы студент осваивает язык C++ и особенности его трансляции в компиляторе Builder.

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

Для достижения этих целей была выбрана задача «Шифр Цезаря». Уровень сложности этой задачи позволяет ознакомиться с основными этапами написания реальных программ, и приобрести определенные навыки программирования.

Для решения задачи был использован метод перебора.

ОСНОВНАЯ ЧАСТЬ

Анализ задачи

Данную задачу для решения удобно разбить на несколько подзадач, а именно:

1) отдельно осуществить подготовку данных;

2) отдельно их обработку;

3) отдельно сделать вывод результата.

Подготовка данных состоит в:

- вводе исходного текста;

- создании временного текстового файла («файл 1») и занесение в него исходного текста ;

- создании временного текстового файла («файл 2») для последующего занесения в него результатов работы программы;

- вводе или автоматическом выборе ключа;

- для режима дешифрования, если ключ неизвестен :

· подсчёте общего числа русских букв в «файле 1»;

· переборе по сдвигам ;

для каждого значения сдвига :

· последовательном считывании кодов всех символов, присутствующих в «файле 1»;

· подсчёте количества вхождений каждой русской буквы в текст и нахождении частоты вхождения каждой русской буквы в текст;

· сравнении найденных частот со значениями соответствующих частот встречи букв в русском алфавите;

· нахождении того значения сдвига, для которого разница частот минимальная;

Обработка данных заключается в:

- проверке корректности ввода ключа пользователем;

- последовательном считывании кодов всех символов, присутствующих в «файле 1»;

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

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

- последовательном занесении очередного изменённого или не измененного символа в «файл 2»;

Вывод результатов включает в себя в зависимости от результатов проверки корректности ввода ключа, а также выбранного режима работы программы:

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

Описание алгоритма

2

Рисунок 1 - Общая блок-схема программы.



2

Рисунок 2 - Блок-схема функции подготовки данных.



2

Рисунок 3 - Блок-схема функции шифрования текста.

2

Рисунок 4 - Блок-схема функции дешифрования текста.



2

Рисунок 5 - Блок-схема функции вывода данных.

Рисунок 6 - Блок-схема функции вывода сообщения об ошибке.

Описание программы

Принцип работы программы несложен и понятно изложен на блок-схеме и в анализе задачи. Основными функциями программы являются функции coding, decoding, decoding_findsdv, keyproverka.

void coding();

int decoding_findsdv();

void decoding();

void keyproverka().

С помощью функции coding осуществляется шифрование текста (подробно см. Рисунок 3). Входными данными являются содержание файла *TmpFName ("cipher_cesar_temp.tmp") и значение ключа, введенного пользователем или выбранного автоматически. Результатом работы функции является зашифрованный текст, в котором зашифрованы только большие и маленькие русские буквы.

С помощью функции decoding_findsdv осуществляется нахождение того сдвига букв, для которого разница частот встречи букв в тексте и в русском алфавите минимальна (подробно см. Рисунок 2). Входными данными является содержание файла *TmpFName ("cipher_cesar_temp.tmp"). Результатом работы функции является значение переменной sdvig типа int, которое возвращается в вызвавшую её функцию decoding.

С помощью функции decoding осуществляется дешифрование текста (подробно см. Рисунок 4). Входными данными являются содержание файла *TmpFName ("cipher_cesar_temp.tmp") и значение ключа, введенного пользователем или найденного в функции decoding_findsdv. Результатом работы функции является расшифрованный текст, который был зашифрован «методом Цезаря».

Функция keyproverka осуществляет проверку корректности значения ключа, введенного пользователем, т.е. проверяет не содержит ли данный ключ символов не относящихся к цифрам из диапазона 0..9. Результатом работы функции является значение переменной prov типа bool (true или false), передаваемое в обработчик события нажатия на кнопку «Начать».

При открытии программы появляется такое окно:



Рисунок 6 - Начало работы.

В верхней правой части окна пользователь может выбрать один из режимов: «Шифрование» и «Дешифрование».

В верхнем желтом поле пользователь может ввести текст самостоятельно или из существующего текстового файла.

Затем ниже надписи "Введите ключ здесь" можно ввести нужное значение ключа , состоящее из цифр в диапазоне от 0 до 9, после чего нажать кнопку "Начать". После того, как процесс шифрования/дешифрования будет окончен, в нижней желтом поле появляется зашифрованный/расшифрованный текст, а после надписи «Ключ = » появляется значение ключа(см. рис. 7).



Рисунок 7 - Вид после окончания расчета.

Если окажется, что введенный ключ некорректен, то будет выведено сообщение об ошибке (см. Рисунок Б.3).

ЗАКЛЮЧЕНИЕ

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Страуструп Б. Язык программирования С++. / Б.Страуструп. - Киев: ДиаСофт, 1993. - 540c.

2. Павловская Е.А. Программирование на языке высокого уровня / Павловская Е.А.. - Минск: Питер, 2005. - 460с.

3. Архангельский А.Я. Программирование в C++ Builder 6./А.Я. Архангельский, М.: «Издательство Бином», 2003 г.. - 1152 c.

4. Подбельский В.В. Программирование на языке Си / В.В. Подбельский, С.С.Фомин. - М.: Финансы и статистика, 2002. - 326c.

ПРИЛОЖЕНИЕ А

Листинг программы.

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include<fstream.h>

#include <cstring.h>

#include<iostream.h>

#include<math.h>

#include "Unit1.h"

#include "About.h"

#include "Unit2.h"

#include "Unit4.h"

#include "Unit3.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

AnsiString MyFName="", //Имя открываемого файла

SaveMyFName=""; //Имя сохраняемого файла

void coding(); //Функция зашифровки

void decoding(); //Функция расшифровки

int decoding_findsdv(); //Функция нахождения ключа

bool keyproverka(); //Функция проверки корректности ввода ключа

//-----------------имена временных файлов-----------------------

char *TmpFName="cipher_cesar_temp.tmp",

*TmpFName1="cipher_cesar_temp_1.tmp";

bool savdet=0; //сохранен ли файл

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//------Сохранение нормального расположения компонентов на форме-------------

void __fastcall TForm1::FormResize(TObject *Sender)

{

Memo1->Height=Form1->ClientHeight/2;

Memo2->Top=Form1->ClientHeight/2;

Memo2->Height=Memo1->Height;

Label3->Left=Memo1->Width+20;

Label1->Left=Memo1->Width+20;

Label4->Left=Memo1->Width+20;

Edit1->Left=Memo1->Width+68;

Label2->Left=Memo1->Width+41;

Label2->Top=Label4->Top+Label4->Height+18;

}

//-----------Отключение активности кнопки НАЧАТЬ если в Memo1 пусто----------

void __fastcall TForm1::Memo1Change(TObject *Sender)

{

if(Memo1->Lines->Text!="")

Button1->Enabled=true;

if(Memo1->Lines->Text=="")

Button1->Enabled=false;

Memo1->Font->Size=10;

Memo2->Font->Size=10;

Label2->Caption="Ключ = ";

}

//--------------------Нажатие на кнопку начать-----------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

// keyproverka(); //Проверка корректности ввода ключа

if(keyproverka())

{

Memo1->Lines->SaveToFile(TmpFName);

if(RadioGroup1->ItemIndex==0)

coding();

if(RadioGroup1->ItemIndex==1)

decoding();

}

//Вывод предупреждения о некорректности ввода

else {WarningBox->ShowModal(); Edit1->Text=""; }

}

//---------------О программе-------------------------------------------------

void __fastcall TForm1::AboutClick(TObject *Sender)

{

AboutBox->ShowModal();

}

//----------Диалог открытия файла--------------------------------------------

void __fastcall TForm1::OpenClick(TObject *Sender)

{

if(OpenDialog1 ->Execute())

{

MyFName=OpenDialog1->FileName;

Memo1->Lines->LoadFromFile(MyFName);

Button1->Enabled=true;

Label2->Caption="Ключ = ";

savdet=0;

}

}

//-------Диалог Сохранить как---------------------------------------------

void __fastcall TForm1::SaveAsClick(TObject *Sender)

{

if(SaveDialog1 ->Execute())

{

SaveMyFName=SaveDialog1->FileName;

Memo2->Lines->SaveToFile(SaveMyFName);

savdet=1;

}

}

//--------Диалог Сохранить------------------------------------------------

void __fastcall TForm1::SaveClick(TObject *Sender)

{

if(savdet==1)

Memo2->Lines->SaveToFile(SaveMyFName);

else if(SaveDialog1 ->Execute())

{

SaveMyFName=SaveDialog1->FileName;

Memo2->Lines->SaveToFile(SaveMyFName);

savdet=1;

}

}

//-----------Проверка сохранения файла перед выходом--------------------------

void __fastcall TForm1::ExitClick(TObject *Sender)

{

if(!savdet)

CloseBox->Show();

else Close();

}

//------Выбор режима работы программы--------------------------------------

void __fastcall TForm1::RadioGroup1Click(TObject *Sender)

{

if(RadioGroup1->ItemIndex==0)

{

Label1->Caption="или он будет выбран";

Memo2->Lines->Text="";

Label2->Caption="Ключ = ";

savdet=0;

}

if(RadioGroup1->ItemIndex==1)

{

Label1->Caption="или он будет найден";

Memo2->Lines->Text="";

Label2->Caption="Ключ = ";

savdet=0;

}

}

//------------Окно помощи---------------------------------------------------

void __fastcall TForm1::HelpClick(TObject *Sender)

{

HelpBox->ShowModal();

}

//---------Проверка корректности ввода----------------------------------------

bool keyproverka()

{ bool prov;

prov=1;

int code,i;

char *editkey2="";

AnsiString editkey1="";

if(Form1->Edit1->Text!="")

{

editkey1=Form1->Edit1->Text;

editkey2=editkey1.c_str();

i=0;

while(editkey2[i]!=NULL)

{

code=editkey2[i];

if(code<48||code>57) prov=0;

i++;

}

}

return prov;

}

//---------------------Функция кодирования текста-----------------------------

void coding()

{

char b; long sdvig;

Form1->Label2->Caption="" ;

if(Form1->Edit1->Text!="")

{

sdvig=StrToInt(Form1->Edit1->Text);

if(sdvig>32)

sdvig%=32;

}

else sdvig=random(32)+1;

ifstream tempfile(TmpFName);

ofstream tempfile1(TmpFName1);

while(!tempfile.eof())

{

b=0;

tempfile.get(b) ;

if(b>=-64&&b<=-33||b==-88) //Сдвиг для больших букв

{

if(b==-88) b=-59+sdvig ; //Если попадается буква Ё

else b+=sdvig;

if(b>-33) b-=32;

}

if(b>=-32&&b<=-1) //Сдвиг для маленьких букв

{

b+=sdvig;

if(b>-1) b-=32;

}

tempfile1.put(b);

}

tempfile.close(); //Закрытие временного файла

remove(TmpFName); //Удаление временного файла

tempfile1.close(); //закрытие закодированного файла

Form1->Memo2->Lines->LoadFromFile(TmpFName1);

remove(TmpFName1); //Удаление временного файла

Form1->Label2->Caption= "Ключ = "+IntToStr(sdvig) ;

}

/*-------------------Функция декодирования текста-----------------------*/

void decoding()

{

int sdvig=0, //сдвиг по алфавиту

i,j;

char b;

sdvig=decoding_findsdv();

//----------------Расшифровка текста------------------------------

ifstream tempfile2(TmpFName); //Открытие файла для чтения

ofstream tempfile1(TmpFName1); //Открытие файла для записи

while(!tempfile2.eof())

{

b=0;

tempfile2.get(b) ; //Считывание кода очередного символа

if(b>=-64&&b<=-33||b==-88) //Сдвиг для больших букв

{

if(b==-88) b=-59-sdvig ; //Если попадается буква Ё

else b-=sdvig; //Сдвиг

if(b<-64) b+=32; //После буквы А

}

if(b>=-32&&b<=-1) //Сдвиг для маленьких букв

{

b-=sdvig; //Сдвиг

if(b<-32) b+=32; //После буквы а

}

tempfile1.put(b); //Запись расшифрованной буквы

}

tempfile2.close(); //Закрытие временного файла

remove(TmpFName); //Удаление временного файла

tempfile1.close(); //закрытие закодированного файла

Form1->Memo2->Lines->LoadFromFile(TmpFName1);

remove(TmpFName1); //Удаление временного файла

Form1->Label2->Caption= "Ключ = "+IntToStr(sdvig) ;

}

//--------------Нахождение ключа-------------------------------

int decoding_findsdv()

{

int counter=0, //счетчик количества букв

sdvig=0, //сдвиг по алфавиту

i,j;

double delta=0,mindelta=50 , //Разница между частотами букв в тексте и в языке

freq[32]; //Массив для подсчета частот вхождения букв в текст для каждой буквы

double frequency[32]={0.074438, 0.016189, 0.050396, 0.019352, //А Б В Г

0.028179, 0.089613, 0.010010, 0.016637, //Д Е Ж З

0.074109, 0.014743, 0.032171, 0.037507, //И Й К Л

0.031160, 0.067640, 0.113329, 0.026275, //М Н О П

0.049378, 0.056569, 0.063209, 0.023785, //Р С Т У

0.001466, 0.009276, 0.004299, 0.014236, //Ф Х Ц Ч

0.006525, 0.004035, 0.000240, 0.017820, //Ш Щ Ъ Ы

0.016222, 0.004256, 0.007210, 0.019724}; //Ь Э Ю Я

char b;

Form1->Label2->Caption="" ;

if(Form1->Edit1->Text!="")

{

sdvig=StrToInt(Form1->Edit1->Text);

if(sdvig>32)

sdvig%=32;

}

else

{

/*--------------Подсчет общего количества букв в тексте-------------------*/

ifstream tempfile(TmpFName);

while(!tempfile.eof())

{

b=0;

tempfile.get(b) ;

if(b>=-64&&b<=-1||b==-88) counter++;

}

tempfile.close();

/*-----------------Обнуление счётчика частот------------------------------*/

for(j=0;j<32;j++)

freq[j]=0;

/*-------Цикл нахождения сдвига по частотам букв для каждого сдвига----*/

for(i=0;i<32;i++)

{

ifstream tempfile(TmpFName);

while(!tempfile.eof())

{

tempfile.get(b) ;

b-=i;

if(b<-64) b+=64;

/*----------Большие буквы-------------*/

if(b>=-64&&b<=-33)

freq[b+64]++;

/*----------Маленькие буквы----------*/

if(b>=-32&&b<=-1)

freq[b+32]++;

}

tempfile.close();

/*----Нахождение разницы между частотами букв текста и букв алфавита---*/

for(j=0;j<32;j++)

{

if (counter!=0)

freq[j]/=counter;

delta+=fabs(frequency[j]-freq[j]);

freq[j]=0;

}

/*----запоминание минимальной разницы частот и размера сдвига ------*/

if(delta<mindelta)

{

mindelta=delta;

sdvig=i;

}

delta=0;

}

}

return sdvig;

}

ПРИЛОЖЕНИЕ Б

Контрольные примеры

1) Выбран режим «Шифрование», значение ключа = 7

Рисунок Б.1 - Работа программы в первом режиме.

2) Выбран режим «Дешифрование», значение найденного ключа = 7

Рисунок Б.2 - Работа программы в первом режиме.

3) В случае, когда ключ введен некорректно появляется сообщение об ошибке



Рисунок Б.3 - случай некорректного ввода ключа