الملاحق

\appendix

الحساب المعياريّ

الحساب المعياريّ (modular arithmetic) مستعمَل في كثير من أنظمة التشفير بالمفتاح العام، بما في ذلك خوارزميات public-key encryption مثل RSA، وبروتوكولات تبادل المفاتيح مثل ديفي-هيلمان (Diffie-Hellman).

الحساب المعياريّ شيءٌ يفهمه معظم الناس في الواقع أصلًا، إنّما هم لا يعلمون أنّ له هذا الاسم. يمكننا توضيح مبادئ الحساب المعياريّ باستعمال ساعة.

ساعةٌ تشير إلى الساعة الثانية.

ولأجل البساطة، تُظهر ساعتنا التجريبية ذات الاثنتي عشرة ساعة الساعات فقط، لا الدقائق ولا الثواني. وأيضًا، بخلاف الساعات الحقيقية، لا تكون مؤشّرات الساعات أبدًا في المنتصف بين ساعتين: فهي تُظهر دائمًا ساعةً كاملة، مثل 2 أو 9.

الجمع والطرح

من البديهيّ أن يكون جمع الساعات على ساعتنا منطقيًّا: إن كانت الساعة الآن الثانية، وأردتَ أن تعرف ما هي الساعة بعد خمس ساعات، يمكنك أن تجمع 5 فتصير 7، كما ترى في fig-Clock2Plus5.

2 + 5 = 7، على الساعة.

وبالمثل، يمكننا طرح الأوقات. إن كانت الساعة الآن العاشرة، وأردتَ أن تعرف ما كانت الساعة قبل ساعتين، فتطرح 2 فتصل إلى 8.

10 - 2 = 8، على الساعة.

الجزء «الغريب» هو حين تعبر الحدّ عند الساعة الثانية عشرة. فبالنظر إلى الساعة، لا فرق حقيقيًّا بين 12 و0. إن كانت الساعة الآن العاشرة، فستكون الساعة الثانية بعد أربع ساعات. وإن كانت الساعة الآن الثانية، فكانت الساعة التاسعة قبل خمس ساعات.

هذا مثال على ما يُسمّى «الحساب المعياريّ». والمقياس (modulus) في هذه الحالة هو 12. ويمكننا كتابة المعادلات أعلاه على الصورة الآتية:

$$(10 + 4) \bmod{12} = 2$$ $$(2 - 5) \bmod{12} = 9$$

في هذه المعادلات، يكون \bmod معاملًا يعطي الباقي بعد القسمة. وعندما نتعامل مع الحساب المعياريّ، حيث تتأثّر كلّ العمليات بالمقياس بدل عملية واحدة بسيطة، نكتب بدلًا من ذلك \negthickspace\pmod{12} في نهاية المعادلة ونستعمل علامة \equiv بدل علامة المساواة (=):

$$10 + 4 \equiv 2 \pmod{12}$$ $$2 - 5 \equiv 9 \pmod{12}$$

تُقرأ هذه «عشرة مضاف إليها أربعة تكافئ اثنين، بمقياس اثني عشر» و«اثنان ناقص خمسة يكافئ تسعة، بمقياس اثني عشر». قد يبدو هذا الآن حيلةً ترميزية تافهة، لكنّ الفرق سيصير واضحًا متى بدأنا في تطبيق حيلٍ لإجراء حسابات معيارية أعقد، مثل الضرب الأسّي.

بوجه عام، نُسمّي عددين متكافئين بمقياسٍ ما إذا كان قسمتهما على ذلك المقياس يترك الباقي نفسه. ويمكننا توضيح ذلك بأمثلتنا السابقة: 10 + 4 = 14 يترك الباقي 2 عند قسمته على 12، فهو إذن مكافئ لـ 2 بمقياس 12. أما الأعداد السالبة، فسنستعمل دائمًا البواقي الموجبة. فمثلًا، 2 - 5 \equiv 9 \pmod{12}. وهذه هي الطريقة التي تعمل بها الساعة أيضًا بالضبط: إن كانت الساعة الآن الثانية، فالساعة قبل خمس ساعات كانت «التاسعة»، لا «السابعة ناقص ثلاث».

الأعداد الأولية

الأعداد الأولية (prime numbers) أنواعٌ رائعة من الأعداد التي تعود فتظهر في كثير من فروع الرياضيات. وأي شيء أقوله عنها لن يُوفّيها حقّها على الأرجح؛ لكنّنا في كتابٍ عمليّ عن التشفير التطبيقي (applied cryptography)، لذا سنرى منها خصائص قليلة فقط.

العدد الأوليّ هو عددٌ لا يقبل القسمة إلّا على عددين: 1 ونفسه. فمثلًا، 3 عدد أوليّ، لكنّ 4 ليس كذلك، لأنّه يقبل القسمة على 2.

يمكن كتابة أي عدد بوصفه حاصل ضرب عوامل أولية: مجموعة من الأعداد الأولية مضروبة بعضها ببعض. ويُسمّى هذا الحاصل تحليلًا أوليًّا (prime factorization). فمثلًا، يمكن تحليل 30 إلى 2 و3 و5:

$$30 = 2 \cdot 3 \cdot 5$$

أحيانًا، يتكرّر عددٌ أوليّ أكثر من مرّة في التحليل. فمثلًا، يحتوي تحليل 360 على 2 ثلاث مرّات، وعلى 3 مرّتين:

$$360 = 2^3 \cdot 3^2 \cdot 5$$

تحليل أي عدد أوليّ ليس سوى ذلك العدد الأولّي نفسه.

لم تعد الرياضيات الحديثة تعتبر 1 عددًا أوليًّا، وإنّما كان يقبل القسمة على 1 وعلى نفسه (أي 1 مرّة أخرى). تحت هذا الاتفاق، فإنّ كل عدد يملك تحليلًا فحسب، بل ذلك التحليل فريد. ولولا ذلك، لأمكن تحليل 4 لا بوصفه 2 \cdot 2 فحسب، بل أيضًا 2 \cdot 2 \cdot 1، و2 \cdot 2 \cdot 1 \cdot 1، وهكذا. وتفيد فراديّة التحليل في بعض البراهين المهمّة في نظرية الأعداد.

وأيضًا، 0 ليس عددًا أوليًّا، لأنّه يقبل القسمة على أعداد كثيرة: جميع الأعداد ما عدا 0 نفسه.

يُسمّى عددان متباعدَين أوليًّا (coprime) عندما يكون القاسم المشترك الأكبر بينهما هو 1، أو بصيغة أخرى، عندما لا يتشاركان أي عامل أولّي. وبما أنّ العامل الأوليّ الوحيد للعدد الأوليّ هو نفسه، فإنّ هذا يعني أنّ جميع الأعداد الأولية متباعدة أوليًّا أيضًا. وبوجه عام، العدد الأوّليّ متباعد أوليًّا مع أي عدد ليس مضاعفًا له.

الضرب

قد تتذكّر أنّ الضرب قُدِّم لك أوّلًا بوصفه جمعًا متكرّرًا:

$$n \cdot x = \underbrace{x + x + \ldots + x}_{n \text{ times}}$$

الضرب المعياريّ لا يختلف عن ذلك. يمكنك حساب الضرب المعياريّ بجمع الأعداد بعضها ببعض، وأخذ المقياس كلّما صار المجموع أكبر من المقياس. ويمكنك أيضًا إجراء الضرب الاعتياديّ ثمّ أخذ المقياس في النهاية.

القسمة والمعكوسات المعيارية

تُعرَّف القسمة بأنها معكوس الضرب. فإذا كان a \cdot b \equiv c \pmod m، فإنّ \frac{c}{b} \equiv a \pmod m.

فمثلًا، 5 \cdot 6 \equiv 2 \pmod 7؛ إذن: \frac{2}{6} \equiv 5 \pmod 7. والسبب في ذلك أنّ 5 \cdot 6 = 30، وهو يترك الباقي 2 عند قسمته على 7.

عادةً، بدل استعمال القسمة مباشرةً، نستعمل الضرب بواسطة شيءٍ يُسمّى المعكوس المعياريّ (modular inverse). المعكوس المعياريّ لـ a هو عددٌ إذا ضربته في a حصلتَ على 1. وهذا مثل معكوس العدد في الحساب الاعتياديّ تمامًا: x \cdot \frac{1}{x} = 1.

كما في الحساب الاعتياديّ، ليست كل الأعداد تمتلك معكوسات معيارية. وهذا هو ما يماثل القسمة على الصفر في الحساب الاعتياديّ.

هناك خوارزميّتان تُستعملان لحساب المعكوسات المعيارية: خوارزمية أوكليد المُمتدّة (extended Euclidean algorithm)، وبمساعدة مبرهنة أويلر (Euler's theorem).

خوارزمية أوكليد المُمتدّة

خوارزمية أوكليد المُمتدّة هي توسيع لخوارزمية أوكليد (التي تعطينا طريقةً كفؤة لحساب القاسم المشترك الأكبر لعددين صحيحين). وإضافةً إلى ذلك، تساعدنا الخوارزمية المُمتدّة في التعبير عن قاسَمَي العددين الصحيحين على صورة مجموع خطّي للعددين الأصليّين:

GCD(x, y) = Px + Qy

بالنظر إلى العددين x وy، تعطينا خوارزمية أوكليد المُمتدّة طريقةً كفؤة لحساب قيمتي المعاملين P وQ.

ويمكن كذلك استعمال هذه الخوارزمية لحساب المعاكسات الضربّية بفضل خاصية معروفة، وهي أنّ معكوس العدد a \pmod n لا يمكن أن يوجد إلّا إذا كان gcd\ (a, n) = 1. لذا يمكننا استبدال x وy بـ a وn على التوالي في معادلة خوارزمية أوكليد المُمتدّة:

1 = Pa + Qn

وكتابة هذه المعادلة في \pmod n ستؤدي إلى إلغاء العامل Qn، لأنّ أيّ مضاعف لـ n متكافئ مع 0 \pmod n.

$$1 \equiv Pa \pmod n$$ $$a^{-1} \equiv P \pmod n$$

وهذا يثبت أنّ المعامل P \pmod n هو المعكوس الضربّي لـ a، ويمكننا استعمال خوارزمية أوكليد المُمتدّة لحساب قيمة المعامل P.

استعمال مبرهنة أويلر

تنصّ مبرهنة أويلر على أنّه إذا كان العددان a وn متباعدَين أوليًّا، فإنّ:

$$a^{\phi(n)} \equiv 1 \pmod n$$

في تلك المعادلة، \phi هي دالة أويلر الكلّية (Euler's totient function)، وهي تعدّ عدد الأعداد التي تتباعد أوليًّا مع مدخلها (وتكون أصغر منه أو مساوية له). فمثلًا، القيمة الكلّية لـ 10 هي 4، لأنّ 1 و3 و7 و9 لا تشترك مع 10 في عوامل أولية.

يمكننا استعمال مبرهنة أويلر لإيجاد المعكوس الضربّي لـ a. فإذا ضربنا طرفي المعادلة في a^{-1}، حصلتَ على:

$$a^{\phi(n) - 1} \equiv a^{-1} \pmod n$$

يعطينا ذلك صيغةً مباشرةً لحساب a^{-1}. وللأسف، فإنّ هذا يظلّ عمومًا أقلّ إثارةً من استعمال خوارزمية أوكليد المُمتدّة، لسببين:

#. تتطلّب حساب الدالة الكلّية، وهذا أصعب من تشغيل خوارزمية أوكليد المُمتدّة في أصل الأمر، ما لم تصادف أن تعرف العوامل الأولية لـ n. #. الأُسّ المعياريّ مكلفٌ حسابيًّا.

وهناك استثناءٌ واحدٌ لهذه القاعدة، وهو حين يكون المقياس عددًا أوليًّا. فبما أنّ العدد الأوليّ متباعد أوليًّا مع كل عدد آخر، وبما أنّ هناك p - 1 عددًا أصغر من p، فإنّ \phi(p) = p - 1. إذن، إذا كان المقياس عددًا أوليًّا، فإنّ المعكوس المعياريّ لـ a هو ببساطة:

$$a^{-1} \equiv a^{\phi(p) - 1} \equiv a^{p - 2} \pmod p$$

وهذا لا يزال يتطلّب مِنّا القدرة على رفع a إلى أُسّ بكفاءة باستعمال الحساب المعياريّ. وسنناقش في القسم التالي كيف يمكنك فعل ذلك بكفاءة.

الأُسّ

كما يُدرَّس الضرب بوصفه جمعًا متكرّرًا، يمكن التفكير في الأُسّ بوصفه ضربًا متكرّرًا:

$$a^n = \underbrace{a \cdot a \cdot \ldots \cdot a}_{n \text{ times}}$$

وكما في الضرب، من الممكن حساب الأُسّ المعياريّ بإجراء أُسّ اعتياديّ ثمّ أخذ المقياس في النهاية. لكنّ هذا غير كفؤٍ جدًّا، خاصّةً مع n كبير: إذ يصير الناتج سريعًا أكبر بكثير ممّا ينبغي.

ولحسن الحظّ، من الممكن حساب الأُسّ المعياريّ بكفاءة أكبر بكثير. ويُم ذلك بتقسيم المشكلة إلى مسائل فرعية أصغر. فمثلًا، بدل حساب 2^{20} مباشرةً، يمكنك تقسيمها:

2^{20} = (2^{10})^2

و2^{10} شيء يمكنك حسابه بأصابع يديك: ابدأ بالرقم 2، وهو 2^1، ثمّ واصل الضرب في اثنين. كلّما ضربت في اثنين، يزيد الأُسّ بمقدار 1، فحين تَعُدّ أصابعك كلّها (بافتراض أنّ لديك عشرة أصابع) تكون قد فرغت. والنتيجة هي 1024. إذن:

$$\begin{aligned} 2^{20} &\equiv (2^{10} \bmod {15})^2 \pmod {15} \\ &\equiv (1024 \bmod {15})^2 \pmod {15} \\ &\equiv 4^2 \pmod {15} \\ &\equiv 16 \pmod {15} \\ &\equiv 1 \pmod {15} \end{aligned}$$

الأُسّ بالتربيع

إحدى الطرق خاصةً الكفؤة لإجرائه على الحاسوب هي تقسيم الأُسّ إلى مجموع من قوى الاثنين. ويُسمّى هذا الأُسّ بالتربيع (exponentiation by squaring)، أو ما يُسمّى أيضًا الأُسّ الثنائيّ (binary exponentiation). لنفترض أنّنا نريد حساب 3^{209} \pmod {19}. أوّلًا، نقسّم 209 إلى مجموع من قوى الاثنين. وهذه العملية هي في جوهرها كتابة 209 بالنظام الثنائي: 0b11010001. وهذا عمليّ جدًّا إذا كان الحساب يُنفَّذ على حاسوب، لأنّ هذا هو الطريق المعتاد الذي يكون به الحاسوب قد خزّن العدد في الأصل.

$$\begin{array}{lllllllll} 209 &= 1 \cdot 2^{7} &+ 1 \cdot 2^{6} &+ 0 \cdot 2^{5} &+ 1 \cdot 2^{4} &+ 0 \cdot 2^{3} &+ 0 \cdot 2^{2} &+ 0 \cdot 2^{1} &+ 1 \cdot 2^{0} \\ &= 1 \cdot 128 &+ 1 \cdot 64 &+ 0 \cdot 32 &+ 1 \cdot 16 &+ 0 \cdot 8 &+ 0 \cdot 4 &+ 0 \cdot 2 &+ 1 \cdot 1 \\ &= 128 &+ 64 & &+ 16 & & & &+ 1 \end{array}$$

نستعمل هذا التوسيع إلى مجموع من قوى الاثنين لإعادة كتابة المعادلة:

$$\begin{aligned} 3^{209} &= 3^{128 + 64 + 16 + 1} \\ &= 3^{128} \cdot 3^{64} \cdot 3^{16} \cdot 3^1 \end{aligned}$$

الآن، علينا حساب تلك الأُسّات من 3 على الصورة: 1 و16 و64 و128. ومن الخصائص اللطيفة لهذه الخوارزميّة أنّنا لا نضطرّ فعليًّا إلى حساب الأُسّات الكبيرة كلّها من الصفر. يمكننا استعمال الأُسّات الأصغر المحسوبة سابقًا لحساب الأكبر منها. فمثلًا، نحتاج إلى 3^{128} \pmod {19} وإلى 3^{64} \pmod {19}، لكنّك تستطيع كتابة الأولى بدلالة الثانية:

$$3^{128} \bmod {19} = (3^{64} \bmod {19})^2 \pmod {19}$$

لنحسب كلّ أُسّات 3 التي نحتاجها. ولأجل الاختصار، لن نكتبها كاملةً، لكنّ تذكّر أنّ كلّ الحيل التي رأيناها سابقًا في حسابها لا تزال تنطبق:

$$\begin{aligned} 3^{16} &\equiv 17 \pmod {19} \\ 3^{64} &\equiv (3^{16})^4 \equiv 17^4 \equiv 16 \pmod {19} \\ 3^{128} &\equiv (3^{64})^2 \equiv 16^2 \equiv 9 \pmod {19} \end{aligned}$$

وإذا أعدنا هذه القيم إلى معادلتنا السابقة:

$$\begin{aligned} 3^{209} &= 3^{128} \cdot 3^{64} \cdot 3^{16} \cdot 3^1 \pmod {19} \\ &\equiv 9 \cdot 16 \cdot 17 \cdot 3 \pmod {19} \end{aligned}$$

تكون هذه الحيلة لافتةً للنظر على الخصوص حين يكون الأُسّ عددًا كبيرًا جدًّا. وهذا هو الحال في كثير من التطبيقات التشفيرية. فمثلًا، في فكّ تشفير RSA، يكون الأُسّ هو المفتاح السرّي d، وهو عادةً أطول من ألف بتّ. واحرص على أنّ هذا الأسلوب سيكشف معلومات عن التوقيت، فلا يصلح إلّا للحساب دون اتصال. ويمكن حساب الأُسّ المعياريّ أيضًا باستعمال تقنية تُسمّى سلّم مونتغومري، وسنراها في القسم التالي.

كثير من لغات البرمجة توفّر الوصول إلى دوالّ أُسّ معيارية محدّدة. فمثلًا، في Python، تُنفّذ pow(e, x, m) أُسًّا معياريًّا بكفاءة. لكنّ التعبير (e ** x) % m سيظلّ يستعمل الطريقة غير الكفؤة.

الأُسّ عبر سلّم مونتغومري

كما ذكرنا من قبل، خوارزمية الأُسّ بالتربيع بسيطة وسريعة، لكنّ الزمن الذي تستغرقه لإتمامها يعتمد على قيمة الأُسّ. وهذا أمر سيّئ، لأنّ الأُسّ عادةً قيمة سرّية، مثل سرّ ديفي-هيلمان أو الأُسّ الخاص d في RSA.

سلّم مونتغومري (Montgomery ladder) خوارزميّة تحلّ هذه المشكلة بضمان عدديّة العمليات نفسها مهما كانت القيمة المحيّنة للأُسّ. وقد طُبِّقت أوّلًا لإجراء ضربات سُلَّمية كفؤة فوق المنحنيات الإهليلجية، لكنّ الرياضيات تعمل في أنظمة كثيرة أخرى: تحديدًا في أي زمرة أبدية (abelian group). montgomerypowerladder

اشتقاق السلّم

متقدّم

يتضمّن هذا القسم قدرًا كبيرًا من الحيل الحسابية. ربّما أخرجتَ ورقةً وقلمًا لتتابع معي.

وكما في الأُسّ بالتربيع، نبدأ بالنظر في التوسّع الثنائي للأُسّ k. وبوجه عامّ، يمكن كتابة أي k على صورة مجموع (\sum) ببعض قوى الاثنين (2^i). فإذا ظهرت 2^j في التوسّع الثنائي، نقول إنّ k_j = 1؛ وإذا لم تظهر، نقول إنّ k_j = 0. وهذا يعطينا:

k = \sum_{i=0}^{t-1} 2^i k_i

قد يبدو هذا التعريف مخيفًا، لكنّ ما تفعله هنا في الحقيقة هو تعريف k_i بأنّه البتّ رقم i من k. والمجموع يمرّ على كلّ البتّات: فإذا كان k بطول t بتّ، وبدأنا الترقيم من 0، فإنّ فهرس أعلى بتّ هو t - 1، وفهرس أدنى بتّ هو 0. فمثلًا، التوسّع الثنائي للعدد 6 هو 0b110. وهذا العدد بطول ثلاثة بتّات، إذن t = 3. إذن:

$$\begin{aligned} 6 &= \sum_{i = 0}^{t - 1} 2^i k_i \\ &= \sum_{i = 0}^{2} 2^i k_i \\ &= k_2 \cdot 2^2 + k_1 \cdot 2^1 + k_0 \cdot 2^0 \\ &= 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0 \end{aligned}$$

إذن، (k_2, k_1, k_0) = (1, 1, 0).

الخطوات القليلة التالية لا تبدو ذات معنى كبير حتى تراها تجتمع في النهاية، فاصبر معي وتأكّد أنّ الرياضيات تصحّ. سنُعرّف مجموعًا ذا صلة، هو L_j:

L_j = \sum_{i = j}^{t - 1} 2^{i - j} k_i

فمثلًا، يصير L_1 (مع k = 6 بطبيعة الحال):

$$\begin{aligned} L_1 & = \sum_{i = 1}^{2} 2^{i - 1} k_i \\ & = \underbrace{2^1 \cdot k_2}_{i = 2} + \underbrace{2^0 \cdot k_1}_{i = 1} \\ & = 2 \cdot 1 + 1 \cdot 1 \\ & = 3 \end{aligned}$$

في جوهره، L_j ليس سوى k مُزاحًا إلى اليمين بمقدار j بتّ. والإزاحة إلى اليمين بمقدار بتّ واحد هي الشيء ذاته القسمة على اثنين مع أخذ الجزء الصحيح، تمامًا كما أنّ الإزاحة إلى اليمين برقم عشريّ واحد هي الشيء ذاته القسمة على 10 مع أخذ الجزء الصحيح. فمثلًا: العدد 73 مُزاحًا رقمًا عشريًّا واحدًا إلى اليمين يساوي 7؛ والعدد 0b101 (5) مُزاحًا خانة ثنائية واحدة (بتّ) إلى اليمين يساوي 0b10 (2). ومثلها، الإزاحة إلى اليسار هي العملية المعكوسة، وهي تعادل الضرب في اثنين.

بعد ذلك، سنُجري قليلًا من السحر الحسابي. أوّلًا كلّ شيء:

$$L_j = 2 \cdot L_{j + 1} + k_j$$

ورغم أنّه يمكن التحقّق من ذلك حسابيًّا، فإنّ أسهل طريقة للتحقّق هي التفكير فيه بدلالة الإزاحات إلى اليمين وإلى اليسار. فإن أزحتَ k إلى اليمين بمقدار j مواضع، فإنّ ذلك

$$\begin{aligned} k & = \mathtt{0b110010111} \\ L_j = L_2 & = \mathtt{0b1100101} \\ L_{j + 1} = L_3 & = \mathtt{0b110010} \\ 2 \cdot L_{j + 1} = 2 \cdot L_3 & = \mathtt{0b1100100} \end{aligned}$$

يمكنك أن تتحقّق بصريًّا أنّ L_2 هو حقًّا L_3 مُزاحًا واحدًا إلى اليسار (وهو الشيء ذاته الضرب في اثنين)، مضافًا إليه ذلك البتّ الواحد k_j الذي «سقط» عند الإزاحة إلى اليمين. وk_j هو البتّ الأخير من L_j؛ وفي هذه الحالة يصادف أنّه 1، لكنّه كان يمكن أن يكون 0 بكلّ بساطة.

نُعرّف دالةً أخرى بالغة البساطة، هي H_j:

H_j = L_j + 1 \iff L_j = H_j - 1

انطلاقًا من نتيجتنا السابقة:

$$\begin{aligned} L_j & = 2 \cdot L_{j + 1} + k_j \\ & \Downarrow (L_{j + 1} = H_{j+1} - 1) \\ L_j & = L_{j + 1} + k_j + H_{j + 1} - 1 \\ & \Downarrow (L_{j + 1} = H_{j+1} - 1) \\ L_j & = 2 \cdot H_{j + 1} + k_j - 2 \end{aligned}$$

ويمكننا الجمع بين هاتين المعادلتين لإنتاج طريقةٍ استقرائيّة لحساب L_j وH_j:

$$L_j = \begin{cases} 2 L_{j + 1} & \mbox{if } k_j = 0, \\ L_{j + 1} + H_{j + 1} & \mbox{if } k_j = 1. \end{cases}$$ $$H_j = \begin{cases} L_{j + 1} + H_{j + 1} & \mbox{if } k_j = 0, \\ 2 H_{j + 1} & \mbox{if } k_j = 1. \end{cases}$$

وتذكّر أننا نفعل هذا لحساب g^k. لنُخرج الأُسّ إلى النور:

$$g^{L_j} = \begin{cases} g^{2 L_{j + 1}} = \left(g^{L_{j + 1}}\right)^2 & \mbox{if } k_j = 0, \\ g^{L_{j + 1} + H_{j + 1}} = g^{L_{j + 1}} \cdot g^{H_{j+1}} & \mbox{if } k_j = 1. \end{cases}$$ $$g^{H_j} = \begin{cases} g^{L_{j + 1} + H_{j + 1}} = g^{L_{j + 1}} \cdot g^{H_{j+1}} & \mbox{if } k_j = 0, \\ g^{2 H_{j + 1}} = \left(g^{H_{j + 1}}\right)^2 & \mbox{if } k_j = 1. \end{cases}$$

وتذكّر أنّ L_j هو k مُزاحًا إلى اليمين بمقدار j بتّ، إذن L_0 هو k مُزاحًا إلى اليمين بصفر بتّ، أي k نفسه. وهذا يعني أنّ g^k، وهو العدد الذي نحاول حسابه، هو الشيء ذاته الذي هو g^{L_0}. فبالانطلاق من g^{L_{t - 1}} (g مرفوعة إلى أُسّ أقصى بتّ أيسر في k) ثمّ النزول تدريجيًّا حتى g^{L_0} = g^k، تتوفّر لدينا طريقةٌ استقرائيّة أنيقة لحساب g^k بناءً على قاعدتين تعاقبيّتين بسيطتين.

الجزء المهمّ في هذه الخوارزميّة هو ثبات عدد العمليات. فإن كان k_j = 0، فإنّ حساب g^{L_j} يتضمّن تربيعًا واحدًا، وحساب g^{H_j} يتضمّن ضربًا واحدًا؛ وإن كان k_j = 1، فإنّ الأمر بالعكس. ومهما كانت بتّات k، فإنّك تحتاج إلى عملية تربيع واحدة وعملية ضرب واحدة لكل بتّ.

تنفيذ سلّم مونتغومري في بايثون

تنفيذ سلّم مونتغومري في بايثون

تطبيق هذه الخوارزميّة في بايثون، على الأُسّ المعياريّ، هو أكثر إيجازًا ممّا يُتوقّع:

def montgomery(x, exponent, modulus):
    x1, x2 = x, x ** 2
    high_bit, *remaining_bits = bits(exponent)
    for bit in remaining_bits:
        if bit == 0:
            x2 = x1 * x2
            x1 = x1 ** 2
        else:
            x1 = x1 * x2
            x2 = x2 ** 2
        x1, x2 = x1 % modulus, x2 % modulus
    return x1

لا يُظهر مقطع الشيفرة هذا تعريف bits: فهو يُنتج التوسّع الثنائي لمَدخله. ولا يوفّر بايثون ذلك افتراضيًّا؛ فـ bin قريبة منه، لكنّها تُنتج سلسلة نصّية: فـ bin(100) تُقيَّم إلى 0b1100100. أمّا البنية a, *b = bits(...) فتسنِد العنصر الأول في bits(...) إلى a، وبقية البتّات كلّها إلى b، أي تُخطّي البتّ الأول ببساطة.

والأمر المهمّ الذي ينبغي ملاحظته هنا هو أنّه مهما كانت القيمة المحيّنة للأُسّ، فهناك تربيع واحد وضرب واحد وعملية باقٍ واحدة لكل بتّ. واحرص على ألّا يعني هذا بالضرورة أنّ الخوارزميّة كاملةً تستغرق زمنًا ثابتًا، لأنّ عمليتي التربيع والضرب الفرديّتين ليستا بالضرورة ذواتي زمن ثابت.

اللوغاريتم المتقطّع

تمامًا كما إنّ الطرح هو معكوس الجمع، والقسمة هي معكوس الضرب، فإنّ اللوغاريتمات هي معكوسات الأُسّ. وفي الحساب الاعتياديّ، إن كان b^x = y، فإنّ :math:x = \log_b y. وتُنطق هكذا: «b مرفوعة إلى أُسّ x تساوي y»، و«لوغاريتم y بالنسبة إلى b هو x». والمقابل لهذا في الحساب المعياريّ يُسمّى «لوغاريتمًا متقطّعًا» (discrete logarithm).

وكما في القسمة، فإنّك إذا انطلقتَ من التعريف بوصفه معكوس معامِل آخر، يسهُل عليك إيجاد أمثلة. فمثلًا، بما أنّ 3^6 \equiv 9 \pmod {15}، يمكننا تعريف 6 \equiv \log_3 9 \pmod {15}. وبخلاف المعكوسات المعيارية، فإنّ حساب اللوغاريتمات المتقطّعة صعب عمومًا. ولا يوجد برهان رسميّ على أنّ حسابها معقّد بطبيعته؛ إنّما لم نُعثر بعدُ على أيّ خوارزميات كفؤة لإجرائه. ولأنّ هذا المجال تلقى بحثًا واسعًا وما زلنا لا نملك خوارزميات عامّة سريعة جدًّا، فإنّنا نعدّ آمنًا أن نبني أمن البروتوكولات على افتراض أنّ حساب اللوغاريتمات المتقطّعة صعب.

هناك خوارزميّة نظريّة واحدة لحساب اللوغاريتمات المتقطّعة بكفاءة. لكنّها تتطلّب حاسوبًا كمّيًّا، وهو نوعٌ من الحواسيب مختلف جوهريًّا عن الحواسيب الكلاسيكية التي نستعملها اليوم. ورغم أنّه يمكننا بناء مثل هذه الحواسيب، فإنّنا لا نستطيع بناء إلّا حواسيب صغيرة جدًّا. والحجم المحدود لحواسيبنا الكمّية يحدّ بشدّة المسائل التي يمكننا حلّها. وإلى الآن، فإنّها أقرب بكثير إلى عالم الحسابات التي يستطيع الطفل إنجازها في رأسه، منها إلى إزاحة أفضل الحواسيب الكلاسيكية من عرش الصدارة في الأداء.

تعقيد حساب اللوغاريتمات المتقطّعة، مع بساطة نسبية في حساب معكوسها، أي الأُسّ المعياريّ، هو الأساس وراء كثير من أنظمة التشفير بالمفتاح العام. ومن الأمثلة الشائعة بناء التشفير RSA وبروتوكول تبادل المفاتيح ديفي-هيلمان.

ورغم أنّ أنظمة التشفير المبنيّة على مسألة اللوغاريتم المتقطّع تعدّ آمنة حاليًّا مع اختيار المعاملات المناسب، فبكلّ تأكيد هناك طرق يمكن أن يتغيّر ذلك في المستقبل. فمثلًا:

• الاختراقات النظريّة في نظرية الأعداد يمكن أن تجعل حساب اللوغاريتمات المتقطّعة أسهل بكثير ممّا نعتقده حاليًّا.
• الاختراقات التكنولوجية في الحوسبة الكمّية يمكن أن تؤدّي إلى حواسيب كمّية كبيرة بما يكفي.
• الاختراقات التكنولوجية في الحوسبة الكلاسيكية، فضلًا عن الزيادة التدريجيّة المستمرّة في الأداء والنقصان في الكلفة، يمكن أن تزيد حجم بعض المسائل التي يمكن معالجتها بالحواسيب الكلاسيكية.

وحساب اللوغاريتم المتقطّع يرتبط ارتباطًا وثيقًا بمسألة تحليل الأعداد. ولا تزال المسألتان مجالَين للبحث الرياضيّ النشط؛ ولا تزال الصلة بينهما غير مفهومة بدقّة. ومع ذلك، هناك أوجه تشابه كثيرة بين المسأنتين:

• يُعتقد أنّ كليهما صعب الحساب على الحواسيب الكلاسيكية، لكنّ ليس لأيٍّ منهما برهانٌ على ذلك.
• يمكن حساب كليهما بكفاءة على الحواسيب الكمّية باستعمال خوارزمية Shor.
• التقدّم الرياضيّ في إحداهما يتحوّل عادةً بسرعة إلى تقدّم رياضيّ في الأخرى.

الرتبة الضربّية

بالنظر إلى العدد الصحيح a والعدد الصحيح الموجب b بحيث gcd\ (a, b) = 1، فإنّ الرتبة الضربّية لـ a \pmod{b} هي أصغر عدد صحيح موجب k بحيث a^k = 1 \pmod{b}.

المنحنيات الإهليلجية

كما الحساب المعياريّ، تُستعمل حسابات المنحنيات الإهليلجية في كثير من أنظمة التشفير بالمفتاح العام. وكثير من أنظمة التشفير التي تعمل تقليديًّا بالحساب المعياريّ، مثل ديفي-هيلمان وDSA، لها نظيرة إهليلجية.

المنحنيات الإهليلجية هي منحنيات على الصورة الآتية:

y^2 = x^3 + ax + b

وتُسمّى هذه «الصيغة القصيرة لوايستراس» (short Weierstrass form)، وهي أكثر الصيغ شيوعًا عند الحديث عن المنحنيات الإهليلجية عمومًا. وهناك عدّة صيغ أخرى لها تطبيقات في التشفير في معظمها، وأبرزها صيغة إدواردز (Edwards form):

x^2 + y^2 = 1 + dx^2y^2

ويمكننا تعريف جمع النقاط على المنحنى.

TODO: انقل مسألة الزمرة الأبدية إلى موضع آخر، لأنّها تنطبق على مسألة الحقول لدينا أيضًا

كلّ هذا مجتمعًا يشكّل شيئًا يُسمّى الزمرة الأبدية (Abelian group). وهو مصطلح رياضيّ يبدو مخيفًا، لكنّ أساسياته يعرفها كلّ الناس تقريبًا. بالتحديد، إن كنتَ تعرف كيف تجمع الأعداد الصحيحة (\ldots -2, -1, 0, 1, 2, \ldots)، فأنت أصلًا تعرف زمرةً أبدية. وتستوفي الزمرة الأبدية خمس خصائص:

#. إذا كان a وb عنصرين في الزمرة الأبدية، وكان \star هو المعامِل، فإنّ a \star b هو أيضًا عنصر في تلك الزمرة الأبدية. وفعلًا، جمع أيّ عددين صحيحين يعطي دائمًا عددًا صحيحًا آخر. وتُسمّى هذه الخاصية الإغلاق، أو نقول إنّ الزمرة مغلقة تحت الجمع (أو أيًّا كان اسم العملية التي عرّفناها). #. إذا كان a وb وc عناصر في الزمرة الأبدية، فإنّ ترتيب العمليات لا يهم؛ وبعبارة أخرى: يمكننا نقل الأقواس. في صيغة المعادلة: (a \star b) \star c = a \star (b \star c). وفعلًا، ترتيب جمع الأعداد الصحيحة لا يهمّ؛ فمجموعها سيكون القيمة نفسها دائمًا. وتُسمّى هذه الخاصية التجميع، ويُقال إنّ الزمرة تجميعية. #. هناك عنصر محايد i واحد بالضبط، بحيث a \star i = i \star a = a. وبالنسبة إلى جمع الأعداد الصحيحة، فإنّه الصفر: a + 0 = 0 + a = a لكل a. #. لكل عنصر a، هناك عنصر عكسيّ b واحد بالضبط، بحيث a \star b = b \star a = i، حيث i هو العنصر المحايد. وفعلًا، بالنسبة إلى جمع الأعداد الصحيحة، a + (-a) = (-a) + a = 0 لكل a. #. ترتيب العناصر لا يهمّ لنتيجة العملية. فبالنسبة إلى كل العناصر a, b، لدينا a \star b = b \star a. وتُعرف هذه الخاصية بـ التبديل، ويُقال إنّ الزمرة تبديلية.

وتُسمّى الخصائص الأربع الأولى خصائص الزمرة، وهي التي تجعل الشيءَ زمرة؛ والخاصية الأخيرة هي ما يجعل الزمرة أبدية.

ويمكننا أن نرى أنّ منحنياتنا الإهليلجيّ، مع نقطة اللانهاية ومعامل الجمع، يشكّل زمرةً أبدية:

#. إذا كان P وQ نقطتين على المنحنى الإهليلجيّ، فإنّ P + Q تكون دائمًا أيضًا نقطةً على المنحنى. #. إذا كانت P وQ وR كلّها نقاطًا على المنحنى، فإنّ P + (Q + R) = (P + Q) + R، إذن المنحنى الإهليلجيّ تجميعيّ. #. هناك عنصر محايد، وهو نقطتنا اللانهائية O. فبالنسبة إلى كل النقاط P على المنحنى، P + O = O + P = P. #. لكل عنصر عنصر عكسيّ. وهذا أسهل شيءٍ تفسيرًا بصريًّا TODO: اشرحه بصريًّا #. ترتيب المتعاملين لا يهمّ، P + Q = Q + P لكل P, Q على المنحنى.

مسألة اللوغاريتم المتقطّع على المنحنيات الإهليلجية

TODO: اشرح بتفصيل

وكما في مسألة اللوغاريتم المتقطّع الاعتيادية، فإنّ مسألة اللوغاريتم المتقطّع على المنحنيات الإهليلجية لا تملك برهانًا رسميًّا على أنّ العملية «صعبة» التنفيذ: إنّما نعرف فقط أنّه لا توجد خوارزمية متاحة للعامة تُجريها بكفاءة. ومن الممكن، وإن كان ذلك بعيد الاحتمال، أن يكون لدى أحدهم خوارزمية سحرية تجعل المسألة سهلة، وعندها سينكسر تشفير المنحنيات الإهليلجية تمامًا. والأرجح بكثير هو أن نرى تدفّقًا مستمرًّا من التحسينات، يقترن بازدياد القدرة الحوسبية، ستأكل في النهاية من أمن الخوارزمية.

هجمات القنوات الجانبية

هجمات التوقيت

توقيت ذاكرة AES المؤقّتة

http://tau.ac.il/~tromer/papers/cache.pdf

هجمات التوقيت على المنحنيات الإهليلجية

TODO: اشرح لماذا صيغة إدواردز رائعة؟

هجمات قياس القدرة

TODO: قل شيئًا هنا.