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

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

Шифр, основывающийся на шифре Виженера, в котором или само сообщение, или результирующая криптограмма используются в качестве ключа, называется шифром с автоключом. Шифрование начинается с помощью «первичного ключа» (который является настоящим ключом в данном случае) и продолжается с помощью сообщения или криптограммы, смещенной на длину первичного ключа. Рассмотрим пример, в котором первичным ключом является набор букв ЗЕБРА. В табл. 12.2 приведено шифрование, при котором в качестве ключа используется сообщение.

Таблица 12.2. Шифр с автоключом (ключ – сообщение)

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

Таблица 12.3. Шифр с автоключом (ключ – криптограмма)

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

Ниже приведен код с объявлением необходимых типов, констант и переменных, а также объявлением класса формы (листинг 12.18).

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

type

TRusLetters = set of Char;

TfmEncryptingAutoKey = 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}

function GetKey: String;

function EncryptString(strEncryptMsg: String; var strKey:

String): String;

function DecryptString(strDecryptMsg: String; var strKey:

String): String;

procedure EncryptDecrypt(SrcLines, DstLines: TStrings; bEncrypt:

Boolean);

public

{Public declarations}

end;

const

RusLett ers: TRusLett ers = ['А'..'я '];

var

 fmEncryptingAutoKey: TfmEncryptingAutoKey;

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

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

function TfmEncryptingAutoKey.GetKey: String;

var

i: Integer;

begin

Result:= '';

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

if not (edKey.Text[i] in RusLetters) then

Exit;

Result:= edKey.Text;

end;

На входе функции EncryptString и DecryptString получают строку, которую требуется преобразовать, и первичный ключ. Внешне они очень похожи, но все же отличаются, и эти отличия существенны. Функция шифрования выполняет следующие действия. В цикле осуществляется проход по строке и проверяется, является ли очередной символ буквой русского алфавита. В случае положительного ответа этот символ преобразуется с помощью очередного символа ключа и добавляется в его конец. Преобразование осуществляется по правилу, которое указывалось при рассмотрении шифра Виженера: I = x + y_t (mod m), то есть символ открытого текста и символ ключа складываются с последующим сокращением этой суммы по модулю m, где m – общее количество букв в алфавите (листинг 12.20).

Листинг 12.20. Функция шифрования строки с помощью ключа и криптограммы

function TfmEncryptingAutoKey.EncryptString(strEncryptMsg: String;

var strKey: String): String;

var

i: Integer;

begin

for i:= 1 to Length(strEncryptMsg) do

if strEncryptMsg[i] in RusLetters then

begin

strEncrypt Msg[i]:= Chr(((Ord(strEncrypt Msg[i]) – Ord('А')) +

(Ord(strKey[1]) – Ord('А'))) mod 64 + Ord('А'));

Delete(strKey, 1, 1);

strKey:= strKey + strEncryptMsg[i];

end;

Result:= strEncryptMsg;

end;

Функция дешифрования строки с помощью ключа и криптограммы выполняет следующие операции. Как и в предыдущей функции, в цикле осуществляется проход по строке и проверяется, является ли очередной символ буквой русского алфавита. При положительном ответе данный символ сначала добавляется в конец ключа, и только потом осуществляется его преобразование. Обратное преобразование символа выполняется по следующему правилу: I = x_t – y_t (mod m), то есть из символа преобразованного текста вычитается символ ключа с последующим сокращением этой разности по модулю m, где m – общее количество букв в алфавите. Если результат отрицателен, происходит дополнение до положительного числа значением m. Код реализации этих действий представлен в листинге 12.21.

Листинг 12.21. Функция дешифрования строки с помощью ключа и криптограммы

function TfmEncryptingAutoKey.DecryptString(strDecryptMsg: String;

var strKey: String): String;

var

i: Integer;

begin

for i:= 1 to Length(strDecryptMsg) do

if strDecryptMsg[i] in RusLetters then

begin

strKey:= strKey + strDecryptMsg[i];

strDecrypt Msg[i]:= Chr((((Ord(strDecrypt Msg[i]) – Ord('А')) –

(Ord(strKey[1]) – Ord('А'))) + 64) mod 64 + Ord('А'));

Delete(strKey, 1, 1);

end;

Result:= strDecryptMsg;

end;

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

Листинг 12.22. Функция шифрования и дешифрования текста сообщения

//bEncrypt = True – шифровать

//bEncrypt = False – дешифровать

procedure TfmEncryptingAutoKey.EncryptDecrypt(SrcLines,

DstLines: TStrings; bEncrypt: Boolean);

var

i: Integer;

strKey: String;

begin

strKey:= GetKey;

if strKey <> '' then

begin

DstLines.BeginUpdate;

DstLines.Clear;

if bEncrypt then

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

DstLines.Add(EncryptString(SrcLines[i], strKey))

else

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

DstLines.Add(DecryptString(SrcLines[i], strKey));

DstLines.EndUpdate;

end

else

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

end;

procedure TfmEncryptingAutoKey.btnEncryptMessageClick(Sender: TObject);

begin

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

end;

procedure TfmEncryptingAutoKey.btnDecpyptMessageClick(Sender: TObject);

begin

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

end;

end.

Пример работы полученного приложения показан на рис. 12.7.

Рис. 12.7. Результат работы приложения «Шифр с автоключом»

Взлом

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

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

Теоретическая основа данной программы создана, поэтому можно переходить к ее реализации. Поместите на форму два компонента классов TMemo с соответствующими именами mmDecryptMessage и mmEncryptMessage три TLabel и по одному компоненту классов TEdit и TButton – edKey и btnHackEncrypting соответственно. Текстовый редактор mmDecryptMessage и текстовое поле edKey сделайте доступными только для чтения, поскольку вводиться будет лишь зашифрованное сообщение, а ключ и соответствующий открытый текст будут определяться программой. Результат разработки интерфейса программы показан на рис. 12.8.

Рис. 12.8. Интерфейс программы «Шифр Цезаря – взлом»

Таблица 12.4. Относительные частоты букв русского языка

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

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

type

//множество всех русских букв

TRusLetters = set of Char;

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

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

//относительные частоты русских букв

TRusFrequency= array[0..32] offReal;

TFrequency = array [Char] of Real;

TRusDstAlphabet = array [Char] of Char;

TfmHackEncrypting = class(TForm)

mmDecryptMessage: TMemo;

mmEncryptMessage: TMemo;

lbDecryptMessage: TLabel;

lbEncryptMessage: TLabel;

btnHackEncrypting: TButton;

edKey: TEdit;

lbKey: TLabel;

procedure FormCreate(Sender: TObject);

procedure btnHackEncryptingClick(Sender: TObject);

private

{Private declarations}

//значение ключа, вычисляемого на основании частотного анализа

nHackKey: Integer;

//количество букв русского алфавита в закодированном сообщении

nCount: LongInt;

//абсолютная частота букв русского алфавита (то есть количество

//каждой буквы по отдельности) в зашифрованном сообщении

AbsFrequency: TFrequency;

//относительная частота букв русского алфавита в шифровке

RelFreqInMsg: TFrequency;

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

RelFreqInLang: TFrequency;

RusDstAlphabet: TRusDstAlphabet;

function UpCaseRus(Ch: Char): Char;

procedure RecalcAlphabet(nKey: Integer);

function DecryptString(strDecryptMsg: String; nKey: Integer): String;

public

{Public declarations}

end;

const

RusLett ers: TRusLett ers = [' Ё Ё', 'ё ё', 'А'..'я '];

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

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

//частоты в соответствии с порядком букв в русском алфавите

RusFrequency: TRusFrequency =(

0.063, 0.014, 0.038, 0.013, 0.025, 0.072, 0.072, 0.007,

0.016, 0.062, 0.010, 0.028, 0.035, 0.026, 0.052, 0.090,

0.023, 0.040, 0.045, 0.053, 0.021, 0.001, 0.009, 0.004,

0.012, 0.005, 0.003, 0.015, 0.017, 0.015, 0.002, 0.006,

0.018);

var

fmHackEncrypting: TfmHackEncrypting;

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

Листинг 12.24. Обработчик события формы OnCreate

procedure TfmHackEncrypting.FormCreate(Sender: TObject);

var

i, h: Integer;

begin

h:= High(RusSrcAlphabet) div 2;

for i:= Low(RusSrcAlphabet) to High(RusSrcAlphabet) do

RelFreqInLang[RusSrcAlphabet[i]]:= RusFrequency[i mod h];

end;

Вспомогательные методы UpCaseRus, RecalcAlphabet и DecryptString вам уже знакомы. Они выполняют стандартные действия из предыдущих примеров, поэтому достаточно привести их реализацию только для данного случая (листинг 12.25).

Листинг 12.25. Вспомогательные функции

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

begin

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

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

Result:= Ch;

end;

procedure TfmHackEncrypting.RecalcAlphabet(nKey: Integer);

var

Ch: Char;

i: Integer;

LetCnt: Integer;

begin

for Ch:= #0 to #255 do

RusDstAlphabet[Ch]:= Ch;

LetCnt:= SizeOf(TRusSrcAlphabet);

for i:= 0 to LetCnt – 1 do

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

RusSrcAlphabet[i];

end;

function TfmHackEncrypting.DecryptString(strDecryptMsg: String;

nKey: Integer): String;

var

i: Integer;

begin

for i:= 1 to Length(strDecryptMsg) do

strDecryptMsg[i]:= RusDstAlphabet[strDecryptMsg[i]];

Result:= strDecryptMsg;

end;

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

Листинг 12.26. Обработчик события кнопки OnClick

procedureTfmHackEncrypting.btnHackEncryptingClick(Sender: TObject);

var

Ch: Char;

i, j, h: Integer;

Delta, MinDelta: Real;

begin

//обнуляем счетчик русских букв в закодированном сообщении

nCount:= 0;

FillChar(AbsFrequency, SizeOf(AbsFrequency), 0);

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

for j:= 1 to Length(mmEncryptMessage.Lines[i]) do

begin

//очередной символ сообщения

Ch:= mmEncryptMessage.Lines[i][j];

//проверяем, принадлежит ли символ множеству русских букв?

if Ch in RusLetters then

begin

//подсчитываем количество данной буквы в отдельности

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

UUAbsFrequency[UpCaseRus(Ch)]:= AbsFrequency[UpCaseRus(Ch)] + 1;

Inc(nCount);

end;

end;

if nCount = 0 then

begin

MessageDlg('Дешифровать сообщение нельзя, так как'+

'отсутствует русский текст', mtError, [mbOk], 0);

Exit;

end;

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

FillChar(RelFreqInMsg, SizeOf(RelFreqInMsg), 0);

for i:= Low(RusSrcAlphabet) to High(RusSrcAlphabet) div 2 do

RelFreqInMsg[RusSrcAlphabet[i]]:= AbsFrequency[RusSrcAlphabet[i]] / nCount;

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

//использовании которого частоты появления русских букв

//в закодированном сообщении наиболее близки к частотам

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

//абсолютных разностей частот букв наименьшая

h:= High (RusSrcAlphabet) div 2 + 1;

MinDelta:= h;

for i:= 1 to h – 1 do

begin

Delta:= 0;

for j:= 0 to h – 1 do

Delta:= Delta + Abs(RelFreqInLang[RusSrcAlphabet[j]] –

RelFreqInMsg[RusSrcAlphabet[(i + j + h) mod h]]);

//очередная сумма разностей меньше всех предыдущих?

if MinDelta > Delta then

begin

//запоминаем ее...

MinDelta:= Delta;

//... и запоминаем ключ, при котором получено данное значение

nHackKey:= i;

end;

end;

edKey.Text:= IntToStr(nHackKey);

h:= High(RusSrcAlphabet) + 1;

RecalcAlphabet(h – nHackKey mod h);

mmDecryptMessage.Lines.BeginUpdate;

mmDecryptMessage.Clear;

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

mmDecryptMessage.Lines.Add(DecryptString(mmEncryptMessage.Lines[i], nHackKey));

mmDecryptMessage.Lines.EndUpdate;

end;

Результат работы написанного приложения показан на рис. 12.9. Как видите, все получилось!

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

Хочется отметить, что частотный анализ может производиться не только по частоте использования букв, но и по частоте употребления определенных слов и даже фраз. Например, если ведется переписка между Димой и Николаем, то вероятность, что Дима начнет свое обращение со слов «Дорогой Николай» выше, чем вероятность того, что он начнет его произвольным набором символов «ЫКр2!». Поэтому, когда вы сами будете пытаться вскрыть чей-то шифр, помните о такой возможности, но не забывайте, что существуют и значительно более сложные шифры, чем рассмотренные здесь. Часто для улучшения стойкости шифров применяются различные методики сжатия информации, чтобы было сложнее воспользоваться частотным анализом, так как в этом случае частоты будут почти одинаковы.

Заключение

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

При написании книги я постарался минимизировать количество примеров, которым невозможно найти применение на практике. Насколько это удалось, судить только вам. Мне остается лишь пожелать вам успехов, уважаемый читатель, в программистской практике (неважно, с использованием Delphi или других языков и сред программирования).

Приложение 1
Коды и обозначения основных клавиш

В табл. П1.1 приведены коды, обозначения целочисленных констант и описания основных клавиш.

Таблица П1.1. Коды, обозначения и описания клавиш

Приложение 2
Оконные стили

В приложении представлены таблицы, описывающие следующие оконные стили: общие (табл. П2.1), дополнительные (табл. П2.2), стили кнопок (табл. П2.3), статических надписей (табл. П2.4), текстовых полей (табл. П2.5), списков (табл. П2.6) и раскрывающихся списков (табл. П2.7).

Таблица П2.1. Общие оконные стили

Таблица П2.2. Дополнительные оконные стили

Таблица П2.3. Стили кнопок

Таблица П2.4. Стили статических надписей

Таблица П2.5. Стили текстовых полей

Таблица П2.6. Стили списков (ListBox)

Таблица П2.7. Стили раскрывающихся списков (ComboBox)

Приложение 3
Сообщения

В таблицах данного приложения приведены обозначения констант, описания сообщений, а также назначения параметров wParam и lParam сообщений. Часто параметры wParam или lParam являются указателями на структуры. Для экономии места объявления этих структур не приведены: их можно найти в модуле Windows.

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

В приложении представлены таблицы с перечислением некоторых часто используемых сообщений (табл. П3.1), уведомлений от элементов управления (табл. П3.2), сообщений для управления кнопками (табл. П3.3), статическими надписями (табл. П3.4), текстовыми полями (табл. П3.5), списками (табл. П3.6) и раскрывающимися списками (табл. П3.7).

Таблица П3.1. Некоторые часто используемые сообщения

Таблица П3.2. Уведомления от элементов управления

Таблица П3.3. Сообщения для управления кнопками

Таблица П3.4. Сообщения для управления статическими надписями

Таблица П3.5. Основные сообщения для управления текстовыми полями

Таблица П3.6. Основные сообщения для управления списками (ListBox)

Таблица П3.7. Основные сообщения для управления раскрывающимися списками (ComboBox)