PDFlibPas подписывает и проверяет подписи с помощью Ed448 и трёх кривых Brainpool ECDSA на чистом Object Pascal. Никаких внешних криптографических библиотек, никаких платформенных провайдеров, никаких DLL: PDFlibEd448 реализует PureEdDSA из RFC 8032 на кривой edwards448, а PDFlibBrainpool реализует brainpoolP256r1, brainpoolP384r1 и brainpoolP512r1 из RFC 5639. Оба модуля построены одинаково — на контрольных векторах, сгенерированных независимо до того, как был написан хоть один Pascal-код, — и рассказать о них стоит в первую очередь из-за найденных ошибок
Арифметика полей — на редкость честный код. Она либо побайтово совпадает с опубликованными векторами, либо нет, поэтому места для состояния «почти работает» здесь нет. Трудность же в том, что ошибочная реализация всё равно создаёт подписи, всё равно проверяет собственные подписи и выглядит абсолютно правдоподобно
Зачем нужны эти кривые и зачем на Pascal
Кривые Brainpool фигурируют в европейских профилях квалифицированной подписи, поэтому библиотека, подписывающая документы для этого рынка, не может считать их экзотикой. Ed448 входит в набор алгоритмов, который ISO/TS 32002 приносит в PDF, где в качестве внутреннего дайджеста используется SHAKE256, а не SHA-2. Ни одно из этих семейств не доступно в распространённых криптографических библиотеках для Pascal, поэтому PDF-библиотеке, которой они нужны, приходится реализовывать их самостоятельно
Аргумент в пользу развёртывания тот же, что и для всей криптографии этой библиотеки: приложение, поставляемое одним исполняемым файлом без криптографических зависимостей, не содержит провайдера, который нужно обнаруживать, версии, которую нужно согласовывать, и поведения, которое меняется после обновления системы. Подпись — именно та область, где скользящая зависимость нежелательна больше всего
Константы берутся из текста спецификации, а не по памяти
Первая попытка записать базовую точку edwards448 была сделана по памяти и оказалась неверной. Это не выдающаяся ошибка, но очень дорогая, ведь неверная базовая точка создаёт самосогласованную систему: генерация ключей, подпись и проверка согласуются между собой и расходятся с остальным миром
Рабочая процедура такова: каждый доменный параметр берётся из текста спецификации, после чего выполняется перекрёстная проверка. Для edwards448 это значит взять из RFC 8032 простое число, константу кривой, порядок группы и обе десятичные координаты базовой точки, преобразовать их во внутреннее limb-представление и сверить с опубликованными в том же документе тестовыми векторами. Для кривых Brainpool это параметры из RFC 5639, независимая реализация, написанная для генерации векторов, и двусторонняя сверка с системной библиотекой ещё до того, как заработал первый Pascal-код
Одного способа ускорить вывод параметров стоит касаться с осторожностью: восстановление базовой точки из фиксированного значения y выглядит универсальным приёмом, но работает для кривой 25519 и не работает для edwards448, где у этого значения нет квадратного корня. Скрипт опроверг его за секунды, что куда дешевле, чем обнаружить это через отладчик
Метод: зеркальная реализация на уровне limbs до любого Pascal-кода
Метод, который сделал оба модуля управляемыми, — это зеркальная реализация на языке с неограниченными целыми числами, построенная снизу вверх. Сначала только арифметический слой: умножение в поле, вычитание и распространение переносов, проверенные стресс-тестами на алгебраических инвариантах на паре сотен случайных случаев. Затем полная генерация ключей внутри зеркала — именно там живут семантические ошибки, и именно там их дёшево находить. И лишь потом перенос на Pascal
Выгода здесь диагностическая, а не конструкторская. Когда зеркало проверено и признано корректным, любое расхождение между зеркалом и Pascal — это ошибка переноса, и зондирование одного и того же промежуточного значения в обеих реализациях сразу её локализует. Тем самым класс ошибок, который иначе почти не отлаживается, — один неверный limb в глубине скалярного умножения — сводится к пятиминутному сравнению
Четыре первопричины в Ed448
Все четыре найдены зондированием промежуточных значений, и все четыре относятся к тому сорту дефектов, который выдаёт правдоподобный на вид результат
Первая — ловушка нотации. Большинство опубликованных формул унифицированного сложения Эдвардса предполагают константу кривой, равную минус единице, а у edwards448 она равна плюс единице. При переносе без изменений числитель координаты y записывается как сумма там, где должна быть разность. Исправление состоит не в замене знака, а в повторном выводе произведения без инвертирования из аффинного закона сложения для правильной кривой: так получаются все четыре выражения для координат и не остаётся места для знака, унаследованного из неверного источника
Вторая — в декомпрессии точек. Восстановление аффинного x из проективных координат требует одного умножения на обратный элемент к Z. Умножение на квадрат обратного даёт значение, которое всё ещё остаётся корректным проективным представлением, но является неверной аффинной координатой, поэтому симптом — правильный y при неверном x. Всякий раз, когда одна координата верна, а другая нет, ошибка находится в нормализации, а не в арифметике
Третья — привычка, занесённая с более короткой кривой. И скаляр для каждой подписи, и скаляр вызова должны приводиться по модулю из полного дайджеста, который для Ed448 составляет 114 байт, а не из его первых 57. 32-байтовая кривая тоже использует свой полный 64-байтовый дайджест, так что правило едино; неверным является лишь допущение, что «половина дайджеста равна ширине скаляра»
Четвёртая — порядок. Префикс разделения доменов идёт первым, перед префиксом контекста и сообщением, а это не тот порядок, который подсказывает интуитивное прочтение R и A в спецификации. Ошибка здесь даёт подписи, которые проверяются вашей собственной реализацией и больше ничем, — самый вводящий в заблуждение из возможных сбоев
// Схема переносов в поле: чистое распространение с семантикой floor,
// поэтому работают и положительные, и отрицательные limbs,
// а вычитанию не требуется смещение. Старший перенос замыкается
// через 2^448 = 2^224 + 1 (mod p), что затрагивает limb 0 и limb 8.
// Ограничено четырьмя проходами; на практике наблюдалось два
procedure FeCarry(var A: TFe448);
var
I, Round: Integer;
Carry: Int64;
begin
for Round := 1 to 4 do
begin
Carry := 0;
for I := 0 to 15 do
begin
A[I] := A[I] + Carry;
Carry := Floor28(A[I]); // floor, а не усечение
A[I] := A[I] - (Carry shl 28);
end;
if Carry = 0 then
Break;
A[0] := A[0] + Carry; // 2^448 == 1
A[8] := A[8] + Carry; // 2^448 == 2^224
end;
end;Ранняя версия этой процедуры применяла смещение перед распространением, и на больших входах она вносила в младшие limbs ложный перенос неверного порядка. Схемы переносов на основе смещения — устойчивый источник дефектов этого класса; семантика floor с ограниченным циклом repeat проще для рассуждений и достаточно быстра, что подтверждается замерами
Две первопричины в Brainpool
Первая вообще не про криптографию. Рабочее представление — 33 limbs, значит, произведение двух значений требует 66, а массив произведения был объявлен с размером 64. Запись за границей портила соседнюю память, что поначалу проявлялось как неверные результаты и превратилось в падение только после добавления более широкой проверки. Из этого выросло правило, которое стоит применять к каждому числовому буферу фиксированного размера: задавать размер по ширине произведения в худшем случае с запасом, после чего больше об этом не думать. Массив в поставляемом коде — 68 limbs
Вторая — перепутанная схема возведения в степень. Есть две корректные формы square-and-multiply, и они потребляют экспоненту в противоположных направлениях: форма справа налево сначала умножает, затем возводит основание в квадрат и должна читать биты с младшего конца, а форма слева направо сначала возводит в квадрат, затем умножает и читает со старшего конца. В цикле модульного инвертирования тело было «справа налево», а обход битов — от старшего. Каждая половина по отдельности взята из учебника, их сочетание — нет, и результатом становится неверное обратное, которое всё ещё выглядит правдоподобным элементом поля
// Удвоение и сложение в якобиевых координатах, когда запись-приёмник
// может совпадать с переменной-источником. Полное копирование записи
// на входе — единственная надёжная защита: запись limbs переменной R
// портит последующие чтения P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
const Curve: TBPCurve);
var
Pin: TBPPoint;
begin
Pin := P; // сначала копия, затем вычисления только из Pin
// ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;Два урока процесса, обошедшиеся дороже самих ошибок
Инкрементальные точечные исправления не сходятся к рабочему криптографическому модулю. Один черновик латали снова и снова, пока он не оброс 32 продублированными процедурами и повреждённой структурой, и спасла его только полная переработка. Рабочий шаблон таков: либо написать модуль за один раз по проверенному зеркалу, либо переписать; последовательность локальных правок арифметики, которую вы ещё не понимаете, накапливает ошибки быстрее, чем исправляет
И проверяйте метку времени исполняемого файла, прежде чем поверить результату теста. Инкрементальная сборка, которая компилируется, но не перелинковывается, запускает предыдущий бинарник, и это породило целый круг ложных следов о пропавших зондах и дублированном выводе. При отладке криптографии необъяснимый результат должен сначала наводить на вопрос «тот ли это бинарник, который вы только что собрали», а уже потом на вопрос «верна ли арифметика»
Производительность, область применения и вызов
Модульное приведение в модуле Brainpool — это поразрядный сдвиг с вычитанием, начиная со старшего установленного бита произведения, поэтому умножение стоит порядка ширины бита. Проверка P-256 укладывается в нижние сотни миллисекунд, что незаметно при подписании или проверке документов и было бы недостаточно для терминатора TLS. Приведение Барретта — очевидное улучшение, но ему нужно более широкое рабочее значение, чем несёт текущее представление, поэтому это изменение на тот случай, когда нагрузка его потребует, а не упреждающая мера
uses
PDFlibEd448, PDFlibBrainpool;
var
PublicKey, Signature: AnsiString;
Curve: TBPCurve;
R, S, PubX, PubY: TBPValue;
begin
// Ed448: PureEdDSA, внутри SHAKE256, ключи по 57 байт
if Ed448PublicKeyFromSeed(Seed, PublicKey) and
Ed448Sign(DocumentDigest, Seed, Signature) then
Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));
// Brainpool: вызывающий сам передаёт nonce для каждой подписи,
// поэтому политика nonce остаётся в приложении
Curve := BPLoadCurve(bpP256r1);
if BPKeyGen(PubX, PubY, PrivateD, Curve) and
BPSignFixedK(R, S, Hash, PrivateD, Nonce, Curve) then
Assert(BPVerify(R, S, Hash, PubX, PubY, Curve));
end;Обратите внимание: точка входа подписания Brainpool принимает nonce, а не генерирует его. Это сделано намеренно: генерация nonce — самая катастрофическая по последствиям ошибка в ECDSA, поскольку повторённое или предсказуемое значение раскрывает закрытый ключ, а решение о том, откуда берётся случайность, принадлежит приложению и его режиму соответствия, а не PDF-библиотеке
Эти кривые дополняют постквантовую работу, описанную в статье о FIPS 204 ML-DSA, и встраиваются в тот же конвейер подписания и проверки, который рассмотрен в материале о подписании и проверке PAdES. Локальная генерация тестовых сертификатов на этих кривых описана в статье о самоподписанных сертификатах с CryptoAPI. Полная матрица алгоритмов перечислена на странице продукта losLab PDF Developer Library