Арифметика кривых NIST на чистом Pascal для подписания PDF

HotPDF выполняет согласование ключей на эллиптических кривых и проверку подписей для PDF на чистом Object Pascal, без привязки к OpenSSL и без платформенного криптопровайдера на пути. Это покрывает пять кривых: P-256, P-384 и P-521 из простых семейств NIST плюс X25519 и X448 для согласования ключей на кривых Монтгомери. Причина писать этот код, а не подключать, — развёртывание, а не чистота. Приложение Delphi или Free Pascal, поставляемое одним исполняемым файлом без криптографической DLL, не имеет рассогласования версий для управления, не имеет провайдера для каждой платформы, которого надо опознавать, и не имеет ничего, что меняет поведение, когда клиент обновляет свои системные библиотеки

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

Зачем PDF-библиотеке вообще арифметика кривых?

Две возможности его втягивают. Первая — шифрование документов с открытым ключом: обработчик списка получателей ISO 32000 оборачивает ключ документа для поименованных сертификатов, и когда получатель держит ключ EC, обёртывание идёт через согласование ключей, а не через транспорт ключей RSA. Без ECDH такой документ не открыть. Вторая — проверка подписей. Проверка подписи ECDSA над байтами /ByteRange требует умножения точек на кривой подписанта, а P-384 обычна в государственных и квалифицированных профилях подписи, где P-256 считается полом, а не целью. HotPDF отдаёт результаты этой работы через путь проверки ECDSA и CMS и через подключаемую модель поставщиков подписи

CIOS и одно вычитание в конце

Умножение Монтгомери избегает деления, работая в преобразованном домене, где приведение — это сдвиг. Вариант, который использует HotPDF, — Coarsely Integrated Operand Scanning: он чередует умножение и приведение limb за limb, так что промежуточное значение никогда не растёт дальше ширины модуля плюс один limb. Тело цикла прямолинейно и легко тестируется. Хвост — нет: после чередующихся проходов аккумулятор может оказаться где угодно в диапазоне до двух модулей, поэтому алгоритм завершается условным вычитанием, убирающим одну копию простого числа тогда и только тогда, когда аккумулятор больше или равен ему

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

// Неверно: P[I] + Borrow может переполниться, когда P[I] равен $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Верно: сравнение без какого-либо прибавления к limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Как на деле выглядит переполнение заёма?

Он выглядит как кривая, работающая всюду, кроме промышленной эксплуатации. Простые числа для P-384 и P-521 содержат limbs, сплошь состоящие из единиц, поэтому P[I] равен $FFFFFFFFFFFFFFFF. Прибавьте входящий заём, равный единице, и 64-битное беззнаковое переполняется до нуля. Сравнение затем спрашивает, меньше ли нуля limb аккумулятора, решает, что нет, и заключает, что заём не нужен. Один limb результата сбит на единицу

P-256 избегает этого, поскольку ни один из его limbs не состоит из сплошных единиц, сложение никогда не переполняется, и ошибочное выражение случайно совпадает с правильным. Для тестового набора это худший возможный исход: самая протестированная кривая проходит, менее протестированные периодически падают в зависимости от значений операндов, а отказ всплывает как результат проверки «недействительная подпись» на совершенно действительных документах. HotPDF именно по этой причине нёс явный заслон на P-384, возвращая статус недоступности вместо неверного ответа, пока арифметика не была доказана по эталонным векторам

Как баг был найден на самом деле

Не чтением кода. Продуктивная последовательность была механической, и её можно переиспользовать. Во-первых, исключите константы: каждый limb p, R и R^2 генерировался заново независимо и сравнивался limb за limb, что отсекает самый частый источник багов кривых. Во-вторых, инструментируйте арифметику, а не API: временная процедура дампа печатала промежуточные значения умножения Монтгомери для R^2, x^3 и y^2 известной точки, чтобы сверить их с независимо вычисленной истиной

Это сравнение указало прямо на виновника. Цепочка x была верна от начала до конца, тогда как y^2 отличался ровно в одном limb ровно на единицу. Разница в один limb на единицу — не баг умножения, не баг распространения переноса и не баг константы; это баг цепочки заёма, а единственная цепочка заёма в процедуре — финальное условное вычитание. Одна деталь чуть не сбила это расследование: эталонная константа, использованная для дампа, сама была записана в неверном порядке байтов при первой попытке, что дало несовпадение в значении y и ненадолго подсказало второй, несуществующий дефект. Проверяйте порядок байтов вашей истины, прежде чем доверять ей обвинять ваш код

Соседние ловушки в той же процедуре

Ещё три режима отказа живут в нескольких строках от того сравнения, и все три в какой-то момент разработки были живы

// 1. У аккумулятора есть limb выше ширины модуля. Сравнение только
//    младших L limbs пропускает случай, когда T равно ровно p плюс 2^(64*L),
//    что случается на заметной доле случайных входов, ведь 2p
//    превышает 2^256 для P-256 и 2^384 для P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Обычное многолимбовое вычитание имеет ту же опасность переполнения:
//    когда Y[I] равен $FFFFFFFFFFFFFFFF, Y[I] + Borrow переполняется до нуля,
//    и заём должен дожить до следующего limb, а не быть сброшенным
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Третья — не код, а происхождение. Простое число для P-521 изначально было переписано со 130 шестнадцатеричными цифрами вместо 131, без одного F, и константы Монтгомери затем вычислялись из того неверного простого, поэтому константы были самосогласованными и совместно неверными. Параметры кривых должны выводиться, а не вводиться вручную: вычислите R как (1 shl (64 * L)) mod p из простого, которым вы действительно пользуетесь, затем сверьте R * R mod p со значением, которое заявляет ваша константа R^2. Пара констант, согласующихся друг с другом, не доказывает ничего ни об одной из них

Стратегия проверки, масштабируемая за пределы одной кривой

Метод, сделавший X25519 и X448 управляемыми, — зеркальная реализация на языке с неограниченными целыми и перенос потока управления Pascal в неё строка за строкой. Когда зеркало даёт правильный ответ, а Pascal нет, дефект — описка переноса, и зондирование одного и того же промежуточного значения в обеих реализациях находит его за секунды. Все три классические ошибки лестницы RFC 7748 были пойманы так: перестановка постоянного времени, чья вторая строка использовала уже переставленное значение; финальное инвертирование, возвращавшее z в степени минус один вместо умножения его на X; и умножение на малую константу, собиравшее произведения полуслов побитовым or и терявшее перенос

Для тестового материала берите векторы байтами, а не текстом. Извлечение закрытого ключа текстовым шаблоном — вот как корректная реализация получает обвинение в ошибке на один байт, которая целиком живёт в шаге извлечения. Вырезайте hex из кодировки DER по известным смещениям и сравнивайте массивы байтов

После исправления цепочки заёма все пять кривых побайтово совпадают с опубликованными эталонными векторами, и HotPDF больше не ставит заслон ни на одну из них. Если вы встраиваете подписание на сертификатах или шифрование по списку получателей, практический вывод таков: выбор кривой теперь — решение политики, а не вопрос возможности; профили и подводные камни порядка байтов на стороне подписания рассмотрены в пошаговом руководстве по подписанию PAdES. Детали компонента и матрица поддерживаемых алгоритмов — на странице продукта HotPDF Delphi PDF component