Создание программы шифрования –расшифрования.
В процессе работы над проектом были написаны три программы на языке Паскаль, каждая из которых осуществляла шифрование и расшифрование задаваемого текста одним из наиболее древних способов:
1. Методом Цезаря, т.е. простой моноалфавитной заменой;
2. Методом Цезаря с постоянным сдвигом, т.е. полиалфавитной заменой с циклическим перебором алфавитов;
3. Методом Вижинера, т.е. полиалфавитной заменой с перебором алфавитов по ключевому слову.
Выбор языка Паскаль обусловлен его простотой и изучаемостью в Гимназии.
Общие части программ.
Во всех программах для простоты использовались одинаковые или похожие куски кода для организации интерфейса в режиме командной строки, задания исходных данных для работы и вывода результата.
Исходная строка текста P обрабатывается побуквенно. Номер обрабатываемой буквы во фразе хранится в переменной i, количество букв во фразе – m. Его легко можно определить при помощи функции нахождения длинны строки m:=Length(p); а перебор всех букв во фразе организовать оператом цикла For i:=1 to m do (блок команд);
Где под «блоком команд» понимаются действия программы по шифрованию или расшифрованию заданной фразы побуквенно.
Поскольку в шифрах Цезаря и Вижинера шифрование – это положительный сдвиг (по часовой стрелке), а расшифрование – отрицательный (против часовой стрелки) поворотного диска шифровального диска (смотри рисунок шифровального диска Конфедерации на странице 10), то при задании программе режима шифрования используется переменная Z. Это – множитель величины сдвига алфавита, определяющий его направление. Он задаётся равным «1» при шифровании и «‑1» при расшифровании.
В большинстве случаев при шифровании выкидываются пробелы, чтобы не давать противнику априорной информации о длине зашифрованного слова. В некоторых случаях пробелы и знаки препинания заменяются на особые комбинации символов. Например, немецкие шифровальщики времён Второй Мировой войны заменяли пробелы на XX, запятые на YY, а точки на ZZ. В моих программах пробелы выкидываются и фраза шифруется без пробелов. Правда и все прочие символы, отличные от русских букв тоже, но на моём уровне знаний программирования и этого достаточно. Сами буквы русского алфавита (традиционно считаем, что их 32, поскольку Ё меняем на Е) преобразуются программой перед обработкой к «верхнему» регистру, то есть пишутся прописными. Это объясняется ещё и тем, что для компьютера код буквы, который он хранит в памяти, разный для прописных и строчных букв. То есть «А» не равно «а» и это затрудняет процесс шифрования старинными м етодами на компьютере. Значит, считаем длину алфавита равной 32 прописные буквы, о чём и объявляем в начале программы Const N=32.
Далее задаём две строки с одинаковым набором букв алфавита, но в одной они маленькие (строка LC – low case), в другой – большие (строка UC – upper case). Во всех трёх программах есть кусок кода, который заменяет в исходной фразе Р маленькие буквы на большие:
For i:=1 to m do
if (Pos(p[i], lc) > 0) then
p[i]:=uc[Pos(p[i], lc)];
Writeln(p);
Волшебная функция Pos(p[i], lc) ищет место очередной i-той буквы из фразы Р в строке малых букв LC. Если её там не обнаружено, то функция POS выдаёт ноль. Значит этот символ – НЕ русская буква. Если функция POS нашла букву в строке LC, она выдаёт её номер в этой строке. А мы берём с этим номером букву из другой строки – из UC. Там на том же месте стоит такая же, но большая буква, которая и запишется вместо маленькой в нашу обрабатываемую фразу. И по окончании этого цикла все буквы в строке Р заменятся на большие!
При программировании алгоритма шифрования и расшифрования тоже используется определение места буквы в алфавите. Однако здесь я использую другой метод. Я прочитала на Википедии, что компьютерные коды всех символов представляют собой обычные натуральные числа от 0 до 255 и сводятся в так называемые «таблицы кодировки», где первые 128 символов кодируются одинаково для всех стран (это латиница, знаки препинания и цифры), а последние от 129 до 255 кодируются по-разному для разных языков. Это символы национальных алфавитов. В русскоязычной таблице кодировки Windows-1251, с которой работает использованная мной в проекте среда программирования Pascal-ABC, все большие русские буквы идут по порядку с номера 192. Однако существуют и другие таблицы кодировки русских букв и в них русские буквы начинаются с других номеров. Например в кодировке CP-866 русский алфавит начинается со 128 номера.
Поэтому я ввела в свои программы «точку отсчёта» ‑ номер русской буквы «А» в используемой кодировке. Он хранится в переменной B и определяется волшебной функцией ORD('A'):
b:=ord('А');
Противоположная ей функция CHR(х) наоборот используется для печати на экран буквы с порядковым номером Х в таблице кодировки.
В результате я:
- Узнала много интересного о способах кодировки символов на компьютере;
- Освоила две дополнительных функции языка Паскаль;
- Сделала программу независимой от используемой таблицы кодировки.
Во всех трёх программах я ввела проверку
if (ord(p[i]) >= b) And (ord(p[i]) < b+N) then
которая определяет по номеру в таблице кодировки, попадает ли обрабатываемая буква нашей фразу в диапазон русских букв от номера B до номера B+N (от «А» до «Я»).
В результате в зашифрованной фразе, увы, выкидываются все цифры, пробелы, знаки препинания и латинские буквы.
Однако восстановить пробелы можно из контекста, а вместо знаков препинания можно использовать сокращения ЗПТ или ТЧК, как в телеграфных сообщениях.
Результатом работы всех трёх программ будет вывод на экран зашифрованной фразы:
Write(chr(b+ «номер шифросимвола»));
Особенностью каждой программы как раз и будет расчёт этого «номера шифросимвола». То есть определение номера в русском алфавите шифруемой буквы и прибавление, с цчётом «закольцованности» алфавита, к неиу величины сдвига шифрования.
Программа «Цезарь».
Для шифра Цезаря этот сдвиг всегда постоянен и равен начально заданному сдвигу S.
Поскольку сдвиг циклический, то есть алфавит «свёрнут» в кольцо, где за «Я» идёт опять «А», то сдвиг равен остатку от деления на размер алфавита N=32. Такие операции в математике называют «операциями по модулю N» и на Паскале записываются как:
(ord(p[i])-b) + s) mod N
Здесь ord(p[i])-b находит по таблице кодировки номер в алфавите i-го символа из фразы P.
Пусть, например, p[i] ‑ это буква «Г». Для таблицы кодировки СP-866 b=128,
Тогда ord(«Г»)=131. Вычислим их разницу ord(«Г»)-b=131-128=3. Это номер буквы «Г» в алфавите. Заодно замечу, что у нас для правильности вычислений нумерация букв в алфавите идёт с нуля до 31!
Пусть сдвиг S=4. Тогда зашифрованная буква вычисляется
(ord(p[i])-b) + s) mod N =(131-128 +4) mod 32= 7 mod 32 =7
Теперь обратный процесс: нужно напечатать на экране эту букву:
Write(chr(b+ «номер шифросимвола»)); где «номер шифросимвола» равен 7.
chr(128+ 7)= chr(135)='З' – На экране появится буква «З».
Если же мы шифруем с тем же сдвигом букву «Ю», то
ORD('Ю')=158
(ord(p[i])-b) + s) mod N = (158 - 128 + 4) mod 32 = 34 mod 32 = 2
chr(b+ «номер шифросимвола»)= chr(128+ 2)= chr(130)='B'
То есть видно, сложение по модулю 32 позволяет успешно работать «на границе» алфавита, имитировать его «закольцованность».
При расшифровке надо делать сдвиг в другую строну. Поэтому в формуле появляется параметр направдения сдвига Z, который равен либо 1, либо ‑1. Номер символа тогда вычисляется по формуле (ord(p[i])-b) + z*s) mod N.
Однако при расшифровнии, когда сдвиг отрицателен функция mod N не сработает правильно, как выясняется на практике. При отрицательном сдвиге может получиться отрицательное число, знак которого mod N не меняет. И в итоге на экране появится символ, стоящий в таблице кодировке ДО начала букв русского алфавита. Это можно исправить, всегда добавляя N к получившемуся номеру буквы.
Операции по модулю N будут давать одинаковый результат, если сдвиг внутри кольца кратен размеру кольца, как часы показывают одно и то же время каждые 12 часов подряд.
X mod N = (X + K*N) mod N, где К – натуральное чсисло.
Действительно, если мы получили сдвиг 7, то 7 mod 32 = (7+32) mod 32 = 39 mod 32 = 7
В случае же отрицательного сдвига, например -3, получим (-3+32) mod 32 = 29 mod 32=29
То есть снова мы попадаем на букву внутри «кольца» алфавита и не выходим за его пределы. В итоге на экран будет выводится символ, который определится по формуле:
chr(b+((ord(p[i])-b)+z*s+N) mod N)
Метод Цезаря с постоянным сдвигом.
В этом случае мы каждую букву фразы шифруем своим адфавитом. Но эти алфавиты перебираются нами по порядку. То есть мы сдвигаем номер буквы в алфавите на сумму постоянного начального сдвига и номера буквы во фразе (s+i). Всё остальное – как в предыдущем случае. Получаем формулу определения замены:
chr(b+((ord(p[i])-b)+z*(s+(i-1) mod N)+N) mod N)
Номер буквы во фразе тоже берем с нуля и тоже с учётом закольцованности всех вычислений, поэтому (i-1) mod N
Метод Вижинера.
Здесь мы вводим ещё ключевую фразу К, которую так же, как и саму шифруемую фразу Р, мы преобразуем в большие буквы, после чего запоминаем в переменную К2.
Теперь сдвиг состоит только из номера в алфавите очередной буквы в ключевой фразе. Его мы также вычисляем по формуле ord(k2[j])-b где j – порядковый номер буквы в ключевой фразе. Подробно метод Вижинера описан на странице 8.
В итоге буква определяется по формуле:
chr(b+((ord(p[i])-b)+z*(ord(k2[j])-b)+N) mod N)
Все три программы работают, шифруют и расшифровывают и использовались мной в работе над последней частью проекта.
Тексты программ.
Program Cezar_codec;
Label eop;
Const N=32;
lc: string = 'йцукенгшщзхъфывапролджэячсмитьбюёЁ';
uc: string = 'ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЕЕ';
Var i, s, b, m: byte;
p, w: string;
z: shortint;
begin
s:=0; {сдвиг алфавита}
m:=0; {длина фразы}
z:=1; {направление сдвига}
b:=ord('А'); {начальная позиция русского алфавита в общей таблице символов}
Write('Выбор действия (1-шифруем, 2-расшифровываем):');
Readln(i);
case i of
1: begin w:='Ш'; z:=1; end;
2: begin w:='Расш'; z:=-1; end
else goto eop
end;
Writeln(w+'ифрование моноалфавитной заменой');
For i:=1 to 2*N do Write('=');
writeln;
Write('Введите число - ключ шифра (сдвиг алфавита):');
Readln(s);
s:=s mod N; {защита от дурака}
Write('Введите свою фразу для '+w+'ифрования:');
Readln(p);
m:=Length(p);
if (m=0) then Writeln('Нечего '+w+'ифровать - строка пустая!')
else
begin
{Преобразуем все буквы в прописные}
For i:=1 to m do
if (Pos(p[i],lc) > 0) then
p[i]:=uc[Pos(p[i],lc)];
Writeln(p);
Write(w+'ифрованый текст: ');
For i:=1 to m do
if (ord(p[i]) >= b) And (ord(p[i]) < b+N) then
Write(chr(b+((ord(p[i])-b)+z*s+N) mod N));
writeln;
end;
eop:
Writeln('Конец работы!');
end.
Program Cezar_codec;
Label eop;
Const N=32;
lc: string = 'йцукенгшщзхъфывапролджэячсмитьбюёЁ';
uc: string = 'ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЕЕ';
Var i, s, b, m: byte;
p, w: string;
z: shortint;
begin
s:=0; {сдвиг алфавита}
m:=0; {длина фразы}
z:=1; {направление сдвига}
b:=ord('А'); {начальная позиция русского алфавита в общей таблице символов}
Write('Выбор действия (1-шифруем, 2-расшифровываем):');
Readln(i);
case i of
1: begin w:='Ш'; z:=1; end;
2: begin w:='Расш'; z:=-1; end
else goto eop
end;
Writeln(w+'ифрование полиалфавитной заменой с постоянным сдвигом');
For i:=1 to 2*N do Write('=');
writeln;
Write('Введите число - ключ шифра (начальный сдвиг алфавита):');
Readln(s);
s:=s mod N; {защита от дурака}
Write('Введите свою фразу для '+w+'ифрования:');
Readln(p);
m:=Length(p);
if (m=0) then Writeln('Нечего '+w+'ифровать - строка пустая!')
else
begin
{Преобразуем все буквы в прописные}
For i:=1 to m do
if (Pos(p[i],lc) > 0) then
p[i]:=uc[Pos(p[i],lc)];
Writeln(p);
Write(w+'ифрованый текст: ');
For i:=1 to m do
if (ord(p[i]) >= b) And (ord(p[i]) < b+N) then
Write(chr(b+((ord(p[i])-b)+z*(s+(i-1) mod N)+N) mod N));
writeln;
end;
eop:
Writeln('Конец работы!');
end.
Program Cezar_codec;
Label eop;
Const N=32;
lc: string = 'йцукенгшщзхъфывапролджэячсмитьбюёЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЕЁ';
uc: string = 'ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЕЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЕЕ';
Var i, j, b, m, dk: byte;
p, w, k, k2: string;
z: shortint;
begin
dk:=0; {длина ключа}
m:=0; {длина фразы}
z:=1; {направление сдвига}
b:=ord('А'); {начальная позиция русского алфавита в общей таблице символов}
Write('Выбор действия (1-шифруем, 2-расшифровываем):');
Readln(i);
case i of
1: begin w:='Ш'; z:=1; end;
2: begin w:='Расш'; z:=-1; end
else goto eop
end;
Writeln(w+'ифрование полиалфавитной заменой Вижинера');
For i:=1 to 2*N do Write('=');
writeln;
Write('Введите слово - ключ шифра (сдвиг алфавита):');
Readln(k);
dk:=Length(k);
k2:='';
For i:=1 to dk do
if (Pos(k[i],lc) > 0) then
k2:=k2+uc[Pos(k[i],lc)];
Writeln(k2);
dk:=Length(k2);
Write('Введите свою фразу для '+w+'ифрования:');
Readln(p);
m:=Length(p);
if (m=0) then Writeln('Нечего '+w+'ифровать - строка пустая!')
else
begin
{Преобразуем все буквы в прописные}
For i:=1 to m do
if (Pos(p[i],lc) > 0) then
p[i]:=uc[Pos(p[i],lc)];
Writeln(p);
Write(w+'ифрованый текст: ');
j:=1;
For i:=1 to m do
if (ord(p[i]) >= b) And (ord(p[i]) < b+N) then
begin
Write(chr(b+((ord(p[i])-b)+z*(ord(k2[j])-b)+N) mod N));
j:=(j mod dk) + 1;
end;
writeln;
end;
eop:
Writeln('Конец работы!');
end.