التشفير باستخدام المنحنى الإهليلجي

في عام 2013، ذكرت صحيفة نيويورك تايمز أن خوارزمية توليد البتات العشوائية الحتمية باستخدام منحنى إهليلجي مزدوج (Dual_EC_DRBG) أُدرجت كمعيار وطني لدى المعهد الوطني للمعايير والتكنولوجيا (NIST) بسبب تأثير وكالة الأمن القومي الأمريكية (NSA )، التي أدخلت ثغرة متعمدة في الخوارزمية والمنحنى الإهليلجي الموصى به. ^{[ 9 ]} وفي سبتمبر من العام نفسه، أصدرت شركة RSA Security بيانًا توصي فيه عملاءها بالتوقف عن استخدام أي برنامج يعتمد على خوارزمية Dual_EC_DRBG. ^{[ 10 ] [ 11 ]} وفي أعقاب الكشف عن خوارزمية Dual_EC_DRBG باعتبارها "عملية سرية لوكالة الأمن القومي"، أعرب خبراء التشفير أيضًا عن قلقهم بشأن أمان المنحنيات الإهليلجية التي أوصى بها المعهد الوطني للمعايير والتكنولوجيا، ^{[ 12 ]} مقترحين العودة إلى التشفير القائم على مجموعات منحنيات غير إهليلجية.

بالإضافة إلى ذلك، أعلنت وكالة الأمن القومي الأمريكية في أغسطس/آب 2015 عن نيتها استبدال مجموعة التشفير "ب" بمجموعة تشفير جديدة، وذلك بسبب المخاوف المتعلقة بهجمات الحوسبة الكمومية على تشفير المنحنيات الإهليلجية. ^{[ 13 ] [ 14 ]} وفي وقت لاحق، نشرت الوكالة توجيهات "CNSA 2.0" للانتقال إلى خوارزميات مقاومة للحوسبة الكمومية لأنظمة الأمن القومي. ^{[ 7 ]}

رغم انتهاء صلاحية براءة اختراع RSA في عام 2000، قد توجد براءات اختراع سارية تغطي جوانب معينة من تقنية ECC، بما في ذلك نظام ECC واحد على الأقل ( ECMQV ). ومع ذلك، فقد جادلت مختبرات RSA ^{[ 15 ]} ودانيال ج. بيرنشتاين ^{[ 16 ]} بأنه يمكن تطبيق معيار التوقيع الرقمي باستخدام المنحنى الإهليلجي للحكومة الأمريكية (ECDSA؛ NIST FIPS 186-3) وبعض أنظمة تبادل المفاتيح العملية القائمة على ECC (بما في ذلك ECDH) دون انتهاك تلك البراءات.

تعتمد التشفير بالمفتاح العام على صعوبة حل بعض المسائل الرياضية . وقد استندت أنظمة المفتاح العام المبكرة، مثل براءة اختراع RSA لعام 1983، في أمانها على افتراض صعوبة تحليل عدد صحيح كبير مكون من عاملين أوليين كبيرين أو أكثر متباعدين. أما بالنسبة لبروتوكولات المنحنيات الإهليلجية، فإن أحد الافتراضات الأساسية للصعوبة هو مسألة اللوغاريتم المنفصل للمنحنى الإهليلجي (ECDLP): عند إعطاء نقطة أساس عامة${\displaystyle P}$ونقطة أخرى${\displaystyle Q=kP}$، ينبغي أن يكون من غير الممكن التعافي${\displaystyle k}$تعتمد بروتوكولات اتفاق المفاتيح مثل ECDH على افتراضات ديفي-هيلمان ذات الصلة، مثل صعوبة الحساب${\displaystyle abP}$من${\displaystyle P}$،${\displaystyle aP}$، و${\displaystyle bP}$يعتمد أمان تشفير المنحنيات الإهليلجية على القدرة على حساب ضرب النقاط بكفاءة، وعلى استحالة عكس هذه العملية ظاهريًا بالنسبة للمنحنيات وأحجام المفاتيح المختارة بعناية. ويُحدد حجم وبنية مجموعة المنحنيات، وليس فقط العدد الإجمالي لأزواج الإحداثيات التي تُحقق معادلة المنحنى، مدى صعوبة المسألة.

تتمثل الميزة الأساسية التي توفرها تقنية التشفير باستخدام المنحنيات الإهليلجية مقارنةً ببدائل أخرى مثل RSA في صغر حجم المفتاح ، مما يقلل من متطلبات التخزين والنقل. ^{[ 1 ]} على سبيل المثال، يوفر مفتاح عام باستخدام المنحنيات الإهليلجية بطول 256 بت مستوى أمان مماثلًا لمفتاح عام باستخدام RSA بطول 3072 بت.

تم تكييف العديد من البروتوكولات القائمة على اللوغاريتمات المنفصلة مع المنحنيات الإهليلجية، لتحل محل المجموعة${\displaystyle (\mathbb {Z} _{p})^{\times }}$مع مجموعة منحنى إهليلجي:

• يعتمد مخطط اتفاقية المفاتيح باستخدام منحنى الإهليلجي ديفي-هيلمان (ECDH) على مخطط ديفي -هيلمان .
• X25519 و X448 هما دالتا ديفي-هيلمان المحددتان من قبل IRTF للاستخدام مع منحنيات شكل مونتغمري، ^{[ 17 ]}
• مخطط التشفير المتكامل للمنحنى الإهليلجي (ECIES)، والمعروف أيضًا باسم مخطط التشفير المعزز للمنحنى الإهليلجي أو ببساطة مخطط تشفير المنحنى الإهليلجي،
• تعتمد خوارزمية التوقيع الرقمي للمنحنى الإهليلجي (ECDSA) على خوارزمية التوقيع الرقمي ،
• تعتمد خوارزمية التوقيع الرقمي لمنحنى إدواردز (EdDSA) على توقيع شنور وتستخدم منحنيات إدواردز الملتوية ، ^{[ 18 ]}
• يعتمد مخطط اتفاقية المفاتيح ECMQV على مخطط اتفاقية المفاتيح MQV ،
• نظام شهادة ECQV الضمني .

لاستخدام خوارزمية ECC، يجب على جميع الأطراف الاتفاق على جميع العناصر التي تحدد المنحنى الإهليلجي، أي معلمات نطاق الخوارزمية. عادةً ما يكون الحقل المنتهي الأساسي إما حقلاً أوليًا، ويرمز له بـ${\displaystyle \mathbb {F} _{p}}$أو حقل ثنائي، يُشار إليه بـ${\displaystyle \mathbb {F} _{2^{m}}}$في الحالة الثنائية،${\displaystyle m}$ومتعددة حدود اختزال غير قابلة للاختزال${\displaystyle f}$حدد تمثيل الحقل؛${\displaystyle f}$ليس منحنىً مساعدًا. يُعرَّف المنحنى الإهليلجي بمعاملات معادلته التعريفية. أخيرًا، تُعرَّف المجموعة الفرعية الدورية بمولدها ( أو نقطة الأساس ) G. في التطبيقات التشفيرية، رتبة G هي أصغر عدد موجب n بحيث${\displaystyle nG={\mathcal {O}}}$(النقطة عند اللانهاية للمنحنى، وعنصر الوحدة )، يكون عادةً عددًا أوليًا. بما أن n هو حجم مجموعة جزئية من${\displaystyle E(\mathbb {F} _{q})}$وبناءً على نظرية لاغرانج ، فإن العدد${\displaystyle h={\frac {1}{n}}|E(\mathbb {F} _{q})|}$هو عدد صحيح. في تطبيقات التشفير، يكون هذا العدد h ، المسمى بالعامل المساعد ، صغيرًا عادةً، ومثاليًا يساوي 1. يجب على البروتوكولات التي تستخدم منحنيات ذات عوامل مساعدة أكبر من 1 التعامل مع العامل المساعد بشكل مناسب. باختصار: في حالة الأعداد الأولية، تكون معلمات المجال هي${\displaystyle (p,a,b,G,n,h)}$أما في الحالة الثنائية، فهم${\displaystyle (m,f,a,b,G,n,h)}$.

ما لم يكن هناك ضمان بأن معلمات المجال قد تم إنشاؤها بواسطة جهة موثوقة فيما يتعلق باستخدامها، فيجب التحقق من صحة معلمات المجال قبل استخدامها.

لا يقوم كل مشارك عادةً بإنشاء معلمات المجال، لأن ذلك يتطلب حساب عدد النقاط على المنحنى، وهو أمر يستغرق وقتًا طويلاً ويُعدّ مُرهقًا. ونتيجةً لذلك، نشرت العديد من هيئات التقييس معلمات مجال للمنحنيات الإهليلجية لأحجام حقول شائعة. تُعرف هذه المعلمات عادةً باسم "المنحنيات القياسية" أو "المنحنيات المُسماة"؛ ويمكن الإشارة إلى المنحنى المُسمى إما بالاسم أو بمعرف الكائن الفريد المُحدد في الوثائق القياسية.

• NIST ، SP 800-186: توصيات للتشفير القائم على اللوغاريتم المنفصل: معلمات مجال المنحنى الإهليلجي ^{[ 6 ]}
• SECG ، القسم 2: معلمات مجال المنحنى الإهليلجي الموصى بها

• ECC Brainpool ( RFC 5639 )، ECC Brainpool Standard Curves and Curve Generation Archived 2018-04-17 at the Wayback Machine ^{[ 19 ] [ 20 ]} 

تتوفر أيضًا متجهات اختبار SECG. ^{[ 21 ]} وقد اعتمد المعهد الوطني للمعايير والتكنولوجيا (NIST) العديد من منحنيات SECG، لذا يوجد تداخل كبير بين المواصفات المنشورة من قبل NIST وSECG. يمكن تحديد معلمات نطاق EC إما بالقيمة أو بالاسم.

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

• اختر منحنى عشوائيًا واستخدم خوارزمية عامة لحساب النقاط، على سبيل المثال، خوارزمية شوف أو خوارزمية شوف-إلكيز-أتكين .
• اختر منحنى عشوائيًا من عائلة تسمح بحساب عدد النقاط بسهولة (مثل منحنيات كوبليتز )، أو
• حدد عدد النقاط وقم بإنشاء منحنى بهذا العدد من النقاط باستخدام تقنية الضرب المركب . ^{[ 22 ]}

هناك عدة أنواع من المنحنيات ضعيفة ويجب تجنبها:

• المنحنيات فوق${\displaystyle \mathbb {F} _{2^{m}}}$تكون الأعداد التي تحتوي على قيم m غير أولية عرضة لهجمات انحدار ويل . ^{[ 23 ] [ 24 ]}
• المنحنيات التي يقسمها n${\displaystyle p^{B}-1}$(حيث p هي خاصية الحقل: q للحقل الأولي، أو${\displaystyle 2}$بالنسبة للحقل الثنائي) تكون قيم B الصغيرة بما فيه الكفاية عرضة لهجوم مينيز-أوكاموتو-فانستون (MOV) ^{[ 25 ] [ 26 ]} الذي يطبق مسألة اللوغاريتم المنفصل المعتادة (DLP) في حقل امتداد ذي درجة صغيرة من${\displaystyle \mathbb {F} _{p}}$لحل ECDLP. يجب اختيار الحد B بحيث تكون اللوغاريتمات المنفصلة في المجال${\displaystyle \mathbb {F} _{p^{B}}}$لا تقل صعوبة حسابها عن صعوبة حساب اللوغاريتمات المنفصلة على المنحنى الإهليلجي${\displaystyle E(\mathbb {F} _{q})}$[ ^{27 ]​}
• منحنيات بحيث${\displaystyle |E(\mathbb {F} _{q})|=q}$تكون عرضة للهجوم الذي يرسم النقاط على المنحنى إلى المجموعة الجمعية لـ${\displaystyle \mathbb {F} _{q}}$[ ^{28 ] [ 29 ] [ 30 ]​}

لأن جميع الخوارزميات الأسرع المعروفة التي تسمح بحل مسألة ECDLP (مثل خوارزمية الخطوة الصغيرة والخطوة العملاقة ، وخوارزمية بولارد رو ، وما إلى ذلك) تحتاج${\displaystyle O({\sqrt {n}})}$وبناءً على هذه الخطوات، يجب أن يكون حجم الحقل الأساسي ضعف معيار الأمان تقريبًا. على سبيل المثال، يتطلب الأمان ذو 128 بت منحنىً على${\displaystyle \mathbb {F} _{q}}$، أين${\displaystyle q\approx 2^{256}}$يمكن مقارنة ذلك بتشفير الحقول المحدودة (مثل DSA ) الذي يتطلب ^{[ 31 ]} مفاتيح عامة بطول 3072 بت ومفاتيح خاصة بطول 256 بت، وتشفير تحليل الأعداد الصحيحة (مثل RSA ) الذي يتطلب قيمة n بطول 3072 بت ، حيث يجب أن يكون المفتاح الخاص بنفس الطول. مع ذلك، قد يكون المفتاح العام أصغر حجمًا لضمان كفاءة التشفير، خاصةً عند محدودية قدرة المعالجة.

تتضمن سجلات تحدي ECDLP العامة التاريخية مفتاحًا بطول 112 بت لحالة الحقل الأولي ومفتاحًا بطول 109 بت لحالة الحقل الثنائي. بالنسبة لحالة الحقل الأولي، تم كسر هذا المفتاح في يوليو 2009 باستخدام مجموعة من أكثر من 200 جهاز ألعاب بلاي ستيشن 3، وكان من الممكن إنجازه في غضون 3.5 أشهر باستخدام هذه المجموعة عند تشغيلها بشكل متواصل. ^{[ 32 ]} أما حالة الحقل الثنائي، فقد تم كسرها في أبريل 2004 باستخدام 2600 جهاز كمبيوتر على مدار 17 شهرًا. ^{[ 33 ]} كما تم استهداف تحدي ECC2K-130 للحقل الثنائي بواسطة الحوسبة الموزعة باستخدام وحدات المعالجة المركزية ووحدات معالجة الرسومات ووحدات FPGA. ^{[ 34 ]}

يُظهر فحص دقيق لقواعد الجمع أنه من أجل جمع نقطتين، لا يحتاج المرء فقط إلى عدة عمليات جمع وضرب في${\displaystyle \mathbb {F} _{q}}$ولكنها أيضًا عملية عكسية . العكس (لـ معطى${\displaystyle x\in \mathbb {F} _{q}}$يجد${\displaystyle y\in \mathbb {F} _{q}}$بحيث${\displaystyle xy=1}$تُعدّ عملية ( ) أبطأ بمقدار يتراوح بين عشرة ومئة ضعف من عملية الضرب ^{[ 35 ]} . مع ذلك، يمكن تمثيل النقاط على منحنى في أنظمة إحداثيات مختلفة لا تتطلب عملية عكسية لجمع نقطتين. وقد اقتُرحت عدة أنظمة من هذا القبيل: في النظام الإسقاطي، تُمثَّل كل نقطة بثلاثة إحداثيات.${\displaystyle (X,Y,Z)}$باستخدام العلاقة التالية:${\displaystyle x={\frac {X}{Z}}}$،${\displaystyle y={\frac {Y}{Z}}}$في نظام جاكوبيان ، يتم تمثيل النقطة أيضًا بثلاثة إحداثيات.${\displaystyle (X,Y,Z)}$ولكن يتم استخدام علاقة مختلفة:${\displaystyle x={\frac {X}{Z^{2}}}}$،${\displaystyle y={\frac {Y}{Z^{3}}}}$في نظام لوبيز-دهب، تكون العلاقة هي${\displaystyle x={\frac {X}{Z}}}$،${\displaystyle y={\frac {Y}{Z^{2}}}}$في نظام جاكوبيان المعدل ، تُستخدم العلاقات نفسها ولكن يتم تخزين أربعة إحداثيات واستخدامها في الحسابات.${\displaystyle (X,Y,Z,aZ^{4})}$وفي نظام جاكوبيان تشودنوفسكي ، تُستخدم خمس إحداثيات${\displaystyle (X,Y,Z,Z^{2},Z^{3})}$تجدر الإشارة إلى أنه قد توجد اصطلاحات تسمية مختلفة، فعلى سبيل المثال، يستخدم معيار IEEE P1363-2000 مصطلح "الإحداثيات الإسقاطية" للإشارة إلى ما يُعرف عادةً بالإحداثيات اليعقوبية. ويمكن تحقيق تسريع إضافي باستخدام الإحداثيات المختلطة. ^{[ 36 ]}

يمكن تنفيذ عملية الاختزال بتردد p (اللازمة للجمع والضرب) بشكل أسرع بكثير إذا كان العدد الأولي p عددًا أوليًا شبه ميرسين (عددًا أوليًا سوليناس)، أي${\displaystyle p\approx 2^{d}}$؛ على سبيل المثال،${\displaystyle p=2^{521}-1}$(P-521) أو${\displaystyle p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1.}$بالمقارنة مع اختزال باريت ، يمكن تحقيق تسريع بمقدار عشرة أضعاف. ^{[ 37 ]} هذا التسريع عملي وليس نظريًا، وينبع من حقيقة أن عمليات حساب باقي قسمة الأعداد على الأعداد القريبة من قوى العدد اثنين يمكن إجراؤها بكفاءة بواسطة أجهزة الكمبيوتر التي تعمل على الأعداد الثنائية باستخدام عمليات البت .

المنحنيات فوق${\displaystyle \mathbb {F} _{p}}$يوصي المعهد الوطني للمعايير والتكنولوجيا (NIST) في منشوره SP 800-186 باستخدام منحنيات شبه ميرسين P-256 وP-384. كما تستخدم منحنيات NIST قيمة a  =  −3، مما يُحسّن عملية الجمع في إحداثيات جاكوبيان. وقد انتقد بيرنشتاين ولانج بعض خيارات تصميم منحنيات NIST، وقدّما معايير بديلة لاختيار المنحنيات في مشروع SafeCurves. ^{[ 38 ]}

تستخدم منحنيات أخرى واسعة الانتشار أعدادًا أولية ذات أشكال خاصة تسمح بالاختزال الفعال، مثل${\displaystyle p=2^{255}-19}$لـ Curve25519 و${\displaystyle 2^{448}-2^{224}-1}$بالنسبة لـ Curve448. ^{[ 38 ]}

على عكس معظم أنظمة مسائل اللوغاريتم المنفصلة الأخرى (حيث يمكن استخدام نفس الإجراء للتربيع والضرب)، فإن عملية الجمع في نظام تصحيح الأخطاء (ECC) تختلف اختلافًا كبيرًا بين المضاعفة ( P = Q ) والجمع العام ( P ≠ Q ) اعتمادًا على نظام الإحداثيات المستخدم. ونتيجة لذلك، من المهم التصدي لهجمات القنوات الجانبية (مثل هجمات التوقيت أو هجمات تحليل الطاقة البسيطة/التفاضلية ) باستخدام، على سبيل المثال، طرق نافذة النمط الثابت (المعروفة أيضًا باسم طريقة المشط) ^{[ 39 ]} (مع ملاحظة أن هذا لا يزيد من وقت الحساب). بدلاً من ذلك، يمكن استخدام منحنى إدواردز ؛ وهو نوع خاص من المنحنيات الإهليلجية التي يمكن فيها إجراء المضاعفة والجمع بنفس العملية. ^{[ 40 ]} ومن المخاوف الأخرى لأنظمة تصحيح الأخطاء (ECC) خطر هجمات الأعطال ، خاصة عند تشغيلها على البطاقات الذكية . ^{[ 41 ]}

أعرب خبراء التشفير عن مخاوفهم من قيام وكالة الأمن القومي الأمريكية بإدخال ثغرة أمنية في مولد أرقام عشوائية زائفة واحد على الأقل يعتمد على المنحنيات الإهليلجية. ^{[ 42 ]} وتشير مذكرات داخلية سربها المتعاقد السابق مع وكالة الأمن القومي، إدوارد سنودن، إلى أن الوكالة وضعت ثغرة أمنية في معيار مولد الأرقام العشوائية الزائفة ثنائي المنحنى الإهليلجي . ^{[ 43 ]} وخلص أحد التحليلات للثغرة الأمنية المحتملة إلى أن أي مهاجم يمتلك المفتاح السري للخوارزمية يمكنه الحصول على مفاتيح التشفير باستخدام 32 بايت فقط من مخرجات مولد الأرقام العشوائية الزائفة. ^{[ 44 ]}

يقوم مشروع SafeCurves بفهرسة المنحنيات التي يسهل تنفيذها بشكل آمن، والمصممة بطريقة قابلة للتحقق بشكل كامل من قبل الجمهور لتقليل احتمالية وجود ثغرة أمنية. ^{[ 45 ]}

يمكن استخدام خوارزمية شور لكسر تشفير المنحنيات الإهليلجية عن طريق حساب اللوغاريتمات المنفصلة على حاسوب كمومي كبير بما يكفي ومقاوم للأخطاء . تشمل التقديرات المنشورة لموارد الحوسبة الكمومية اللازمة لكسر منحنى ذي معامل 256 بت (مستوى أمان 128 بت) 2330 كيوبت منطقي و126 مليار بوابة توفولي . ^{[ 46 ]} أما في حالة المنحنى الإهليلجي الثنائي، فيلزم 906 كيوبت منطقي لكسر مستوى أمان 128 بت. ^{[ 47 ]} لا تعني هذه التقديرات أن الحواسيب الكمومية الحالية قادرة على كسر أنظمة تشفير المنحنيات الإهليلجية المستخدمة، ولكنها تُعد دافعًا للتخطيط للهجرة.

في أغسطس 2024، وافق المعهد الوطني للمعايير والتكنولوجيا (NIST) على أول ثلاثة معايير فيدرالية لمعالجة المعلومات في مجال التشفير ما بعد الكمومي : FIPS 203 لـ ML-KEM، وFIPS 204 لـ ML-DSA، وFIPS 205 لـ SLH-DSA. ^{[ 48 ]} يصف المعهد هذه المعايير بأنها المعايير الرئيسية لما بعد الكموم لإنشاء المفاتيح والتوقيعات الرقمية. ^{[ 49 ]} وبالمثل، تحدد إرشادات وكالة الأمن القومي (NSA) الخاصة بـ CNSA 2.0 خوارزميات مقاومة للحوسبة الكمومية لأنظمة الأمن القومي، وتنص على أن الامتثال لـ CNSA 1.0 يظل مطلوبًا خلال المرحلة الانتقالية. ^{[ 7 ]}

تم اقتراح تبادل مفاتيح ديفي-هيلمان باستخدام التماثل الفائق التفرد كشكل ما بعد الكم لتبادل المفاتيح القائم على المنحنيات الإهليلجية باستخدام التماثلات . ^{[ 50 ]} ومع ذلك، قوضت الهجمات الكلاسيكية الجديدة أمان هذا البروتوكول. ^{[ 51 ]}

في أغسطس 2015، أعلنت وكالة الأمن القومي الأمريكية أنها تخطط للانتقال "في المستقبل القريب" إلى مجموعة تشفير جديدة مقاومة للهجمات الكمومية . "لسوء الحظ، اصطدم تزايد استخدام المنحنيات الإهليلجية بحقيقة التقدم المستمر في أبحاث الحوسبة الكمومية، مما يستلزم إعادة تقييم استراتيجيتنا التشفيرية." ^{[ 13 ]}

قد تكون تطبيقات تشفير المنحنيات الإهليلجية (ECC) عرضةً لهجمات المنحنيات غير الصالحة إذا ضربت قيمةً عدديةً سريةً بنقاط يُحددها المهاجم دون التحقق من وقوع هذه النقاط على المنحنى المقصود وفي المجموعة الفرعية الصحيحة. في مثل هذه الهجمات، قد تؤدي العمليات المتكررة على نقاط غير صالحة أو ذات رتبة منخفضة إلى تسريب معلومات حول القيمة العددية الخاصة. في عام 2019، تم الإبلاغ عن هجوم منحنى غير صالح ضد تقنية التشفير الافتراضي الآمن من AMD لاستعادة مفتاح خاص لتقنية ديفي-هيلمان (PDH). ^{[ 52 ]}