التشفير بالمفتاح العام

الوصف

حتى الآن، لم نُنجِز إلّا التشفير بالمفتاح السرّي (secret-key encryption). فلنفترض أنّ بإمكانك امتلاك نظام تشفير لا يتضمّن مفتاحًا سرّيًا واحدًا، بل زوجًا من المفاتيح: مفتاح عامّ توزّعه بحرّية، ومفتاح خاصّ تحتفظ به لنفسك.

يستطيع الناس تشفير المعلومات الموجَّهة إليك باستعمال مفتاحك العامّ. وعندئذٍ يستحيل فكّ رموز تلك المعلومات من دون مفتاحك الخاصّ. ويُسمَّى ذلك التشفير بالمفتاح العام (public-key encryption).

لمدة طويلة، ظنّ الناس أنّ هذا مستحيل. غير أنّه ابتداءً من السبعينيات بدأت هذه الخوارزميات تظهر. وأول نظام تشفير متاح للعامة أنتجه ثلاثة من خَبَراء التشفير في MIT: Ron Rivest وAdi Shamir وLeonard Adleman. والخوارزمية التي نشروها لا تزال الأكثر شيوعًا إلى اليوم، وتحمل الحروف الأولى من أسمائهم العائلية: RSA.

خوارزميات المفتاح العام (public-key algorithms)\s لا تقتصر على التشفير. وفعلًا، لقد رأيتَ بالفعل في هذا الكتاب خوارزمية مفتاح عامّ لا تُستعمل مباشرةً في التشفير. وهناك في الواقع ثلاث أصناف متّصلة من خوارزميات المفتاح العام\s:

#. خوارزميات تبادل المفاتيح <key exchange> (key exchange)، مثل ديفي-هيلمان، تتيح لك الاتفاق على سرّ مشترك عبر وسيط غير آمن. #. خوارزميات التشفير، مثل التي سنتحدّث عنها في هذا الفصل، تتيح للناس التشفير من دون حاجة إلى الاتفاق على سرّ مشترك. #. خوارزميات التوقيع، التي سنتحدّث عنها في فصل لاحق، تتيح لك توقيع أيّ معلومة باستعمال مفتاحك الخاصّ بطريقة تتيح لأيّ شخص آخر التحقّق منها بسهولة باستعمال مفتاحك العامّ.

لماذا لا نستعمل التشفير بالمفتاح العامّ لكلّ شيء؟

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

والسبب الأهمّ لهذا بكثير هو الأداء. فمقارنةً بشيفرات التيار السريعة (stream cipher\s) (أصلية كانت أم غير ذلك)، فإنّ آليات التشفير بالمفتاح العام (public-key encryption) بطيئة إلى حدٍّ متطرّف. فمثلًا، مع مفتاح RSA بطول 2048 بتًّا (256 بايتًا)، يستغرق التشفير 0.29 ميغادورة، بينما يستغرق فكّ التشفير 11.12 ميغادورة. cryptopp:bench ولوضع ذلك في منظور صحيح، تعمل خوارزميات المفتاح المتماثل ضمن رتبة مقدار تعادل 10 دورات تقريبًا لكلّ بايت في أيّ من الاتجاهين. وهذا يعني أنّ خوارزمية المفتاح المتماثل تحتاج نحو 3 كيلودورة لفكّ تشفير 256 بايتًا، وهو أسرع بنحو 4000 مرّة من النسخة اللامتماثلة. وحتى أفضل ما توصّل إليه علم الشيفرات المتماثلة الآمنة أسرع من ذلك: فـ AES-GCM مع تسريع العتاد أو Salsa20/ChaCha20 يحتاجان نحو 2 إلى 4 دورات لكلّ بايت فقط، مما يوسّع فجوة الأداء أكثر.

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

RSA

وكما ذكرنا من قبل، فإنّ RSA إحدى أوائل أنظمة التشفير بالمفتاح العام (public-key encryption) العملية. ولا يزال الأكثر شيوعًا إلى هذا اليوم.

التشفير وفكّ التشفير

يعتمد تشفير RSA وفكّ تشفيره على الحساب النمطي (modular arithmetic). وقد ترغب في مراجعة مقدّمة في الحساب النمطي <modular-arithmetic> قبل المتابعة.

يصف هذا القسم المسألة الرياضية المبسّطة وراء RSA، والمشار إليها عادةً بـ«RSA الكتاب المدرسي» (textbook RSA). وهي وحدها لا تنتج نظام تشفير آمنًا. وسنرى في قسم لاحق تركيبًا آمنًا اسمه OAEP مبنيًّا فوقها.

ولتوليد مفتاح، تختار عددين أوّليَّين (prime) كبيرين p وq. ويجب أن يُختار هذان العددان عشوائيًّا وفي سرّية. ثمّ تضربهما معًا لإنتاج المقياس (modulus) N، وهو عامّ. ثمّ تختار أس التشفير (encryption exponent) e، وهو أيضًا عامّ. وعادةً ما تكون هذه القيمة إمّا 3 أو 65537. ولأنّ هذين العددين يحويان عددًا صغيرًا من الآحاد 1 في تفككهما الثنائي، فإنا نستطيع حساب الأُسّ بكفاءة أكبر. ومجتمعةً، فإنّ (N, e) هو المفتاح العامّ. ويستطيع أيّ شخص استعمال المفتاح العامّ لتشفير رسالة M إلى نصّ مشفَّر C:

C \equiv M^e \pmod{N}

أمّا المشكلة التالية فهي فكّ التشفير. ويتبيّن أنّ هناك قيمة d هي أس فكّ التشفير (decryption exponent)، تحوّل C مجدّدًا إلى M. وهذه القيمة سهلة الحساب نسبيًّا بافتراض أنّك تعرف p وq، وهو ما نعرفه فعلًا. وباستعمال d، تستطيع فكّ تشفير الرسالة على هذا النحو:

M \equiv C^d \pmod{N}

يعتمد أمن RSA على استحالة إجراء عملية فكّ التشفير تلك من دون معرفة الأُسّ السرّي d، وعلى أنّ حساب الأُسّ السرّي d من المفتاح العامّ (N, e) صعب إلى حدٍّ كبير (مستحيل عمليًّا). وسنرى في القسم التالي طرائق لكسر RSA.

كسر RSA

كثير من الأنظمة التشفيرية، يعتمد RSA على مسألة RSA، وتحديدًا: إيجاد الرسالة الصريحة M، معطى نصًّا مشفَّرًا C ومفتاحًا عامًّا (N, e) في المعادلة:

C \equiv M^e \pmod{N}

وأيسر طريقة نعرفها للقيام بذلك هي تحليل N (factor) إلى p \cdot q من جديد. فمعطى p وq، يستطيع المهاجم ببساطة أن يكرّر العملية التي يجريها المالك الشرعي للمفتاح أثناء توليد المفتاح، ليحسب الأُسّ الخاصّ d.

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

في هذا القسم، لم ندرس إلّا هجوم استعادة المفتاح الخاصّ الذي يهاجم مسألة RSA الرياضية المجرّدة البحتة عبر تحليل المقياس. أمّا في القسم التالي فسنرى جميع أنواع الهجمات الواقعية على RSA التي تعتمد على عيوب في التنفيذ (implementation) لا على المسألة الرياضية المذكورة أعلاه.

مزالق التنفيذ

لا توجد حتى الآن أيّ كسور عملية كاملة معروفة لـ RSA. لكنّ هذا لا يعني أنّ الأنظمة التي تستعمل RSA لا تُكسَر باستمرار. فكما في معظم الأنظمة التشفيرية المكسورة، هناك حالات كثيرة تكون فيها مكوّنات سليمة لكنّها طُبِّقت على نحو خاطئ، فتُنتج نظامًا بلا فائدة. ولمزيد من الاستعراض الكامل للأشياء التي يمكن أن تخطئ في تنفيذات RSA، راجع boneh:twentyyears وanderson:mindingyourpsandqs. وسنكتفي في هذا الكتاب بإبراز بضعة أمثلة مثيرة.

حشو PKCSv1.5 '''''''''''''''

ملح ''''

Salt ^[1] هو نظام تهيئة (provisioning) مكتوب بايثون. ولديه عيب رئيسي واحد: فهو يحوي وحدة تُسمّى crypt. وبدلًا من إعادة استعمال الأنظمة التشفيرية الكاملة القائمة، فإنّه ينفّذ نظامه الخاصّ، مستعملًا RSA وAES المقدَّمَين من حزمة طرف ثالث.

لمدة طويلة، كان Salt يستعمل أُسًّا عامًّا (e) قدره 1، ما يعني أنّ مرحلة التشفير لم تكن تفعل شيئًا في الواقع: P^e \equiv P^1 \equiv P \pmod N. وكان هذا يعني أنّ النصّ المشفَّر الناتج لم يكن في الواقع سوى النصّ الصريح. وبرغم أنّ هذه المشكلة أُصلحت الآن، فإنّ ذلك يبيّن فقط أنّه على الأغلب ينبغي ألّا تنفّذ التشفير بنفسك. وSalt يدعم حاليًّا أيضًا SSH كنقل، لكنّ نظام RSA/AES المنزلي المذكور أعلاه ما زال قائمًا، وهو حتى وقت كتابة هذا الكتاب لا يزال النقل الموصى به والنقل الافتراضي.

OAEP

OAEP، اختصارًا لعبارة optimal asymmetric encryption padding (حشو التشفير اللامتماثل الأمثل)، يمثّل أفضل ما توصّل إليه علم حشو RSA. وقد أدخلاه Mihir Bellare وPhillip Rogaway سنة 1995. bellarerogaway:oaep. ويبدو بنيته على هذا النحو:

بنية حشو OAEP

الشيء الذي يُشفَّر في النهاية هو X \| Y، وطوله n بتًّا، حيث n هو عدد بتّات N مقياس RSA. وهو يأخذ كتلة عشوائية R بطول k بتًّا، حيث k ثابت يحدّده المعيار. أوّلًا يُحشو الرسالة بأصفار لتصبح بطول n - k بتًّا. وإذا نظرت إلى «السُلّم» أعلاه، فإنّ كلّ ما في النصف الأيسر بطول n - k بتًّا، وكلّ ما في النصف الأيمن بطول k بتًّا. وتُدمج الكتلة العشوائية R مع الرسالة M \| 000\ldots المحشوّة بالأصفار باستعمال دالتَي «الباب الخلفي» (trapdoor)، وهما G وH. ودالة الباب الخلفي هي دالة يسهل حسابها إلى حدٍّ كبير في اتجاه واحد ويصعب عكسها إلى حدٍّ كبير. وفي الممارسة العملية، هذه دوالّ تجزئة تشفيرية (cryptographic hash functions)؛ وسنرى المزيد عنها لاحقًا.

وكما يتّضح من المخطّط، تأخذ G مقدار k بتًّا وتحوله إلى n - k بتًّا، وH هي الأمر بالعكس: تأخذ n - k بتًّا وتحولها إلى k بتًّا.

تُدمج الكتلتان الناتجتان X وY معًا، ثمّ يُشفَّر الناتج باستعمال عملية تشفير RSA القياسية، لإنتاج النصّ المشفَّر.

ولنرى كيف يعمل فكّ التشفير، نعكس كلّ الخطوات. فيحصل المستقبِل على X \| Y عند فكّ تشفير الرسالة. وهو يعرف k لأنّها ثابتة في البروتوكول، لذا يستطيع تقسيم X \| Y إلى X (وهي n - k بتًّا الأولى) وY (وهي k بتًّا الأخيرة).

في المخطّط السابق، كانت الأسهم تشير إلى تطبيق الحشو. فاعكس أسهم جانب السُلّم لترى كيفية التراجع عن الحشو:

TODO: اعكس الأسهم

نريد أن نصل إلى M، وهي ضمن M \| 000\ldots. وهناك طريقة واحدة فقط لحسابها، وهي:

M \| 000\ldots = X \xor G(R)

وحساب G(R) أصعب قليلًا:

G(R) = G(H(X) \xor Y)

وكما ترى، فإنّنا — على الأقلّ في بعض تعريفات الدالتَي H وG — نحتاج إلى X كاملة وY كاملة (وبالتالي الرسالة المشفَّرة بأسرها) كي نعرف أيّ شيء عن M. وهناك دوالّ كثيرة تصلح اختيارًا جيدًا لـH وG؛ المبنيّة على دوالّ التجزئة التشفيرية، التي سنتحدّث عنها بمزيد من التفصيل لاحقًا في الكتاب.

التشفير بالمنحنيات الإهليلجية

TODO: هذا

المشكلة المتبقّية: التشفير غير المصادَق

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

وعند حديثنا عن شيفرات التيار (stream cipher)\s، كانت إحدى المشكلات المتبقّية التي واجهناها هي أنّنا ما زلنا بحاجة إلى تبادل المفاتيح السرّية مع عدد كبير من الناس. أمّا مع الأنظمة التشفيرية بالمفتاح العامّ، مثل التشفير بالمفتاح العامّ وبروتوكولات تبادل المفاتيح (key exchange)، فقد رأينا الآن طريقتين لحلّ تلك المشكلة. ويعني ذلك أنّنا يمكننا الآن التواصل مع أيّ شخص، باستعمال المعلومات العامّة وحدها، مع أمان تامّ من المستقِعين.

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

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

ونتيجةً لذلك، صار واضحًا أنّنا بحاجة إلى طرائق للمصادقة إضافةً إلى التشفير في اتصالاتنا السرّية. ويتم ذلك بإضافة معلومات إضافية إلى الرسالة لا يمكن إلّا للمُرسِل أن يكون قد حسبها. ومثل التشفير تمامًا، تأتي المصادقة في صيغتين: بالمفتاح الخاصّ (المتماثل) وبالمفتاح العامّ (اللامتماثل). وتُسمَّى أنظمة المصادقة المتماثلة عادةً رموز مصادقة الرسائل (message authentication codes)، أمّا مقابل المفتاح العامّ فيُسمَّى عادةً توقيعًا (signature).

أوّلًا، سنقدّم بناءً تشفيريًا (primitive) جديدًا: دوالّ التجزئة (hash functions). ويمكن استعمالها لإنتاج أنظمة التوقيع فضلًا عن أنظمة مصادقة الرسائل. وللأسف، فكثيرًا ما يُساء استعمالها أيضًا لإنتاج أنظمة غير آمنة تمامًا.

إذن، هناك Salt نظام التهيئة، وsalt\s الأشياء المستعملة في مخازن كلمات المرور المكسورة، وNaCl وهي مكتبة التشفير التي تُنطق «salt»، وNaCl التي تشغّل شيفرة أصلية (native code) في بعض المتصفّحات، وربما أشياء أخرى كثيرة أنساها. هل نتوقّف عن تسمية الأشياء باسمه؟ ↩︎

السابق تبادل المفاتيح التالي دوال التجزئة