Пост памяти одного М.

Пост памяти одного М. 

Постараемся в очень простой и кривой гуманитарной аналогии объяснить, как может работать шифрование. Например:

1. У вас есть ящик, замок и два ключа от него. Вы кладёте в ящик один ключ от своего замка и закрываете его на свой замок. 
2. Отправляете этот ящик второму человеку, например, нам. Мы получаем запертый ящик с ключом и не можем его открыть, но зато можем запереть на второй свой замок. Запираем и отправляем вам обратно.
3. Вы получаете ящик на двух замках, внутри которого ключ от вашего. Вы отпираете свой замок и снимаете его, а потом отправляете ящик нам.
4. У нас теперь есть ящик с вашим ключом и нашим замком. Мы отпираем ящик своим ключом, вынимаем ваш ключ и кладём свой. Закрываем на свой замок. Дальше см. пункт 1. 

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

На посылку возможны другие атаки от подбора ещё одного ключа третьей стороной до проламывания стенки. 

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

Вся история с замками и ключами в цифровом мире держится на несимметричных операциях. Например, если вас попросить найти все делители числа 2701, это наверняка займёт какое-то время. Предположим, вы найдёте пару 37 и 73. И вот если развернуть задачу и сказать, что есть делители 37 и 73, и надо найти число, от которого они, то процесс пойдёт сильно быстрее. Всё держится на разнице в скорости решения задачи в одну и другую сторону. 

А знаете, кто у нас решает многие задачи в обе стороны почти одинаково быстро? Квантовые компьютеры! Нужны более сложные ассиметричные задачи, но это уже частично решённая задача.

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

В этом плане показателен пример шифра MD5, известного по мемам безопасников как Military-Grade Security Protocol. Предположим, вам надо проверять пароль к своему чату на чужом хостинге. Но вы не хотите сообщать пароль владельцу хостинга. Берёте свой пароль, применяете к нему сложную математическую операцию, получаете результат этой операции (хэш, например, 42). Хэш храните на хостинге. Когда кто-то вводит пароль, над ним проводится та же операция, и если результат не 42 — это не тот пароль. То есть владелец хостинга знает медленный сложный способ вычисления и ответ, но не знает пароль. Он может попробовать перебрать пароль, печально изыскивая тот, который даст ответ 42 после вычисления. Ассиметрия!

К сожалению, оказалось, что есть способ поменять память на время, и при огромных объёмах оперативки искать исходный пароль куда быстрее. То есть MD5 превратился в смешной алгоритм сжатия. А потом ещё обнаружилась атака коллизий, когда одному и тому же хэшу соответствовали разные пароли. В 2008 так взломали сертификаты X.509, а в 2012 — цифровую подпись MS. Мы пару раз встречали применение MD5 для шифрования персональных данных при обезличенной передаче в таргетинг, что для криптографов аналогично тому, как если бы вы оставили распечатку на турникете на Савёловской. Почитать про алгоритм можно по ссылкам на Вики.

Что на 100% защищает от подбора ключа — это одноразовые шифроблокноты. Которыми надо как-то поменяться до того, как вы начнёте отправлять друг другу сообщения. Это как заранее родиться с ключом от чьей-то посылки. Патент Вернама вот, а вот труды Моборна не были опубликованы из-за военной важности, и потом попали в учебники по криптографии (как матмодель) и исторические труды, в т.ч. эту работу. Доказательство математической невозможности их вскрыть сделано в 1949 Шенноном, вот оно.

-- 
Вступайте в ряды Фурье! Статистически, если вы подбросите монету достаточно много раз, она потребует консультации физика.