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

[fsunroo]

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

با یه برنامه حاصل ضرب اعداد عمودی افقی و خونه های 3*3 رو نشون میدیم اگه همه 362880 (یعنی 9!) بودن یعنی درسته!

 

[shnava]

با یه برنامه حاصل ضرب اعداد عمودی افقی و خونه های 3*3 رو نشون میدیم اگه همه 362880 (یعنی 9!) بودن یعنی درسته!

این باگ داره چون مثلا داریم عدد هایی که ضربشون یکی بشه بعد طرف میتونه تکراری استفاده کرده باشه
3*6=2*9

 

[HeiSenberG]

این باگ داره چون مثلا داریم عدد هایی که ضربشون یکی بشه بعد طرف میتونه تکراری استفاده کرده باشه
3*6=2*9

اگه مجموع سطر و ستون (45) رو هم بهش اضافه کنیم باگش برطرف می شه

 

[tiberium]

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

 

[fsunroo]

این باگ داره چون مثلا داریم عدد هایی که ضربشون یکی بشه بعد طرف میتونه تکراری استفاده کرده باشه
3*6=2*9

نه باگ نداره و نیاز نیست مجموع 45 رو اضافه کنیم
اگه حاصل ضرب مثلا به جای 9*2 باشه 6*3 در این صورت حاصل ضرب طرف دیگه و مربع های سه در سه بهم میخوره و حاصل ضرب "همه" یکی نمیشه
ولی حرف @tiberium به نظرم منطقیه
خب یک کار دیگه میتونیم بکنیم که به نظرم عملی نیست ولی از لحاظ تئوری شاید درست باشه
به طرف میگیم یه لیست از hash های جایگشت های مختلف اعداد یک تا نه درست کن (میشه حدود360هزار تا ناقابل ) بعد حالا ما بهم ریخته هش های سطر و سطون و مربع هامون رو بهش میدیم
اگه تمام هش های ما تو اون لیست بود یعنی درسته

درمورد بحث بالا هم که گفتید برنامه ای برای حلش نیست قبلا یه ماژول پایتون دیده بودم الان که سرچ کردم برنامه های زیادی هستن اتفاقا

 

[tiberium]

نه باگ نداره و نیاز نیست مجموع 45 رو اضافه کنیم
اگه حاصل ضرب مثلا به جای 9*2 باشه 6*3 در این صورت حاصل ضرب طرف دیگه و مربع های سه در سه بهم میخوره و حاصل ضرب "همه" یکی نمیشه
ولی حرف @tiberium به نظرم منطقیه
خب یک کار دیگه میتونیم بکنیم که به نظرم عملی نیست ولی از لحاظ تئوری شاید درست باشه
به طرف میگیم یه لیست از hash های جایگشت های مختلف اعداد یک تا نه درست کن (میشه حدود360هزار تا ناقابل ) بعد حالا ما بهم ریخته هش های سطر و سطون و مربع هامون رو بهش میدیم
اگه تمام هش های ما تو اون لیست بود یعنی درسته

درمورد بحث بالا هم که گفتید برنامه ای برای حلش نیست قبلا یه ماژول پایتون دیده بودم الان که سرچ کردم برنامه های زیادی هستن اتفاقا

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

در رابطه با حل.
طبیعتا حل میشه. ولی الگوریتم با زمان چند جمله ای وجود نداره هنوز براش. یعنی چی ؟ یعنی اینکه من میتونم همه حالاتو چک کنم. اگر x تا خونه خالی باشه هر کدوم ۹ حالت دارن. من کافیه ۹ به توان x حالت چک کنم و قطعا به جواب میرسم. ولی این یه الگوریتم توانیه. ۹ به توان x توانیه و چند جمله ای نیست. چند جمله ای یعنی یه عددی مثل x به توان یه عدد ثابت. حتی خیلی بزرگ. این الگوریتم ها "خوب" و قابل قبول به حساب میان.

 

[Moshk]

نه باگ نداره و نیاز نیست مجموع 45 رو اضافه کنیم
اگه حاصل ضرب مثلا به جای 9*2 باشه 6*3 در این صورت حاصل ضرب طرف دیگه و مربع های سه در سه بهم میخوره و حاصل ضرب "همه" یکی نمیشه

اگه به جای همه 9 ها 3 بذاریم و بجای همه 2 ها 6 بذاریم
حاصل ضرب همه چیز اوکی میشه

+هش چیه؟

 

[someon]

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

خب زمانی که رنگ 2 تا ماژیک فرق داره مطمئنا یکی تیره تر و یکی روشن تره.
ما میدونیم که اجسام تیره تر گرمای کمتری رو پس میدن و در نتیجه گرمای بیشتری در خود ذخیره میکنند.
پس به اون انسان کور میگیم(البته دور از جون شما) اگر من سر این دو ماژیک رو بردارم و اونارو در دمای یکسان قرار بدم،سر یکی از ماژیک ها در زمان یکسان بیشتر گرم میشه.اینجوری میفهمه

 

[fsunroo]

اگه به جای همه 9 ها 3 بذاریم و بجای همه 2 ها 6 بذاریم
حاصل ضرب همه چیز اوکی میشه

+هش چیه؟

بله حرفتون درسته...
پس باید همون مجموع 45 رو هم اضافه کنیم ولی همچنان مشکل استفاده از برنامه هست

+هش یکی دو صفحه قبل توضیح داده شد

 

[tiberium]

اون روش کارت های برعکس درست هست ولی تعاملی هست. شما باید بگید بهش که مثلا فلا سطر یا فلان ستون. اینکه یکی دیگه چند تا سطر و ستون و بگه و تو ویدئو نشون بده درسته شاید تقلب بشه. مثلا شما به من یکم پول میدید و میگید سطر ۱ و ۵ و ستون ۲ رو بپرس فقط . و من میپرسم. اگر رندوم باشه منطقیه ولی اگر‌ از قبل هماهنگ شده باشه نه!!! و ما تعاملی با طرف نداریم. پس اون ایده کارتا جواب نمیده

 

[Moshk]

اون روش کارت های برعکس درست هست ولی تعاملی هست. شما باید بگید بهش که مثلا فلا سطر یا فلان ستون. اینکه یکی دیگه چند تا سطر و ستون و بگه و تو ویدئو نشون بده درسته شاید تقلب بشه. مثلا شما به من یکم پول میدید و میگید سطر ۱ و ۵ و ستون ۲ رو بپرس فقط . و من میپرسم. اگر رندوم باشه منطقیه ولی اگر‌ از قبل هماهنگ شده باشه نه!!! و ما تعاملی با طرف نداریم. پس اون ایده کارتا جواب نمیده

اقا ایده کارت ها جواب میده دیگه میتونه همه سطر و ستون ها و 3در 3 هارو بپرسه (بعد از اینکه پرسید کارت هارو دوباره میزاره سرِ جاش مثل حالت اول بشه)
ولی مشکل اینه که کلا میشه تو ویدئو ها تقلب کرد و یجورایی ادیتشون کرد (مثل کارای زک کینگ)
اگه این باگ نباشه که میشه ویدئو رو ادیت کرد این راه باز جواب میده
حالا نمیدونم راه شما با ادیت ویدئو ممکنه توجیح شه یا نه

 

[tiberium]

اقا ایده کارت ها جواب میده دیگه میتونه همه سطر و ستون ها و 3در 3 هارو بپرسه (بعد از اینکه پرسید کارت هارو دوباره میزاره سرِ جاش مثل حالت اول بشه)
ولی مشکل اینه که کلا میشه تو ویدئو ها تقلب کرد و یجورایی ادیتشون کرد (مثل کارای زک کینگ)
اگه این باگ نباشه که میشه ویدئو رو ادیت کرد این راه باز جواب میده
حالا نمیدونم راه شما با ادیت ویدئو ممکنه توجیح شه یا نه

این روش برای هر محاسباتی جواب میده.

 

[someon]

این روش برای هر محاسباتی جواب میده.

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

 

[tiberium]

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

نکته اینجاست که اینطوری باز یه چیزی میفهمه
مثلا میفهمه کدوم تیره تره

می خوایم هیچی نفهمه!

 

[someon]

نکته اینجاست که اینطوری باز یه چیزی میفهمه
مثلا میفهمه کدوم تیره تره

می خوایم هیچی نفهمه!

خب ما که بهش نمیگیم .خودش میفهمه.تنها چیزی که ما بهش میگیم اینه : این ماژیکارو در زمان مساوی در دمای مساوی قرار دادیم
بعد میدیم دستش میبینه یکیش گرم تره میفهمه

 

[tiberium]

خب ما که بهش نمیگیم .خودش میفهمه.تنها چیزی که ما بهش میگیم اینه : این ماژیکارو در زمان مساوی در دمای مساوی قرار دادیم
بعد میدیم دستش میبینه یکیش گرم تره میفهمه

خب الان راجع به رنگ ماژیک ها یه دیتایی داره! ما می‌خوایم zero knowledge باشه. یعنی دانش صفر
یعنی طرف نباید هیچگونه اطلاعاتی بدست بیاره. صفر!

 

[someon]

خب الان راجع به رنگ ماژیک ها یه دیتایی داره! ما می‌خوایم zero knowledge باشه. یعنی دانش صفر
یعنی طرف نباید هیچگونه اطلاعاتی بدست بیاره. صفر!

خب پس چجوری بفهمه رنگ ماژیکا فرق دارن

 

[tiberium]

خب پس چجوری بفهمه رنگ ماژیکا فرق دارن

حل شده این

قرار نبود بفهمه حتی رنگشون فرق داره لزوما. قرار بود بفهمه این دو تا ماژیک یه فرقی دارن خلاصه

 

[tiberium]

خیلی وقت روی این حالتش نزارید . بیاید یکم مساله رو علمی تر و ریاضیاتی ترش‌ کنیم.

من یک سری هدف میدم و بیاید به ترتیب این اهداف رو انجام بدیم.
۱- من می خوام اثبات کنم که برای یه معدله ای مثل x+y = 7 یه جوابی میدونم و نمی خوام راجع به جواب هیچ اطلاعای لو بدم


۲- مساله لگاریتم گسسته رو فرض کنید. من مثلا یه عدد x دارم و g^x mod p رو که مثلا برابر با y هست رو دارم. حالا من اگر به یکی y رو بدم دلیلی نمیشه که x رو بدونم! اینجوری فکر‌کنیو که من یه چیزی رو رمز می کنم و هدفم اینه که اثبات کنم اون داده ای که معادل این رمز هست رو هم میدونم! ولی داده رو ندم. توی این مثل می خوام اثبات کنم x رو میدونم ولی x رو ندم .


فعلا همین ۲ تا رو حل کنیم و بریم جلو

 

[tiberium]

ادامه سوالات :
من تابع E(x) ro به صورت زیر تعریف می کنم
E(x) = g^x mod p
که قبلا سر P و g توافق شده

3- فرض کنید من یه چند جمله ای دارم P(x) و شما یک نقطه s دارید. می خوایم بدون اینکه من نقطه رو به شما بدم و شما چند جمله ای رو به من بدید E(P(s)) ro رو بدست بیاریم. یعنی E اون چند جمله ای توی نقطه ای که شما دارید.
چطور این کارو انجام بدیم ؟


4- حالا فرض کنیم شما به من گفتین جواب مثلا فلان چیزه . شاید این جواب رو رندوم داده باشید ! من می خوام مطمئن باشم که شما این جواب رو بر اساس یه محاسبه و بر اساس یک چند جمله ای دادید . حالا اینکه این چند جمله ای "قابل قبول" هست یا نه رو بعدا میفهمیم. اما هدف اینه که مطمعن باشم بر اساس یه چند جمله ای حاصل شده که شما هم میدونید این چند جمله ای رو .