خوارزميات التوقيع

خوارزميات التوقيع

الوصف

خوارزمية التوقيع (signature algorithm) هي نظير خوارزمية مصادقة الرسائل بالمفتاح العام. وهي تتألّف من ثلاثة أجزاء:

#. خوارزمية توليد المفاتيح، ويمكن أن تتشارك مع خوارزميات المفتاح العام\s أخرى #. خوارزمية توليد التوقيع #. خوارزمية التحقّق من التوقيع

يمكن بناء خوارزميات التوقيع باستعمال خوارزميات التشفير. فباستعمال المفتاح الخاص، نُنتج قيمة مبنيّة على الرسالة، عادةً باستعمال دالة تجزئة (hash function) تشفيرية. ثمّ يستطيع أيّ شخص استعمال المفتاح العام ليسترجع تلك القيمة، ويحسب ما ينبغي أن تكون عليه القيمة انطلاقًا من الرسالة، ثمّ يقارن بين الاثنين للتحقّق. والفرق الواضح بين هذا والتشفير بالمفتاح العام (public-key encryption) هو أنّ التوقيع يستعمل المفتاح الخاص لإنتاج الرسالة (وهي التوقيع في هذه الحالة)، ويستعمل المفتاح العام لتفسيرها، وهو عكس ما يجري في التشفير وفكّ التشفير.

ويتجاوز الشرحُ أعلاه تفاصيلَ مهمّةَ كثيرة. وسنناقش أدناه مخطّطات حقيقيّة بمزيد من التفصيل.

التوقيعات المعتمدة على RSA

PKCS#1 v1.5

TODO (راجع #48)

PSS

TODO (راجع #49)

DSA

خوارزمية التوقيع الرقمي (Digital Signature Algorithm, DSA) هي معيار الحكومة الأمريكيّة للتوقيعات الرقمية. وقد اقترحه المعهد الوطني للمعايير والتكنولوجيا (NIST) أوّل مرّة سنة 1991، ليستعمل في معيار التوقيع الرقمي (Digital Signature Standard, DSS). أمّا الخوارزمية فتُنسب إلى David W. Kravitz، الذي كان مستشارًا تقنيًا سابقًا في NSA.

وتتمّ عملية توليد مفاتيح DSA في خطوتين. الخطوة الأولى هي اختيار معاملات، يمكن أن تتشاركها بين المستخدمين. أمّا الخطوة الثانية فهي توليد المفتاح العام والمفتاح الخاص لمستخدم واحد.

توليد المعاملات

نبدأ باختيار دالة تجزئة تشفيرية معتمدة H. ونختار كذلك طول المفتاح L وطول عدد أوّلي N. وقد نصّ معيار DSS الأصلي على أن يكون L بين 512 و1024، غير أنّ NIST توصي اليوم بطول قدره 3072 للمفاتيح التي يتجاوز عمرها الأمني سنة 2030. وكما يزداد L، ينبغي أن يزداد N كذلك.

ثمّ نختار عددًا أوّليًا q بطول N بتًّا؛ ويجب أن يكون N أصغر من أو يساوي طول خرج دالة التجزئة. ونختار كذلك عددًا أوّليًا p بطول L بتًّا بحيث يكون p-1 من مضاعفات q.

والجزء الأخير هو الأكثر إرباكًا. فعلينا أن نجد عددًا g تكون رتبته الضربية (multiplicative order ) modulo p هي q. والأمر السهل للقيام بذلك هو وضع g \equiv 2^{(p-1)/q} \pmod{p}. وإذا كانت g مساويةً لـ 1، فيمكننا تجربة عدد آخر أكبر من 2 وأصغر من p-1.

ومتى توفّرت لدينا المعاملات (p, q, g)، أمكن مشاركتها بين المستخدمين.

توليد المفاتيح

وبما أنّنا تسلّحنا بالمعاملات، فقد حان الوقت لحساب المفتاح العام والمفتاح الخاص لمستخدم بعينه. أوّلًا، نختار x عشوائيّة بشرط 0 < x < q. ثمّ نحسب y حيث y \equiv g^x \pmod{p}. على أنّ هذا يمنحنا المفتاح العام (p, q, g, y)، والمفتاح الخاص x.

توقيع رسالة

ولتوقيع رسالة، يختار المُوقِّع عددًا k عشوائيًّا بين 0 وq. وقد اتضح أنّ اختيار k ذاك عمليّة حسّاسة ومتعمّقة إلى حدٍّ ما؛ لكنّنا سنعود إليها بمزيد من التفصيل لاحقًا. وبعد اختيار k، يحسب المُوقِّع جزأي التوقيع r, s الخاصَّين بالرسالة m:

$$r \equiv (g^k \pmod p) \pmod q$$ $$s \equiv k^{-1} (H(m) + xr) \pmod q$$

فإذا كانت أيّ من هاتين النتيجتين تساوي 0 (وهو حدث نادر، باحتمال واحد في q، وq عدد كبير إلى حدٍّ ما)، فاختر k أخرى.

TODO: تحدّث عن k\\ -1، وهو المقلوب النمطي (راجع #52)

التحقّق من التوقيع

والتحقّق من التوقيع أعقد بكثير. ومعطى الرسالة m والتوقيع (r, s):

$$w \equiv s^{-1} \pmod q$$ $$u_1 \equiv wH(m) \pmod q$$ $$u_2 \equiv wr \pmod q$$ $$v \equiv (g^{u_1}y^{u_2} \pmod p) \pmod q$$

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

المشكلة في k

المشكلة في :math:k

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

وعلى الخصوص، فإنّ اختيار معامل التوقيع k مسألة حرجة. فمتطلّبات هذا الرقم تُعدّ من أشدّ متطلّبات كلّ الأعداد العشوائيّة في الخوارزميات التشفيريّة. فمثلًا، تتطلّب خوارزميات كثيرة قيمةً عشوائيّة وحيدة (nonce). ولا يلزم في القيمة العشوائيّة الوحيدة سوى أن تكون فريدة: يمكنك استعمالها مرّة واحدة، ثمّ لا يمكن أن تستعملها مرّة أخرى أبدًا. ولا يلزم أن تكون سرّية. بل ولا يلزم حتى ألّا تكون متوقّعة. ويمكن تنفيذ القيمة العشوائيّة الوحيدة بعدّاد بسيط، أو بساعة رتيبة. أمّا خوارزميات أخرى كثيرة، مثل وضع CBC (CBC mode)، فتستعمل متجه تهيئة (initialization vector). ولا يلزم في متجه التهيئة أن يكون فريدًا: بل يلزم فقط ألّا يكون متوقّعًا. ولا يلزم أن يكون سرّيًا أيضًا: فمتجهات التهيئة تُلحق عادةً بالنصّ المشفَّر. ومتطلّبات DSA في قيمة k تجمع كلّ هذه المتطلّبات:

• يجب أن تكون فريدة.
• يجب ألّا تكون متوقّعة.
• يجب أن تكون سرّية.

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

ويُبيّن الواقع أنّ كثيرًا من تنفيذات DSA لا تتأكّد حتى من شرط الفريدة، فتُعيد بكلّ بساطة استعمال قيم k. وهذا يتيح استرجاعًا مباشرًا للمفتاح السرّي باستعمال عمليات حسابية أساسيّة. وبما أنّ هذا الهجوم أسهل كثيرًا في الفهم، وقابل للتطبيق إلى حدٍّ شائع، ومدمّر بالقدر نفسه، فسنناقشه بالتفصيل.

ولنفترض أنّ مهاجمًا يرى عدّة توقيعات (r_i, s_i)، الخاصّة برسائل مختلفة m_i، وأنّها كلّها تحمل k نفسها. ويختار المهاجم أيّ توقيعين (r_1, s_1) و(r_2, s_2) للرسالتين m_1 وm_2 على التوالي. وبكتابة معادلتَي s_1 وs_2:

$$s_1 \equiv k^{-1} (H(m_1) + xr_1) \pmod q$$ $$s_2 \equiv k^{-1} (H(m_2) + xr_2) \pmod q$$

ويمكن للمهاجم أن يبسّط هذا أكثر: فبحسب تعريف r_i، يجب أن يتساوى r_1 وr_2:

$$r_i \equiv g^k \pmod q$$

ولأنّ المُوقِّع يعيد استعمال k، ولا تعتمد قيمة r إلّا على k، فإنّ كلّ قيم r_i ستكون متساوية. ولأنّ المُوقِّع يستعمل المفتاح نفسه، فإنّ x متساوية في المعادلتين أيضًا.

نطرح معادلتي s_i إحداهما من الأخرى، ثمّ نتبع ذلك ببعض التحويلات الحسابية الأخرى:

$$\begin{aligned} s_1 - s_2 & \equiv & k^{-1} (H(m_1) + xr) - k^{-1} (H(m_2) + xr) \pmod q \\ & \equiv & k^{-1} \left( (H(m_1) + xr) - (H(m_2) + xr) \right) \pmod q \\ & \equiv & k^{-1} (H(m_1) + xr - H(m_2) - xr) \pmod q \\ & \equiv & k^{-1} (H(m_1) - H(m_2)) \pmod q \end{aligned}$$

وهذا يعطينا الحلّ البسيط والمباشر لـ k:

$$k \equiv \left(H(m_1) - H(m_2)\right) \left(s_1 - s_2\right)^{-1} \pmod q$$

وقيمتا التجزئة H(m_1) وH(m_2) سهلتا الحساب. فهما ليستا سرّيتين: فالرسائل التي يجري توقيعها علنيّة. أمّا القيمتان s_1 وs_2 فهما جزء من التوقيعات التي راها المهاجم. ومن ثمّ يستطيع المهاجم أن يحسب k. غير أنّ ذلك لا يمنحه المفتاح الخاص x بعد، ولا القدرة على تزوير التوقيعات.

ولنُعِد كتابة معادلة s من جديد، لكنّنا هذه المرة نُدرك k على أنّه معلوم، وx على أنّه هو المتغيّر الذي نحاول حلّه:

$$s \equiv k^{-1} (H(m) + xr) \pmod q$$

وكلّ زوج (r, s) يمثّل توقيعًا صالحًا يحقّق هذه المعادلة، ومن ثمّ يكفينا أن نأخذ أيّ توقيعٍ رايناه. ونحلّ المعادلة لإيجاد x بجملة من الجبر:

$$sk \equiv H(m) + xr \pmod q$$ $$sk - H(m) \equiv xr \pmod q$$ $$r^{-1}(sk - H(m)) \equiv x \pmod q$$

ومرّة أخرى، H(m) علنيّة، وكان المهاجم بحاجة إليها أصلًا من أجل حساب k. فهو قد حسب k بالفعل، وs منتزعةٌ مباشرةً من التوقيع. ولا يبقى إلّا r^{-1} \pmod q (تُقرأ: «المقلوب النمطي لـ r modulo q»)، وهو ما يمكن حسابه بكفاءة أيضًا. (ولمزيد من المعلومات، راجع الملحق عن الحساب النمطي <modular-arithmetic>؛ وانتبه إلى أنّ q عدد أوّلي، فيمكن حساب المقلوب النمطي مباشرةً.) ويعني ذلك أنّ المهاجم، ما إن يكتشف k لأيّ توقيع، يستطيع استرجاع المفتاح الخاص مباشرةً.

حتى الآن، افترضنا أنّ المُوقِّع المكسور سيستعمل k نفسها دائمًا. ولكي يكون الأمر أسوأ من ذلك، لا يحتاج المُوقِّع إلّا أن يعيد استعمال k مرّة واحدة في أيّ توقيعَين يراهما المهاجم كي ينجح الهجوم. وكما رأينا، إذا تكرّرت k، فإنّ قيم r_i تتكرّر بدورها. وبما أنّ r_i جزء من التوقيع، فإنّ الوقوف على وقوع المُوقِّع في هذا الخطأ سهلٌ إلى حدٍّ ما. ومن ثمّ، حتّى لو كان إعادة استعمال k أمرًا نادرًا ما يفعله المُوقِّع (مثلًا لأنّ مولّد الأعداد العشوائيّة لديه معطوب)، فإنّ فعله مرّة واحدة يكفي ليعطّل المهاجم مخطّط DSA.

وباختصار، فإنّ إعادة استعمال معامل k في عملية توقيع DSA تعني أنّ المهاجم يسترجع المفتاح الخاص.

TODO: Debian http://rdist.root.org/2009/05/17/the-debian-pgp-disaster-that-almost-was/

ECDSA

TODO: اشرح (راجع #53)

ومثل DSA العاديّة، فإنّ اختيار k بالغ الأهمية. وهناك هجمات تنجح في استرجاع مفتاح التوقيع باستعمال بضع آلاف من التوقيعات، حين يتسرّب مجرّد عدد قليل من بتّات القيمة العشوائيّة الوحيدة. demulder:ecdsa

المصادقات القابلة للإنكار

التوقيعات مثل التي وصفناها أعلاه توفّر خاصيّة تُسمّى عدم الإنكار (non-repudiation). باختصار، هذا يعني أنّك لا تستطيع لاحقًا أن تنكر أنّك كنتَ مُرسِل الرسالة الموقَّعة. ويستطيع أيّ شخص التحقّق من أنّ التوقيع قد أُنشئ باستعمال مفتاحك الخاص، وهو أمر لا يستطيع سواه.

قد لا تكون هذه خاصيّة مفيدة في كلّ الأحوال؛ فقد يكون من الأَوْلى أن تملك مخطّطة لا يستطيع إلّا المستلِم المقصود التحقّق من التوقيع. ومن الطُّرُق البديهية لتصميم مثل هذه المخطّطة أن نحرص على أن يكون بإمكان المستلِم (أو في الواقع أيّ شخص آخر) أن يكون قد حسب القيمة نفسها.

يمكن إنكار مثل هذه الرسائل؛ وغالبًا ما تُسمّى مخطّطة من هذا النوع «المصادقة القابلة للإنكار» (deniable authentication). فبينما تُصدِق هذه المخطّطة المُرسِل أمام المستلِم المقصود، يستطيع المُرسِل أن ينكر لاحقًا (أمام أطراف أخرى) أنّه أرسل الرسالة. وبالمثل، لا يستطيع المستلِم أن يقنع أيّ شخص آخر بأنّ المُرسِل أرسل تلك الرسالة بعينها.