العشوائية والعشوائية الزائفة

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

Definition

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

Scope

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

Core questions

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

Key concepts

• الإنتروبيا والعشوائية الحقيقية
• مولدات الأرقام العشوائية
• المولد العشوائي الزائف (PRG)
• الدالة العشوائية الزائفة (PRF)
• التبديل العشوائي الزائف (PRP)
• عدم القدرة على التمييز حسابياً
• البذرة واشتقاق المفتاح
• إخفاقات إعادة استخدام العشوائية
• تهيئة الإنتروبيا

Key theories

المولدات العشوائية الزائفة

يقوم المولد العشوائي الزائف بتوسيع بذرة قصيرة إلى سلسلة أطول لا يمكن تمييزها عن العشوائية المنتظمة لأي مميز فعال؛ توجد هذه المولدات إذا وفقط إذا كانت الدوال أحادية الاتجاه موجودة، مما يربط العشوائية الزائفة بأسس التشفير.

الدوال والتبديلات العشوائية الزائفة

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

Mechanisms

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

Clinical relevance

تُعد إخفاقات العشوائية مصدراً متكرراً للاختراقات الكارثية في العالم الحقيقي: أدت ثغرة Debian OpenSSL عام 2008 إلى تعطيل توليد المفاتيح، وأدت القيم العشوائية (nonces) المتوقعة في ECDSA إلى تسريب المفاتيح الخاصة (Sony PlayStation 3، بعض محافظ Bitcoin)، وأنتجت الإنتروبيا الضعيفة للأجهزة المدمجة مفاتيح قابلة للتخمين على نطاق واسع. لذا، فإن العشوائية القوية — جمع الإنتروبيا المناسب ومولدات الأرقام العشوائية الزائفة المعتمدة — ضرورية لكل عملية نشر تشفيرية.

Evidence & guidelines

تحدد NIST SP 800-90A/B/C مولدات البتات العشوائية الحتمية المعتمدة، والتحقق من صحة مصدر الإنتروبيا، وإرشادات البناء. تستخدم أفضل الممارسات مولد الأرقام العشوائية التشفيري المعتمد لنظام التشغيل (بدلاً من إنشاء واحد خاص)، وتضمن وجود إنتروبيا كافية قبل توليد المفاتيح، ولا تعيد استخدام القيم العشوائية (nonces) أبداً. تساعد مجموعات الاختبارات الإحصائية في الكشف عن العيوب الجسيمة ولكنها لا تستطيع إثبات القوة التشفيرية.

History

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

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

لماذا لا يمكنني استخدام دالة عشوائية عادية مثل rand() للتشفير؟

تُبنى مولدات الأرقام العشوائية العادية من أجل التوحيد الإحصائي والسرعة، وليس عدم القدرة على التنبؤ؛ يمكن التنبؤ بمخرجاتها من بضع عينات. يحتاج التشفير إلى مولدات يكون من المستحيل التنبؤ بمخرجاتها المستقبلية حتى بالنظر إلى المخرجات السابقة، وهذا يتطلب مولد أرقام عشوائية آمن تشفيرياً ومُبذر بإنتروبيا حقيقية.

ما الفرق بين العشوائية الحقيقية والعشوائية الزائفة؟

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