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

[tiberium]

چرا تنبل شدید دوستان) فکر کنید و ایده بزنید تاپیک نخوابه و خاک نخوره مباحث پر کاربردی هستن ررای اونایی که می خوان بیان علوم کامپیوتر و رمز

 

[Moshk]

کلیت قضیه اون x+y=7 هم دقیقا اینه که یه ایکسی میدونم میخوام ثابت کنم میدونم!
پس کافیه رو دو فکر کنیم
این احساس میکنم باید اینجوری باشه که مثل اون حرکت فرد کور و دوتا ماژیک، بی نهایت بار یه الگوریتمی رخ بده که تهش اون فرد به این برسه که من واقعا یه عدد خاص میدونم!
منطقا هم باید اون یه متغیر تصادفی داشته باشه. (مثل اینکه با کدوم ماژیک علامت بزنه)
یخورده فکر میکنم به چیز دقیقی رسیدم اعلام میکنم

این پست صرفا در راستای این بود که تنبل نشدیم ((:

 

[tiberium]

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

ببین این دو تا مساله یکی نیستن. برای حله دو متغیره به یه متغیره نیاز داریم. ولی مفهوم دو متغیره ساده تره.

 

[tiberium]

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

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

 

[Iman Rage]

میانگین و واریانس رو بپرسیم کارمون راه نمیفته؟

 

[tiberium]

اخه شاید رو هوا بگه. چطوره میتونی اعتناد کنی ؟ اینجا نمیتونه حتی رو هوا بگه. لو میره

 

[Iman Rage]

تو این راه حلی که پیشنهاد میشه دوباره همه چیز شفاف است؟یعنی طرف مقابل میدونه قصد شما از سوال پرسیدن چیه؟

 

[tiberium]

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

 

[Iman Rage]

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

 

[tiberium]

آها. خب ببین دو بزار آروم آروم پیش بریم.

یه سوالی که قبلا هم بود. فرض کن x+y=7 . تو می خوای به یکی اثبات کنی یه جواب از این رابطه میدونی ولی نمی خوای جواب رو بگی. چی کار می کنی؟ ( از مساله لگاریتم گسسته استفاده کن )

 

[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]

نه