Арифметика кривих 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 містять limb, цілком з одиниць, тож P[I] дорівнює $FFFFFFFFFFFFFFFF. Додайте вхідну позику одиниця до цього — і 64-бітове беззнакове згортається в нуль. Порівняння потім питає, чи limb акумулятора менший за нуль, вирішує, що ні, і висновує, що позика не потрібна. Один limb результату збивається на одиницю

P-256 вислизає, бо жоден з його limb не з усіх одиниць, тож додавання ніколи не переповнюється і хибний вираз випадково погоджується з правильним. Це найгірший можливий результат для тестового набору: найтестованіша крива проходить, менш тестовані періодично зазнають невдачі залежно від значень операндів, а збій виявляється результатом перевірки «нечинний підпис» на документах, що цілком чинні. HotPDF ніс явну перепону на P-384 саме з цієї причини, повертаючи статус недоступності замість неправильної відповіді, доки арифметику не доведено проти референсних векторів

Як ваду насправді знайшли

Не читанням коду. Продуктивна послідовність була механічною, і вона повторно вживана. Перше: усуньте константи — кожен limb p, R і R^2 перегенеровано незалежно і порівняно limb за limb, що відсікає найпоширеніше джерело вад кривих. Друге: інструментуйте арифметику, а не API — тимчасова підпрограма вивантаження надрукувала проміжні значення множення Монтгомері для R^2, для x^3 і для y^2 відомої точки, тож їх можна було звірити з незалежно обчисленою правдою

Те порівняння вказало прямо на винуватця. Ланцюг x був правильний з кінця в кінець, тоді як y^2 різнився рівно в одному limb рівно на одиницю. Однолімбова різниця на одиницю — не вада множення, не вада поширення переносу і не вада константи; це вада ланцюга позики, а єдиний ланцюг позики в підпрограмі — фінальне умовне віднімання. Одна деталь мало не зійшла з рейок: референсна константа, використана для вивантаження, сама була записана в неправильному порядку байтів на першій спробі, що дало розбіжність у значенні y і короткий натяк на другу, неіснуючу ваду. Перевіряйте порядок байтів вашої еталонної правди, перш ніж довіряти їй звинувачувати ваш код

Сусідні пастки в тій самій підпрограмі

Ще три режими збою живуть у кількох рядках від того порівняння, і всі три були живі в якийсь момент розробки

// 1. Акумулятор має один limb понад шириною модуля. Порівняння лише
//    нижніх L limb пропускає випадок, коли 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; і множення на малу константу, що збирало півсловесні добутки побітовим або і втратило перенос

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

З виправленим ланцюгом позики всі п'ять кривих збігаються з опублікованими референсними векторами байт у байт, і HotPDF більше не ставить перепони жодній. Якщо ви інтегруєте підписування на основі сертифікатів або шифрування зі списком отримувачів, практичний висновок: вибір кривої тепер рішення політики, а не питання можливостей; профілі та пастки порядку байтів сторони підписування охоплені в поясненні підписування PAdES. Деталі компонента та підтримувана матриця алгоритмів — на сторінці продукту HotPDF Delphi PDF component