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

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

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

RusLetters: TRusLetters = ['А'..’я’];

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. На входе они получают строку, которую требуется преобразовать, и первичный ключ. Внешне они очень похожи, но все же отличаются, и эти отличия существенны. Функция шифрования выполняет следующие действия. В цикле осуществляется проход по строке и проверяется, является ли очередной символ буквой русского алфавита. В случае положительного ответа этот символ преобразуется при помощи очередного символа ключа и добавляется в его конец. Преобразование осуществляется по правилу, которое мы указывали при рассмотрении шифра Виженера: li =xi + yi (modm), то есть символ открытого текста и символ ключа складываются с последующим сокращением этой суммы по модулю т, где т – общее количество букв в алфавите (листинг 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

strEncryptMsg[i] := Chr(((Ord(strEncryptMsg[i]) –

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

Delete(strKey, 1, 1);

strKey := strKey + strEncryptMsg[i];

end;

Result := strEncryptMsg;

end;

Функция дешифрования строки с помощью ключа и криптограммы делает следующее. Как и в предыдущей функции, в цикле осуществляется проход по строке и проверяется, является ли очередной символ буквой русского алфавита. При положительном ответе данный символ сначала добавляется в конец ключа, а потом только осуществляется его преобразование. Обратное преобразование символа проходит по следующему правилу: li = xi – yi (mod 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];

strDecryptMsg[i] := Chr((((Ord(strDecryptMsg[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.6. Взлом

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

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

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

Теоретическая основа для нашей программы имеется, поэтому перейдем к реализации задуманного. Создадим новое приложение. На форму поместим два компонента классов ТМето с соответствующими HMeHaMHmmDecryptMessage HmmEncryptMessage, TpHTLabel, а также по одному компоненту KnaccoBTEdit и TButton – edKey HbtnHackEncrypting соответственно. Текстовый редактор mmDecryptMessage и текстовое поле edKey сделаем доступными только для чтения, поскольку мы будем вводить лишь зашифрованное сообщение, а ключ и соответствующий открытый текст будет определяться нашей программой. Результат разработки интерфейса программы показан на рис. 12.8.

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

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

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

type

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

TRusLetters = set of Char;

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

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

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

TRusFrequency = array [0..32] of Real;

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

RusLetters: TRusLetters = ['Ё', 'ё', 'А'..’я’];

RusSrcAlphabet: TRusSrcAlphabet =

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

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

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

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

procedure TfmHackEncrypting.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

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

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

AbsFrequency[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 или 1 Par am являются указателями на структуры. Для экономии места объявления этих структур не приводятся: их можно найти в модуле Windows.

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

Итак, в приложении представлены таблицы с перечислением некоторых часто используемых сообщений (табл. П3.1), уведомлений от элементов управления (табл. П3.2), сообщений для управления кнопками (табл. П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)