مباحث بنیادین در علم رمزنگاری

[Eshpilen]

اینجا فعلا لیست یکسری مقاله های مهم رو میذارم جمع آوری و حفظ بشه، بعدا اگر وقت کردم شاید توضیح و مطلب بیشتری به فارسی هم بذارم.

https://en.wikipedia.org/wiki/Computatio...assumption

https://en.wikipedia.org/wiki/Concrete_security

https://en.wikipedia.org/wiki/Provable_security

https://en.wikipedia.org/wiki/Strong_secrecy

https://en.wikipedia.org/wiki/Semantic_security

https://en.wikipedia.org/wiki/Probabilistic_encryption

https://en.wikipedia.org/wiki/Security_parameter

https://en.wikipedia.org/wiki/Digital_signature_forgery

https://en.wikipedia.org/wiki/Informatio...c_security

https://en.wikipedia.org/wiki/Classical_cipher

https://en.wikipedia.org/wiki/Confusion_and_diffusion

https://en.wikipedia.org/wiki/Substituti...on_network

https://en.wikipedia.org/wiki/Feistel_cipher

https://en.wikipedia.org/wiki/RSA_problem

البته بعضی از این موارد که گذاشتم بیشتر تعریف های عمومی هستن که آدم باید بدونه تا مطالب تخصصی این رشته رو بتونه به خوبی مطالعه کنه. مثلا Classical_cipher یا Digital_signature_forgery از این نوع هستن که بیشتر تعریف اصطلاحات هستن تا اینکه تئوری های بنیادین این رشته باشن.
فعلا نمیخوام خیلی مرزبندی کنم و محدودیتی هم نیست، بنابراین هرچی پیدا میکنم بنظرم میرسه که اطلاع پیشاپیش از اون میتونه خیلی مفید باشه همینطور قاطی پاتی میذارم :D
من خودم مدتها سردرگم بودم سر خیلی این موارد و تازگی یک دید و ساختار کلی تر و روشن تری رو متوجه شدم. شاید یک دلیلش این بود که انگار مقاله های ویکیپدیا به مرور زمان زیادتر و جامع تر و بهتر میشن! البته هم که علم رمزنگاری رشتهء کمتر شناخته شده ای است و بخاطر پیچیدگی ها و گستردگی زیادی که داره و دائم به مرور زمان در حال پیشرفت و روشن شدن و کاملتر شدن تئوری ها و تعریف ها هست، این مسائل توش طبیعیه. افراد زیادی وجود ندارن که بینش کلی جامع و عمیق و دقیقی از این رشتهء گسترده و پیچیده داشته باشن، و بنابراین پیدا کردن منابع کامل و خوب دسته بندی شده و روشن و همه فهم در این زمینه دشواره (حداقل تاحالا که بوده). متخصصان علم رمزنگاری در دنیای خودشون زندگی میکنن و با افراد معمولی معمولا کار و ارتباط چندانی ندارن و اهمیت خاصی هم نمیدن که بیان مفاهیم پیچیده و ریاضی وار این رشته رو در سطح عمومی تر و همه فهمی ارائه کنن.

[Eshpilen]

خب لینک اول Computational hardness assumption داره چی میگه.
میگه در علم رمزنگاری مدرن دنبال این هستن که الگوریتم هایی ایجاد کنن که بشه امنیت اونا رو به روشی بقدر کافی قابل اطمینان ثابت کرد (طبیعتا با متدهای منطقی/ریاضی). چون میدونیم که در دنیای علم و منطق، تکیه بر حدس و تصور و احساسات اعتباری نداره و باید تاجاییکه شدنی هست به اثبات و روشنی و اطمینان رسید، که بالاترین حد این اثبات معمولا اثبات با ریاضیات است. اما حتی در این شکل هم سطوح اثبات با هم فرق میکنن. بعضی اثبات ها کامل و مطلق هستن، ولی خیلی دیگر اثبات های کامل و مطلق ندارن و مثلا بر یکسری فرض هایی بنا شدن که عموما تصور میشه و احتمال زیادی داده میشه که درست هستن و تجربه و شواهد بر این امر صحه میگذارند اما بهرحال اثبات منطقی/ریاضی براشون وجود نداره.
در بعضی موارد، الگوریتم ها دارای امنیت اثبات شدنی از نوع نظریهء اطلاعات هستن که قوی ترین نوع امنیته که مشروط و موکول روی فرضهای ثابت نشده و یا محدودیت های دنیای واقعی نیست؛ بطور مثال الگوریتم one-time pad. ولی در خیلی موارد هم طراحی چنین الگوریتم هایی و اثبات امنیت اونا در عمل ممکن نیست؛ در این موارد متخصصان به امنیت از نوع توان پردازشی عقب نشینی میکنن که سطح محدودتر و پایین تری از اثبات و امنیت رو داراست. در این سطح، امنیت بر اساس محدودیت توان پردازشی در دسترس بشر فرض میشه. یعنی میگن این الگوریتم ها با در نظر گرفتن اینکه در واقعیت توان پردازشی در دسترس انسان محدودیت های خاص فعلی و آیندهء نزدیک یا دور رو داره، امن هستن و کسی عملا قادر به شکست اونا نیست چون مثلا نیاز به زمان و/یا انرژی بسیار بسیار زیادی هست که در نتیجه انجامش عملا غیرممکنه یا اهمیتی نداره. طبیعتا برای تعریف و اثبات این نوع از امنیت، بر میزان سختی انجام یک عملیات خاص، تکیه میشه (اینکه چقدر نیاز به منابع پردازشی/زمان/انرژی داشته باشه). اما چون خود اثبات «حداقل میزان سختی انجام یک عملیات خاص» کار دشواریه و در خیلی موارد کسی نتونسته تاحالا این کار رو بکنه، بنابراین خیلی از این عملیات تنها فرض میشن که فلان قدر یا بقدر کافی سخت هستن، چون تاحالا کسی نتونسته راه ساده تری برای انجام اونا پیدا کنه. و به این هست که میگن Computational hardness assumption، یعنی «فرض دشواری پردازشی». نکته: بنده اهل برگردان های فارسی نیستم و اونا رو در خیلی موارد چندان مناسب و مفید نمی بینم و ترجیح میدم از همون عبارت های انگلیسی خودشون استفاده کنم، و اینطور ترجمه ها رو صرفا برای درک مطلب میذارم که شاید ترجمه های چندان دقیق و درستی هم نباشن.
بطور مثال میدونیم که اگر کسی بتونه الگوریتمی از نوع Polynomial time برای فاکتورگیری از اعداد صحیح بزرگ پیدا کنه، الگوریتم رمزنگاری RSA قطعا بطور کامل شکسته میشه، ولی خب کسی تاحالا نتونسته چنین روش کارایی برای فاکتورگیری اعداد صحیح بزرگ پیدا کنه، با وجود اینکه خیلی افراد خیلی ریاضیدان ها در تاریخ برای این کار تلاش کردن؛ و بنابراین فرض رو بر این میذاریم که فاکتورگیری از اعداد صحیح بزرگ ماهیتا عملیات ناکارایی هست (به نسبت بزرگی عدد بصورت تصاعدی به پردازش نیاز داره). کسی نمیدونه آیا واقعا هیچ روش کارایی برای فاکتورگیری اعداد وجود داره یا نه که بشریت روزی بتونه بهش دست پیدا کنه، ممکنه وجود داشته باشه و ممکنه وجود نداشته باشه، کسی نتونسته چیزی رو در این مورد ثابت کنه، ولی هرکس تلاش کرده چنین روشی/الگوریتمی پیدا کنه موفق نشده، و بنابراین میشه گفت چنین الگوریتمی احتمالش زیاده اصولا از نظر ریاضی ممکن نیست یا حداقل دست یافتن بهش خیلی دشواره و چندان محتمل نیست به زودی محقق بشه (البته بحث رایانه های کوانتمی و الگوریتم Shor که برای فاکتورگیری اعداد بزرگ قابل استفاده است جداست و ما فعلا کاری با اون نداریم چون فیلد جداگانه ایه و هنوز هم رایانه های کوانتمی در مقیاس بزرگ تحقق پیدا نکردن و بنظر نمیرسه چندان هم به این امر نزدیک باشیم یا اصلا هیچوقت بالاخره شدنی بشه).

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