Ed448 и Brainpool ECDSA на чист Pascal за PDF

PDFlibPas подписва и верифицира с Ed448 и с трите криви Brainpool ECDSA на чист Object Pascal; Без външна криптографска библиотека, без доставчик на платформата, без DLL: PDFlibEd448 реализира RFC 8032 PureEdDSA върху edwards448, а PDFlibBrainpool реализира brainpoolP256r1, brainpoolP384r1 и brainpoolP512r1 по RFC 5639; И двете са изградени по един и същ начин, срещу known-answer вектори, генерирани независимо, преди да е написан дори ред 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, където тази стойност няма квадратен корен; Скрипт го опроверга за секунди, което е много по-евтино от откриването му през дебъгер

Методът: огледална имплементация на ниво limb преди всеки Pascal

Техниката, която направи двата модула управляеми, е огледална имплементация на език с неограничени цели числа, изградена отдолу нагоре; Първо самият аритметичен слой: умножение в полето, изваждане и разпространение на преноса, стрестествани срещу техните алгебрични инварианти върху няколкостотин случайни случая; После пълното генериране на ключове вътре в огледалото, което е мястото, където живеят семантичните дефекти и където е евтино да се открият; Едва след това Pascal транскрипцията

Ползата е диагностична, а не развиваща; Щом огледалото е известно като правилно, всяко разминаване между огледалото и Pascal е пропуск в транскрипцията, а сондирането на една и съща междинна стойност в двете имплементации го локализира веднага; Това превръща клас дефекти, които иначе са почти недебъгваеми – един-единствен грешен limb дълбоко в скаларното умножение – в сравнение от пет минути

Четири първопричини в Ed448

И четирите са открити чрез сондиране на междинни стойности, и четирите са от рода неща, които произвеждат изход, изглеждащ валиден

Първата е капан в нотацията; Повечето публикувани формули за унифицирано Edwards събиране предполагат константа на кривата минус едно, а 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;

По-ранна версия на тази процедура прилагаше отместване (bias) преди разпространението и при големи входове внасяше фалшив пренос с грешната величина в ниските limbs; Схемите за пренос, базирани на отместване, са постоянен източник на този клас дефекти; floor семантиката с ограничен цикъл на повторение е по-лесна за разсъждение и измеримо достатъчно бърза

Две първопричини в Brainpool

Първата изобщо не е криптография; Работното представяне е 33 limbs, така че произведението на две стойности се нуждае от 66, а масивът за произведението беше деклариран с 64; Записването след края повреждаше съседна памет, което първо се проявяваше като грешни резултати и стана срив едва когато беше добавено по-широко сканиране; Правилото, излязло оттам, си заслужава да се прилага за всеки числов буфер с фиксиран размер: оразмерете го според ширината на произведението в най-лошия случай и добавете запас, после никога повече не мислете за него; Масивът в кода, който се доставя, е 68 limbs

Втората е разбъркана форма на степенуване; Има две правилни форми square-and-multiply и те консумират експонентата в противоположни посоки: формата отдясно-наляво умножава и след това повдига на квадрат основата и трябва да чете битовете от най-младшия край, докато формата отляво-надясно повдига на квадрат и след това умножава и чете от най-старшия край; Цикълът за модулно инвертиране имаше тяло отдясно-наляво с обхождане на битовете старши-пръв; И двете половини са от учебника, комбинацията не е, а резултатът е грешна обратна стойност, която все още изглежда като правдоподобен елемент на полето

// Удвояване и събиране в Jacobian, при които записът-приемник може да
// е същата променлива като източник. Копиране на целия запис при входа
// е единствената надеждна защита: записът на 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; Barrett редукцията е очевидното надграждане и се нуждае от по-широка работна стойност от тази, която текущото представяне носи, така че това е промяна, която се прави, когато натоварването я изиска, а не превантивно

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