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

1 августа 1977 года научно-популярный журнал Scientific American выпустил свое ежемесячное издание, публикуемое с 1921 года. Это – интересная смесь математики, естественных наук, техники, биологии, механики, географии и других дисциплин. В конце публикации на странице 120 была опубликована короткая статья популярного математика Мартина Гарднера под названием "Математические игры".

В ней он описал "новый вид шифра, для взлома которого потребуются миллионы лет".

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

Что нужно миру, так это... шифрование, не требующее доверия

До 1977 года в криптографии доминировали потоковые шифры и, в частности, шифр Вернама. Шифр Вернама – это случайная последовательность букв или битов, которая при соединении с исходным сообщением создает псевдослучайную последовательность. Не зная одноразового ключа, невозможно расшифровать зашифрованное сообщение. Но если вы знаете ключ, то извлечь исходное сообщение из шифра – тривиальная задача.

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

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

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

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

Назревает цифровая буря...

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

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

ARPANET (распределенная сеть с коммутацией пакетов и предшественница современного интернета) уже существовала и использовалась в различных корпоративных и академических центрах. TCP (протокол управления передачей, протокол, ориентированный на соединение, используемый интернетом) и FTP (протокол передачи файлов, используемый для передачи компьютерных файлов между клиентом и сервером в сети) также уже использовались. Были изобретены различные формы обмена электронными сообщениями “тет-а-тет”, такие как FTPmail и Mail Protocol (который в 80-х годах превратился в электронную почту с использованием SMTP), которые использовались для отправки почтовых сообщений через ARPANET. В 1965 году Гордон Мур, тогдашний генеральный директор Intel, предсказал ежегодное удвоение количества компонентов на интегральную схему (в 1975 году он изменил прогноз на удвоение каждые два года). Его предсказание стало известно как закон Мура и обещало постоянный и устойчивый прогресс в цифровой электронике и аппаратном обеспечении.

Такие компьютерные компании, как Intel, IBM, SAP и Honeywell, уже были хорошо известны. Двумя годами ранее два молодых предпринимателя основали компанию в Альбукерке, штат Нью-Мексико, для разработки и продажи интерпретаторов языка BASIC для Altair 8800. А за год до этого другой молодой предприниматель стал соучредителем компании в доме своего детства на Крист Драйв в Лос Альтос, Калифорния. Этими компаниями были Microsoft и Apple соответственно.

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

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

Загадки Меркла – первая попытка решить проблему

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

Протокол работает следующим образом:

1. Предположим, что Алиса и Боб хотят безопасно общаться.
2. Алиса создает большое количество головоломок (математическая задача, которую трудно, но не невозможно решить).
3. Боб случайным образом выбирает одну из присланных ему головоломок и решает ее.
4. Расшифрованное решение содержит идентификатор и ключ сеанса (который будет служить ключом для их общения). Боб передает идентификатор обратно Алисе, тем самым указывая ей, какую головоломку он решил.
5. Теперь у обеих сторон есть общий ключ: у Боба – потому что он решил головоломку, а у Алисы – потому что она отправила головоломку.
6. Любая подслушивающая сторона (скажем, Ева) имеет более сложную задачу, поскольку она не знает, какую из головоломок решил Боб. Ее лучшая стратегия – решить все головоломки, но поскольку их очень много, это требует бóльших вычислительных затрат для Евы, чем для Боба.

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

В наши дни временнáя сложность, как правило, не считается достаточно безопасной защитой от злоумышленника в контексте практических реальных криптографических приложений. Кроме того, протокол Merkle Puzzle требует, чтобы Алиса придумала большое количество головоломок и отправила их Бобу. Это, очевидно, представляет собой довольно большой объем работы для Алисы, а также довольно большой объем сетевого трафика между Алисой и Бобом. Учитывая эти требования, данный протокол считается слишком неэффективным для практического использования. Однако не следует забывать о значимости вклада Меркла. Это была первая реализация схемы, в которой два участника могут придумать ключ "на лету", и в которой существует значительный разрыв между количеством работы, необходимой участникам, чтобы придумать ключ, и количеством работы, необходимой злоумышленнику, чтобы взломать его. Эта работа также послужила источником вдохновения для нового протокола распределения ключей, разработанного два года спустя...

Важный теоретический прорыв

Вдохновленные работой Меркла, 6 ноября 1976 года два профессора Гарварда, Уитфилд Диффи и Мартин Хеллман, опубликовали теоретическую работу, в которой были решены многие давние проблемы, связанные с не требующим доверия шифрованием и распределением ключей.

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

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

Протокол использует математические свойства, чтобы гарантировать, что:

• E является обратным D
• вычислить E и D легко
• нахождение D из E является вычислительно невыполнимым (т.е. *очень* трудным)
• E может быть публично раскрыто без нарушения целостности D (исходя из условия выше).

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

Каким образом?

1. Пользователь (Боб) генерирует пару обратных преобразований E и D.
2. Расшифровывающее преобразование D должно храниться в секрете и не должно никому сообщаться.
3. Ключ шифрования E можно сделать публичным, поместив его в публичный каталог вместе с именем и адресом Боба.
4. Любой человек (скажем, Алиса) может найти в каталоге публичный ключ Боба E, зашифровать сообщения с помощью E и отправить их Бобу, но никто другой не сможет расшифровать сообщения, предназначенные Бобу, кроме самого Боба (который использует для этого D).

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

Разработана практическая односторонняя функция

Рональд Ривест и Ади Шамир были программистами из Массачусетского технологического института, а Лен Адлеман – математиком.

Работа Диффи-Хеллмана захватила их воображение, и они попытались найти реализацию, которая удовлетворяла бы его спецификациям. Когда Ривест или Шамир предлагали новую теоретическую схему, Адлеман обычно отвергал ее после нескольких минут анализа. Около полуночи во время седера Пасхи в 1977 году Ривест позвонил Адлеману с идеей использовать факторизацию простых чисел в качестве функции-ловушки. Адлеману не удалось найти в этой идее никаких дыр. (На самом деле, спустя более 40 лет никому так и не удалось этого сделать).

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

Простые числа – числа больше единицы, которые делятся только на единицу и сами на себя – обладают особыми математическими свойствами, которые интриговали математиков на протяжении веков. Блестящая идея Ривеста, Шамира и Адлемана заключалась в том, чтобы использовать эти свойства простых чисел для создания практичной и эффективной функции-ловушки.

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

1. Найдите два простых числа P и Q (обычно каждое из них состоит из сотен цифр) и перемножьте их вместе, чтобы получить их произведение, называемое N.
2. Сгенерируйте число, называемое функцией Эйлера и обозначаемое φ(N), которое рассчитывается как (P-1) * (Q-1). Это число представляет собой количество целых чисел, взаимно простых с N (за исключением числа 1, которое относительно просто к каждому ненулевому целому числу).
3. Найдите число E (ключ шифрования), которое взаимно просто с числами N и φ(N).
4. Определите число D (ключ дешифрования), которое является обратным по модулю числа E. Это вычисляется с помощью уравнения E * D = 1 (mod φ(N)).
5. Публичный ключ – это число N и число E.
6. Приватный ключ – число N и число D.

Шифр достигается путем возведения сообщения в степень E mod N. Расшифровка достигается путем возведения шифра в степень D mod N.

C ≡ Mᴱ mod N
M ≡ Cᴰ mod N

(операция "mod", используемая выше, описана здесь).

Заключительные замечания

Хотя Ривест, Шамир и Адлеман опубликовали свою работу в апреле 1977 года, именно публикация в журнале Scientific American 4 месяца спустя оповестила мир об их открытии и ознаменовала начало новой эры криптографии.

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

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

"Каждая компания, каждый гражданин теперь обрели доступ к тем видам криптографических технологий, которые еще не так давно были источником силы наряду с атомной бомбой".

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

Поэтому мы можем с уверенностью предположить, что эти протоколы и стандарты будут работать еще долго.

Оригинал статьи на английском.