شرح RSA

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

العددان الأوليان السريّان 61 و 53 يعطيان المقياس العام 3233. تتحول حروف HELLO بالأس العام 17 إلى 3000 و 28 و 2726 و 2726 و 1307، ويعيد الأس الخاص 2753 العدد 3000 إلى 72
العددان الأوليان السريّان 61 و 53 يعطيان المقياس العام 3233. تتحول حروف HELLO بالأس العام 17 إلى 3000 و 28 و 2726 و 2726 و 1307، ويعيد الأس الخاص 2753 العدد 3000 إلى 72

المشكلة التي يحلها RSA

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

مارتن هيلمان (يسار) وويتفلد ديفي (يمين)، 1977
مارتن هيلمان (يسار) وويتفلد ديفي (يمين)، 1977

إنشاء المفاتيح

اختر عددين أوليين كبيرين، p و q، واضربهما: n = p × q. احسب φ(n) = (p − 1)(q − 1)، وهي دالة أويلر، التي تعدّ الأعداد الأصغر من n التي لا تشترك معه في أي عامل. اختر أسًّا عامًا e لا يشترك مع φ(n) في أي عامل؛ والاختيار المعتاد هو 65537. ثم أوجد الأس الخاص d بحيث يترك e × d الباقي 1 عند قسمته على φ(n). وخوارزمية إقليدس الموسّعة تفعل ذلك بسرعة. المفتاح العام هو الزوج (e, n)؛ والمفتاح الخاص هو d. ومع p = 61 و q = 53 ينتج n = 3233 و φ(n) = 3120 و e = 17 و d = 2753.

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

تُحوَّل الرسالة أولًا إلى عدد m أصغر من n. لتشفيرها احسب c = mᵉ mod n، أي باقي قسمة mᵉ على n. ولفك التشفير احسب cᵈ mod n. وتضمن مبرهنة أويلر أن هذا يعيد m، لأن e × d أكبر بواحد من أحد مضاعفات φ(n). مع المفاتيح أعلاه يصبح الحرف A، ورمزه 65، العدد 65¹⁷ mod 3233 = 2790، و 2790²⁷⁵³ mod 3233 = 65 من جديد. ولا تُكتب قوى بهذا الحجم كاملة أبدًا: يحسبها التربيع المتكرر بعملية تربيع واحدة لكل بت من الأس، مع أخذ الباقي في كل خطوة.

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

يعمل RSA بالعكس أيضًا. رفع الرسالة إلى الأس الخاص، s = mᵈ mod n، ينتج توقيعًا لا يستطيع إنشاءه إلا مالك المفتاح. ويستطيع أي شخص التحقق منه بالمفتاح العام: إذا أعاد sᵉ mod n الرسالة m، فإن الرسالة جاءت من حامل d ولم تُغيَّر في الطريق. وعمليًا، ما يُوقَّع هو بصمة (hash) قصيرة للرسالة لا الرسالة نفسها. ومثل هذه التواقيع تحمي تحديثات البرامج والمواقع الآمنة والمستندات الإلكترونية.

لماذا هو آمن

يستطيع الجميع رؤية n و e. ولإيجاد d يحتاج المهاجم إلى φ(n)، ولإيجاد φ(n) يحتاج إلى p و q، لذا يرجع كسر RSA إلى تحليل n إلى عوامله. ضرب عددين أوليين يستغرق من الحاسوب جزءًا من الميكروثانية؛ أما تفكيك الناتج إليهما من جديد فيُعتقد أنه بالغ الصعوبة. وأكبر أعداد تحدي RSA التي حُلّلت حتى الآن، RSA-250 عام 2020، طوله 829 بت واستغرق تحليله نحو 2700 سنة من وقت الحاسوب. والمفاتيح المستخدمة اليوم لا تقل عن 2048 بت، أي نحو 617 رقمًا.

سرّ اكتُشف مرتين

في عام 1973، قبل RSA بأربع سنوات، وجد عالم الرياضيات البريطاني كليفورد كوكس المخطط نفسه أثناء عمله في وكالة الاستخبارات GCHQ، بالبناء على فكرة لزميله جيمس إليس. وقد صُنّف العمل سريًا ولم يُكشف إلا عام 1997. أما RSA نفسه فقد حصل على براءة اختراع في الولايات المتحدة عام 1983؛ وانتهت البراءة في سبتمبر 2000، بعد أسبوعين من طرح الخوارزمية في الملك العام.

رون ريفيست وأدي شامير ولين أدليمان (من اليسار إلى اليمين)
رون ريفيست وأدي شامير ولين أدليمان (من اليسار إلى اليمين)

RSA في التطبيق العملي

لا يشفّر RSA الحقيقي النص مباشرة أبدًا. تُحشى الرسالة ببايتات عشوائية، باستخدام مخطط مثل OAEP، حتى تُشفَّر الرسالة نفسها بشكل مختلف في كل مرة ولا تتسرب منها أنماط. ولأن RSA بطيء، فهو يُستخدم في الغالب لتبادل مفتاح قصير لشيفرة متماثلة سريعة مثل AES أو لحمايته، أو للتوقيع. ويمكن لحواسيب كمومية كبيرة بما يكفي أن تحلل n بسرعة بخوارزمية شور لعام 1994، ولهذا تُعتمد الآن طرق جديدة لما بعد الكم إلى جانب RSA.

استكشفه بنفسك

افتح العرض التوضيحي لتشفير RSA لتبني مفاتيح من أعدادك الأولية أو من أعداد عشوائية من 2 إلى 8 أرقام، وتشاهد خوارزمية إقليدس الموسّعة تعثر على d صفًا بعد صف، وتشفّر رسالة أو توقّعها حرفًا حرفًا، وتتابع التربيع المتكرر لأي حرف. ثم دع إيف تحلل n وشاهد كيف يزداد الوقت الذي تحتاجه مع حجم الأعداد الأولية.

الأسئلة المتداولة

لماذا يحتاج RSA إلى أعداد أولية؟

لأن حساب φ(n) سهل فقط عندما تعرف كيف يتحلل n إلى عوامل أولية. فإذا كان n = p × q حيث p و q أوليان، فإن φ(n) = (p − 1)(q − 1). كما أن الأعداد الأولية تجعل تحليل n صعبًا قدر الإمكان بالنسبة إلى حجمه، لأنه لا يملك أي عوامل صغيرة على الإطلاق.

لماذا يكون e غالبًا 65537؟

65537 = 2¹⁶ + 1 عدد أولي وفيه رقمان 1 فقط بالنظام الثنائي، لذا فالتشفير به لا يتطلب سوى 16 عملية تربيع وعملية ضرب واحدة. وهو أيضًا كبير بما يكفي لتجنب نقاط ضعف الأسس الصغيرة جدًا مثل 3.

ما الفرق بين RSA وديفي–هيلمان؟

يتيح ديفي–هيلمان لشخصين الاتفاق على مفتاح سري مشترك عبر قناة مفتوحة؛ لكنه لا يشفّر ولا يوقّع أي شيء بمفرده. أما RSA فيشفّر ويوقّع مباشرة بزوج مفاتيح. وكلاهما يقوم على مسائل سهلة في اتجاه وصعبة في الاتجاه الآخر: التحليل إلى العوامل في RSA، واللوغاريتم المتقطع في ديفي–هيلمان.

هل يمكن استخدام مفاتيح العرض للتشفير الحقيقي؟

لا. أعداده الأولية لا تتجاوز اثني عشر رقمًا، لذا يمكن تحليل أي مفتاح ينشئه في ثوانٍ أو أقل، كما أنه يشفّر كل حرف وحده دون حشو. إنه مخصص لرؤية كيف يعمل RSA، لا لحماية أي شيء.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

افتح العرض التوضيحي لتشفير RSA