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

Глава 12
Шифрование

• Основы криптографии

• Шифр простой подстановки

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

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

• Шифр с автоключом

• Взлом

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

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

• создание абсолютно надежного канала связи, к которому есть доступ только у отправителя и адресата;

• использование общедоступного канала связи, но скрытие самого факта передачи информации;

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

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

Второй способ является предметом изучения стеганографии. В область этой науки входит разработка средств и методов скрытия факта передачи сообщения.

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

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

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

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

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

Основы криптографии

Американский математик Клод Шеннон (Claude Elwood Shannon) написал работу «Теория связи в секретных системах», в которой обобщил накопленный до него опыт разработки шифров. В этой работе указано, что даже в самых очень сложных шифрах в качестве типичных компонентов можно выделить шифры замены и шифры перестановки или их сочетание.

Для начала рассмотрим эти шифры, а позже реализуем их. Начать стоит, пожалуй, с шифра замены, как с самого простого и наиболее популярного. Примерами самых распространенных из известных шифров замены могут служить шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конана Дойла. Из самого названия видно, что шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Математическое описание шифра замены можно дать следующим образом. Пусть X и Y – два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового количества символов. Пусть также g:X→Y – взаимнооднозначное отображение X в Y. Тогда шифр замены действует так: открытый текст x₁ x₂ …x_n преобразуется в шифрованный текст g(x₁)g(x₂)…g(x_n).

Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Примером одного из известных шифров перестановки может служить шифр «Сцитала». Обычно открытый текст разбивается на отрезки равной длины, и каждый отрезок шифруется независимо. Например, длина отрезков равна n и g — взаимнооднозначное отображение множества {1, 2, …, n} в себя. Тогда шифр перестановки действует следующим образом: отрезок открытого текста x₁ x₂ …x_n преобразуется в отрезок шифрованного текста. x_g(1) x_g(2) …x_g(n).

Наиболее важным для развития криптографии является вывод К. Шеннона о существовании и единственности абсолютно стойкого шифра. Единственным таким шифром является форма так называемой ленты однократного использования, в которой открытый текст «объединяется» с полностью случайным ключом такой же длины.

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

Стоит пояснить один очень важный момент по поводу единственного абсолютно стойкого шифра. Чтобы шифр являлся таковым, должны выполняться три условия:

• полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя выработать с помощью какого-либо детерминированного устройства);

• равенство длины ключа и длины открытого текста;

• однократность использования ключа.

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

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

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

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

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

У пользователя остается единственный путь – получение практических оценок стойкости. Этот путь включает следующие этапы.

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

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

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

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

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

Существует много их классификаций. Принципы классификации относятся не к качеству рассматриваемых криптосистем, а к присущим им свойствам.

Шифр простой подстановки

В шифре простой подстановки производится замена каждой буквы сообщения некоторым заранее определенным символом (обычно также буквой). В результате сообщение, имеющее вид M = m₁m₂m₃m₄ …, где m₁, m₂, … – последовательность букв, преобразуется в сообщение вида E = e₁e₂e₃e₄ = f(m₁)f(m₂)f(m₃)f(m₄)…, причем функция f(m) имеет обратную функцию g, для которой верно g(f(m)) = m для всех возможных значений m. В данном шифре в качестве ключа используется простая перестановка алфавита (верно в том случае, если буквы заменяются буквами), например, перестановка ЛРЭИБПВЪДЁЗЩЙГХМЦАУОСЖТЯФКЕШНЫЬЧЮ. Она используется следующим образом:

• буква «А» открытого текста заменяется буквой «Л»;

• буква «Б» заменяется буквой «Р»;

• буква «В» заменяется буквой «Э» и т. д.

Как можно понять из определения, данный шифр является довольно простым.

Рассмотрим пример, демонстрирующий одну из возможных реализаций этого шифра. Для этого понадобится создать новое приложение, а на форму поместить следующие компоненты: по два компонента классов TMemo и TLabel с соответствующими именами(mmDecryptMessage, mmEncryptMessage, lbDecryptMessage, lbEncryptMessage), три компонента класса TButton (btnEncryptMessage, btnDecpyptMessage, btnGenRearrangement), а также один компонент класса TValueListEditor (vleSubst). По умолчанию все перечисленные компоненты находятся на вкладке Standard, за исключением компонента класса TValueListEditor, который расположен на вкладке Additional. Когда вы закончите создание интерфейса программы, у вас должно будет получиться нечто подобное тому, что изображено на рис. 12.1.

Рис. 12.1. Интерфейс программы «Шифр простой подстановки»

Текстовый редактор mmDecryptMessage будет служить для ввода и отображения открытого текста сообщения, mmEncryptMessage – для текста, преобразованного с помощью шифра. Редактор значений vleSubst будет использоваться для задания перестановки алфавита, с помощью которой будет шифроваться и дешифроваться текст сообщения. Кнопка btnEncryptMessage будет отвечать за шифрование сообщения из текстового редактора mmDecryptMessage и помещение результата в mmEncryptMessage. Кнопка же btnDecpyptMessage будет выполнять противоположные действия. Последняя кнопка btnGenRearrangement будет служить для генерации случайной перестановки алфавита, чтобы не утруждать себя ее указанием вручную. Для каждой из кнопок необходимо будет добавить обработчики событий OnClick, а для формы – обработчик события OnCreate (он нужен для инициализации редактора значений vleSubst).

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

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

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

type

TRusDstAlphabet = array [Char] of Char;

TfmSubstitution = class(TForm)

mmDecryptMessage: TMemo;

mmEncryptMessage: TMemo;

lbDecryptMessage: TLabel;

lbEncryptMessage: TLabel;

btnEncryptMessage: TButton;

btnDecpyptMessage: TButton;

btnGenRearrangement: TButton;

vleSubst: TValueListEditor;

procedure FormCreate(Sender: TObject);

procedure btnGenRearrangementClick(Sender: TObject);

procedure btnEncryptMessageClick(Sender: TObject);

procedure btnDecpyptMessageClick(Sender: TObject);

private

{Private declarations}

RusDstAlphabet: TRusDstAlphabet;

procedure GenRearrangment;

function ValidateRearrangement: Boolean;

function UpCaseRus(Ch: Char): Char;

function LowCaseRus(Ch: Char): Char;

procedure RecalcAlphabet(nKey: Integer);

function EncryptDecryptString(strMsg: String): String;

public

{Publicccdeclarationss}

end;

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

В данном приложении для удобства и простоты работы будет реализована возможность задания случайной автоматической перестановки. Первым рассматриваемым методом является функция, реализующая алгоритм генерации случайной перестановки заданной длины из букв русского алфавита. Принцип ее работы заключается в следующем. Сначала считается, что в перестановке нет ни единого символа, о чем свидетельствует установка всех элементов массива WasGen в значение False. Далее в цикле случайным образом генерируются буквы русского алфавита. На очередном шаге цикла буква генерируется до тех пор, пока не будет присутствовать среди уже сгенерированных. Как только такая буква будет получена, соответствующий элемент массива WasGen установится в значение True, которое свидетельствует о том, что буква больше не может быть сгенерирована. Буква добавляется в перестановку. Код, соответствующий данному описанию, приведен в листинге 12.2.

Листинг 12.2. Реализация метода генерации случайной перестановки

procedure TfmSubstitution.GenRearrangment;

var

Ch, c: char;

//нужен для определения, встречался ли символ ранее

WasGen: array [Char] of Boolean;

begin

//заполняем массив значением False

FillChar(WasGen, SizeOf(WasGen), False);

for Ch:= ' А'to 'Я'do

begin

//генерируем случайный символ до тех пор, пока

//не будет получен еще не сгенерированный

repeat

c:= Chr(Ord('А') + random(32));

until not WasGen[c];

//помечаем, что символ сгенерирован

WasGen[c]:= True;

vleSubst.Values[Ch]:= c;

end;

end;

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

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

function TfmSubstitution.ValidateRearrangement: Boolean;

var

i: Integer;

s: String;

Used: array [Char] of Boolean;

begin

Result:= False;

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

for i:= 1 to vleSubst.RowCount – 1 do

Begin

//символ единственный в строке?

s:= vleSubst.Cells[1, i];

if (Length(s) <> 1) then

Exit;

//символ – буква русского языка?

s[1]:= UpCaseRus(s[1]);

if not (s[1] in [' А '..'Я ']) then

Exit;

//уже встречался ранее?

if Used[s[1]] then Exit;

Used[s[1]]:= True;

End;

Resulttt:= True;

end;

Далее будут реализованы две вспомогательные функции, которые позволят преобразовывать буквы верхнего регистра к нижнему и наоборот. Их реализация немного специфична и основывается на используемой кодировке. Отдельная проверка буквы «Ё» производится на основании иного расположения в таблице кодировки, чем у остальных букв. Буквы русского алфавита верхнего регистра расположены, начиная с буквы «А», по порядку следования в алфавите, а сразу после них аналогично расположены буквы нижнего регистра. Этим объясняется увеличение кода буквы на фиксированное число. Код реализации данных вспомогательных функций приведен в листинге 12.4.

Листинг 12.4. Вспомогательные функции преобразования регистра букв

function TfmSubstitution.UpCaseRus(Ch: Char): Char;

begin

if Ch = 'ё' then Ch:= 'Е';

if Ch in ['а'..'я'] then Dec(Ch, 32);

Result:= Ch;

end;

function TfmSubstitution.LowCaseRus(Ch: Char): Char;

begin

if Ch = 'Ё' then Ch:= 'е';

if Ch in ['А'..'Я'] then Inc(Ch, 32);

Result:= Ch;

end;

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

Листинг 12.5. Использование генерации случайной перестановки

procedureTfmSubstitution.FormCreate (Sender: TObject);

var

Ch: char;

begin

Randomize;

//инициализация редактора значений

for Ch:= 'А'to 'Я'do

vleSubst.InsertRow(Ch, '', True);

//генерация случайной перестановки

GenRearrangment;

end;

procedure TfmSubstitution.btnGenRearrangementClick(Sender: TObject);

begin

GenRearrangment;

end;

Следующим объектом рассмотрения является функция предварительной подготовки алфавита преобразования для шифрования либо дешифрования сообщения. У метода RecalcAlphabet есть параметр nKey, который в зависимости от своего значения показывает, что является ключом. Возможными значениями параметра nKey являются 0 и 1. Значение 0 указывает, что будет производиться шифрование сообщения и требуется сопоставить в соответствие буквам открытого текста буквы перестановки. Значение 1, напротив, указывает на то, что будет производиться дешифрование сообщения и требуется сопоставить в соответствие буквам перестановки буквы открытого текста. Для этого массив сопоставления символов изначально заполняется таким образом, чтобы каждый символ соответствовал самому себе. Это происходит в следующих строках метода:

for Ch:= Low(RusDstAlphabet) to High(RusDstAlphabet) do RusDstAlphabet[Ch]:= Ch;

После этого требуется подкорректировать данный массив таким образом, чтобы выполнялось требуемое соответствие. Для этого необходимо пройти по всем элементам редактора значений vleSubst и поправить массив, указывая в качестве индекса элемента то, чему ставится соответствие, а в качестве значения элемента массива то, что является соответствием.

for i:= 1 to vleSubst.RowCount – 1 do

RusDstAlphabet[vleSubst.Cells[nKey, i][1]]:= vleSubst.Cells[1 – nKey, i][1];

Редактор значений vleSubst предназначен для сопоставления букв верхнего регистра. Нам же требуется избавиться от различия между буквами верхнего и нижнего регистров. Для этого необходимо дополнительно произвести следующие действия:

for i:= 1 to vleSubst.RowCount – 1 do

RusDstAlphabet[LowCaseRus(vleSubst.Cells[nKey, i][1])]:=

LowCaseRus(vleSubst.Cells[1 – nKey, i][1]);

Работа данного метода по частям рассмотрена. Полный же его код приведен в листинге 12.6. Как видите, все относительно просто (здесь используется вспомогательная функция LowCaseRus).

Листинг 12.6. Функция предварительной подготовки алфавита преобразования

procedure TfmSubstitution.RecalcAlphabet(nKey: Integer);

var

Ch: Char;

i: Integer;

begin

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

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

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

RusDstAlphabet[Ch]:= Ch;

//формируем алфавит от дельно для каждого из регистров букв

//здесь для верхнего

for i:= 1 to vleSubst.RowCount – 1 do

RusDstAlphabet[vleSubst.Cells[nKey, i][1]]:= vleSubst.Cells[1

–nKey, i][1];

//здесь для нижнего

for i:= 1 to vleSubst.RowCount – 1 do

RusDstAlphabet[LowCaseRus(vleSubst.Cells[nKey, i][1])]:=

LowCaseRus(vleSubst.Cells[1 – nKey, i][1]);

end;

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

Листинг 12.7. Преобразование строки с помощью массива сопоставления

function TfmSubstitution.EncryptDecryptString(strMsg: String): String;

var

i: Integer;

begin

//преобразуем строку посимвольно

for i:= 1 to Length(strMsg) do

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

Result:= strMsg;

end;

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

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

procedureTfmSubstitution.btnEncryptMessageClick(Sender: TObject);

var

i: Integer;

begin

//проверяем корректность ввода перестановки

if ValidateRearrangement then

begin

//создаем алфавит преобразования открытого текста

RecalcAlphabet(0);

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

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

mmEncryptMessage.Lines.BeginUpdate;

//очищаем текстовый редактор

mmEncryptMessage.Clear;

//шифруем открытый текст построчно

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

mmEncryptMessage.Lines.Add(EncryptDecryptString(mmDecryptMessage.Lines[i]));

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

mmEncryptMessage.Lines.EndUpdate;

end

else

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

[mbOk], 0);

end;

procedure TfmSubstitution.btnDecpyptMessageClick(Sender: TObject);

var

i: Integer;

begin

//проверяем корректность ввода перестановки

if ValidateRearrangement then

begin

//создаем алфавит преобразования шифрованного текста

RecalcAlphabet(1);

mmDecryptMessage.Lines.BeginUpdate;

mmDecryptMessage.Clear;

//дешифруем шифрованный текст построчно

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

mmDecryptMessage.Lines.Add(EncryptDecryptString(mmEncryptMessage.Lines[i]));

mmDecryptMessage.Lines.EndUpdate;

end

else

MessageDlg('Ошибка: символы подстановки заданы неверно', mtError, [mbOk], 0);

end;

В итоге получился вполне рабочий вариант приложения, способного без особого труда шифровать и дешифровать сообщения. На рис. 12.2 представлен результат работы данного приложения.

Рис. 12.2. Результат работы приложения «Шифр простой подстановки»