Ключ к шифру

goodfon.ru

Текст: Вадим Давыдов, Сергей Беззатеев

Криптография от Цезаря

Давным-давно, когда даже слова «компьютер» еще не придумали, римский политик Гай Юлий Цезарь изобрел простой шифр: он брал алфавит, сдвигал его на три буквы и сопоставлял оригинальный алфавит с получившимся. Если взять первые шесть букв русского алфавита «абвгде», затем применить сдвиг на три, то получится «гдеёжз». Соответственно, слово «бег» зашифруется в «дзё». Достаточно просто, не правда ли? Теперь посмотрим, что здесь происходит с точки зрения математики. Чтобы взломать шифр Цезаря, необходимо всего лишь перебрать 32 варианта сдвига, и один из них точно станет ключом. В наше время использование такого шифра очень рискованно – слишком легко взломать. Но во времена Цезаря из-за неграмотности его врагов этот способ был достаточно эффективным.

Криптография изучает обеспечение конфиденциальности данных, их целостности, шифрования и аутентификации.

С развитием математики развивалась и криптография. Появлялись более сложные шифры, например, шифр Виженера. По сути, это тот же метод Цезаря, только шифрование происходит с помощью ключевого слова – не весь алфавит сдвигается на определенное значение, а каждый символ сообщения, которое нужно зашифровать. Первая буква шифруемого слова сдвигается на номер первой буквы ключа. К примеру, чтобы зашифровать слово «бег» с ключевым словом «крипто», необходимо сдвинуть букву «б» (вторая в алфавите) на 12 позиций (буква «к» имеет номер 12 в русском алфавите), букву «е» (номер 6) – на 18 позиций, а букву «г» – на 10 позиций. Получим зашифрованное слово «мцм». Если наше сообщение длиннее ключа, то он циклически повторяется: к примеру, для слова «безопасность» ключ будет «криптокрипто». Главная проблема данного шифра – повторяемость ключа. С помощью некоторых тестов очень просто найти длину ключа. Как только она будет обнаружена, из этого «сложного» шифра получится только некоторое количество шифров Цезаря, а их уже легко вскрыть.

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

Практически все исторические шифры не обладают высокой криптостойкостью (способностью противостоять атакам), поэтому сейчас в серьезных системах не используются. Безопасность того или иного алгоритма шифрования определяется сложностью задачи, которую должен решить злоумышленник, чтобы успешно взломать послание. В шифре Цезаря задачу поиска сдвига способен «расколоть» даже ребенок. В шифре Виженера все уже не настолько просто, но для компьютера – пара минут работы. В мировой истории существует огромное количество различных шифров. Большинство из них вскрыты и на сегодняшний день неприменимы.

Исторически стойкость шифра объяснялась тем, что о нем не было никакой информации, поэтому порой требовалось очень много времени, чтобы понять, каким образом идет шифрование и расшифровка. Например, шифр немецкой машины Энигма считался в Третьем рейхе настолько качественным, что немцы искали причины утечек информации в чем угодно, но не в проблемах с Энигмой. Между тем, слаженная работа Великобритании, Франции и Польши по «взлому» Энигмы позволила им, пусть и не быстро, но получить к ней доступ, воспользовавшись данными разведки: сотрудник министерства обороны Германии передал французам вышедшие из употребления коды, которые ему поручили уничтожить. Но для победы над Энигмой британцам пришлось построить более двухсот криптоаналитических машин – они делали расшифровки, которые уже не удавалось проводить вручную. В наши дни, чтобы шифр был стойким, необходимо использовать в его основе задачу, которую злоумышленник не сможет решить, не зная «секрета». Для таких целей выбираются NP-полные задачи: их невозможно решить за разумное время на современном компьютере. Например, если решение задачи может быть найдено за 50 лет непрерывной работы, то она считается нерешаемой, – через 50 лет информация, конечно, устареет.

goodfon.ru «Энигма» – шифровальная машина для секретных сообщений. Использовалась в коммерческих целях, а также военными службами во многих странах мира, но наибольшее распространение получила в гитлеровской Германии во время Второй мировой войны.

Современные проблемы

Одной из самых известных задач в криптографии стала факторизация: необходимо разложить число на простые множители. Разложение числа 33, например, не составит большого труда: нужно перебрать все простые числа меньше 33 и проверить, делится ли на какое-то из них число 33. Но как быть с числами, в которых количество знаков превышает десятки тысяч? Конечно, существуют алгоритмы, ускоряющие перебор простых множителей, но до сих пор не найдено такого, который позволит сделать это за разумное время на классическом компьютере.

Вторая очень известная задача – поиск дискретного логарифма. В ней нужно найти логарифм, но основная загвоздка – в том, что искать приходится по модулю. Объяснение – дальше. Представим, что у нас есть электронные часы со шкалой часа от 0 до 23. Представим также, что наш день подходит к концу и часы показывают 23:00. Через два часа на часах будет 1:00, но не 25:00. Всё дело в том, что часы работают по модулю 24. То есть, когда число выходит за пределы 24, оно возвращается в набор значений от 0 до 23. Поэтому возможные значения для показателя часа – это целые числа 0, 1, 2 … 23. В криптографии используются точно такие же модули. Например, 43 по модулю 15 будет равно 13. 13 – это остаток от деления 43 на 15. Можно воспользоваться той же логикой, что и у часов: при выходе за границу 15 число снова будет попадать в набор от 0 до 14. В задаче дискретного логарифмирования необходимо решить уравнение gx = a mod p. До сих пор для классического компьютера не найдено алгоритма, с помощью которого это можно сделать за разумное время.

Задача дискретного логарифма состоит в том, что необходимо вычислить показатель степени, зная число, возводимое в степень, результат и простое число (модуль), по которому выполнялись вычисления.

Внимательный читатель наверняка заметил, что в задачах факторизации и дискретного логарифмирования используется словосочетание «классический компьютер», когда речь идет об алгоритмах решения. Помимо классического компьютера, существует квантовый – он не общедоступен и разрабатывается только в крупных лабораториях. Задачи факторизации и дискретного логарифмирования, которые мы обсудили выше, могут быть решены очень быстро с помощью специального алгоритма Шора, разработанного для квантового компьютера. Еще один алгоритм, алгоритм Гровера, позволит несколько сократить время вскрытия криптографических алгоритмов, основанных на любых задачах, поэтому уже сегодня рекомендуется увеличивать длину ключа при работе с любыми алгоритмами.

Этот успех вызывает опасения всего криптографического сообщества. Чтобы подготовиться к развитию квантового компьютера (о сложностях работы квантовых компьютеров мы писали здесь. – Ред.) уже создано целое направление – постквантовая криптография. В ней разрабатываются алгоритмы, основанные на задачах, отличных от задач факторизации и дискретного логарифмирования. Такие задачи используют в своей основе более сложную математику и различные интересные конструкции, например, коды, исправляющие ошибки, или решетки. Важно помнить, что в основе любого криптографического алгоритма с открытым ключом на сегодняшний день должна лежать какая-либо NP-полная задача, иначе он будет очень быстро вскрыт с использованием современных вычислительных мощностей.

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

Математика стоит на страже информационной безопасности, но только тогда, когда она используется аккуратно и эффективно. Перед тем как криптографический алгоритм становится стандартом или патентуется, он изучается учеными по всему миру, подвергается различным атакам, и если после этого он все еще остается «несломленным», то его можно внедрять в реальные системы, не беспокоясь о безопасности пользователей. Так что, когда будете в следующий раз доверять персональные данные социальным сетям и беспокоиться о них, помните, что за сохранность информации в этом случае отвечает наука, более ранняя, чем даже слово «компьютер».