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

حجم التجزئة	128
عدد العناصر	1,000,000

حجم التجزئة

128

عدد العناصر

1,000,000

آخر تحديث: 2026-06-23

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

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

مفارقة عيد الميلاد

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

الصيغة

لدالة تجزئة ناتجها $b$ بتاً، يضمُّ فضاء البحث $2^b$ قيمة متساوية الاحتمال. بافتراض تجزئة $n$ عنصراً بشكل عشوائي، احتمالية التصادم الدقيقة هي مكمِّل احتمال اختلاف جميع النواتج الـ $n$ :

p = 1 - \prod_{k=0}^{n-1}\left(1 - \frac{k}{2^b}\right)

لقيم $2^b$ الكبيرة و $n$ المعتدلة، يُعطي تقريب عيد الميلاد صيغةً مغلقة أبسط:

p \approx 1 - e^{-n^2 / (2 \cdot 2^b)}

وحل المعادلة لإيجاد عدد العناصر عند بلوغ الاحتمالية 50٪:

n_{50\%} = \sqrt{2 \cdot 2^b \cdot \ln 2}

مثال توضيحي

لتجزئة 32 بت (كـ CRC32 المستخدمة في مجاميع التحقق):

\begin{aligned} n_{50\%} &= \sqrt{2 \times 2^{32} \times \ln 2} \\ &= \sqrt{2 \times 4{,}294{,}967{,}296 \times 0.6931} \\ &\approx \sqrt{5{,}954{,}124{,}768} \\ &\approx 77{,}163 \end{aligned}

مع 77,163 ملفاً في مستودع ما، ثمة احتمالية تبلغ نحو 50٪ أن يتشارك اثنان منها نفس تجزئة CRC32 المؤلفة من 32 بت. التحقق بصيغة التقريب:

p = 1 - e^{-77163^2 / (2 \times 2^{32})} \approx 1 - e^{-0.693} \approx 0.50

وهذا هو السبب في أن CRC32 غير مناسب كمُعرِّف فريد في المجموعات الكبيرة، رغم كونه رمزاً ممتازاً لاكتشاف الأخطاء في التدفقات البيانية الصغيرة.

الانعكاسات الأمنية

يُرسي حد عيد الميلاد حقيقةً مفادها أن دالة تجزئة بـ $b$ بت لا توفر إلا $\lfloor b/2 \rfloor$ بتاً من مقاومة التصادم. يحتاج المهاجم إلى نحو $2^{b/2}$ تقييم تجزئي للعثور على تصادم — لا $2^b$ . ولهذا تُصمَّم دوال التجزئة التشفيرية بنواتج أطول من مستوى الأمان المستهدف:

دالة التجزئة	حجم الناتج	مقاومة التصادم
MD5	128 بت	~ $2^{64}$ (مكسورة عملياً)
SHA-1	160 بت	~ $2^{80}$ (مكسورة عملياً)
SHA-256	256 بت	~ $2^{128}$ (المعيار الحالي)
SHA-3-512	512 بت	~ $2^{256}$ (أمان عالٍ)

يُوصف MD5 وSHA-1 بأنهما "مكسورتان" ليس فقط بسبب حد عيد الميلاد، بل لأن الباحثين اكتشفوا ثغرات خوارزمية تُوجد التصادمات بكفاءة أعلى بكثير مما يتنبأ به هذا الحد. تصادمات MD5 يمكن الآن حسابها على حواسب شائعة خلال دقائق باستخدام أساليب منشورة.

للاطلاع على تحليل مرتبط بفضاءات البحث في كلمات المرور، انظر حاسبة إنتروبيا كلمة المرور.

الأسئلة الشائعة (FAQ)

ما مفارقة عيد الميلاد في التشفير؟

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

ينطبق المنطق ذاته على دوال التجزئة: لا يحتاج المهاجم سوى نحو √(2^b) = 2^(b/2) عنصراً مُجزَّأً للوصول إلى احتمالية 50٪ للعثور على اثنين بنفس الناتج. هذا هو هجوم عيد الميلاد. لتجزئة 128 بت كـ MD5، يبلغ هذا الحد نحو 2^64 ≈ 1.8 × 10¹⁹ عنصراً — أقل بكثير من 2^128 توليفة التي يستلزمها هجوم صورة مسبقة.

لماذا يتطلب هجوم عيد الميلاد نصف بتات التجزئة فحسب لكسرها؟

يجب على هجوم الصورة المسبقة إيجاد ناتج تجزئة محدد، فيستلزم البحث في كامل فضاء 2^b. أما هجوم عيد الميلاد فلا يحتاج سوى اثنين من المدخلات يتشاركان الناتج ذاته، وبحكم حد عيد الميلاد تتجاوز احتمالية الإيجاد 50٪ بعد نحو 2^(b/2) عينة.

لذلك تُصمَّم دوال التجزئة التشفيرية بضعف عدد بتات الناتج مقارنةً بمستوى الأمان المستهدف: تجزئة 256 بت توفر مقاومة تصادم تعادل 128 بت.

لماذا تُعدُّ خوارزميتا MD5 وSHA-1 غير آمنتين؟

تعرضت كل من MD5 (128 بت) وSHA-1 (160 بت) للكسر بهجمات تصادم عملية — ليس فقط هجمات احتمالية قائمة على حد عيد الميلاد، بل ثغرات خوارزمية تُوجد التصادمات بكفاءة أعلى بكثير مما يتنبأ به هذا الحد. عام 2004 أثبت باحثون تصادمات MD5؛ وعام 2017 أنتج مشروع SHAttered من Google أول تصادم لـ SHA-1 معروف علناً.

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

ما الفرق بين التصادم والصورة المسبقة؟

التصادم يعني إيجاد مدخلين متمايزين x وy يُعطيان نفس ناتج التجزئة: hash(x) = hash(y). الصورة المسبقة تعني إيجاد مدخل x يُنتج ناتج تجزئة مستهدفاً h — وهو أصعب لأنك لا تستطيع اختيار المدخلين بحرية. الصورة المسبقة الثانية تعني إيجاد مدخل مختلف y يحمل التجزئة ذاتها لـ x معروف.

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

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

المدخلات

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

معاملات التجزئة

احتمالية التصادم

تضمين هذه الآلة الحاسبة

مشاركة هذه العملية الحسابية

التالي الموصى به

حاسبة إنتروبيا كلمة المرور

حاسبة الشبكات الفرعية (CIDR)

هل كانت هذه الحاسبة مفيدة؟

لا، تحتاج إلى تحسين

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

المدخلات

المدخلات

معاملات التجزئة

النتائج

احتمالية التصادم

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

مفارقة عيد الميلاد

الصيغة

مثال توضيحي

الانعكاسات الأمنية

الأسئلة الشائعة (FAQ)

التالي الموصى به

حاسبة إنتروبيا كلمة المرور

حاسبة الشبكات الفرعية (CIDR)

هل كانت هذه الحاسبة مفيدة؟