Питер Монтгомери

Питер Монтгомери (англ. Peter Montgomery; 13 августа 1947, Ланкастер, Пенсильвания, США — 21 января 2024, там же) — американский программист, математик и криптограф, известный разработкой алгоритмов, лежащих в основе современной криптографии с открытым ключом. Наиболее значимые достижения — алгоритм Монтгомери для модульного умножения (1985) и метод эллиптических кривых для факторизации чисел (ECM, 1987). Внёс вклад в развитие криптосистемы RSA, протоколов Диффи — Хеллмана и стандартов цифровой подписи.

Биография

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

Питер Монтгомери родился в семье инженера-электрика. В 1965 году поступил в Калифорнийский университет в Беркли, где изучал математику. В 1969 году получил степень бакалавра, а в 1972 году — магистра по математике. В 1974 году защитил докторскую диссертацию (Ph.D.) по теории чисел в Калифорнийском университете в Лос-Анджелесе (UCLA). Тема диссертации касалась распределения простых чисел в арифметических прогрессиях.

Карьера

После защиты диссертации Монтгомери работал в Лаборатории реактивного движения (JPL) НАСА в Пасадине, где занимался численным анализом и разработкой алгоритмов для космических программ. В 1980-х годах перешёл в компанию Microsoft Research, где проработал до выхода на пенсию в 2012 году. В Microsoft Research его исследования были сосредоточены на криптографии, теории чисел и высокопроизводительных вычислениях. Параллельно с 1990-х годов сотрудничал с Центром прикладной математики Национального института стандартов и технологий (NIST).

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

Алгоритм Монтгомери (модульное умножение)

В 1985 году Монтгомери опубликовал статью «Modular Multiplication Without Trial Division», в которой описал метод, позволяющий выполнять модульное умножение (a × b mod n) без операции деления, которая является ресурсоёмкой для компьютеров. Алгоритм преобразует числа в специальную форму (представление Монтгомери), что позволяет заменить деление на сдвиги и сложения. Это ускорило вычисления в криптосистемах с открытым ключом, таких как RSA и Диффи — Хеллман, в 2–4 раза. Алгоритм стал стандартом в аппаратных реализациях криптографических чипов (например, в смарт-картах и процессорах Intel с поддержкой AES-NI).

Метод эллиптических кривых для факторизации (ECM)

В 1987 году Монтгомери разработал метод факторизации целых чисел с использованием эллиптических кривых (Elliptic Curve Method, ECM). Этот алгоритм эффективен для нахождения небольших (до 50–60 десятичных знаков) простых делителей больших составных чисел. ECM стал основой для многих рекордов факторизации, в том числе для чисел длиной до 1000 бит. Метод используется в криптоанализе для проверки стойкости ключей RSA.

Вклад в криптографию эллиптических кривых

Монтгомери внёс важные усовершенствования в арифметику эллиптических кривых. Он предложил так называемую «лестницу Монтгомери» (Montgomery ladder) — метод вычисления скалярного умножения точки на эллиптической кривой, устойчивый к атакам по сторонним каналам (например, по времени выполнения или потреблению энергии). Этот метод используется в протоколах Curve25519 и Curve448, разработанных Дэниелом Бернштейном, а также в стандартах TLS 1.3 и Signal.

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

• Алгоритм Монтгомери для вычисления обратных величин — метод нахождения обратного элемента по модулю без деления.
• Участие в разработке стандарта SHA-3 — Монтгомери входил в экспертную группу NIST по отбору кандидатов для нового хеш-алгоритма.
• Исследования в области теории чисел — работы по распределению простых чисел, гипотезе Римана и алгоритмам проверки простоты.

Применение

Криптография

Алгоритмы Монтгомери лежат в основе практически всех современных криптографических библиотек: OpenSSL, GnuTLS, libgcrypt, Bouncy Castle. Они используются в:

• RSA — для шифрования и цифровой подписи.
• Диффи — Хеллман — для обмена ключами.
• Эллиптическая криптография — в протоколах ECDH, ECDSA, EdDSA.
• Постквантовая криптография — в некоторых кандидатах на стандарты NIST (например, в алгоритмах на основе решёток).

Аппаратная реализация

Алгоритм Монтгомери реализован в виде инструкций в процессорах Intel (начиная с архитектуры Skylake) и ARM (начиная с Cortex-A72). Это позволяет выполнять криптографические операции на порядок быстрее по сравнению с программными реализациями.

Факторизация чисел

Метод ECM используется в распределённых проектах по факторизации (например, Mersenne Forum, NFS@Home) для поиска делителей чисел Мерсенна и других составных чисел. Без ECM невозможно было бы проверить простоту многих больших чисел.

Критика и ограничения

• Алгоритм Монтгомери требует предварительного преобразования чисел в специальную форму, что добавляет вычислительные накладные расходы при однократном умножении. Однако при многократных операциях (как в RSA) эти затраты окупаются.
• Метод ECM неэффективен для факторизации чисел, состоящих из двух больших простых множителей (например, стандартных RSA-ключей длиной 2048 бит). Для таких чисел применяются более сложные алгоритмы (GNFS).
• Лестница Монтгомери, хотя и устойчива к атакам по времени, может быть уязвима для атак по мощности (power analysis) при неправильной реализации.

Признание

• В 2013 году Монтгомери получил премию RSA за выдающийся вклад в криптографию (RSA Conference Award for Excellence in Mathematics).
• В 2018 году его имя было включено в Зал славы криптографии (Cryptography Hall of Fame) при Международной ассоциации криптологических исследований (IACR).
• В 2020 году журнал IEEE Spectrum назвал алгоритм Монтгомери одним из «10 алгоритмов, изменивших мир».

Личная жизнь

Питер Монтгомери был женат, имел двоих детей. Увлекался классической музыкой и игрой на фортепиано. Скончался 21 января 2024 года в возрасте 76 лет от осложнений, вызванных онкологическим заболеванием.

Память

После смерти Монтгомери многие криптографические сообщества (включая IACR и NIST) опубликовали некрологи, отметив его вклад как «фундаментальный для современной безопасности цифровых коммуникаций». В 2024 году в его честь назван один из алгоритмов в стандарте постквантовой криптографии FALCON.

Источники

• Montgomery, P. L. «Modular Multiplication Without Trial Division». Mathematics of Computation, 1985.
• Montgomery, P. L. «Speeding the Pollard and Elliptic Curve Methods of Factorization». Mathematics of Computation, 1987.
• Bernstein, D. J. «Curve25519: New Diffie-Hellman Speed Records». Public Key Cryptography — PKC 2006.
• NIST. «Report on the Development of the Advanced Encryption Standard (AES)». 2001.
• IACR. «Peter Montgomery: 1947–2024». IACR Newsletter, 2024.
• Intel. «Intel® 64 and IA-32 Architectures Software Developer’s Manual». 2023.