• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

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

  • شروع کننده موضوع
  • #121

tiberium

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

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

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

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

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
خب الان لو نمیره x و y ?
 
  • شروع کننده موضوع
  • #123

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
آها من تازه راهتو فهمیدم. جالبه ایدت . تو میگی‌میتونی یه خطی معرفی کنی که اینو قطع کنه پس یه نقطه ازشو میدونی! قشنگه ولی بازم اگر خطت رو به من معرفی کنی من میفهمم اون نقطه رو
 
  • شروع کننده موضوع
  • #124

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
خب برای همین اون ثابت a رو اضافه کردم...
من انتخاب a رو دلخواه ب عهده خودت گذاشتم
و این a بینهایت عدد میتونه باشه
و با هررر عددی ک ب عنوان a انتخاب کنی
من یک معادله پیشنهاد دادم که توش یه نقطه از خط تو هست D:
ولی حالا ب راه حل های دگم فک‌میکنم... :‌))))
آره ولی من یه جواب رو یاد میگیرم. و نمی خوایم این اتفاق بیفته.
از مساله لگاریتم گسسته میشه ایده گرفت؟
 
  • شروع کننده موضوع
  • #125

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
حالا ریاضی!
یه فرض خیلی مهمی وجود داره توی علوم کامپیوتر به اسم لگاریتم گسسته . فرض کنید من یه عدد g دارم ( این عدد رندم انتخاب نمیشه و یه سری خصوصیات می خواد ولی مهم نیست الان وارد جزییات بشیم ) و یه عدد اول خیلی خیلی خیلی بزرگ P ( در حد چند میلیون رقم! هرچی این عدد بزرگتر باشه امنیت بیشتر هست. ابررایانه ها بیکار نیستن دنبال عدد اول میگردن . که گاهی تو اخبار میشنوین یه عدد اول پیدا کردن اینقدر میلیون رقم! کشوری که عدد اول های بزرگتری داشته باشه تو این رمزگزاریایی که می کنه امن تر هست سیستمش. )

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

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


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

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

مساله لگاریتم گسسته رو بخونید از بالا. این یه مساله سخت ریاضی به حساب میاد.
آلیس و باب هر دو به عدد مخفی انتخاب می کنن مثل 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

کاربر حرفه‌ای
ارسال‌ها
339
امتیاز
2,062
نام مرکز سمپاد
شهید بهشتی
شهر
خرم آباد
سال فارغ التحصیلی
1399
X+Y=7
X+m=10
Y+n=11
m+n=14
درسته؟
 
  • شروع کننده موضوع
  • #127

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات

HeiSenberG

کاربر حرفه‌ای
ارسال‌ها
339
امتیاز
2,062
نام مرکز سمپاد
شهید بهشتی
شهر
خرم آباد
سال فارغ التحصیلی
1399
خب دوستان من یکم سوالای فنی تر میزارم. که حالا لزوما دانش خیلی زیادی هم نخوان . به همین چیزایی که تا الان خوندیم حل میشن.

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

این چیه الان ؟ کدوم سوال؟
من این اطلاعات رو به شما می‌دم و شما می‌فهمی که می‌دونم x و y چندن
 
  • شروع کننده موضوع
  • #129

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
من این اطلاعات رو به شما می‌دم و شما می‌فهمی که می‌دونم x و y چندن
هنوز یه مشکلی وجود داره. مشکل اینجاست که تو اگر بگی x+m مثلا 10 هست از کجا معلوم x رو میدونی ؟ اگر اینو بخوای بگی من ایکس رو میفهمم و اگر نگی معلوم نیست جوابی برای این معادله بدونی.
 
  • شروع کننده موضوع
  • #130

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
خب از اونجایی که تاپیک خوابیده من یه سوال دیگه میزارم که فکر کنید.

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

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
نمیفهمم این چطوری به مساله کمک می کنه . میشه بیشتر توضیح بدی؟
 

SHAMIM.J

کاربر فوق‌حرفه‌ای
ارسال‌ها
924
امتیاز
10,003
نام مرکز سمپاد
.
شهر
.
سال فارغ التحصیلی
93
دانشگاه
ع پ گلستان
رشته دانشگاه
نرسینگ
خب از اونجایی که تاپیک خوابیده من یه سوال دیگه میزارم که فکر کنید.

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

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

Asdfghjk

...
ارسال‌ها
263
امتیاز
695
نام مرکز سمپاد
...
شهر
...
سال فارغ التحصیلی
1391
رشته دانشگاه
مهندسی نرم افزار
خب از اونجایی که تاپیک خوابیده من یه سوال دیگه میزارم که فکر کنید.

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

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
راه حلم رو نفهمیدید ینی؟
خب وقتی همه خونه ها صفر بشن این ینی جدول حل داره.
هنوز نفهمیدم
میتونیم اعدادو تویه برنامه حل کننده جدول سودوکو بذاریم وقتی برنامه حل کرد جوابو نشون نمیدیم فقط تاییدشو نشون میدیم ک جدول ابی میشه ینی قابل حله : ) )
برنامه ای وجود نداره .
ماشین تورینگ؟؟؟؟؟؟
نمیفهمم یعنی چطور ؟

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

Moshk

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,141
امتیاز
2,880
نام مرکز سمپاد
شهید بهشتی 1
شهر
ساری
سال فارغ التحصیلی
1397
مثلا تعداد اعدادی که داخل هر خونه میتونن قرار بگیرنو مینویسیم بعد از اون خونه ای که عددش یک هست شروع میکنیم و صفرش میکنیم و از بقیه ی عددهای مرتبط باهاش یکی کم میکنیم و دوباره یه سریا ممکنه یک بشن و تکرار همین مرحله و الی آخرتا جایی که همه خونه ها صفر بشن؟ : دی
خب ببین با این روش اگه طرف کنارت بشینه و ببینه کدوم عدد یک رو داری صفر میکنی میره همون خونه جدول رو با تک عددی که میتونه بذاره پر میکنه و طبق حرکات تو جدول رو میسازه
ممکنه جدولی اول کار یک نداشته باشه و حل شه :-?
 
  • لایک
امتیازات: z.a97

Moshk

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

Asdfghjk

...
ارسال‌ها
263
امتیاز
695
نام مرکز سمپاد
...
شهر
...
سال فارغ التحصیلی
1391
رشته دانشگاه
مهندسی نرم افزار
هنوز نفهمیدم

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

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

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

tiberium

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

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

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

tiberium

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,057
امتیاز
1,051
نام مرکز سمپاد
شهید بهشتی سمنان
شهر
سمنان
سال فارغ التحصیلی
1389
مدال المپیاد
المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی فن آوری اطلاعات
خب دوستان حالا همین مساله ی سودوکو رو فکر کنید. من یه کانال یوتیوب دارم مثلا که هر هفته یه سودوکو برا حل میزارم. یه هفته سودوکوش خیلی سخته و همه تو کامنت ها ادعا می کنن که چطوری ممکنه! اصلا از کجا معلوم که حل داره. حالا من با هیچکدومشون تعاملی ندارم ! ولی می خوام اثبات کنم که حل داره و من حلش رو میدونم. و از طرفی نمی خوام هیچگونه اطلاعاتی راجع به حلش بدم.هر کس باید بتونه این ادعای من رو اعتبارسنجی کنه.
این مساله شاید یکم سخت باشه پس زود جا نزنید و فکر کنید !
 

Asdfghjk

...
ارسال‌ها
263
امتیاز
695
نام مرکز سمپاد
...
شهر
...
سال فارغ التحصیلی
1391
رشته دانشگاه
مهندسی نرم افزار
آفرین. راه حل خیلی خوبیه!


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

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