Во все времена люди пытались найти способ безопасной передачи информации, метод, при котором зашифрованное сообщение мог прочитать только тот, кому оно было адресовано. В современном мире шифры используют повсюду: от мессенджеров и банков до блокчейнов. Происходит непрекращаемое улучшение алгоритмов шифровки: создаются новые методы, находятся уязвимости в прошлых решениях.
Предлагаю рассмотреть разные методы шифрования и проследить за их развитием на протяжении нескольких тысяч лет.
Атбаш
Атбаш — простой шифр подстановки, который можно встретить в священных иудейских книгах VI век до н. э. Правило шифрования состоит в замене i-й буквы алфавита буквой с номером , где
— число букв в алфавите. Пример для латинского алфавита выглядит так: при исходном тексте abcdefghijklmnopqrstuvwxyz шифр будет таким — zyxwvutsrqponmlkjihgfedcba.
Безусловно, такой алгоритм нельзя назвать надежным. Человеку, желающему узнать переданную информацию, необходимо было лишь знать, какой алгоритм использовал шифровщик. Используя эти знания, он мог с легкостью расшифровать сообщение.
Шифр Цезаря
Суть алгоритма заключалась в сдвиге алфавита на целое количество символов (для алфавита а,б,в…,ю,я при сдвиге на 1 символ вправо результат был бы — я,а,б...,ю).
![Алгоритм шифра Цезаря Алгоритм шифра Цезаря](https://habrastorage.org/getpro/habr/upload_files/1f2/397/487/1f2397487133735e48d5942266bbcca2.jpg)
Стоит признать, что этот метод был уже менее тривиальным. Несмотря на это, третья сторона, зная, что вы использовали шифр Цезаря, могла расшифровать сообщение, перебрав разные «сдвиги» — даже вручную это не занимало много времени. Что дальше?
Пляшущие человечки и другие алгоритмы сопоставления букв символам/знакам
При переборе «в лоб» мы имеем нерешаемую задачу, так как приходится перебирать порядка вариантов (если брать 30 букв за средний размер алфавита) — на первый знак есть 30 вариантов заменяемой его буквы, на второй знак — 29 букв и так далее; то есть
. Это огромное число, которое с трудом обработает даже современный компьютер. Казалось бы, рабочий алгоритм!
![Пляшущие человечки Пляшущие человечки](https://habrastorage.org/getpro/habr/upload_files/4ae/ab8/be8/4aeab8be8b601a63f3e030ff8b4e1492.jpg)
Но лингвистика и статистика тоже не стояли на месте: появился такой термин, как «число вхождений» буквы в текст. Соответственно, впервые расшифровав букву «а» или «о», мы знаем, как расшифровать ее еще несколько десятков раз в тексте. Это позволило значительно сократить величину перебора вариантов (уже не , а гораздо меньше).
![Статистика использования букв латинского алфавита Статистика использования букв латинского алфавита](https://habrastorage.org/getpro/habr/upload_files/cd3/919/51a/cd391951aee8b9a2d680bfc71ac4bc4d.jpg)
Улучшенное сопоставление букв символам/знакам
Решили, что можно производить шифровку, заменяя не одну букву, а сочетание из двух-трех-четырех. Например — ab = @, bc = #, ac = $ и так далее. Ну и в чем здесь проблема?
Оказалось, что в этом способе было несколько несовершенств: во-первых, алгоритм был не таким удобным в использовании: процесс шифрования и расшифровки значительно усложнился. Во-вторых, статистический анализ текста, описанный в прошлом методе, давал возможность расшифровывать и этот алгоритм.
На помощь пришла теория чисел
Для начала предлагаю вспомнить ту математическую базу, которая понадобится для понимания процессов шифровки: о чем гласит теорема Эйлера и Эйлерова функция? Для составного числа можно посчитать функцию
, вычисляющую количество различных натуральных чисел, не превосходящих
и не имеющих общих делителей с
; так вот,
для всех
, взаимно простых с
— так и выглядит теорема Эйлера. Разбираемся дальше: если
— произведение
и
, то справедливо утверждение о том, что
— назовем эту величину
. Попытаемся подобрать два числа
и
так, чтобы
при t — любом целом числе.
Начинается магия — процесс шифрования
Как же в действительности все описанное работает? Предположим, нам необходимо безопасно передать другу важное послание. В первую очередь нужно, чтобы человек, который намерен переслать нам информацию, знал два числа: и
(эти данные можно передать как угодно — в любом мессенджере, например). Назовем передаваемую информацию буквой
. И дальше говорим отправителю, используя
, посчитать
, равное
и сообщить нам результат. Отлично,
мы знаем.
Внимательно следите за математикой: . Значит, посчитав остаток от деления
на
, мы узнаем исходную информацию. Соответственно, если мы возьмем
и
такими, чтобы
было громадным 700-значным числом, то алгоритм нам позволит «резать» информацию на части по 2 килобита информации. Круто, да?
Алгоритм RSA
Описанная мною математика — это то, как работает самый популярный в современном мире алгоритм шифрования RSA, который является одним из первых асимметричных алгоритмов.
Даже если мы открытым образом передаем информацию об и
, человеку, перехватившему эти данные, необходимо знать
, чтобы найти
. А для того чтобы посчитать
, ему нужно разложить на множители гигантское число
— а это не такая простая задача, как кажется. Еще не существует алгоритмов, способных разложить на множители 700-значное число за разумное время.
![Алгоритм ассиметричного шифрования Алгоритм ассиметричного шифрования](https://habrastorage.org/getpro/habr/upload_files/e71/288/293/e71288293bded336873eb2ec3bb7a8c3.png)
Подводя итог по RSA, не умея разложить на простые множители, вы никогда не сможете найти
и расшифровать информацию.
Применение шифрования в блокчейне
На мой взгляд, блокчейн — это вершина шифрования, так как децентрализация подразумевает под собой постоянное использование алгоритмов шифрования данных. Разберем один из примеров шифровки: при создании нового криптовалютного кошелька генерируется пара ключей (открытый и закрытый ключ). Для чего это нужно? С одной стороны есть публичный адрес, который генерируется с использованием открытого ключа и может безопасно передаваться другим; с другой стороны используется закрытый ключ для создания цифровых подписей и проверки транзакций. Как только транзакция была подтверждена путем валидации хэша, содержащегося в цифровой подписи, эта транзакция может быть добавлена в блокчейн-регистр.
Эта система проверки цифровой подписи гарантирует, что только лицо, у которого есть закрытый ключ, связанный с соответствующим криптовалютным кошельком, может выводить из него средства.
![Работа RSA Работа RSA](https://habrastorage.org/getpro/habr/upload_files/29f/f02/b35/29ff02b359915e00dc5396d6607545af.png)
Заключение
Конечно, те алгоритмы, которые мы разобрали в этой статье — это далеко не всё, что придумало человечество. Я обошел стороной развивающийся алгоритм Elliptic Curve Digital Signature Algorithm (Алгоритм Цифровой Подписи Эллиптической Кривой, ECDSA), который может посоревноваться с RSA во многих аспектах. Но эллиптические кривые — это отдельная тема с суровой математикой и множеством нюансов.
Математика повсюду! Задумайтесь: математические теоремы, сформулированные в 17-18 веках, нашли свое применение через сотни лет в банковских системах, современных базах данных. И все эти системы можно взломать, лишь понимая, как устроены простые числа!