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

[tiberium]

فکر کنم یافتم
ببین فرض کنیم که آلیس و باب قبلا روی یک تابع هش خاص توافق کردن
آلیس یک عدد درست (بدون اعشار و بیشتر از یک) انتخاب می کنه در ذهنش(اسمش رو میذاریم A)
و باب هم یک عدد درست انتخاب میکنه در ذهنش (اسمش رو میذاریم B)
باب به آلیس B رو میگه
بعد آلیس سکه رو میندازه
یا شیر میاد یا خط (مثلا برای شیر عدد S رو در نظر میگیریم و برای خط K رو و این موضوع رو هر دو طرف می دونن)
حالا اگه شیر اومد
آلیس هش این عدد رو میگیره SAB
یا اگه خط اومد
KAB
بعد این عدد رو به باب میگه و بعد از باب میخواد که بگه شیر اومده یا خط
حالا باب یک کدوم رو میگه (یا شیر یا خط)
و آلیس یا تایید میکنه
یا تکذیب
بعد از این
...
باب از آلیس عددش رو (که همون A باشه) میپرسه
حالا باید جواب آلیس رو چک کنه
پس این بار باب هش میگیره!
باید جواب هش باب با جواب هش آلیس یکی بشه تا باب بفهمه که آلیس قبلا راست گفته و واقعا درصد جواب درست ۵۰ ۵۰ بوده ...

پ.ن: هش چقدر چیز به درد بخوریه! یه تابعه که نمیشه معکوسش کرد و خلاصه خیلی باحاله!!
پ.ن۲: ممنون از توضیح کاملت @tiberium

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

حتی کوتاه ترم میشه. فرض کنید من سکه میندازم. و از اول باهم طی می کنیم که متن ورودی من نتیجه آزمایش، یک خط تیره و بعد یه عدد رندم هست. مثلا KHAT-124221 یا مثلا SHIR-826251
بعد من میام سکه رو میندازم. و بعد یه عدد رندوم انتخاب می کنم و هش این رو میگیرم و برات میفرستم!!! ولی از رو این نمیدونی جواب چیه. حالا میپرسم تو میگی شیر یا خط؟ و تو میگی مثلا خط. بعد من میگم عدد رندم من اینه( مثلا 241 ) و جواب آزمایش هم مثلا خط بوده. حالا تو میای هش KHAT-241 رو حساب می کنی. اگر با چیزی که قبلا برات فرستاده بودم یکیه یعنی حرفم درسته

حالا یه امکان تقلبی هست. من باید بتونم با همون هش یه ورودی دیگه به صورت SHIR-randnum پیدا کنم ( یه عدد رندم دیگه به عبارتی پیدا کنم که با تغییر جواب آزمایش بازم هش یکسان بشه ). ولی این از لحاظ محاسباتی سخت هست و امکان پذیر‌ نیست!

 

[tiberium]

خب الان لو نمیره x و y ?

 

[tiberium]

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

 

[tiberium]

خب برای همین اون ثابت a رو اضافه کردم...
من انتخاب a رو دلخواه ب عهده خودت گذاشتم
و این a بینهایت عدد میتونه باشه
و با هررر عددی ک ب عنوان a انتخاب کنی
من یک معادله پیشنهاد دادم که توش یه نقطه از خط تو هست D:
ولی حالا ب راه حل های دگم فک‌میکنم... :‌))))

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

 

[tiberium]

حالا ریاضی!
یه فرض خیلی مهمی وجود داره توی علوم کامپیوتر به اسم لگاریتم گسسته . فرض کنید من یه عدد g دارم ( این عدد رندم انتخاب نمیشه و یه سری خصوصیات می خواد ولی مهم نیست الان وارد جزییات بشیم ) و یه عدد اول خیلی خیلی خیلی بزرگ P ( در حد چند میلیون رقم! هرچی این عدد بزرگتر باشه امنیت بیشتر هست. ابررایانه ها بیکار نیستن دنبال عدد اول میگردن . که گاهی تو اخبار میشنوین یه عدد اول پیدا کردن اینقدر میلیون رقم! کشوری که عدد اول های بزرگتری داشته باشه تو این رمزگزاریایی که می کنه امن تر هست سیستمش. )

حالا من اگر تابع y= g ^ x mod p داشته باشم. یعنی g رو به توان x برسونم و باقیماندش رو به P حساب کنم و نمایش بدم . با داشتن y,g,P حساب کردن x یه مساله سخت به حساب میاد . با این میگن مساله ی لگاریتم گسسته

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


مساله َشیر یا خط هم هنوز مونده

خب در رابطه با اینکه سر یک عدد به توافق برسیم :

مساله لگاریتم گسسته رو بخونید از بالا. این یه مساله سخت ریاضی به حساب میاد.
آلیس و باب هر دو به عدد مخفی انتخاب می کنن مثل X_a و X_b
و به صورت عمومی سر یک عدد اول خیلی بزرگ و یه g به توافق میرسن و همه این اعداد رو میبینن! چون عمومی هست.
حالا هر کس این رو محاسبه می کنه .
آلیس این رو برای باب میفرسته g^X_a mod p = Y_a
و باب اینو برای آلیس میفرسته : g^X_b mod p = Y_b

دقت کنید که بر اساس مساله لگاریتم گسسته با دونستن p,g , Y_a نمیشه X_a رو بدست آورد . و همچنین X_b رو.

حالا آلیس این محاسبه رو روی عددی که از طرف باب گرفته انجام میده. باب هم همینطور.
آلیس Y_b ^ X_a mod p = Z
باب Y_a ^ X_b mod p = Z
اگر دقت کنید خروجی یکسانه برای هردو. چون جفتشون میشن g^X_a) ^ X_b)
پس هردو به عدد Z رسیدن ولی افرادی که پیام رسان بودن نمیتونن این Z رو بدست بیارن.

 

[HeiSenberG]

X+Y=7
X+m=10
Y+n=11
m+n=14
درسته؟

 

[tiberium]

X+Y=7
X+m=10
Y+n=11
m+n=14
درسته؟

این چیه الان ؟ کدوم سوال؟

 

[HeiSenberG]

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

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

این چیه الان ؟ کدوم سوال؟

من این اطلاعات رو به شما می‌دم و شما می‌فهمی که می‌دونم x و y چندن

 

[tiberium]

من این اطلاعات رو به شما می‌دم و شما می‌فهمی که می‌دونم x و y چندن

هنوز یه مشکلی وجود داره. مشکل اینجاست که تو اگر بگی x+m مثلا 10 هست از کجا معلوم x رو میدونی ؟ اگر اینو بخوای بگی من ایکس رو میفهمم و اگر نگی معلوم نیست جوابی برای این معادله بدونی.

 

[tiberium]

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

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

 

[tiberium]

نمیفهمم این چطوری به مساله کمک می کنه . میشه بیشتر توضیح بدی؟

 

[SHAMIM.J]

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

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

میتونیم اعدادو تویه برنامه حل کننده جدول سودوکو بذاریم وقتی برنامه حل کرد جوابو نشون نمیدیم فقط تاییدشو نشون میدیم ک جدول ابی میشه ینی قابل حله : ) )

 

[Asdfghjk]

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

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

ماشین تورینگ؟؟؟؟؟؟

 

[tiberium]

راه حلم رو نفهمیدید ینی؟
خب وقتی همه خونه ها صفر بشن این ینی جدول حل داره.

هنوز نفهمیدم

میتونیم اعدادو تویه برنامه حل کننده جدول سودوکو بذاریم وقتی برنامه حل کرد جوابو نشون نمیدیم فقط تاییدشو نشون میدیم ک جدول ابی میشه ینی قابل حله : ) )

برنامه ای وجود نداره .

ماشین تورینگ؟؟؟؟؟؟

نمیفهمم یعنی چطور ؟

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

 

[Moshk]

مثلا تعداد اعدادی که داخل هر خونه میتونن قرار بگیرنو مینویسیم بعد از اون خونه ای که عددش یک هست شروع میکنیم و صفرش میکنیم و از بقیه ی عددهای مرتبط باهاش یکی کم میکنیم و دوباره یه سریا ممکنه یک بشن و تکرار همین مرحله و الی آخرتا جایی که همه خونه ها صفر بشن؟ : دی

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

 

[Moshk]

کافیه جدول رو پیش خودمون پر کنیم بعد به نفر روبرومون ثابت کنیم که در هر سطر و ستون اعداد یک تا نه وجود دارن
مثلا میتونیم جدول رو با کارت بسازیم و بعد خونه هایی که خالیه تو جدول اصلی رو بنویسیم و مخفیش کنیم (مثلا برعکس بذاریم کارتاشو) (دقت کنید که به ترتیب سِیر منطقی حل جدول عددهارو وارد نمیکنیم که بفهمه منطق حل رو)
بعد هر سطر یا ستون رو که خواست، همه کارت هاشو جمع میکنیم و بعد ترتیبشون رو بهم میزنیم بهش تحویل میدیم! میبینه که همه اعداد 1 تا 9 هستن داخلش.

 

[Asdfghjk]

هنوز نفهمیدم

برنامه ای وجود نداره .

نمیفهمم یعنی چطور ؟

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

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

 

[tiberium]

کافیه جدول رو پیش خودمون پر کنیم بعد به نفر روبرومون ثابت کنیم که در هر سطر و ستون اعداد یک تا نه وجود دارن
مثلا میتونیم جدول رو با کارت بسازیم و بعد خونه هایی که خالیه تو جدول اصلی رو بنویسیم و مخفیش کنیم (مثلا برعکس بذاریم کارتاشو) (دقت کنید که به ترتیب سِیر منطقی حل جدول عددهارو وارد نمیکنیم که بفهمه منطق حل رو)
بعد هر سطر یا ستون رو که خواست، همه کارت هاشو جمع میکنیم و بعد ترتیبشون رو بهم میزنیم بهش تحویل میدیم! میبینه که همه اعداد 1 تا 9 هستن داخلش.

آفرین. راه حل خیلی خوبیه!

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

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

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

 

[tiberium]

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

 

[Asdfghjk]

آفرین. راه حل خیلی خوبیه!


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

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

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