حساب منحنی NIST در پاسکال خالص برای امضای PDF

HotPDF توافق کلید روی منحنی بیضوی و تأیید امضا را برای PDF در Object Pascal خالص انجام می‌دهد، بدون بایندینگ OpenSSL و بدون هیچ ارائه‌دهنده رمزنگاری پلتفرمی در مسیر. این پنج منحنی را پوشش می‌دهد: P-256، P-384 و P-521 برای خانواده‌های اول NIST، به‌علاوه X25519 و X448 برای توافق کلید روی منحنی مونتگومری. دلیل نوشتن آن کد به‌جای لینک‌کردنش استقرار است، نه خلوص. یک برنامه Delphi یا Free Pascal که یک فایل اجرایی و هیچ DLL رمزنگاری عرضه نکند، نه ناهمخوانی نسخه‌ای برای مدیریت دارد، نه ارائه‌دهنده به‌ازای هر پلتفرمی برای شناسایی، و نه هیچ‌چیزی که وقتی مشتری کتابخانه‌های سیستمی‌اش را وصله می‌کند رفتار را تغییر دهد

هزینه‌اش این است که حالا حساب مال شماست. ضرب پیمانه‌ای اعداد صحیح بزرگ کد بی‌رحمی است: یا نتایج بایت‌به‌بایت یکسان با بردارهای آزمون منتشرشده تولید می‌کند یا زباله موجه‌نما، و فاصله میان آن دو حالت می‌تواند یک مقایسه باشد. این قصه همان مقایسه است، چون شکل باگ به هر پورت پاسکالی از حساب میدانی تعمیم می‌یابد

اصلاً چرا یک کتابخانه PDF به حساب منحنی نیاز دارد؟

دو ویژگی آن را می‌کشند در. اولی رمزگذاری کلید عمومی اسناد است: handler فهرست گیرندگان در 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 به پایین در حالی که یک borrow حمل می‌شود. راه بدیهی نوشتنش این است که limb انباره را با limb پیمانه به‌علاوه borrow ورودی مقایسه کنید. آن عبارت غلط است، و به شکلی غلط است که بیشتر منحنی‌ها پنهانش می‌کنند

// غلط: P[I] + Borrow وقتی P[I] برابر $FFFFFFFFFFFFFFFF باشد می‌تواند wrap کند
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 در عمل چه شکلی دارد؟

شبیه منحنی‌ای است که همه‌جا کار می‌کند به‌جز در تولید. اول‌های P-384 و P-521 limbهایی کاملاً یک دارند، پس P[I] برابر $FFFFFFFFFFFFFFFF است. borrow ورودی یک را به آن اضافه کنید و یک عدد بدون‌علامت ۶۴بیتی به صفر wrap می‌شود. مقایسه بعد می‌پرسد آیا limb انباره کوچک‌تر از صفر است، تصمیم می‌گیرد که نیست، و نتیجه می‌گیرد که borrow لازم نیست. یک limb از نتیجه یکی خطا دارد

P-256 فرار می‌کند چون هیچ limbهایش همه‌یک نیستند، پس جمع هرگز سرریز نمی‌شود و عبارت باگ‌دار اتفاقاً با درست موافق است. آن بدترین نتیجه ممکن برای یک مجموعه تست است: پرتست‌ترین منحنی پاس می‌شود، کمتست‌ترها بسته به مقادیر عملوند به‌طور متناوب شکست می‌خورند، و شکست به‌شکل نتیجه تأیید «امضای نامعتبر» روی اسنادی که کاملاً معتبرند ظاهر می‌شود. HotPDF دقیقاً به همین دلیل یک کنترل صریح روی P-384 داشت، که به‌جای پاسخ غلط وضعیت ناموجود برمی‌گرداند، تا وقتی که حساب در برابر بردارهای مرجع اثبات شد

باگ در عمل چگونه پیدا شد

نه با خواندن کد. رشته کارا مکانیکی بود و قابل استفاده مجدد است. اول، ثابت‌ها را حذف کنید: هر limb از p، R و R^2 به‌طور مستقل دوباره تولید و limb به limb مقایسه شد، که رایج‌ترین منبع منفرد باگ‌های منحنی را کنار می‌گذارد. دوم، حساب را ابزاردهی کنید نه API را: یک رویه dump موقت مقادیر میانی ضرب مونتگومری R^2، x^3 و y^2 برای یک نقطه معلوم را چاپ می‌کرد، تا بتوان آن‌ها را با حقیقت محاسبه‌شده به‌طور مستقل کنترل کرد

آن مقایسه مستقیم به مقصر اشاره کرد. زنجیره x سرتاسر درست بود، در حالی که y^2 دقیقاً در یک limb و دقیقاً به اندازه یک تفاوت داشت. یک تفاوت تک-limb به اندازه یک، نه باگ ضرب است، نه باگ انتشار carry، و نه باگ ثابت؛ باگ زنجیره borrow است، و تنها زنجیره borrow در روتین همان تفریق شرطی پایانی است. یک جزئیات تقریباً این را از ریل خارج کرد: ثابت مرجعی که برای dump استفاده شد خودش در تلاش اول با ترتیب بایت غلط نوشته شده بود، که ناهمخوانی در مقدار y تولید می‌کرد و مدتی کوتاه یک عیب دوم ناموجود را القا کرد. endian بودن حقیقت مبنای خودتان را پیش از آنکه اجازه دهید کدتان را متهم کند راستی‌آزمایی کنید

تله‌های همسایه در همان روتین

سه حالت شکست دیگر در چند خطی همان مقایسه زندگی می‌کنند، و هر سه در نقطه‌ای از توسعه فعال بودند

// 1. انباره یک limb بالاتر از پهنای پیمانه دارد. مقایسه فقط
//    L limb پایانی حالتی را که T دقیقاً برابر p به‌علاوه 2^(64*L) است
//    از دست می‌دهد، که برای سهم معناداری از ورودی‌های تصادفی رخ می‌دهد چون 2p
//    برای P-256 از 2^256 و برای P-384 از 2^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 ابتدا با ۱۳۰ رقم هگزادسیمال پیاده شد به‌جای ۱۳۱، یک F کمتر، و ثابت‌های مونتگومری بعد از روی آن اولِ غلط محاسبه شدند، پس ثابت‌ها خودسازگار و مشترکاً غلط بودند. پارامترهای منحنی باید استخراج شوند، هرگز تایپ نشوند: R را به‌صورت (1 shl (64 * L)) mod p از روی اولی که واقعاً استفاده می‌کنید محاسبه کنید، سپس R * R mod p را با مقداری که ثابت R^2 ادعا می‌کند کنترل متقاطع کنید. جفت ثابت‌هایی که با هم موافق‌اند درباره هیچ‌کدام چیزی ثابت نمی‌کند

راهبرد راستی‌آزمایی که از یک منحنی فراتر می‌رود

تکنیکی که X25519 و X448 را اداره‌پذیر کرد نوشتن یک پیاده‌سازی آینه در زبانی با اعداد صحیح بدون کران و پیاده‌کردن جریان کنترل پاسکال در آن خط به خط بود. وقتی آینه پاسخ درست تولید می‌کند و پاسکال نه، عیب یک لغزش پیاده‌سازی است و کاویدن همان مقدار میانی در هر دو پیاده‌سازی در چند ثانیه پیدایش می‌کند. هر سه اشتباه کلاسیک نردبان RFC 7748 این‌شکل گرفته شد: یک swap با زمان ثابت که خط دومش از مقدار از پیش عوض‌شده دوباره استفاده می‌کرد، یک وارون‌سازی پایانی که z را به توان منفی یک برمی‌گرداند به‌جای ضرب‌کردنش در X، و یک ضرب با ثابت کوچک که حاصل‌ضرب‌های نیم‌کلمه را با یک or بیتی مونتاژ می‌کرد و carry را از دست می‌داد

برای مواد تست، بردارها را به‌صورت بایت بگیرید نه متن. بیرون‌کشیدن یک کلید خصوصی با یک الگوی متنی همان چیزی است که یک پیاده‌سازی درست به خطای آفست-یک-بایتی متهم می‌شود که به‌طور کامل در گام استخراج زندگی می‌کند. هگز را در آفست‌های معلوم از رمزگذاری DER برش بزنید و آرایه‌های بایتی را مقایسه کنید

با اصلاح زنجیره borrow، هر پنج منحنی با بردارهای مرجع منتشرشده بایت‌به‌بایت مطابقت دارند، و HotPDF دیگر هیچ‌کدام را کنترل نمی‌کند. اگر در حال یکپارچه‌سازی امضای مبتنی بر گواهی یا رمزگذاری فهرست گیرندگان هستید، نکته عملی این است که انتخاب منحنی اکنون یک تصمیم خط‌مشی است نه یک پرسش قابلیت؛ پروفایل‌ها و تله‌های ترتیب بایت سمت امضا در آموزش گام‌به‌گام امضای PAdES پوشش داده شده است. جزئیات مؤلفه و ماتریس الگوریتم‌های پشتیبانی‌شده در صفحه محصول HotPDF Delphi PDF component است