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

Предлагаю рассмотреть разные методы шифрования и проследить за их развитием на протяжении нескольких тысяч лет.

Атбаш

Атбаш — простой шифр подстановки, который можно встретить в священных иудейских книгах VI век до н. э.  Правило шифрования состоит в замене i-й буквы алфавита буквой с номером , где  — число букв в алфавите. Пример для латинского алфавита выглядит так: при исходном тексте abcdefghijklmnopqrstuvwxyz шифр будет таким — zyxwvutsrqponmlkjihgfedcba.

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

Шифр Цезаря

Суть алгоритма заключалась в сдвиге алфавита на целое количество символов (для алфавита а,б,в…,ю,я при сдвиге на 1 символ вправо результат был бы — я,а,б...,ю).

Стоит признать, что этот метод был уже менее тривиальным. Несмотря на это, третья сторона, зная, что вы использовали шифр Цезаря, могла расшифровать сообщение, перебрав разные «сдвиги» — даже вручную это не занимало много времени. Что дальше?

Пляшущие человечки и другие алгоритмы сопоставления букв символам/знакам

При переборе «в лоб» мы имеем нерешаемую задачу, так как приходится перебирать порядка вариантов (если брать 30 букв за средний размер алфавита) — на первый знак есть 30 вариантов заменяемой его буквы, на второй знак — 29 букв и так далее; то есть . Это огромное число, которое с трудом обработает даже современный компьютер. Казалось бы, рабочий алгоритм!

Но лингвистика и статистика тоже не стояли на месте: появился такой термин, как «число вхождений» буквы в текст. Соответственно, впервые расшифровав букву «а» или «о», мы знаем, как расшифровать ее еще несколько десятков раз в тексте. Это позволило значительно сократить величину перебора вариантов (уже не , а гораздо меньше).

Улучшенное сопоставление букв символам/знакам

Решили, что можно производить шифровку, заменяя не одну букву, а сочетание из двух-трех-четырех. Например — ab = @, bc = #, ac = $ и так далее. Ну и в чем здесь проблема?

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

На помощь пришла теория чисел

Для начала предлагаю вспомнить ту математическую базу, которая понадобится для понимания процессов шифровки: о чем гласит теорема Эйлера и Эйлерова функция? Для составного числа можно посчитать функцию , вычисляющую количество различных натуральных чисел, не превосходящих и не имеющих общих делителей с ; так вот, для всех , взаимно простых с — так и выглядит теорема Эйлера. Разбираемся дальше: если — произведение и , то справедливо утверждение о том, что — назовем эту величину . Попытаемся подобрать два числа и так, чтобы при t — любом целом числе.

Начинается магия — процесс шифрования

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

Внимательно следите за математикой: . Значит, посчитав остаток от деления на , мы узнаем исходную информацию. Соответственно, если мы возьмем и такими, чтобы было громадным 700-значным числом, то алгоритм нам позволит «резать» информацию на части по 2 килобита информации. Круто, да?

Алгоритм RSA

Описанная мною математика — это то, как работает самый популярный в современном мире алгоритм шифрования RSA, который является одним из первых асимметричных алгоритмов.

Даже если мы открытым образом передаем информацию об и , человеку, перехватившему эти данные, необходимо знать , чтобы найти . А для того чтобы посчитать , ему нужно разложить на множители гигантское число — а это не такая простая задача, как кажется. Еще не существует алгоритмов, способных разложить на множители 700-значное число за разумное время.

Подводя итог по RSA, не умея разложить на простые множители, вы никогда не сможете найти и расшифровать информацию.

Применение шифрования в блокчейне

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

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

Заключение

Конечно, те алгоритмы, которые мы разобрали в этой статье — это далеко не всё, что придумало человечество. Я обошел стороной развивающийся алгоритм Elliptic Curve Digital Signature Algorithm (Алгоритм Цифровой Подписи Эллиптической Кривой, ECDSA), который может посоревноваться с RSA во многих аспектах. Но эллиптические кривые — это отдельная тема с суровой математикой и множеством нюансов.

Математика повсюду! Задумайтесь: математические теоремы, сформулированные в 17-18 веках, нашли свое применение через сотни лет в банковских системах, современных базах данных. И все эти системы можно взломать, лишь понимая, как устроены простые числа!