مباحث جذاب رمزنگاری!

[tiberium]

خب ۳ تا مساله ی بعدی

۱- Alice و Bob هرکدوم یه تعداد شکلات دارن. و فرض کنید این تعداد میتونه ۱۰ یا ۲۰ یا ۳۰ یا ۴۰ یا ۵۰ تا باشه‌ و هردو میدونن که یکی‌از این ۵ حالته. این دو فرد می خوان بفهمن آیا تعداد شکلات یکسانی دارن یا نه؟ بدون اینکه بفهمن طرف مقابل چقدر شکلات داره. مثلا اگر من ۱۰ تا داشته باشم و یکی ۳۰ تا. اگر بگیم عدد هارو لو میره تعداد شکلاتا.


۲- دو میلیارد وجود دارن. می خوان بدون اینکه داراییشونو بگن بفهمن کی پولدارتره.(حتی هیچ اطلاعاتی راجع به پولشون ندن ) ( این یکم ریاضیاتی تره )

۳- فرض کنید یه کامپیوتر هست با اطلاعات خیلی خیلی حساس. و پسورد ورود عدد t هست. حالا اگر این پسورد رو یه نفر بدونه خیلی خطرناکه. من می خوام این پسورد رو جوری بین مثلا ۱۰ نفر آدم تقسیم کنم که هر دو نفری که بیان بتونن با اعدادشون t رو بدست بیارن. ولی یه نفر با عدد یا اعدادی که داره نتونه هیچی راجع به t بفهمه.

 

[M R X]

شکلاتاشونو با هم عوض کنن تا زمانی که مال یکیشون تموم بشه
البته در این صورت آخرش میفهمن طرف مقابل چندتا شکلات داره ، نمیشه که اخرش بفهمن؟

 

[tiberium]

شکلاتاشونو با هم عوض کنن تا زمانی که مال یکیشون تموم بشه
البته در این صورت آخرش میفهمن طرف مقابل چندتا شکلات داره ، نمیشه که اخرش بفهمن؟

خب‌ اگر برا من زودتر تموم بشه طرف مقابل میفهمه چند تا شکلات دارم. با اینکه من نمیفهمم اون چنو تا داره. ولی اون میفهمه من چند تا دارم

 

[Armita.N]

نمیشه مثلا برن شکلاتاشونو آب کنن بعد جرمشو اندازه بگیرن ببینن تقریبا یکیه یا نه؟

 

[tiberium]

نمیشه مثلا برن شکلاتاشونو آب کنن بعد جرمشو اندازه بگیرن ببینن تقریبا یکیه یا نه؟

ایده خوبیه ولی باز لو میره. من اگر‌ آب کنم و بشه ۱۰۰ گرم ( و فرض کنید ۵۰ تا شکلات داشتم ) پس اگر اون آب شده شکلاتاش باشه ۶۰ گرم میتونم بفهمم چندتا داشته ( نسبت ساده )

 

[HeiSenberG]

خب ۳ تا مساله ی بعدی

۱- Alice و Bob هرکدوم یه تعداد شکلات دارن. و فرض کنید این تعداد میتونه ۱۰ یا ۲۰ یا ۳۰ یا ۴۰ یا ۵۰ تا باشه‌ و هردو میدونن که یکی‌از این ۵ حالته. این دو فرد می خوان بفهمن آیا تعداد شکلات یکسانی دارن یا نه؟ بدون اینکه بفهمن طرف مقابل چقدر شکلات داره. مثلا اگر من ۱۰ تا داشته باشم و یکی ۳۰ تا. اگر بگیم عدد هارو لو میره تعداد شکلاتا.

۵ تا سوال می‌پرسیم :
آیا ۱۰تا شکلات دارید؟
آیا بیشتر از ۱۵ تا دارید؟
آیا بیشتر از ۲۵ تا دارید؟
آیا بیشتر از ۳۵ تا دارید؟
آیا بیشتر از ۴۵ تا دارید؟
بعد جوابش رو به صورت بله و خیر توی کاغدای کوچیک طوری که طرف مقابل نبینه می‌نویسن.
بعد کاغذا رو می‌ندازن تو یه تنگ و هم می‌زنن و بعد درش میارن.
اگه تعداد بله‌ها و خیر ها زوج بود یعنی شکلات یکسانی دارن

 

[tiberium]

۵ تا سوال می‌پرسیم :
آیا ۱۰تا شکلات دارید؟
آیا بیشتر از ۱۵ تا دارید؟
آیا بیشتر از ۲۵ تا دارید؟
آیا بیشتر از ۳۵ تا دارید؟
آیا بیشتر از ۴۵ تا دارید؟
بعد جوابش رو به صورت بله و خیر توی کاغدای کوچیک طوری که طرف مقابل نبینه می‌نویسن.
بعد کاغذا رو می‌ندازن تو یه تنگ و هم می‌زنن و بعد درش میارن.
اگه تعداد بله‌ها و خیر ها زوج بود یعنی شکلات یکسانی دارن

مرسی ولی یه باگ هست. من وقتی جواب میدم میدونم مثلا چند تا بله گفتم. پس اگر تعداد بله های کل رو بدونم میفهمم اون چند تا بله گفته. و میفهمم چند تا شکلات داره

 

[Armita.N]

۵ تا سوال می‌پرسیم :
آیا ۱۰تا شکلات دارید؟
آیا بیشتر از ۱۵ تا دارید؟
آیا بیشتر از ۲۵ تا دارید؟
آیا بیشتر از ۳۵ تا دارید؟
آیا بیشتر از ۴۵ تا دارید؟
بعد جوابش رو به صورت بله و خیر توی کاغدای کوچیک طوری که طرف مقابل نبینه می‌نویسن.
بعد کاغذا رو می‌ندازن تو یه تنگ و هم می‌زنن و بعد درش میارن.
اگه تعداد بله‌ها و خیر ها زوج بود یعنی شکلات یکسانی دارن

خب مثلا فرض کنیم ۴ تا بله اومد ۶ تا خیر
میتونه ترکیبش ۳۰ و ۳۰ باشه میتونه ۴۰ و ۱۰ هم باشه

 

[0001111]

۱ هردو شکلاتاشون رو تو یه ظرف کاملا مشابه میریزن و به صورت اتفاقی یکی از کیسه ها رو بر میدارن اگه هیچکدوم متوجه تغییر وزن نشدن میتونن بفهمن شکلاتاشون برابر بوده.
۳ به هر کدوم یه رقم فرد میدیم و به کامپیوتر میگیم اگه حاصل جمع زوج شد قفلش باز بشه (مشکلش این میتونه باشه که رمز به صورت یک عدد یا یک حرف نیست پس بیشتر از یه رمز داریم ولی اگه مفهوم رمز زوج یا فرد بودن باشه درسته)

 

[tiberium]

۱ هردو شکلاتاشون رو تو یه ظرف کاملا مشابه میریزن و به صورت اتفاقی یکی از کیسه ها رو بر میدارن اگه هیچکدوم متوجه تغییر وزن نشدن میتونن بفهمن شکلاتاشون برابر بوده.
۳ به هر کدوم یه رقم فرد میدیم و به کامپیوتر میگیم اگه حاصل جمع زوج شد قفلش باز بشه (مشکلش این میتونه باشه که رمز به صورت یک عدد یا یک حرف نیست پس بیشتر از یه رمز داریم ولی اگه مفهوم رمز زوج یا فرد بودن باشه درسته)

مرسی ولی‌یه باگ. بر فرض من ۴۰ تا شکلات دارم.
یه ظرف برمیدارم و میبینم از من سنگینتره. پس قطعا اون ۵۰ تا داره ( چون حالت دیگه ای نیست ) پس هنوز یه سری اطلاعات دارم بدست میارم!

 

[tiberium]

۱ هردو شکلاتاشون رو تو یه ظرف کاملا مشابه میریزن و به صورت اتفاقی یکی از کیسه ها رو بر میدارن اگه هیچکدوم متوجه تغییر وزن نشدن میتونن بفهمن شکلاتاشون برابر بوده.
۳ به هر کدوم یه رقم فرد میدیم و به کامپیوتر میگیم اگه حاصل جمع زوج شد قفلش باز بشه (مشکلش این میتونه باشه که رمز به صورت یک عدد یا یک حرف نیست پس بیشتر از یه رمز داریم ولی اگه مفهوم رمز زوج یا فرد بودن باشه درسته)

در رابطه با سوال ۳. مسیر فکریتو دوست دارم ولی مشکلاتی هست. قطضیه اینه که نحوه ی عملکرد این رمز رو همه بلدن و میدونن. اگر بدونن با عدد زوج باز میشه خب من ۱۷ دارم ولی میرم ۲۰ میزنم که زوجه.

 

[Iman Rage]

خب ۳ تا مساله ی بعدی

۱- Alice و Bob هرکدوم یه تعداد شکلات دارن. و فرض کنید این تعداد میتونه ۱۰ یا ۲۰ یا ۳۰ یا ۴۰ یا ۵۰ تا باشه‌ و هردو میدونن که یکی‌از این ۵ حالته. این دو فرد می خوان بفهمن آیا تعداد شکلات یکسانی دارن یا نه؟ بدون اینکه بفهمن طرف مقابل چقدر شکلات داره. مثلا اگر من ۱۰ تا داشته باشم و یکی ۳۰ تا. اگر بگیم عدد هارو لو میره تعداد شکلاتا.


۲- دو میلیارد وجود دارن. می خوان بدون اینکه داراییشونو بگن بفهمن کی پولدارتره.(حتی هیچ اطلاعاتی راجع به پولشون ندن ) ( این یکم ریاضیاتی تره )

۳- فرض کنید یه کامپیوتر هست با اطلاعات خیلی خیلی حساس. و پسورد ورود عدد t هست. حالا اگر این پسورد رو یه نفر بدونه خیلی خطرناکه. من می خوام این پسورد رو جوری بین مثلا ۱۰ نفر آدم تقسیم کنم که هر دو نفری که بیان بتونن با اعدادشون t رو بدست بیارن. ولی یه نفر با عدد یا اعدادی که داره نتونه هیچی راجع به t بفهمه.

به من یک تبدیل ریاضی بدین که معکوس گرفتن ازش "سخت" باشه.

 

[tiberium]

به من یک تبدیل ریاضی بدین که معکوس گرفتن ازش "سخت" باشه.

مساله لگاریتم گسسته. فرض کن یه عدد اول خیلی بزرگ داری. ( خیلی بزرگ!) و روی یک g پایه به صورت عمومی توافق می کنیم. حالا اگر تو x داشته باشی . تابع f رو اینجوری تعریف کنیم
f (x) = (g ^ x) mod p.
با داشتن خروجی اون تابع و g بدست آوردن x یه مساله سخت به حساب میاد.
یا مثلا یه تابع Hash. مثل SHA-256.

آفرین میتونم حدس بزنم دنبال چی هستی ولی یه مشکلی وجود داره اینجا ! تو می خوای به جای عدد f اون عدد و بدی و اگر f ها برابر بودن برابره و اگر f برابر نبود نمیتونی عددشو هم بفهمی. آره کاملا درسته. ولی! من میام f همرو حساب میکنم . f 10 20 30 40 50. بعد میام با عددت مقایسه می کنم و میفهمم کدومو از این تابع گذروندی.

 

[Mohammadreza128]

شکلاتا رو بریزن تو آب ببینن مال کی بیشتر سطح اب بالا میاد...با ماژیک علامت بزنن زودم پاک کنن ک نخان ارشمیدس بزنن وزن بدست بیارن )...

 

[tiberium]

شکلاتا رو بریزن تو آب ببینن مال کی بیشتر سطح اب بالا میاد...با ماژیک علامت بزنن زودم پاک کنن ک نخان ارشمیدس بزنن وزن بدست بیارن )...

خب بازم همون ایراد بهش وارد هست. مثلا تو 40 تا داری. میبینی برای اون سطح آب بیشتر میاد بالا. پس میفهمی اون 50 تا داره چون عدد دیگه ای نیست

 

[Iman Rage]

مساله لگاریتم گسسته. فرض کن یه عدد اول خیلی بزرگ داری. ( خیلی بزرگ!) و روی یک g پایه به صورت عمومی توافق می کنیم. حالا اگر تو x داشته باشی . تابع f رو اینجوری تعریف کنیم
f (x) = (g ^ x) mod p.
با داشتن خروجی اون تابع و g بدست آوردن x یه مساله سخت به حساب میاد.
یا مثلا یه تابع Hash. مثل SHA-256.

آفرین میتونم حدس بزنم دنبال چی هستی ولی یه مشکلی وجود داره اینجا ! تو می خوای به جای عدد f اون عدد و بدی و اگر f ها برابر بودن برابره و اگر f برابر نبود نمیتونی عددشو هم بفهمی. آره کاملا درسته. ولی! من میام f همرو حساب میکنم . f 10 20 30 40 50. بعد میام با عددت مقایسه می کنم و میفهمم کدومو از این تابع گذروندی.

الگوریتم کار:
نفر A با استفاده از عددی که داره و یک عدد رندوم یک تابع hash میسازه.(ایده ای ندارم اینکار شدنیه یا نه)(تابع ساخته شده نسبت به عدد A حساس است اما این موضوع تنها برای نفر A مشهود است چراکه اعداد رندوم موضوع را برای فرد B پیچیده می کنند!)
نفر B:یک عدد رندوم به همراه عدد خود را وارد تابع می کند.نتیجه را به A اعلام می کند.(Bنمی تواند بفهمد تابع Aبه چ چیزی حساس است.حتی با آزمایش و خطا مقادیر متفاوت را مشاهده می کند اما نمی داند که کدام جواب برای A حساس است چرا که برای تشخیص آن نیاز به عدد رندوم Aدارد)
از آنجا که Aخود میداند که تابعی که به Bداده بود نسبت به عدد خودش حساس است.(به نظرم ایده حساسیت در اعداد اول باشه)نگاه می کند ببیند آیا جواب B شرط حساسیت که از قضا فقط خودش می داند بر آورده کرده است یا نه؟
Aبه هیچ عنوان نمی تواند بفهمد کدام عدد را وارد کرده که چرا ک پای یک عدد رندوم دیگر هم در میان هست که کار رو برای A سخت میکنه.
می دونم تو یک فضای کاملا انتزاعی دارم صحبت می کنم ولی خب حل سیستماتیک اینطور به نظر می آید.
در مورد مسئله فرد پول دار حل در حساسیت خصوصی در اختلاف پولها.
در مسئله سوم هم همان تابعی که دو ورودی دارد حساسیت خاصی نسبت به جفت ورودیهای خاصی دارد.هیچ کس نمی تواند از خروجی تابع و عدد خودش عدد دیگر را حدس بزند چرا که معکوس گیری کار خیلی سختی است.اما همه می دانند جواب باید tشود فقط قدرت محاسبه عدد دیگر را ندارند!
به وضوح این توابع به شدت غیر خطی هستند

 

[tiberium]

الگوریتم کار:
نفر A با استفاده از عددی که داره و یک عدد رندوم یک تابع hash میسازه.(ایده ای ندارم اینکار شدنیه یا نه)(تابع ساخته شده نسبت به عدد A حساس است اما این موضوع تنها برای نفر A مشهود است چراکه اعداد رندوم موضوع را برای فرد B پیچیده می کنند!)
نفر B:یک عدد رندوم به همراه عدد خود را وارد تابع می کند.نتیجه را به A اعلام می کند.(Bنمی تواند بفهمد تابع Aبه چ چیزی حساس است.حتی با آزمایش و خطا مقادیر متفاوت را مشاهده می کند اما نمی داند که کدام جواب برای A حساس است چرا که برای تشخیص آن نیاز به عدد رندوم Aدارد)
از آنجا که Aخود میداند که تابعی که به Bداده بود نسبت به عدد خودش حساس است.(به نظرم ایده حساسیت در اعداد اول باشه)نگاه می کند ببیند آیا جواب B شرط حساسیت که از قضا فقط خودش می داند بر آورده کرده است یا نه؟
Aبه هیچ عنوان نمی تواند بفهمد کدام عدد را وارد کرده که چرا ک پای یک عدد رندوم دیگر هم در میان هست که کار رو برای A سخت میکنه.
می دونم تو یک فضای کاملا انتزاعی دارم صحبت می کنم ولی خب حل سیستماتیک اینطور به نظر می آید.
در مورد مسئله فرد پول دار حل در حساسیت خصوصی در اختلاف پولها.
در مسئله سوم هم همان تابعی که دو ورودی دارد حساسیت خاصی نسبت به جفت ورودیهای خاصی دارد.هیچ کس نمی تواند از خروجی تابع و عدد خودش عدد دیگر را حدس بزند چرا که معکوس گیری کار خیلی سختی است.اما همه می دانند جواب باید tشود فقط قدرت محاسبه عدد دیگر را ندارند!
به وضوح این توابع به شدت غیر خطی هستند

من یه بار خوندم ولی یه سری جاهاشو خوب متوجه نشدم. بزار یه بار دیگه بهتر بخونم ببینم میفهمم یا نه. ولی سیستماتیک داری پیش میری و این احتمالا جوابای خوبیه. ولی هنوز نفهمیدم که بتونم راجع به درستی غلطیش نظر بدم.

 

[tiberium]

الگوریتم کار:
نفر A با استفاده از عددی که داره و یک عدد رندوم یک تابع hash میسازه.(ایده ای ندارم اینکار شدنیه یا نه)(تابع ساخته شده نسبت به عدد A حساس است اما این موضوع تنها برای نفر A مشهود است چراکه اعداد رندوم موضوع را برای فرد B پیچیده می کنند!)
نفر B:یک عدد رندوم به همراه عدد خود را وارد تابع می کند.نتیجه را به A اعلام می کند.(Bنمی تواند بفهمد تابع Aبه چ چیزی حساس است.حتی با آزمایش و خطا مقادیر متفاوت را مشاهده می کند اما نمی داند که کدام جواب برای A حساس است چرا که برای تشخیص آن نیاز به عدد رندوم Aدارد)
از آنجا که Aخود میداند که تابعی که به Bداده بود نسبت به عدد خودش حساس است.(به نظرم ایده حساسیت در اعداد اول باشه)نگاه می کند ببیند آیا جواب B شرط حساسیت که از قضا فقط خودش می داند بر آورده کرده است یا نه؟
Aبه هیچ عنوان نمی تواند بفهمد کدام عدد را وارد کرده که چرا ک پای یک عدد رندوم دیگر هم در میان هست که کار رو برای A سخت میکنه.

خب حل جالبی بود. و یه سری بخشای خیلی خوبی داره. ولی من یه چیزیو بهش مشکوکم.
الان تو یه تابعی ساختی که مثلا توی اون عددی که داری یه رفتار خاصی از خودش نشون میده درسته ؟ با اینکه یه رندوم هم هست.
حالا طرف عدد خودش و یه رندوم میده . اگر عدد B برابر باشه با عدد A و اون رفتار خاص رو از تابع ببینه میتونه ( با اینکه رندوم B هم نمیدونه ) و بگه اینا برابر هستن درسته ؟
اگر اون رندوم توی رفتار تابع تو اون نقطه تاثیر خاصی نذاره میشه نتیجه گرفت که بقیه جاها هم میشه یه سری دیتا بدست آورد. یعنی من اگر یه سری خروجی بگیرم با عدد 50 و رندوم های متفاوت احتمالا میتونم تشخیص بدم که اینا همشون مال یه عدد هستن و رندوم های متفاوت دارن فقط. یکم اینو باید ریاضیاتی تر بررسی کنیم. بزار باز من فکر کنم .
ولی حل جالبیه به هر حال.

 

[HeiSenberG]

آقا زیردیپلم حرف بزنین ماهم بفهمیم

 

[Iman Rage]

خب حل جالبی بود. و یه سری بخشای خیلی خوبی داره. ولی من یه چیزیو بهش مشکوکم.
الان تو یه تابعی ساختی که مثلا توی اون عددی که داری یه رفتار خاصی از خودش نشون میده درسته ؟ با اینکه یه رندوم هم هست.
حالا طرف عدد خودش و یه رندوم میده . اگر عدد B برابر باشه با عدد A و اون رفتار خاص رو از تابع ببینه میتونه ( با اینکه رندوم B هم نمیدونه ) و بگه اینا برابر هستن درسته ؟
اگر اون رندوم توی رفتار تابع تو اون نقطه تاثیر خاصی نذاره میشه نتیجه گرفت که بقیه جاها هم میشه یه سری دیتا بدست آورد. یعنی من اگر یه سری خروجی بگیرم با عدد 50 و رندوم های متفاوت احتمالا میتونم تشخیص بدم که اینا همشون مال یه عدد هستن و رندوم های متفاوت دارن فقط. یکم اینو باید ریاضیاتی تر بررسی کنیم. بزار باز من فکر کنم .
ولی حل جالبیه به هر حال.

نگاه کنید در کل راه حل ما برای مخفی کردن اطلاعاتمون اعداد رندوم هست.
بیایید خودمون رو جای B بگذاریم.Aبه ما تابعی داده و این یعنی اطلاعات.اعداد رندوم بزرگ به خوبی باعث شده است تا Bاز واکاوی تابع به صورت صرف خودداری کنه.
پس به Bبه عنوان یک جعبه سیاه به تابع نگاه میکنه که میتونه یکی از 5 عدد و یک رندوم بده و جواب رو مشاهده کنه(در اینجا اعداد رندوم اطلاعات B رو مخفی می کنند).علی رغم آزمایش های بسیار بدون داشتن عدد رندومA بررسی اینکه جواب به ازای عدد Aچه الگویی باید داشته باشه غیر ممکن به نظر میاد.
نتیجه را برای فرد A ارسال می کند در صورت عدم مشاهده الگو عدد رندوم باید به خوبی نفش خودش در مخفی کردن اطلاعات ایفا کنه.
بنده با ابزار ریاضی این بحث متاسفانه اصلا آشنایی ندارم.
و در کل از توابع غیر خطی مثل همین Hashو این جور چیزها خیلی ارتباط بر قرار نمی کنم...