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

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

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

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