مقدمة

لنفترض أنني أسألك عن عدد الأشخاص الذين يجب أن يكونوا في غرفة حتى يكون لدى اثنين منهم عيد ميلاد مع احتمال 50 ٪ ليوم واحد. ماذا سيكون الجواب؟ هذا هو ما يسمى مفارقة عيد ميلاد.

المفارقة تقول:

إذا كان هناك 23 شخصًا في الغرفة ، فقد ولد اثنان منهم في نفس اليوم بنسبة 50٪.

بعض إصدارات المفارقة تجعل بيانات أقوى:

إذا كانت الغرفة تحتوي على 70 شخصًا ، مع احتمال 99 ٪ ، ولد اثنان منهم في نفس اليوم.

في البداية ، بدا لي هذا مفاجئًا وبديهيًا. دعنا نعرف لماذا هذا صحيح. لتبسيط المهمة ، نقوم بعمل الافتراضات التالية:

1. نحن نفترض أن جميع الناس في الغرفة لم يولدوا في سنة كبيسة. نفترض هذا الافتراض حتى لا نضطر لتحليل حالتين مختلفتين.
2. لا توجد توائم في الغرفة. مع زوج من التوائم ، فإن الحل سيكون تافها.
3. نحن نفترض أن الناس يولدون بالتساوي والعشوائية. ماذا يعني هذا؟ يحتمل أن يولد الناس في أي يوم من أيام السنة. إذا تم إضفاء الطابع الرسمي على هذا قليلاً ، فإن احتمال الولادة في أي يوم يتم اختياره يساوي $$$\ frac {1} {365}$ .
4. يولد الناس بشكل مستقل عن بعضهم البعض. هذا يعني أن تاريخ ميلاد أي شخص لا يؤثر على تاريخ ميلاد شخص آخر.

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

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

تخيل أن هناك شخص واحد في الغرفة ، ثم احتمال عيد ميلاده المشترك مع شخص آخر هو 0. هيا $$$(A_n)$ ستكون النتيجة التي بين $$$ن$ الناس ليس لديهم عيد ميلاد واحد. سمح $$$\ Pr [A_n]$ - احتمال أن بين $$$ن$ من الناس في الغرفة ، كل شخص لديه عيد ميلاد في يومهم. وبالمثل ، اسمحوا $$$\ overline {A_n}$ سيكون مكملا $$$A_n$ ، أي نتيجة فيها $$$ن$ الناس شخصين لديهم نفس عيد الميلاد.

$$

$$\ Pr [A_n] + \ Pr [\ overline {A_n}] = 1$$

$$

$$\ Pr [A_1] = 1 \ text {لأنه يوجد شخص واحد فقط في الغرفة}$$

لنفترض أن هناك شخصين في الغرفة ، A و B. دون فقدان التعميم ، فقط تخيل أن الشخص A قد ولد في 1 يناير. لكي يكون لـ B و A أعياد ميلاد مختلفة ، يجب أن يولد B في أي يوم باستثناء 1 يناير. الشخص ب سيكون لديه 364 خيار عيد ميلاد.

$$

$$\ Pr [A_2] = \ Pr [\ text {B مختلف عن A}] = \ frac {364} {365}$$

تخيل أن هناك ثلاثة أشخاص في الغرفة ، أ ، ب ، ج. لنفترض أن الشخص أ قد وُلد في 1 يناير ، بحيث وُلدوا جميعهم في أيام مختلفة ، وكان الشخص ب 364 يومًا فقط ، كما في المثال السابق. نظرًا لأن A و B يستغرق يومين ، لا يمكن أن يولد الشخص C إلا في 365 - 2 = 363 يومًا.

$$

$$\ Pr [A_3] = \ Pr [\ text {B مختلف A و C مختلف عن B ، A}] = \ frac {364} {365} \ times \ frac {363} {365}$$

يحدث شيء أكثر إثارة للاهتمام هنا: لنفترض أن الغرفة بالفعل $$$ك - 1 دولا$ الناس. عندما يدخل الغرفة $$$ك$ هذا الشخص $$$ك$ كان لدى الناس أعياد ميلاد مختلفة ، يجب أن تكون نتيجتين صحيحتين

1. جميع $$$ك - 1 دولا$ يجب أن يكون للأشخاص الذين دخلوا الغرفة من قبله أعياد ميلاد مختلفة. ما هو احتمال هذا؟ $$$\ Pr [A_ {k-1}]$ .
2. $$$ك$ - يحتاج هذا الشخص إلى عيد ميلاد مختلف عن جميع الآخرين $$$ك - 1 دولا$ الناس في الغرفة. ما هو احتمال هذا؟ $$$\ frac {365 - (k-1)} {365}$ .

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

$$عرض $$ $$ \ بدء {المعادلة *} \ بدء {تقسيم} \ العلاقات العامة [A_k] & = \ Pr [k - 1 \ text {الأشخاص في الغرفة لديهم أعياد ميلاد مختلفة} \ textbf {AND} \\ & \ \ \ \ \ \ \ \ \ text {لدى الشخص k عيد ميلاد مختلف عن} k - 1 \ text {people}] \\ & = \ Pr [k - 1 \ text {الأشخاص في الغرفة لديهم أعياد ميلاد مختلفة}] \\ & \ \ \ \ \ times \ Pr [\ text {person k له عيد ميلاد مختلف عن} k - 1 \ text {people}] \\ & = \ Pr [A_ {k-1}] \ times \ frac { 365 - (k-1)} {365} \ end {split} \ end {equation *} $$ عرض $$

الآن نحسب الاحتمالات:

$$عرض $$ $ \ تبدأ {المعادلة *} \ تبدأ {split} \ Pr [A_1] & = 1 \\ \ Pr [A_2] & = \ Pr [A_1] \ times \ frac {364} {365} = \ frac {364} {365} \ approx 0.997 \\ \ Pr [A_3] & = \ Pr [A_2] \ times \ frac {363} {365} = \ frac {364} {365} \ times \ frac {363} {365} \ approx 0.991 \\ \ Pr [A_4] & = \ Pr [A_3] \ times \ frac {362} {365} \ approx 0.983 \\ & \ vdots \\ \ Pr [A_ {22}] & = \ Pr [A_ {21}] \ times \ frac {344} {365} \ approx 0.525 \\ \ Pr [A_ {23}] & = \ Pr [A_ {22}] \ times \ frac {343} {365 } \ approx 0.493 \\ \ end {split} \ end {equation *} $$ عرض $$

منذ وصلنا $$$\ Pr [A_ {23}] = 0.493 <0.5$ هذا يعني أن احتمال وجود عيد ميلاد مشترك لشخصين متساوٍ

$$

$$\ Pr [\ overline {A_ {23}}] = 1 - \ Pr [A_ {23}] = 1 - 0.493 = 0.507> 0.5$$

مع زيادة $$$ن$ الاحتمال يميل إلى 1 ويصل إليه.

مهمة أكثر صعوبة

لنفترض أننا نريد تعميم هذه المشكلة على الحالة عندما تكون هناك $$$ن$ الناس و $$$م دولا$ أعياد الميلاد ممكن. وجود $$$n ، m$ ، هل يمكننا تحديد احتمال احتفال شخصين بعيد ميلاد مشترك؟

يمكنك استخدام نفس النظام: سيكون لدينا نتيجة $$$A_n$ تدل على كل شيء $$$ن$ الناس الذين ولدوا في أيام مختلفة. في حالة شخص واحد ، لا شيء يتغير

$$

$$\ Pr [A_1] = 1 دولا$$

في حالة وجود شخصين ، فإننا نعيّنهما على أنه "أ" و "ب". لكي يولد الشخص "ب" في يوم آخر ، يجب أن يكون لدى الشخص "ب" عيد ميلاد بين $$$م - 1 دولا$ خيارات أخرى.

$$

$$\ Pr [A_2] = \ frac {m-1} {m}$$

في حالة ثلاثة أشخاص ، يجب أن يكون لدى الشخص B عيد ميلاد مختلف عن عيد ميلاد A. يجب أن يكون لدى الشخص C يوم مختلف عن أعياد الميلاد A و B.

$$

$$\ Pr [A_3] = \ frac {m-1} {m} \ times \ frac {m-2} {m}$$

عموما لأي $$$ن$ يمكننا استخدام نفس الصيغة العودية كما في القسم السابق:

$$

$$\ Pr [A_n] = \ Pr [A_ {n-1}] \ الأوقات \ frac {m - (n-1)} {m}$$

لنفترض إذا كنا نريد العثور على تعبير في شكل مغلق لـ $$$\ Pr [A_n]$ ، ثم نحلل التعبير

$$عرض $$ $$ \ بدء {المعادلة *} \ بدء {تقسيم} \ العلاقات العامة [A_n] & = \ Pr [A_ {n-1}] \ الأوقات \ frac {m - (n-1)} {m} \ \ & = \ Pr [A_ {n-2}] \ الأوقات \ frac {m - (n-2)} {m} \ times \ frac {m - (n-1)} {m} \\ & = \ Pr [A_ {n-3}] \ times \ frac {m - (n-3)} {m} \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n -1)} {m} \\ & \ \ vdots \\ & = \ Pr [A_2] \ times \ frac {m-2} {m} \ times \ frac {m-3} {m} \ times \ cdots \ times \ frac {m - (n-3)} {m} \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n-1)} {m} \\ & = \ prod_ {i = 1} ^ {n-1} \ frac {mi} {m} = \ prod_ {i = 1} ^ {n-1} 1 - \ frac {i} {m} \\ & \ approx \ prod_ {i = 1} ^ {n-1} e ^ {\ frac {-i} {m}} \ text {باستخدام الهوية} 1 - x \ approx e ^ {- x} \\ & = e ^ {- \ sum_ {i = 1} ^ {n-1} \ frac {i} {m}} \\ & = e ^ {\ frac {-n (n-1)} {2m}} \ approx e ^ {\ frac {-n ^ 2} {2m}} \ end {split} \ end {equation *} $$ عرض $$

تقريب هذه النتيجة هو $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}}$ . على الرغم من أننا يمكن أن نجد المزيد من الحدود التقريبية ، فإن هذا يعطينا تقريبًا كافيًا. الهوية الوحيدة التي استخدمناها في هذا التقريب:

$$

$$1 - x \ approx e ^ {- x}$$

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

تطبيق

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

أولاً ، دعونا نحدد ما هي دالة التجزئة. وظيفة التجزئة $$$h: U \ rightarrow [0، m-1]$ هي وظيفة تؤدي تعيين من مجموعة $$$يو$ في عدد في النطاق $$$[0، m-1]$ . وظيفة $$$ح$ كما هو محدد $$$h (x) = x \ mod m$ - مثال دالة التجزئة من $$$\ mathbb {N} \ rightarrow [0، m-1]$ . دالات التجزئة لها العديد من الاستخدامات ، خاصةً مع بنية بيانات جدول التجزئة الشهيرة. يتم استخدامه أيضًا في التشفير ، حيث يتم استخدام نوع معين من دالة التجزئة يسمى "دالة تجزئة cryptoraphic".

واحدة من العديد من الخصائص التي يجب أن تحتوي عليها دالة هاش cryptoraphic هي مقاومة التصادم. يجب أن يكون من الصعب العثور على اثنين من هذا القبيل $$$u_1 ، u_2 \ in U$ بحيث تشكل تصادمًا ، أي $$$h (u_1) = h (u_2)$ .

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

في الماضي ، كان الناس والمنظمات يستخدمون التواقيع والأختام "لتوقيع" المستندات. في الآونة الأخيرة ، كان هناك انتقال إلى التوقيعات الإلكترونية أو الرقمية. يجب أن يفي التوقيع الرقمي بثلاثة خصائص أساسية.

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

التوقيع الرقمي هو وسيلة للتحقق من صحة وثيقة أو رسالة. يضمن التوقيع الرقمي أن الرسالة المستلمة تم إنشاؤها بواسطة مرسل معروف ولم يتم تغييرها.

دعنا نقول لدينا وثيقة $$$م دولا$ . كيف يمكننا التوقيع عليه؟

كل مستخدم / مؤسسة لديها مفتاح خاص فريد من نوعه $$$p_k$ والمفتاح العام $$$pub_k$ . يستخدمون وظيفة التوقيع لتوقيع وثيقة بمفتاحهم الخاص. ومع ذلك ، يمكن للتوقيع الرقمي توقيع عدد صغير فقط من المستندات. نطاق وظيفة التوقيع صغير. إحدى الطرق لحل هذه المشكلة هي إنشاء مستند أصغر يمثل المستند الأصلي ، ولكن بحجم أصغر بكثير. في معظم الأحيان ، يتم تطبيق دالة هاش على هذا المستند الكبير. يتم استخدام دالة التجزئة لرسم خريطة لها من مساحة كبيرة إلى مساحة أصغر ، وتسمى نتيجة هذه العملية "بصمة". يستخدم التوقيع البصمة والمفتاح الخاص لإنشاء التوقيع. يمكن وصف الإجراء على النحو التالي:

1. الحصول على المفتاح الخاص $$$p_k$ .
2. تجزئة وثيقة $$$م دولا$ واحصل $$$h (m)$ .
3. علامة $$$h (m)$ باستخدام المفتاح الخاص $$$p_k$ .
4. نحن نرسل $$ والمفتاح العام $$$pub_k$ أي شخص يريد تأكيد المستند.

أي شخص لديه $$ والمفتاح العمومي ، يمكن التحقق مما إذا كانت الوثيقة حقا $$$م دولا$ وقعت من قبل الشخص المناسب.

المشكلة: افترض أن المهاجم وجد إيفا وثيقتين $$$م ، م 'دولا$ حيث $$$م دولا$ - هذا هو العقد الحالي ، و $$$m '$ - وثيقة احتيالية من هذا القبيل $$$h (m) = h (m ')$ . لنفترض أن حواء تعرف مسبقاً أن أليس ستوقع فقط $$$م دولا$ لكن لا $$$m '$ . قبل التوقيع ، يتم تطبيق دالة تجزئة التشفير على الوثيقة $$$ح$ . تذهب حواء إلى أليس وتطلب منها توقيع وثيقة $$$م دولا$ باستخدام التسلسل الموضح أعلاه. الآن ، قد تزعم حواء أن أليس وقعت وثيقة احتيالية $$$m '$ لأن $$$h (m) = h (m ')$ . لن تتمكن أليس من إثبات أنها لم توقع بأي شكل من الأشكال $$$m '$ .

في المثال أعلاه $$$ح$ تحولت إلى وظيفة مقاومة للاصطدام ، لذلك تمكنت حواء من العثور على مجموعتي بيانات واردة وصلتا بنفس القيمة. حواء كانت قادرة على الادعاء بأن أليس وقعت $$$m '$ على الرغم من أنها وقعت في الواقع فقط $$$م دولا$ . هذا يؤكد على أهمية مقاومة التصادم ويوضح لماذا تكون التوقيعات الرقمية ضعيفة إذا كانت وظيفة التجزئة غير مستقرة.

سمح $$$h: U \ rightarrow [0، m-1]$ ستكون وظيفة التجزئة. افترض أن بيانات الإدخال يتم تجزئتها بشكل عشوائي ومستقل في أي من العناصر $$$م دولا$ .

مهمة الهجوم "عيد ميلاد" هي العثور على أصغر عدد من العناصر $$$ن$ والتي يمكن تجزئة مع $$$ح$ حتى نتمكن من العثور على عنصرين $$$x ، y \ in U$ في أي $$$h (x) = h (y)$ .

عند مهاجمة "أعياد الميلاد" ، يقوم المهاجم بالتقاطها بشكل عشوائي $$$x \ في U$ والحفاظ على الأزواج $$$(x، h (x))$ . سيقوم المهاجم بتحديد هذه الأزواج وحفظها بشكل متكرر حتى يجد قيمتين $$$x ، y$ في أي $$$h (x) = h (y)$ . نحتاج إلى تحديد عدد المرات التي يحتاج فيها المهاجم إلى تكرار هذه العملية حتى يجد تصادمًا.

لتحليل هجوم "أعياد الميلاد" ، يمكنك استخدام نفس المبادئ التي استخدمناها لمفارقة أعياد الميلاد. في الهجوم "أعياد الميلاد" $$$م دولا$ يدل على عدد الأيام في السنة ، و $$$يو$ على غرار الأشخاص الذين يدخلون الغرفة. يتم تجزئة الناس في أعياد ميلادهم ، والتي يمكن أن تكون واحدة من المعاني. $$$م دولا$ . دعنا نقول أننا بحاجة إلى العثور على تصادم مع احتمال 99 ٪. نحن بحاجة لمعرفة ما هو أصغر $$$ن$ ، والتي سيكون فيها تجزئة القيمتين عيد ميلاد واحد (في عالم دالات التجزئة ، هذا يعني أن مجموعتي بيانات المدخلات مجزأة في نفس القيمة).

سبق أن أظهرنا ذلك $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}}$

نريد أن نسأل $$$\ Pr [\ overline {A} _n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {99} {100}$ هذا هو $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {1} {100}$ .

$$عرض $$ $ \ تبدأ {المعادلة *} \ تبدأ {split} e ^ {\ frac {-n ^ 2} {2m}} & = \ frac {1} {100} \\ \ frac {n ^ 2} {2m} & = \ ln 100 \\ n ^ 2 & = 2 m \ ln 100 \\ n & = \ sqrt {2 m \ ln 100} \ end {split} \ end {equation *} $$ عرض $$

يخبرنا التحليل الموضح أعلاه أنه للحصول على تصادمات في وظائف التجزئة بفاصل زمني للحجم $$$م دولا$ يحتاج المهاجم إلى التجزئة بشكل موحد ومستقل تقريبًا $$$\ sqrt {2 m \ ln 100} = O (\ sqrt {m})$ للحصول على ضمان كامل تقريبًا (احتمال بنسبة 99٪) يتم تجزئة عنصرين بنفس القيمة.

لنفترض أننا نريد الحصول على تصادم مع احتمال 50 ٪. ثم نحتاج $$$n = \ sqrt {2 m \ ln 2}$ . الاستنتاج المهم هنا هو أنه من أجل الحصول على تصادم مع احتمال أكثر من 0.5 ، يتعين علينا تجزئة الأمر $$$\ sqrt {m}$ عناصر. هذا يتفق مع تحليلنا السابق ل $$$م = 365 دولا$ لأن $$$\ sqrt {2 \ ln 2 \ cdot 365}$ يساوي تقريبا 23.

مهام إضافية

1. وجود $$$ن$ من الناس $$$م دولا$ أيام وعدد معين $$$ك$ العثور على احتمال ذلك بالضبط $$$ك$ الناس لديهم نفس عيد الميلاد.
2. دعونا تحويل المهمة المذكورة أعلاه قليلا. دعنا نقول لدينا $$$م دولا$ أيام وعدد معين $$$ك$ . ماذا ستكون أصغر قيمة $$$ن$ التي لا تقل $$$ك$ سيحصل الناس على نفس عيد الميلاد مع احتمال 0.5 على الأقل؟ يمكنك تعميم هذه المهمة إلى أي احتمال $$$p> 0$ ؟
3. افترض أن لدينا 100 رقم من 1 إلى 100 ، بالإضافة إلى آلة تخمين عدد عشوائي من 1 إلى 100 في ترتيب موحد وعشوائي. كم مرة سنحتاج إلى استخدام الجهاز كما هو متوقع ، بحيث يخمن الجهاز جميع الأرقام من 1 إلى 100؟
4. يمكنك تعميم هذه المهمة إلى أي $$$ن$ ؟
5. افترض أن لدينا دالة هاش تعرض بشكل عشوائي عناصر في منطقة الذاكرة. واسمحوا مجموع المناطق $$$م دولا$ . كم عدد العناصر $$$ن$ هل نحتاج إلى إضافة توقع رياضي إلى بنية بياناتنا بحيث يتم تجزئة عنصرين على الأقل في كل منطقة؟