CRYSTALS-Kyber: KEM قائم على الشبكات

إن CRYSTALS-Kyber، الذي أعادت NIST تسميته إلى ML-KEM في FIPS 203، هو آلية تغليف مفاتيح (KEM) قائمة على Module-LWE. وهو يحل محل RSA وECDH في تبادل المفاتيح، ويوفر مقاومة للحوسبة الكمّية مع مستويات أداء عملية.

تغلّف KEM سرًا مشتركًا: ينشئ المُرسِل مفتاحًا عشوائيًا K، ويشفّره باستخدام المفتاح العام للمستقبِل (التغليف)، منتجًا نصًا مشفّرًا C. ويفكّ المستقبِل تغليف C باستخدام مفتاحه الخاص لاستعادة K. ولا حاجة إلى تبادل مفاتيح تفاعلي.

تستخدم Kyber خوارزمية Module-LWE فوق الحلقة R_q = Z_q[x]/(x^256+1) حيث q=3329. ويكون البعد k=2 في Kyber-512، وk=3 في Kyber-768، وk=4 في Kyber-1024. أما مستويات الأمان فهي نحو 128 و192 و256 بت على التوالي. ويُعد k=3 (Kyber-768) الخيار الافتراضي الموصى به.

ولّد المصفوفة A ∈ R_q^{k×k} من البذرة ρ (القابلة للتوسعة). خذ العينة السرية s والضوضاء e من توزيع ثنائي الحدين متمركز (بمعاملات صغيرة). المفتاح العام: (ρ, t=As+e). المفتاح الخاص: s. تكون الضوضاء e صغيرة، لكنها تمنع استعادة s من المفتاح العام.

لإرسال سر مشترك إلى مالك المفتاح العام (ρ, t): خذ عينات r وe1 وe2 من توزيع الضوضاء. احسب u = A^T r + e1، وv = t^T r + e2 + round(q/2)*m، حيث m رسالة عشوائية بطول 256 بت. السر المشترك K = KDF(m). النص المشفّر = (u, v).

باستخدام المفتاح الخاص s: احسب m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). تتلاشى حدود الضوضاء تقريبًا، ويبقى m'≈m. احسب K = KDF(m'). ويبلغ احتمال فشل فك التغليف: < 2^{-139}.

Kyber-768: المفتاح العام 1184 بايت، والمفتاح الخاص 2400 بايت، والنص المشفّر 1088 بايت، والسر المشترك 32 بايت. وبالمقارنة، يحتوي ECDH-P256 على مفتاح عام بحجم 65 بايت ونص مشفّر بحجم 32 بايت. حجم Kyber أكبر بنحو 15 مرة، لكنه آمن في عصر الحوسبة الكمّية. ومع ذلك فهو سريع: إذ يستغرق التغليف وفك التغليف أقل من 1 مللي ثانية على وحدات المعالجة المركزية الحديثة.

يستخدم ضرب كثيرات الحدود في R_q = Z_q[x]/(x^256+1) تحويلَ الأعداد النظرية (NTT)، وهو النظير الحسابي المعياري لتحويل FFT. ويخفض NTT تعقيد ضرب كثيرات الحدود من O(n^2) إلى O(n log n). وقد اختير q=3329 لامتلاكه خصائص NTT مناسبة لـ n=256.

أثناء الترحيل إلى التشفير ما بعد الكم، استخدموا تبادل مفاتيح هجينًا يجمع بين ECDH وKyber. السر المشترك = KDF(ECDH_output || Kyber_output). يتطلب الأمان كسر النظامين معًا: فلا يستطيع المهاجمون التقليديون كسر أي منهما، بينما يستطيع المهاجمون الكمّيون كسر ECDH دون Kyber. وتدعم مسودات TLS 1.3 (IETF RFC 8446) آليات KEM الهجينة.

لا يكون فك تغليف Kyber بزمن ثابت في التطبيقات الساذجة، إذ تكشف خطوة أخذ عينات الرفض معلومات من خلال التوقيت. ويستخدم التطبيق المرجعي NTT بزمن ثابت ومقارنةً بزمن ثابت للنص المشفّر المضغوط. استخدموا الشفرة المرجعية المقدمة في طلب NIST أو تطبيقات المكتبات الخاضعة للتدقيق.

نشرت NIST المعيار FIPS 203 (ML-KEM) في أغسطس 2024. وأضاف Chrome دعم Kyber في TLS 1.3 عام 2023. وتنشر Cloudflare وGoogle وAWS حاليًا حلول ECDH+Kyber الهجينة. وأضاف OpenSSL 3.x دعم ML-KEM. ولا تزال تطبيقات LibSSH وWireGuard قيد التطوير.

Kyber (ML-KEM) هي KEM قائمة على Module-LWE وتحل محل ECDH. يبلغ حجم المفاتيح نحو 1 كيلوبايت، وتتميز بحسابات NTT سريعة، كما أنها مقاومة للحوسبة الكمّية. انشروها بصورة هجينة مع ECDH أثناء الترحيل. وقد وُحّدت في FIPS 203. التالي: مخططا التوقيعات CRYSTALS-Dilithium وFalcon.