Валерий Борисок - Delphi. Трюки и эффекты
Листинг 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;
//перебираем все возможные ключи и выбираем тот, при
//использовании которого частоты появления русских букв
//в закодированном сообщении наиболее близки к частотам
