ИСТОРИЯ КРИПТОГРАФИИ !

Что такое криптография? Откуда она появилась? Как так оказалось, что любой пользователь Интернета использует шифрование, даже не подозревая об этом? Почему IT-специалисты ругают администраторов сайтов, которые могут отправить пользователю его пароль? Многие заинтересовались этими вопросами в связи с большим количеством новостей про Сноудена, Роскомнадзор и так далее. Редакция UserFriendly объясняет.

Классическая криптография
Еще в древние времена люди начали использовать шифры, чтобы вести секретную переписку. Одним из самых известных классических шифров является шифр Цезаря — сдвиг букв на определенное количество символов:

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

Очевидно, что никакой безопасности в наше время такой шифр не предоставляет. Но для скрытия спойлеров и решений загадок часто используется ROT13 — шифр Цезаря со сдвигом 13. 13 — половина 26 — количества букв в английском алфавите, что делает функцию обратной самой себе.

В 15–16 веках были впервые описаны полиалфавитные шифры — следующий этап в развитии криптографии. Идея заключалась в том, чтобы для каждой следующей буквы переключать алфавит, на который происходит подстановка, на другой. Самым известным оказался шифр Виженера, который сочетает несколько шифров Цезаря с разными значениями сдвига. Для шифрования нужна квадратная таблица алфавитов (tabula recta), ключ (ключевое слово) и исходный текст. Посмотрим, как это работает:

Такой шифр считался стойким аж до 19 века, когда был разработан метод Касиски.

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

Идеальный шифр
Но один шифр оказался особенным. One-time pad (OTP, «одноразовый блокнот»), или шифр Вернама, предложенный для телеграфных сообщений сотрудником AT&T, оказался абсолютно стойким к любому криптоанализу. Это было доказано в 1940-х годах великим математиком и инженером Шенноном. В чем подвох? Рассмотрим, как такой шифр устроен.

В отличие от выше описанных алгоритмов, описанных для текстов на естественном языке, OTP можно описать только для двоичного (бинарного) кода. В современных компьютерах и прочих электронных устройствах для представления текста чаще всего используется кодировка ASCII и совместимая с ней UTF-8. Но двоичные кодировки появились задолго до двоичных компьютеров — они использовались в телеграфах. Стандартом в США в то время был код Бодо.

Итак, у нас есть исходный текст — строка (последовательность) битов (цифр 0 и 1 — «bit» значит «binary digit», двоичная цифра). Все, что делает шифр Вернама — объединяет эту строку с секретным ключом. Побитово. Операцией «исключающее ИЛИ», XOR, она же «сложение по модулю 2». 0 ⊕ 0 = 0. 0 ⊕ 1 = 1. 1 ⊕ 0 = 1. 1 ⊕ 1 = 0. (Благодаря симметричности такой операции, расшифровка происходит точно так же, как и шифрование.)

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

Собственно необходимость иметь достаточно длинный ключ — главная причина того, что OTP не используется в современных компьютерных системах. Ну разве кто-то захочет хранить ключ объемом 1 Гигабайт, чтобы защитить данные такого же объема? Да и где взять длинные случайные числа?

Впрочем, принцип одноразового блокнота лежит в основе одного из двух видов современных шифров — поточных шифров (stream ciphers). Вместо длинного ключа используется последовательность, созданная криптографически стойким генератором псевдослучайных чисел — маленький ключ (обычно — случайная последовательность из 128 или 256 бит) «растягивается» с помощью алгоритма до огромной длины. А идея применения сложения по модулю 2 все та же.

Новое направление
Все описанные выше методы можно обобщить как симметричное шифрование (шифрование с секретным ключом) — отправитель и получатель сообщения должны заранее договориться о том, какой ключ использовать, и держать его в тайне.

Все изменилось в 1976 году, когда двое ученых из Стенфорда Уитфилд Диффи и Мартин Хеллман опубликовали статью «New Directions in Cryptography» («Новые направления в криптографии»). В ней была представлена идея асимметричной криптографии, или криптографии с открытым ключом (public-key cryptography). Каждый участник обмена сообщениями создает пару ключей — открытый (public key) и закрытый (private key). Открытый ключ используется для шифрования, а закрытый — для расшифровки. Таким образом, можно опубликовать свой открытый ключ и безопасно получать сообщения от кого угодно.

Диффи и Хеллман придумали протокол, позволяющий двум участникам получить общий (одинаковый) ключ для симметричного шифрования, имея в распоряжении только открытый (незащищенный от подслушивания) канал связи. Чтобы понять, как он работает, достаточно простой школьной математики — используется только возведение в степень и взятие остатка от деления. Все гениальное просто:

Обмен ключами Диффи-Хеллмана защищен от подслушивания, но не от подмены сообщений. Для этого нужна дополнительная защита…

Электронная подпись
А первый алгоритм, осуществлявший именно идею шифрования с открытыми ключами, опубликовали Рональд Ривест, Ади Шамир и Леонард Адлеман из MIT, всего лишь через год после выхода той статьи. Алгоритм назвали RSA, по первым буквам фамилий изобретателей. Стойкость RSA основана на сложности разложения числа на простые множители.

Этот алгоритм также можно использовать в качестве электронной подписи. Подпись позволяет подтвердить авторство сообщения (authentication), его целостность, то есть отсутствие изменений с момента подписания (integrity), и невозможность отказа от подписи (non-repudiation). Оказывается, если использовать криптосистему с открытым ключом «наоборот», можно получить систему подписи сообщений.

Напомним: для шифрования используется открытый ключ, для расшифрования — закрытый. Что значит использовать такую систему «наоборот»? Автор сообщения шифрует текст с помощью закрытого ключа — полученный зашифрованный документ и есть подпись. Вместе с ней отправляется исходный текст в открытом виде. Соответственно получатели могут попробовать расшифровать подпись, используя открытый ключ. Если результат совпадает с открытым текстом, подпись верна.

Хеширование
Подписывать само сообщение — не очень хорошая идея, поскольку оно может быть большое, а RSA работает не очень быстро, и не может подписывать сообщения, более длинные, чем ключ.

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

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

На самом деле, для этого правильно использовать основанные на хешировании функции формирования ключа (KDF), которые также можно использовать для, как ни странно, формирования ключей :) Дело в том, что хеш-функции работают очень быстро и не требуют много оперативной памяти. Они предназначены для быстрого сравнения значений. А KDF работают медленнее и требуют больше ресурсов, что позволяет серьезно замедлить перебор пароля!

Но многие сайты до сих пор хранят пароли открытым текстом. И если вдруг происходит утечка базы данных, все могут сразу зайти от чьего угодно имени, так как в базе хранился сам пароль. Если бы там был его хеш, то с ним войти нельзя, ведь поле «пароль» в форме входа принимает именно пароль, а не хеш от него.

Еще одно интересное применение хеширования — proof of work (доказательство работы). В 1997 году была предложена система Hashcash, предназначенная для борьбы со спамом в электронной почте. Суть в том, что отправитель может доказать, что потратил некоторое время на вычисление специальной отметки для сообщения, а получатель проверяет эту отметку моментально. Вычисление заключается, конечно же, в переборе хеш-функции.

Но самое интересное, что принцип proof of work лег в основу криптовалют. Вместе с электронными подписями.

Безопасность в Интернете
В 1990-е годы Интернет начал очень быстро расти. Появились интернет-магазины, такие как Amazon. Передавать домашние адреса и номера кредитных карт в открытом виде по общедоступной сети — очень плохая идея. Поэтому разработчики браузера Netscape придумали протокол SSL (Secure Sockets Layer), который в дальнейшем превратился в стандарт TLS (Transport Level Security).

Когда вы открываете адрес, начинающийся с https://, ваш браузер использует TLS для подключения к серверу. Этот протокол использует выше перечисленные алгоритмы — симметричный шифр, электронную подпись, обмен ключами Диффи-Хеллмана, хеш-функцию… а также инфраструктуру открытых ключей.

Этот протокол обеспечивает конфиденциальность (интернет-провайдеры между вами и сервером не видит содержимое просматриваемых страниц), целостность (провайдеры не могут изменять страницы, например, вставляя свою рекламу — или вредоносное ПО) и аутентификацию (вы можете быть уверены, что https://google.com — это действительно Google, если ваш браузер отображает тот самый замок в адресной строке).

Инфраструктура открытых ключей, используемая для аутентфикации сайтов, не идеальна.