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)$
يبدو أنه لضرب نقطة في عدد 𝑛 نحتاج إلى تنفيذ 𝑛 عملية جمع بين النقاط. وذلك لأنه عند نقطة بداية معينة، من الصعب معرفة مسبقًا أين ستقع النقطة «الأخيرة»، دون الوصول إليها «خطوة بخطوة». مثل هذه الحسابات ستكون غير فعّالة جدًا، لأن 𝑛 قد يكون كبيرًا جدًا.
