تشفير المفتاح غير المتماثل

في هذا الدرس سنتناول تشفير المفتاح غير المتماثل الذي يُشكّل أساس كثير من التفاعلات الشبكية الآمنة اليوم.

بنهاية الدرس سنكون قد تناولنا:

• ما هو تشفير المفتاح غير المتماثل
• استخدامات تشفير المفتاح غير المتماثل، بما في ذلك تبادل المفاتيح والتوقيعات الرقمية
• أمان تشفير المفتاح غير المتماثل بشكل عام
• تفاصيل إضافية حول خوارزميات RSA وDSA والمنحنيات الإهليلجية وأمانها
• أمثلة برمجية بلغة Python توضح كيفية عمل هذه الخوارزميات في التطبيق العملي
• التهديدات التي تواجه هذه الخوارزميات من أجهزة الحوسبة الكلاسيكية والكمومية على حدٍّ سواء

مقدمة إلى تشفير المفتاح غير المتماثل

كما تعلمنا في الدرس السابق، يتميز تشفير المفتاح المتماثل بسرعته وكفاءته في حماية المعلومات، غير أن له بعض القيود:

1. مع تزايد عدد الأطراف الراغبة في تبادل المعلومات بشكل آمن، يتزايد عدد المفاتيح المطلوبة بشكل تركيبي. كما أنه لا يوفر آلية لتوزيع هذه المفاتيح بأمان بين المُرسِلين والمُستقبِلين.
2. لا يوفر دعماً لـعدم الإنكار. إذ يستطيع أي طرف فك تشفير الرسائل أو تشفيرها دون وجود وسيلة لضمان استلام الرسالة أو تحديد مصدرها.

الحل لكلا المشكلتين يتمثل في تشفير المفتاح غير المتماثل (AKC)، المعروف أيضاً بـتشفير المفتاح العام (PKC)، والذي يُشكّل حجر الزاوية في الأمن الرقمي الحديث.

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

الشكل 1. تشفير المفتاح غير المتماثل

يوفر تشفير المفتاح غير المتماثل (AKC) عدة وظائف مفيدة، منها:

1. التشفير وفك التشفير لتحقيق سرية الاتصالات.
2. التوقيعات الرقمية لضمان المصداقية وسلامة البيانات وعدم الإنكار.
3. تبادل المفاتيح الآمن لتيسير الاستخدام اللاحق لأنظمة التشفير المتماثل.

في التطبيقات الحديثة، يُستخدم تشفير المفتاح غير المتماثل (AKC) بصورة رئيسية للتوقيعات الرقمية وتبادل المفاتيح الآمن. في هذا الدرس، نُقدّم هاتين الوظيفتين الأساسيتين، ثم نناقش عدة أشكال مختلفة من البروتوكولات التشفيرية الخاصة بهما.

تبادل المفاتيح باستخدام تشفير المفتاح غير المتماثل

من المشكلات الجوهرية في التشفير هي تبادل المفاتيح بأمان. على سبيل المثال، إذا أراد طرفان استخدام التشفير المتماثل، فإنهما يحتاجان إلى المفتاح ذاته لتشفير الرسائل وفك تشفيرها. لكن كيف يتبادلان هذا المفتاح بشكل آمن؟ يُعالج تشفير المفتاح غير المتماثل هذه الإشكالية من خلال آليات تبادل مفاتيح تفاعلية وغير تفاعلية.

تبادل المفاتيح التفاعلي

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

أشهر هذه البروتوكولات هو خوارزمية ديفي-هيلمان (DH)، التي صُمِّمت تحديداً لتيسير تبادل المفاتيح. في هذا البروتوكول، يُولِّد كل طرف زوجاً من المفاتيح (عام وخاص) ويُعلن مفتاحه العام. ثم يستخدم كل طرف مفتاحه الخاص ومفتاح الطرف الآخر العام لإنشاء مفتاح سري مشترك. تعتمد خوارزمية DH على مبادئ الحسابات المعيارية (modular arithmetic) لضمان أن كلا الطرفين يصلان إلى المفتاح السري المشترك ذاته، على الرغم من أن كل طرف لا يطلع إلا على المفتاح العام للطرف الآخر.

تمتد أنظمة التشفير الحديثة القائمة على تشفير المنحنى الإهليلجي (ECC) لتشمل هذا المفهوم من خلال ديفي-هيلمان للمنحنى الإهليلجي (ECDH). تعمل خوارزمية ECDH بطريقة مشابهة لـDH لكنها تستثمر خصائص المنحنيات الإهليلجية، مما يُفضي إلى نظام أكثر أماناً وكفاءة.

الشكل 2. بروتوكول تبادل المفاتيح

تبادل المفاتيح غير التفاعلي

على خلاف بروتوكولات تبادل المفاتيح كـDH وECDH التي تتطلب تفاعلاً متبادلاً للاتفاق على المفتاح المتماثل، يوفر تشفير المفتاح غير المتماثل (AKC) أيضاً طرقاً غير تفاعلية لإنشاء مفتاح سري مشترك. في هذه الأنظمة، يُولِّد أحد الطرفين زوج مفاتيح (عام وخاص) ويُشارك المفتاح العام مع الطرف الآخر. يقوم الطرف الثاني بعدها بإنشاء مفتاح متماثل عشوائي، وتشفيره بالمفتاح العام المُستلَم، ثم إرساله إلى الطرف الأول. يستخدم الطرف الأول مفتاحه الخاص لفك تشفير الرسالة المُستلَمة والحصول بذلك على المفتاح المتماثل المشترك. يُعدّ هذا النظام غير تفاعلي بمعنى أن المفتاح المتماثل يُحدَّد من قِبَل طرف واحد ويُنقل بأمان إلى الطرف الآخر في صورة مشفرة.

من الاعتبارات المهمة في تبادل المفاتيح غير التفاعلي الفارقُ في الطول بالبِت بين المفتاح المتماثل الذي يرغب الطرفان في تبادله والأحجام الموصى بها للرسائل في تشفير المفتاح غير المتماثل. عادةً ما تتراوح المفاتيح المتماثلة الحديثة بين 128 و256 بِت، بينما تعمل أنظمة تشفير المفتاح غير المتماثل كـRSA مع أحجام رسائل تتراوح بين 1024 و4096 بِت. لذلك، عند استخدام تشفير المفتاح غير المتماثل لنقل مفتاح متماثل، يجب تأمينياً ترميزه في رسالة أطول تتراوح بين 1024 و4096 بِت. يمكن تحقيق ذلك عبر نهجين:

• تبادل المفاتيح القائم على الحشو (Padding): في هذا النهج، يُولَّد المفتاح المتماثل الأقصر (128-256 بِت) أولاً، ثم يُستخدم مخطط حشو عكسي متفق عليه مثل OAEP لتضمينه في رسالة أطول (1024-4096 بِت). تُشفَّر هذه الرسالة الأطول باستخدام تشفير المفتاح غير المتماثل وتُبثّ بوصفها نصاً مشفراً. يقوم المُستقبِل أولاً بفك تشفير النص المشفر ثم إزالة الحشو لاستخراج المفتاح المتماثل الأقصر.

• آليات تغليف المفاتيح (KEMs): مع تبادل المفاتيح القائم على KEM، يُولَّد أولاً نص عادي طويل عشوائي (1024-4096 بِت)، يمكن منه استخراج مفتاح متماثل أقصر (128-256 بِت) باستخدام دالة اشتقاق مفاتيح (KDF) متفق عليها. يُشفَّر النص العادي الأطول باستخدام تشفير المفتاح غير المتماثل ويُبثّ إلى المُستقبِل كنص مشفر. يفك المُستقبِل تشفير النص المشفر باستخدام مفتاحه الخاص، ثم يستخدم دالة KDF لاستخراج المفتاح المتماثل الأقصر (128-256 بِت). يمكن استخدام أنظمة تشفير شائعة مثل RSA، بفضل قدرتها على تشفير البيانات مباشرة، لتنفيذ آليات KEM.

الشكل 3. آلية تغليف المفاتيح

التوقيعات الرقمية باستخدام تشفير المفتاح غير المتماثل

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

الشكل 4. التوقيعات الرقمية باستخدام تشفير المفتاح غير المتماثل

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

يُعدّ المعيار الأمريكي الحالي لمعالجة المعلومات الفيدرالية (FIPS) للتوقيعات الرقمية مخططاً مخصصاً يُعرف ببساطة بـخوارزمية التوقيع الرقمي (DSA). تستخدم DSA، بطريقة تشبه بروتوكول ديفي-هيلمان إلى حدٍّ ما، الخصائص الجبرية لـالأس المعياري والمعكوسات الضربية في توليد التوقيعات والتحقق منها.

خوارزمية التوقيع الرقمي للمنحنى الإهليلجي (ECDSA) هي نسخة من DSA تعتمد على ECC، وتوفر الوظيفة ذاتها لكن بمفاتيح أقصر بكثير. ينعكس ذلك إيجاباً على الكفاءة، مما يجعلها خياراً شائعاً للأنظمة ذات القيود على الموارد.

سيتم توضيح كلٍّ من DSA وECDSA بمزيد من التفصيل لاحقاً.

مخططات التوقيع الرقمي باستخدام أنظمة تشفير عامة

إلى جانب الخوارزميات المخصصة، يمكن أيضاً توليد التوقيعات الرقمية باستخدام أنظمة تشفير غير متماثلة عامة مثل RSA.

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

تطبيقات تشفير المفتاح غير المتماثل

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

1. الاتصالات عبر الإنترنت: تعتمد الاتصالات الآمنة عبر الإنترنت، كـHTTPS، اعتماداً كبيراً على تشفير المفتاح غير المتماثل. تستخدم بروتوكولات أمان طبقة النقل (TLS) وسابقتها طبقة المقابس الآمنة (SSL) تشفير المفتاح غير المتماثل خلال عملية المصافحة الأولية لإنشاء مفتاح متماثل، يُستخدم بعدها في بقية جلسة الاتصال.

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

3. تشفير البريد الإلكتروني: تستخدم بروتوكولات تشفير البريد الإلكتروني مثل PGP (Pretty Good Privacy) وبديله مفتوح المصدر GPG (GNU Privacy Guard) تشفير المفتاح غير المتماثل لضمان أن المُستقبِل المقصود وحده هو من يستطيع قراءة محتوى البريد الإلكتروني.

4. الصدفة الآمنة (SSH): SSH هو بروتوكول لتسجيل الدخول عن بُعد بشكل آمن وتوفير خدمات شبكية آمنة أخرى عبر شبكة غير آمنة. يستخدم تشفير المفتاح غير المتماثل للمصادقة على الخادم أمام العميل، وبشكل اختياري على العميل أمام الخادم.

5. الشبكة الافتراضية الخاصة (VPN): يُستخدم تشفير المفتاح غير المتماثل لإنشاء اتصالات آمنة في شبكات VPN، مما يضمن اتصالاً آمناً عبر الشبكات العامة.

6. البلوك تشين والعملات المشفرة: تستخدم تقنيات البلوك تشين، بما في ذلك Bitcoin وEthereum، تشفير المفتاح غير المتماثل. على سبيل المثال، يُثبَت ملكية Bitcoin من خلال التوقيعات الرقمية باستخدام تشفير المفتاح غير المتماثل.

7. هيئات الشهادات: يستخدم تشفير المفتاح غير المتماثل من قِبَل هيئات الشهادات (CAs) لإصدار الشهادات الرقمية والتوقيع عليها، والتي تُستخدم في اتصالات TLS وتوقيع الأكواد البرمجية وتشفير البريد الإلكتروني وغيرها. تربط الشهادة الرقمية مفتاحاً عاماً بكيان محدد (شخص أو خادم مثلاً).

الشكل 5. إصدار الشهادات الرقمية والتوقيع عليها باستخدام تشفير المفتاح غير المتماثل

أمان تشفير المفتاح غير المتماثل

تتضافر عدة مفاهيم تشفيرية لتمكين تشفير المفتاح غير المتماثل الآمن، منها:

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

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

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

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

البروتوكول	أحجام المفاتيح النموذجية (بالبِت)	التطبيق
RSA	1024 (مهمل)، 2048، 3072، 4096	التشفير، التوقيعات الرقمية
DSA	1024 (مهمل)، 2048، 3072	التوقيعات الرقمية
DH	2048، 3072، 4096	تبادل المفاتيح
ECDH	224، 256، 384، 521	تبادل المفاتيح
ECDSA	224، 256، 384، 521	التوقيعات الرقمية

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

مخاطر أمنية تهدد تشفير المفتاح غير المتماثل

كما هو موضح في الجدول أعلاه، تعتمد خوارزميات المفتاح غير المتماثل الحديثة كـRSA عادةً على أحجام مفاتيح أكبر بكثير مقارنةً بنظيراتها من خوارزميات المفتاح المتماثل الشائعة كـAES-128. حتى البروتوكولات القائمة على ECC (ECDH وECDSA) ذات أحجام المفاتيح الأصغر تستخدم 224 بِت على الأقل. يستتبع ذلك أن هجوم القوة الغاشمة القائم على البحث المستفيض في فضاء المفاتيح الخاصة لتحديد المفتاح الصحيح يظل غير قابل للتنفيذ حسابياً في المستقبل المنظور، حتى لو وُظِّفت الحواسيب الكمومية لهذه المهمة. لذلك، تركز الهجمات على تشفير المفتاح غير المتماثل عادةً على استغلال نقاط ضعف محتملة أخرى في أنظمة تشفير بعينها. من أشهر أساليب الهجوم الموثقة تلك التي تستهدف:

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

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

3. عيوب التنفيذ كالأخطاء في تطبيق الخوارزميات التشفيرية التي تكشف عن معلومات حول المفاتيح بشكل غير مقصود. على سبيل المثال، قد يكشف الحشو الخاطئ عن تفاصيل المفاتيح.

4. القنوات الجانبية التي تشير إلى تسرب المعلومات من النظام المادي الذي ينفذ التشفير. قد يكون هذا التسرب على شكل معلومات توقيت أو استهلاك طاقة أو حتى صوت، وهو ما يمكن استغلاله في ما يُعرف بـهجوم القناة الجانبية. فعلى سبيل المثال، قد يكشف تحليل المدة التي تستغرقها العمليات التشفيرية عن عدد الـ'1' في مفتاح ثنائي. هذا التسرب الذي يبدو بريئاً يُضيِّق مساحة البحث بشكل ملحوظ، كاشفاً عن حلول محتملة لمسائل بدت في البداية شبه مستعصية.

5. تبادل المفاتيح عبر اعتراض المفاتيح أثناء تبادلها، كما في هجوم الوسيط (MITM). يكون بروتوكول DH عرضة لهجمات MITM إذا لم تُدمج خطوات مصادقة إضافية.

6. تخزين المفاتيح بهدف سرقة المفاتيح من مخزن غير محمي بشكل كافٍ. يشمل ذلك الهجمات المادية كالتلاعب بأجهزة التخزين أو سرقتها.

تأمين أنظمة تشفير المفتاح غير المتماثل ضد الأنواع المتعددة الممكنة من الهجمات يُشكِّل بالتالي مهمة ضخمة تنطوي على اعتبارات رياضية وعتادية وبرمجية ولوجستية وقانونية.

RSA

تُعدّ خوارزمية RSA (ريفيست-شامير-أدلمان) واحدة من أوائل أنظمة تشفير المفتاح العام وتُستخدم على نطاق واسع لنقل البيانات بأمان. وهي نظام تشفير متعدد الاستخدامات إذ توفر العمليات اللازمة لتمكين التشفير وفك التشفير والتوقيعات الرقمية وتبادل المفاتيح ضمن إطار موحد.

في هذا القسم، سنوضح تشفير المفتاح غير المتماثل (AKC) باستخدام RSA من خلال أمثلة بسيطة.

سنستخدم السيناريو القياسي لطرفين، أليس وبوب، يرغبان في التواصل بأمان باستخدام تشفير المفتاح غير المتماثل.

خوارزمية RSA

تشتمل خوارزمية RSA الأساسية على أربع عمليات: توليد المفاتيح، وتوزيع المفاتيح، والتشفير، وفك التشفير:

1. توليد المفاتيح:

   تُولَّد المفاتيح العامة والخاصة بناءً على مبادئ رياضية مرتبطة بالأعداد الأولية، حيث يسهل حسابها لكن يصعب عكسها.

   سنشير إلى:

   • المفتاح العام: $(e, n)$
   • المفتاح الخاص: $(d, n)$

   لاحظ أن $n$ مشترك بين المفتاحين العام والخاص ويُعرف بالمعامل (modulus)، وسنحتاج إليه لاحقاً.

التفاصيل الرياضية

• اختر عددين أوليين متمايزين $p$ و$q$.
  • يُختاران بشكل عشوائي (لأغراض أمنية).
  • ينبغي أن يتقاربا في الحجم لكن يختلفا في عدد الأرقام ببضعة أرقام لجعل التحليل إلى عوامل أصعب.
  • يمكن اختيار الأعداد الأولية بكفاءة باستخدام اختبار الأولية.
• احسب $n = p*q$.
  • $n$ هو المعامل لكلٍّ من المفتاحين العام والخاص.
• احسب توتينت $φ$$(n) = (p-1)*(q-1)$.
  • يُفترض أن يُحفَظ التوتينت سراً وعادةً ما يُتلَف بعد توليد المفاتيح.
• اختر عدداً صحيحاً $e$ بحيث $1 < e <$$φ$$(n)$ و$gcd$$(e,$$φ$$(n)) = 1$.
  • أي أن $e$ و$φ$$(n)$ يجب أن يكونا أوليَّين نسبياً.
  • يُشكِّل هذا العدد $e$ أسَّ المفتاح العام الأس ويُختار عادةً عدداً صغيراً لتحقيق الكفاءة الحسابية.
  • كثيراً ما يُستخدم العدد الأولي $65537 = 2^{16} + 1$.
  • احسب $d$ لتحقيق علاقة التطابق $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • أي أن $d$ هو المعكوس الضربي لـ$e$ بالنسبة المعيارية $φ$$(n)$.
    • يُحسب هذا بكفاءة أعلى باستخدام خوارزمية إقليدس الموسعة.
    • هذا العدد $d$ هو أسَّ المفتاح الخاص الأس.
• يتكوّن المفتاح العام من $(e, n)$، والمفتاح الخاص هو $(d, n)$.

2. توزيع المفاتيح:

   • يُعلَن المفتاح العام $(e, n)$ لمن يرغب في إرسال رسالة.
   • يُحفظ المفتاح الخاص $(d, n)$ سراً.

3. التشفير:

   • تريد أليس إرسال رسالة $M$ إلى بوب، وهي في هذه الحالة عدد صحيح بسيط.
   • تستخدم أليس المفتاح العام لبوب $(e, n)$ لتشفير الرسالة إلى نص مشفر $C$.

   التفاصيل الرياضية

   • $M$ هو عدد صحيح $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$، حيث $C$ هو النص المشفر.

4. فك التشفير:

   • يستلم بوب النص المشفر $C$.
   • يستخدم بوب مفتاحه الخاص $(d, n)$ لفك تشفير الرسالة واسترداد الرسالة الأصلية $M$.

   التفاصيل الرياضية

   • $M ≡ C^d (mod n)$.

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

توضيح خوارزمية RSA بلغة Python

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

ملاحظة

ملاحظة: في هذا القسم سنعرض الحسابات الرياضية بالتفصيل ضمن كود Python

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

لنتتبّع خطوة بخطوة مثالًا بسيطًا لخوارزمية RSA باستخدام أعداد أولية صغيرة.

سنحتاج إلى حساب القاسم المشترك الأكبر لعددين صحيحين، إذ يلزمنا للتحقق مما إذا كان العددان متباينَين.

سنشرح طريقة بسيطة لحساب ذلك، غير أن استخدام دالة Python math.gcd يكون أكثر كفاءة بكثير مع الأعداد الصحيحة الكبيرة.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

المرحلة الأولى في سير عمل RSA هي توليد المفاتيح. تبدأ بالاختيار من عددين أوليين، يُفترض أن تحتفظ بهما الجهة المولِّدة للمفاتيح سرًا.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

بعد ذلك، يُحسَب المعامل $n$، الذي هو ببساطة حاصل ضرب العددين الأوليين المختارَين. سيُنشَر هذا المعامل ضمن المفتاح العام.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

يُحسَب بعد ذلك دالة أويلر للتوتيينت $\varphi(n)$، لأنها ضرورية لعملية المعكوس الضربي المعياري المُستخدَمة لتحديد المفاتيح في RSA. وتُحفَظ قيمة $phi$ سرًا أيضًا وتُهمَل عادةً بعد توليد المفاتيح.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

أصبحنا الآن جاهزين لحساب المفتاحَين العام والخاص. في RSA، يُعبَّر عن كل منهما بزوج مرتّب من عددين صحيحين. العنصر الأول في كل زوج عدد صحيح مميز، أما الثاني فهو المعامل $n$ المشترك بين المفتاحَين.

العنصر الأول في المفتاح العام يمكن أن يكون أي عدد صحيح أكبر من 1 ومتباين مع $phi$. يكون عددان متباينَين إذا كان قاسمهما المشترك الأكبر هو 1. لذا نستخدم الدالة math.gcd لإيجاد عدد صحيح $e$ متباين مع $phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

يتطلب المفتاح الخاص عددًا صحيحًا $d$، وهو المعكوس الضربي للعدد $e$ بالنسبة للمعامل $phi$؛ أي يحقق علاقة التكافؤ $d*e\equiv 1 \pmod{\varphi(n)}$. في هذا التوضيح البسيط الذي يتعامل مع أعداد صغيرة، يمكننا المرور على الأعداد الصحيحة الموجبة للعثور على $d$ مناسب. أما في التطبيقات الواقعية، فيُستخدَم خوارزمية أوقليدس الموسّعة لهذا الغرض نظرًا لكفاءتها الحسابية.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

نُكوِّن الآن الزوجَين $(e, n)$ و$(d, n)$ اللذين يُمثّلان المفتاح العام والمفتاح الخاص على التوالي. يُنشَر المفتاح العام بعد ذلك، بينما يُحفَظ المفتاح الخاص سرًا.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

تعتمد عمليتا التشفير وفك التشفير في RSA على عملية الأس المعياري. فضلًا عن ذلك، المفتاحان العام والخاص متكاملان، إذ يمكن لأي منهما تشفير رسالة يستطيع الآخر فك تشفيرها.

نوضّح هنا الحالة التي يُستخدَم فيها المفتاح العام $(e,n)$ للتشفير والمفتاح الخاص $(d, n)$ لفك التشفير، من خلال تعريف دالة Python لكل عملية.

ثم نقوم بتشفير رسالة عددية صحيحة $msg$ ثم فك تشفيرها.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

رغم أن الأعداد الصغيرة المستخدمة أعلاه مفيدة لتوضيح الأفكار الجوهرية في خوارزمية RSA، إلا أن التطبيقات الفعلية تستلزم استخدام أعداد صحيحة كبيرة جدًا. فمثلًا، يستخدم RSA بمفتاح 2048 بت معاملًا $n$ بطول 2048 بت، وما يعادله من أعداد صحيحة عشرية يبلغ نحو 10$^{616}$. هذه الأعداد الضخمة حقًا ضرورية للأمان العملي لـRSA.

تبادل المفاتيح المتماثلة باستخدام RSA

كما نوقش سابقًا، يُتيح تشفير المفاتيح غير المتماثلة (AKC) لطرفَين يرغبان في التواصل إمكانية إنشاء سر مشترك بشكل آمن، يمكن استخدامه مثلًا مفتاحًا سريًا للتشفير المتماثل للنصوص العادية لاحقًا.

لنأخذ السيناريو التالي: تريد أليس وبوب استخدام تشفير المفاتيح المتماثلة (SKC) لتشفير الرسائل وفك تشفيرها. غير أنهما بحاجة قبل ذلك إلى الاتفاق على مفتاح سري مشترك. أحد الخيارات أن تقوم إحدى الجهتَين — أليس مثلًا — بتوليد مفتاح سري ثم إرساله بشكل آمن إلى بوب. ولتحقيق هذا النقل الآمن، تقرر أليس استخدام RSA بوصفه آلية تغليف المفاتيح (KEM).

تتضمن هذه العملية الخطوات التالية:

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

الشكل 1. تبادل المفاتيح المتماثلة باستخدام RSA

مثال عملي على تبادل المفاتيح بالحشو في Python

نوضّح الآن سير عمل عملي يستخدم RSA لتبادل مفاتيح غير تفاعلي قائم على الحشو، باستخدام مكتبة cryptography في Python.

نستورد الوحدات الضرورية من مكتبة cryptography في Python. عند الحاجة، يمكن تثبيت هذه المكتبة باستخدام الأمر pip install cryptography.

ثم تولّد أليس مفتاحًا سريًا عشوائيًا تنوي إرساله إلى بوب.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

باستخدام وحدة rsa من مكتبة cryptography، يولّد بوب زوج مفاتيح ثم يُذيع مفتاحه العام. يستطيع أي شخص اعتراض المفتاح العام وقراءة الأرقام العامة $(e,n)$ التي تشكّل المفتاح.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

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

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

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

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

في هذه المرحلة، تمتلك أليس وبوب كلاهما المفتاح المتماثل السري، ويمكنهما استخدامه في تطبيقات تشفير المفاتيح المتماثلة (SKC).

محاكاة آلية تغليف المفاتيح باستخدام RSA في Python

في سير العمل التالي، نوضّح استخدام RSA لمحاكاة آلية تغليف المفاتيح (KEM)، حيث يتم تبادل رسالة سرية عشوائية طويلة بشكل آمن ثم تحويلها إلى سر مشترك بالطول المناسب باستخدام دالة اشتقاق المفاتيح (KDF).

مرة أخرى، تريد أليس وبوب إنشاء سر مشترك بشكل غير تفاعلي، وأليس هي الجهة التي تحدد السر المُستخدَم.

نبدأ باستيراد بعض مكتبات Python الضرورية.

ثم يولّد بوب زوج مفاتيح RSA ويُذيع مفتاحه العام.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

تولّد أليس أولًا سرًا عشوائيًا طويلًا سيُشتَق منه السر المشترك في نهاية المطاف. في آلية KEM النقية، يكون السر الطويل عنصرًا عشوائيًا من البنية الجبرية الكامنة في منظومة التشفير. في حالة RSA بمفتاح 2048 بت، سيكون هذا عددًا صحيحًا عشوائيًا بالنسبة لمعامل RSA البالغ 2048 بت. بما أن آلية KEM النقية لا تستلزم حشوًا إضافيًا، إلا أننا في هذا المثال نحاكي فقط KEM باستخدام RSA، وتشترط مكتبة cryptography استخدام الحشو عند التشفير بـRSA. لذا سنستخدم سرًا طويلًا أقصر نسبيًا لكنه لا يزال أطول بكثير من مفتاح AES القياسي بـ256 بت.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

بعد ذلك تشفّر أليس السر الطويل باستخدام مفتاح بوب العام ويُرسَل السر المشفّر إلى بوب.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

يفك بوب تشفير السر المشفّر الذي تلقّاه من أليس باستخدام مفتاحه الخاص.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

أخيرًا، تطبّق كل من أليس وبوب بشكل مستقل دالة اشتقاق مفاتيح (KDF) متفقًا عليها على السر الطويل لاشتقاق المفتاح المتماثل.

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

لذا سنفترض أن كلًا من أليس وبوب لديهما إمكانية الوصول إلى نفس الملح العشوائي.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

التوقيعات الرقمية باستخدام RSA

سنُوسّع الآن سيناريو التواصل السري بين أليس وبوب ليشمل التحقق بمساعدة التوقيع الرقمي.

كما في السابق، ستُرسل أليس إلى بوب رسالة تحوي مفتاحًا متماثلًا بشكل سري، لكنها ستوقّع الرسالة رقميًا أيضًا حتى يستطيع بوب عند استلامها التحقق من أن أليس هي من أرسلها وأن محتواها لم يُعبَث به أثناء الإرسال.

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

سنأخذ هذه الحالة العامة التي تتضمن الخطوات التالية:

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

الشكل 2. التوقيعات الرقمية باستخدام RSA

يُوضَح سير العمل هذا للتوقيع الرقمي في الجزء التالي.

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

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

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

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

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

1. إنشاء قيمة تجزئة للنص المشفّر باستخدام خوارزمية تجزئة.
2. تشفير قيمة التجزئة باستخدام المفتاح الخاص لأليس، مما يُشكّل التوقيع.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

تُذيع أليس بعد ذلك النص المشفّر والتوقيع عبر الشبكة ليتمكن بوب من استلامهما.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

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

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

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

في كود Python أدناه، تُدمَج هذه العمليات في دالة مساعدة مفيدة تُسمّى verify توفّرها كائن مرتبط بالمفتاح العام لأليس.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

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

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

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

من خلال تمكين التوزيع الآمن للمفاتيح ودعم عدم الإنكار، يُرسي تشفير المفاتيح العامة أساسًا متينًا للتواصل الرقمي الآمن.

كسر تشفير RSA

تستند فائدة خوارزمية RSA وأمانها إلى افتراضين رياضيين:

1. إيجاد المعكوس الضربي المعياري $d$ عند توفر $(e, n)$ فحسب يُعدّ أمرًا غير قابل للتنفيذ حسابيًا.

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

الهجوم الأبرز على خوارزمية RSA يهدف إلى إسقاط الافتراض الأول عبر استرداد رقم المفتاح الخاص $d$ بكفاءة من خلال تحليل المعامل $n$ إلى عوامله الأولية. كما سيتضح أدناه، يسهل استرداد $d$ إذا توفر الوصول إلى العوامل الأولية $p$ و$q$ لـ$n$، أو إلى الدالة أويلر $φ$$(n)$. تذكر أن $p$ و$q$ و$φ$$(n)$ تُحفظ سرية أثناء توليد المفاتيح وتُتلف بعد ذلك. أي طرف ثالث يتمكن من استرداد هذه المعلومات باستخدام حاسوب كلاسيكي أو كمي يكون قد كشف المفتاح الخاص عمليًا، وبالتالي كسر تشفير RSA. وهكذا، يُعدّ تحليل الأعداد إلى عواملها الأولية العملية الحسابية الجوهرية اللازمة لكسر RSA.

الحوسبة الكلاسيكية وRSA

من المعروف أن تحليل الأعداد الصحيحة الكبيرة إلى عواملها الأولية يُظهر تعقيدًا فوق كثير الحدود أو دون الأسي على الحواسيب الكلاسيكية. أفضل خوارزمية كلاسيكية معروفة لتحليل الأعداد الصحيحة الأكبر من $10^{100}$ هي المنخل العام لحقل الأعداد (GNFS)

التفاصيل الرياضية

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

بوصفها دالة للعدد الصحيح $n$ المراد تحليله إلى عوامل أولية.

هذا التعقيد فوق كثير الحدود من حيث عدد البتات اللازمة لتمثيل $n$.

لذلك، يُعدّ تحليل الأعداد إلى عواملها الأولية غير فعّال على الحواسيب الكلاسيكية.

في الوقت الحالي، تتراوح أكبر الأعداد الصحيحة المحلَّلة على العتاد الكلاسيكي في نطاق 829 بت أو 250 رقمًا عشريًا. نظرًا للنمو الأسي الذي شهدته قدرات الحوسبة الكلاسيكية على مدار العقود الماضية، لم يعد RSA بطول 1024 بت آمنًا على المدى القريب وأُهمل الآن. ومع ذلك، يُعدّ تحليل الأعداد الصحيحة ذات 2048 بت التي تتراوح في نطاق $10^{617}$ أمرًا غير قابل للتنفيذ على الأنظمة الكلاسيكية في المستقبل المنظور، مما يُبقي على جدواها. غير أن ظهور الحواسيب الكمية يُلغي هذا التقييم.

خوارزمية شور الكمية وRSA

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

تستطيع خوارزمية شور تحليل الأعداد الأولية بتعقيد $O(n^2)$ حيث $n$ هو عدد البتات.

الشرح الرياضي لخوارزمية شور

في سياق RSA، تعمل خوارزمية شور باستغلال دورية دالة الأسس المعيارية $f(x) = a^x (mod~n)$، وتوفر أداة كمية لإيجاد الدورة تُمكّن من تحليل المعامل $n$ إلى عواملها الأولية بكفاءة.

فيما يلي مخطط عالي المستوى مبسّط لمنهجية شور الإجمالية لكسر RSA:

1. بمعرفة المعامل $n$ المنشور كجزء من المفتاح العام، اختر عددًا $a$ أوليًا نسبيًا مع $n$، أي $gcd(a,n) = 1$. بما أننا نعلم أن $n = p*q$ يملك بالضبط عاملين أوليين $(p, q)$، فإن أي عدد نختاره عشوائيًا أقل من $n$ يُرجَّح أن يكون أوليًا نسبيًا مع $n$.

2. بعد اختيار $a$، أوجد الأس $r$ بحيث يكون $a^r \equiv 1 (mod~n)$. هذا يعني $a^r - 1 \equiv 0 (mod~n)$. وجود أس $r$ يحقق هذه التطابق مضمون بـخاصية الدورية لـالأسس المعيارية.

3. إذا كان $r$ زوجيًا، فإن $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ لعدد صحيح $\gamma$ ما. يجب أن يحتوي الطرف الأيسر من هذه المعادلة الأخيرة على $p$ و$q$ كعاملين أوليين له بما أن الطرف الأيمن كذلك. إذا كان $r$ فرديًا، عُد إلى الخطوة 1 وجرّب قيمة مختلفة لـ$a$.

4. استخدم خوارزمية أوقليدس الموسعة لإيجاد $gcd((a^{r/2} - 1), n)$ أو $gcd((a^{r/2} + 1), n)$. يُرجَّح أن يُحدد القاسم المشترك الأكبر المحسوب أحد العاملين الأوليين $p$ أو $q$. اقسم $n$ على هذا العامل الأولي لاستعادة الآخر.

5. بمعرفة $p, q$، استخدم خطوات خوارزمية RSA الأصلية لإعادة بناء الدالة $\phi(n)$ وتوليد رقم المفتاح الخاص $d$ بوصفه المعكوس المعياري لرقم المفتاح العام المعروف $e$.

في أغسطس 2023 نشر Oded Regev تحسينًا على خوارزمية شور الأصلية باستخدام منهج متعدد الأبعاد، مما أسفر عن تعقيد $O(n^{1.5})$. لا تزال هناك أبحاث جارية في هذا المجال، من بينها أبحاث Ragavan وVaikuntanathan، التي قد تُحسّن الزمن أو التكلفة أو عدد الكيوبتات اللازمة. بينما لا يمكننا الجزم بموعد أن يصبح تشغيل مثل هذه الخوارزميات على تشفير RSA الحقيقي أمرًا ممكنًا فعليًا، فإن ذلك يقترب باستمرار.

مثال بايثون يوضح كسر تشفير RSA

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

ملاحظة

في هذا القسم سنعرض الحسابات الرياضية بالتفصيل كجزء من كود بايثون

في المثال، لدينا مفتاح عام $(5, 247)$، وسنقوم باسترداد المفتاح الخاص.

الخطوة 1: أول خطوة هي اختيار عدد أولي نسبيًا مع 247. تقريبًا أي عدد نخمّنه سيؤدي الغرض. لنختر 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

الخطوة 2: بعد ذلك نحتاج إلى إيجاد الدورة $r$ بحيث تكون $6^r \equiv 1 (mod~247)$. في هذا المثال، نحسب $r$ كلاسيكيًا بالقوة الغاشمة، لكن يمكننا أيضًا استخدام خوارزمية شور على حاسوب كمي باستخدام Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

الخطوة 3: بما أن الدورة $r = 36$ زوجية، يمكننا حساب $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

الخطوة 4: أوجد القاسم المشترك الأكبر لأيٍّ من تلك العوامل مع $n$. اقسم ببساطة $n$ على العامل الأولي الذي وجدته للحصول على العامل الأولي الثاني.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

الخطوة 5: بعد استرداد العاملين الأوليين لـ$n = 247$ وهما $p_{found}=13$ و$q_{found}=19$، نحسب الدالة $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

المفتاح الخاص هو المعكوس المعياري لرقم المفتاح العام $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

في المخطط أعلاه، الخطوة 2 هي عملية إيجاد الدورة الحاسمة التي تستخدم فيها خوارزمية شور أداتين كميتين أساسيتين، وهما تحويل فورييه الكمي وتقدير الطور الكمي. للاطلاع على شرح تفصيلي للجوانب الكمية في خوارزمية شور، راجع درس تقدير الطور والتحليل الأولي في أساسيات الخوارزميات الكمية. الخطوات 1 و3 إلى 5 تتضمن عمليات رخيصة نسبيًا يمكن إجراؤها بسهولة على الحواسيب الكلاسيكية.

اختياريًا، إليك شرح مرئي تفصيلي لتطبيق خوارزمية شور.

على الحواسيب الكمية، يمكن لخوارزمية شور أن تُظهر تعقيدًا لوغاريتميًا متعدد الحدود مواتيًا بقدر $O((log~n)^2 (log~log~n))$ من حيث المعامل $n$، أو تعقيدًا كثير الحدود من حيث عدد البتات اللازمة لتمثيل $n$. وهذا تسريع فوق كثير الحدود مقارنةً بـخوارزمية GNFS الكلاسيكية.

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

تبادل مفاتيح ديفي-هيلمان وخوارزمية التوقيع الرقمي

في القسم السابق، ناقشنا نظام تشفير RSA الذي يعتمد أمانه على الصعوبة الحسابية لتحليل الأعداد إلى عواملها الأولية. هنا، سنناقش بروتوكولَين تشفيريَّين شائعَين بالمفتاح غير المتماثل، هما تبادل مفاتيح ديفي-هيلمان (DH) وخوارزمية التوقيع الرقمي (DSA)، وكلاهما يقوم على مسألة رياضية مختلفة، وهي مسألة اللوغاريتم المتقطع (DLP).

مسألة اللوغاريتم المتقطع

في المعادلة التالية نحتاج إلى إيجاد $a$ بمعرفة $e$ و$M$ و$c$ فحسب

$a^e$ $mod$ $M = c$

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

يُعرف هذا بـمسألة اللوغاريتم المتقطع (DLP).

التفاصيل الرياضية لمسألة اللوغاريتم المتقطع

تُصاغ مسألة DLP عادةً في سياق المجموعات الدورية وتُعبَّر عنها كما يلي.

لتكن مجموعة دورية $G$ مولَّدة بعنصر $g \in G$، وبمعرفة عنصر اعتباطي $h \in G$، أوجد عددًا صحيحًا $k$ بحيث يكون $h = g^{k}$.

هنا العدد الصحيح $k \equiv log_{g}h$ هو اللوغاريتم المتقطع. تضمن الخاصية الدورية لـ$G$ وجود عدد صحيح $k$ صالح لكل $h$.

لأغراض التشفير، تبيّن أن مسألة DLP على المجموعة الضربية للأعداد الصحيحة معيارية عدد أولي $p$ المُرمَّز بـ$(\mathbb{Z}_p)^{\times}$ مفيدة. عناصر $(\mathbb{Z}_p)^{\times}$ هي فئات التطابق المُسمَّاة بأعداد صحيحة معيارية $p$ تكون أولية نسبيًا مع $p$.

مثلًا:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

عملية الضرب $(\times)$ على هذه المجموعات هي ببساطة ضرب الأعداد الصحيحة العادي متبوعًا بالاختزال معيارية $p$، والرفع لأس $k$ هو مجرد ضرب متكرر $k$ مرة واختزال معياري $p$.

لنوضح مثالًا على مسألة DLP على $(\mathbb{Z}_7)^{\times}$.

هذه المجموعة الضربية لها مولّدان ${[3],[5]}$ يُعرفان أيضًا بالجذور الأولية. سنستخدم $[5]$ كمولّد؛ أي نولّد كل عنصر من عناصر $(\mathbb{Z}_7)^{\times}$ باستخدام القوى الصحيحة المتتالية لـ5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

نرى أنه في حساب معياري 7، رفع 5 لقوى صحيحة متتالية يُنتج كل عنصر من عناصر $(\mathbb{Z}_7)^{\times}$ مرة واحدة تمامًا قبل أن تتكرر الدورة إلى ما لا نهاية بفترة $p-1 =6$.

إذن مسألة DLP على $(\mathbb{Z}_7)^{\times}$ بالمولّد [5] هي:

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$.

من خرج خلية بايثون أعلاه نرى أن:

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

في حساب الأعداد الحقيقية العادية، الأسّ دالة رتيبة ويسهل حسابيًا إيجاد لوغاريتم أي عدد لأي أساس. في المقابل، كما يتضح من مثال $(\mathbb{Z}_7)^{\times}$ البسيط أعلاه، الأسّ المعياري غير رتيب، وعلى الرغم من دوريته بفترة $p-1$، إلا أنه بالغ التعقيد في غير ذلك. لذلك يبيّن أن حساب معكوسه، اللوغاريتم المتقطع، أمر غير فعّال للـ$p$ الكبيرة على الحواسيب الكلاسيكية.

هذه الملاحظة تدعم كلًّا من تبادل مفاتيح ديفي-هيلمان (DH) وخوارزمية التوقيع الرقمي (DSA) اللذين تناقشهما الفقرة التالية.

يمكن توسيع مسألة DLP لتشمل المجموعات الفرعية الدورية كما يلي:

• لتكن $(\mathbb{Z}_p)^{\times}$ معرَّفة أعلاه وعنصر $g \in (\mathbb{Z}_p)^{\times}$ ذو رتبة أولية $r$، أي $g^r \equiv 1 (~mod~p)$.
• مجموعة القوى الصحيحة لـ$g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ هي مجموعة فرعية دورية من $(\mathbb{Z}_p)^{\times}$ برتبة مجموعة $r$.
• يمكن صياغة مسألة DLP على $\langle g \rangle$ باختيار $h \in \\langle g \rangle$ والبحث عن $1 \le a \le r$ بحيث يكون $g^a~(mod~p) = h$

تبادل مفاتيح ديفي-هيلمان

في عام 1976، اقترح ويتفيلد ديفي ومارتن هيلمان بروتوكول تبادل مفاتيح لتمكين إنشاء مفتاح سري مشترك عبر قنوات اتصال غير آمنة. يمكن عندئذٍ للأطراف المشاركة في المفتاح استخدامه للتشفير المتماثل. تعتمد الخوارزمية على مسألة DLP.

الشكل 1. تبادل مفاتيح ديفي-هيلمان

التفاصيل الرياضية لتبادل مفاتيح ديفي-هيلمان

مع كون أليس وبوب الطرفين المتواصلَين، يعمل البروتوكول كما يلي:

• أولًا، تتفق أليس وبوب على عدد أولي كبير $p$ وجذر أولي أو مولّد $a$.
• ثم تختار أليس أسًّا سريًا $k_A$ عشوائيًا بحيث يكون $1 \le k_A \le p-2$ وتحسب $h_A = a^{k_A}~(mod~p)$. $k_A, h_A$ هما المفتاح الخاص والعام لأليس على التوالي.
• بعد ذلك يختار بوب أسًّا سريًا $k_B$ عشوائيًا بحيث يكون $1 \le k_B \le p-2$ ويحسب $h_B = a^{k_B}~(mod~p)$. $k_B, h_B$ هما المفتاح الخاص والعام لبوب على التوالي.
• ثم ترسل أليس لبوب $h_A$ ويرسل بوب لأليس $h_B$ عبر قناة موثوقة وليس بالضرورة آمنة.
• ثم تستخدم أليس الـ$h_B$ التي تلقّتها لحساب المفتاح السري المشترك $\kappa = h_B^{k_A}~(mod~p)$.
• أخيرًا، يستخدم بوب الـ$h_A$ التي تلقّاها لحساب المفتاح السري المشترك $\kappa = h_A^{k_B}~(mod~p)$.

بهذا البروتوكول،

• يُضمن أن تنتهي أليس وبوب بنفس المفتاح السري $\kappa$ لأن $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• طرف ثالث يعترض $h_A$ أو $h_B$ لا يستطيع بناء المفتاح السري $\kappa$ لأنه لا يملك الوصول إلى $k_B$ أو $k_A$ على التوالي.
• استخلاص $k_A$ أو $k_B$ باستخدام المعلومات العامة $a$ و$p$ و$h_A$ و$h_B$ أمر صعب حسابيًا لأنه مكافئ لحل مسألة DLP على $(\mathbb{Z}_p)^{\times}$.

توضيح بروتوكول ديفي-هيلمان بالبايثون

لنلقِ نظرة على مثال بسيط لبروتوكول DH بالبايثون باستخدام أعداد أولية صغيرة:

ملاحظة

في هذا القسم سنعرض الحسابات الرياضية بالتفصيل كجزء من كود بايثون

الخطوة 1: تتفق أليس وبوب على عدد أولي $p$ وجذر أولي $a$. لنختر $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

الخطوتان 2 و3: تختار أليس أسًّا سريًا $k_A$ وتحسب $h_A = a^{k_A}~(mod~p)$. وبالمثل، يختار بوب أسًّا سريًا $k_B$ ويحسب $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

الخطوة 4: يُذيع الطرفان مفاتيحهما العامة $h_A$ و$h_B$.

الخطوتان 5 و6: يجمع كل طرف مفتاحه الخاص مع المفتاح العام للطرف الآخر لإنشاء المفتاح السري المشترك.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

يمكن لأليس وبوب الآن استخدام المفتاح السري المشترك للتشفير المتماثل.

أمان تبادل مفاتيح ديفي-هيلمان

كما أُشير أعلاه، يعتمد أمان DH على صعوبة حل مسألة DLP مع أعداد أولية كبيرة $p$. في التطبيقات النموذجية، توصي NIST باستخدام أعداد أولية بطول 2048 أو 3072 بت لتبادل مفاتيح DH، وهو ما يُعدّ آمنًا بما يكفي ضد محاولات حل مسألة DLP باستخدام الحواسيب الكلاسيكية.

هجمات الرجل في المنتصف (MITM): حقيقة أن DH مخطط تفاعلي حيث يعتمد المفتاح السري المشترك على دمج المفتاح الخاص لطرف مع المفتاح العام للطرف الآخر تجعله عرضة لما يُسمى بـهجوم الرجل في المنتصف (MITM).

التفاصيل الرياضية لأمان DH وهجمات MITM

في هذا السيناريو، يعترض طرف ثالث — لنقل إيف — المفاتيح العامة $h_A, h_B$ أثناء الإرسال ويُحل محل كل من $h_A$ و$h_B$ مفتاحها العام $h_E$ قبل إعادة توجيهها إلى بوب وأليس على التوالي.

عندئذٍ، بدلًا من استخدام $h_B$ لإنشاء سرها المشترك، ستستخدم أليس $h_E$ معتقدةً أنها تستخدم المفتاح العام لبوب. وبالمثل، بدلًا من استخدام $h_A$ لإنشاء سره المشترك، سيستخدم بوب $h_E$ معتقدًا أنه يستخدم المفتاح العام لأليس.

لأن $h_E$ قد استُخدم لإنشاء السر المشترك لأليس (بوب)، يمكن لإيف فك تشفير النص المشفَّر من قِبل أليس (بوب).

وهكذا، يُستخدم تبادل مفاتيح DH عادةً جنبًا إلى جنب مع خوارزمية توقيع رقمي لضمان استخدام كل طرف مفتاحًا عامًا موثَّقًا لإنشاء سره المشترك.

خوارزمية التوقيع الرقمي (DSA)

على الرغم من أن أنظمة التشفير العامة مثل RSA توفر وظيفة التوقيع الرقمي، اعتمدت NIST عام 1994 مخططًا متخصصًا للتوقيع يعتمد على الأسس المعيارية ومسألة اللوغاريتم المتقطع بوصفه المعيار الفيدرالي للتوقيعات الرقمية. يتضمن هذا المخطط، الذي أصبح يُعرف ببساطة بـخوارزمية التوقيع الرقمي (DSA)، أربع مراحل متمايزة:

1. توليد المفاتيح:

   تُولَّد مفاتيح DSA من:

   • عددين أوليين يستوفيان قواعد معينة
     • $p$ - عادةً 256 بت (سنسمي هذا الطول $N$)
     • $q$ - عادةً 3072 بت (سنسمي هذا الطول $L$)
   • دالة تجزئة تشفيرية تحوّل من سلاسل بطول $L$ إلى $N$
   • معامل إضافي $g$ (انظر التفاصيل أدناه)

   من هذا نختار عددًا عشوائيًا $x$ كمفتاح خاص، ويمكننا حساب مفتاح عام $y$

   التفاصيل الرياضية لتوليد المفاتيح

   • توليد المعاملات: رياضيًا، تتضمن DSA مجموعة فرعية دورية من $(\mathbb{Z}_p)^{\times}$ مولَّدة بعنصر $g$ ذي رتبة أولية q < p. الخطوة الأولى في DSA إذن هي اختيار عددين أوليين p وq لإعداد البنى الرياضية اللازمة.

     • اختر عددًا أوليًا $q$ بطول $N$ بت.
     • اختر عددًا أوليًا $p$ بطول $L$ بت بحيث يكون $p-1$ مضاعفًا لـ$q$. اختيار $p$ يحدد المجموعة $(\mathbb{Z}_p)^{\times}$
     • اختر عددًا صحيحًا $1 < h < p-1$ عشوائيًا واحسب $g = h^{(p-1)/q}~mod~p$. إذا كانت $g=1$ وهو نادر الحدوث، جرّب $h$ آخر.
     • تحقق من أن $g^q~mod~p = 1$. وبذلك $g$ مولّد للمجموعة الفرعية الدورية $\langle g \rangle$ من $(\mathbb{Z}_p)^{\times}$ ذات الرتبة الأولية q.

     المعاملات $(q, p, g)$ تحدد نسخة من الخوارزمية وهي معلومات عامة. عادةً $N \sim 256$ و$L \sim 3072$ في التطبيقات الواقعية.

     يتطلب البروتوكول أيضًا دالة تجزئة تشفيرية $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ تُعيّن سلاسل ثنائية بطول $L$ بت إلى سلاسل بطول $N$ بت، مثل SHA-256.

   • توليد زوج المفاتيح: يحتاج الموقِّع إلى توليد زوج مفاتيح من جانبه.

     • اختر عددًا صحيحًا سريًا عشوائيًا $x \in \{1,2...q-1\}$. $x$ هو المفتاح الخاص.
     • احسب $y = g^{x}~mod~p$. $y$ هو المفتاح العام للموقِّع.

2. توزيع المفاتيح:

   تُشارَك المعلومات التالية مع أي شخص يرغب في التحقق من التوقيع

   • المعاملات المستخدمة $(p,q,g)$ التي تصف الخوارزمية
   • دالة التجزئة $H$
   • المفتاح العام $y$

3. التوقيع:

   • يستطيع الموقِّع الآن توقيع رسالة $m$. التوقيع الناتج هو $(r,s)$
   • تُرسل الرسالة والتوقيع كلاهما إلى المستلم

   التفاصيل الرياضية لتوقيع رسالة

   يوقّع الموقِّع رسالة $m$ كما يلي:

   • اختر عددًا صحيحًا سريًا k عشوائيًا من $\{1,2...q-1\}$
   • احسب $r = (g^k~mod~p)~mod~q$. في الحالة النادرة التي يكون فيها $r=0$، جرّب k عشوائيًا آخر.
   • احسب $s = (k^{-1} (H(m) + xr))~mod~q$. في الحالات النادرة إذا كانت $s=0$، جرّب k عشوائيًا آخر.
   • التوقيع هو الثنائي $(r, s)$.
   • يرسل الموقِّع الرسالة $m$ والتوقيع $(r,s)$ إلى المتحقق.

   لأن كلًّا من $r, s$ عددان صحيحان معيارية $q$، يكون حجم التوقيع في نطاق $N$ بت وليس $L$ بت الأطول.

4. التحقق:

   يرغب المستلم الآن في التحقق من هوية المرسل. لديه الوصول إلى المعلومات العامة $(q, p, g, H, y, (r,s), m)$ يمكنه تنفيذ حساب يُثبت أن المرسل لديه الوصول إلى المفتاح الخاص $x$

   ويسعى إلى التحقق من أن الموقِّع هو شخص لديه الوصول إلى المفتاح الخاص $x$.

   التفاصيل الرياضية لمخطط التحقق في DSA

   • تحقق من أن $0 \lt r \lt q$ و$0 \lt s \lt q$، أي أن $r, s$ أعداد صحيحة صالحة معيارية~q.
   • احسب $w = s^{-1}~mod~q$.
   • احسب $u_1 = H(m)w~mod~q$.
   • احسب $u_2 = rw~mod~q$.
   • احسب $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • يُتحقق من التوقيع إذا كانت $v = r$.

   لأجل التوقيعات الشرعية، يمكن إثبات صحة خوارزمية DSA بسهولة كما يلي:

   • من جانب الموقِّع: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • بالنظر إلى الطرف الأيمن من هذه المعادلة الأخيرة، يمكن للمتحقق حساب $s^{-1}, H(m)$ لأن $s, q, m, H$ معلومات عامة.
   • وهكذا يحسب المتحقق $w = s^{-1}~mod~q$ و$u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • يحسب المتحقق أيضًا $u_2 = rw~mod~q = rs^{-1}~mod~q$ إذ إن $r$ عام أيضًا.
   • لاحظ أن $k = (u_1 + xu_2)~mod~q$.
   • غير أن المتحقق لا يملك الوصول إلى $x$ لأنه المفتاح الخاص للموقِّع، لذا لا يمكن حساب $k$ مباشرةً. يعتمد المخطط بدلًا من ذلك على حقيقة أنه حتى لو لم يستطع المتحقق حساب $k$، فإنه مع موقِّع شرعي ينبغي للمتحقق أن يتمكن من إعادة حساب $(g^k~mod~p)~mod~q = r$ بمساعدة المفتاح العام للموقِّع $y = g^{x}~mod~p$.
   • إذن يحسب المتحقق $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • تتبع المساواة الأخيرة من كون $g$ ذا رتبة $q$ وتُثبت أن $v = r$ للتوقيعات الصالحة.

توضيح خوارزمية DSA بلغة Python

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

ملاحظة

يمكنك تجربة إعادة تشغيل هذا المثال بقيم مختلفة لمشاهدة سلوك الخوارزمية، لكن تأكد من البدء بتشغيل الخلية الأولى في هذا القسم.

نبدأ باستيراد المكتبات اللازمة واختيار المعاملات. المعاملات الصحيحة $p$ و$q$ و$g$ هي معلومات عامة، وتستوفي الشروط التالية:

• $p$، $q$ كلاهما عددان أوليان
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

بعد ذلك، تُنشئ الموقِّعة أليس مفتاحها الخاص.

يجب أن يستوفي المفتاح الخاص k (المسمى alice-private-key في كود Python) الشرطين التاليين:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

تحتفظ أليس بمفتاحها الخاص طيّ الكتمان.

بعد ذلك، تحسب أليس مفتاحها العام باستخدام الأس المعياري. إن عكس هذه الخطوة لاسترداد المفتاح الخاص هو مسألة من مسائل DLP، وهو أمر يصعب حسابه على الحاسبات الكلاسيكية حين تُستخدم أعداد أولية كبيرة.

من الشرح الرياضي أعلاه، نعلم أن هذا يمكن حسابه باستخدام المعادلة:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

كالمعتاد، تُتيح أليس مفتاحها العام عبر قناة لا يُشترط أن تكون سرية.

الآن يمكن لأليس توقيع رسالة.

لمخطط التوقيع الرقمي، نحتاج إلى توليد دالة تجزئة $H(m)$ للرسالة $m$ المُراد توقيعها.

لنفترض أن أليس وبوب يتفقان على استخدام خوارزمية تجزئة معينة بطول تجزئة $N$ يساوي عدد البتات في $q$. في هذا المثال البسيط، سنحصر مخرجات دالة التجزئة الوهمية لدينا بحدود $q$. دالة التجزئة هنا بسيطة للغاية، إذ تقوم فقط بتوليد عدد صحيح عشوائي.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

بعد ذلك، تحتاج أليس إلى توليد رقم سري عشوائي $k$ لكل رسالة على حدة، فضلاً عن معكوسه الضربي بالنسبة المعيارية للـ $q$ لحساب التوقيع.

يمكن استخدام خوارزمية بسيطة بالقوة الغاشمة لحساب المعكوس المعياري، غير أن الأفضل هو استخدام الدالة المدمجة في Python وهي pow كما هو موضح أدناه.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

يمكن لأليس الآن حساب التوقيع.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

لاحظ أن ثمة شروطاً معينة ستستلزم منا اختيار قيمة مختلفة لـ $k$ في حال أسفر حساب إما $r$ أو $s$ عن الصفر. في هذه الحالة سنُولّد قيمة جديدة ونكرر العملية.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

تُذيع أليس الرسالة وتوقيعها إلى المُستقبِل أو المُحقِّق بوب.

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

للقيام بذلك، يُجري بعض الفحوصات، ثم يعيد توليد دالة تجزئة لرسالة أليس المذاعة ويحسب الكميات المساعدة $w$ و$u_1$ و$u_2$ و$v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

أخيراً، يتحقق بوب مما إذا كانت $v$ تساوي $r$. إن تساويا، فقد تم التحقق من التوقيع.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

أمان خوارزمية DSA

على صعيد الحوسبة الكلاسيكية، يتأثر أمان خوارزمية DSA بعدة عوامل:

1. حجم المفتاح: كما هو الحال دائماً، يوفر حجم المفتاح الحماية الأساسية ضد هجمات القوة الغاشمة. تستخدم التطبيقات الحديثة التي تعتمد DSA أحجام مفاتيح لا تقل عن 2048 بت.

2. جودة $k$: في خوارزمية DSA، يحتاج كل توقيع إلى قيمة $k$ فريدة وعشوائية وسرية (انظر أعلاه). تُعدّ فرادة $k$ وعشوائيتها وسريتها أموراً بالغة الأهمية، وأي ضعف في أيٍّ من هذه الجوانب قد يؤدي إلى الكشف عن المفتاح الخاص $x$. لذلك يجب أن تكون مولدات الأرقام العشوائية المستخدمة في توليد $k$ آمنةً بحد ذاتها.

3. قوة دالة التجزئة: نظراً لاستخدام خوارزمية DSA لدالة تجزئة ضمن عملية توليد التوقيع والتحقق منه، فإن ضعف دالة التجزئة قد يُخلّ بأمان التوقيع الرقمي. على سبيل المثال، استخدام SHA-1 مع DSA بات مهجوراً ويُوصى باستخدام SHA-2 أو ما يعلوه.

علاوة على ما سبق، ينبغي لأي تطبيق قوي لخوارزمية DSA أن يتصدى أيضاً لأنواع أخرى من الهجمات التي تستهدف التشفير بالمفتاح غير المتماثل كما سبق توضيحه.

تبادل المفاتيح الموثّق بدمج Diffie-Hellman و DSA

تتضمن بروتوكولات أمان الشبكات الحديثة، كـ Transport Layer Security (TLS) وغيرها الكثير، الجمع بين وظيفتي تبادل المفاتيح والمصادقة. وفي سياق Diffie-Hellman، تُعدّ المصادقة ضرورية للحماية من هجمات MITM. في خلايا الكود التالية، نُوضّح مثالاً تُجري فيه أليس وبوب تبادلاً موثّقاً للمفاتيح بدمج بروتوكولَي Diffie-Hellman وDSA، وسنستخدم لذلك مكتبة cryptography في Python.

الشكل 2. تبادل المفاتيح الموثّق بدمج Diffie-Hellman وDSA

أولاً، تتفق أليس وبوب على مجموعة من معاملات DH ويُولّدان أزواج مفاتيح عامة-خاصة وفق بروتوكول DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

تُذاع مفاتيح DH العامة. بعد ذلك، يُولّد كل من أليس وبوب زوجاً منفصلاً من المفاتيح لاستخدامه مع DSA. ستُوظَّف هذه المفاتيح بدورها لتوقيع مفاتيح DH العامة المُراد تبادلها.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

تُوقّع أليس مفتاح DH العام الخاص بها باستخدام مفتاحها الخاص في DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

بالمثل، يُوقّع بوب مفتاح DH العام الخاص به باستخدام مفتاحه الخاص في DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

تُذاع مفاتيح DH العامة والتوقيعات المقابلة لها من قِبَل أليس وبوب. وعند استلام كل طرف المفتاح العام والتوقيع الخاص بالطرف الآخر، يتحقق كل منهما من صحة التوقيع. بهذه الطريقة يمكن منع هجمات MITM، إذ تعلم أليس مثلاً أن مفتاح DH العام الخاص ببوب قد وقّعه بوب فعلاً، والعكس صحيح.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

عقب التحقق من التوقيعات، تُولّد أليس وبوب السر المشترك، مما يُكمل عملية تبادل المفاتيح.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

اختياريًا، ولمزيد من الأمان، يمكن لأليس وبوب استخدام دالة اشتقاق مفاتيح متخصصة كـ HKDF لتوليد مفتاح تماثلي أكثر أماناً من سرّهما المشترك باستخدام تقنيات key stretching.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

كسر Diffie-Hellman و DSA

يعتمد بروتوكولا Diffie-Hellman (DH) وDSA على توليد مفاتيح عامة بالصيغة $y = g^{x}~mod~p$، حيث يكون المفتاح الخاص $x$ هو اللوغاريتم المنفصل.

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

في أنظمة الحوسبة الكلاسيكية، يُعتقد أن مسألة DLP لا تمتلك حلًا بوقت متعدد الحدود. لكن كما أثبت Peter Shor في ورقته الأصلية عام 1994، فإن خوارزمية Shor تحل مسألة DLP أيضًا بوقت متعدد الحدود على أجهزة الحاسوب الكمومية.

خوارزمية Shor ومسألة اللوغاريتم المنفصل

خوارزمية Shor قادرة على حل مسألة اللوغاريتم المنفصل في وقت متعدد الحدود. تحقق هذه الكفاءة بشكل رئيسي باستخدام خوارزميات كمومية قادرة على إيجاد دورية دالة تعتمد على مدخل المسألة — ثم يُدمج ذلك مع عمليات أكثر تقليدية.

التفاصيل الرياضية لخوارزمية Shor

توفر خوارزمية Shor حلًا فعّالًا لمسألة DLP عبر إرجاعها إلى مسألة أكثر عمومية في نظرية المجموعات تُعرف بـمسألة المجموعة الجزئية المخفية (HSP).

في مسألة HSP، يُعطى مجموعة جبرية $G$ ودالة $f: G \rightarrow X$ من $G$ إلى مجموعة ما $X$ بحيث تكون $f$ ثابتة على كل مصفوفة جانبية لمجموعة جزئية $H$ من $G$ (ومختلفة على المصفوفات الجانبية المختلفة). والمطلوب هو تحديد $H$. ومن المعروف أن الحواسيب الكمومية تستطيع حل مسألة HSP على المجموعات الأبيلية المنتهية في وقت متعدد الحدود في $log~|G|$ حيث $|G|$ هو رتبة المجموعة.

في حالة مسألة DLP الصحيحة التي نناقشها في هذا الدرس، يكون التعيين إلى مسألة HSP على النحو التالي:

• ليكن $p$ عددًا أوليًا، وننظر في مسألة DLP المعطاة بـ $y = g^r~mod~p$ حيث $g$ مولّد لـ $(\mathbb{Z}_p)^{\times}$. نظرًا لأن $g^{p-1} \equiv 1~mod~p$، فإن $g$ لها رتبة $p-1$.
• اختر $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ حيث $\mathbb{Z}_{p-1}$ هي مجموعة الأعداد الصحيحة modulo $(p-1)$.
• اختر $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ المعرّفة بـ $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$.
• نواة $f$ هي إذن المجموعة الجزئية $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ ثابتة على المصفوفات الجانبية $(\delta, 0) + H_0$ و"تُخفي" المجموعة الجزئية $H_0$ مما يُنشئ مسألة HSP.

بناءً على ما سبق، تستخدم خوارزمية Shor الكمومية لمسألة DLP الصحيحة أوراكلًا كموميًا لتقييم الدالة $f$ على حالة تمثل تراكبًا منتظمًا على $G$، ثم تستخدم تحويل فورييه الكمومي والقياسات مع تقدير الطور لإنتاج حالات كمومية تُتيح تحديد المولّد $(r, 1)$ لـ $H_0$. ومن ذلك يمكن استخراج $r$، وهو اللوغاريتم المنفصل المطلوب.

الورقة الأصلية لـ Shor تحتوي على وصف تفصيلي للخوارزمية.

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

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

المبادئ الأساسية لتشفير المنحنى الإهليلجي

المنحنى الإهليلجي يكون عادةً بالصيغة $y^2 = x^3 + ax + b$ وله بعض الخصائص المثيرة للاهتمام.

• إنه متماثل أفقيًا. لذا فإن أي نقطة $(x,y)$ على المنحنى، انعكاسها $(x,-y)$ يكون أيضًا على المنحنى
• أي خط مستقيم غير عمودي لن يتقاطع مع المنحنى في أكثر من ثلاث نقاط

الشكل 1. عمليتا الجمع ومضاعفة النقطة على منحنى إهليلجي. الوجه 1 يُعرّف P + Q = -R. الوجه 2 يوضح مضاعفة النقطة 2Q = -P. الوجه 3 يُعرّف المعكوس الجمعي لنقطة بوصفه انعكاسها حول المحور الأفقي، أي P = -Q

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

المبادئ الرياضية لتشفير المنحنى الإهليلجي

المنحنى الإهليلجي فوق حقل جبري $K$ يُعرَّف بمعادلة رياضية، عادةً بالصيغة $y^2 = x^3 + ax + b$ مع المعاملات $a, b \in K$ ويصف نقاطًا $(x, y) \in K \otimes K$ مع اشتراط إضافي بأن يكون المنحنى خاليًا من التشابكات والتقاطعات الذاتية.

خصائص المنحنيات الإهليلجية تسمح بتعريف عمليتي "الجمع" و"الضرب القياسي" على النقاط الواقعة على المنحنى.

الجمع: إذا كانت $P$ و$Q$ نقطتين على منحنى إهليلجي، فإن $P + Q$ تصف نقطة ثالثة وحيدة تُحدَّد كالتالي: ارسم الخط الذي يمر بـ $P$ و$Q$ وأوجد النقطة الثالثة $R$ التي يتقاطع عندها الخط مع المنحنى مجددًا. نُعرّف حينئذ $P + Q = −R$، وهي النقطة المقابلة لـ $R$ المنعكسة عبر المحور $x$ (انظر الشكل أدناه). حين لا يتقاطع الخط المار بـ $P, Q$ مع المنحنى عند أي $(x, y)$ منتهية، نقول إنه يتقاطع مع المنحنى عند نقطة اللانهاية $\mathbf{O}$.

جمع المنحنى الإهليلجي يستوفي خصائص المجموعة الجبرية مع نقطة اللانهاية بوصفها المحايد الجمعي.

المضاعفة والضرب القياسي: عملية مضاعفة النقطة التي تقابل الضرب القياسي في $2$ تُحصل بضبط $P = Q$ في عملية الجمع وتشمل بيانيًا خط المماس عند $P$. الضرب القياسي العام بعدد صحيح $n$ المعرّف كـ $nP = P + P + ...~n$ مرة يُحصل عبر التضعيف والجمع المتكرر.

مسألة اللوغاريتم المنفصل على المنحنى الإهليلجي

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

عملية الضرب القياسي على المنحنيات الإهليلجية تُتيح تعريف مسألة اللوغاريتم المنفصل على المنحنى الإهليلجي:

بمعلومية نقطتين $P, Q$ على منحنى إهليلجي بحيث $Q = nP$، أوجد $n$.

تُعدّ هذه المسألة غير قابلة للحل على الحاسوب الكلاسيكي للقيم الكبيرة من $n$ وتشكّل أساسًا للأمان التشفيري.

الوصف الرياضي لمسألة ECDLP

يقوم تشفير المنحنى الإهليلجي أساسًا على مسألة ECDLP المصاغة على حقول منتهية جبرية معينة. في عام 1999، أوصت NIST بعشرة حقول منتهية للاستخدام في ECC. وهي:

• خمسة حقول أولية $\mathbb {F} _{p}$ للأعداد الأولية $p$ بأحجام $\{192, 224, 256, 384, 521\}$ بت.
• خمسة حقول ثنائية $\mathbb {F} _{2^{n}}$ لـ $n \in \{163, 233, 283, 409, 571\}$.

بهذه الإعدادات، يمكن تحديد نظام تشفير بمفتاح غير متماثل مبني على ECC في حالة الحقول الأولية على النحو التالي:

• اختر $p$ من قائمة القيم الموصى بها من NIST لتحديد $\mathbb {F} _{p}$.

• حدد المعاملات $a, b$ للمنحنى الإهليلجي.

• اختر نقطة أساسية $G$ "تولّد" مجموعة جزئية دورية على المنحنى ذات رتبة $n$؛ أي أصغر عدد صحيح بحيث $nG = \mathbf{O}$.

• احسب المعامل الثانوي $h = |E(\mathbb {F} _{p})|/n$ حيث $|E(\mathbb {F} _{p})|$ هو عدد النقاط على المنحنى. $h$ عادةً عدد صحيح صغير.

• معاملات النطاق $(p, a, b, G, n, h)$ تُتيح تحديد المفاتيح غير المتماثلة على هذا النحو:

  • المفتاح الخاص هو عدد صحيح $d$ مختار عشوائيًا بعدد بتات مساوٍ للعدد الأولي $p$. ينبغي الحفاظ على سريته.
  • المفتاح العام هو نتيجة "ضرب" النقطة الأساسية $G$ في المفتاح الخاص $d$. ويُرمز له عادةً بـ $Q = dG$.

استرداد $d$ يكافئ حل مسألة ECDLP، التي يُفترض أنها غير قابلة للحل للقيم الكبيرة من $d$. لذا تشكّل ECDLP الأساس لبروتوكولات تبادل المفاتيح والتوقيعات الرقمية بالتماثل المباشر مع بروتوكولي Diffie-Hellman وDSA المعرّفين على $(\mathbb{Z}_p)^{\times}$ اللذين ناقشناهما سابقًا.

تبادل المفاتيح باستخدام ECC

أحد الاستخدامات الرئيسية لـ ECC هو بروتوكول تبادل المفاتيح المعروف بـDiffie-Hellman على المنحنى الإهليلجي (ECDH). في ECDH، يُولّد كل طرف زوج مفاتيح خاص-عام ثم يتبادل المفاتيح العامة. يستخدم كل طرف حينئذٍ مفتاحه الخاص ومفتاح الطرف الآخر العام لحساب سر مشترك يمكن استخدامه مفتاحًا للتشفير المتماثل.

بينما يسهل نسبيًا إجراء جمع النقاط على منحنى إهليلجي واشتقاق مفتاح عام من مفتاح خاص، فإن عكس هذه العملية واشتقاق المفتاح الخاص من المفتاح العام أمر غير ممكن حسابيًا. هذا السلوك "الأحادي الاتجاه" هو ما يوفر أمان تبادل مفاتيح ECDH.

هنا سنوضح مثالًا على كيفية إجراء تبادل مفاتيح ECDH باستخدام Python ومكتبة cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

التوقيعات الرقمية باستخدام ECC

يمكن أيضًا استخدام ECC لتوليد توقيعات رقمية عبر خوارزمية التوقيع الرقمي على المنحنى الإهليلجي (ECDSA). في ECDSA، ينشئ الموقّع توقيعًا باستخدام مفتاحه الخاص، ويمكن للآخرين التحقق من التوقيع باستخدام مفتاحه العام. تمامًا كما في ECDH، يعتمد أمان ECDSA على مسألة ECDLP. فتزوير توقيع دون الوصول إلى المفتاح الخاص للموقّع أمر غير ممكن حسابيًا.

فيما يلي مثال على عملية بسيطة للتوقيع والتحقق باستخدام ECDSA مع Python وcryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

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

كسر ECDH و ECDSA

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

الملخص

في هذا الدرس، بدأنا بالنظر في الخصائص الرئيسية لتشفير المفتاح غير المتماثل (AKC) وناقشنا اعتبارات الأمان الأساسية التي تدعم الأنظمة التشفيرية غير المتماثلة. وبشكل خاص، قدّمنا التطبيقين الرئيسيين لـ AKC — وهما تبادل المفاتيح والتوقيعات الرقمية — وكلاهما مكوّن أساسي في الاتصالات الحديثة عبر الإنترنت.

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

ثم تناولنا تبادل مفاتيح Diffie-Hellman (DH) وخوارزمية التوقيع الرقمي (DSA). يستند أمان هذه البروتوكولات إلى مسألة اللوغاريتم المنفصل الصحيح (DLP)، حيث يصعب حسابيًا استخراج المفتاح الخاص من المفتاح العام دون حل متعدد الحدود على الحاسوب الكلاسيكي. يُضفي استخدام مفاتيح عشوائية وفريدة أمانًا إضافيًا ضد الهجمات. يجد كلا متغيري الحقل المنتهي الصحيح والمنحنى الإهليلجي لبروتوكولي DH وDSA استخدامًا واسعًا حاليًا في كثير من بروتوكولات الاتصالات الرقمية الحديثة مثل TLS، وSSH، وغيرها.

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

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