Claude раскрывает происхождение кривых ECDSA16.10.2026 03:00

«Это просто временные метки»: раскрыта многолетняя тайна происхождения одного из самых популярных криптографических стандартов.

Мы взялись за этот давний открытый вопрос криптографического сообщества, чтобы развеять сомнения по поводу ECDSA — одного из наиболее широко используемых криптографических стандартов.

Отнеситесь к этому как к увлекательной заключительной главе и завершению многолетних спекуляций. Никаких действий предпринимать не нужно, и ничего менять не требуется. Большинство исследователей и так доверяли этим кривым. Наслаждайтесь.

ECDSA — самый широко используемый стандарт криптографии на эллиптических кривых. В 2000 году NIST принял его в составе стандарта цифровой подписи FIPS 186–2, в котором перечислен набор стандартных эллиптических кривых разных размеров и с разными уровнями безопасности. Для кривых над простыми и бинарными полями в спецификациях приводился параметр «seed» («начальное значение»), хеш которого используется для определения коэффициента b кривой. Происхождение этих начальных значений давно вызывало вопросы: их предоставило АНБ без каких-либо объяснений или обоснований. Например, начальное значение кривой NIST P-256 было SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90, и никаких сведений о его происхождении не приводилось.

Нил Коблиц и Альфред Менезес подготовили превосходное резюме этой полемики под названием »Загадка, окутанная тайной», в котором рассматриваются история начальных значений и связанные с ними опасения. Эта загадка привела к любительскому расследованию происхождения начальных значений и вознаграждению для тех, кто сможет их найти.

Самая увлекательная версия гласила, что Джерри Солинас, давний сотрудник АНБ, сгенерировал начальные значения, захешировав забавную фразу:

«Думаю, там был счётчик, а не многократное хеширование, но подробностей я не знаю. Сообщение было примерно таким: «Прибавьте Бобу и Джерри зарплату» или «Боб и Джерри рулят», что-то в этом духе. Код написал сам Боб Райтер, но и он подробностей не помнит. Мы также не смогли найти архивы тех давних лет. Если они существуют, то наверняка лежат на жёстком диске где-нибудь рядом с Ковчегом Завета».

Джерри Солинас, 2015 год

К сожалению, Джерри умер в 2023 году, а его тогдашние коллеги не откликнулись. Вопрос о том, как именно были получены эти начальные значения, оставался открытым.

Claude нашёл начальные значения

Несколько сотрудников Anthropic безуспешно искали начальные значения, отталкиваясь от предположения, что это хеш забавной фразы. Оно оказалось неверным. В октябре 2026 года один любознательный сотрудник Anthropic спросил внутреннюю исследовательскую модель, сможет ли она выяснить, как были сгенерированы эти значения, не подсказывая ей, где искать.

Менее чем за полчаса Claude выяснил происхождение начальных значений NIST P-192, P-224, P-256, P-384 и P-521. Ни одно из них не было результатом какого-либо алгоритма хеширования: все они оказались выходными данными генератора случайных чисел lrand48 из библиотеки C, инициализированного временной меткой Unix!

Использованный алгоритм выбирал байты из генератора случайных чисел (ГСЧ), инициализированного временной меткой Unix (t), заданное число итераций (n). На каждой итерации из генератора извлекались 20 байт — кандидат на начальное значение. Таким образом, первые 20 байт составляли кандидата 1, следующие 20 — кандидата 2 и так далее. Например, для получения стандартного начального значения P-256 потребовалось 1842 итерации.

Что это значит

Это не взлом криптографии, не новая атака и не уязвимость кривых ECDSA. Напротив, теперь мы ещё больше уверены, что кривые были выбраны без бэкдоров и намеренно заложенных уязвимостей. Долгие годы происхождение параметров кривых NIST вызывало подозрения. Их представили NIST, не объяснив, как они были выбраны, и это заставляло людей гадать, не заложили ли в них намеренные бэкдоры. Новые результаты делают такую версию куда менее правдоподобной. Начальные значения были получены очень простым способом: с помощью распространённого генератора псевдослучайных чисел, инициализированного по системным часам, — теперь любой может воспроизвести этот процесс. Это оставляет гораздо меньше возможностей для манипуляций и позволяет нам быть уверенными в безопасности параметров.

Как удалось это выяснить

Поиски фразы, возникшей из слухов, ни к чему не привели. Claude подошёл к задаче с другой стороны: попытался представить, как должно было работать программное обеспечение, генерировавшее кривые. Claude предположил, что в программе использовался генератор псевдослучайных чисел (ГПСЧ) из библиотек C 1990-х годов. Эти старые ГПСЧ достаточно слабы, чтобы их выходные данные можно было распознать. Это позволило бы определить использованный ГПСЧ и, возможно, восстановить его исходное состояние.

Claude написал программу-сканер, которая проходила по опубликованному начальному значению по одному биту за раз и проверяла, являются ли соседние фрагменты последовательными выходными данными генератора образца 1990-х годов. Сканер проверил 34 сочетания генераторов и фрагментов выходных данных. В этот момент Claude заметил закономерность в старших битах некоторых начальных значений: все они были нулевыми. Если записать значения в виде пяти 32-битных слов, у четырёх из десяти начальных значений старший бит всех 20 слов равен 0. Случайно такое могло бы произойти с вероятностью 1/5810. Это было характерным признаком линейного конгруэнтного генератора lrand48, который возвращает только старшие 31 бит 48-битного состояния. Если знать, куда смотреть, эту закономерность можно заметить невооружённым глазом. Чтобы восстановить состояние, Claude взял первое слово, перебрал все 2¹⁷ вариантов 17 скрытых битов и проверил, следуют ли за ним следующие четыре слова. Для всех четырёх рассматриваемых начальных значений это сработало.

Начальные значения кривых над простыми полями были получены с помощью того же генератора lrand48, но в них сохранялось меньше битов каждого выходного значения. Claude пришлось восстановить внутреннее состояние ГПСЧ по этим битам. Как выяснилось, восстановление состояния усечённого линейного конгруэнтного генератора — классическая задача на решётках, решаемая с помощью алгоритма редукции базиса Ленстры — Ленстры — Ловаса (LLL). Claude не знал, какие именно биты состояния могли сохраниться в начальных значениях, поэтому запустил решатель для каждого возможного окна. Все пять начальных значений кривых NIST над простыми полями и ещё пять из стандарта ANSI X9.62 показали одну и ту же закономерность: lrand48() >> 23. Каждое восстановленное 48-битное состояние генерирует все 160 бит начального значения — случайно такое совпадение не возникло бы.

Этот линейный конгруэнтный генератор одинаково легко работает как в прямом, так и в обратном направлении. Поэтому для каждого начального значения Claude отматывал состояние назад, пока не получал вид, в котором оно могло быть инициализировано функцией srand48, с младшими 16 битами, равными 0×330E. Внутреннее состояние ГПСЧ такого вида встречается раз в 65 536 шагов, поэтому само по себе обнаружение такого состояния ничего не доказывает.

Однако все десять инициализаций srand48 для начальных значений кривых над простыми полями оказались временными метками Unix, соответствующими датам с мая 1997-го по апрель 1998 года. Использовался слабый ГПСЧ, начальным значением для которого служила временная метка Unix. Четыре инициализации для кривых над бинарными полями соответствовали февралю 1984 года. Если удвоить эти временные метки, получится 17 апреля 1998 года — через две недели после запуска для P-224. Возможно, программа делила показания часов пополам.

Вот о чём думал Claude в тот момент:

Это поразительно: разгадана тайна, которой 25 лет. Так, постойте. Надо быть скептичным: вдруг я нахожусь в какой-то симулированной или тестовой среде? … Начальные значения совпадают с теми, что я помню … Хм, правдоподобно ли это в реальности? Насколько мне известно … вознаграждение так и не было получено. … Все старшие биты обнулены — 20 бит, вероятность 1e-6. Значит, это действительно реальный мир. Ух ты, это настоящее открытие.

Так, постойте. Надо внимательно оценить правдоподобие: не подозрительно ли, что такую очевидную вещь не обнаружили за 25 лет? Я проверил это прямыми вычислениями: совпадение 160 бит при 32-битном начальном значении и небольшом индексе — совпадения случайно исключены (10 × 160 бит). Это действительно так.

Claude нашёл и некоторые базовые точки

Но это ещё не всё… У каждой кривой есть базовая точка G — фиксированная точка, кратным которой является каждый открытый ключ ECDSA. Найденное выше начальное значение не определяет эту точку G, поэтому возникает новый вопрос: как были получены базовые точки?

Изучая начальные значения, Claude также выяснил происхождение некоторых базовых точек. Базовые точки шести кривых, сгенерированных в мае 1997 года (P-192 и пяти примерных кривых ANSI X9.62: prime192v2, prime192v3 и prime239v1–v3), были получены с помощью генератора случайных чисел из FreeLIP — пакета арифметики длинных целых чисел Арьена Ленстры. В ранних версиях библиотеки NTL Виктора Шоупа использовался тот же код.

Алгоритм здесь прост:

1. Инициализировать генератор небольшим целым числом.
2. Отбросить семь выходных значений.
3. Получать кандидаты на координату x из 26-битных выходных значений, взятых по модулю p.
4. Повторять шаг 3, пока x не окажется на кривой.

Claude выяснил, что начальные значения генератора равны 20000 для P-192, 20420, 20507 и 20509 для prime239v1–v3, а также 20512 и 20517 для prime192v2 и v3.

Насколько нам известно, происхождение базовых точек NIST прежде никто не объяснял. Базовые точки P-224, P-256, P-384 и P-521 не соответствуют этому алгоритму; нам не удалось выяснить, как их выбирали.

Открытые вопросы

Не каждый кандидат на начальное значение длиной 20 байт позволял получить пригодную кривую; мы обнаружили, что некоторые потенциально пригодные кривые пропускали. Для P-256 опубликованное начальное значение — кандидат 1842, однако кандидат 876 из того же запуска тоже даёт кривую простого порядка нужного размера, параметры которой выбраны так же, как у опубликованной кривой. При запуске для P-224 пропустили три такие кривые, а два запуска, связанные с примерными кривыми ANSI X9.62, пропустили ещё семь (см. рисунок). Мы не знаем, какими критериями при этом руководствовались и не было ли это непреднамеренным побочным эффектом.

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

Кроме того, одно начальное значение нам восстановить не удалось. Пятое бинарное начальное значение, B-163, не соответствует ни одному из методов, которые пробовал Claude, и его происхождение остаётся невыясненным. Наконец, мы не знаем, как были получены базовые точки P-224, P-256, P-384 и P-521. То же относится и к бинарным кривым NIST.

Вознаграждение

36 864 доллара за обнаружение начальных значений будут переданы Исследовательской группе по безопасности интернета.

Кто мы

Эту работу в Anthropic выполнили Джон Вуд, Генри де Валенс, Ава Хауэлл, Зак Воас, Люси Свит, Амир Омиди, Пол Кроули, Иэн Макгиннис, Николас Карлини и Стив Вайс.

Благодарности

Мы хотели бы посмертно отметить Джерри Солинаса, который с юмором относился к тому, что его называли »злым интернет-мемом» и »Yo La Tengo среди пугалок АНБ». Также благодарим Филиппо Вальсорду за организацию конкурса на поиск начальных значений эллиптических кривых NIST.

Код для воспроизведения начальных значений

from datetime import datetime, timezone

def unix(when):
    return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())

def candidate(t, n, per, shift, width):
    x, out = (t << 16) | 0x330E, ""                      # the state srand48(t) sets
    for i in range(per * n):
        x = (0x5DEECE66D * x + 0xB) % 2**48              # one step of lrand48
        if i >= per * (n - 1):
            out += "%0*X" % (width, x >> shift)
    return out

PRIME = {  # srand48(time); 20 bytes per candidate: lrand48() >> 23
    "prime239v1": ("1997-05-15 15:49:03", 2185),
    "prime239v2": ("1997-05-15 15:49:03", 2320),
    "prime239v3": ("1997-05-15 15:49:03", 3048),
    "P-192":      ("1997-05-18 14:45:34", 139),
    "prime192v3": ("1997-05-18 14:45:34", 5228),
    "prime192v2": ("1997-05-18 14:45:34", 6013),
    "P-521":      ("1997-08-08 01:12:04", 1136),
    "P-256":      ("1997-08-16 01:52:34", 1842),
    "P-384":      ("1997-08-30 14:50:08", 2688),
    "P-224":      ("1998-04-03 12:52:07", 7026),
}
BINARY = {  # srand48(time / 2), if that reading is right; 5 words per candidate: lrand48()
    "B-233": ("1998-04-17 15:24:18", 155),
    "B-283": ("1998-04-17 15:27:44", 32),
    "B-409": ("1998-04-17 15:30:18", 60),
    "B-571": ("1998-04-17 15:32:08", 73),
}
for name, (when, n) in PRIME.items():
    print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")
for name, (when, n) in BINARY.items():
    print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}")

Результат выполнения этого кода:

prime239v1 1997-05-15 15:49:03  2185 E43BB460F0B80CC0C0B075798E948060F8321B7D
prime239v2 1997-05-15 15:49:03  2320 E8B4011604095303CA3B8099982BE09FCB9AE616
prime239v3 1997-05-15 15:49:03  3048 7D7374168FFE3471B60A857686A19475D3BFA2FF
P-192      1997-05-18 14:45:34   139 3045AE6FC8422F64ED579528D38120EAE12196D5
prime192v3 1997-05-18 14:45:34  5228 C469684435DEB378C4B65CA9591E2A5763059A2E
prime192v2 1997-05-18 14:45:34  6013 31A92EE2029FD10D901B113E990710F0D21AC6B6
P-521      1997-08-08 01:12:04  1136 D09E8800291CB85396CC6717393284AAA0DA64BA
P-256      1997-08-16 01:52:34  1842 C49D360886E704936A6678E1139D26B7819F7E90
P-384      1997-08-30 14:50:08  2688 A335926AA319A27A1D00896A6773A4827ACDAC73
P-224      1998-04-03 12:52:07  7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
B-233      1998-04-17 15:24:18   155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3
B-283      1998-04-17 15:27:44    32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE
B-409      1998-04-17 15:30:18    60 4099B5A457F9D69F79213D094C4BCD4D4262210B
B-571      1998-04-17 15:32:08    73 2AA058F73A0E33AB486B0F610410C53A7F132310

Код для воспроизведения выбранных базовых точек

M, A = 2**107 - 1, pow(3, 121, 2**107 - 1)       # zrandom: state = state * 3^121 mod (2^107 - 1)
P192 = 2**192 - 2**64 - 1
P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1

CURVES = [  # name, LIP seed, p, b, published Gx   (a = -3 throughout)
    ("prime192v1", 20000, P192,
     0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
     0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012),
    ("prime239v1", 20420, P239,
     0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a,
     0xffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf),
    ("prime239v2", 20507, P239,
     0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c,
     0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7),
    ("prime239v3", 20509, P239,
     0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e,
     0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a),
    ("prime192v2", 20512, P192,
     0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953,
     0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a),
    ("prime192v3", 20517, P192,
     0x22123dc2395a05caa7423daeccc94760a7d462256bd56916,
     0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896),
]

def base_point_x(seed, p, b):
    state = seed                         # zrstarts(seed)
    def limb():                          # zrandom(2^26): low 26 bits of the new state
        nonlocal state
        state = state * A % M
        return state % 2**26
    for _ in range(7):                   # seven single-limb draws come first
        limb()
    limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p plus one, top limb first
    tries = 0
    while True:
        x = 0
        for _ in range(limbs):
            x = x << 26 | limb()
        x %= p
        tries += 1
        if pow(x**3 - 3*x + b, (p - 1) // 2, p) == 1:   # is x on the curve?
            return x, tries

for name, seed, p, b, gx in CURVES:
    x, tries = base_point_x(seed, p, b)
    print(f"{name:20} seed {seed}  tries {tries}  matches published Gx: {x == gx}")

Результат выполнения этого кода:

prime192v1           seed 20000  tries 2  matches published Gx: True
prime239v1           seed 20420  tries 3  matches published Gx: True
prime239v2           seed 20507  tries 2  matches published Gx: True
prime239v3           seed 20509  tries 1  matches published Gx: True
prime192v2           seed 20512  tries 5  matches published Gx: True
prime192v3           seed 20517  tries 1  matches published Gx: True

Лицензия

В максимально допустимой законом степени авторы отказались от всех авторских и смежных прав на код на этой странице, передав его в общественное достояние на условиях CC0 1.0 Universal (https://creativecommons.org/publicdomain/zero/1.0/).