احتمالية تصادم التجزئة

خطوات الاستخدام

أدخل عدد بتات التجزئة (hashBits): هذا يمثل طول مخرجات دالة التجزئة بالبت، مثل 256 بت لخوارزمية SHA-256. كلما زاد عدد البتات، زاد عدد القيم الممكنة (2^hashBits) وبالتالي انخفض احتمال التصادم. يجب إدخال قيمة صحيحة موجبة.

أدخل عدد الرسائل (messages): يمثل عدد العناصر أو الرسائل التي سيتم تجزئتها. كلما زاد عدد الرسائل، زاد احتمال التصادم. يمكن أن يكون أي عدد صحيح موجب.

تقوم الحاسبة بحساب احتمال حدوث تصادم واحد على الأقل باستخدام مفارقة عيد الميلاد. الصيغة المستخدمة هي: P ≈ 1 - e^(-n² / (2 * 2^b)) حيث n = عدد الرسائل، b = عدد بتات التجزئة. هذه تقريبية دقيقة عندما يكون n أصغر بكثير من 2^(b/2).

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

الأسئلة الشائعة

مفارقة عيد الميلاد هي مفارقة احتمالية تنص على أنه في مجموعة من 23 شخصاً، يكون احتمال أن يتشارك اثنان على الأقل في نفس تاريخ ميلاد أكبر من 50%. هذا يثير الدهشة لأن عدد التواريخ الممكنة هو 365، أي أن العدد المتوقع من الأشخاص لتكرار عيد ميلاد هو √365 ≈ 19، وليس 183 (نصف 365). في سياق التجزئة، عدد القيم الممكنة هو 2^b (حيث b عدد البتات). لذلك، فإن عدد الرسائل المطلوبة لتحقيق احتمال 50% للتصادم هو تقريباً 2^(b/2). على سبيل المثال، لـ SHA-256 (b=256)، عدد الرسائل المطلوب هو حوالي 2^128، وهو رقم ضخم. هذا هو أساس أمان التجزئة: مقاومة التصادم تعتمد على حجم نصف طول المخرجات. لذا، فإن أي دالة تجزئة آمنة يجب أن تتطلب حوالي 2^(b/2) عملية للعثور على تصادم.

في التوقيعات الرقمية، يتم توقيع قيمة التجزئة للوثيقة بدلاً من الوثيقة نفسها. إذا تمكن المهاجم من إيجاد تصادم بين وثيقتين مختلفتين (أي تجزئة متطابقة)، فيمكنه خداع الموقع للاعتقاد بأنه وقع على وثيقة بريئة بينما هو في الواقع يوقع على وثيقة ضارة. لذلك، يجب أن يكون عدد البتات كبيراً بما يكفي لجعل إيجاد التصادم غير ممكن حسابياً. على سبيل المثال، يعتبر SHA-256 حالياً آمناً حيث أن 2^128 عملية مستحيلة عملياً. في الماضي، استخدم SHA-1 (160 بت) لكن مع تقدم القوة الحاسوبية، أصبح من الممكن إيجاد تصادمات فيه (تم إثبات تصادم عملي لـ SHA-1 في 2017). لذلك، يوصى باستخدام SHA-256 أو SHA-3 وما فوق.

نعم، الحاسبة تستخدم نموذج الدالة العشوائية (Random Oracle Model) حيث تفترض أن دالة التجزئة توزع المخرجات بشكل منتظم ومستقل. في الواقع، دوال التجزئة الحقيقية (مثل SHA-256) مصممة لتكون قريبة جداً من هذا المثالية، ولكن قد توجد نقاط ضعف بنيوية تقلل من الأمان الفعلي. على سبيل المثال، تم العثور على ثغرات عملية في MD5 وSHA-1 تجعل إيجاد التصادم أسهل بكثير مما تشير إليه الصيغة النظرية. لذلك، تستخدم الحاسبة أفضل تقدير نظري، لكن الأمان الفعلي قد يكون أقل إذا كانت الدالة ضعيفة. عند اختيار دالة تجزئة، يجب الاعتماد على معايير حديثة وآمنة.

مقاومة التصادم تعني أنه من الصعب حسابياً العثور على أي رسالتين مختلفتين لهما نفس التجزئة. وهذا ما تحسبه الحاسبة. أما مقاومة الصورة الأولى فتعني أنه إذا أعطينا قيمة تجزئة محددة، فمن الصعب العثور على أي رسالة تنتج تلك التجزئة. مقاومة التصادم أضعف: إن وجد هجوم تصادم، فقد لا يساعد في إيجاد الصورة الأولى. لكن في التطبيقات مثل التوقيعات الرقمية، كلا الخاصيتين ضروريتان. عادةً، لتحقيق مقاومة تصادم عند مستوى أمان k بت، يجب أن يكون طول التجزئة 2k بت (مبدأ عيد الميلاد). بينما لمقاومة الصورة الأولى، يكفي k بت. لذا، SHA-256 توفر 128 بت أمان ضد التصادم و256 بت ضد الصورة الأولى.

احتمالية تصادم التجزئة

أدخل القيم

خطوات الاستخدام

أمثلة محلولة

أمثلة محسوبة

الأسئلة الشائعة

أدخل القيم

خطوات الاستخدام

1إذا كنت تستخدم SHA-256 (256 بت) ولديك مليون رسالة، ما هو احتمال التصادم؟

2ماذا عن SHA-1 (160 بت) مع 2^32 رسالة (حوالي 4.3 مليار)؟

أمثلة محسوبة

الأسئلة الشائعة