Криптоанализ — наука решения головоломок

Иван Скляров

Xakep, номер #062, стр. 062-072-3

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

Да, не сильно помогло, однако второе слово, очевидно, должно быть словом «ещё». Итого, вместе с «чаю» мы имеем предположительно два расшифрованных слова, а это значит 5 пар клавиш, которые поменял местами эксцентричный директор:

ч – б

у – а

ю – ж

е – э

щ - з

Попробуем произвести замену этих пар в первоначальном зашифрованном предложении:

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

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

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

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

XOR

Но частотный анализ бессилен перед другими типами шифровок, когда одна буква может иметь разные значения в одном и том же шифротексте. Так, к примеру, шифрует знаменитый XOR при условии, что ключ, которым кодируют, больше одного знака. Сначала вспомним, что такое XOR. XOR – это операция логического исключающего ИЛИ, имеющая следующую семантику:

0 xor 1 = 1

1 xor 0 = 1

0 xor 0 = 0

1 xor 1 = 0

Например, буква «А» (латинская) в кодировке ASCII имеет код 41h или 1000001 в двоичном виде, а цифра «1» 31h=110001. Проксорим эти буквы (точнее, их коды):

A = 1000001

XOR

1 = 0110001

-----------

p = 1110000

Получился ответ 1110000, а это есть двоичный ASCII-код буквы «p». На этом принципе и основана шифровка XOR!

Ну а что если дан ключ «1984». Закодируем с его помощью фразу «Hacker Hacker Hacker». Это может сделать, например, следующая программа на Си (протестировано в среде Visual C++ 6.0):

Кодировщик

#include <stdio.h>

int main() {

char str[]="Hacker Hacker Hacker";

char key[]="1984";

int i=0, j=0;

printf("%s\n", str);

while (str[i] != '\0') {

if (j>3) j=0;

printf("%c", str[i++]^=key[j++]);

}

printf("\n");

return 0;

}

Посмотрим на схеме, что происходит в действительности.

Как видишь, одна и та же буква может быть закодирована по-разному. Например, буква «H» в шифротексте принимает следующие значения: «y» «|» и «p» (см. рисунок 6). XOR представляет собой, по сути, шифр Вижнера. Такой шифр частотным анализом вскрыть невозможно!

АТАКА ПО ОТКРЫТОМУ ТЕКСТУ

У XOR есть еще одно важное свойство, которое нужно всегда держать в голове:

X xor Key = Y

Y xor Key = X

X xor Y = Key

Т.е., зная хотя бы часть открытого текста, можно получить ключ! Посмотрим это еще на одном примере из рубрики X-Puzzle (][ #55):

M.J.Ash скачал третью версию уже всем знакомой программы CryptFuck! Уверенной рукой Эш набрал в поле ввода слово «Ivan» (без кавычек) и нажал кнопку Crypt, программа выдала следующий шифр:

{@Q^

Затем он набрал «Sklyarov» и получил следующее:

a]\ISD_F

И что-то опять не понравилось ведущему самой варезной рубрики. Набрав последнее слово «Ash» и посмотрев на полученный шифр, M.J.Ash окончательно разгадал алгоритм шифрования, после чего ему ничего не оставалось, как удалить программу со своего винчестера (он совершенно не хотел рекомендовать читателям программу со столь нестойким алгоритмом шифрования).