تشفير المنحنيات الإهليلجية

يحقق تشفير المنحنيات الإهليلجية (ECC) مخططات المفتاح العام على مجموعة النقاط على منحنى إهليلجي، مما يحقق نفس مستوى الأمان الذي توفره RSA أو ديفي-هيلمان للحقول المنتهية ولكن بمفاتيح أصغر بكثير.

Definition

تشفير المنحنيات الإهليلجية هو تشفير مفتاح عام تكون مجموعته الأساسية هي مجموعة النقاط على منحنى إهليلجي فوق حقل منتهٍ، ويعتمد أمانه على صعوبة مشكلة اللوغاريتم المتقطع للمنحنيات الإهليلجية.

Scope

يغطي هذا الموضوع قانون مجموعة المنحنيات الإهليلجية على الحقول المنتهية، ومشكلة اللوغاريتم المتقطع للمنحنيات الإهليلجية، والمخططات المبنية عليها: ديفي-هيلمان للمنحنيات الإهليلجية (ECDH)، ومخططات التوقيع ECDSA وEdDSA، والمنحنيات الحديثة مثل Curve25519. ويتناول سبب صعوبة اللوغاريتمات المتقطعة للمنحنيات الإهليلجية مقارنة بتلك الخاصة بالحقول المنتهية (لا يوجد حساب مؤشر شبه أسي) ومخاوف التنفيذ مثل إعادة استخدام النونس (nonce) في ECDSA. ويستثني RSA ومخططات اللوغاريتم المتقطع للحقول المنتهية التي تغطيها مواضيع ذات صلة.

Core questions

• كيف يشكل الجمع الهندسي للنقاط على منحنى إهليلجي مجموعة تشفيرية؟
• لماذا يعتبر اللوغاريتم المتقطع للمنحنيات الإهليلجية أصعب من نظيره في الحقول المنتهية، مما يسمح بمفاتيح أصغر؟
• كيف يتم تطبيق ديفي-هيلمان والتوقيعات الرقمية على المنحنيات الإهليلجية؟
• ما الذي يجعل المنحنيات الحديثة مثل Curve25519 أكثر أمانًا للتنفيذ من منحنيات NIST القديمة؟
• لماذا تعتبر فرادة النونس (nonce) لكل توقيع أمرًا حاسمًا في ECDSA؟

Key concepts

• قانون مجموعة المنحنيات الإهليلجية
• الضرب القياسي
• مشكلة اللوغاريتم المتقطع للمنحنيات الإهليلجية
• ECDH
• ECDSA
• EdDSA وEd25519
• Curve25519
• ثغرة إعادة استخدام النونس
• حجم المفتاح مقابل RSA

Key theories

مشكلة اللوغاريتم المتقطع للمنحنيات الإهليلجية

بالنظر إلى النقطتين P و Q = kP على منحنى، يُعتقد أن استعادة القيمة القياسية k تتطلب جهدًا أسيًا كاملاً للمنحنيات المختارة جيدًا، لأن هجمات حساب المؤشر التي تضعف اللوغاريتمات المتقطعة للحقول المنتهية لا تنطبق.

مفاتيح أصغر لأمان متساوٍ

نظرًا لأن أفضل الهجمات على اللوغاريتمات المتقطعة للمنحنيات الإهليلجية هي خوارزميات الجذر التربيعي العامة، فإن منحنى إهليلجي بحجم 256 بت يوفر أمانًا يبلغ حوالي 128 بت — وهو ما يعادل RSA بحجم 3072 بت — مما يؤدي إلى عمليات أسرع ومفاتيح وتوقيعات أصغر.

Mechanisms

تشكل النقاط على منحنى إهليلجي فوق حقل منتهٍ مجموعة أبيلية (abelian group) بموجب قانون جمع هندسي؛ فإضافة نقطة أساس P إلى نفسها k مرة (الضرب القياسي، kP) عملية فعالة، لكن استعادة k من kP هي المشكلة الصعبة. يقوم ECDH بإجراء ديفي-هيلمان عن طريق تبادل المضاعفات القياسية لنقطة أساس؛ وينتج ECDSA وEdDSA توقيعات من قيمة قياسية لكل رسالة (نونس) — والتي، إذا تكررت أو كانت قابلة للتنبؤ، فإنها تكشف المفتاح الخاص، كما أظهرت العديد من الاختراقات الحقيقية.

Clinical relevance

ECC هو الخيار الافتراضي للمفتاح العام للأنظمة الجديدة: يوفر ECDHE تبادل مفاتيح سرية أمامية في TLS 1.3، ويوقع Ed25519 مفاتيح SSH وتحديثات البرامج والشهادات، ويؤمن Curve25519 تطبيقات Signal وWireGuard والرسائل الحديثة. إن مفاتيحه الصغيرة وعملياته السريعة تجعله مناسبًا تمامًا للأجهزة المحمولة والبطاقات الذكية وأجهزة إنترنت الأشياء المقيدة الموارد.

Evidence & guidelines

تم توحيد ECDSA في FIPS 186، وECDH في NIST SP 800-56A، وEdDSA/Ed25519 في RFC 8032؛ وCurve25519/X25519 في RFC 7748. تفضل الممارسات الحديثة منحنيات إدواردز وX25519 لمقاومتها لمزالق التنفيذ. يعد انهيار ECDSA عند إعادة استخدام النونس (خاصة استخراج مفتاح Sony PlayStation 3 في عام 2010) مثالًا تحذيريًا قياسيًا.

History

اقترح نيل كوبليتز وفيكتور ميلر بشكل مستقل استخدام المنحنيات الإهليلجية للتشفير في الفترة 1985-1987. كان التبني بطيئًا في البداية بسبب مخاوف براءات الاختراع والثقة وتعقيد منحنيات NIST، لكن ECC أصبح مهيمنًا في العقد الثاني من القرن الحادي والعشرين مع تزايد أهمية كفاءة حجم المفتاح، وقدمت Curve25519 (2006) وEd25519 من بيرنشتاين تصاميم سريعة ومقاومة لسوء الاستخدام يتم نشرها على نطاق واسع الآن.

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

لماذا يتطابق مفتاح منحنى إهليلجي بحجم 256 بت مع مفتاح RSA بحجم 3072 بت؟

أفضل الهجمات المعروفة على اللوغاريتم المتقطع للمنحنيات الإهليلجية عامة وتستغرق وقتًا يعادل تقريبًا الجذر التربيعي لحجم المجموعة، بينما يتوفر للتحليل إلى عوامل واللوغاريتمات المتقطعة للحقول المنتهية خوارزميات شبه أسية أسرع. لذا تحتاج المنحنيات الإهليلجية إلى عدد أقل بكثير من البتات لنفس مستوى الأمان.

هل منحنيات NIST الإهليلجية جديرة بالثقة؟

تُستخدم منحنيات NIST P القياسية على نطاق واسع ولا يُعرف أنها قد تم اختراقها، لكن اختياراتها الثابتة غير المبررة وصعوبة تنفيذها دفعت الكثيرين إلى تفضيل Curve25519 وEd25519، التي تتميز بمنطق تصميم شفاف وأسهل في التنفيذ بأمان في وقت ثابت.