elikaski/ecc_attacksالهجمات المعروفة على تشفير المنحنيات الإهليلجية
في السنوات الأخيرة، أصبح نهج التشفير بالمنحنيات الإهليلجية (Elliptic Curve Cryptography) شائعًا بسبب كفاءته العالية وأمانه القوي. الغرض من هذه المقالة هو تقديم هذا الموضوع بطريقة أوضح نسبيًا مما هو موجود اليوم على الإنترنت.
في هذه المقالة سأقدّم ما هي المنحنيات الإهليلجية، والعمليات الأساسية التي يمكن إجراؤها عليها، وكيف يمكن استخدامها في السياق التشفيري. يتكوّن الجزء الأكبر من هذه المقالة من أمثلة على هجمات معروفة على تطبيقات غير صحيحة أو استخدامات خاطئة لها. طوال المقالة أحاول تقسيم الشرح إلى جزء بديهي رفيع المستوى، وجزء رياضي يتعمق في التفاصيل. القارئ مدعو للتركيز على الجزء الذي يهمه في ذلك الموضع، وتخطي الأجزاء الأقل أهمية.
قراءة ممتعة!
بشكل عام، المنحنى الإهليلجي هو نوع من الخطوط المنحنية. مثال على ذلك القطع المكافئ، الذي تكون معادلته من الشكل $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ ويبدو هكذا:
في سياق التشفير، من المعتاد استخدام منحنيات إهليلجية تكون معادلتها من الشكل
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
على سبيل المثال، منحنى إهليلجي يقابل المعادلة $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ يبدو هكذا:
تحدد معادلة المنحنى العلاقة بين إحداثي 𝑥 لنقطة على المنحنى وإحداثي 𝑦 الخاص بها. في السياق التشفيري، نقصر 𝑥، 𝑦، 𝑎، 𝑏 على أن تكون أعدادًا صحيحة، ونقصر الحسابات على أنها بتردد (modulo) عدد أولي كبير. إذن تكون معادلة المنحنى الإهليلجي هي:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
هذا يعني أن لدينا عددًا محدودًا من النقاط على المنحنى. باللغة الرياضية، يُعرَّف المنحنى على أنه معرف على حقل محدود من الرتبة 𝑝. ونتيجة لذلك، ليس بالضرورة أن يكون لكل إحداثي 𝑥 نقطة مقابلة على المنحنى، لأنه قد يكون الإحداثي 𝑦 المقابل له ليس عددًا صحيحًا.
مجموعة النقاط على المنحنى تتكون من أزواج من الأعداد الصحيحة (𝑥, 𝑦) التي تحقق معادلة المنحنى. بالإضافة إلى هذه النقاط، تُعرَّف نقطة خاصة أخرى تسمى «اللانهاية» (Infinity)، ويُرمز لها بـ 𝒪. باللغة الرياضية، هذه النقطة هي العنصر المحايد لمجموعة النقاط على المنحنى بالنسبة لعملية الجمع، والتي سنعرّفها في القسم التالي. عدد النقاط على المنحنى (بما في ذلك النقطة 𝒪) يسمى «رتبة المنحنى».
ملاحظة أخرى هي أن المنحنيات الإهليلجية متناظرة حول محور X. وهذا يعني أنه إذا كانت النقطة 𝑃 = (𝑥, 𝑦) على المنحنى، فإن النقطة −𝑃 = (𝑥, −𝑦) تكون أيضًا على المنحنى. في الواقع، تُعتبر هاتان النقطتان «معكوسين» لبعضهما البعض (ومن هنا جاء الترميز −𝑃 للنقطة الثانية)، ويُعرَّف ناتج عملية الجمع بينهما على أنه العنصر المحايد 𝒪.
توفر نظرية تُسمى نظرية هاس (Hasse's Theorem) تقديرًا لـ #𝐸، رتبة المنحنى، وهو من مرتبة Θ(𝑝). وبشكل أكثر دقة:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
بالنظر إلى نقطتين على المنحنى، يمكن تعريف عملية جمع بينهما، ينتج عنها نقطة ثالثة تقع أيضًا على المنحنى. لإيجاد هذه النقطة هندسيًا، نرسم خطًا بين النقطتين المعطاتين، ونواصله حتى يتقاطع مع المنحنى عند نقطة ثالثة. تُعكس هذه النقطة بالنسبة لمحور 𝑋، وتُعرَّف النقطة الناتجة على أنها ناتج الجمع.
إليك مخطط يوضح كيف يمكن إيجاد النقطة 𝑃 + 𝑄 عند توفر النقطتين 𝑃 و𝑄:
سؤال قد يطرح من هذا الوصف: ماذا يحدث إذا لم يتقاطع الخط المرسوم بين النقطتين مع المنحنى مرة أخرى؟ في هذه الحالة يُقال إن الخط يتقاطع مع المنحنى عند «اللانهاية»، ويكون ناتج الجمع هو النقطة 𝒪. لاحظ أن هذه الحالة تحدث إذا كان الخط المرسوم عموديًا، أي أننا نحاول جمع نقطة 𝑃 مع نقطتها المعكوسة −𝑃:
تُشتق من هذا متطابقتان أساسيتان. لكل نقطة 𝑃 يتحقق ما يلي:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
سؤال آخر يطرحه الوصف الهندسي: كيف نجمع نقطة إلى نفسها؟ رأينا أنه من أجل جمع نقطتين مختلفتين 𝑃 و𝑄، نرسم خطًا بينهما وننظر إلى نقطة تقاطع امتداده مع المنحنى. بشكل بديهي، سنبقي 𝑃 ثابتًا، وننظر إلى الخط الذي يتشكل بينما نحرّك 𝑄 «أقرب فأقرب» إلى 𝑃، حتى تندمج 𝑄 مع 𝑃. ما سنحصل عليه هو خط يصبح أكثر فأكثر «مماسًا» للمنحنى عند النقطة 𝑃، وهذا هو بالضبط الخط الذي سننظر إليه عندما نريد جمع 𝑃 إلى نفسها:
لجمع نقطة 𝑃 إلى نفسها، نرسم مماسًا للمنحنى عند النقطة 𝑃، ونواصله حتى يتقاطع مع المنحنى عند نقطة ثانية. تُعكس هذه النقطة بالنسبة لمحور 𝑋، وتُعرَّف النقطة الناتجة على أنها ناتج الجمع. من المعتاد ترميز ناتج الجمع على أنه 𝑃 + 𝑃 = 2𝑃. ومرة أخرى، إذا لم يتقاطع المماس مع المنحنى عند نقطة ثانية، فيُقال إنه يتقاطع مع المنحنى عند «اللانهاية»، ويكون ناتج الجمع في هذه الحالة هو النقطة 𝒪.
هذه الأوصاف الهندسية المرئية توضح بشكل جميل وتساعدنا على فهم كيفية عمل جمع النقاط. لكن كيف نحسبه فعليًا؟ معادلات رياضية، بالطبع!
بالنظر إلى النقطتين $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ و $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$، فإن ناتج جمعهما هو النقطة $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ بحيث:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
حيث يُعرَّف 𝜆 على أنه ميل الخط الواصل بين النقطتين إذا كانتا مختلفتين، وميل المماس للمنحنى عند النقطة إذا كانت النقطة مضافة إلى نفسها. رسميًا:
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
الحسابات الرياضية الكامنة خلف جمع النقاط ليست جوهرية لبقية المقالة. لذلك يمكننا النظر إلى جمع النقاط على أنه صندوق أسود يستقبل نقطتين على المنحنى ويعيد نقطة ثالثة تقع أيضًا على المنحنى.
رأينا أنه من الممكن جمع نقطة 𝑃 إلى نفسها، وأشرنا إلى النقطة الناتجة بـ 2𝑃. إذا أضفنا النقطة 𝑃 إلى هذه النتيجة مرة أخرى، سنصل إلى نقطة يُشار إليها بـ 3𝑃، وهكذا. بهذه الطريقة يمكن تعريف «ضرب» نقطة في ثابت، عن طريق تكرار جمع النقطة إلى نفسها (على غرار الضرب بين الأعداد):
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
يبدو أنه لضرب نقطة في عدد 𝑛 نحتاج إلى تنفيذ 𝑛 عملية جمع بين النقاط. وذلك لأنه عند نقطة بداية معينة، من الصعب معرفة مسبقًا أين ستقع النقطة «الأخيرة»، دون الوصول إليها «خطوة بخطوة». مثل هذه الحسابات ستكون غير فعّالة جدًا، لأن 𝑛 قد يكون كبيرًا جدًا.
لهذا الغرض، توجد خوارزمية Double And Add (ضاعف وأضف)، حيث نبدأ من النقطة 𝑃، ثم لكل بت في التمثيل الثنائي للعدد 𝑛، تُضرب النقطة الحالية في 2 (أي تُضاف إلى نفسها)، وتُضاف إلى النتيجة إذا كانت قيمة البت هي 1. التعقيد الزمني لهذه الخوارزمية هو 𝑂(log 𝑛)، وهي تسمح بضرب النقاط في أعداد كبيرة جدًا بكفاءة.
خاصية مهمة لضرب النقاط سنستخدمها لاحقًا هي أنه لكل نقطة 𝑃 وزوج من الأعداد 𝑎، 𝑏 يتحقق:
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
بشكل بديهي، لنفترض أننا نبدأ من النقطة 𝑃، ونأخذ 𝑎 خطوة منها، ونصل إلى النقطة 𝑎𝑃. من هذه النقطة، نأخذ 𝑏 خطوة «بحجم» 𝑎 ونصل إلى النقطة 𝑏(𝑎𝑃). بدلاً من ذلك، في سيناريو آخر، يمكن أن نبدأ من النقطة 𝑃، ونأخذ 𝑏 خطوة منها ونصل إلى النقطة 𝑏𝑃. ثم من هذه النقطة نأخذ 𝑎 خطوة «بحجم» 𝑏 ونصل إلى النقطة 𝑎(𝑏𝑃).
في كلا السيناريوهين أخذنا نفس العدد الإجمالي من الخطوات 𝑎𝑏 من النقطة 𝑃، لذا وصلنا في كلا السيناريوهين إلى نفس النقطة النهائية. رياضيًا، ضرب نقطة في ثابت هو عملية تجميعية (associative).
إذا بدأنا من نقطة 𝑃 وأضفناها إلى نفسها مرارًا وتكرارًا، فسنصل في كل خطوة من هذه الخطوات إلى نقطة جديدة على المنحنى. ولأن عدد النقاط على المنحنى محدود، فسنصل في مرحلة ما إلى نقاط سبق أن وصلنا إليها، وسنكون في نوع من الحلقة، أو «دائرة». وبشكل أكثر دقة، في مرحلة ما سنصل إلى النقطة -𝑃، وفي الخطوة التالية سنصل إلى النقطة 𝒪، وفي الخطوة التي تليها سنصل مجددًا إلى النقطة 𝑃 التي بدأنا منها.
النقطة التي تنشئ مثل هذه «الدائرة» تُسمى مولّدًا (Generator)، لأنه يمكن توليد «الدائرة» بأكملها منها، ومن المعتاد ترميزها بالحرف 𝐺. عدد النقاط في «الدائرة» (بما في ذلك النقطة 𝒪) يُسمى «رتبة المولّد 𝐺»، ويُرمز إليه عادةً بـ 𝑛. كل نقطة على المنحنى تشكل «دائرة» ما. رياضيًا، مجموعة النقاط في هذه «الدائرة» هي زمرة دورية (cyclic group).
خاصية مثيرة للاهتمام تنتج عن ذلك هي أن ضرب نقطة 𝐺 في رتبتها 𝑛 يعطينا نقطة اللانهاية:
𝑛𝐺 = 𝒪
«بالنظر إلى نقطتين 𝑃 و𝑄 بحيث 𝑄 = 𝑥𝑃 لقيمة ما 𝑥، من الصعب إيجاد 𝑥.»
وبالكلمات، لنفترض أن شخصًا ما بدأ من نقطة بداية معينة، وأخذ عددًا معينًا من الخطوات منها، ووصل إلى نقطة نهائية. بالنظر إلى نقطة البداية والنقطة النهائية، كيف يمكننا معرفة عدد الخطوات التي أخذها؟
الإجابة على هذا السؤال ليست بديهية جدًا، لأنه من الصعب التنبؤ مسبقًا من نقطة بداية بالنقاط التي سيتم الوصول إليها عن طريق أخذ خطوات منها. الحل الساذج يمكن أن يكون أن نبدأ من 𝑃 بأنفسنا، ونتقدم منها خطوة بخطوة ونعدّ الخطوات التي نأخذها، حتى نصل إلى 𝑄. تعقيد هذا الحل هو 𝑂(𝑥)، وهو غير ممكن إذا كان معروفًا أن 𝑥 عدد كبير، على سبيل المثال إذا كانت 𝑥 هي 256 bit.
تُسمى هذه المشكلة مشكلة اللوغاريتم المتقطع للمنحنيات الإهليلجية (Elliptic Curve Discrete Logarithm Problem - ECDLP)، وهي مشكلة صعبة. لكن ما مدى صعوبتها؟
في السياق التشفيري، من المعتاد قياس «صعوبة المشكلات» أو «قوة نظام تشفيري» بمقياس يُسمى Security Level. وفقًا لهذا المقياس، يُقال إن مشكلة ما تتمتع بـ«أمان بمقدار 𝑛 بت» إذا كان أفضل هجوم معروف يحل المشكلة في $𝑂(2^𝑛)$ خطوة.
حاليًا، أفضل خوارزمية تحل مشكلة ECDLP تفعل ذلك بتعقيد $𝑂(\sqrt n)$، حيث 𝑛 هي رتبة النقطة 𝑃، وتفعل ذلك باستخدام هجوم اللقاء في المنتصف (Meet In The Middle). عندما يتم اختيار نقطة برتبة كبيرة بما يكفي، يصبح حلها غير ممكن، ومن هنا تأتي قوة المشكلة.
على سبيل المثال، إذا اخترنا 𝑛 بحجم 256 bit، نحصل على أن مشكلة ECDLP لديها مستوى أمان بمقدار 128 bit. للمقارنة، لتحقيق نفس مستوى الأمان البالغ 128 bit في تشفير RSA، الذي يعتمد على مشكلة تحليل الأعداد الصحيحة إلى عوامل، يلزم مفتاح عام بحجم 3072 bit. وهذا يجعل استخدام المنحنيات الإهليلجية أكثر كفاءة حسابيًا نسبيًا.
بعد كل هذه المقدمة إلى عالم المنحنيات الإهليلجية، سننتقل لنرى ما يمكن فعله بها في سياق تشفيري. كما نعرف، تعتمد الأنظمة التشفيرية عادةً على «مشكلة صعبة» يصعب حلها. مثال ذلك RSA مع مشكلة تحليل عدد إلى عوامل التي ذكرناها، أو بروتوكول Diffie-Hellman مع مشكلة اللوغاريتم المتقطع. النظام التشفيري الذي يعتمد على مشكلة ECDLP في منحنى إهليلجي ينتمي إلى عائلة التشفير بالمنحنيات الإهليلجية (Elliptic Curve Cryptography)، أو اختصارًا ECC.
لنبدأ بقصة. تخيل أنك في حفلة - غرفة مليئة بالأشخاص، حيث يمكن للجميع التحدث إلى الجميع والجميع يسمع الجميع. في هذه الغرفة أيضًا يوجد أليس وبوب، اللذان لم يلتقيا من قبل. أليس معجبة بوب، وتريد أن تطلب منه الخروج. أليس خجولة بعض الشيء، لذا تريد إخبار بوب بهذه الرسالة السرية دون أن يسمعها ضيوف الحفلة الآخرون. لم ينسق أليس وبوب أي شيء مسبقًا، وكل ما تقوله أليس إلى بوب سيسمعه جميع الضيوف الآخرين في الحفلة. كيف يمكن لأليس أن تخبر بوب بالرسالة دون أن يسمعها أي شخص آخر؟
إذا كانت إجابتك «المنحنيات الإهليلجية»، فأنت محق!
ستختار أليس منحنى إهليلجيًا معينًا ومولّدًا فيه، وتخبر بوب بهما. تحديدًا، ستمرر أليس إلى بوب (وإلى كل شخص آخر في الغرفة) معاملي المنحنى 𝑎، 𝑏، والمعامل 𝑝، والمولّد 𝐺. بالإضافة إلى ذلك، ستختار أليس قيمة $𝑑_𝐴$ في النطاق $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$ حيث 𝑛 هي رتبة 𝐺. تُسمى القيمة $𝑑_𝐴$ المفتاح الخاص لأليس. ستحسب أليس النقطة $𝐴 = 𝑑_𝐴𝐺$، التي تُسمى المفتاح العام لأليس، وتخبر بوب بها. وبالمثل، سيختار بوب مفتاحًا خاصًا $𝑑_𝐵$، ويحسب النقطة $𝐵 = 𝑑_𝐵𝐺$، التي تُسمى المفتاح العام لبوب، ويخبر أليس بها.
ستأخذ أليس المفتاح العام لبوب، وتضرب تلك النقطة في مفتاحها الخاص، وتصل إلى نقطة ثالثة $𝑃_𝐴 = 𝑑_𝐴𝐵$. وبالمثل، سيأخذ بوب المفتاح العام لأليس، ويضربه في مفتاحه الخاص، ويصل إلى نقطة ثالثة خاصة به $𝑃_𝐵 = 𝑑_𝐵𝐴$. إذا فحصنا النقطتين اللتين وصلت إليهما أليس وبوب بشكل منفصل، نجد أنهما وصلا إلى النقطة نفسها! هذه الحقيقة تأتي من خاصية التجميع لضرب نقطة في ثابت التي رأيناها سابقًا:
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
في نهاية العملية بأكملها، تمكن أليس وبوب من التوصل إلى اتفاق على نقطة معينة على المنحنى، ولم يقم أي منهما في أي مرحلة بتمرير تلك النقطة إلى الشخص الآخر. المعلومات التي سمعها الجميع هي: 𝑎، 𝑏، 𝑝، 𝐺، 𝐴، 𝐵. الشخص الموجود في الغرفة والذي يستمع إلى هذه المعلومات لا يمكنه إيجاد النقطة التي اتفق عليها أليس وبوب باستخدامها.
هذا لأنه إذا أراد شخص آخر في الغرفة إيجاد تلك النقطة، فسيحتاج إلى معرفة إما المفتاح الخاص لأليس أو المفتاح الخاص لبوب من أجل ضرب 𝐵 أو 𝐴 بهما. لإيجاد المفتاح الخاص لأليس على سبيل المثال، سينظر إلى $𝐴 = 𝑑_𝐴𝐺$، لأن هذه هي المعلومة الوحيدة التي تم إرسالها والتي «تحتوي» المفتاح الخاص لأليس. بالنظر إلى 𝐺 و $𝑑_𝐴𝐺$، فإن إيجاد $𝑑_𝐴$ يعادل حل مشكلة اللوغاريتم المتقطع في المنحنيات الإهليلجية، وهي كما ذُكر مشكلة صعبة.
يُسمى هذا البروتوكول الجميل: Elliptic Curve Diffie-Hellman (ECDH).
لم ننتهِ من قصتنا. على الرغم من أن أليس وبوب اتفقا على نقطة سرية مشتركة، إلا أن أليس لم تطلب بعد من بوب الموعد الذي تريده بشدة.
بعد أن يتفق الطرفان على نقطة سرية مشتركة، يمكنهما استخدامها كمفتاح تشفير لأي طريقة تشفير، مثل AES، ومن تلك النقطة يمكنهما التواصل بأمان عبر التشفير.
من الشائع أخذ أحد الإحداثيين 𝑥 أو 𝑦 للنقطة واستخدامه. للحفاظ على الأمان، يُنصح بتجزئة القيمة المحددة واستخدام ناتج التجزئة فقط كمفتاح تشفير. عمليًا، في بعض الأحيان تكون القيمة كبيرة جدًا بحيث لا يمكن استخدامها كمفتاح تشفير. على سبيل المثال، إذا كانت دالة التجزئة المستخدمة هي SHA-1، فإن طول مخرجاتها هو 160 bit، بينما يتطلب تشفير AES 128 bit فقط. في هذه الحالة، من المعتاد استخدام 128 bits فقط من أصل 160، وتجاهل الباقي.
على أي حال، في هذه المرحلة يتفق أليس وبوب على مفتاح تشفير، وهما الوحيدان اللذان يعرفانه. من هذه النقطة فصاعدًا يتواصلان عبر التشفير، ولا يمكن لأي شخص يستمع في الغرفة فهم ما يقولانه.
إليك مخطط للبروتوكول:
باستخدام المفتاح المتفق عليه، تشفر أليس الرسالة «مرحبًا بوب، هل ترغب في الخروج لتناول القهوة مساء الغد؟»، وتمرر الرسالة المشفرة إلى بوب. يقوم بوب بفك تشفير الرسالة بالمفتاح الذي يعرفه أيضًا. تأمل أليس أن يقول بوب نعم، لكن هذا ليس جزءًا من البروتوكول.
في بروتوكول Diffie-Hellman (DH) المعروف، يرسل الطرفان علنًا عددًا أوليًا 𝑝 ومولّدًا 𝑔 موجودًا في الزمرة المقابلة للقيمة 𝑝. تولد أليس عشوائيًا مفتاحًا خاصًا 𝑎 وتبث علنًا مفتاحها العام $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$. وبالمثل، يولد بوب عشوائيًا مفتاحًا خاصًا 𝑏 ويبث علنًا مفتاحه العام $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$. ثم تأخذ أليس المفتاح العام لبوب وترفعه إلى قوة مفتاحها الخاص، وبالتالي تحسب القيمة $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. وبنفس الطريقة يحسب بوب القيمة $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. في نهاية العملية، تمكن أليس وبوب من الاتفاق على قيمة مشتركة 𝐾، دون نقلها بينهما.
لا يمكن للمهاجم الذي يستمع إليهما إيجاد 𝐾 بالنظر إلى القيم المبثوثة 𝑝، 𝑔، 𝐴، 𝐵. للقيام بذلك، سيتعين عليه إيجاد المفتاح الخاص لأليس أو بوب. لحساب المفتاح الخاص لأليس على سبيل المثال، سيتعين عليه إيجاد 𝑎 بالنظر إلى 𝑔 و $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$، وهي مشكلة صعبة. تُسمى هذه المشكلة مشكلة اللوغاريتم المتقطع (Discrete Logarithm Problem - DLP).
هناك تشابه واضح جدًا بين DH، الذي يعتمد على DLP، وECDH، الذي يعتمد على ECDLP (هما في الأساس نفس الشيء، مع اختلاف بادئة EC فقط). في كلا البروتوكولين، يمكن لطرفين يتواصلان مع بعضهما الاتفاق على قيمة سرية مشتركة، دون تنسيق أي شيء مسبقًا. أي شخص يستمع إلى الرسائل بين الطرفين سيكون مطلعًا على المعلومات العامة التي يتبادلانها، لكنه لن يتمكن من الوصول إلى القيمة السرية المشتركة بينهما.### الاستخدام الثاني للمنحنيات الإهليلجية - توقيع رسالة لمواصلة قصتنا، لنفترض أن أليس وبوب خرجا في موعد وقضيا أمسية جميلة معًا. في اليوم التالي تتلقى أليس رسالة نصها "مرحبًا أليس، أنا بوب، لقد قضيت وقتًا رائعًا معك أمس وأود مقابلتك مرة أخرى في نهاية هذا الأسبوع". تشك أليس في أن بوب لم يرسل الرسالة، لأنها تعرف أن بوب استمتع كثيرًا معها أمس، لدرجة أنه لن ينتظر حتى نهاية الأسبوع لمقابلتها، بل سيريد مقابلتها غدًا! كيف يمكن لأليس التحقق من أن بوب هو من كتب الرسالة؟
إذا كانت إجابتك "المنحنيات الإهليلجية"، فأنت على حق مرة أخرى!
يمكن أيضًا استخدام صعوبة مسألة ECDLP لتوقيع الرسائل. خلال موعدهما، اتفقت أليس وبوب على منحنى إهليلجي معين ومولّد 𝐺 فيه. ولّد بوب قيمة $𝑑_𝐵$ تسمى المفتاح الخاص لبوب، وحسب النقطة $𝑃_𝐵 = 𝑑_𝐵𝐺$ تسمى المفتاح العام لبوب. أعطى بوب لأليس مفتاحه العام لتتمكن من استخدامه لاحقًا للتحقق مما إذا كانت الرسالة التي تستلمها موقعة منه بالفعل.
لنفترض أن بوب يريد توقيع رسالة معينة 𝑚. سيحسب القيمة $z = hash(m)$ باستخدام دالة تجزئة آمنة، ويحتفظ بعدد من البتات من النتيجة يساوي طول البتات لـ n، وهو رتبة المولّد 𝐺. سيولّد بوب قيمة عشوائية 𝑘 في المدى $1 ≤ 𝑘 ≤ 𝑛 − 1$. ثم سيحسب النقطة $𝑘𝐺 = (𝑥_1, 𝑦_1)$، ويأخذ الإحداثي 𝑥 لها، ويحسب $𝑟 = 𝑥1\ \ \ \ (mod\ n)$. أخيرًا، سيحسب بوب القيمة $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$.
تُعرَّف توقيع الرسالة 𝑚 على أنه زوج القيم المحسوبة 𝑟 و 𝑠.
لنفترض أن أليس استلمت رسالة معينة 𝑚، وتوقيعها يتكون من زوج من القيم 𝑟 و 𝑠. تريد أليس التأكد من أن بوب هو بالفعل من وقّع الرسالة. ستحسب أليس القيمة $z = hash(m)$ بنفس الطريقة التي اتبعها بوب. ثم ستحسب أليس القيمتين $𝑢_1 = 𝑧𝑠^{−1}$ و $𝑢_2 = 𝑟𝑠^{−1}$. أخيرًا، ستستخدم أليس المفتاح العام لبوب $𝑃_𝐵$، وتحسب النقطة $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$. سيُعتبر التوقيع صالحًا إذا تحقق أن $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$. سبب صحة ذلك هو أن:
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
إذا كان التوقيع صالحًا، فيجب أن يكون الإحداثي 𝑥 لهذه النقطة هو 𝑟 كما هو معرّف في توقيع الرسالة. وتجدر الإشارة إلى أن رتبة المولّد 𝐺، التي يُرمز إليها بالحرف 𝑛، يجب أن تكون عددًا أوليًا، وذلك ليكون من الممكن بالفعل حساب القيم العكسية في خوارزميتي التوقيع والتحقق.
يمكن ملاحظة أن الشخص الوحيد الذي يملك المفتاح الخاص $𝑑_𝐵$ يمكنه إنشاء توقيع صالح للمفتاح العام $𝑃_𝐵$. فالمهاجم الذي لا يملك القيمة $𝑑_𝐵$ لا يمكنه حساب القيمة 𝑠 المقابلة لـ $𝑃_𝐵$ في التوقيع. إذا أراد المهاجم إنشاء توقيع يطابق رسالة معينة، فسيتعين عليه حل مسألة ECDLP، أي إيجاد المفتاح الخاص $𝑑_𝐵$ بمعلومية $𝐺$ و $𝑃_𝐵 = 𝑑_𝐵𝐺$، وهي مسألة صعبة.
يُسمى بروتوكول التوقيع هذا خوارزمية التوقيع الرقمي بالمنحنيات الإهليلجية، أو اختصارًا ECDSA. يضمن البروتوكول أن الرسائل الموقعة لم يتم تغييرها أو تزويرها، ويضمن أيضًا أن الشخص الذي وقّع الرسالة لا يمكنه إنكار أنه هو من أنشأها.
على عكس بروتوكول ECDH، حيث لم يتعين على الأطراف تنسيق أي شيء مسبقًا، في بروتوكول ECDSA يجب على الأطراف الاتفاق مسبقًا على مفتاح عام. فقط بعد أن يتأكد كل طرف من أن المفتاح العام الذي بحوزته ينتمي بالفعل إلى الشخص الذي يريد التواصل معه، يمكن استخدام البروتوكول. وإلا، فلا معنى للتحقق من التوقيع باستخدام المفتاح العام الذي يملكه كل طرف.
نعود إلى قصتنا. أليس متأكدة تمامًا من أن المفتاح العام $𝑃_𝐵$ الذي بحوزتها يعود بالفعل إلى بوب، لأن بوب أعطاها إياه صراحةً خلال موعدهما. تحاول أليس التحقق من الرسالة به فتكشف عدم تطابق. بالطبع! شخص آخر أنشأ الرسالة ووقّعها، تمامًا كما شكّت أليس.
فيما يلي رسم توضيحي للبروتوكول:
في بروتوكول ElGamal لتوقيع الرسائل، يتفق الطرفان على عدد أولي كبير 𝑝 وعدد مولّد 𝑔. يولّد الطرف الموقّع قيمة 𝑑 في المدى $1 ≤ 𝑑 < 𝑝 − 1$، تسمى المفتاح الخاص، ويحسب القيمة $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$، تسمى المفتاح العام، وينشرها.
لتوقيع رسالة معينة، يحسبون القيمة $z = hash(m)$ ويولّدون قيمة عشوائية 𝑘 في المدى $1 ≤ 𝑘 < 𝑝 − 1$ بحيث تكون أولية نسبيًا مع $(p-1)$. يحسبون $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ و $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$. يُعرَّف توقيع الرسالة m على أنه زوج القيم المحسوبة 𝑟 و 𝑠.
الطرف الذي استلم رسالة معينة 𝑚، وتوقيعها يتكون من زوج من القيم 𝑟 و 𝑠، يستخدم المفتاح العام 𝑦 للتحقق من التوقيع بحساب القيمتين $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ و $𝑢_2 = 𝑔^𝑧$. سيُعتبر التوقيع صالحًا إذا كان $𝑢_1 = 𝑢_2$. وذلك لأنه وفقًا لتعريف 𝑠 فإنه يرمز إلى:
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$، وبالتالي $𝑘𝑠 = 𝑧 − 𝑑𝑟$، ومنه $𝑧 = 𝑘𝑠 + 𝑑𝑟$. لذلك:
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
لا يمكن للمهاجم إنشاء توقيع صالح للمفتاح العام 𝑦 دون معرفة المفتاح الخاص 𝑑. للحصول على المفتاح الخاص بمعلومية المفتاح العام، سيتعين على المهاجم حل مسألة DLP، وهي مسألة صعبة.
هنا أيضًا يوجد تشابه واضح بين ECDSA، التي تعتمد على ECDLP، وElGamal، التي تعتمد على DLP. في كلتا الحالتين، يتعين على الأطراف تنسيق مفتاح عام مسبقًا، ومن المطلوب توليد قيمة عشوائية 𝑘 في كل مرة نريد فيها توقيع رسالة جديدة. أيضًا، في كلتا الحالتين، لا يمكن لمهاجم يستمع إلى الرسائل المتبادلة بين الأطراف استنتاج معلومات مفيدة تسمح له بتزوير التوقيعات.
رأينا كيف يمكن استخدام المنحنيات الإهليلجية في الأنظمة التشفيرية للاتفاق على قيمة سرية وتوقيع الرسائل. وكما هو الحال مع كل شيء في الحياة، عندما يتعلق الأمر بوضع شيء موضع التنفيذ، لا تسير الأمور دائمًا كما هو مخطط لها. في بقية المقال سأعرض طرقًا مختلفة لمهاجمة الأنظمة التشفيرية القائمة على ECC والتي أساء المستخدم استخدامها، أو نُفِّذت بطريقة غير آمنة.
بطبيعة الحال، قسّمت هذا الجزء إلى هجمات على ECDH وهجمات على ECDSA. في كلتا الحالتين سنقول إننا "نجحنا" في الهجوم إذا وجدنا المفتاح الخاص لأحد الأطراف، وسنتوقف عند ذلك. في حالة ECDH، يكفي ذلك لأنه من المفتاح الخاص يمكن الوصول إلى القيمة السرية المشتركة وكل المعلومات التي شُفِّرت بها لاحقًا. في حالة ECDSA، يكفي ذلك لأن المفتاح الخاص يمكن استخدامه لتوقيع الرسائل كيفما نشاء.
SageMath هو برنامج رياضي مجاني ومفتوح المصدر. يمكن كتابة الكود به بنفس قواعد لغة Python تقريبًا، ويمكن أيضًا استخدامه كمكتبة لغة Python. تنفّذ هذه المكتبة دوالًا مفيدة ذات صلة بالمنحنيات الإهليلجية، وهي لذلك مفيدة جدًا للحسابات التي نحتاج إلى إجرائها في سياق ECC. كجزء من هذا المقال، أقدّم مقاطع أكواد مكتوبة بهذه المكتبة. وجدت أنه من الأسهل تثبيته على نظام التشغيل Ubuntu، وتحديدًا الإصدار 22.04. لتثبيته، ما عليك سوى تشغيل الأمر: sudo apt install sagemath.
لتشغيل ملف يحتوي على كود، احفظ الملف بامتداد .sage وشغّل الأمر: sage file.sage.
بالإضافة إلى ذلك، يمكن استخدام مترجم تفاعلي، على غرار مترجم Python، بتشغيل الأمر: sage. من الممكن أيضًا إنشاء ملفات .py يُستورد فيها مكتبة sage.all، وتشغيلها بالأمر python3 file.py. لاحظ أنه عند تشغيل ملف بالأمر sage، يُفسَّر الرمز ^ على أنه أس، بينما عند التشغيل بـ python3، يُفسَّر هذا الرمز على أنه xor.
في هذا المقال أستخدم أساسًا الدوال التالية في SageMath:
E.gens() - إيجاد المولّدات في المنحنى EG.order() - حساب رتبة المولّد Gn*G - ضرب المولّد G في العدد nn.factor() - تحليل العدد n إلى عوامله - تعيد الدالة قائمة بأزواج (𝑝, 𝑒) بحيث يكون 𝑝 عاملًا أوليًا، و 𝑒 هو أسه، أي عدد المرات التي يظهر فيها 𝑝 في تفكيك ncrt - حل نظام معادلات نظرية الباقي الصينيربما يكون الاستخدام الخاطئ لـ ECDH الأسهل هجومًا هو اختيار مولّد برتبة n صغيرة جدًا.
كما ذُكر، يمكن حل مسألة ECDLP بتعقيد $O(\sqrt{n})$. عندما تكون 𝑛 صغيرة جدًا، مثل 32 بت، يصبح حل هذه المسألة ممكنًا. توجد عدة خوارزميات تحل المسألة، بما فيها Baby-Step Giant-Step وPollard's Rho وPollard's Lambda. يمكن تشغيل هذه الخوارزميات كصندوق أسود بمساعدة SageMath، باستخدام دالة discrete_log:```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
في هذا المقتطف البرمجي نختار معاملات المنحنى عشوائيًا مع قيد أن يكون `𝑝` بطول 32 بت. يضمن لنا هذا القيد أن عدد النقاط على المنحنى هو $O(2^{32})$ وبالتالي فإن رتبة كل نقطة فيه هي على الأكثر $O(2^{32})$ أيضًا. بعد ذلك ننشئ المنحنى، ونختار مولّدًا ما فيه، ونولّد مفتاحًا خاصًا عشوائيًا، ونحسب المفتاح العام. أخيرًا، من المولّد والمفتاح العام، نحسب اللوغاريتم المتقطع للعثور على المفتاح الخاص، ونتحقق من أن المفتاح الذي تم العثور عليه صحيح بالفعل. يستغرق هذا الكود بضع ثوانٍ فقط كحد أقصى للعثور على المفتاح الخاص.
## ترتيب المولّد هو عدد أملس
كما ذُكر، تُعرَّف رتبة المولّد على أنها عدد النقاط في "الدائرة" التي تتشكل عندما نضيف نقطة المولّد إلى نفسها مرارًا وتكرارًا، ويُرمز إليها بـ `𝑛`. إذا كان `𝑛` عددًا مركبًا يمكن تحليله إلى عوامل أولية أصغر، فمن الممكن حل ECDLP بكفاءة. يُسمى هذا العدد بالعدد الأملس، ولأغراض هذه المقالة، هو عدد يمكن تحليله إلى عدد كافٍ من العوامل الأولية، كل منها صغير بما يكفي لكي يعمل هجومنا. التعريف الرسمي للعدد الأملس مختلف قليلًا ولا يهمنا.
بشكل بديهي، يتم ذلك عن طريق "مهاجمة" كل عامل من العوامل الأولية على حدة. بافتراض وجود نقطة مولّد `𝐺` تشكّل "دائرة" كبيرة جدًا، ونقطة ما `𝑃` في "الدائرة" بحيث `𝑃 = 𝑘𝐺`. يمكن تفكيك "الدائرة" الكبيرة إلى عدة "دوائر" صغيرة، حجم كل منها يساوي عاملًا أوليًا واحدًا من عوامل `𝑛`. في كل "دائرة" صغيرة يمكننا ربط `G` و`P` بنقاط مقابلة أخرى `G'` و`P'` تقع في "الدائرة" الصغيرة، وتحقق `𝑃′ = 𝑘′𝐺′`. ولأن "الدائرة" صغيرة، فمن السهل نسبيًا حل المسألة وإيجاد `𝑘′`. أخيرًا، يمكننا دمج كل قيم `𝑘′` الصغيرة التي وجدناها في القيمة المطلوبة `𝑘` في "الدائرة" الأصلية.
الخوارزمية التي تنفذ ما وصفته تُسمى خوارزمية بوليج-هيلمان. تعقيد وقت تشغيلها هو $O(\sqrt{p_{max}})$ حيث $p_{max}$ هو أكبر عامل أولي في تحليل `𝑛`. وهذا منطقي، لأن الجزء "الأثقل" في الخوارزمية هو حل مسألة ECDLP في أكبر "دائرة" بين "الدوائر" الأصغر. على سبيل المثال، قد يكون `n` عددًا بطول 128 بت، ويتحلل إلى عوامل أولية بحيث يكون أكبرها عددًا بطول 30 بت. تقلل الخوارزمية تعقيد حل المسألة من $2^{64}$ إلى $2^{15}$، محوّلةً إياه من غير الممكن إلى الممكن.
لحسن الحظ، تنفذ دالة `discrete_log` في SageMath هذه الخوارزمية في تطبيقها. لتشغيل الهجوم، يمكنك ببساطة استدعاء الدالة:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
في مقتطف الشيفرة هذا نعرّف منحنى إهليلجياً ومولّداً فيه، ونطبع العوامل الأولية لرتبته. الناتج هو:``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
يمكن ملاحظة أنه على الرغم من أن ترتيب المولد يبلغ طوله 128 بت، فإنه يتحلل إلى عوامل أولية بحيث يكون أكبر عامل أولي هو 32 بت.
بعد ذلك، تمامًا كما في الهجوم السابق - نختار مفتاحًا خاصًا عشوائيًا، ونحسب منه مفتاحًا عامًا، ثم بوجود المولد والمفتاح العام، نحسب المفتاح الخاص ونتحقق من صحته.
على الرغم من أننا انتهينا، لم نرَ كيف تُعرَّف الدوائر «الصغيرة»، وكيف نرسم النقطتين `𝐺` و`𝑃` إلى النقطتين المقابلتين `𝐺′` و`𝑃′`، وكيف نجمع كل الحلول الصغيرة في حل واحد كبير. سأحاول شرح ذلك بشكل حدسي هنا، لأن الهجوم التالي يعتمد على هذا الجزء أيضًا.
لنفترض أن لدينا «دائرة» من الترتيب `3𝑥5𝑥7 = 105`، ومولدها هو `𝐺`. سنعرّف نقطة `𝐺′ = (5𝑥7)𝐺 = 35𝐺`، وننظر إلى «الدائرة» المولَّدة منها. إذا تقدمنا من `𝐺′` «خطوة» واحدة، أي أضفنا `𝐺′` إلى نفسها، فسيكون الأمر وكأننا نتقدم 35 خطوة من النقطة `35𝐺` في «الدائرة» الأصلية، وسنصل إلى النقطة `2𝐺′ = 70𝐺`. إذا تقدمنا «خطوة» إضافية واحدة، سنصل إلى النقطة `3𝐺′ = 105𝐺 = 𝒪`، وإذا تقدمنا منها «خطوة» أخرى، سنصل إلى النقطة `4𝐺′ = 35𝐺 = 𝐺′`، أي نعود إلى نقطة البداية. «الدائرة» المكوَّنة من `G′` ترتيبها `3`، وهذا ليس مصادفة، لأنه على «دائرة» من الترتيب `105` يمكن أخذ `3` «خطوات» بالضبط بحجم `35`. وبالمثل، يمكننا إنشاء «دائرة» من الترتيب `5` بتعريف النقطة `𝐺′ = (3𝑥7)𝐺 = 21𝐺`، ودائرة من الترتيب `5` بتعريف `𝐺′ = (3𝑥5)𝐺 = 15𝐺`.
عندما ننظر إلى الأمر بالاتجاه المعاكس يصبح أكثر إثارة للاهتمام. لنفترض أننا في «الدائرة» الأصلية أخذنا `𝑛` خطوة من النقطة `G` ووصلنا إلى النقطة `𝑛𝐺`. إذا أخذنا أيضًا في «الدائرة» الصغيرة `𝑛` خطوة من النقطة `𝐺′`، فسنصل إلى النقطة `𝑛′𝐺′` بحيث `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`. ولماذا هذا مثير للاهتمام؟ لأن ترتيب `𝐺′` أصغر بكثير من ترتيب `𝐺`، وبالتالي بمعرفة `𝐺′` و`𝑛′𝐺′` يمكننا بسهولة نسبية إيجاد `𝑛′`. إذا فعلنا ذلك، وفعلناه أيضًا للعاملين الأوليين الآخرين لترتيب «الدائرة»، وهما `5` و`7`، فسنحصل على القيم التالية:
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
من هذه القيم الثلاث، يمكن إيجاد `𝑛` بسهولة باستخدام نظرية الباقي الصيني، وبالتالي حل المسألة الأصلية.
## ترتيب المولد هو عدد أملس تقريبًا، والمفتاح الخاص صغير
لنفترض أنه، على غرار الهجوم السابق، حصلنا على منحنى يتحلل فيه ترتيب المولد إلى عوامل أولية، لكن هذه المرة، يكون أكبر عامل أولي كبيرًا جدًا بحيث لا يكون من العملي حل مسألة ECDLP الخاصة به. على سبيل المثال، إذا كان ترتيب المولد `256 بت`، لكن أكبر عامل أولي هو `128 بت`. ستتطلب خوارزمية بوليج-هيلمان حوالي $O(2^{64})$ عملية لإيجاد المفتاح الخاص، وهو أمر غير ممكن عمليًا.
إذا علمنا أن المفتاح الخاص المستخدم صغير نسبيًا، فلا يزال من الممكن إيجاده بكفاءة.
لنفترض أن المفتاح الخاص هو `64 بت` (بدلاً من `256 بت`). عند إنشاء المفتاح العام، يُضرَب المولد في المفتاح الخاص فتحصل على نقطة ما في «الدائرة» التي ينشئها المولد. على الرغم من أن حجم «الدائرة» يبلغ حوالي $2^{256}$ نقطة، فإن هذه النقطة «ستقع» في مكان ما ضمن أول $2^{64}$ نقطة. لا يوجد أي «تفاعل» بين المفتاح الخاص والنقاط في «الدائرة» التي تقابل قيمًا أكبر.
من الممكن تشغيل خوارزمية بوليج-هيلمان، لكن مع «تجاهل» «الدوائر» الكبيرة جدًا، بشرط أن يكون حاصل ضرب ترتيبات «الدوائر» المتبقية على الأقل بطول المفتاح الخاص. إذا تم العثور على عدد كافٍ من العوامل الأولية الصغيرة، التي يكون حاصل ضربها على الأقل `64 بت`، فإن «الدوائر» المقابلة ستكون كافية لتنفيذ نفس الهجوم الذي رأيناه سابقًا.
إذا كانت حياتنا سهلة سابقًا من حيث كتابة الكود، فسيتعين علينا هذه المرة تنفيذ الأمور بأنفسنا، لأن دالة `discrete_log` في SageMath لا تعرف أننا نريد «تجاهل» بعض العوامل الأولية. مقتطف الكود التالي يقوم بذلك:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
في مقتطف الشيفرة هذا نعرّف منحنى إهليلجياً ومولّداً فيه، ونطبع العوامل الأولية لرتبته. الناتج هو:``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
ترتيب المولّد هو `256 bit`، ويتحلل إلى عدة عوامل أولية، بحيث يكون أكبر عاملين هما `77 bit` و `107 bit`. إنهما كبيران بما يكفي بحيث يكون حل ECDLP غير عملي. ثم يتم توليد مفتاح خاص بطول `64 bit` بشكل عشوائي، ويتم حساب مفتاح عام. في الخطوة التالية، نقوم "بتجميع" عدد كافٍ من العوامل الأولية حتى نحصل على ترتيب بطول لا يقل عن `64 bit`. الناتج هو:```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
يمكن ملاحظة أن العاملين الأكبر حجمًا زائدان عن الحاجة، وأكبر عامل يتبقى لدينا هو 40 bit. في الخطوة التالية، لكل عامل من العوامل المتبقية لدينا، نحسب النقطتين 𝐺′ و 𝑃′ كما شرحت سابقًا، ولكل واحدة منهما نحل مسألة ECDLP. تُحفظ النتائج والعوامل الأولية في القائمتين subsolutions و subgroups على التوالي. أخيرًا، تُدمج جميع النتائج باستخدام نظرية الباقي الصيني للحصول على المفتاح الخاص، ونتحقق من أنه صحيح بالفعل.
عند فحص تعريف جمع النقاط في المنحنيات الإهليلجية، نلاحظ خاصية مثيرة للاهتمام حيث إن جمع النقاط لا يستخدم القيمة 𝑏، بل فقط القيمتين 𝑎 و 𝑝. وهذا يعني أن جمع نقاط تقع على منحنى ما يمكن أن يكون ذا معنى أيضًا لمنحنى آخر لا يختلف عنه إلا في قيمة 𝑏 هذه. وينطبق هذا بالطبع أيضًا على ضرب نقطة في عدد. إذا لم يتحقق المستخدم من أن النقطة التي يستلمها من الطرف الآخر كمفتاح عام تقع فعلًا على منحناه، فإنه يعرّض نفسه لهجوم المنحنى غير الصالح (Invalid Curve Attack).
لنفترض أن طرفين اتفقا على منحنى إهليلجي ما $E_1$. يمكن للمهاجم إنشاء منحنى خبيث $𝐸_2$ له نفس قيم 𝑎 و 𝑝 الخاصة بـ $𝐸_1$ لكن بقيمة 𝑏 مختلفة. في المنحنى $𝐸_2$ سيختار المهاجم نقطة 𝑃 رتبتها صغيرة، مثلًا 3. بالطبع، لن تقع النقطة 𝑃 على $𝐸_1$، لأنها تحقق معادلة بقيمة 𝑏 مختلفة عن تلك الخاصة بـ $𝐸_1$. سيرسل المهاجم النقطة 𝑃 إلى المستخدم كمفتاح عام خاص به. لنفترض أن المستخدم لا يكلف نفسه عناء التحقق من أن النقطة التي يستلمها تقع فعلًا على المنحنى $𝐸_1$ الذي اتفق عليه الطرفان. سيأخذ المستخدم المفتاح العام الذي استلمه من المهاجم، ويضربه في مفتاحه الخاص، ويصل إلى نقطة ينبغي أن تكون نقطة السر المشترك كما رأينا في تعريف بروتوكول ECDH. من وجهة نظر المستخدم، سيحسب عملية الضرب على المنحنى $𝐸_1$. لكن لأن النقطة 𝑃 ليست عليه إطلاقًا، بل على $𝐸_2$، فإن المستخدم سيحسب في الواقع عملية الضرب على المنحنى $𝐸_2$. لاحقًا، سيستخدم المستخدم نقطة السر المشترك لمواصلة التواصل مع المهاجم. لنفترض أن الطرفين يستخدمان الإحداثي 𝑥 للنقطة كمفتاح تشفير AES. في هذه الحالة، سيشفر المستخدم رسالة ما ويرسلها إلى المهاجم.
بما أن رتبة 𝑃 هي 3، هناك فقط 3 احتمالات للنقطة المشتركة التي يمكن للمستخدم حسابها. سيجتاز المهاجم هذه النقاط الممكنة، ويعثر على أيّها يقابل المفتاح الذي يفك تشفير الرسالة المشفرة التي أرسلها المستخدم بنجاح. بمعرفة هذه النقطة والنقطة الابتدائية 𝑃، يمكن للمهاجم استنتاج باقي قسمة المفتاح الخاص للمستخدم على العدد 3. يمكن للمهاجم أن يرسل إلى المستخدم نقاطًا خبيثة إضافية 𝑃، برتب متزايدة، مثلًا 5، 7، وهكذا. وبهذه الطريقة يمكن للمهاجم جمع قيم كافية تمثل بواقي قسمة المفتاح الخاص للمستخدم على أعداد صغيرة. أخيرًا، يمكن للمهاجم استخدام نظرية الباقي الصيني لحساب المفتاح الخاص للمستخدم، بالطريقة نفسها التي رأيناها في الهجوم السابق.
إليك تفسيرًا أكثر بديهية: يمكن للمهاجم أن يزوّد المستخدم بنقطة على «دائرة» صغيرة جدًا، مثلًا طولها 2. سيتقدم المستخدم في هذه «الدائرة» أي عدد من الخطوات ويصل إلى نقطة الوجهة. يعرف المهاجم نقطة وجهة المستخدم، والتي يمكن أن تكون واحدة من 2 احتمال. لذلك يستطيع المهاجم أن يعرف ما إذا كان المستخدم قد قطع عددًا زوجيًا أم فرديًا من الخطوات على الدائرة. يمكن للمهاجم أن يزوّد المستخدم بنقاط إضافية على «دوائر» بأطوال 3، 5، 7، وهكذا. إلى أن يمتلك المهاجم عددًا كافيًا من هذه العوامل، يحتوي كل منها على معلومات قليلة عن عدد الخطوات التي قطعها المستخدم. أخيرًا يمكن للمهاجم دمج كل هذه القيم في العدد الدقيق للخطوات التي قطعها المستخدم، وهو مفتاحه الخاص.
يُظهر الكود التالي الهجوم:```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
في مقطع الكود هذا، يتم اختيار منحنى ومولّد، ويقوم المستخدم بتوليد مفتاح خاص بشكل عشوائي ويستخدمه في جميع استخدامات بروتوكول ECDH. تبحث الدالة `find_curves_with_small_subgroup` عن أزواج من النقاط والرتب، بحيث تكون رتبة كل نقطة صغيرة نسبيًا، وتكون النقطة على منحنى يختلف عن المنحنى الأصلي فقط بقيمة `𝑏`. يولّد الكود مثل هذه الأزواج حتى يجد عددًا كافيًا منها. لكل زوج، يتم إرسال المفتاح العام إلى المستخدم واستلام رسالة مشفّرة منه.
يتم تنفيذ القوة الغاشمة على الرسالة المشفّرة من أجل إيجاد قيمة المفتاح الخاص للمستخدم، بمعامل الرتبة الحالية. يتم حفظ جميع هذه النتائج، وأخيرًا نستخدم نظرية الباقي الصيني لحساب المفتاح الخاص للمستخدم والتحقق من صحته. في هذه الحالة اتفق الطرفان على أن التواصل سيتم باستخدام AES، مع مفتاح تشفير هو الإحداثي `x` لنقطة السر المشتركة، وقيمة IV هي الإحداثي `𝑦` الخاص بها.
تعقيد الهجوم هو $𝑂(𝑛_{𝑚𝑎𝑥})$ حيث $𝑛_{𝑚𝑎𝑥}$ هي أكبر رتبة بين رتب النقاط الخبيثة. ويعود السبب في ذلك إلى أن الجزء "الأثقل" من الهجوم هو القوة الغاشمة على أكبر "دائرة" بين "الدوائر" الصغيرة، ولحسن حظ المهاجم، يمكنه التحكم في هذه القيمة بشكل شبه كامل. لذلك فإن هذا الهجوم فعّال نسبيًا من حيث التعقيد. وكما ذُكر، جذر المشكلة في هذه الحالة هو أن المستخدم لا يتحقق من أن النقطة التي استلمها تقع حتى على المنحنى الذي يعمل عليه. بالإضافة إلى ذلك، يستخدم المستخدم نفس المفتاح الخاص في كل استخدام جديد لـ ECDH، وهذا ليس آمنًا تمامًا.
## المنحنى الشاذ
من الخصائص المهمة التي يجب أن يمتلكها المنحنى الإهليلجي ليكون آمنًا تشفيريًا هو أن يكون غير شاذ. المنحنى غير الشاذ هو منحنى تكون فيه قيمة معيّنة تُسمى "مميّز" المنحنى غير صفرية. يتحقق ذلك عندما تحقق معاملاته `𝑎` و `𝑏` المتباينة:
$4a^3 + 27b^2 ≠ 0$
المنحنى الذي لا يحقق هذه المتباينة يحتوي على نقطة "إشكالية" تُسمى `singular point`. هناك نوعان من هذه النقاط: عقدة وشرافة. توجد نقطة العقدة على منحنى يحتوي نوعًا من الحلقة التي تتقاطع مع نفسها عند النقطة الشاذة، ويمكن تمرير مماسّين مختلفين للمنحنى عبر هذه النقطة.
نقطة الشرافة هي نقطة يكون فيها المنحنى "حادًا"، كما لو كان هناك خطان يخرجان منها، لكن يوجد مماس واحد فقط للمنحنى عند تلك النقطة.
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
في نقطة من نوع العقدة يوجد جذر مزدوج، لذا يمكن كتابة معادلة المنحنى على النحو التالي:
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
يمكن "إزاحة" المنحنى إلى اليسار عن طريق استبدال المتغير $x$ بالمتغير $(𝑥 + 𝑥_0)$ والوصول إلى الشكل:
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
إذن الآن النقطة الشاذة تقع عند أصل المحاور. يمكن استخدام القيمة العددية $t = (x_0-x_1)$ لإنشاء تعيين بين نقاط المنحنى والأعداد الصحيحة، بحيث تكون عملية الجمع بين النقاط على المنحنى مكافئة لعملية الضرب بين الأعداد. لكل نقطة `(𝑥, 𝑦)` سنطابق العدد
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$. على وجه الخصوص، لزوج من النقاط `𝐺` و `𝑄` بحيث `𝑄 = 𝑛𝐺`، يمكننا ربط العددين `𝑔` و `𝑞` بحيث $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$، وهذه مسألة DLP "طبيعية". لتوضيح هذه العملية، أضفت رابطًا لمثال بأعداد صغيرة في المراجع في نهاية المقال. في التعيين الذي قمنا به، استخدمنا معادلتي الخطين المستقيمين $y+\sqrt{t}x$ و $y-\sqrt{t}x$، وهما الخطان اللذان يقابلان المماسّين اللذين يمكن رسمهما عند النقطة الشاذة (بعد أن "أزحنا" المنحنى)، وهذا هو السبب الأساسي في إمكانية استخدام هذا الهجوم.
يمكن حل مسألة DLP كهذه بكفاءة بمساعدة خوارزمية Pohlig-Hellman، التي رأيناها من قبل، لأنها يمكن استخدامها أيضًا على الأعداد الصحيحة بدلًا من النقاط على المنحنى. في سياق النقاط، رأينا أن الخوارزمية تكون مفيدة عندما تكون رتبة المولّد عددًا أملس. على عكس "دائرة" النقاط على المنحنى، التي قد تكون لها أي رتبة، في حقل الأعداد الصحيحة بمعامل عدد أولي `𝑝` تكون الرتبة `𝑝 − 1`. إذا كان `𝑝 − 1` عددًا أملس، فإن الخوارزمية ستحل مسألة DLP بكفاءة، وبالتالي تجد المفتاح الخاص `n`.
مقطع الكود التالي يقوم بذلك:```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
في مقتطف الشيفرة هذا، نعرّف معاملات منحنى إهليلجي، ونتحقق من أنه منحنى شاذ فعلًا. نجد جذور كثيرة الحدود المقابلة للمنحنى، ونحدد أيًّا منها هو الجذر المزدوج. نستخدم الجذر المزدوج "لتحريك" المنحنى، ونصل إلى النقطتين المُزاحتين 𝐺 و𝑄. ثم نحسب $\sqrt{t}$ من الجذور التي وجدناها ونستخدمه لربط النقطتين 𝐺 و𝑄 بالعددين 𝑔 و𝑞. نطبع تحليل 𝑝 − 1 إلى عوامله الأولية (للتحقق من أن مسألة اللوغاريتم المتقطع DLP يمكن حلّها بكفاءة فعلًا). أخيرًا، نحسب DLP ونفسّر النتيجة كسلسلة نصية.
المخرجات هي: ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
هذه المرة أخفيت رسالة في المفتاح الخاص نفسه. وتجدر الإشارة إلى أنه نظرًا لأنه منحنى مفرد، فليس من الممكن في SageMath إنشاؤه بالطريقة العادية، أو تعريف نقاط عليه، أو إجراء العمليات عليها كما فعلنا سابقًا. في هذا الكود عرّفت إحداثيات النقاط كمتغيرات ثابتة. ولحساب النقطة `𝑄`، قمت بضرب المفتاح الخاص في المولّد بنفسي باستخدام تطبيقي الخاص لخوارزمية Double And Add.
## المنحنى فائق التفرد
إذا كان لدينا منحنى إهليلجي modulo `𝑝`، ومولّدًا ترتيبه `𝑛`، فإن درجة التضمين (Embedding Degree) للمنحنى بالنسبة إلى المولّد تُعرَّف على أنها أصغر عدد `k` يحقق المعادلة $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$. مع تحويلات معيّنة، يمكن اختزال مسألة ECDLP إلى مسألة DLP في حقل من الرتبة $𝑝^𝑘$. عادةً ما تكون القيمة `𝑘` كبيرة جدًا (بنفس حجم `𝑝` تقريبًا)، لكن عندما تكون صغيرة نسبيًا (على سبيل المثال، أصغر من `6`)، يُسمى المنحنى `supersingular` ويصبح من الممكن حل مسألة DLP بكفاءة. يُسمى هذا الهجوم هجوم MOV، نسبةً إلى مخترعيه الثلاثة (Menezes-Okamoto-Vanstone).
التحويلات التي ذكرتها هي دوال تستقبل نقطتين، وتُرجِع عددًا ما في حقل الأعداد المركّبة. من بين التحويلات التي يمكن استخدامها: Weil Pairing أو Tate Pairing، وسنستخدمها كصندوق أسود. هذا التحويل `𝑇` يحقق الخاصية التالية لكل زوج من النقاط `𝑃`, `𝑄`:
$T(mP, nQ)=T(P,Q)^{mn}$
لذلك، إذا كان لدينا نقطتان `𝐺` و`𝑄 = 𝑚𝐺`، يمكننا اختيار نقطة ثالثة `𝑅` عشوائيًا وحساب القيمتين: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
من هنا يمكننا حل مسألة DLP لكلٍّ من `𝑔` و`𝑞` في حقل من الرتبة $p^k$، وبالتالي إيجاد المفتاح الخاص `𝑚`. لقد أدرجت رابطًا لشرحٍ أكثر تفصيلًا للرياضيات وراء هذا الهجوم، في المراجع في نهاية المقال.
مقتطف الكود التالي ينفّذ هذا الهجوم:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
في هذا المقتطف البرمجي نعرّف منحنى ومولّده، ونحسب قيمة درجة التضمين الخاصة به، والتي هي 2 في هذه الحالة، ولذلك يكون تنفيذ الهجوم عمليًا. نعرّف منحنى مطابقًا للمنحنى الأصلي، باستثناء أن العمليات الحسابية تتم باستخدام modulo $𝑝^𝑘$ بدلاً من modulo $𝑝$. النقطتان 𝐺 و 𝑄 تقعان أيضًا على المنحنى الجديد. ثم نجد نقطة ثالثة ترتيبها يقسّم 𝑛.
باستخدام النقطة الثالثة، نقوم بتعيين النقطتين 𝐺 و 𝑄 إلى العددين 𝑔 و 𝑞 ونحسب اللوغاريتم المتقطع لهما. أخيرًا، نتحقق من أن النتيجة التي تم الحصول عليها صحيحة بالفعل.
الإخراج هو:``` Found k: 2 Calculating private key... success! The private key is: Festivus
من وجهة نظر حسابية، توجد اليوم خوارزميات Index Calculus يمكنها حل مسألة DLP بطريقة فعّالة نسبيًا، وهي تفعل ذلك بتعقيد مقداره $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$. قد يبدو هذا التعبير مخيفًا، لكنه بالمقارنة مع خوارزميات ECDLP التي يكون تعقيدها $O(\sqrt{p})=e^{O(log\ p)}$، يمكن ملاحظة أن حل مسألة DLP أسهل، بافتراض أن درجة التضمين (المُشار إليها بـ `𝑘`) صغيرة فعلًا.
## المنحنى الشاذ
إذا كان منحنى معيّن يمتلك خاصية أن رتبة المنحنى (عدد النقاط الواقعة عليه) تساوي تمامًا المعامل `𝑝`، فإنه يُسمى `Anomalous Curve` ويكون عرضة لهجوم يُعرف باسم هجوم سمارت. يستخدم هذا الهجوم `𝑝-adic numbers`. يمكن تمثيل مثل هذا العدد كمجموع قوى للعدد `p` (الموجبة والسالبة) مع معاملات. رسميًا، مثل هذا العدد `s` هو متسلسلة من الشكل:
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
عندما تكون المعاملات أعدادًا صحيحة في المجال $0 ≤ 𝑎_𝑖 < 𝑝$، ويمكن أن يكون المجموع غير منتهٍ في اتجاه القوى الموجبة للعدد `𝑝`. في مثل هذه الأعداد، نحن "ننظر إلى" الأرقام من اليمين إلى اليسار بدلًا من اليسار إلى اليمين، وبالتالي يمكن لمثل هذه المتسلسلة أن تتقارب إلى قيمة ما. تنتمي هذه الأعداد إلى نظام عددي مختلف عن النظام المألوف لدينا، وتتصرف بشكل مختلف جدًا عن القواعد الرياضية "العادية". يمكن كتابة مقال منفصل كامل حول هذا الموضوع وحده، ولمن يهتم به، أدرجت في المراجع في نهاية المقال رابطًا لفيديو يعرضه بطريقة واضحة نسبيًا.
على أي حال، في هذا الهجوم، يتم إنشاء منحنى جديد من المنحنى المعطى، بحيث يكون معرّفًا فوق الأعداد p-ادية. بوجود نقطتين `𝐺` و`𝑄 = 𝑚𝐺` على المنحنى الأصلي، نقوم بتعيينهما إلى نقطتين مناظرتين على المنحنى الجديد. من إحداثيات النقطتين اللتين تم الحصول عليهما، يسهل حساب `𝑚`.
يقوم الكود التالي بتنفيذ الهجوم:```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
في مقطع البرمجة هذا، يتم تعريف دالة رفع (lift function) تأخذ نقطة على المنحنى الأصلي وتقابلها بنقطة على المنحنى الجديد. ثم نعرّف منحنى إهليلجيًا ومولّدًا فيه، ونتحقق من أن رتبة المنحنى هي فعلاً p. نختار مفتاحًا خاصًا ونحسب المفتاح العام المقابل، ثم ننفّذ الهجوم. نعرّف منحنى جديدًا فوق الأعداد p-ادية، ونرسم النقطتين الأصليتين 𝐺 و𝑃 إلى نقطتين مقابلتين في المنحنى الجديد باستخدام دالة الرفع وضربهما في 𝑝.
لكل نقطة جديدة، نحسب النسبة بين إحداثي 𝑥 وإحداثي 𝑦. خارج قسمة هاتين القيمتين هو حل ECDLP للنقطتين الأصليتين.
الناتج هو:``` success! The private key is: >>>>> Extraordinarily Nice <<<<<
سبب نجاح هذه الحسابات مرتبط بحقيقة أن عدد النقاط على المنحنى هو بالضبط `𝑝`. تتيح لنا هذه الخاصية تنفيذ عدة تحويلات، آخرها يحوّل النقاط على منحنى فوق الأعداد p-ادية إلى أعداد بمعامل $p^2$. لهذا التحويل خاصية أن النسبة بين زوج الأعداد المقابلة للنقطتين الأصليتين هي بالضبط ناتج لوغاريتم النقطتين. سنترك كل هذه التحويلات كصندوق أسود، لكن في نهاية المقال أضفت مراجع للتفسيرات الرياضية ذات الصلة.
# هجمات ECDSA
## عدم تجزئة الرسالة قبل توقيعها
رأينا أنه في عملية توقيع رسالة، تُحسب أولاً تجزئة الرسالة، وتُستخدم البتات العليا من التجزئة في حساب التوقيع. لنفترض أنه في بعض تطبيقات توقيع الرسائل والتحقق منها، يتم تخطي خطوة التجزئة هذه، وبدلاً من أخذ البتات العليا من التجزئة، تؤخذ البتات من الرسالة كما هي. في مثل هذا التطبيق، الجزء الوحيد من الرسالة الذي يؤثر على توقيعها هو بداية الرسالة. بمعنى آخر، إذا كانت لدينا رسالة وتوقيعها، يمكننا الاحتفاظ ببداية الرسالة وتغيير ما تبقى منها، وسيظل التوقيع صالحًا. إنه هجوم بسيط حقًا.
لنفترض، على سبيل المثال، أنك تكتب الرسالة التالية إلى مصرفك وتوقّعها دون تجزئتها:```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
سيتحقق البنك من هذه الرسالة بنجاح، وسينفذ الإجراء. بعض ... المهاجم ... يمكنه إنشاء الرسالة التالية:``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
واستخدم التوقيع الذي أنشأته للتو. سيكون التوقيع صالحًا أيضًا لهذه الرسالة، وسينفّذ البنك الإجراء. ليس جيدًا (حسنًا، يعتمد على من).
يوضح الكود التالي الهجوم:```python
from ecdsa import SigningKey, NIST256p
signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key
class MyHash:
def __init__(self, data):
self.data = data
def digest(self):
return self.data
# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)
# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
في مقتطف الشيفرة هذا، يتم استخدام المكتبة ecdsa مع منحنى معروف. نعرّف فئةً ينبغي أن تنفّذ دالة تجزئة، لكنها لا تفعل ذلك، وبدلاً من ذلك تُبقي الرسالة كما هي. لذلك عند توقيع رسالة، تُستخدم فقط البتات الأولى من الرسالة الأصلية بدلاً من بتات تجزئتها. ثم يتم توقيع الرسالة والتحقق منها بنجاح. بعد ذلك يتم إنشاء رسالة خبيثة، ويتحقق الكود من أن توقيع الرسالة الأصلية يطابق الرسالة الخبيثة أيضًا.
في مثل هذا السيناريو، قد لا نكون قد حصلنا على المفتاح الخاص لتوليد توقيعات جديدة خاصة بنا، لكن بوجود توقيع واحد، يمكننا توقيع أي عدد نريده من الرسائل، بشرط أن تبدأ جميعها بالبادئة نفسها.
k في توقيعات مختلفةكجزء من عملية توقيع الرسالة، يُطلب من المستخدم توليد قيمة 𝑘 عشوائيًا واستخدامها لتوقيع الرسالة. من المهم جدًا استخدام قيم 𝑘 مختلفة في توقيعات مختلفة. وإلا - إذا وُجدت رسالتان موقّعتان استخدم فيهما المستخدم نفس القيمة 𝑘 بدلاً من إعادة توليدها، يمكن لمهاجم حساب المفتاح الخاص للمستخدم.
كما ذُكر، أثناء توقيع الرسالة، يرسل المستخدم علنًا $r=x_1\ \ \ \ (mod\ p)$ و $s=k^{-1}(z+rd_A)$. بافتراض أن المستخدم وقّع رسالتين مختلفتين تقابلان $𝑧_1$ و $𝑧_2$، وأرسل علنًا زوجي القيم $𝑟, 𝑠_1$ و $𝑟, 𝑠_2$، أي أنه استخدم نفس القيمة 𝑘 في هذين التوقيعين. نلاحظ أن:
$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$
من هذا، يمكن للمهاجم إيجاد قيمة 𝑘 عن طريق حساب:
$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$
بعد أن يعثر المهاجم على 𝑘، يمكنه حساب المفتاح الخاص للمستخدم من أحد التوقيعين. لاحظ أن:
$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$
بالنظر إلى القيم 𝑟 و𝑠 و𝑧 الخاصة برسالة وتوقيعها، وقيمة 𝑘 التي وجدها المهاجم، يمكن للمهاجم حساب $d_A=r^{-1}(ks-z)$. من هذه النقطة، يمكن للمهاجم توقيع أي رسالة يريدها، نيابةً عن المستخدم الذي حصل على مفتاحه الخاص.
ينفّذ مقتطف الشيفرة التالي هذا الهجوم:```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random
curve = curve_256 generator = generator_256 n = generator.order()
secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())
signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
في هذا المقتطف البرمجي، تُستخدم مكتبة `ecdsa` مع منحنى معروف. نعرّف مفتاحًا خاصًا ونستخدمه لتوقيع رسالتين. قيمة `𝑘` تُولَّد عشوائيًا، لكنها تبقى نفسها للتوقيعين. بالنظر إلى الرسالتين وتوقيعيهما، ينفّذ الكود العملية الحسابية التي رأيناها لإيجاد `𝑘`. أخيرًا، نستخدم قيمة `𝑘` التي وجدناها لحساب المفتاح الخاص كما رأينا. الناتج هو:```
Success!
The secret is: Mistakes were made
It is interesting to note that this attack was actually used in 2010, when Sony insecurely implemented their signing mechanism on the PlayStation console software. Sony used a static value of 𝑘 for its signatures, which allowed attackers to obtain Sony's private key using the above calculation. This led to the ability to sign any code, and make PlayStation agree to run it. Later this ability was used to install pirated and unofficial games on the console.
k بطريقة غير آمنةإذا اختار المستخدم 𝑘 بطريقة غير عشوائية بما فيه الكفاية، فمن الممكن اكتشاف المفتاح الخاص. على سبيل المثال، إذا علم المهاجم أن 𝑘 يقع في نطاق صغير جدًا من القيم، أو كانت بعض بايتات 𝑘 معروفة للمهاجم، فمن الممكن عبر القوة العمياء البسيطة إيجاد المفتاح الخاص للمستخدم بمعرفة رسالة موقّعة واحدة. سيشغّل المهاجم الحساب الذي رأيناه في الهجوم السابق لقيم 𝑘 المختلفة، حتى يصل إلى القيمة الصحيحة ويستخرج منها المفتاح الخاص.
للتغلب على هذه المشكلة، يقوم المستخدمون أحيانًا بتوليد قيمة عشوائية، ثم حساب تجزئتها باستخدام دالة تجزئة ما، واستخدام النتيجة كقيمة 𝑘. قد تسبب هذه الطريقة مشاكل. لنفترض، على سبيل المثال، أن رتبة المولّد 𝑛 هي 256 bit، ودالة التجزئة المختارة هي SHA-1. ناتج هذه الدالة هو رقم بطول 160 bit. في الحسابات بمعامل 𝑛، من المعروف أن قيمة 𝑘 تحتوي على 96 صفرًا في البداية، مما يعني أن 𝑘 عدد صغير نسبيًا. في مثل هذه الحالة، يُقال إن قيم 𝑘 هي منحازة، وبمعرفة عدة رسائل موقّعة بنفس المفتاح الخاص، يمكن إيجاد المفتاح الخاص.
يعتمد الهجوم على بنية جبرية تُسمى Lattice. بشكل غير رسمي، يمكن تصوّر الشبكة (lattice) على أنها مجموعة من المتجهات في فضاء بُعدي 𝑚، يمكن التعبير عنها كتركيبة خطية من متجهات "الأساس" بمعاملات صحيحة. رياضيًا، إذا كانت $\{b_1,\dots,b_d\}$ هي متجهات الأساس على $ℝ^𝑚$، فإن الشبكة المقابلة لها هي $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$. في هذه البنية توجد مسألة معروفة: بمعرفة أساس الشبكة، أوجد أقصر متجه موجود في الشبكة. في هذا السياق، وبشكل غير رسمي، "المتجه القصير" هو متجه تكون عناصره أقرب ما يمكن إلى الصفر. تُسمى هذه المسألة مسألة أقصر متجه (Shortest Vector Problem - SVP)، وتُعتبر NP-hard. هناك خوارزميات تحل مسألة مشابهة لكنها أسهل - إيجاد متجه قصير ما، أي متجه "قريب" نسبيًا من أقصر متجه في الشبكة. تُسمى هذه المسألة مسألة أقرب متجه (Closest Vector Problem - CVP)، ومن الخوارزميات التي تحلها خوارزمية Lenstra-Lenstra-Lovász (LLL). في هذا الهجوم سنستخدم هذه الخوارزمية كصندوق أسود.
بمعرفة 𝑑 رسائل موقّعة، من الممكن بناء شبكة تحتوي على المتجه $(𝑘_1, \dots , 𝑘_𝑑)$، حيث كل عنصر من عناصر المتجه هو قيمة 𝑘 تقابل توقيعًا واحدًا. ستجد خوارزمية LLL تقريبًا لأقصر متجه في هذه الشبكة. وبما أنه من المعروف أن قيم 𝑘 صغيرة، فهناك احتمال كبير أن المتجه القصير الذي تجده الخوارزمية سيحتوي على الأقل على عنصر k صحيح واحد. وبمجرد إيجاد 𝑘 صحيح، يمكن حساب المفتاح الخاص كما رأينا في الهجوم السابق.
لبناء هذه الشبكة، يجب تعريف متجهات الأساس الخاصة بها. لقد أدرجت في المراجع في نهاية المقال رابطًا لمقال يشرح كيفية تعريف هذه المتجهات الأساسية. تقنيًا، يمكن تمثيل متجهات الأساس للشبكة كمصفوفة، بحيث يتكون كل صف فيها من عناصر متجه أساس واحد. لتحسين دقة خوارزمية LLL، يُنصح بإضافة عمودين إلى هذه المصفوفة يحتويان على معلومات حول الحجم المتوقع لقيم 𝑘 والنسبة بين 𝑘 و𝑛. هذا التحسين موضح أيضًا في المرجع الذي أرفقته. يوضح مقطع الشيفرة التالي هذا الهجوم:```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random
def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """
# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
row1.append((inverse_mod(s, q) * m) % q)
row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])
# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])
# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M
def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d
curve = curve_256 generator = generator_256 q = int(generator_256.order())
secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]
signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))
bias = 2^160 M = build_matrix(signatures, bias, q)
L = M.LLL()
found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
في مقتطف الكود هذا، يُستخدم منحنى قياسي، ويُختار مفتاح خاص، ويُحسب المفتاح العمومي المقابل منه. يتم إنشاء 3 رسائل وتوقيعها باستخدام 3 قيم عشوائية `k` ناتجة عن دالة التجزئة SHA-1. ثم ننشئ المصفوفة المقابلة لأساس الشبكة كما هو موضح في المقال، ونطبّق خوارزمية LLL عليها. بعد ذلك، نمر على صفوف المصفوفة الناتجة ونتحقق مما إذا كانت القيمة الصحيحة لأي `𝑘` موجودة في أحدها. يتم التحقق عن طريق حساب المفتاح الخاص من القيمة المحتملة `𝑘`، كما رأينا في الهجوم السابق، والتحقق مما إذا كان المفتاح الذي تم الحصول عليه صحيحًا بالفعل. أخيرًا، نتأكد من أن المفتاح الخاص الذي تم العثور عليه صحيح بالفعل. الناتج هو:```
success!
The secret is: I am Jack's broken heart
إن تعقيد هذا الهجوم يعادل تعقيد خوارزمية LLL، والتي تساوي $O(d^6\ \log^3B)$، حيث يشير 𝐵 إلى طول انحياز 𝑘 ($2^{160}$ في حالتنا)، و𝑑 يشير إلى عدد الرسائل الموقَّعة (3 في حالتنا). يطرح السؤال: ما هو الحد الأدنى لعدد الرسائل الموقَّعة المطلوب استخدامه لكي نتمكن من تنفيذ الهجوم؟ الجواب على ذلك هو
$\displaystyle d=O(\frac {\log n}{\log n-\log B})$ حيث 𝑛 هو رتبة المولّد و𝐵 هو الانحياز. يوجد شرح لهذا في الرابط الثاني من المراجع التي أرفقتها بهذا الموضوع في نهاية المقال.
عمليًا، يمكن أيضًا تشغيل نسخة مختلفة من هذا الهجوم في الحالات التي تكون فيها البتات العليا من 𝑘 معروفة، أو حتى أي بتات من 𝑘. يمكن تشغيل الهجوم حتى لو كانت قيمة بت واحدة فقط معروفة، أو حتى لو كانت قيمة بت واحدة فقط معروفة باحتمال أكبر من 50%! لكن بالطبع، في هذه الحالات، يلزم عدد أكبر بكثير من الرسائل الموقَّعة لتنفيذ الهجوم.
لقد رأينا أنه في عملية التحقق من التوقيع، يرسل الطرف الموقِّع زوج القيم 𝑟 و𝑠 إلى الطرف المتحقِّق. في المتصفحات التي تنفّذ بروتوكول HTTPS، على سبيل المثال، من المعتاد إرسال زوج القيم هذا في شهادة، وقد تحتوي الشهادة أيضًا على بيانات حول المنحنى الذي استخدمه الطرف الموقِّع. يجب على الطرف المتحقِّق التأكد من أن بيانات المنحنى الموجودة في الشهادة تطابق المنحنى المتفق عليه مسبقًا. إذا لم تطابق، فقد يكون ذلك مشكلة.
لنفترض أنه في منحنى معيّن، تمتلك أليس مفتاحًا خاصًا $d_A$ ومفتاحًا عامًا $𝑃_𝐴$ يقابله، مما يعني أن $𝑃_𝐴 = 𝑑_𝐴𝐺$ بالنسبة للمولّد 𝐺 في هذا المنحنى. باستخدام المفتاح الخاص $𝑑_𝐴$، يمكن لأليس توقيع رسائلها كما رأينا في تعريف بروتوكول ECDSA. لنفترض أن الطرف الذي يتحقق من التوقيع يستلم أيضًا المولّد 𝐺 من المستخدم، ولا يتحقق من أن المولّد المستلَم من المستخدم هو بالفعل المولّد المتفق عليه. يمكن للمهاجم أن يرسل كمولّد النقطة التي تمثل المفتاح العام لأليس، $𝐺^′ = 𝑃_𝐴$. سيختار المهاجم كمفتاح خاص "مزوّر" القيمة $𝑑_𝐴^′ = 1$، وبالتالي من الواضح أن $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$. هذا يعني أن المهاجم يمكنه "إثبات" أنه يمتلك المفتاح الخاص المطابق للمفتاح العام لأليس. وبالتالي يمكن للمهاجم إنشاء أي رسالة يريدها، وحساب زوج القيم 𝑟 و𝑠 لها بالطريقة المعتادة باستخدام $𝑑_𝐴^′$، وسيتم التحقق من التوقيع الناتج بنجاح.
بشكل بديهي، في عملية التحقق من التوقيع، يثبت الطرف الموقِّع أنه بالفعل "مالك" المفتاح العام، والذي هو في الواقع نقطة "الوجهة" على المنحنى. وذلك لأن الموقِّع وحده يعرف عدد الخطوات التي يجب اتخاذها من نقطة البداية للوصول إلى نقطة الوجهة. إذا لم يتحقق الطرف المتحقِّق من أن نقطة البداية المستلَمة من المستخدم هي بالفعل نقطة البداية الحقيقية، فيمكن للمهاجم أن يقرر أن نقطة البداية هي نقطة الوجهة، وأن عدد الخطوات التي يجب اتخاذها منها هو صفر. تظل جميع الأجزاء الأخرى من التحقق من التوقيع كما هي، وسيتم التحقق من التوقيع بنجاح. يُسمى هذا الهجوم Curveball.
يمكن تعميم هذا الهجوم بقيم إضافية. سيختار المهاجم قيمة ما 𝑥، ويحسب $𝐺^′ = 𝑥𝑃_𝐴$. سيكون المفتاح الخاص المزوّر هو $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$. ومن الواضح عندها أن $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$.
يوضح الكود التالي الهجوم:```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random
def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())
def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r
def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)
r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s
G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G
message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)
x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G
evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)
في هذا المقطع البرمجي نختار مولّدًا معروفًا، ومفتاحًا خاصًا، ومفتاحًا عامًا. نوقّع رسالة ونتأكد من نجاح التحقق منها. ثم ننشئ مفتاحًا خاصًا مزيفًا ومولّدًا مزيفًا بحيث يطابق كلاهما المفتاح العام الأصلي. يتم توقيع رسالة خبيثة بالمفتاح المزيف، وأخيرًا يتم التحقق من التوقيع المزيف بنجاح باستخدام المفتاح العام الأصلي. المشكلة في هذا الكود هي أن خوارزمية التحقق لا تتحقق من أن المولّد `𝐺` يطابق المفتاح العام. على الرغم من أننا في هذا الهجوم لم نعثر على المفتاح الخاص للمستخدم، يمكن للمهاجم استغلال التنفيذ غير الصحيح للتحقق من التوقيع، وإنشاء توقيع يتم التحقق منه بنجاح. ومع ذلك، لا يمكن للمهاجم إنشاء توقيعات "حقيقية" سيتم التحقق منها بنجاح فعلًا في تنفيذ صحيح للتحقق من التوقيع.
من المثير للاهتمام ملاحظة أن هذه ثغرة حقيقية كانت موجودة في بنية Windows CryptoAPI. في الدالة المسؤولة عن التحقق من توقيع الشهادة، كان هناك تحقق غير كافٍ من معاملات المنحنى، في الحالات التي كانت فيها مضمنة في الشهادة نفسها. على وجه الخصوص، لم يكن هناك تحقق من أن المولّد هو بالفعل المولّد المطابق للمفتاح العام. يمكن للمهاجم إنشاء شهادات مزيفة تُعتبر موثوقة لأنها تبدو وكأنها موقعة من مرجع مصدّق موثوق (Certificate Authority). تم ذلك عن طريق إضافة حقول منحنى خبيثة إلى الشهادة، واختيار المولّد بالطريقة التي وصفتها. تم اكتشاف الثغرة من قبل وكالة الأمن القومي (NSA)، وتم إصلاحها في عام 2020 وحصلت على الرقم CVE-2020-0601.
# الخلاصة
## نظرة عامة على هجمات ECDH
| نوع المشكلة | المشكلة | الهجوم | كيف يعمل الهجوم | تعقيد الهجوم |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| اختيار منحنى بمولّد غير آمن | ترتيب المولّد `n` صغير جدًا | Baby-Step Giant-Step | Meet In The Middle | $𝑂(\sqrt n)$ |
| اختيار منحنى بمولّد غير آمن | ترتيب المولّد `n` عدد أملس | Pohlig-Hellman | تحليل `𝑛` إلى عوامله الأولية، ومهاجمة كل عامل على حدة، ثم دمج النتائج باستخدام نظرية الباقي الصيني | $O(\sqrt{p_{max}})$ حيث $p_{max}$ هو أكبر عامل أولي في تحليل `𝑛` |
| اختيار منحنى بمولّد غير آمن + اختيار مفتاح خاص غير آمن | ترتيب المولّد `n` يكاد يكون عددًا أملس، والمفتاح الخاص صغير | Improved Pohlig-Hellman | تحليل `𝑛` إلى عوامله الأولية، واستبعاد العوامل الكبيرة جدًا، ومهاجمة كل عامل على حدة، ثم دمج النتائج باستخدام نظرية الباقي الصيني | $O(\sqrt{p_{max}})$ حيث $p_{max}$ هو أكبر عامل أولي في تحليل `𝑛` |
| تنفيذ غير صحيح لـ ECDH | عدم التحقق من أن النقطة تقع على المنحنى | Invalid Curve Attack | إرسال نقاط ذات رتب صغيرة على منحنيات خبيثة كمفتاح عام، ومهاجمة كل واحدة على حدة، ثم دمج النتائج باستخدام نظرية الباقي الصيني | $𝑂(𝑛_{𝑚𝑎𝑥})$ حيث $𝑛_{𝑚𝑎𝑥}$ هو أكبر رتبة بين رتب النقاط الخبيثة |
| اختيار معاملات المنحنى بطريقة غير آمنة | المنحنى مفرد (Singular) | تقليل ECDLP إلى DLP | تعيين النقاط إلى أعداد بطريقة تحوّل جمع النقاط إلى ضرب الأعداد الصحيحة | $O(\sqrt{p_{max}})$ حيث $p_{max}$ هو أكبر عامل أولي في تحليل $(p-1)$ |
| اختيار معاملات المنحنى بطريقة غير آمنة | المنحنى فائق التفرد (Supersingular) | تقليل ECDLP إلى DLP | تعيين النقاط إلى أعداد بطريقة تحوّل جمع النقاط إلى ضرب الأعداد الصحيحة | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$ حيث `k` هي درجة التضمين (embedding degree) بالنسبة إلى المولّد |
| اختيار معاملات المنحنى بطريقة غير آمنة | المنحنى شاذ (Anomalous) | Smart's Attack | سلسلة من التعيينات بين نقاط على منحنى إلى نقاط على منحنى فوق أعداد `p-adic`، ثم العودة إلى الأعداد الصحيحة | $O(1)$ |
## نظرة عامة على هجمات ECDSA
| نوع المشكلة | المشكلة | الهجوم | كيف يعمل الهجوم | تعقيد الهجوم |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| تنفيذ غير صحيح للتوقيع والتحقق | عدم تجزئة الرسالة قبل توقيعها | بالنظر إلى رسالة موقعة، تزوير رسائل إضافية تطابق نفس التوقيع | إبقاء بادئة الرسالة كما هي وتعديل بقية أجزائها | $O(1)$ |
| استخدام غير صحيح لخوارزمية التوقيع | إعادة استخدام نفس قيمة `k` في توقيعات مختلفة | إيجاد المفتاح الخاص للمستخدم | إيجاد قيمة `k`، وحساب المفتاح الخاص للمستخدم منها | $O(1)$ |
| استخدام غير صحيح لخوارزمية التوقيع | توليد قيم `k` بطريقة غير آمنة | بالنظر إلى عدة رسائل موقعة، إيجاد المفتاح الخاص للمستخدم | تقليل المسألة إلى إيجاد متجه قصير في شبكة (lattice)، وإيجاد قيمة `k`، وحساب المفتاح الخاص للمستخدم منها | $O(d^6\ \log^3B)$ حيث `B` هو انحياز `k`، و `d` هو عدد الرسائل الموقعة |
| تنفيذ غير صحيح للتحقق | عدم التحقق من صحة المولّد | تزوير توقيعات يتم التحقق منها بنجاح (Curveball) | اختيار مولّد ومفتاح خاص مزيفين يطابقان المفتاح العام لمستخدم آخر | $O(1)$ |
## الحماية من هذه الهجمات
تجدر الإشارة إلى أنه في ECDH، يجب على الطرفين الاتفاق على المنحنى في بداية البروتوكول. إذا كان المستخدم يتواصل مع مهاجم، وكان المهاجم هو من يوفّر معاملات المنحنى، فيمكن للمهاجم توفير معاملات غير آمنة. ونتيجة لذلك، يمكن للمهاجم الحصول على المفتاح الخاص للمستخدم. إذا كان المستخدم يستخدم دائمًا نفس المفتاح الخاص، فسيتمكن المهاجم من فك تشفير جميع المحادثات بين ذلك المستخدم وأي مستخدم آخر. لهذا السبب من المهم جدًا عدم السماح لمستخدمين غير معروفين بتوفير معاملات المنحنى إذا لم يكونوا موثوقين. بالإضافة إلى ذلك، يجب التأكد من أن كل نقطة يتم استلامها من مستخدم خارجي تقع فعليًا على المنحنى المتفق عليه. وبالطبع، يجب التأكد من أن المنحنى المختار نفسه غير معرّض لإحدى الهجمات المعروفة التي رأيناها. أيضًا، من الأفضل استخدام مفتاح خاص جديد في كل مرة تستخدم فيها بروتوكول ECDH.
وبالمثل، في ECDSA، يجب توخي الحذر لتنفيذ خوارزميات التوقيع والتحقق بشكل صحيح. لا تتخطَّ تجزئة الرسالة، والتوليد العشوائي والآمن لقيمة `𝑘` في كل مرة يُستخدم فيها البروتوكول، وبالطبع في التحقق من التوقيع، إذا تم استلام المولّد من المستخدم - تأكد من أنه بالفعل نفس المولّد الذي تم الاتفاق عليه مسبقًا.
## المراجع
- في هذا المقال استخدمت رسومًا بيانية من كتاب Understanding Cryptography بقلم كريستوف
بار:\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf
- موقع يوضح كيف تبدو المنحنيات الإهليلجية التشفيرية:\
https://graui.de/code/elliptic2/
- شرح مفصل لعمليات الجمع والضرب في المنحنيات الإهليلجية:\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
- محاضرة عن مقدمة إلى المنحنيات الإهليلجية وجمع النقاط - بقلم كريستوف بار:\
https://www.youtube.com/watch?v=vnpZXJL6QCQ
- محاضرة عن المولّدات، ECDLP، صعوبة المسائل، ECDH، المضاعفة والإضافة (Double And Add) - بقلم كريستوف بار:\
https://www.youtube.com/watch?v=zTt4gvuQ6sY
- شرح لمستوى الأمان (Security Level) لخوارزميات التشفير المختلفة:\
https://en.wikipedia.org/wiki/Security_level
- شرح لـ ECDH:\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman
- شرح لـ ECDSA:\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
- شرح للتوقيعات باستخدام ElGamal:\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme
- شرح لنظرية الباقي الصيني:\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
- شرح للعلاقة بين مميّز المنحنى المفرد وحقيقة أنه يحتوي على جذر مزدوج:\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity
- مثال بأعداد صغيرة على التعيين بين النقاط والأعداد في المنحنيات المفردة:\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434
- شروحات للأعداد 𝑝-adic:\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA
- شرح للرياضيات وراء هجوم MOV:\
https://risencrypto.github.io/WeilMOV/
- شروحات للرياضيات وراء هجوم Smart (إنه معقد للغاية، لقد حُذِّرت):\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf
- شرح للهجوم القائم على الشبكات (lattice) وخوارزمية LLL:\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
يعتمد الهجوم على الجزء 4 في مقال بقلم Joachim Breitner و Nadia Heninger:\
https://eprint.iacr.org/2019/023.pdf
- شرح لمسألة CVP:\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)
- شرح لخوارزمية LLL:\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm