Лабораторная работа № 1

Тема: Простейшие шифры замены

Цель работы: Изучить алгоритмы простейших шифров замены

Теоретические сведения: Наиболее известными и часто используемыми шифрами являются шифры замены. Они характеризуются тем, что отдельные части сообщения (буквы, слова) заменяются на какие-либо другие буквы, числа, символы и т.д. При этом замена осуществляется так, чтобы потом по шифрованному сообщению можно было однозначно восстановить передаваемое сообщение.

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

Таблица 1– Шифрообозначения

а	б	в	…	я
			…

является ключом шифра замены. Зная ее, можно осуществить как зашифрование, так и расшифрование.

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

Таблица 2 - Ключ

а

б

в

г

д

е

ж

з

и

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

то сообщение ``я знаком с шифрами замены'' может быть зашифровано, например, любым из следующих трех способов (таблица 3):

Таблица 3 - Зашифрованное сообщение

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

Часто состоит из одного элемента. Например, в романе Ж. Верна «Путешествие к центру Земли» в руки профессора Лиденброка попадает пергамент с рукописью из знаков рунического письма. Каждое множество состоит из одного элемента. Элемент каждого множества выбирается из набора символов вида

Рисунок 1- Символы рунического письма

В рассказе А. Конан Дойла «Пляшущие человечки» каждый символ изображает пляшущего человечка в самых различных позах

Рисунок ­2 – Пляшущие человечки

На первый взгляд кажется, что чем хитрее символы, тем труднее вскрыть сообщение, не имея ключа. Это, конечно, не так. Если каждому символу однозначно сопоставить какую-либо букву или число, то легко перейти к зашифрованному сообщению из букв или чисел. В романе Ж. Верна ``Путешествие к центру Земли'' каждый рунический знак был заменен на соответствующую букву немецкого языка, что облегчило восстановление открытого сообщения. С точки зрения криптографов использование различных сложных символов не усложняет шифра. Однако, если зашифрованное сообщение состоит из букв или цифр, то вскрывать такое сообщение удобнее.

Рассмотрим некоторые примеры шифров замены. Пусть каждое множество состоит из одной буквы. Пример 1:

Рисунок ­3 – Пример шифра замены

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

Запомнить произвольный порядок букв алфавита достаточно сложно. Поэтому всегда пытались придумать какое-либо правило, по которому можно просто восстановить вторую строчку в (1).

Одним из первых шифров, известных из истории, был так называемый шифр Цезаря, для которого вторая строка в (1) является последовательностью, записанной в алфавитном порядке, но начинающейся не с буквы а:

Рисунок ­4 – Шифр Цезаря

В одной из задач используется шифр Цезаря. Запомнить ключ в этом случае просто - надо знать первую букву второй строки (1) (последовательность букв в алфавите предполагается известной). Однако такой шифр обладает большим недостатком. Число различных ключей равно числу букв в алфавите. Перебрав эти варианты, можно однозначно восстановить открытое сообщение, так как при правильном выборе ключа получится ``осмысленный'' текст. В других случаях обычно получается «нечитаемый» текст.

Другим примером шифра замены может служить лозунговый шифр. Здесь запоминание ключевой последовательности основано на лозунге - легко запоминаемом слове. Например, выберем слово-лозунг ``учебник'' и заполним вторую строку таблицы по следующему правилу: сначала выписываем слово-лозунг, а затем выписываем в алфавитном порядке буквы алфавита, не вошедшие в слово-лозунг. Вторая строка в (1) примет вид

у ч е б н и к а в г д ж з л м о

п р с т ф х ц ш щ ъ ы ь э ю я

В данном случае число вариантов ключа существенно больше числа букв алфавита.

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

Кроме частоты появления букв, могут быть использованы другие обстоятельства, помогающие раскрыть сообщение. Например, может быть известна разбивка на слова и расставлены знаки препинания. Рассматривая небольшое число возможных вариантов замены для предлогов и союзов, можно попытаться определить часть ключа. В этой задаче существенно используется, какие гласные или согласные могут быть удвоенными: ``нн'', «ее», «ии» и др.

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

Вообще-то можно сказать, что вскрытие шифров замены является искусством и достаточно трудно формализовать этот процесс.

Популярные у студентов криптограммы по сути дела являются шифром замены с ключом (таблица 4)

Таблица 4- Шифр замены с ключом

ш	и	ф	р	з	а	м	е	н	ы

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

Шифрование даже относительно небольших текстов на одном ключе для рассмотренных шифров замены создает условия для вскрытия открытых сообщений. Поэтому такие шифры пытались усовершенствовать. Одно из направлений - построение шифров разнозначной замены, когда каждой букве ставится в соответствие один или два символа. Например (таблица 5):

Таблица 5 - Построение шифров равнозначной замены

а

б

в

г

д

е

ж

з

и

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

Если шифрованное сообщение написано без пробелов между символами, то появляется дополнительная трудность при разбиении шифрованного сообщения на отдельные символы и слова.

Другое направление создания шифров замены состоит в том, чтобы множества шифробозначений содержали более одного элемента. Такие шифры получили название шифров многозначной замены. Они позволяют скрыть истинную частоту букв открытого сообщения, что существенно затрудняет вскрытие этих шифров. Главная трудность, которая возникает при использовании таких шифров, заключается в запоминании ключа. Надо запомнить не одну строчку, а для каждой буквы алфавита - множество ее шифробозначений . Как правило, элементами множеств являются числа. Из художественной литературы и кинофильмов про разведчиков вам известно, что во время второй мировой войны часто использовались так называемые книжные шифры. Множество шифробозначений для каждой буквы определяется всеми пятизначными наборами цифр, в каждом из которых первые две цифры указывают номер страницы, третья цифра- номер строки, четвертая и пятая цифры - номер места данной буквы в указанной строке. Поэтому при поимке разведчика всегда пытались найти книгу, которая могла быть использована им в качестве ключа.

Реализация описанного алгоритма в среде Delphi показана в примере 2.

Пример 1:

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

const

key = '134567';

crname = 'crypt.txt';

dcrname = 'decrypt.txt';

type

TForm1 = class(TForm)

OpenDialog1: TOpenDialog;

Shifr: TButton;

Label1: TLabel;

Rasshif: TButton;

Label2: TLabel;

Label3: TLabel;

Memo1: TMemo;

Label4: TLabel;

Label5: TLabel;

procedure ShifrClick(Sender: TObject);

procedure RasshifClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure Crypt_Ko (FileName: TFileName);

var

f, f1: File of Char;

j: Integer;

i, i2: Char;

begin

AssignFile (f, FileName);

AssignFile (f1, crname);

Reset (f);

Rewrite (f1);

while not Eof(f) do

begin

Read (f, i);

j:= Ord(i) xor StrToInt(key);

i2:= Chr(j);

Write (f1, i2);

end;

CloseFile (f);

CloseFile (f1);

Form1.Label1.Caption:= 'Файл обработан';

end;

procedure Decrypt_Ko (FileName: TFileName);

var

f, f1: File of Char;

i, i2: Char;

begin

AssignFile (f, FileName);

AssignFile (f1, dcrname);

try

Reset (f);

Rewrite (f1);

finally

While not Eof(f) do

begin

Read (f, i);

i2:= Chr(Ord(i) xor StrToInt(key));

Write (f1, i2);

end;

CloseFile (f);

CloseFile (f1);

end;

end;

procedure TForm1.ShifrClick(Sender: TObject);

begin

OpenDialog1.Execute;

Crypt_Ko (OpenDialog1.FileName);

end;

procedure TForm1.RasshifClick(Sender: TObject);

begin

OpenDialog1.Execute;

DeCrypt_Ko (OpenDialog1.FileName);

end;

procedure TForm1.FormCreate(Sender: TObject);

var

f: File of Char;

k,k1,j,kol,kol1: Integer;

i: Char;

Filename: TFilename;

s1:array[0..20] of string;

s:WideString;

col:array[0..19] of integer;

begin

Filename:='Unit1.pas';

AssignFile (f, FileName);

k:=0;

try

Reset(f);

finally

While not Eof(f) do

begin

Read (f, i);

k1:= Ord(i);

k:=k+k1;

end;

CloseFile (f);

Label2.Caption:=IntToStr(k);

end;

begin

s1[0]:='*';

s1[1]:='/';

s1[2]:='+'; s1[3]:='-';s1[4]:='div';

s1[5]:='mod'; s1[6]:='not';s1[7]:='and';s1[8]:='or';

s1[9]:='xor';s1[10]:='>';s1[11]:='<';

s1[12]:=':=';s1[13]:='=';s1[14]:='<>';s1[15]:='>=';s1[16]:='<=';

s1[17]:='if';s1[18]:='case';

Memo1.Lines.LoadFromFile('Unit1.pas');

s:=Memo1.Text;

kol1:=0;

for j:=0 to 18 do

begin

kol:=0;

while pos(s1[j],s)<>0 do

begin

{if ((s[pos(s1,s)-1] in punct) and (s[pos(s1,s)+length(s1)] in punct)) or

((pos(s1,s)=1) and (s[pos(s1,s)+length(s1)] in punct)) then }

kol:=kol+1;

delete(s,pos(s1[j],s),length(s1[j]));

end;

col[j]:=kol;

kol1:=kol1+kol;

Label4.Caption:=inttostr(kol1);

end;

end;

end;

end.

Задание: Используя теоретические сведения и примеры, программно реализовать нижеописанный алгоритм, осуществляющий шифрование и дешифрование на любом (по выбору студента) языке программирования.