منحنى ديفي-هيلمان الإهليلجي

يترك${\displaystyle A,B\in F_{p}}$بحيث${\displaystyle B(A^{2}-4)\neq 0}$منحنى مونتغمري الإهليلجي${\displaystyle E_{M,A,B}}$هي مجموعة الكل${\displaystyle (x,y)\in F_{p}\times F_{p}}$تحقيق المعادلة${\displaystyle By^{2}=x(x^{2}+Ax+1)}$بالإضافة إلى النقطة عند اللانهاية المشار إليها بـ${\displaystyle \infty }$يُطلق على هذا الشكل اسم الشكل الأفيني للمنحنى. مجموعة جميع${\displaystyle F_{p}}$- نقاط عقلانية لـ${\displaystyle E_{M,A,B}}$، المشار إليه بـ${\displaystyle E_{M,A,B}(F_{p})}$هي مجموعة الكل${\displaystyle (x,y)\in F_{p}\times F_{p}}$مُرضٍ${\displaystyle By^{2}=x(x^{2}+Ax+1)}$ جنبا إلى جنب مع${\displaystyle \infty }$في ظل عملية جمع محددة بشكل مناسب،${\displaystyle E_{M,A,B}(F_{p})}$هي مجموعة مع${\displaystyle \infty }$باعتباره العنصر المحايد. من المعروف أن رتبة هذه المجموعة هي من مضاعفات العدد 4. في الواقع، من الممكن عادةً الحصول على${\displaystyle A}$و${\displaystyle B}$بحيث يكون ترتيب${\displaystyle E_{M,A,B}}$يكون${\displaystyle 4q}$لـ${\displaystyle q}$للحصول على مناقشات أكثر تفصيلاً حول منحنيات مونتغمري وحساباتها، يمكن الرجوع إلى المراجع التالية: ^{[ 5 ] [ 6 ] [ 7 ]}

لتحقيق الكفاءة الحسابية، يُفضّل العمل باستخدام الإحداثيات الإسقاطية. الشكل الإسقاطي لمنحنى مونتغمري${\displaystyle E_{M,A,B}}$يكون${\displaystyle BY^{2}Z=X(X^{2}+AXZ+Z^{2})}$. من أجل نقطة${\displaystyle P=[X:Y:Z]}$على${\displaystyle E_{M,A,B}}$، ال${\displaystyle x}$خريطة إحداثيات${\displaystyle x}$وهو ما يلي: ^{[ 7 ]}${\displaystyle x(P)=[X:Z]}$لو${\displaystyle Z\neq 0}$و${\displaystyle x(P)=[1:0]}$لو${\displaystyle P=[0:1:0]}$قدّم بيرنشتاين ^{[ 8 ] [ 9 ]} الخريطة${\displaystyle x_{0}}$على النحو التالي:${\displaystyle x_{0}(X:Z)=XZ^{p-2}}$وهو ما يُحدد لجميع قيم${\displaystyle X}$و${\displaystyle Z}$في${\displaystyle F_{p}}$استنادًا إلى ميلر ^{[ 10 ]} ، ومونتغمري ^{[ 5 ]} ، وبرنشتاين ^{[ 9 ]،} يمكن إجراء اتفاقية مفاتيح ديفي-هيلمان على منحنى مونتغمري على النحو التالي.${\displaystyle Q}$ليكن مولدًا لمجموعة فرعية من الرتبة الأولية من ${\displaystyle E_{M,A,B}(F_{p})}$تختار أليس مفتاحًا سريًا${\displaystyle s}$وله مفتاح عام${\displaystyle x_{0}(sQ)}$يختار بوب مفتاحًا سريًا${\displaystyle t}$وله مفتاح عام${\displaystyle x_{0}(tQ)}$المفتاح السري المشترك بين أليس وبوب هو${\displaystyle x_{0}(stQ)}$باستخدام الحواسيب التقليدية، وهي الطريقة الأكثر شهرة للحصول على${\displaystyle x_{0}(stQ)}$من${\displaystyle Q,x_{0}(sQ)}$و${\displaystyle x_{0}(tQ)}$يتطلب حوالي${\displaystyle O(p^{1/2})}$الوقت باستخدام خوارزمية بولاردز رو . ^{[ 11 ]}

أشهر مثال على منحنى مونتغمري هو المنحنى 25519 الذي قدمه بيرنشتاين. ^{[ 9 ]} بالنسبة للمنحنى 25519،${\displaystyle p=2^{255}-19,A=486662}$و${\displaystyle B=1}$أما منحنى مونتغمري الآخر الذي يُعد جزءًا من TLS 1.3 فهو المنحنى 448 الذي قدمه هامبورغ. ^{[ 12 ]} بالنسبة للمنحنى 448،${\displaystyle p=2^{448}-2^{224}-1,A=156326}$و${\displaystyle B=1}$تم اقتراح منحنيين من منحنيات مونتغمري يُطلق عليهما M[4698] و M[4058]، وهما منافسان للمنحنيين Curve25519 و Curve448 على التوالي، في ^{[ 13 ]} . بالنسبة إلى M[4698]،${\displaystyle p=2^{251}-9,A=4698,B=1}$وبالنسبة لـ M[4058]،${\displaystyle p=2^{444}-17,A=4058,B=1}$عند مستوى أمان 256 بت، تم اقتراح ثلاث منحنيات مونتغمري تسمى M[996558] وM[952902] وM[1504058]. ^{[ 14 ]} بالنسبة لـ M[996558]،${\displaystyle p=2^{506}-45,A=996558,B=1}$، بالنسبة لـ M[952902]،${\displaystyle p=2^{510}-75,A=952902,B=1}$وبالنسبة لـ M[1504058]،${\displaystyle p=2^{521}-1,A=1504058,B=1}$على التوالي. وبصرف النظر عن هذين المقترحين، يمكن العثور على مقترحات أخرى لمنحنيات مونتغمري في ^{[ 15 ] .}