Текст книги "Программирование в Delphi. Трюки и эффекты"

Транспозиция

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

Таким образом, для d = 5 в качестве перестановки можно взять ключ 23154. Его использование будет означать, что m₁m₂m₃m₄m₅m₆m₇m₈m₉m₁₀… переходит в m₂m₃m₁m₅m₄m₇m₈m₆m₁₀m₉… Последовательное применение двух или более транспозиций будет называться составной транспозицией. Если периоды последовательно применяемых транспозиций d₁, …, d_s, то в результате получится составная транспозиция периода d, где d – наименьшее общее кратное d₁, …, d_s.

Теперь, ознакомившись с теорией, можно переходить к рассмотрению примера одной из возможных реализаций данного шифра. Для этого, как и в предыдущем случае, создадим новое приложение, а на форму поместим те же самые компоненты, за исключением редактора значений и кнопки генерации перестановки. Вместо них используем текстовое поле класса TEdit и еще один компонент класса TLabel с соответствующими именами edRearrangement и lbRearrangement. В результате должно будет получиться приложение, подобное изображенному на рис. 12.3.

Рис. 12.3. Интерфейс программы «Транспозиция с фиксированным периодом»

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

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

Теперь перейдем к рассмотрению исходного кода приложения. Как и в прошлый раз, сначала объявим класс необходимых типов, а также класс формы. Соответствующий программный код показан в листинге 12.9. Здесь была введена целочисленная константа, ограничивающая длину задаваемого периода. В данном случае она равна 100. Также, поскольку необходимо помнить саму перестановку, с помощью которой будет осуществляться транспозиция сообщения, был добавлен соответствующий тип.

Листинг 12.9. Объявление типов и класса формы

const

MaxTerm = 100;

type

TRearrangement = array [0..MaxTerm] of Integer;

TfmTransposition = class(TForm)

mmDecryptMessage: TMemo;

mmEncryptMessage: TMemo;

lbDecryptMessage: TLabel;

lbEncryptMessage: TLabel;

lbRearrangement: TLabel;

edRearrangement: TEdit;

btnEncryptMessage: TButton;

btnDecpyptMessage: TButton;

procedure btnEncryptMessageClick(Sender: TObject);

procedure btnDecpyptMessageClick(Sender: TObject);

private

{Private declarations}

Rear: TRearrangement;

function RecalcRearrangement(nKey: Integer): Boolean;

function GetLine(Lines: TStrings; nRow, nInd: Integer): String;

procedure EncryptDecrypt(SrcLines, DstLines: TStrings; nKey: Integer);

public

{Publicccdeclarationss}

end;

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

Функция RecalcRearrangement подготавливает перестановку требуемым образом для шифрования либо дешифрования в зависимости от значения параметра nKey, который может быть равно 0 или 1. Значение 0 указывает на то, что будет производиться шифрование сообщения и дополнительных действий по подготовке перестановки, за исключением проверки ее корректности, не требуется. Значение 1, напротив, указывает на то, что будет производиться дешифрование сообщения и требуется дополнительно преобразовать перестановку так, чтобы она была симметрична исходной – в этом случае процесс дешифрования ничем не будет отличаться от процесса шифрования.

Чтобы введенная перестановка считалось корректной, необходимо и достаточно, чтобы выполнялись следующие требования:

• были введены только числа через пробел;

• числа не повторялись;

• числа находились в диапазоне от одного до их общего количества.

Проверка первого условия осуществляется следующим образом. Изначально считается, что строка состоит из пробелов. Как только пробелы заканчиваются, предполагается, что началось число, и оно выделяется до следующего пробела. Как только встретится пробел, будет произведена попытка преобразовать выделенную часть из строкового представления в численное, после чего полученное число добавлено к итоговой перестановке. Когда фрагмент кода, в котором находится первый цикл с условием после него, отработает, в массиве Rear будет сохранена введенная перестановка (в массиве Rear [0] хранится количество чисел в полученной перестановке). Сразу за первой проверкой осуществляется совместно вторая и третья, то есть проверяется допустимость самих введенных чисел, а также их уникальность. После всех проверок при необходимости осуществляется преобразование исходной перестановки к симметричной.

Для получения симметричной перестановки необходимо выполнить нехитрое действие по обмену местами индексов чисел и самих чисел, то есть если имеется перестановка 312, то она преобразуется в 231, так как 1 стоит на втором месте, 2 – на третьем, а 3 – на первом.

Исходный код выполняющей эти действия функции приведен в листинге 12.10.

Листинг 12.10. Функция разбора строки и проверки допустимости перестановки

function TfmTransposition.RecalcRearrangement(nKey: Integer): Boolean;

var

i: Integer;

s: String;

Space: Boolean;

Used: array [1..MaxTerm] of Boolean;

ExRear: TRearrangement;

begin

Result:= False;

Rear[0]:= 0;

Space:= True;

//выделяем каждое слово, разделенное пробелом,

//и преобразовываем его к числу

for i:= 1 to Length(edRearrangement.Text) do

if (edRearrangement.Text[i] = '') and (not Space) then

begin

Inc(Rear[0]);

Rear[Rear[0]]:= StrToInt(s);

Space:= True;

end

else

if (edRearrangement.Text[i] <> '') then

begin

if Space then

begin

Space:= False;

s:= '';

end;

s:= s + edRearrangement.Text[i];

end;

if not Space then

begin

Inc(Rear[0]);

Rear[Rear[0]]:= StrToInt(s);

end;

//проверяем допустимость полученных чисел

FillChar(Used, SizeOf(Used), False);

for i:= 1 to Rear[0] do

if (0 < Rear[i]) and (Rear[i] <= Rear[0]) and not Used[Rear[i]] then

Used[Rear[i]]:= True

else

Exit;

//преобразуем перестановку к шифровке, обратной

//для симметричности процесса дешифровки шифровке

if nKey = 1 then

begin

ExRear[0]:= Rear[0];

for i:= 1 to Rear[0] do

ExRear[Rear[i]]:= i;

Rear:= ExRear;

end;

Result:= Rear[0] > 1;

end;

Кроме того, для упрощения алгоритма шифрования необходимо уметь получать часть текста заданной длины, начиная с указанной позиции, в виде одной строки, пропуская все переводы строк. Это действие выполняет следующая описываемая функция. Алгоритм ее работы довольно прост. Изначально результирующая строка не содержит ни единого символа. Далее осуществляется двойной вложенный цикл. Цикл верхнего уровня осуществляет изменение значения переменной, начиная с указанной строки и заканчивая самой последней. Вложенный цикл, в свою очередь, изменяет значение переменной, первый раз начиная с указанной в строке позиции, а в остальных случаях всегда с единицы, и заканчивая последней позицией текущей обрабатываемой строки. Каждый очередной символ добавляется к результирующей строке до тех пор, пока не будет достигнута заданная длина строки, равная периоду транспозиции. Соответствующий код приведен в листинге 12.11.

Листинг 12.11. Функция получения части текста заданной длины, начиная с указанной позиции, в виде одной строки

function TfmTransposition.GetLine(Lines: TStrings; nRow, nInd: Integer): String;

var

i, j, k: Integer;

s: String;

begin

Result:= '';

s:= '';

k:= nInd;

for i:= nRow to Lines.Count – 1 do

begin

for j:= k to Length(Lines[i]) do

begin

s:= s + Lines[i][j];

if Length(s) = Rear[0] then

begin

Result:= s;

Exit;

end;

end;

kk k:= 1;

end;

end;

Подготовительный этап рассмотрен. Теперь остается рассмотреть основной код программы. Обработчики кнопок OnClick вызывают один и тот же метод и указывают необходимые параметры, чтобы зашифровать либо дешифровать текст сообщения. Процедура EncryptDecrypt в качестве параметров принимает источник текста сообщения, с которым нужно проделать необходимые действия, приемник преобразованного текста сообщения и тип преобразования. Последний параметр принимает одно из двух значений: 0 или 1. Значение 0 указывает на то, что будет производиться шифрование сообщения. Значение 1 указывает на то, что будет производиться дешифрование сообщения. Процедура EncryptDecrypt выполняет следующие действия. Сначала она пытается подготовить необходимую перестановку и, только если все прошло успешно, переходит к попытке преобразования текста сообщения, предварительно выполнив еще одну проверку. Эта проверка заключается в том, чтобы удостовериться в соответствии общей длины текста накладываемому на нее ограничению, то есть длина обязательно должна быть кратна периоду транспозиции. Если проверка выполнена успешно, далее следует код преобразования текста сообщения с использованием подготовленной транспозиции. В листинге 12.12 приведен исходный код.

Листинг 12.12. Шифрование и дешифрование текста сообщения

procedure TfmTransposition.btnEncryptMessageClick(Sender: TObject);

begin

EncryptDecrypt(mmDecryptMessage.Lines, mmEncryptMessage.Lines, 0);

end;

procedure TfmTransposition.btnDecpyptMessageClick(Sender: TObject);

begin

EncryptDecrypt(mmEncryptMessage.Lines, mmDecryptMessage.Lines, 1);

end;

procedure TfmTransposition.EncryptDecrypt(SrcLines, DstLines:

TStrings; nKey: Integer);

var

i, j, Cnt: Integer;

s, EncryptMsg: String;

begin

if RecalcRearrangement(nKey) then

begin

//вычисляем общую длину текста

Cnt:= 0;

for i:= 0 to SrcLines.Count – 1 do

Inc(Cnt, Length(SrcLines[i]));

//проверяем кратность общей длины длине перестановки

if Cnt mod Rear[0] <> 0 then

begin

MessageDlg('Ошибка: текст сообщения не кратен длине

перестановки', mtError, [mbOk], 0);

Exit;

end;

//преобразовываем сообщение

Cnt:= Rear[0];

DstLines.BeginUpdate;

DstLines.Clear;

for i:= 0 to SrcLines.Count – 1 do

begin

EncryptMsg:= '';

for j:= 1 to Length(SrcLines[i]) do

begin

if Cnt = Rear[0] then

begin

s:= GetLine(SrcLines, i, j);

Cnt:= 0;

end;

Inc(Cnt);

EncryptMsg:= EncryptMsg + s[Rear[Cnt]];

end;

DstLines.Add(EncryptMsg);

end;

DstLines.EndUpdate;

end

else

MessageDlg('Ошибка: перестановка задана неверно', mtError,

[mbOk], 0);

end;

Здесь переменная Cnt отвечает за то, какая часть очередной группы букв уже обработана. Если эта часть равна количеству чисел в перестановке, то происходит переход к очередной группе букв сообщения. Алгоритм преобразования усложняется тем, что строки текста необязательно кратны количеству чисел в перестановке. Поэтому для удобства добавлена функция GetLine, получающая часть сообщения, начиная с указанной позиции, в виде одной строки определенной длины, которая при необходимости «склеивается» из нескольких идущих подряд строк. Теперь ничего не мешает заменить очередную букву сообщения соответствующей буквой из полученной строки. Результат работы приложения показан на рис. 12.4.

Рис. 12.4. Результат работы приложения «Транспозиция с фиксированным периодом»

Шифр Виженера и его варианты

Ключ в шифре Виженера задается набором из n букв. Такие наборы подписываются с повторением под текстом сообщения, и полученные две последовательности складываются по модулю m, где m – количество букв в рассматриваемом алфавите (например, для русского алфавита каждая буква нумеруется от 0 (А) до 32 (Я) и m = 33). В результате получается правило преобразования открытого текста l_i = x_i + y_i (mod m), где x_i – буква в открытом тексте с номером i, y_i – буква ключа, полученная сокращением числа i по модулю n. В табл. 12.1 приведен пример использования ключа ПБЕ.

Таблица 12.1. Шифр Виженера с ключом ПБЕ

Шифр Виженера с периодом 1 называется шифром Цезаря. По сути, он представляет собой простую подстановку, в которой каждая буква некоторого сообщения M сдвигается циклически вперед на фиксированное количество знаков по алфавиту. Именно это количество является ключом. Оно может принимать любое значение в диапазоне от 0 до m – 1. Повторное применение двух или более шифров Виженера называется составным шифром Виженера. Он имеет уравнение l_i = x_i + y_i + … + z_i (mod m), где x_i + y_i + … + z_i имеют различные периоды. Период их суммы, как и в составной транспозиции, составляет наименьшее общее кратное отдельных периодов.

Если используется шифр Виженера с неограниченным неповторяющимся ключом, то получается шифр Вернама, в котором l_i = x_i + y_i (mod m) и y_i выбираются случайно и независимо среди чисел 0, 1, …, m – 1. Если ключом служит текст, имеющий смысл, то получается шифр «бегущего ключа».

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

Рис. 12.5. Интерфейс приложения «Шифр Цезаря»

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

Перейдем к рассмотрению исходного кода программы. Объявление необходимых типов, описание классов и переменных приведено в листинге 12.13.

Листинг 12.13. Объявление типов и класса формы

type

//исходный алфавит русского языка

TRusSrcAlphabet = array [0..65] of Char;

//сопоставление букв алфавита открытого текста и зашифрованного

TRusDstAlphabet = array [Char] of Char;

TfmCryptography = class(TForm)

mmDecryptMessage: TMemo;

mmEncryptMessage: TMemo;

lbDecryptMessage: TLabel;

lbEncryptMessage: TLabel;

btnEncryptMessage: TButton;

btnDecpyptMessage: TButton;

edKey: TEdit;

lbKey: TLabel;

procedure btnEncryptMessageClick(Sender: TObject);

procedure btnDecpyptMessageClick(Sender: TObject);

private

{Private declarations}

RusDstAlphabet: TRusDstAlphabet;

function GetKey: Integer;

procedure RecalcAlphabet(nKey: Integer);

function EncryptDecryptString(strMsg: String; nKey: Integer): String;

public

{Public declarations}

end;

var

RusSrcAlph abet: TRusSrcAlph abet = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'+

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

fmCryptography: TfmCryptography;

Далее приведено описание работы методов, которые решают определенные подзадачи, возникающие в процессе решения основной задачи. Начнем рассмотрение с функции получения введенного пользователем ключа. Ее работа заключается в следующем. Сначала текстовое представление ключа преобразуется в численное. Затем проверяется, успешно ли прошло преобразование. Если проверка выполнена успешно, то возвращается полученное значение. В противном случае функция возвращает значение -1, что свидетельствует о некорректном вводе пользователем ключа. Исходный код данной функции приведен в листинге 12.14.

Листинг 12.14. Функция получения ключа

function TfmCryptography.GetKey: Integer;

var

key, code: Integer;

begin

Result:= –1;

//получаем текст элемента управления текстовая строка

Val(edKey.Text, key, code);

//ошибка во время преобразования к целому числу?

//или ключ имеет отрицательное значение?

if (code = 0) and (0 < key) then

Result:= key;

end;

Процедура RecalcAlphabet имеет один параметр nKey, который может принимать любое целое значение. Он показывает, на сколько необходимо сдвинуть алфавит циклически вперед, то есть, если имеется алфавит АБВГД, а nKey = 3, результатом будет ВГДАБ. Первым делом алфавит соответствия заполняется один к одному, то есть каждый символ соответствует сам себе. После этого нужно пройти циклом по строке, содержащей весь необходимый алфавит, подлежащий сдвигу, и переназначить соответствия для этих букв на смещенные (листинг 12.15).

Листинг 12.15. Функция пересчета алфавита преобразования

procedure TfmCryptography.RecalcAlphabet(nKey: Integer);

var

Ch: Char;

i: Integer;

LetCnt: Integer;

begin

//предварительно все символы в алфавите шифрования

//соответствуют символам из незашифрованного алфавита

for Ch:= Low(RusDstAlphabet) to High(RusDstAlphabet) do

RusDstAlphabet[Ch]:= Ch;

//количество символов в алфавите

LetCnt:= SizeOf(TRusSrcAlphabet);

//смещаем эталонный алфавит циклически влево на значение,

//заданное ключом nKey

for i:= 0 to LetCnt – 1 do

RusDstAlphabet[RusSrcAlphabet[(i – – nKey + LetCnt) mod LetCnt]]:=

RusSrcAlphabet[i];

end;

Процедура RecalcAlphabet производит необходимую подготовку перед шифрованием или дешифрованием. Ее результаты используются в функции EncryptDecryptString, где каждая буква открытого текста заменяется соответствующей ей буквой из смещенного алфавита. Это преобразование осуществляется простым проходом по всей строке и выполнением операции замены символа соответствующим ему. Стоит заметить, что для дешифровки сообщения по заданному ключу вычисляется симметричный ему ключ. В результате процесс дешифровки текста сообщения ничем не отличается от процесса его шифровки (листинг 12.16).

Листинг 12.16. Шифрование и дешифрование строки

function TfmCryptography.EncryptDecryptString (strMsg: String;

nKey: Integer): String;

var

i: Integer;

begin

//каждый символ строки заменяется соответствующим символом

//алфавита шифрования

for i:= 1 to Length(strMsg) do

strMsg[i]:= RusDstAlphabet[strMsg[i]];

Result:= strMsg;

end;

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

Листинг 12.17. Шифрование и дешифрование текста сообщения

procedure TfmCryptography.btnEncryptMessageClick(Sender: TObject);

var

i: Integer;

nKey: Integer;

begin

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

nKey:= GetKey;

//ключ задан верно ?

if nKey = –1 then

Begin

MessageDlg('Ошибка: ключ задан неверно', mtError, [mbOk], 0);

Exit;

End;

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

RecalcAlphabet(nKey);

//предотвращаем перерисовку компонента до тех пор, пока не

//зашифруем все строки сообщения

mmEncryptMessage.Lines.BeginUpdate;

//освобождаем список от любых старых значений

mmEncryptMessage.Clear;

//шифруем сообщение построчно

for i:= 0 to mmDecryptMessage.Lines.Count – 1 do

mmEncryptMessage.Lines.Add(

EncryptDecryptString(mmDecryptMessage.Lines[i], nKey));

//заново разрешаем перерисовку компонента

mmEncryptMessage.Lines.EndUpdate;

end;

procedure TfmCryptography.btnDecpyptMessageClick(Sender: TObject);

var

i: Integer;

nKey: Integer;

begin

nKey:= GetKey;

if nKey = –1 then

Begin

MessageDlg('Ошибка: ключ задан неверно', mtError, [mbOk], 0);

Exit;

End;

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

RecalcAlphabet(SizeOf(TRusSrcAlphabet) – nKey mod SizeOf(TRusSrcAlphabet));

mmDecryptMessage.Lines.BeginUpdate;

mmDecryptMessage.Clear;

for i:= 0 to mmEncryptMessage.Lines.Count – 1 do

mmDecryptMessage.Lines.Add(

EncryptDecryptString(mmEncryptMessage.Lines[i], nKey));

mmDecryptMessage.Lines.EndUpdate;

end;

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

Рис. 12.6. Результат работы приложения «Шифр Цезаря»