به قلم امیرارسلان یاوری، ورودی 98مهندسی کامپیوتر دانشگاه صنعتی اصفهان
بازنگری‌شده توسط پارسا شیرکوند، ورودی 402 کارشناسی مهندسی کامپیوتر صنعتی اصفهان
اگه تو یه کلاس ۷۵ نفره نشسته باشین و استادتون جلسه اول بیاد داخل کلاس و بگه کسی حاضره که با من شرط ببنده که اگه حداقل ۲ نفر روز تولد یکسانی در سال داشته باشن از شما ۲ نمره کم کنم اما در غیر این صورت به شما ۲۰ بدم، شما حاضرین این شرط رو باهاش ببندین؟ (فرض کنین هیچ کدوم از ۷۶ نفر داخل کلاس هم تاریخ تولد هیچ کسی رو نمی‌دونن).
یا اگه کلاس ۲۳ نفره بودین و استادتون می‌گفت اگه حداقل دو نفر تاریخ تولد یکسان داشتن ۴ نمره کم می‌کنم ازتون و در غیر این صورت ۴ نمره بهتون اضافه می‌کنم چطور؟
حالا اگه استادتون یه سکه گرفته باشه دستش و بگه من سکه رو می‌ندازم اگه رو اومد ۲ نمره کم می‌کنم ولی اگه پشت اومد ۲ نمره بهتون میدم چی؟ بازم حاضرین شرط ببندین؟
خب راستش همه‌مون همون شرط اول رو می‌پذیریم و احتمالا با خودمون می‌گیم ببین تو ۳۶۵ روز سال واقعا احتمالش خیلی کمه که دو نفر تو یه روز به دنیا اومده باشن. حتی تو دومی می‌گیم دیگه محال ممکنه که از ۲۳ نفر ۲ نفر تو یه روز از سال بدنیا اومده باشن پس حتما شرط رو ببندم که استاده میخواد ۴ نمره مفتی بهم بده. احتمالا هم همه‌ی ما فکر می‌کنیم شرایط دو شرط اولیه نسبت به اون شرطی که با سکه بسته می‌شه خیلی بهتره و مادامی که شرط اول و شرط دوم هست اصلا چرا به شرط سوم فکر کنیم. خب خبر بد ماجرا اینه که ما اشتباه فکر می‌کنیم :) حالا داستان چیه؟
داستان اینه که شرط دوم (یعنی اونی که ۲۳ نفر باشین) یه مسئله معروفه به اسم "Birthday Paradox" که می‌گه تو چنین شرایطی با احتمال بیش از یک دوم دو نفر تاریخ تولد یکسانی خواهند داشت؛ احتمالا هنوز هم پذیرفتنش براتون سخته؛ پس بیاید با هم دیگه احتمالش رو حساب کنیم. احتمال اینکه تاریخ تولد حداقل دو نفر در یک روز باشه، در واقع می‌شه ۱ (احتمال کل) منهای این که تمامی افراد در روز‌های متفاوتی به دنیا اومده باشن. پس داریم:
برای نفر اوّل ۳۶۵ حالت مختلف وجود داره؛ پس 365/365 ام احتمال داره برای نفر دوم چون قراره تو روز دیگه‌ای متولد شده باشه پس ۳۶۴/۳۶۵ ام حالت هست و به همین ترتیب برای نفر i ام ۳۶۵ منهای i به روی ۳۶۵ احتمالش خواهد بود. عدد حاصله رو از یک که کم کنیم احتمال نقیض P محاسبه شده (یعنی احتمال اینکه تاریخ تولد تمامی افراد متفاوت نباشد محاسبه شده). این توضیحی که دادیم در واقع همون فرمول بالاست. خب دیگه قضیه خیلی راحت شد! فقط کافیه عبارت بالا رو یک بار برای ۲۳ و یک بار برای ۷۵ حساب کنین که اون وقت می‌بینین برای ۲۳ احتمال ۰/۵۰۷۳ و برای ۷۵ برابر ۰/۹۹۹۷ هست :)
خب حالا چرا احتمالش اینطوری می‌شه؟ اگه شهود احتمالی خوبی داشتین، همون خط اول این متن متوجه این موضوع شاید می‌شدین ولی ما آدما اصولا حتی اگه خیلی منطقی هم باشیم به آمار و احتمال مسلط هم باشیم گاهی وقتا حسی تو ذهنمون فکر می‌کنیم. ماجرا اینه که همه‌ی ما می‌دونیم ضرب هر عددی در صفر برابر صفر می‌شه؛ در واقع توی این سلسله‌ضرب‌ها ما در حال ضرب کردن یه عدد کسری (حتی می‌شه ۱ در نظرش گرفت) در یه عدد کمتر هستیم(چون رفته‌رفته صورت کسر کوچیک‌تر می‌شه) و در نتیجه، مقدار حاصل‌مون هم مرحله به مرحله کمتر می‌شه.
من تکه کد پایتونی زیر رو هم براتون گذاشتم که اگه دوست داشتین با تغییر متغیر n بتونین برای هر تعداد احتمالش رو به دست بیارین:
خب حالا این رو فهمیدیم که نباید اون شرط‌ها رو با استادمون ببندیم چون تو اولی که یه جورایی قطعا بازنده‌ایم و توی مورد دوم هم احتمال پیروزی‌مون توی شیر یا خط کردن با سکه بیشتر از شانس‌‌مون توی این شرطه :)
حالا مسئله اصلی اینه که این مسئله در کجای زندگیمون کاربرد داره؟ مثلا اگه درس ساختمان داده رو گذروندین و با مبحث توابع Hash آشنایی دارین (توابع Hash توابعی هستن که هر ورودی با هر سایزی رو به یک خروجی با سایز معین تبدیل می‌کنن). برای یادآوری کوتاه میتونین به عکس زیر دقت کنین. هر ورودی که از تابع Hash می‌گذره و مپ می‌شه به یه سطر از جدول خروجی.
خب همون‌طور که می‌دونین که ما انتظار داریم که Collision توی خروجی تابع Hashمون کم باشه تا بتونیم از
O(1) بهش دسترسی داشته باشیم (مثلا اگه تمامی خروجی‌ها تابع Hash ما در یک خانه قرار بگیرن بعدا در زمان دسترسی بهشون باید از O(n) زمان مصرف کنیم). خب تا اینجا براتون واضحه که اگه یه تابع Hash داشته باشیم و خروجیش یه جدول ۳۶۵ تایی باشه بعد از چه تعداد با چه احتمالی ممکنه Collision رخ بده :) پس برای یک تابع Hash نمی‌تونیم فقط به Randomness اعتماد کنیم.
بگذریم؛
تو مبحث امنیت هم ما یک نوع حمله داریم که اسمش "Birthday Attack" هست و بر اساس همین مسئله "Birthday Paradox" تعریف شده و از طریق Collision توابع Hash حمله صورت می‌گیره. مثلا فرض کنین یک تابع Hash داریم که خروجیش ۱۰۰۰ تایی باشه؛ بعد از ۱۰۰ تا مقدار احتمالا ۵ تا Collision خواهیم داشت و حتی بعد از ۲۵۰ تا به ۳۱ Collision خواهیم رسید که آمار بدیه (منطقیه تعداد Collision به صورت نمایی با افزایش تعداد نمونه‌ها افزایش پیدا می‌کنه). آقای Wang و همکارانش در سال ۲۰۰۵ روی همین مسئله تحقیق کردن و نشون دادن که SHA1 و MD5 برای توابع Hash ضعیف هستن؛ چرا که شما اگه 2¹²⁸ حالت ممکنه داشته باشین با 2⁶³ تا حالت میتونین یک Collision پیدا کنین و به همین دلیل فضای سرچ رو به میزان خیلی قابل توجهی کاهش دادین. حالا اصلا چرا Collision مهمه؟ فرض کنین قراردادی صورت می‌گیره و Hash فایل قرارداد به عنوان تضمین قرار داده می‌شه؛ بعدا قرارداد با یک نسخه‌ی جعلی که Hash یکسانی با قرارداد اصلی داره، جایگزین بشه و کلاه‌برداری صورت بگیره :دی.
خب اگه بیشتر بگردین احتمالا به مسائل جالب‌تری هم تو این حوزه برسین. (مثلا تو رفرنس سوم چند تا مثال دیگه هم هست که دوست داشتین بخونین‌شون) اما من درکل دلم می‌خواست هم با مسئله "Birthday Paradox" آشنا بشیم، هم حواسمون به Multiplicative Sequences Limit Behavior باشه و بر همین اساس از این به بعد سعی کنیم ذهنمون احساسی به مسئله نگاه نکنه. (مثلا اگه یه تاس رو ۱۰ بار انداختیم و ۶ نیومده پس توی ذهنمون نگیم چون ۱۰ بار ۶ نیومده پس دیگه این سری باید ۶ بیاد؛ آخه متغیرمون مستقله و حتی اگه ۱۰۰۰ بار هم ۶ نیومده باشه برای بار ۱۰۰۱ ام احتمال ۶ اومدن ⅙ هستش :دی)
https://betterexplained.com/articles/understanding-the-birthday-paradox/
https://arishs.medium.com/the-birthday-paradox-and-collisions-in-a-hashtable-e32ce611f5c
https://builtin.com/articles/birthday-paradox
https://eprint.iacr.org/2007/474.pdf
