Шамир, Ади

В Википедии есть статьи о других людях с фамилией Шамир.

Ади Шамир
ивр. עדי שמיר‎
Шамир на конференции, 2009
Дата рождения	6 июля 1952(1952-07-06) (72 года)
Место рождения	Тель-Авив, Израиль
Страна	Израиль
Род деятельности	математик, криптолог, специалист в области информатики
Научная сфера	Информатика, криптография
Место работы	Институт Вейцмана
Альма-матер	Тель-Авивский университет, Институт Вейцмана
Научный руководитель	Зохар Манна
Известен как	RSA, Протокол Фейга-Фиата-Шамира, дифференциальный криптоанализ, Схема разделения секрета Шамира
Награды и премии	Премия Японии (2017)
Сайт	Home page on the site of The Weizmann Institute of Science
Медиафайлы на Викискладе

Ади Шамир (ивр. עדי שמיר‎, 6 июля 1952 года^[1], Тель-Авив, Израиль) — известный израильский криптоаналитик, учёный в области теории вычислительных систем, профессор информатики и прикладной математики в институте Вейцмана, лауреат премии Тьюринга. Член НАН Израиля (1998), иностранный член НАН США (2005)^[2], Французской академии наук (2015)^[3], Лондонского королевского общества (2018) и Американского философского общества (2019).

Введение

Ещё в 1977 году совместно с Рональдом Ривестом и Леонардом Адлеманом он разработал знаменитую криптосхему с открытым ключом RSA. В 80-е годы им были написаны ещё несколько аналитических работ, а также криптографических протоколов и криптосхем. В начале 90-х Шамир с Эли Бихамом разрабатывают основу современных методов исследования и вскрытия блочных шифров — дифференциальный криптоанализ. Сам он пишет на своем сайте так: «в течение последних нескольких лет я создал (при содействии моих студентов и коллег) новые реальные криптографические парадигмы, такие как:

• радио- и телевещательное кодирование (broadcast encryption), ring signatures и T-функции;
• новые криптоаналитические атаки против блочных шифров, потоковых шифров и ряд теоретических схем;
• и новые защитные методы от атак по сторонним каналам (side channel attacks), таких как атака по энергопотреблению (power analysis).»^[4]

В 2007 году, по сообщениям rnd.cnews.ru, Ади Шамир заявил, что для современных криптосистем серьёзная угроза таится в виде роста числа невыявленных ошибок, вызванных постоянным усложнением микропроцессоров. «Если спецслужбы обнаружат или скрытно внедрят в популярный микропроцессор алгоритм неправильного вычисления произведения только лишь одной пары чисел A и B (хотя бы в бите номер 0, то есть наименее значимом бите), то любой ключ в любой RSA-программе на любом из миллионов ПК с этим чипом может быть взломан с помощью единственного сообщения», — пишет Ади Шамир.^[5] Взлом может быть применен к любой системе, где задействованы открытые ключи, причем сейчас это не только ПК, но и телефоны и другие устройства.

Стоял у истоков NDS Group^[англ.] и долгие годы работал консультантом этой фирмы.

Биография

Шамир получил степень бакалавра от Тель-Авивского университета в 1973 году, поступил в институт Вейцмана, где получил степени магистра (1975) и доктора философии по информатике (1977). Его диссертация носила заголовок «The fixedpoints of recursive definitions»^[6]. Затем проработал год в качестве постдока в университете Уорик (Великобритания), после чего занимался исследованиями в MIT до 1980 года. После этого Шамир вернулся в институт Вейцмана, где и работает по сей день. С 2006 года также является приглашённым профессором в Высшей нормальной школе (Париж).

В 1979 году Ади Шамиром была разработана схема разделения секрета, математический метод для разбиения некого «секрета» на несколько «участников» для последующей реконструкции. В 1986 году он участвовал в разработке протокола аутентификации, названного впоследствии протоколом Фейга-Фиата-Шамира. Вместе со своим учеником Эли Бихамом (ивр. אלי ביהם‎) Шамир разработал дифференциальный криптоанализ, метод атаки на блочные шифры.

Метод дифференциального анализа

Основная статья: Дифференциальный криптоанализ

В 1990 году была опубликована работа Эли Бихама и Ади Шамира «Дифференциальный Криптоанализ DES-подобных Криптосистем».^[7] Это был новый метод атаки, применимый к шифрам замены/перестановки блочных симметричных криптосистем, подобных широко тогда распространенной DES (позже окажется, что эта же техника уже была известна корпорации IBM и Агентству национальной безопасности (NSA/CCS) США, но удержана в секрете, что подтверждает Брюс Шнайер в своей книге «Прикладная криптография»; Дон Копперсмит утверждает, что этот метод был известен команде разработчиков DES, но был засекречен; идея, близкая к методу дифференциального анализа, была опубликована С. Мёрфи ранее Э. Бихама и А. Шамира). Дифференциальный криптоанализ может взломать вплоть до 15-раундовый DES менее, чем за 2⁵⁶ шагов и, как сообщили авторы, показывает ключевую роль правил проектирования. Метод основан на атаках с выбором открытого текста, когда исследуются вероятности дифференциалов — сумм по модулю 2 пар шифротекстов, образованных от специальных открытых сообщений. Вслед за первой публикацией в 1991 году выходят статьи «Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer»^[8] и «Differential Cryptanalysis of Feal and N-Hash»^[9], где метод распространяется на хеш-функции Snefru и N-Hash и блочные шифры Khafre, REDOC-II, LOKI, Lucifer и FEAL.

В 1998 году Ади Шамир, Эли Бихам и Алекс Бирюков дали название методике Криптоанализа невозможных дифференциалов, впервые описанной Ларсом Кнудсеном. Также они выпустили книгу «Атаки вида потеря в середине»,^[10] разработав основанный на методе невозможных дифференциалов криптоанализ систем с сокращенным количеством раундов (например 31-м вместо 32-х). Вследствие этого и можно построить невозможный дифференциал от 2 сообщений, противоречащих друг другу в единственном бите в середине пути шифрования. Этим способом был вскрыт IDEA с 4 и 5 раундами, хотя сложность анализа составила 2¹¹² операций, и другие шифры — Skipjack, Khufu и Khafre.

В 1996 году Шамир и Бихам огласили «метод дифференциальных искажений» («Differential Fault Analysis» или DFA). Новая атака с одной стороны воплотила в себе известные к тому времени идеи, применявшие искажение вычислений для вскрытия систем с открытым ключом, с другой стороны, эти методы явились развитием метода дифференциального анализа. Суть состоит в том, что при искажении вычислений в процессе эксплуатации реальное шифрующее устройство выдаст другие данные, сравнение которых с неискаженными может облегчить восстановление секретных параметров устройства.

Другие работы

В 1982 году Ади Шамир раскрыл ранцевую криптосистему Меркля-Хеллмана, базирующуюся на асимметричном шифровании с лазейкой.

В декабре 1999 года Шамир и Алекс Бирюков описывают в своей статье нетривиальный и эффективный способ взлома алгоритма A5/1, публикуя «Real Time Cryptanalysis of the Alleged A5/1 on a PC»^[11]. Как говорит Шамир, это была сложная идея, осуществляющая применение нескольких небольших преимуществ для общего выигрыша. Здесь он обращается к слабостям в структуре регистров сдвига (хотя каждый компонент защиты коммуникаций GSM ослаблен компрометацией разведслужб^[12]).

В методе Шамира и Бирюкова есть 2 вида проверенных практически атак (вначале проводится несложная подготовка данных): первой необходим выход алгоритма в течение первых 2 минут разговора, и ключ вычисляется за примерно 1 секунду; второй, наоборот, необходима пара секунд разговора, а ключ вычисляется за несколько минут на обычном ПК.

На 28-й Международной конференции Crypto-2008 Ади Шамир продемонстрировал «кубические» атаки (cube attack), вскрывающие потоковые шифры. Этот новый вид атак полагается на представление функции потокового шифрования в виде «полиномиальных уравнений невысоких степеней». Как считает Брюс Шнайер (Bruce Schneier), «кубическая» атака может быть успешно применена к генераторам псевдо-случайных чисел, используемым в телефонах сетей системы GSM и устройствах Bluetooth. Уязвимы также сотовые телефоны и устройства RFID, использующие потоковые шифры. Ранее на конференции RSA в городе Сан-Хосе Шамир показал несостоятельность RFID-чипов, предлагавшихся для электронных паспортов, и по такой причине: используя направленную антенну и цифровой осциллограф, он обнаружил характерную картину показаний потребления электроэнергии чипами для правильных и неправильных битов пароля.

Награды

• 1983 — Премия Эрдёша^[13]
• 1986 — IEEE W.R.G. Baker Award^{[англ.][14]}
• 1987 — Премия Вейцмана за исследования в области точных наук
• 1990 — UAP Scientific Prize
• 1992 — Золотая медаль Пия XI^[1]
• 1994 — Ротшильдовская премия
• 1996 — Премия Канеллакиса^[15]
• 2000 — IEEE Премия в области компьютеров и коммуникаций имени Кодзи Кобаяси^[16]
• 2002 — Премия Тьюринга, «за уникальный вклад по увеличению практической пользы систем шифрования с открытым ключом»^[17]
• 2008 — Государственная премия Израиля
• 2008 — Премия Окава
• 2009 — C&C Prize
• 2012 — Гранд-медаль Французской академии наук
• 2017 — Премия Японии
• 2017 — BBVA Foundation Frontiers of Knowledge Award

Примечания

1. The Emergence of Complexity in Mathematics, Physics, Chemistry and Biology: Proceedings, Plenary Session of the Pontifical Academy of Sciences, 27-31 October 1992 Архивная копия от 28 марта 2018 на Wayback Machine (англ.)
2. Adi Shamir  (неопр.). Дата обращения: 17 мая 2019. Архивировано 24 марта 2019 года.
3. Adi Shamir | Liste des membres de l'Académie des sciences / S | Listes par ordre alphabétique | Listes des membres | Membres | Nous connaître  (неопр.). Дата обращения: 22 декабря 2018. Архивировано 22 декабря 2018 года.
4. Adi Shamir  (неопр.). Дата обращения: 17 февраля 2009. Архивировано 1 декабря 2008 года.
5. RSA-защита становится эфемерной Архивная копия от 5 ноября 2008 на Wayback Machine, rnd.cnews.ru  (Дата обращения: 23 декабря 2009)
6. Shamir, Adi. The fixedpoints of recursive definitions : [англ.]. — Weizmann Institute of Science, October 1976.
7. Eli Biham, Adi Shamir. Differential cryptanalysis of DES-like cryptosystems // CRYPTO'90 & Journal of Cryptology. — 1991. — Т. 4, вып. 1. — С. 3—72. Архивировано 14 мая 2011 года.
8. Eli Biham, Adi Shamir. Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer // CRYPTO'91. — 1991. Архивировано 14 мая 2011 года.
9. Eli Biham, Adi Shamir. Differential cryptanalysis of Feal and N-Hash // EUROCRYPT'91. — 1991. Архивировано 14 мая 2011 года.
10. Biham E., Biryukov A., Shamir A. Miss in the Middle Attacks on IDEA and Khufu (англ.) // Fast Software Encryption: 6th International Workshop, FSE’99 Rome, Italy, March 24–26, 1999 Proceedings / L. R. Knudsen — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 1999. — P. 124—138. — (Lecture Notes in Computer Science; Vol. 1636) — ISBN 978-3-540-66226-6 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-48519-8_10
11. Real Time Cryptanalysis of A5/1 on a PC
12. Система профессионального тестирования и мониторинга GSM: Берд Киви. Гигабайты власти  (неопр.). Дата обращения: 23 декабря 2009. Архивировано из оригинала 12 февраля 2009 года.
13. erdos_prize_t – Israel Mathematical Union  (неопр.). Дата обращения: 17 февраля 2009. Архивировано 22 июня 2007 года.
14. IEEE — IEEE Medals, Technical Field Awards, and Recognitions  (неопр.). Дата обращения: 17 февраля 2009. Архивировано 4 февраля 2009 года.
15. ACM Award Citation / Adi Shamir Архивировано 6 апреля 2009 года.
16. IEEE — IEEE Medals, Technical Field Awards, and Recognitions  (неопр.). Дата обращения: 17 февраля 2009. Архивировано 25 октября 2008 года.
17. ACM Award Citation / Adi Shamir  (неопр.). Дата обращения: 17 февраля 2009. Архивировано из оригинала 6 июля 2007 года.

Ссылки

• Сайт профессора Шамира Архивная копия от 1 декабря 2008 на Wayback Machine при институте Вейцмана (англ.)
• Crypt-OpenSSL-RSA Архивная копия от 12 января 2010 на Wayback Machine — бесплатный XS Perl модуль c базовой функциональностью RSA, Ian Robertson