خطوات الاستخدام
أدخل عدد بتات التجزئة (hashBits): هذا يمثل طول مخرجات دالة التجزئة بالبت، مثل 256 بت لخوارزمية SHA-256. كلما زاد عدد البتات، زاد عدد القيم الممكنة (2^hashBits) وبالتالي انخفض احتمال التصادم. يجب إدخال قيمة صحيحة موجبة.
أدخل عدد الرسائل (messages): يمثل عدد العناصر أو الرسائل التي سيتم تجزئتها. كلما زاد عدد الرسائل، زاد احتمال التصادم. يمكن أن يكون أي عدد صحيح موجب.
تقوم الحاسبة بحساب احتمال حدوث تصادم واحد على الأقل باستخدام مفارقة عيد الميلاد. الصيغة الدقيقة المستخدمة هي: P = 1 − e^(−x) حيث x = n(n−1) ÷ 2^(b+1)، وهي نفس 1 − e^(−n²/(2·2^b)) المعروفة عند تجاهل −n مقارنة بـ n². تُحسب النتيجة بصيغة عددية مستقرة (−expm1(−x)) لأن الحساب المباشر 1 − e^(−x) يعطي صفرًا تامًا في الأرقام المزدوجة كلما كانت x أصغر من نحو 10⁻¹⁶ — وهو حال SHA-256 مع مليون رسالة حيث x ≈ 4.3×10⁻⁶⁶ كانت تُطبع 0% بلا أي معلومة. هذه التقريبية دقيقة عندما يكون n أصغر بكثير من 2^(b/2).
الناتج يظهر احتمال التصادم كنسبة مئوية مقربة إلى منزلتين عشريتين. لكن النسبة المئوية وحدها لا تُظهر شيئًا للاحتمالات الفلكية الصغر (فـ 4.3×10⁻⁶⁶ تظهر 0.00%)، لذلك تعرض التفاصيل أربع قيم بالصيغة العلمية: الاحتمال نفسه، والأس x، وحجم فضاء التجزئة 2^b، وعدد الرسائل اللازم لبلوغ احتمال 50% تقريبًا وهو 2^(b/2) كما يشرح السؤال الأول. فإذا كانت النسبة 50% فمعناها فرصة متوسطة لحدوث تصادم واحد على الأقل في هذه المجموعة من الرسائل.
أمثلة محلولة
تطبيقات عملية على احتمالية تصادم التجزئة بخطوات الحل كاملة.
الحل
نقوم بإدخال hashBits = 256 و messages = 1,000,000. نحسب 2^256 = 1.1579e77. ثم n(n−1) = 1,000,000 × 999,999 = 9.99999e11. إذن x = n(n−1) ÷ (2 × 2^b) = 9.99999e11 ÷ 2.3158e77 ≈ 4.318e-66. وبما أن الأس متناهي الصغر فإن e^(−x) ≈ 1 − x أي P ≈ 4.318e-66؛ تنبيه: لو حُسبت 1 − e^(−x) مباشرة بالأرقام المزدوجة لخرجت 0 تمامًا، لذلك تستخدم الحاسبة الدالة المستقرة expm1. الاحتمال ضئيل للغاية (تقريبًا صفر)، ويظل كذلك حتى مع مليار رسالة حيث x ≈ 4.318e-60. هذا يظهر أن SHA-256 آمن جدًا ضد التصادم.
الحل
نحسب 2^160 ≈ 1.4615e48. و n = 2^32 = 4.295e9، فمن n(n−1) ≈ 2^64 = 1.8447e19 نحصل على x = 1.8447e19 ÷ (2 × 1.4615e48) ≈ 6.311e-30. إذن P ≈ 6.311e-30، وهو أيضًا ضئيل. ولكن في الواقع، SHA-1 يعاني من ثغرات عملية تقلل من أمانه، بينما الحاسبة تفترض توزيعًا مثاليًا (نموذج العرّاف العشوائي). وإذا استخدمت 2^80 رسالة (أي 1.209e24) فقد صار x = (2^80)² ÷ 2^161 = 0.5 بالضبط، أي P = 1 − e^(−0.5) = 0.3935 أي 39.35%. ولبلوغ 50% يلزم x = ln 2 ≈ 0.693 أي n ≈ 1.18 × 2^80؛ فالترتيب هو 2^80 نفسه، وهذا سبب اعتبار SHA-1 غير آمن: مقاومته للتصادم نصف طول المخرجات لا أكثر.
أمثلة محسوبة
قيم مُدخَلة ونتيجة محسوبة فعليًا بواسطة احتمالية تصادم التجزئة.
مرجع — SHA-256 مع مليون رسالة: 4.318e-66
- بتات التجزئة (1-1000)
- 256
- عدد الرسائل
- 1,000,000
مرجع — SHA-1 عند 2^80 رسالة: 39.35%
- بتات التجزئة (1-1000)
- 160
- عدد الرسائل
- 1,208,925,819,614,629,200,000,000
مرجع — 77 ألف رسالة في 32 بت: 49.85%
- بتات التجزئة (1-1000)
- 32
- عدد الرسائل
- 77,000
مرجع — تجزئة 8 بت ضعيفة: 81.72%
- بتات التجزئة (1-1000)
- 8
- عدد الرسائل
- 30