پارادوکس روز تولد (۳)

نویسنده: وهاب مختاری, منتشر شده در بخش علم و فناوری,

No file selected.

پیش‌تر در اینجا ثابت کردیم که وجود ۲۳ نفر کافی است تا احتمال بروز اشتراک در میان روز تولد آنها بیش از ۵۰ درصد باشد. در این بخش، ابتدا به ماهیت به ظاهر متناقض‌نمای این قضیه می‌پردازیم. در ادامه، اندکی راجع به پیش‌فرض‌های این مسئله روی آدم‌های واقعی در دنیای واقعی خودمان صحبت می‌کنیم. نهایتا یک کاربرد از این مسئله ریاضی را در علم رمزنگاری به طور گذرا شرح می‌دهیم.

۲۳ جواب عجیبی نیست؟!

بیایید همین اول کار یک نگاهی به نمودار زیر بیندازیم: محور عمودی نمودار احتمال بروز اشتراک (Probability of a pair) در روز تولد را نشان می‌دهد و محور افقی تعداد افراد (Number of people) را. مشاهده می‌کنید که هر چه تعداد افراد بیشتر شود، احتمال بروز اشتراک هم افزایش می‌یابد. این چیزی است که به طور کامل در بخش دوم مقاله مورد بحث و دقت قرار گرفت.

پارادوکس روز تولد (۳)

اما نکته جالب‌تر این است که در همان ابتدای کار، با افزایش تعداد نفرات، احتمال بروز اشتراک به طور تصاعدی افزایش پیدا می‌کند. به بیان ریاضی، در ابتدا مشتق تابع احتمال صعودی است و این باعث می‌شود که خیلی زود احتمال بروز اشتراک رشد کند به طوری که وقتی تعداد نفرات به ۲۳ نفر می‌رسد، احتمال بروز اشتراک بیش از نیمی از مسیر را طی می‌کند و به بالای ۵۰ درصد دست می‌یابد. ۲۳ از یک‌پانزدهم ۳۶۵ (تعداد حالات ممکن برای روز تولد) هم کمتر است! یعنی در یک مهمانی ۲۳ نفری شما می‌توانید "در حد احتمال شیر آمدن در پرتاب یک سکه"، از بروز اشتراک در تاریخ تولد آن ۲۳ نفر "مطمئن باشید"! در بدایت امر، این با عقل جور در نمی‌آید. ۳۶۵ حالت در برابر تنها ۲۳ نفر ناقابل به نظر دست‌نیافتنی می‌آید. اما اینجا می‌توان به یک شهود ساده اشاره کرد: هر یک از ۲۳ نفر می‌تواند با ۲۲ نفر دیگر روز تولد مشترکی داشته باشد. اگر همه حالت‌های دو به دو را در نظر بگیریم، تعداد حالات با ۳۶۵ روز ممکن برای تاریخ تولد "قابل قیاس" خواهد بود. به این توجه کنید که مثلا اگر نفر۲۴ام به جمع اضافه شود، خودش به تنهایی به تعداد ۲۳ (تعداد نفرات قبلی) حالت جدید برای امکان بروز اشتراک در روز تولد معرفی می‌کند. به این ترتیب، اگر حالت‌های ممکن برای روز تولد را با حالت‌های ممکن برای اشتراک روز تولد بین نفرات (و نه به طور ناشیانه صرفا تعداد نفرات!) مقایسه کنیم، حداقل جرقه‌ای در ذهن ما زده می‌شود که جواب ۲۳ عدد پرتی نیست!

آیا توزیع روز تولد افراد یکنواخت است؟امنیت

هر چند در بخش قبلی اشاره شد، اما جا دارد مجددا تاکید کنم که همه محاسبات بالا در شرایط توزیع یکنواخت  روز تولد بین ۳۶۵ روز سال بوده است. اگر به دلیلی این توزیع یکنواخت نباشد، احتمال بروز اشتراک بیشتر هم می‌شود! سایت ولفرام (Wolfram) این حدس را تایید می‌کند. پترسون در سال ۱۹۹۸ با استفاده از داده‌های آماری مربوط به روز تولد کودکان امریکایی بین سال‌های ۱۹۷۸ و ۱۹۸۷ به این نتیجه رسید که شانس تولد نوزادان امریکایی در فصل تابستان به طور محسوسی بالاتر است. باز در میان ماه‌های تابستان، ماه سپتامبر و در رتبه بعدی ماه آگوست به طور ویژه‌ای روزهای تولد بیشتری را به خود می‌بینند. شاید خیال کنید که بچه‌های امریکایی عاشق تعطیلات تابستانی یا شاید هم گرما یا میوه‌های تابستانی هستند که ترجیح می‌دهند در تابستان به‌دنیا بیایند! اما مسئله این است که درصد قابل توجهی از مادران امریکایی ترجیح می‌دهند در روزهای پایانی سال یا حول و حوش ایام کریسمس باردار شوند: احتمالا به دلیل اعتقادات مذهبی و خوش‌یمن دانستن آن. به این ترتیب حدودا ۹ ماه بعد نوزادشان به دنیا می‌آید که می‌کند به عبارتی اواخر تابستان (خصوصا ماه سپتامبر)!

جالب است بدانید در بیمارستان‌ها عمل سزارین و بارداری القایی در روزهای تعطیل آخر هفته به ندرت انجام می‌شود. این باعث می‌شود تا درصدی از بار تولدهای آخر هفته به روزهای دوشنبه و سه‌شنبه (روزهای اول هفته) منتقل شود و در نتیجه این روزها شاهد نوزادان بیشتری باشند. یک تحقیق دیگر در کشور سوئد نشان می‌دهد که سوئدی‌ها در ماه مارس بیشتر متولد می‌شوند و در ماه نوامبر کمتر.

روی هم رفته می‌توان چنین نتیجه گرفت که توزیع روز تولد آدم‌ها نمی‌تواند یکنواخت باشد و همین باعث می‌شود تا شانس بروز اشتراک روز تولد در یک جمع چند-نفره افزایش پیدا کند و برای مسئله پارادوکس روز تولد، در واقعیت چه بسا به عددی کمتر از ۲۳ هم برسیم.

کاربرد "پارادوکس روز تولد" در رمزنگاری

در مباحث امنیت اطلاعات الکترونیکی دو مسئله عمده وجود دارد: یکی قابلیت اعتماد و محرمانه بودن (Confidentiality) در انتقال یا ذخیره اطلاعات و دیگری درستی و یکپارچگی (Integrity).امنیت

زمانی که مجموعه‌ای از اطلاعات خصوصی خودتان را ای‌میل می‌کنید یا مثلا شماره حساب و رمز حساب بانکی‌تان را در سامانه مربوطه وارد می‌کنید یا حتی یک فایل شخصی را بر روی کامپیوتر یا گوشی موبایل‌تان ذخیره می‌کنید، دوست دارید شخص غیرمجاز نتواند به اطلاعات شما دسترسی داشته باشد. این قابلیتی است که از آن به Confidentiality یاد می‌کنند.

اما بعضی وقت‌ها Confidentiality یا محرمانه بودن دغدغه شمای کاربر نیست. فرض کنید اطلاعاتی را در دسترس عموم قرار داده‌اید. اطلاعات شما نه تنها خصوصی و محرمانه نیست بلکه شاید تمایل داشته باشید بازدیدکننده بیشتری هم پیدا کند. مثلا ممکن است این اطلاعات مربوط به تبلیغ درباره یک محصول در دنیای سایبر باشد. در اینجا فقط می‌خواهید اطلاعات‌تان دست‌کاری نشود! این قابلیتی است که از آن با عنوان صحت و یکپارچگی یا Integrity یاد می‌کنند. شما فقط می‌خواهید اطلاعات‌تان همانی باشد که ارسال کرده‌اید نه چیز دیگری. مثلا دوست ندارید سر و کله یک هکر پیدا شود و بر روی عکس پرسنلی پروفایل شما که در سایت شخصی‌تان عمومی کرده‌اید، یک دماغ بزرگ قرمز مسخره قرار دهد! یا دوست ندارید امضای دیجیتال شما هک شده و متن نقد شما در صفحه مربوط به یک کتاب الکترونیکی دست‌کاری شود.

خب! حالا رمزنگاری به میدان آمده و با طراحی مکانیسم‌هایی قصد دارد ارسال و ذخیره اطلاعات را امن کند. منظور از ایجاد امنیت تعبیه قابلیت‌های Confidentiality یا Integrity یا هر دو، بسته به مورد کاربرد است. هکر کیست؟ فردی که بر علیه اطلاعات رمز شده به میدان می‌آید تا حداقل یکی از دو ویژگی فوق‌الذکر را زیر سوال ببرد. البته توجه‌مان معطوف به آن دسته از هکرهایی است که بر علیه خود مکانیسم رمزنگاری وارد عمل می‌شوند و نه حفره‌ها و اشکالات امنیتی سخت‌افزاری و نرم‌افزاری رایج. دسته اخیر در بحث شبکه‌های کامپیوتری و امنیت شبکه مطرح می‌شود نه رمزنگاری.

برای تامین ویژگیIntegrity  یا صحت و تمامیت اطلاعات، رمزنگار "معمولا" از مکانیسمی به نام درهم‌سازی (Hash Function) استفاده می‌کند تا از روی پیغام (Message) و یک کلید (Key) مشترک بین فرستنده و گیرنده اطلاعات، کدی به نام تگ (tag) را ضمیمه اطلاعات کند. گیرنده هم با استفاده از یک مکانیسم راست‌آزمایی (Authentication) می‌تواند با در اختیار داشتن سه تکه اطلاعات پیغام، کلید و تگ به صحت یا عدم صحت اطلاعات ارسالی از طرف فرستنده پی ببرد.امنیت

برای شکستن Integrity در ارسال یا ذخیره اطلاعات، هکر بایستی بتواند خروجی تابع Hash، یعنی tag، را برای یک پیغام محاسبه کند. با توجه به پیچیدگی محاسباتی مکانیسم‌های رمزنگاری، یک هکر فقط می‌تواند به کمک آزمون و خطا به پیغام رمزشده حمله کند. فرآیند آزمون و خطا مستلزم صرف زمان طولانی و بعضا استفاده از حجم زیاد حافظه‌های کامپیوتری است. اینجاست که "پارادوکس روز تولد" به جناب هکر ایده می‌دهد تا فرآیند آزمون و خطا را خیلی کوتاه‌تر کند!پارادوکس روز تولد

فرض کنید هکر مجبور باشد n پیغام مختلف را برای پیدا کردن tag یک پیغام خاص بیازماید. اثبات می‌شود که اگر هکر بتواند یک تصادم (Collision) در برد تابع Hash پیدا کند، کار تمام است. منظور از تصادم، پیدا کردن دو پیغام متفاوت با tag یکسان است. با توجه به کوچک‌تر بودن برد تابع Hash به نسبت دامنه پیغام‌ها، این احتمال وجود دارد. مسئله شبیه پیدا کردن اشتراک روز تولد بین آدم‌های مختلف است. تعمیم‌یافته مسئله پارادوکس روز تولد می‌گوید که اگر فضای پیغام‌ها دربرگیرنده n حالت مختلف باشد، در میان حدودا رادیکال n (به مراتب کمتر از n) پیغام مختلف با احتمال دست کم ۵۰ درصد یک تصادم (Collison) رخ خواهد داد.

ثابت می‌شود به طور متوسط با تنها دو بار تلاش متوالی در یافتن تصادم، هکر موفق به این کار می‌شود! بنابراین پارادوکس روز تولد حجم محاسبات هکر را به میزان قابل توجهی کاهش می‌دهد. از دیگر سو لازم است برای دفع خطر حملات، پیچیدگی محاسباتی الگوریتم‌های رمزنگاری به طور متناسبی افزایش پیدا کند.

به این مطلب چه امتیازی می‌دهید؟

4.0/5 امتیازهای داده شده (18 امتیاز)

به اشتراک گذاری

در مورد نویسنده

وهاب مختاری

پزشکی و سلامت