Серия «Кто владеет ключами», часть 2. Человек, который не хотел быть в истории
Леонард Адлеман не собирался становиться криптографом.
В юности он хотел быть химиком — насмотрелся передачи Mr. Wizard. Потом врачом — вдохновился друзьями по студенческому братству. В математику его привёл школьный учитель английского, который дал прочитать «Гамлета» и показал, что можно «видеть вещи глубже, чем на поверхности».
В 1976 году Адлеман работал в MIT. Двое его коллег — Рон Ривест и Ади Шамир — были одержимы задачей, которую поставили Диффи и Хеллман: найти практическую реализацию криптографии с открытым ключом. Концепция существовала, но работающего алгоритма не было.
Ривест и Шамир генерировали идеи. Адлеман их ломал.
Это продолжалось почти год. Десятки схем — и каждая разбивалась о математическую реальность. В какой-то момент им казалось, что задача вообще нерешаема: требования противоречат друг другу.
Ночь, которая всё изменила
Апрель 1977 года. Троица провела вечер Песаха у знакомого студента. Вина было много — сладкого кошерного Manischewitz.
Ривест вернулся домой около полуночи и не мог заснуть. Лёг на диван с учебником математики. Стал думать об односторонних функциях — тех, которые легко вычислить в одну сторону и практически невозможно обратить.
К рассвету у него была готова бо́льшая часть статьи.
Идея оказалась элегантной до обидного. Перемножить два огромных простых числа — легко. Разложить результат обратно на множители — вычислительно неподъёмно. На этой асимметрии можно построить всё: и шифрование, и цифровые подписи.
Утром Ривест принёс черновик Адлеману. Тот прочитал, попробовал найти дыру — и не нашёл.
Зато нашёл другую проблему.
«Убери моё имя»
«Я сказал Рону убрать меня из авторов, — вспоминал Адлеман. — Это его изобретение, не моё. Я только ломал чужие идеи, а эту сломать не смог».
Ривест отказался. Они проспорили до следующего дня.
Адлеман предложил компромисс: пусть его имя будет последним. В алфавитном порядке — Adleman, Rivest, Shamir — он стоял бы первым. Но алгоритм назвали RSA, а не ARS.
«Я думал, что эта статья будет наименее интересной из всех, на которых когда-либо появится моя подпись», — признавался Адлеман позже.
Он ошибся. Это стала самая цитируемая работа в его карьере.
Когда математика опережает журналы
Статья «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems» вышла в журнале Communications of the ACM в феврале 1978 года. Но к тому моменту RSA уже была знаменита.
Летом 1977-го, ещё до официальной публикации, Ривест отправил черновик Мартину Гарднеру — автору легендарной колонки «Mathematical Games» в Scientific American. Гарднер был настолько впечатлён, что нарушил собственное правило планировать материалы заранее.
В августе 1977 года вышла колонка под заголовком «Новый тип шифра, который потребует миллионов лет на взлом». Гарднер объяснил идею широкой аудитории и бросил вызов читателям: зашифрованное сообщение с ключом из 129 цифр, приз сто долларов тому, кто расшифрует.
Криптография впервые попала в массовую прессу — за полгода до академического журнала.
Спрятанная фраза была: «The magic words are squeamish ossifrage». Брезгливый ягнятник. Выбрали за абсурдность, чтобы никто не угадал случайно.
Ривест оценил время взлома: около сорока квадриллионов лет.
На деле ушло семнадцать. В 1994 году международная группа из шестисот добровольцев, координируясь через интернет, взломала ключ за шесть месяцев. В 2015-м исследователь повторил это за 47 минут на облачных серверах.
Не потому что RSA «сломан» — просто 129 цифр оказалось мало. Сегодня используют ключи в тысячи бит. Но история с ягнятником хорошо показывает: криптография — не талисман, а инженерия. Параметры устаревают, мощности растут.
Патент, банкротство, империя
А дальше началось то, чего академический мир не ожидал.
RSA запатентовали. Патент US 4405829 — подан в декабре 1977-го, выдан в сентябре 1983-го. Криптографический алгоритм стал интеллектуальной собственностью.
В том же 1983 году авторы основали компанию RSA Data Security. Идея казалась очевидной: раз алгоритм запатентован, можно продавать лицензии.
Реальность оказалась жёстче. Компьютеры восьмидесятых не тянули тяжёлую математику RSA. Рынка не было. К 1986 году компания стояла на грани банкротства.
Спас её Джим Бидзос — бизнесмен, пришедший на позицию CEO. В 1987 году Lotus встроила RSA в Lotus Notes. За ней потянулись Motorola, Apple, Novell. В 1988-м Руперт Мёрдок предложил купить компанию за несколько миллионов.
К середине девяностых RSA Data Security стоила двести миллионов долларов.
Патент истекал в сентябре 2000 года. За две недели до срока компания выпустила алгоритм в общественное достояние — символический жест. Монополия на математику в интернете всё равно долго не работает.
Странное положение
Возникла парадоксальная ситуация.
С одной стороны, правительство США рассматривало криптографию как оружие. Экспорт ограничен. Публикации под подозрением. Исследователи рискуют попасть под статью.
С другой стороны, криптография стала товаром. Патенты, лицензии, венчурный капитал. Компании платят роялти за право использовать алгоритм.
Одно и то же знание — одновременно «слишком опасное для распространения» и «достаточно ценное для продажи».
Этот парадокс взорвётся в девяностых, когда программист по имени Фил Циммерман выложит в интернет программу PGP, использующую RSA, — и попадёт под уголовное расследование за «незаконный экспорт вооружений». Но это уже следующая история.
Человек, который ушёл
А что Адлеман?
Он получил премию Тьюринга в 2002 году — вместе с Ривестом и Шамиром, за ту самую «наименее интересную» статью.
К тому моменту он давно занимался другим.
В восьмидесятых Адлеман заметил сходство между тем, как фермент полимераза копирует ДНК, и тем, как работает машина Тьюринга. Лента с символами, головка, которая читает и пишет. Только вместо битов — молекулы.
В 1994 году он опубликовал статью о ДНК-вычислениях: использование биологических молекул для решения комбинаторных задач. Его называют «отцом ДНК-компьютинга».
Он также боксёр-любитель, тренировавшийся с профессиональными чемпионами. Консультант фильма «Sneakers» с Робертом Редфордом — для него Адлеман придумал реплику «прорыв гауссовых пропорций», чтобы «принц математиков мог получить немного рекламы».
Человек, который не хотел быть в истории криптографии, стал её частью помимо собственной воли — и ушёл строить другую историю.
Что осталось
RSA — не просто алгоритм. Это момент, когда криптография перестала быть чистой наукой и стала индустрией.
До RSA шифрование было либо государственной тайной, либо академическим упражнением. После RSA появились патенты, компании, продукты, рынок. Математика превратилась в товар.
Это изменило расклад сил. Теперь не только правительства владели сильным шифрованием — им владели корпорации. А значит, скоро им смогут владеть и обычные люди.
Государству это не понравилось.
Продолжение: Первая священная война
Источники
- A Method for Obtaining Digital Signatures and Public-Key Cryptosystems — оригинальная статья RSA, 1978
- The Magic Words are Squeamish Ossifrage — история криптографического вызова
- Leonard Adleman — MacTutor — биография с деталями о Mr. Wizard, Гамлете и ДНК
- RSA Security — Company History — история компании, банкротство 1986, роль Бидзоса
- Leonard Adleman — A.M. Turing Award — биография лауреата
- RSA Cryptosystem — Wikipedia — история Пасхальной ночи и «наименее интересной статьи»
- Patent US4405829 — патент на RSA