Ади Шамир

Ади Шамир — израильский криптограф, один из создателей криптосистемы RSA, криптоаналитик, соавтор ряда фундаментальных алгоритмов и протоколов в области защиты информации. Наиболее известен как соразработчик алгоритма RSA, за что вместе с Роном Ривестом и Леонардом Адлеманом был удостоен премии Тьюринга (2002). Шамир также является автором алгоритма Шамира (разделение секрета), атаки «встреча посередине» и ряда других значимых работ в криптографии и криптоанализе.

Биография

Ади Шамир родился 6 июля 1952 года в Тель-Авиве, Израиль. В 1973 году получил степень бакалавра по математике в Тель-Авивском университете. Продолжил обучение в США: в 1975 году получил степень магистра по информатике в Иллинойсском университете в Урбане-Шампейне, а в 1977 году — докторскую степень (PhD) по информатике в Станфордском университете под руководством Роберта Флойда. Во время работы в Массачусетском технологическом институте (MIT) в 1977–1980 годах совместно с Роном Ривестом и Леонардом Адлеманом разработал криптосистему RSA, названную по первым буквам их фамилий. Впоследствии Шамир работал в Научно-исследовательском институте Вейцмана (Израиль), а также сотрудничал с IBM, Bell Labs и другими организациями. С 1980-х годов занимается как теоретическими, так и прикладными аспектами криптографии и компьютерной безопасности. В 2017 году был избран иностранным членом Российской академии наук.

Научные достижения

Алгоритм RSA

Основным вкладом Шамира в криптографию стала разработка алгоритма RSA, который стал первым практически применимым алгоритмом асимметричного шифрования (с открытым ключом). RSA основан на сложности факторизации больших целых чисел — разложения произведения двух простых чисел на множители. Этот алгоритм лёг в основу многих современных систем шифрования, в том числе протоколов HTTPS, SSL/TLS, электронной подписи и цифровых сертификатов. За эту работу в 2002 году Шамир, Ривест и Адлеман получили премию Тьюринга, высшую награду в области информатики.

Схема разделения секрета (схема Шамира)

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

Атака «встреча посередине»

Шамир является соавтором (совместно с Уитфилдом Диффи) метода криптоанализа, названного атакой «встреча посередине» (meet-in-the-middle). Эта атака направлена против блочных шифров, использующих двойное шифрование (например, двойной DES). Атака позволяет сократить время перебора ключей с 2^(2n) до 2^(n+1) с использованием пространства памяти. Атака показала, что простое удвоение ключа не даёт ожидаемого удвоения стойкости, что привело к разработке тройного шифрования (Triple DES).

Криптоанализ RSA

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

Прочие достижения

• Алгоритм Шамира (дискретный логарифм) — один из ранних методов решения задачи дискретного логарифмирования.
• Схема подписи Фиата — Шамира — метод аутентификации и цифровой подписи, основанный на сложности извлечения квадратных корней по модулю.
• Двухъядерная архитектура — концепция «алгоритма с доказательно нулевым разглашением», используемая в протоколах идентификации.
• Криптоанализ шифра A5/1 (с соавторами) — анализ алгоритма шифрования, используемого в сотовой связи GSM. В 1994 году Шамир с коллегами показал возможность атаки с известным открытым текстом, что ставило под сомнение стойкость этого алгоритма.
• Разработка криптоаналитического метода «атаки на основе выбора текста с открытым ключом», а также исследование уязвимостей в криптографических протоколах, включая SSL/TLS.

Награды и признание

• Премия Тьюринга (2002) — совместно с Р. Ривестом и Л. Адлеманом за разработку алгоритма RSA.
• Премия Парижа Канеллакиса (2004) — за вклад в криптографию и безопасность компьютерных систем.
• Премия фонда Вольфа (2008) — за фундаментальный вклад в криптографию.
• Премия Израиля (2010) — высшая государственная награда Израиля в области точных наук.
• Член Национальной академии наук США (2012), иностранный член Российской академии наук (2017).
• Почётные докторские степени ряда университетов.

Критика

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

Источники

• Rivest R. L., Shamir A., Adleman L. M. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. — 1978. — Vol. 21, No. 2. — P. 120–126.
• Shamir A. How to share a secret // Communications of the ACM. — 1979. — Vol. 22, No. 11. — P. 612–613.
• Diffie W., Shamir A. A new attack on double encryption // IEEE Transactions on Information Theory. — 1981. — Vol. 27, No. 4. — P. 461–465.
• Fiat A., Shamir A. How to prove yourself: Practical solutions to identification and signature problems // Advances in Cryptology — CRYPTO’86. — Springer, 1987.
• Biryukov A., Shamir A., Wagner D. Real time cryptanalysis of A5/1 on a PC // Fast Software Encryption — FSE 2001. — Springer, 2001.
• Бирюков А., Шамир А. Атаки на криптосистемы: принципы и практика. — М.: Мир, 2005.
• Премия Тьюринга 2002 года / ACM A. M. Turing Award. — Association for Computing Machinery.