Джеймс Эллис

Джеймс Эллис (англ. James Ellis; 19 мая 1924, Сидней — 10 ноября 1997, Канберра) — австралийский инженер-электрик, криптограф и математик, наиболее известный своей пионерской работой в области криптографии с открытым ключом. В 1970 году, работая в британском Центре правительственной связи (GCHQ, Government Communications Headquarters), он теоретически обосновал возможность создания системы шифрования, не требующей предварительного обмена секретным ключом между отправителем и получателем. Его идеи, изложенные во внутреннем отчёте GCHQ, легли в основу алгоритмов, которые позже были независимо переоткрыты и публично представлены Уитфилдом Диффи, Мартином Хеллманом и Ральфом Мерклом. Вклад Эллиса оставался засекреченным до 1997 года.

Биография

Ранние годы и образование

Джеймс Генри Эллис родился 19 мая 1924 года в Сиднее, Австралия. Его отец, Генри Эллис, был банковским служащим, а мать, Этель Мэй Эллис (урождённая Грей), занималась домашним хозяйством. Семья часто переезжала, и Джеймс посещал несколько школ, прежде чем поступить в престижный Сиднейский технический колледж (Sydney Technical College). В 1943 году он получил диплом инженера-электрика.

Во время Второй мировой войны Эллис служил в Австралийских имперских силах (Australian Imperial Force), где занимался радиолокационными системами и телекоммуникациями. После войны он продолжил обучение в Имперском колледже Лондона (Imperial College London), который окончил в 1948 году со степенью бакалавра наук по электротехнике.

Карьера в GCHQ

После окончания колледжа Эллис остался в Великобритании и в 1949 году поступил на работу в GCHQ — британскую разведывательную службу, занимающуюся радиоэлектронной разведкой и криптографией. Первоначально он работал над системами связи, но вскоре переключился на криптографические исследования. В GCHQ он проработал до выхода на пенсию в 1985 году, занимая должность главного инженера-криптографа.

Последние годы

После выхода на пенсию Эллис продолжал консультировать GCHQ по вопросам криптографии. Он скончался 10 ноября 1997 года в Канберре, Австралия, куда переехал после смерти жены. Только после его смерти, в 1997 году, GCHQ рассекретил его работу, и Эллис получил признание как один из первооткрывателей криптографии с открытым ключом.

Открытие криптографии с открытым ключом

Контекст и предпосылки

До 1970-х годов все известные системы шифрования были симметричными: для шифрования и расшифровки сообщения требовался один и тот же секретный ключ, который должен был быть заранее передан отправителю и получателю по защищённому каналу. Эта проблема, известная как «проблема распределения ключей», была фундаментальным ограничением криптографии.

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

Теоретическое обоснование

В 1970 году Эллис написал внутренний отчёт GCHQ под названием «Возможность несекретного шифрования» (The Possibility of Non-Secret Encryption). В этом документе он впервые математически сформулировал концепцию криптографии с открытым ключом. Он показал, что если существует односторонняя функция с потайным входом (trapdoor one-way function) — функция, которую легко вычислить в одном направлении, но практически невозможно обратить без знания секретной информации (потайного входа), — то можно построить систему, где ключ шифрования является открытым, а ключ расшифровки — секретным.

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

Развитие идей: Клиффорд Кокс и Малкольм Уильямсон

Идеи Эллиса не были немедленно реализованы, так как ни он, ни его коллеги не могли найти подходящую одностороннюю функцию. В 1973 году к работе подключился молодой математик Клиффорд Кокс (Clifford Cocks), который, ознакомившись с отчётом Эллиса, предложил первую практическую реализацию — алгоритм, основанный на сложности разложения больших чисел на простые множители. Этот алгоритм был идентичен тому, что позже стал известен как RSA (Rivest–Shamir–Adleman).

В 1974 году другой сотрудник GCHQ, Малкольм Уильямсон (Malcolm Williamson), разработал протокол обмена ключами, аналогичный протоколу Диффи — Хеллмана. Таким образом, все три ключевых элемента криптографии с открытым ключом (концепция, алгоритм RSA и протокол обмена ключами) были открыты в GCHQ на несколько лет раньше, чем в академической среде.

Признание и наследие

Засекреченность

Вся работа Эллиса, Кокса и Уильямсона была строго засекречена в соответствии с британским Законом о государственной тайне (Official Secrets Act). Они не могли публиковать свои результаты или обсуждать их с кем-либо за пределами GCHQ. В результате, когда в 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали свою работу «Новые направления в криптографии» (New Directions in Cryptography), а в 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман представили алгоритм RSA, эти открытия стали мировой сенсацией и принесли авторам широкую известность.

Рассекречивание

В 1997 году, после того как алгоритм RSA и протокол Диффи — Хеллмана стали общепринятыми стандартами, GCHQ решил рассекретить часть своих ранних работ. В декабре 1997 года были опубликованы отчёты Эллиса, Кокса и Уильямсона. Это вызвало значительный интерес в криптографическом сообществе, так как подтвердило, что британские криптографы сделали те же открытия на несколько лет раньше.

Оценка вклада

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

В 2000 году, уже посмертно, Эллис был награждён премией IEEE Richard W. Hamming Medal (совместно с Коксом и Уильямсоном) за выдающийся вклад в информационные науки и системы. Его имя также внесено в Зал славы криптографии (Cryptography Hall of Fame).

Интересные факты

• Эллис был известен своим эксцентричным характером. Он часто работал по ночам, а днём спал, и предпочитал записывать идеи на салфетках и клочках бумаги.
• По свидетельствам коллег, Эллис не был математиком-теоретиком, а скорее инженером-практиком, который мыслил нестандартно. Именно это позволило ему задать вопрос, который до него никто не ставил.
• Когда в 1976 году Диффи и Хеллман опубликовали свою работу, Эллис, по слухам, был раздосадован тем, что не может публично заявить о своём приоритете из-за секретности.
• Несмотря на то, что Эллис, Кокс и Уильямсон опередили своих американских коллег, их работа не оказала прямого влияния на развитие криптографии, так как оставалась неизвестной. Именно публичные работы Диффи, Хеллмана, Ривеста, Шамира и Адлемана стимулировали развитие этой области.

Источники

• James Ellis. The Possibility of Non-Secret Encryption (1970). Рассекреченный отчёт GCHQ.
• Clifford Cocks. A Note on 'Non-Secret Encryption' (1973). Рассекреченный отчёт GCHQ.
• Malcolm J. Williamson. Non-Secret Encryption Using a Finite Field (1974). Рассекреченный отчёт GCHQ.
• Levy, Steven. Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age. Viking, 2001.
• Singh, Simon. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Doubleday, 1999.
• Некролог Джеймса Эллиса в газете The Times (1997).
• Статья «James Ellis (cryptographer)» в Википедии (англ.).