Шифрование: от Цезаря до замочка в браузере

Шифр Цезаря

Древнеримский историк Светоний пишет, что Юлий Цезарь в секретных письмах заменял каждую букву на ту, что стоит в алфавите на три позиции дальше. По-русски А превращается в Г, Б в Д, В в Е и так далее, а в конце алфавита счёт идёт по кругу.

КОТ → НСХ

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

Зашифруйте так своё имя и дайте другу, не называя сдвиг. Скорее всего, он подберёт ключ за пару минут: именно поэтому шифр Цезаря годится только для игры.

Частотный анализ: как ломают любую замену

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

Но такой шифр всё равно вскрыли ещё в IX веке. Арабский учёный аль-Кинди заметил: в любом языке одни буквы встречаются часто, а другие редко. В русском самая частая буква О, за ней Е, А, И, Н, Т. Если в шифровке больше всего значков «Ж», почти наверняка это О. Дальше угадываются короткие слова и частые сочетания, и текст раскрывается.

Тот же метод использовал Шерлок Холмс в рассказе Артура Конан Дойла «Пляшущие человечки», а Эдгар По в рассказе «Золотой жук» описал его ещё раньше. Попробуйте взять длинный текст и посчитать буквы: частоты получатся удивительно постоянными.

«Энигма» и Тьюринг

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

Первыми «Энигму» начали взламывать польские математики ещё до войны. Потом в британском Блетчли-парке работу продолжил математик Алан Тьюринг с коллегами. Они построили электромеханические машины, которые быстро перебирали возможные настройки, отсекая невозможные с помощью логики. Например, «Энигма» никогда не шифровала букву саму в себя, и это одно свойство резко сокращало перебор. Историки считают, что эта работа сократила войну на несколько лет. Тьюринга сегодня называют одним из основателей информатики.

Главная проблема и её решение

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

В 1976 году Уитфилд Диффи и Мартин Хеллман придумали решение. Его объясняют через смешивание красок.

• Алиса и Борис открыто договариваются об общей краске, например жёлтой. Её видят все.
• Каждый втайне выбирает свой цвет: Алиса красный, Борис синий.
• Алиса смешивает жёлтую со своим красным и открыто отправляет смесь Борису. Борис смешивает жёлтую с синим и отправляет Алисе.
• Алиса добавляет к смеси Бориса свой красный, Борис к смеси Алисы свой синий. У обоих получилась одинаковая краска: жёлтый плюс красный плюс синий.
• Подслушивающий видел жёлтую и обе смеси, но разделить смесь обратно на цвета он не может.

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

Что происходит при замочке в браузере

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

Мессенджеры со сквозным шифрованием идут дальше: ключи есть только у собеседников, и даже сервер компании не может прочитать переписку.

Как хранят пароли

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

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

Частые вопросы