رمزگذاری کلید عمومی

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

رمزنگاری متقارن برای سازمانهایی مانند دولت ها ، نظامی ها و شرکت های بزرگ مالی در ارتباطات طبقه بندی شده مناسب بود.

با گسترش شبکه های رایانه ای ناامن تر در چند دهه گذشته ، نیاز واقعی به استفاده از رمزنگاری در مقیاس بزرگتر احساس شد. به دلیل چالش هایی که برای مدیریت کلیدی با آن روبرو بود ، کلید متقارن غیر عملی بود. این امر باعث ایجاد رمزنگاری کلید عمومی شد.

روند رمزگذاری و رمزگشایی در تصویر زیر به تصویر کشیده شده است -

 

 

مهمترین ویژگی های طرح رمزگذاری کلید عمومی عبارتند از -

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

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

گیرنده باید یک کلید رمزنگاری را منتشر کند که به آن کلید عمومی گفته می شود.

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

الگوریتم رمزگذاری به اندازه کافی پیچیده است که مهاجم را از استنباط متن ساده از متن رمزنگاری و کلید رمزگذاری (عمومی) منع نمی کند.

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

سه نوع طرح رمزگذاری کلید عمومی وجود دارد. ما در بخش های بعدی درباره آنها بحث می کنیم -

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

ما دو جنبه از رمزنگاری RSA را خواهیم دید ، اولا تولید جفت کلید و دوم الگوریتم رمزگذاری-رمزگشایی.

تولید RSA Key Pair
هر شخص یا طرفی که مایل به استفاده از رمزگذاری در ارتباطات است ، باید یک جفت کلید ، یعنی کلید عمومی و کلید خصوصی تولید کند. فرآیند تولید کلیدها در زیر شرح داده شده است -

تولید ماژول RSA (n)

دو سرآغاز بزرگ ، p و q را انتخاب کنید.

محاسبه n = p * q. برای رمزنگاری ناپذیر قوی ، اجازه دهید n تعداد زیادی باشد ، به طور معمول حداقل 512 بیت.

یافتن شماره مشتق شده (e)

عدد e باید از 1 و کمتر از (p - 1) باشد (q - 1).

برای e و (p - 1) (q - 1) هیچ عاملی وجود ندارد به جز 1. به عبارت دیگر دو عدد e و (p - 1) (q - 1) coprime هستند.

کلید عمومی را تشکیل دهید

جفت اعداد (n ، e) کلید عمومی RSA را تشکیل می دهند و عمومی می شوند.

جالب توجه است ، اگرچه n بخشی از کلید عمومی است ، اما دشواری در تعیین تعداد زیاد اصلی تضمین می کند که مهاجمی نمی تواند در زمان محدود دو ابتکار عمل (p & q) را برای به دست آوردن n پیدا کند. این قدرت RSA است.

کلید خصوصی را ایجاد کنید

کلید خصوصی d از p ، q و e محاسبه می شود. برای n و e داده شده ، شماره d منحصر به فرد وجود دارد.

عدد d معکوس e modulo (p - 1) (q - 1) است. این بدان معنی است که d عدد کمتر از (p - 1) (q - 1) است به گونه ای که وقتی با e ضرب شود ، برابر با 1 مدول (p - 1) است (q - 1).

این رابطه به صورت ریاضی به صورت زیر نوشته شده است -

 

ed = 1 mod (p − 1)(q − 1)

الگوریتم توسعه یافته اقلیدسی p ، q و e را به عنوان ورودی در نظر گرفته و d را به عنوان خروجی می دهد.

مثال
نمونه ای از تولید جفت RSA Key در زیر آورده شده است. (برای سهولت در درک ، ابتدای عمل p & q در اینجا مقادیر اندکی است. از نظر عملی ، این مقادیر بسیار بالا هستند).

بگذارید دو مقدمه p = 7 و q = 13. بدین ترتیب ، مدول n = pq = 7 x 13 = 91.

e = 5 را انتخاب کنید ، که یک انتخاب معتبر است زیرا هیچ شماره ای وجود ندارد که فاکتور مشترک 5 و (p - 1) باشد (q - 1) = 6 × 12 = 72 ، به جز 1.

جفت اعداد (n ، e) = (91 ، 5) کلید عمومی را تشکیل می دهد و در دسترس هرکسی که مایل هستیم بتواند پیام های رمزگذاری شده برای ما ارسال کند.

ورودی p = 7 ، q = 13 و e = 5 به الگوریتم Extended Euclidean. خروجی d = 29 خواهد بود.

بررسی کنید که d محاسبه شده با محاسبه صحیح است -

 

de = 29 × 5 = 145 = 1 mod 72

از این رو ، کلید عمومی (91 ، 5) و کلیدهای خصوصی (91 ، 29) هستند.

رمزگذاری و رمزگشایی
پس از ایجاد جفت کلید ، فرایند رمزگذاری و رمزگشایی نسبتاً ساده و محاسباتی آسان است.

جالب اینجاست که RSA بطور مستقیم در مورد رمزنگاری کلید متقارن ، مستقیماً روی رشته های بیت کار نمی کند. این در شماره modulo n کار می کند. از این رو ، لازم است متن ساده را به عنوان یک سری اعداد کمتر از n نشان دهیم.

رمزگذاری RSA
فرض کنید فرستنده مایل است پیام شخصی را به شخصی ارسال کند که کلید عمومی آن (n ، e) باشد.

فرستنده سپس متن ساده را به عنوان یک سری اعداد کمتر از n نشان می دهد.

برای رمزگذاری متن ساده P ، که یک modulo شماره است. فرآیند رمزگذاری یک مرحله ساده ریاضی است -

C = Pe mod n

به عبارت دیگر ، متن رمزنگاری C برابر است با متن ساده P که در زمان خود ضرب شده و سپس مدول n را کاهش می دهد. این بدان معنی است که C نیز عددی کمتر از n است.

با بازگشت به مثال کلید اصلی ما با متن ساده P = 10 ، متن متن C را بدست می آوریم -

C = 105 mod 91

رمزگشایی RSA
فرایند رمزگشایی برای RSA نیز بسیار سرراست است. فرض کنید گیرنده جفت کلید عمومی (n ، e) متن رمزگذاری C را دریافت کرده است.

گیرنده C را به قدرت کلید خصوصی خود بالا می برد d. modulo n نتیجه متن ساده P خواهد بود.

Plaintext = Cd mod n

با بازگشت دوباره به مثال عددی ، رمزنگاری C = 82 با استفاده از کلید خصوصی 29 به شماره 10 رمزگشایی می شود -

Plaintext = 8229 mod 91 = 10

تجزیه و تحلیل RSA
امنیت RSA به نقاط قوت دو عملکرد جداگانه بستگی دارد. رمزنگاری RSA محبوب ترین قدرت رمزنگاری کلید عمومی است که بر اساس دشواری عملی در تعیین فاکتورهای عظیم بسیار زیاد است.

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

تولید کلید - مشکل در تعیین یک کلید خصوصی از کلید عمومی RSA معادل فاکتورسازی مدول n است. بنابراین یک مهاجم نمی تواند از دانش یک کلید عمومی RSA برای تعیین یک کلید خصوصی RSA استفاده کند ، مگر اینکه بتواند عامل n باشد. همچنین این یک تابع یک طرفه است ، رفتن از مقادیر p & q به modulus n آسان است اما معکوس امکان پذیر نیست.

اگر هر یک از این دو عملکرد غیر یک طرفه ثابت شود ، RSA شکسته می شود. در حقیقت ، اگر تکنیکی برای کارخانه سازی کارآمد ایجاد شود ، RSA دیگر ایمن نخواهد بود.

قدرت رمزگذاری RSA به طرز چشمگیری در برابر حملات کاهش می یابد اگر تعداد p و q اولین اعداد بزرگ نباشند و یا کلید عمومی الکترونیکی انتخاب شده تعداد کمی باشد.

رمزنگاری ElGamal
همراه با RSA ، سیستم رمزنگاری کلید عمومی دیگری نیز ارائه شده است. بسیاری از آنها براساس نسخه های مختلف Problem Logarithm Problem ساخته شده اند.

رمزنگاری ElGamal ، به نام Elliptic Curve Variant ، مبتنی بر مسئله لگاریتم گسسته است. این استحکام را از این فرض بدست می آورد که لگاریتم های گسسته را نمی توان در یک بازه زمانی عملی برای یک عدد مشخص یافت ، در حالی که عملکرد معکوس نیرو را می توان به طور مؤثر محاسبه کرد.

اجازه دهید نسخه ساده ElGamal را که با modulo اعداد کار می کند ، برویم. در مورد انواع منحنی بیضوی ، مبتنی بر سیستم های عددی کاملاً متفاوت است.

نسل ElGamal Key Pair
هر کاربر رمزنگاری ElGamal جفت اصلی را از طریق زیر تولید می کند -

انتخاب یک صفحه اصلی بزرگ به طور کلی تعداد اولیه 1024 تا 2048 بیت طول انتخاب می شود.

انتخاب عنصر ژنراتور g.

این عدد باید بین 1 تا p - 1 باشد ، اما نمی تواند عدد باشد.

این تولید کننده گروه ضرب اعداد صحیح modulo p است. این بدان معنی است که برای هر عدد صحیح m از نخست به p ، یک عدد صحیح k وجود دارد به طوری که gk = a mod n.

به عنوان مثال ، 3 ژنراتور گروه 5 است (Z5 = {1 ، 2 ، 3 ، 4).

 

 

انتخاب کلید خصوصی. کلید خصوصی x هر عدد بزرگتر از 1 و کوچکتر از p − 1 است.

محاسبه بخشی از کلید عمومی. مقدار y از پارامترهای p ، g و کلید خصوصی x به شرح زیر محاسبه می شود -

y = gx mod p

به دست آوردن کلید عمومی. کلید عمومی ElGamal از سه پارامتر (p ، g ، y) تشکیل شده است.

به عنوان مثال ، فرض کنید که p = 17 و آن g = 6 (می توان تأیید کرد که 6 ژنراتور گروه Z17 است). کلید خصوصی x می تواند هر عدد بزرگتر از 1 و از 71 کوچکتر باشد ، بنابراین x = 5 را انتخاب می کنیم. مقدار y به شرح زیر محاسبه می شود -

y = 65 mod 17 = 7

بنابراین کلید خصوصی 62 است و کلید عمومی (17 ، 6 ، 7).

رمزگذاری و رمزگشایی
تولید یک جفت کلید ElGamal نسبتاً ساده تر از روند معادل RSA است. اما رمزگذاری و رمزگشایی کمی پیچیده تر از RSA است.

رمزگذاری ElGamal
فرض کنید فرستنده می خواهد متن شخصی را برای شخصی که کلید عمومی ElGamal آن (p ، g ، y) است ارسال کند ، سپس -

فرستنده بیان متن ساده را به عنوان یک سری اعداد و مد اعداد ص.

برای رمزگذاری اولین متن ساده P ، که به عنوان modulo شماره p نشان داده شده است. فرآیند رمزگذاری برای به دست آوردن متن رمزنگاری C به شرح زیر است -

به طور تصادفی عدد k تولید می شود.
دو مقدار C1 و C2 را محاسبه کنید ، جایی که -

C1 = gk mod p
C2 = (P*yk) mod p

 

متن رمزنگاری C را که شامل دو مقدار جداگانه (C1 ، C2) است ، ارسال کنید.

با اشاره به نمونه اصلی کلید ElGamal که در بالا آورده شده است ، متن ساده P = 13 به شرح زیر رمزگذاری شده است -

به طور تصادفی عددی را ایجاد کنید ، بگویید k = 10
دو مقدار C1 و C2 را محاسبه کنید ، جایی که -

 

C1 = 610 mod 17
C2 = (13*710) mod 17 = 9

 

متن رمزنگاری C = (C1 ، C2) = (15 ، 9) را ارسال کنید.

رمزگشایی ElGamal
برای رمزگشایی رمزنگاری متن (C1 ، C2) با استفاده از کلید خصوصی x ، دو مرحله زیر انجام می شود -

معکوس مدولار (C1) x modulo p ، که (C1) -x است را محاسبه کنید ، به طور کلی به عنوان عامل رمزگشایی از آن یاد می شود.

متن مثال را با استفاده از فرمول زیر بدست آورید -

 

C2 × (C1)-x  mod p = Plaintext

در مثال ما ، برای رمزگشایی رمزنگاری C = (C1 ، C2) = (15 ، 9) با استفاده از کلید خصوصی x = 5 ، فاکتور رمزگشایی است

15-5  mod 17 = 9

استخراج متن ساده P = (9 9 9) مود 17 = 13.

تجزیه و تحلیل ElGamal
در سیستم ElGamal ، هر کاربر یک کلید خصوصی x دارد. و دارای سه مؤلفه کلید عمومی - modulus Prime p، generator g و عمومی Y = gx mod p. استحکام ElGamal مبتنی بر مشکل مشکل لگاریتم گسسته است.

اندازه کلید امن معمولاً> 1024 بیت است. امروزه حتی از کلید بلند 2048 بیت نیز استفاده می شود. در جلو سرعت پردازش ، Elgamal بسیار کند است ، آن را به طور عمده برای پروتکل های تأیید اعتبار کلیدی استفاده می شود. با توجه به راندمان پردازش بالاتر ، انواع Eliptic Curve ElGamal به طور فزاینده ای محبوب می شوند.

رمزنگاری منحنی بیضوی (ECC)
رمزنگاری Elliptic Curve Cryptography (ECC) اصطلاحی است که برای توصیف مجموعه ای از ابزارها و پروتکل های رمزنگاری استفاده می شود که امنیت آن براساس نسخه های خاص از مشکل لگاریتم گسسته است. از modulo اعداد استفاده نمی کند.

ECC براساس مجموعه اعدادی است که با اشیاء ریاضی که منحنی بیضوی نامیده می شوند در ارتباط است. قوانینی برای اضافه کردن و محاسبه تکثیر از این اعداد وجود دارد ، دقیقاً همانطور که برای modulo اعداد وجود دارد.

ECC شامل انواع بسیاری از طرح های رمزنگاری شده است که در ابتدا برای شماره های مدولار مانند رمزگذاری ElGamal و الگوریتم امضای دیجیتال طراحی شده اند.

اعتقاد بر این است که هنگام استفاده از نقاط روی منحنی بیضوی ، مشکل لگاریتم گسسته بسیار سخت تر است. این امر باعث تغییر از مدول اعداد به نقاط بر روی منحنی بیضوی می شود. همچنین اگر از انواع مبتنی بر منحنی بیضوی استفاده کنیم ، می توان با کلیدهای کوتاه تر سطح امنیتی معادل آن را بدست آورد.

کلیدهای کوتاهتر منجر به دو مزیت می شوند -

سهولت مدیریت کلید
محاسبه کارآمد
این مزایا باعث می شود انواع مبتنی بر منحنی بیضوی از طرح رمزگذاری برای کاربردهایی که منابع محاسباتی در آن محدود هستند بسیار جذاب باشد.

طرح های RSA و ElGamal - یک مقایسه
بگذارید به طور خلاصه طرح های RSA و ElGamal را در مورد جنبه های مختلف مقایسه کنیم.