Чист Pascal аритметика на NIST криви за подписване на PDF

HotPDF извършва key agreement върху елиптични криви и верификация на подписи за PDF на чист Object Pascal, без OpenSSL обвързване и без платформен крипто доставчик в пътя; Това покрива пет криви: P-256, P-384 и P-521 за NIST простите семейства, плюс X25519 и X448 за Montgomery-curve съгласуване на ключове; Причината да се напише този код, вместо да се линкне, е внедряването, не чистотата; Delphi или Free Pascal приложение, което доставя един изпълним файл и без криптографска DLL, няма разминаване на версии за управление, няма per-platform доставчик за откриване и нищо, което променя поведението, когато клиент кърпи своите системни библиотеки

Цената е, че сега вие притежавате аритметиката; Big-integer модулното умножение е непрощаващ код: то или произвежда байт-идентични резултати спрямо публикувани тестови вектори, или произвежда правдоподобно изглеждащ боклук, а разстоянието между тези две състояния може да бъде едно-единствено сравнение; Това е историята на това сравнение, защото формата на дефекта се обобщава за всеки Pascal пренос на аритметика в полето

Защо изобщо една PDF библиотека се нуждае от аритметика на криви?

Две функции го дърпата навътре; Първата е encryption на документи с публичен ключ: ISO 32000 recipient-list обработчикът увива per-document ключ за назовани сертификати и когато получател притежава EC ключ, увиването минава през key-agreement, а не RSA key transport; Без ECDH няма начин да се отвори такъв документ; Втората е валидация на подписи; Верифицирането на ECDSA подпис върху /ByteRange байтовете се нуждае от умножение на точка върху кривата на подписващия, а P-384 е често срещан в правителствени и qualified-signature профили, където P-256 се смята за пода, а не целта; HotPDF излага резултатите от тази работа през пътя за ECDSA и CMS верификация и през модела на включваеми signature доставчици

CIOS и едното изваждане накрая

Montgomery умножението избягва делението, работейки в трансформирана област, където редукцията е отместване; Вариантът, който HotPDF използва, е Coarsely Integrated Operand Scanning, който преплита умножението и редукцията limb по limb, така че междинното никога не расте отвъд ширината на модула плюс един limb; Тялото на цикъла е праволинейно и лесно за тестване; Опашката не е: след преплетените проходи акумулаторът може да е някъде в диапазона до два пъти модула, така че алгоритъмът завършва с условно изваждане, което премахва едно копие на простото число, ако и само ако акумулаторът е по-голям или равен на него

Сравняването на две числа от много limbs означава обхождане от най-старшия limb надолу, докато носите borrow; Очевидният начин да го напишете е да сравните limb-а на акумулатора с limb-а на модула плюс входящия borrow; Този израз е грешен и е грешен по начин, който повечето криви крият

// Грешно: P[I] + Borrow може да wrap-не, когато 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;

Как всъщност изглежда borrow wrap-around?

Изглежда като крива, която работи навсякъде освен в продукцията; Простите числа за P-384 и P-521 съдържат limbs, които са изцяло единици, така че P[I] е равно на $FFFFFFFFFFFFFFFF; Добавете входящия borrow от едно към това и 64-битово unsigned wrap-ва до нула; Сравнението пита дали limb-ът на акумулатора е по-малък от нула, решава, че не е, и заключава, че не се нуждае от borrow; Един limb от резултата е грешен с едно

P-256 избягва, защото нито един от неговите limbs не е от само единици, така че събирането никога не прелива и дефектният израз случайно съвпада с правилния; Това е най-лошият възможен изход за тестов набор: най-тестваната крива минава, по-малко тестваните се провалят прекъсващо в зависимост от стойностите на операндите, а отказът излиза на повърхността като резултат от верификация „невалиден подпис“ върху документи, които са напълно валидни; HotPDF носеше изрична порта върху P-384 именно поради тази причина, връщайки недостъпен статус, а не грешен отговор, докато аритметиката не беше доказана спрямо reference вектори

Как дефектът всъщност беше локализиран

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

Това сравнение сочи направо към виновника; Веригата x беше правилна от край до край, докато y^2 се разминаваше в точно един limb с точно едно; Едно-limb разлика от едно не е дефект на умножение, дефект на carry разпространение или дефект на константа; тя е дефект на borrow верига, а единствената borrow верига в рутината е финалното условно изваждане; Един детайл почти дерайлира това: reference константата, използвана за dump-а, беше сама написана в грешния байтов ред при първия опит, което произведе разминаване в стойността y и за момент подсказа втори, несъществуващ дефект; Проверете endianness на вашата ground истина, преди да ѝ поверите обвинението на вашия код

Съседните капани в същата рутина

Още три режима на отказ живеят в рамките на няколко реда от това сравнение и и трите бяха живи в някакъв момент по време на разработката

// 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. Общото много-limb изваждане има същата wrap опасност: когато
//    Y[I] е $FFFFFFFFFFFFFFFF, Y[I] + Borrow wrap-ва до нула и 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 по-малко, а Montgomery константите бяха после изчислени от това грешно просто число, така че константите бяха самосъгласувани и съвместно грешни; Параметрите на кривата трябва да се извеждат, никога да се пишат: изчислете R като (1 shl (64 * L)) mod p от простото число, което действително използвате, после кросчекнете R * R mod p спрямо стойността, която вашата константа R^2 твърди; Двойка константи, които се съгласуват помежду си, не доказва нищо за нито една от тях

Стратегия за верификация, която мащабира отвъд една крива

Техниката, която направи X25519 и X448 управляеми, беше писане на огледална имплементация на език с неограничени цели числа и преписване на Pascal контролния поток в нея ред по ред; Когато огледалото произвежда правилния отговор, а Pascal не, дефектът е пропуск в транскрипцията и сондирането на същата междинна стойност в двете имплементации го намира за секунди; И трите класически грешки в RFC 7748 ladder-а бяха хванати така: constant-time swap, чийто втори ред преизползва вече разменената стойност, финално инвертиране, което върна z на степен минус едно вместо да го умножи в X, и умножение с малка константа, което сглоби half-word произведения с bitwise or и загуби преноса

За тестов материал вземайте векторите като байтове, а не като текст; Извличането на частен ключ с текстов модел е начинът, по който правилна имплементация бива обвинена в off-by-one-byte грешка, която живее изцяло в стъпката на извличане; Отрежете hex от DER кодирането на известни offsets и сравнявайте байтови масиви

С поправената borrow верига и петте криви съвпадат с публикуваните reference вектори байт по байт и HotPDF вече не огражда нито една от тях; Ако интегрирате подписване, базирано на сертификати, или recipient-list шифроване, практическият извод е, че изборът на крива вече е политическо решение, а не въпрос на възможност; профилите и капаните с байтов ред на страната за подписване са разгледани в прошетката за PAdES подписване; Детайлите на компонента и поддържаната алгоритмична матрица са на продуктовата страница HotPDF Delphi PDF component