Введение
На
написание данной статьи натолкнул фильм «Игра в имитацию». Всем
известная машина Тьюринга успешно расшифровала сообщения передаваемые
нацисткой криптографической машиной Энигма. И вот я захотел выяснить
какие в те времена были алгоритмы шифрования? И реализовать их на
сегодняшней машине! Интересно? Прошу под кат…
В
нашу эпоху алгоритмов шифрование хоть отбавляй: aes, rsa и т.д. В их
основу положены вычислительные сложности больших чисел и так далее… Но
неужели в эпоху когда не было такой мощи, а точней даже не было
интегральных схем, не было криптоустойчивого алгоритма? И на самом деле
был и есть, который и в наши дни может похвастаться совершенно стойким
шифром как сказал математик Шеннон – “совершенной стойкостью”- шифр
Вернама.
За
автобиографией этого инженера можно обратиться в дополнительные
источники цель же данной статьи принцип работы шифра и его реализация.
Единственное что стоит отметить что данный шифр был разработан в 1917
году! Прошло практический 100 лет, а при правильной реализации алгоритма
шифра и в наши дни для него невозможен полный перебор ключей с целью
определения открытого текста по известному шифртексту. Перейдем к
принципу работы шифра.
Принцип работы
Опишу
сначала немного абстрактно, а потом уже перейдем к низкоуровневой
реализации под современные пк. И так если абстрактно давайте представим
себе что у меня есть два листа бумаги на первом листе есть буква которую
я хочу зашифровать на втором листе ключ которым я хочу зашифровать. Я
должен выполнить следующие действие – первую букву и ключ сложить
побитово (дальше мы разберем побитовую операцию исключающее «или») в
результате я получу шифртекст первой буквы. Принцип такой же для
шифрования и второй буквы, только здесь я использую уже второй ключ.
После чего ключи я уничтожаю, оставляю только шифртекст. Дальше я
посылаю вам свой шифротекст вы имея ключи для каждой буквы проделываете
операцию побитового «или», а именно: побитово складывает первую букву
полученной шифртекста с первым ключом, вторую - со вторым, и т.д. пока
не расшифруете весь текст, после чего обязательно уничтожаете ключи.
Без знания ключа сообщение не поддаётся анализу. Но здесь стоит
соблюдать правила при создании ключа:
1. Длина ключа должна совпадать с длиной сообщения.
2. Нельзя шифровать разные сообщения одним и тем же ключом.
3. Иметь случайное равномерное распределение.
Благодаря
этим правилам с точки зрения криптографии, невозможно придумать систему
безопаснее шифра Вернама. Но почему шифр не так распространен поговорим
позже, а сейчас к его «внутренностям».
И
так мы хотим зашифровать сообщение или символ не суть и написать
программу для этого, а писать я буду её на C#, но и на любом другом
языке можно реализовать, кто забыл стоит вспомнить двоичную систему
счисления. И так мы знаем что все данные в ЭВМ представлены в двоичном
виде, про системы счисления напишу отдельно. Кто забыл напомню что бит - единица измерения информации-один двоичный разряд в двоичной системе счисления, а байт
- единица хранения и обработки цифровой информации где байт считается
равным восьми битам, тогда он может принимать 256 различных значений
(0…255). К примеру число 8 в двоичной виде будет представлено как
00001000. Да сразу же хотелось бы заметить что у чисел в степени двойки
только один бит будет установлен в единицу. Как переводить числа из
десятичной в двоичную думаю ни у кого труда не составляют, это учат еще в
школе. К чему я все это? Потому что мы сейчас подойдем к побитовому
«или» операции XOR. Но давайте сразу вспомним таблицу истинности для
XOR.
1^1=0
1^0=1
0^1=1
0^0=0
Таблицу
истинности вспомнили. И так приступим! Давайте зашифруем сперва число
которое очень секретно допустим это код от вашего сейфа и мы с вами не
хотим чтоб его кто то узнал, правда? Начнем с простого представим что
ваш код пусть будет это же число 8. Число 8 как мы уже выяснили это 1
байт, поэтому вспоминаем правило - длина ключа должна совпадать с длиной
сообщения. То есть ключ у нас тоже будет 1 байт. И так число 8 в
двоичном виде = 00001000. И давайте возьмем ключ 00111001. Хорошо,
хорошо скажите вы, а что дальше? А дальше проще простого применяем XOR.
00001000
00111001
________
00110001
Вау!
Вот он наш шифротекст! 00110001 в двоичной = 49 в десятичной. То есть я
вам передам сообщение 49, но как вы узнаете настоящий какой код от
вашего сейфа? Легко скажите вы, я знаю ключ и могу его применить!
Попробуете? Я попробую точно!
00110001
00111001
________
00001000
И
так мы взяли число 49 которое я вам передал применили наш ключ и что
вышло в результате? Вышло 00001000 в двоичной = 8 в десятичной. Супер!
То есть применив этот ключ к числу 49 мы получили исходное сообщение
число 8. Просто? Просто(когда знаем ключ)))! Зачем над делать это
руками? Ведь это долговато не правда ли? Будем кодить? Будем!
Реализация шифра Вернама будем реализована на C# для набора команд
процессора x86.
А давайте будем шифровать символ? Выберу я классический символ ‘A’.
{
char character = 'A';
ushort key = 0x0036;
Console.WriteLine ("Символ {0} в UNICODE =
{1:X}",
character, (byte)(character));
character = (char)(character ^ key);
Console.WriteLine(character);
character = (char)(character ^ key);
Console.WriteLine(character);
Console.ReadKey();
}
}
И
так что мы получили? Символ w! Пройдемся по программе. И так мы хотим
зашифровать символ А, стоит заметить что в C# тип char 16 бит, в отличии
от С/С++ где 8 бит, связано это с очень огромными алфавитами китайского
языка например где очень много символов поэтому майкрософт принял
решение сделать базовый тип символов длинной в 16 бит. Соответственно и
ключ у нас длинной 16 бит. И так смотрим символ А в UNICODE у нас 41 или
в двоичной системе счисления представлен как = 0000 0000 0100 0001. Так
и ключ у нас выбран 0036 в hex что в двоичной = 0000 0000 0011 0110.
Отлично. Дальше по программе мы пробуем использовать XOR и явно
преобразовать выражение в тип char, пробуем и руками!
0000 0000 0100 0001
0000 0000 0011 0110
_________________
0000 0000 0111 0111
Отлично зашифрование сообщение в двоичном виде 0000 0000 0111 0111 = 0x77. Смотрим в таблицу UNICODE http://unicode-table.com/ru/#control-character
находим там 0x77 и чудо мы видим наш маленький символ w! Конечно данная
программа не представляет собой практической ценности так как его легко
дизассемблировать и узнать ключ, она показывает сам метод реализации.
Ну и следующей строкой просто расшифровываем этим же ключом
зашифрованное сообщение и получаем тот самый символ А. И так с
принципами работы данного алгоритма разобрались и реализовали поговорим
теперь о его недостатках.
Недостатки
Сразу
же бросается в глаза первый недостаток это длина ключа должна совпадать
с длиной сообщения, а это означает, что защита больших объемов
информации требует огромных трудозатрат, связанных с производством,
распределением, хранением и уничтожением ключей. Второй недостаток это
конечно передача ключа. Если существует надёжно защищённый от перехвата
канал передачи сообщений, то и шифр вообще не нужен по сути секретное
сообщение можно передавать по этому каналу. Ключ должен быть абсолютно
случайным, то есть ключ нельзя использовать повторно и он не должен
повторяться.
Итог
В
связи с приведенными выше недостатками, на практике, как правило,
приходится довольствоваться шифрами, которые не являются совершенными.
На практике можно один раз физически передать носитель информации с
длинным истинно случайным ключом, а потом по мере необходимости
пересылать сообщения. В этом и заложена идея шифра шифровальщик при
личной встрече снабжается
блокнотом, каждая страница которого содержит ключи. Такой же блокнот
есть и у принимающей стороны. Использованные страницы уничтожаются. Тем
не менее, стойкие шифры все же нашли практическое применение для
защиты особо важных линий связи с относительно небольшим объемом
информации. Так, например, англичане и американцы использовали шифры
типа Вернама во время Второй мировой войны.
Комментариев нет :
Отправить комментарий