Текст книги "Delphi. Трюки и эффекты"

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

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

Таким образом, для d = 5 в качестве перестановки можно взять 23154. Это будет означать, что т1т2 тЗт4т5т6т7т8т9 тЮ… переходит в т2 тЗт1т5т4т7т8т6т10т9… Последовательное применение двух или более транспозиций будет называться составной транспозицией. Если периоды этих транспозиций d1…., ds, то, очевидно, в результате получится транспозиция периода d, где d – наименьшее общее кратное d1…., ds.

Теперь, зная определение данного шифра, можно перейти к примеру одной из возможных его реализаций. Для этого, как и в предыдущем случае, создадим новое приложение, а на форму поместим те же самые компоненты, за исключением редактора значений и кнопки для генерации перестановки. Вместо них используем следующие компоненты: текстовое поле класса TEdit и еще один компонент класса TLabel с соответствующими HMeHaMHedRearrangement и IbRearrangement. Когда вы закончите, то в результате должно получиться нечто подобное изображенному на рис. 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

{ Public declarations }

end;

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

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

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

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

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

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

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

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

Исходный код данной функции приведен в листинге 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;

Еще для упрощения алгоритма шифрования необходимо уметь получать часть текста заданной длины, начиная с указанной позиции, в виде одной строки, пропуская все переводы строк. Это действие выполняет следующая описываемая функция. Алгоритм ее работы довольно прост. Изначально в результирующей строке нет ни единого символа. Далее осуществляется двойной вложенный цикл. Цикл верхнего уровня осуществляет изменение значения переменной, начиная с указанной строки до самой последней. Вложенный цикл, в свою очередь, изменяет значение переменной, первый раз начиная с указанной позиции в строке, а в остальных случаях всегда с 1, до длины текущей обрабатываемой строки. Каждый очередной символ добавляется к результирующей строке до тех пор, пока не будет достигнута заданная длина строки, равная периоду транспозиции. Соответствующий код приведен в листинге 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;

k := 1;

end;

end;

Подготовительный этап мы рассмотрели, теперь остается рассмотреть основной код программы. Обработчики кнопок Onclick вызывают один и тот же метод и указывают необходимые параметры, чтобы зашифровать либо дешифровать текст сообщения. Процедура EncryptDecrypt в качестве параметров принимает источник текста сообщения, с которым нужно проделать необходимые действия, приемник преобразованного текста сообщения и тип преобразования. Последний параметр принимает одно из двух значений: 0 или 1. Значение О указывает на то, что будет производиться шифрование сообщения. Значение 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. Результат работы приложения «Т ранспозиция с фиксированным периодом»

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

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

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

Шифр Виженера с периодом 1 называется шифром Цезаря. По сути, он представляет собой простую подстановку, в которой каждая буква некоторого сообщения М сдвигается циклически вперед на фиксированное количество мест по алфавиту. Именно это количество является ключом. Оно может принимать любое значение в диапазоне от 0 до т – 1. Повторное применение двух или более шифров Виженера будет называться составным шифром Виженера. Он имеет уравненией = xi + yi +… + zi (modm), где xi + yi +… + zi имеют различные периоды. Период их суммы, как и в составной транспозиции, будет наименьшим общим кратным отдельных периодов.

Если используется шифр Виженера с неограниченным неповторяющимся ключом, то мы имеем шифр Вернама, в котором й = xi + yi (mod т) и yi выбираются случайно и независимо среди чисел 0, 1…., т – 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

RusSrcAlphabet: TRusSrcAlphabet =

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

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

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, который принимает любое целое значение. Он показывает, на сколько требуется сдвинуть алфавит циклически вперед, то есть если имеется алфавит АБВГД, а пКеу=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. Результат работы приложения «Шифр Цезаря»