ناقش مبدأ التنفيذ وقابلية التوسع في Ed25519
ستقدم هذه المقالة مبدأ التنفيذ وقابلية التوسع لخوارزمية التوقيع الرقمي القائمة على المنحنى البيضاوي Ed25519.
** بقلم: آه وي **
Ed25519 هي خوارزمية توقيع رقمي تعتمد على منحنى بيضاوي ، وهي فعالة وآمنة ومستخدمة على نطاق واسع. يتم استخدامه في TLS 1.3 و SSH و Tor و ZCash و WhatsApp و Signal. تشرح هذه المقالة بشكل أساسي النقاط التالية:
- تقديم القليل من المعرفة بنظرية المجموعة ، والغرض من ذلك هو السماح لكل فرد بالحصول على حدس حول مبدأ Ed25519 ومشكلة قابلية التوسع الخاصة به. لفهم أعمق ، تحتاج إلى الرجوع إلى مواد أخرى ؛
- شرح تطبيق ed25519 للإصدار 1.0.1 من مكتبة الصدأ ed25519-dalek ؛
- شرح تمدد المكتبة.
مراجعة أساسيات الرياضيات
** تعريف المجموعات وخصائصها **
نظرية المجموعة هي محتوى أبحاث الجبر المجرد ، لكن بعض أفكار الجبر المجرد مألوفة جدًا للمبرمجين. الوراثة في وجوه المنحى مثال جيد ، كلنا نعلم أنه بعد أن ترث الفئات الفرعية الصنف الأصل ، يمكنهم استخدام الطرق المحددة في الصنف الأصل. يمكن فهم الجبر المجرد على أنه تحديد بعض الخصائص لبنية بيانات مجردة ، والنظريات المشتقة من هذه الخصائص تنطبق على جميع الفئات الفرعية.
باستخدام الاستعارة الآن ، دعنا نرى كيف يتم تعريف بنية بيانات المجموعة.
تتكون المجموعة من عملية (يُشار إليها بأي عملية ثنائية) وبعض العناصر التي تفي بالخصائص التالية:
يمكن اشتقاق العديد من النظريات المثيرة للاهتمام من هذا:
لإعطاء بعض الأمثلة:
- الأعداد الصحيحة … ، 2 ، −1 ، 0 ، 1 ، 2 ، … والإضافة مجموعة لأنها تحقق الخصائص الأربعة المذكورة أعلاه
- الأعداد الصحيحة والضرب ليست مجموعات لأنها لا تحقق إمكانية الانعكاس ، 4 × 1/4 = 1 ، لكن 1/4 ليس عددًا صحيحًا
** قص المصطلحات النظرية الجماعية **
** نظرية لاغرانج **
قدم الآن نظرية مثيرة للاهتمام ، اشتقاق هذه النظرية موجود في الفيديو المقتبس في نهاية المقالة.
** “ترتيب المجموعة قابل للقسمة حسب ترتيب المجموعة الفرعية.” **
لماذا تعتبر هذه النظرية مثيرة للاهتمام ، ليس فقط لأن عملية الإثبات الخاصة بها تربط الكثير من المعرفة التي تم تقديمها للتو ، ولكن أيضًا بسبب الاستنتاجات التالية:
** "إذا كان ترتيب المجموعة عددًا أوليًا ، فوفقًا لنظرية لاغرانج ، يجب أن يكون ترتيب المجموعة الفرعية أو. جميع العناصر في المجموعة هي مولدات باستثناء
تنفيذ Ed25519
الآن دعنا نتحدث عن Ed25519 ، وهو أحد خوارزميات EdDSA. يحتوي EdDSA على 11 معلمة (التحديد المحدد لهذه المعلمات له تأثير كبير على أمان وأداء الخوارزمية. للاختيار المحدد لـ Ed25519 ، يرجى الرجوع إلى الرابط (
بالإضافة إلى ذلك ، تجدر الإشارة إلى أن هذه الخوارزمية تستخدم منحنى إهليلجي يسمى Curve25519 (. بالنسبة للمنحنى الإهليلجي ، نحتاج فقط إلى معرفة أن هناك العديد والعديد من النقاط عليه ، ويمكن أن يؤدي إضافة هذه النقاط إلى الحصول على نقاط جديدة. النقاط الجديدة لا تزال على المنحنى وهذه النقاط وهذه الإضافة يمكن أن تشكل مجموعة. لاحظ أن إضافة المنحنى البيضاوي (محددة بشكل خاص.
نحن نتفق على الترميز التالي:
هذه خوارزمية تفاعلية ، لكن لا يهم ، هناك خدعة تسمى Fiat - Shamir الإرشادية (يمكنها تحويل أي خوارزمية تفاعلية إلى خوارزمية غير تفاعلية. في النهاية سنستخدم خوارزمية غير تفاعلية.
ستوفر لنا خوارزمية التوقيع الرقمي واجهة برمجة التطبيقات التالية:
** تنفيذ KeyGen **
إخراج مفتاح خاص ومفتاح عام:
- إنشاء بذرة بشكل عشوائي (تحتوي هذه البذرة على 32 بايت. نستخدم مولد أرقام عشوائي آمن مشفرًا يأتي مع النظام.
حانة fn تولد (csprng: & mut T) -> SecretKeywhere
T: CryptoRng + RngCore ،
{
اسمح لـ mut sk: SecretKey = SecretKey ([0u8 ؛ 32]) ؛
csprng.fill \ _bytes (& mut sk.0) ؛
كورونا
}
- قم بتوسيع البذرة الآن إلى 64 بايت (أي ، xseed في الشكل. إن 32 بايت المنخفضة من xseed هي مفتاحنا الخاص (المعروف أيضًا باسم a). تسمى وحدات البايت العالية البالغة 32 بايت nonce ، والتي سيتم استخدامها لاحقًا فيها ، وظيفتها مشابهة لمباشر المجال.
pub هيكلة ExpandedSecretKey {// xseed pub (crate) key: Scalar، // a
حانة (قفص) nonce: [u8 ؛ 32] ، // nonce
}
fn من (secret \ _key: & 'a SecretKey) -> ExpandedSecretKey {
دع mut h: Sha512 = Sha512 :: default () ؛
اسمح لـ mut hash: [u8؛ 64] = [0u8 ؛ 64] ؛
دع موت أقل: [u8؛ 32] = [0u8 ؛ 32] ؛
دع موت الجزء العلوي: [u8؛ 32] = [0u8 ؛ 32] ؛
h.update (سر \ _key.as \ _bytes ()) ؛
hash.copy \ _from \ _slice (h.finalize (). as \ _slice ()) ؛
Lower.copy \ _from \ _slice (& hash [00…32]) ؛
upper.copy \ _from \ _slice (& hash [32…64]) ؛
// هذه الخطوة هي المشبك
أدنى [0] & = 248 ؛
أدنى [31] & = 63 ؛
أدنى [31] | = 64 ؛
ExpandedSecretKey {مفتاح: Scalar :: from \ _bits (Lower)، nonce: upper،}
}
- استخدم المفتاح الخاص لإنشاء المفتاح العام (المفتاح العمومي هو نقطة على المنحنى البيضاوي. على وجه التحديد ، نستخدم النقطة الأساسية للمنحنى الناقص لإجراء عملية ضرب المنحنى البيضاوي للحصول على المفتاح العام. العدد القياسي في الضرب يتم الحصول عليها عن طريق إقران المفتاح الخاص ، قم بإجراء تجزئة للحصول عليه.
pub هيكلة ExpandedSecretKey {// xseed pub (crate) key: Scalar، // a
حانة (قفص) nonce: [u8 ؛ 32] ، // nonce
}
fn من (secret \ _key: & 'a SecretKey) -> ExpandedSecretKey {
دع mut h: Sha512 = Sha512 :: default () ؛
اسمح لـ mut hash: [u8؛ 64] = [0u8 ؛ 64] ؛
دع موت أقل: [u8؛ 32] = [0u8 ؛ 32] ؛
دع موت الجزء العلوي: [u8؛ 32] = [0u8 ؛ 32] ؛
h.update (سر \ _key.as \ _bytes ()) ؛
hash.copy \ _from \ _slice (h.finalize (). as \ _slice ()) ؛
Lower.copy \ _from \ _slice (& hash [00…32]) ؛
upper.copy \ _from \ _slice (& التجزئة [32…64]) ؛
// هذه الخطوة هي المشبك
أدنى [0] & = 248 ؛
أدنى [31] & = 63 ؛
أدنى [31] | = 64 ؛
ExpandedSecretKey {مفتاح: Scalar :: from \ _bits (Lower)، nonce: upper،}
}
تنفيذ التوقيع
هنا يمكنك ذكر تقنية Fiat Shamir التي تم ذكرها سابقًا. في الواقع ، ما عليك سوى استبدال جميع الأرقام العشوائية التي يوفرها Verifier بنتيجة دالة التجزئة. انظر تعليقات التعليمات البرمجية للحصول على التفاصيل.
علامة pub fn (& self ، message: & [u8] ، public \ _key: & PublicKey) -> ed25519 :: التوقيع {
دع mut h: Sha512 = Sha512 :: new () ؛
دع R: CompressedEdwardsY ؛
دعونا ص: عددي.
دعونا ق: عددي.
دع ك: عددي ؛
ح. التحديث (& غير ذاتي) ؛
ح. التحديث (والرسالة) ؛
r = Scalar :: from \ _hash (h)؛ // r هو رقم عشوائي في الخوارزمية التفاعلية ، لكن هنا نستخدم التجزئة.
R = (& r \ * & ثوابت :: ED25519 \ _BASEPOINT \ _TABLE) .compress () ؛ // R = [r] ب
ح = Sha512 :: new () ؛
ح. التحديث (R.as \ _bytes ()) ؛
h.update (public \ _key.as \ _bytes ()) ؛
ح. التحديث (والرسالة) ؛
ك = عددي :: من \ _ هاش (ح) ؛ // h = Sha512 (R || A || M)
s = & (& k \ * & self.key) + & r؛ // s = r + h \ * a ، h في الأصل رقم عشوائي
التوقيع الداخلي {R، s} .into ()
}
تنفيذ التحقق
المدقق الضمنيed25519::Signature لـ PublicKey {
[السماح (non \ _snake \ _case)]
fn تحقق (
&الذات،
رسالة: & [u8] و
التوقيع: & ed25519 :: التوقيع
) -> النتيجة <() ، خطأ التوقيع>
{
السماح للتوقيع = InternalSignature :: try \ _from (signature) ؟؛
دع mut h: Sha512 = Sha512 :: new () ؛
دع R: EdwardsPoint ؛
دع ك: عددي ؛
دع ناقص \ _A: EdwardsPoint = -self.1 ؛
h.update (signature.R.as \ _bytes ()) ؛
h.update (self.as \ _bytes ()) ؛
ح. التحديث (والرسالة) ؛
k = Scalar :: from \ _hash (h)؛ // حساب h هو نفسه كما في الإشارة ، h = Sha512 (R || A || M)
R = EdwardsPoint :: time \ _double \ _scalar \ _mul \ _basepoint (& k، & (minus \ _A)، & signature.s) ؛ // R '= [s] ب - [h] أ
إذا كانت R.compress () == signature.R {// إذا كانت R '== R ، فإن نتيجة التحقق صحيحة.
نعم(())
} آخر {
خطأ (InternalError :: VerifyError.into ())
}
}
}
- عنوان الكود (*
قضايا قابلية التوسع
هناك العديد من الأماكن التي يجب الانتباه إليها عند تنفيذ واستخدام خوارزميات التشفير. عندما نقول أن خوارزمية التوقيع الرقمي آمنة ، فهذا يعني عمومًا أنه حتى إذا تمكن المهاجم من الحصول على توقيع أي رسالة (هجوم الرسائل المختار) ، فلا يزال المهاجم غير قادر على تزوير التوقيع. Ed25519 يلبي هذه الخاصية ، لكن هذا لا يعني أن Ed25519 آمن تمامًا. كما ورد في الورقة الأصلية أن مشكلة قابلية التوسع مقبولة ، والخوارزمية الأصلية بها هذه المشكلة.
بهذه الطريقة ، يمكن التحقق بنجاح من كل من التوقيع المُنشأ حديثًا والتوقيع القديم. تخبرنا مشكلة القابلية للتطويع أن التوقيع ليس حتميًا بالنسبة للرسالة والمفتاح العام.عندما تواجه خوارزمية التوقيع مشكلة قابلية للتطويع وتفترض الكود أن التوقيع حتمي ، فمن المحتمل أن تكون هناك ثغرات.
وفقًا للمعيار (في الواقع ، لا توجد مشكلة في قابلية التوسع. لأنه في عملية التحقق ، سوف نتحقق مما إذا كانت أقل من ، إذا كانت نتيجة الفحص غير صحيحة ، يفشل التحقق. ولكن المعيار (يظهر بعد الورقة (لذلك في البيئة الفعلية ، لا تزال هناك تطبيقات لـ Ed25519 بها مشكلات قابلية التوسع وتتطلب عمليات تنفيذ نقوم بفحصها.
لخص
شكرًا
- بفضل Safeheron ، المزود الرائد لخدمات الحفظ الذاتي للأصول الرقمية الشاملة ، لتقديم المشورة الفنية المهنية. *
** المراجع **
[1] .
[2] .
[3] .
[4] .
[5] . يستخدم الباحثون نظرية المجموعة لتسريع الخوارزميات - مقدمة للمجموعات
