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

[Iman Rage]

خب حالا لگاریتم گسسته چی بود؟

 

[tiberium]

بچه ها اینجا خاک خورده ها! سوال بعدی. یه نفر ادعا می کنه یه لیستی داره شامل 1000000 عدد که هر کدوم بین 1 تا 10 هست.
شما می خواید با تقریب 99% مطمعن بشید که داره راست میگه.
ایده اولی اینه که یک سری نمونه ببینید از لیست. اگر شما 2 عدد از لیست رو ببینید قطعا نمیتونید با این تقریب مطمعن باشید که همه عددا بین 1 تا 10 هستن.!!! کسی ایده ای داره که با 2 تا query زدن چطور بتونیم مطمئن بشیم با احتمال 99% که همه عدداش بین 1 تا 10 هستن.

سوال سختیه خیلی. فکر کنید. جزو جدیدترین مباحث رمزنگاری الانه

حالا فرض کنید من یه اینترپلیشن از بین این 1 میلیون عدد بگیرم . و اسم تابعم رو f میزارم.

بچه ها بیاید روی این موضوع یکم پیش بریم.
یه اصلی توی ریاضی وجود داره به اسم لم شوارتز-زیپل
و خیلی هم بدیهیه. چیزی که میگه اینه که اگر دو تا چند جمله ای از درجه d داشته باشیم که متفاوت باشن با هم اینها نهایتن توی d نقطه هم رو قطع می کنن.
حالا من میام دو تا تابع تعریف می کنم .
C(X) = x * (x-1) * x-2 * x-3 * ... * x-10
D(x) = x* x-1 * ... * x-1000000
ادعایی که داره میشه اینه که C(f(x)) be ازای ایکس های بین 1 تا 1 میلیون میشه 0.
اینو کسی میتونه ادامه بده ؟ یه سری باگ اینا وجود خواهد داشت که رد می کنیم آروم آروم .

 

[MahanGh]

ازش میخوام که اسم رنگهایی که بلد هست رو بگه و اینجوری به آبی و قرمز میرسه

 

[HeiSenberG]

خب دوستان. از اونجایی که من کل درس و مطالعاتم در رابطه با رمزنگاریه دوست داشتم یه سری از مباحثی که حس کردم شاید خیلی جذاب باشه باهاتون در میون بزارم


مبحث اولی که قراره با هم بررسی کنیم چیزی هست به اسم Zero knowledge
ولی اصلا این چی هست ؟
تاحالا شده بخواید چیزی رو به یکی اثبات کنید بدون اینکه اطلاعاتی به طرف بدین ؟
مثلا شما جواب یه سوالی رو میدونید. می خواید بدون این که جواب رو به طرف بگید یا حتی اطلاعاتی بدین به طرف این موضوع رو اثبات کنید!! این کاملا شدنیه توی علم رمزنگاری
مثال های ریاضیش : مثلا یه معادله هست . A+B+c+D+E = 20 مثلا!!! شما می خواید بدون اینکه این اعداد رو که جواب هستن به طرف بدین اثبات کنید که یه جوابی میدونید که تو این معادله صدق کنه!
اینکه چطوری اینجوری میشه ریاضیات به نسبت قوی ای می خواد که میتونیم بررسی کنیم. اما بیاید از یه مثال ساده تر شروع کنیم .


مساله : من یه فرد کور هستم. و شما 2 تا ماژیک دارید که با هم فرق دارن ( رنگاشون متفاوت هست ). شما می خواید به من این مساله رو اثبات کنید که این 2 ماژیک با هم فرق دارن ولی نمی خواید هیچ اطلاعات دیگه ای به من بدید .
کسی ایده ای داره چطوری اینکارو کنیم ؟

می‌تونیم ماژیکو بهش بدیم و هرکدومو بذاریم تو یه دستش. بعد پشت کنه به ما و یه چیزی بکشه. اگه ما ۱۰ بار درست تشخیص بدیم با کدوم دست کشیده طرف به احتمال ۹۹.۹ باور می‌کنه که فرق دارن

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

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


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

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

اولی: جمع شکلاتا+ضربشون رو جوری حساب می‌کنیم که هر فرد فقط تعداد خودش رو وارد تابع کرده باشه و نتیجه هم فقط به صورت yes(مساوی) no(نامساوی) ارائه بشه

دومی عدد یکی از میلیاردرا منفی می‌شه و دیگری مثبت اگر جمع + بود صرفا جواب علامت + بیاد و نه عدد و اینجوری معلوم می‌شه

سومی ریشه دوم t رو به هرکدوم می‌دیم و بهشون میگیم برای به دست اوردن باید عددشون با یه تابعی که نمی‌دونن چی کار می‌کنه هرکدوم عددشو وارد کنه. اینجوری فرد نه ۹ عدد دیگه رو می‌دونه نه تابع رو. نگید افراد می تونن بفهمن که چی عددی بهشون دادیم. چون تابع رو نمی‌دونن تابع می‌تونه کارای مختلفی انجام بده‌. می‌تونیم به فرد اول ریشه دوم +۱ و به فرد دوم ریشه دوم +۲ بدیم تا تابع تشخیص بده هر عدد مال کی هست و بعد بهش بگیم مثلا عدد فرد n ام رو منهای n کنه و نفر m ام منهای m و بعد در هم ضرب کنه تا t بشه
یا یه کار دیگه هم می‌شه کرد. به هرکدوم یه عدد بدیم و دو تابع. برای فهمیدن این‌که از کدوم تابع استفاده کنه نیاز داره یک شرط yes or no رو داشته باشه که باید از یکی از ۹ نفر دیگه استخراج کنه. یعنی از عدد ۹ نفر دیگه استفاده نکنه و یکی از اون ۹ نفر دیگه صرفا ازشون می‌فهمه که کدوم تابع رو روی عددی که خودش داره اعمال کنه. (یعنی خود عدد افراد دیگر وارد عملیات نمی‌شه) مثلا برای فرد شماره ۱ اینجوری باشه: اقای ۱ اگر عدد شخص دیگر بیشتر از 4.5 بود عددت را در f وارد کن و اگر کوچکتر مساوی بود در g. بعد اینجوری باید اعداد تمام ۹ نفر دیگه مثلا از 4.5 کوچکتر باشه تا نتیجه فرق نکنه. البته یه مشکلی که هست دوتابع کمه و سرجمع ۲ رمز می‌شه که جفتشو امتحان می‌کنه خودش بدون نیاز به دیگری. برای حل این مشکل می‌تونیم ۱۰شرط رو به جای ۱ شرط بگیریم و هر شرط استفاده از یک تابع از بین هر جفت تابع رو برای ما معین کنه (می‌شه ۱۰۲۴ رمز) و دست آخر t تابع دیگری از این ۱۰ تابع باشه (مثلا جمعشون)
کلا جواب هر۳تا مث همه. امیدوارم درست باشه. اگه درست بود بعدیارم جواب می‌دم

 

[Amirhsz]

من یه چیزی به ذهنم رسید اینه که مثلا هربار که به ماژیک A دست زد براش اعلانی پخش شه که با B متفاوته

 

[Amirhsz]

بچه ها اینجا خاک خورده ها! سوال بعدی. یه نفر ادعا می کنه یه لیستی داره شامل 1000000 عدد که هر کدوم بین 1 تا 10 هست.
شما می خواید با تقریب 99% مطمعن بشید که داره راست میگه.
ایده اولی اینه که یک سری نمونه ببینید از لیست. اگر شما 2 عدد از لیست رو ببینید قطعا نمیتونید با این تقریب مطمعن باشید که همه عددا بین 1 تا 10 هستن.!!! کسی ایده ای داره که با 2 تا query زدن چطور بتونیم مطمئن بشیم با احتمال 99% که همه عدداش بین 1 تا 10 هستن.

سوال سختیه خیلی. فکر کنید. جزو جدیدترین مباحث رمزنگاری الانه

فکر کنم ما میتونم مثلا از این اعداد اول میانگین بگیریم. بعد عملیات های مثل میانگین رو انجام بدیم هعی و دوباره رو اونا هم انجام بدیم تا آخر به ۲ اطلاعات برسیم و بعد امتحان کنیم

 

[ili]

این تاپیک نباید بخوابه♻️خواهش می کنم

 

[valter]

نه

 

[ili]

چه ادمای خفنی اینجا بودن😭😭

 

[ili]

@tiberium
@Iman Rage
اقایون این سوالات خلاقانه رو از کجا می اودوید؟