رمزگذاری کلید عمومی
اهداف
آشنایی با مفاهیم و کاربردهای رمزنگاری کلید عمومی
مقایسه روشهای رمزنگاری کلید عمومی با رمز نگاری مرسوم (کلید خصوصی)
بررسی یک نمونه از کاربرد کلید عمومی در مکانیسم توزیع کلیدDH
فهرست مطالب
مبانی رمزنگاری کلید عمومی
مقایسه رمزنگاری مرسوم و رمزنگاری کلید عمومی
کاربردهای رمزنگاری کلید عمومی
معرفی چند الگوریتم کلید عمومی
لغت نامه
پیوست ها
مبانی رمزنگاری کلید عمومی
رمزنگاری کلید عمومی اساساً با انگیزه رسیدن به دو هدف طراحی شد:
حل مساله توزیع کلید در روشهای رمزنگاری متقارن
امضای دیجیتال
دیفی و هلمن اولین راه حل را در 1976 ارایه دادند.
کلید های رمزگذاری و رمزگشایی متفاوت اما مرتبط هستند.
رسیدن به کلید رمز گشایی از کلید رمزگذاری از لحاظ محاسباتی ناممکن می باشد.
رمزگذاری امری همگانی میباشد و اساساً نیازی به اشتراک گذاشتن اطلاعات محرمانه ندارد.
رمز گشایی از طرف دیگر امری اختصاصی بوده و محرمانگی پیامها محفوظ میماند.
رمزنگاری کلید عمومی
نمادها و قراردادها
کلید عمومی: کلید رمزگذاری
این کلید را برای شخص A با KUa نشان میدهیم.
کلید خصوصی: کلید رمز گشایی
این کلید را برای شخص A باKRa نشان میدهیم.
نیازمندیهای رمزنگاری کلید عمومی
از نظر محاسباتی برای طرف B تولید یک زوج کلید (کلید عمومی KUb و کلید خصوصی KRb ) آسان باشد.
برای فرستنده تولید متن رمز آسان باشد:
برای گیرنده رمزگشایی متن با استفاده از کلید خصوصی آسان باشد:
نیازمندیهای رمزنگاری کلید عمومی
از نظر محاسباتی تولید کلید خصوصی (KRb) با دانستن کلید عمومی (KUb) غیر ممکن باشد.
بازیابی پیام M با دانستن KUb و C غیر ممکن باشد.
( ویژگی تقارنی ) از هر یک از کلیدها میتوان برای رمزکردن استفاده کرد. در این صورت از کلید دیگر برای رمزگشایی استفاده میشود.
رمزگذاری کلید عمومی-2
برای رمز نگاری کلید عمومی گامهای زیر را برمیداریم:
هر کاربر یک زوج کلید رمزگذاری و رمز گشایی تولید میکند.
کاربران کلید رمزگذاری خود را به صورت عمومی اعلان میکنند درحالی که کلید رمز گشایی مخفی میباشد.
همگان قادر به ارسال پیام رمز شده برای هر کاربر دلخواه با استفاده از کلید رمزگذاری (عمومی) او میباشند.
هر کاربر میتواند با کمک کلید رمزگشایی (خصوصی) پیامهایی که با کلید رمزگذاری (عمومی) او رمز شده رمزگشایی کند.
رمزگذاری کلید عمومی
مقایسه رمزنگاری مرسوم و رمزنگاری کلید عمومی-1
رمزنگاری مرسوم (Conventional Cryptography)
استفاده از یک کلید یکسان و مخفی برای رمزگذاری و رمزگشایی
معایب
مشکل مدیریت کلیدها
نیاز به توافق بر روی کلید پیش از برقراری ارتباط
برای ارتباط n نفر باهم به n(n-1)/2 کلید احتیاج داریم
عدم پشتیبانی از امضاء الکترونیکی
مزایا
با این وجود از الگوریتمهای رمزنگاری با کلید عمومی سریع تر است
مقایسه رمزنگاری مرسوم و رمزنگاری کلید عمومی-2
رمزگذاری مرسوم
برای امن بودن باید:
کلید سری، مخفی نگه داشته شود.
رسیدن به پیام واضح از روی متن رمز شده از نظر محاسباتی نا ممکن باشد.
اطلاع از الگوریتم و داشتن نمونه هایی از پیغام رمز شده برای تعیین کلید کافی نباشد.
مقایسه رمزگذاری مرسوم و رمزگذاری کلید عمومی-3
ملزومات امنیتی(رمزگذاری با کلید عمومی)
تنها یکی از دو کلید باید مخفی بماند
رسیدن به پیام واضح از روی متن رمز شده حتی با داشتن کلید عمومی از نظر محاسباتی نا ممکن باشد.
اطلاع از الگوریتم، داشتن یکی از کلیدها و نیز دراختیار داشتن نمونه پیغام های رمزشده برای تعیین کلید دوم کافی نباشد.
جایگزینی یا تکمیل؟
از نظر کاربردی، رمزگذاری با کلید عمومی بیش از آنکه جایگزینی برای رمزگذاری مرسوم باشد, نقش مکمل آنرا برای حل مشکلات توزیع کلید بازی می کند.
Misconceptions!
دو تصور اشتباه دیگر درباره الگوریتمهای کلید عمومی
رمزنگاری با کلید عمومی امن تر است!
در هر دو روش رمزنگاری امنیت به طول کلید وابسته است.
مسئله توزیع کلید در رمزنگاری با کلید عمومی برطرف شده است
چگونه مطمئن شویم کلید عمومی لزوما متعلق به شخص ادعاکننده است؟!
پس توزیع کلید عمومی آسانتر است، ولی بدیهی نیست.
محرمانگی و احراز هویت به صورت همزمان
رمزگذاری کلید عمومی: محرمانگی و احراز هویت به صورت همزمان
فهرست مطالب
مبانی رمزگذاری کلید عمومی
مقایسه رمزگذاری مرسوم و رمزگذاری کلید عمومی
کاربردهای رمزگذاری کلید عمومی
معرفی چند الگوریتم کلید عمومی
لغت نامه
پیوست ها
کاربردهای رمزگذاری کلید عمومی
دسته بندی کلی کاربردها
رمزگذاری/ رمز گشایی : برای حفظ محرمانگی
امضاء رقمی : برای حفظ اصالت پیام و معین نمودن فرستنده پیام (پیوند دادن پیام با امضاء کننده)
توزیع کلید : برای توافق طرفین روی کلید جلسه مخفی پیش از برقراری ارتباط
جایگاه عملی رمزگذاری کلید عمومی
کلیدهای این نوع از الگوریتمها بسیار طولانی تر از الگوریتمهای مرسوم (کلید خصوصی) میباشند.
الگوریتم RSA با پیمانه 1024 بیتی امنیتی در حد الگوریتمهای متقارن با کلیدهای 80 بیتی دارد.
سرعت الگوریتمهای کلید عمومی از الگوریتمهای رمزگذاری مرسوم پایین تر است.
RSA تقریباً 1000 بار کند تر از رمزهای کلید سری (با امنیت یکسان) میباشد.
جایگاه عملی رمزگذاری کلید عمومی
امروزه کاربرد این الگوریتمها به حل مساله توزیع کلید و امضای دیجیتال محدود میشود. (مطابق اهداف و انگیزه های اولیه طراحی)
حملات به رمزنگاری کلید عمومی
جستجوی فراگیر (Brute force)
محاسبه کلید خصوصی از کلید عمومی
اثبات نشده که غیر ممکن است!
حمله پیام احتمالی (Probable-message attack)
مخصوص رمزنگاری کلید عمومی
فهرست مطالب
مبانی رمزگذاری کلید عمومی
مقایسه رمزگذاری مرسوم و رمزگذاری کلید عمومی
کاربردهای رمزگذاری کلید عمومی
معرفی چند الگوریتم کلید عمومی
لغت نامه
پیوست ها
کلیات الگوریتم رمز نگاری RSA
کلیات
توسط Adleman- Shamir- Rivestدر سال 1977 در MIT ارائه شد
مشهورترین و پرکاربردترین الگوریتم رمزگذاری کلیدعمومی
مبتنی بر توان رسانی پیمانه ایی
استفاده از اعداد طبیعی خیلی بزرگ
امنیت آن ناشی از دشوار بودن تجزیه اعداد بزرگ، که حاصلضرب دو عامل اول بزرگ هستند، می باشد.
مستندات مربوط به آن تحت عنوان PKCS استاندارد شده است.
Public Key Cryptography Standards
نمادگذاری RSA
N : پیمانه محاسبات
e: نمای رمزگذاری
d: نمای رمزگشایی
M: پیام ، عدد صحیح متعلق به
تابع RSA: تالباتبتابتا بتا
تابع معکوس: سیسیسیسیسی
مبانی ریاضی RSA
p و q دو عدد اول میباشند.
(N): تعداد اعداد(کوچکتر ازN) که نسبت به N اول است.
کلید عمومی: {e,n}
کلید خصوصی: {d,n}
قراردادها و پرتکل RSA
هم فرستنده و هم گیرنده مقدار N را می دانند
فرستنده مقدار e را می داند
کلید عمومی : (N , e)
تنها گیرنده مقدار d را می داند
کلید خصوصی : (N, d)
نیازمندیها:
محاسبه Me و Cd آسان باشد
محاسبه d با دانستن کلید عمومی غیرممکن باشد
RSA -مثال
p = 17, q = 11, n = p*q= 187
(n) = 16*10 =160, pick e=7, d.e=1 mod (n) d = 23
روشهای کارا برای محاسبه نما
برای محاسبه ab (mod N) الگوریتمهای متفاوتی ابداع شده است…
فرض کنید bkbk-1…b0 نمایش مبنای 2 عدد b باشد.
بنابراین خواهیم داشت:
الگوریتم توان و ضرب
بر این مبنا میتوان الگوریتم زیر را طراحی نمود:
مثال عددی الگوریتم توان و ضرب
نتیجه الگوریتم توان رساندن سریع پیمانه ایی برای ab mod n که مقادیر a،b و n عبارتند از:
a=7,b=560=(1000110000)2,n=561
حملات ممکن بر RSA
حمله آزمون جامع(Brute Force)
طول کلید با پیدایش هر نسل جدید از پردازنده ها افزایش می یابد، ضمن اینکه قدرت پردازشی هکرها زیاد می شود!
طول کلید معادل تعداد بیتهای پیمانه محاسبات(N) می باشد.
حملات ریاضی
تجزیه N و در نتیجه محاسبه (N)
محاسبه (N) به صورت مستقیم
محاسبه d بدون استفاده از (N)
حمله زمانی
زمان اجرای عملیات رمزگذاری یا واگشایی رمز میتواند اطلاعاتی را در مورد کلید افشاء کند.
حملات ریاضی RSA
مقاله Dan Boneh در دانشگاه Stanford (پیوست) :
Twenty Years of Attacks on the RSA Cryptosystem 1999
راههای مقابله با حمله زمانی به RSA
استفاده از توان رساندن با زمان ثابت محاسباتی.
تابع باید به ازای همه ورودیها زمان ثابتی به طول بیانجامد
اضافه کردن تاخیرهای تصادفی
قرار دادن اعمال اضافی و گمراه کننده در بین محاسبات
ضرب کردن متن رمزشده در یک عدد تصادفی قبل از عملیات به توان رسانی
تحلیلگر از ساختار بیتی متنی که به توان می رسد، مطلع نیست و این حمله زمانی را برای او غیرممکن می سازد
الگوریتم Diffie Hellman
برای تبادل کلید مورد استفاده قرار می گیرد
طرفین بر روی مقادیر و توافق میکنند.
qq یک عدد اول و ha یک مولد (عدد اولی که توانهانش اعداد از 1 تا q -1 را تولید کند) برای این عدد می باشد.
امنیت روش مبتنی بر مشکل بودن لگاریتم گسسته است.
الگوریتم Diffie – Hellman
Alice
Bob
مقدار تصادفی XA را انتخاب میکند
مقدار تصادفیXB را انتخاب میکند
حمله مرد میانی
مهاجم به عنوان کانال ارتباطی میان طرفین عمل میکند.
از نوع حملات فعال محسوب میشود
الگوریتم Diffie-Hellman را تهدید می کند.
حمله مرد میانی
A
K
B
A گمان میکند کلید K1 را با B به اشتراک گذاشته است
B گمان میکند کلید K2 را با A به اشتراک گذاشته است
پایان فصل 5
لغت نامه
توابع یک طرفه
تابع یک طرفه: تابع f(.) را یک طرفه گوییم اگر یافتن مقدار ورودی تابع از روی مقدار خروجی از لحاظ محاسباتی ناممکن باشد.
یک تابع یک طرفه همانند ماشین چرخ گوشت عمل میکند!
از روی خروجی (گوشت چرخ شده ) نمی توان ورودی را بازسازی کرد.
برای تعریف دقیق به پیوست 1 مراجعه نمایید.
وجود توابع یک طرفه صرفاً یک فرض میباشد.
دریچه
اما در برخی کاربردها نیاز داریم تا ورودی تابع یک طرفه را معین کنیم…
وجود یک دریچه در تابع: اطلاعات اضافی که با دانستن آنها میتوانیم تابع را به روشی کارا معکوس کنیم.
توابع یک طرفه دریچه
مجموعه ای از توابع معکوس پذیر fk(.) به طوریکه :
محاسبه y= fk(x) با دانستن k و x آسان باشد
محاسبه fk-1(y) x=با دانستن k و y آسان باشد
محاسبه fk-1(y) x= با دانستن y و مخفی بودن k امکانپذیر نباشد
توابع یک طرفه دریچه به عنوان یک ابزار
توابع یک طرفه دریچه ابزارهای مناسبی برای طراحی الگوریتمهای رمزگذاری و امضای دیجیتال میباشند.
در حقیقت ثابت میشود وجود توابع یک طرفه دریچه شرط لازم و کافی برای وجود الگوریتمهای رمزگذاری و امضای دیجیتال امن میباشد.
کاربردهای برخی الگوریتمهای کلید عمومی