Excel. Трюки и эффекты
Шрифт:
Листинг 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
. Общие оконные стили