Коблиц и Миллер: секущая Диофанта в каждом рукопожатии

Группа, которой семнадцать веков

Возьмите кубическую кривую и две точки на ней с рациональными координатами. Проведите через них прямую: она пересечёт кривую в третьей точке — и та тоже окажется рациональной, потому что кубическое уравнение с рациональными коэффициентами, у которого два корня рациональны, имеет рациональным и третий.

Этим приёмом Диофант искал решения ещё в третьем веке. ФермаПьер Фермафранцузский юрист и математик · 1607–1665Советник тулузского парламента, не напечатавший при жизни ни одной математической книги — и успевший заложить теорию чисел, аналитическую геометрию, метод касательных и теорию вероятностей. и НьютонИсаак Ньютонанглийский математик, физик и астроном · 1643–1727Создатель анализа, механики и оптики, четверть века проработавший начальником Монетного двора и потративший на алхимию и богословие больше бумаги, чем на физику. его формализовали, а в 1901 году ПуанкареАнри Пуанкарефранцузский математик, физик и философ науки · 1854–1912Последний универсал математики: создал топологию, увидел хаос там, где все видели порядок, и подошёл к теории относительности вплотную, не сделав последнего шага. заметил главное: если третью точку отразить относительно оси, получается сложение. Рациональные точки кривой образуют группу.

Дальше эта группа и есть сюжет линии. Морделл доказал в 1922-м, что она порождается конечным числом элементов. Танияма связал такие кривые с модулярными формами, Бёрч и Свиннертон-Дайер на машине нащупали, чем управляется её размер, Фальтингс отделил их от кривых старшего рода, а Уайлс через девять лет закроет ими теорему Ферма.

Всё это — чистейшая теория чисел, в применения не метившая.

Что заметили в 1985-м

Ту же секущую можно проводить не над рациональными числами, а по модулю простого $p$. Кривая превращается в конечное множество точек, и сложение на нём остаётся тем же самым — просто теперь группа конечна.

Теперь вспомним, чего требует протокол Диффи — Хеллмана. Ему нужна любая группа, в которой умножать легко, а извлекать показатель трудно. Обычно берут остатки по модулю простого. Но можно взять и точки кривой: вместо «возвести $g$ в степень $a$» — «сложить точку $P$ саму с собой $a$ раз».

Это и предложили в 1985 году, независимо друг от друга, Виктор Миллер из исследовательского центра IBM (доклад на конференции CRYPTO в августе) и Нил Коблиц из Вашингтонского университета в Сиэтле.

Зачем менять группу

Затем, что старую группу умеют взламывать лучше.

Для остатков по модулю $p$ есть метод исчисления индексов: он пользуется тем, что целые числа раскладываются на простые множители, и находит дискретный логарифм заметно быстрее перебора. У точек кривой раскладывать не на что — понятия «маленький простой делитель точки» не существует, и метод не переносится. Остаётся общий перебор с квадратным корнем, а он работает в любой группе и ничего про кривую не знает.

Отсюда практический вывод, ради которого всё и делалось:

При одинаковой стойкости ключ короче примерно в двенадцать раз, а подпись и рукопожатие — во столько же раз дешевле. Для смарт-карты, банковского чипа или телефона это разница между «работает» и «не помещается».

Почему стандартом стало не сразу

Мешали патенты: канадская фирма Certicom держала целый куст прав на приёмы быстрого счёта на кривых, и до середины 2000-х многие предпочитали не связываться. Перелом наступил в 2005 году, когда Агентство национальной безопасности США рекомендовало кривые для защиты собственных секретных данных.

А потом маятник качнулся обратно. В 2013 году выяснилось, что в стандарте генерации случайных чисел, продвинутом тем же агентством, скорее всего была закладка. Сами кривые это не порочило, но доверие к параметрам, происхождение которых никто не мог объяснить, кончилось. Победила кривая Curve25519 Даниэля Бернштейна (2005), у которой каждое число в определении выведено из явного правила и подобрать его тайно было нельзя. Сегодня именно она стоит по умолчанию в TLS, в SSH и в мессенджерах.

Человек, чьё имя здесь уже встречалось

Нил Коблиц — теоретик чисел, попавший в криптографию со стороны математики, а не связи. В том же 1985 году он вместе с женой, историком науки Энн Хибнер Коблиц, основал фонд имени Софьи КовалевскойСофья Васильевна Ковалевскаярусский математик и писательница · 1850–1891Нашла третий и последний интегрируемый случай вращения тяжёлого волчка — после Эйлера и Лагранжа. Метод оказался важнее результата, а премию Парижской академии за него повысили с трёх до пяти тысяч франков., который до сих пор поддерживает женщин в науке в бедных странах: деньгами послужил гонорар за биографию Ковалевской, написанную Энн.

Что дальше

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

Но пока квантовой машины нужного размера нет, семнадцативековая секущая Диофанта отрабатывает миллиарды рукопожатий в секунду.

Следующая точка: Принстон — где закроется задача, поставленная на полях книги за 357 лет до того.