موضوع مقاله: آراس‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # آراس‌ای | مقدمه: در این چنین سیستم‌های رمزنگاری، کلید رمزگذاری عمومی است و از کلید رمزگشایی که مخفی است، جداست. | ## بخش 1: آراس‌ای | در آراس‌اِی، این عدم تقارن مبتنی بر این است که تجزیه از عددی که ضرب دو عدد اول بزرگ است در عمل بسیار دشوار است. این روش، نخستین روش مورد اعتماد در بین روش‌های رمزنگاری دیگر است و یکی از بزرگ‌ترین پیشرفت‌ها در زمینهٔ رمزنگاری به حساب می‌آید. آراس‌ای همچنان به صورت گسترده‌ای در تبادلات الکترونیکی استفاده می‌شود و در صورت استفاده درست با کلیدهای طولانی کاملاً امن به نظر می‌رسد. یک ریاضی‌دان انگلیسی به نام Clifford Cocks، که برای ستاد ارتباطات دولت بریتانیا کار می‌کرد، سیستمی معادل این سیستم را در سال ۱۹۷۳ پیاده‌سازی کرده بود، که تا سال ۱۹۷۳ به صورت محرمانه باقی ماند. یک کاربر RSA، یک کلید عمومی را بر اساس دو عدد اول بزرگ را همراه با یک مقدار تصادفی ساخته و به صورت عمومی منتشر می‌کند. هر کسی می‌تواند از این کلید عمومی برای رمزگذاری یک پیام استفاده کند، اما تنها کسی که آن دو عدد اولی که کلید بر اساس آن‌ها ساخته شده را می‌داند، قادر به رمزگشایی پیام است. تاکنون هیچ روشی برای شکست دادن این سیستم (در صورت استفادهٔ کلید به اندازهٔ کافی بزرگ) منتشر نشده‌است. RSA به صورت نسبی، الگوریتم کندی است و به همین علت، کمتر برای رمزگذاری مستقیم اطلاعات کاربر استفاده می‌شود. بیشتر اوقات، RSA کلید رمزگشایی شده را برای الگوریتم کلید متقارن انتقال می‌دهد که در عوض قادر است توده ای از عملیات رمزگذاری-رمزگشایی را با سرعتی بسیار بالاتر انجام دهد. آن‌ها هم چنین امضای مجازی را معرفی کردند و تلاش کردند تا نظریه اعداد را نیز اعمال کنند. رمزنگاری به روش کلید عمومی به معنی استفاده از کلید عمومی برای رمزنگاری و پنهان کردن اطلاعات است. ویژگی این روش آن است که هر کدام از این کلیدها می‌توانند اطلاعاتی را که کلید دیگر رمزنگاری کرده‌است رمزگشایی کند. رونالد ریوست، ادی شامیر، و لئونارد آدلمن در مؤسسه فناوری ماساچوست (اِم‌آی‌تی) تلاش‌های بسیاری برای ساختن یک تابع یک طرفه که معکوس کردن آن بسیار دشوار بود کردند. ریوست و شامیر که دانشمند حوزه علوم کامپیوتر بودند توابع بسیاری را پیشنهاد دادند در حالی که آدلمن که یک ریاضی‌دان بود، مسئول یافتن نقاط ضعف این توابع بود. آن‌ها رویکردهای متعددی از جمله رویکردی بر اساس مسئلهٔ کوله پشتی و «جایگشت چند جمله ای» را امتحان کردند. در آوریل سال ۱۹۷۷، پس از این که از یک جمع دانشجویی بازگشتند و مقداری نوشیده بودند، ریوست که نمی‌توانست بخوابد روی مبل دراز کشید و شروع به مطالعهٔ یک کتاب ریاضی کرد و کل شب را به تفکر راجع به تابع مذکور کرد. هرچند روش‌های اولیه آن پیشتر در سال ۱۹۷۳ (میلادی) توسط فردی به نام کلیفورد کاکس که در ستاد روابط دولت بریتانیا بدست آمده بود اما تا سال ۱۹۷۷ اولاً الگورتیم رمزنگاری او کاملاً محرمانه بود و دوم اینکه به سادگی آنچه در سال ۱۹۷۶ مطرح شد نبود. گرچه این الگوریتم در زمانی که توسط کاکس کشف شد به علت هزینهٔ بسیار زیاد کامپیوترهایی که برای پیاده‌سازی آن لازم بودند، هیچ‌گاه پیاده‌سازی نشد. RSA کودکان یا kid-RSA، یک الگوریتم رمزگشایی کلید عمومی ساده‌سازی شده‌است که در سال ۱۹۹۷، برای اهداف آموزشی معرفی شد. ثبت اختراع اختراع ۴٬۴۰۵٬۸۲۹ در سال ۱۹۸۳ به موسسهٔ فناوری ماساچوست یا MIT با عنوان «سیستم و روش ارتباطات رمزنگاری» که در سال ۱۹۸۳از این الگوریتم استفاده کرد، اهدا شد. چگونگی کارکرد کلیات RSA شامل ۴ مرحله است: ساخت کلید، توزیع کلید، رمزنگاری و رمزگشایی. یک اصل اساسی در RSA این است که یافتن سه عدد صحیح مثبت بسیار بزرگ مانند e, n و d که رابطهٔ زیر برایشان بر قرار باشد، عملی است. به بیان دیگر همه می‌توانند یک پیام را رمز کنند اما فقط صاحب کلید خصوصی می‌تواند پیام را باز کند و بخواند. کلید عمومی توسط اعداد صحیح n و e نمایش داده می‌شود و کلید خصوصی، توسط عدد صحیح d(گرچه n در فرایند رمزگشایی هم استفاده می‌شود بنا بر این ممکن است قسمتی از کلید خصوصی هم در نظر گرفته شود). m، نمایان گر پیام است که از قبل توسط یک تکنیک خاص آماده شده‌است و در ادامه این تکنیک شرح داده شده‌است. هر چند از لحاظ ریاضی کلیدهای عمومی و خصوصی با یکدیگر ارتباط دارند اما تقریباً محال است که کسی بتواند حتی با تجیهزات پیشرفته و صرف وقت زیاد با داشتن یکی از کلیدها، دیگری را تشخیص دهد. در واقع می‌توان گفت که با توجه به سطح دانش کنونی و سامانه‌های رایانه‌ای موجود، الگوریتم رمزنگاری و ارتباط میان کلیدها تقریباً غیرقابل شکستن است. آراس‌ای مبتنی بر توان‌رسانی پیمانه‌ای است و از اعداد طبیعی خیلی بزرگ استفاده می‌کند. ساخت کلید مراحل زیر برای ساخت کلید طی می‌شود: دو عدد اول بزرگ و را به صورت تصادفی بیابید به‌طوری‌که . برای اهداف امنیتی، p و q باید به صورت تصادفی انتخاب شوند، و در اندازه مشابه باشند اما طول آن‌ها در حد چند رقم متفاوت باشد تا تجزیه را کمی دشوارتر کند. معمول‌ترین مقدار انتخاب شده برای e، حدود عدد۲۱۶ یک که برابر با ۶۵۵۳۶ است می‌باشد. کوچک‌ترین و سریع‌ترین مقدار ممکن برای e، عدد ۳ است اما چنین مقدار کمی نشان داده‌است که در بعضی ساختارها امنیت کم تری را ایجاد می‌کند. این مقدار می‌تواند به صورت کارآمدی توسط الگوریتم تعمیم‌یافته اقلیدس پیدا شود از آن جایی که d و اول هستند، این معادله یک فرمی از قضیه بزو است که در آن d یکی از ضریب‌ها است. کلید عمومی تشکیل می‌شود از: عدد n (عدد مشترک) عدد e (عدد عمومی) کلید خصوصی تشکیل می‌شود از: عدد n (عدد مشترک) عدد d (عدد خصوصی) کلید خصوصی به صورت‌های دیگری غیر از ممکن است نگهداری شود. در تمام مراحل باید اجزای کلید خصوصی سری نگه داشته شود، دو عدد و اگر به عنوان صورتی از کلید خصوصی نگهداری نشود بهتر است به شیوه‌ای امن نابود شوند؛ زیرا با این دو عدد تمام اعداد و ، قابل محاسبه خواهند بود. اگر آن‌ها تصمیم بگیرند که از RSA استفاده کنند، باب باید کلید عمومی آلیس را برای رمز گذاری پیام بداند و آلیس باید از کلید خصوصی ای که در اختیار دارد استفاده کند تا پیام را رمزگشایی نماید. بنابر این برای این که باب قادر باشد پیام رمز شده اش را ارسال کند، آلیس کلید عمومی (n,e) خود را توسط یک مسیر مطمئن ولی نه لزوماً مخفی به باب منقل می‌کند. رمزنگاری پیام حالا که باب کلید عمومی آلیس را دریافت کرد، قصد دارد پیام M را به توسط الگوریتم RSA به آلیس بفرستد. باب باید پیام خود را در قالب یک عدد (m) در بیاورد به‌طوری‌که این فرایند برگشت‌پذیر بوده و روی آن توافق شده باشد و شناخته شده باشد. بدیهی است اگر پیام بزرگ‌تر از حد معمول باشد آن را در بسته‌های جداگانه می‌فرستیم. او اکنون عدد C را محاسبه می‌کند به‌طوری که این کار با استفاده از به توان رسانی پیمانه ای می‌تواند خیلی سریع انجام شود، حتی برای اعداد خیلی بزرگ. حال باب می‌تواند c را به آلیس بفرستد و آلیس توسط کلید خصوصی اش آن را رمزگشایی کند و آن را بفهمد. نمونه انتخاب دو عدد اول مانند: and محاسبه : محاسبه تابع فی اویلر با ساخت خواهدشد: انتخاب هر عددی که نسبت به ۳۱۲۰ اول باشد. در نظر می‌گیریم محاسبه d, the وارون ضربی (هم‌نهشتی) , کلید عمومی (, ) برای پیام m هست. برای متن رمز c تابع رمزگشایی به صورت زیر خواهد بود: برای نمونه در رمزنگاری , را حساب می‌کنیم. نمونه دیگر تهیه کلیدهای عمومی و خصوصی به‌طور خلاصه روش کار برای تهیه کلیدها به شرح زیر است: ۱- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام‌های p و q را انتخاب می‌کنیم، بهتر است این اعداد از لحاظ سایز نزدیک به یکدیگر باشند. ۲- عدد دیگری به نام n را معادل با حاصلضرب p در q تعریف می‌کنیم:n = p x q ۳- عدد چهارم یعنی m را معادل حاصلضرب p-۱ در q-۱ تعریف می‌کنیم: m = (q-1 p-1) ۴- عدد e را که از m کوچکتر است آنگونه پیدا می‌کنیم که بزرگترین مقسوم علیه مشترک این دو یک باشد به عبارتی نسبت به هم اول باشند. ۵- عددی مانند d را پیدا کنید که باقی‌مانده حاصلضرب d در e تقسیم بر m مساوی عدد ۱ باشد، یعنی: d x e) mod m = ۱) حال پس از طی این مراحل شما می‌توانید از e و n به عنوان کلید عمومی و از d و n به عنوان کلید اختصاصی استفاده کنید. | ## بخش 2: آراس‌ای | روش پنهان کردن و آشکار کردن برای رمزنگاری اطلاعات کافی است عدد منتصب به هر کاراکتر - مثلاً ASCII - را که در اینجا M می‌نامیم در فرمول زیر قرار دهید و به جای ارسال آن عدد C = M^e mod n را ارسال کنید. در واقع دراینجا شما توانسته‌اید با کمک کلید عمومی، کاراکتر M را به C تبدیل کنید. حال گیرنده برای آشکارسازی کافی است عدد دریافتی یعنی C را با استفاده از کلید خصوصی به M تبدیل کند. برای اینکار کافی است از این فرمول استفاده کنید: M = C^d mod n، بنابراین شما با دریافت کاراکتر کد شده C و در دست داشتن کلید خصوصی توانسته‌اید کاراکتر اصلی را مشخص نمایید. اما برای سادگی محاسبات از اختیار کردن اعداد بزرگ دوری خواهیم کرد و توجه شما را به این نکته جلب می‌کنیم که هرچقدر اعداد اولیه بزرگتر باشند احتمال شکستن رمز در مدت زمان محدود ناچیزتر می‌شود. ۱- ابتدا باید دو عدد اول بزرگ انتخاب کنیم که در اینجا از اعداد ساده و هم اندازه‌ای مانند ۱۱ و ۳ استفاده می‌کنیم. پس p=۱۱ , q=۳ ۲- حاصلضرب p در q که همان n است را به اینصورت خواهیم داشت: n = ۱۱ x ۳ = ۳۳ ۳- حاصلضرب p-۱ در q-۱ که همان m است را به اینصورت خواهیم داشت: m = ۱۰ x ۲ = ۲۰ ۴- برای انتخاب عدد e که نسبت به m=۲۰ اول باشد و کمتر از آن هم باشد ساده‌ترین گزینه یعنی عدد ۳ را انتخاب می‌کنیم. ۵- برای یافتن عدد d که در رابطه d x e) mod m = ۱) صادق باشد اعداد ۱٬۲٬۳٬۴٬۵ و… را امتحان می‌کنیم، بنظر می‌رسد که عدد ۷ برای اینکار مناسب باشد چرا که ۷x3=۲۱ باقی‌مانده‌ای معادل ۱ بر m=۲۰ دارد. حال می‌توانیم از زوج (۳۳٬۳) به عنوان کلید عمومی و از زوج (۳۳٬۷) به عنوان کلید خصوصی استفاده کنیم. حال اگر از فرمول‌هایی که در مطلب قبل برای رمزنگاری و آشکارسازی استفاده کنیم برای اعداد ۱ تا ۱۶۳۲ به جدول زیر خواهیم رسید. m: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 c: ۰ ۱ ۸ ۲۷ ۳۱ ۲۶ ۱۸ ۱۳ ۱۷ ۳ ۱۰ ۱۱ ۱۲ ۱۹ ۵ ۹ ۴ m: 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 c: ۲۹ ۲۴ ۲۸ ۱۴ ۲۱ ۲۲ ۲۳ ۳۰ ۱۶ ۲۰ ۱۵ ۷ ۲ ۶ ۲۵ ۳۲ بنابراین هم‌اکنون شما یک جدول تبدیل کد دارید که با کمک کلید عمومی اعداد صفر تا ۳۲ را به اعدادی کد شده و در همین رنج تبدیل کرده‌اید. اولآ باید بدانیم که ۰ و ۱ همواره به همین اعداد تبدیل می‌شوند و مطلب دیگر اینکه اگر رنج دو عدد اول ابتدایی را بزرگ در نظر بگیریم دیگر مشکلی پیش نخواهد آمد. در این پیام، او می‌تواند ادعا کند که آلیس است، اما باب هیچ راهی برای تأیید این که این پیام واقعاً از طرف آلیس است ندارد، چرا که هر کس می‌تواند از کلید عمومی باب برای ارسال پیام‌های رمز گذاری شده به وی استفاده کند. برای این کار، او مقدار هش پیام مورد نظر خود را محاسبه می‌کند، آن را به توان d می‌رساند (در پیمانهٔ n همان‌طور که هنگام رمزگشایی یک پیام این کار را انجام می‌دهد) و آن را به عنوان «امضا» به پیام خود الصاق می‌کند. هنگامی که باب این پیام امضا شده را دریافت می‌کند، او هم از همان تابع هش در رابطه با کلید عمومی آلیس استفاده می‌کند. او این امضا را به توان e (در پیمانهٔ m) می‌رساند (همان‌طور که این کار را هنگام رمزگشایی یک پیام نیز انجام می‌دهد) و مقدار هش حاصل را با مقدار هش واقعی پیام مقایسه می‌کند. اگر این دو با هم توافق داشته باشیند، او می‌داند که نویسده پیام کلید خصوصی آلیس را در اختیار داشته‌است و پیام از آن زمان دست نخورده باقی مانده‌است. این روش به دلیل قوانین به توان رسانی، کار می‌کند: بنابر این، کلید خصوصی می‌تواند برای: رمزگشایی یک پیام که برای یک گیرنده فرستاده شده‌است، که می‌تواند توسط هر فردی که دارای کلید عمومی است، برای رمزنگاری استفاده شود. رمزنگاری یک پیام که ممکن است توسط هر کس رمزگشایی شود، اما فقط توسط یک نفر می‌تواند رمزنگاری شود، این استفاده، امضای دیجیتال را ممکن می‌سازد. اثبات درستی اثبات با استفاده از قضیه کوچک فرما اثبات درستی الگوریتم RSA بر اساس قضیه کوچک فرما است که بیان می‌کند که اگر یک عدد p اول و a عددی صحیح باشد که در این صورت . ما می‌خواهیم نشان دهیم که برای هر عدد صحیح m در صورتی که p و q اعداد اول مجزا از هم هستند و e و e اعداد صحیح مثبتی هستند که مقدار آن‌ها در معادلهٔ صدق می‌کند: از آن جایی که به علت ساختارش، هم بر p-1 و هم بر q-1 بخش پذیر است، می‌توان به ازای یک مقدار غیر منفی h و k نوشت: برای بررسی این که آیا دو عدد مانند و m، به پیمانهٔ pq معادل هستند یا خیر، بررسی می‌کنیم که آیا آن‌ها به پیمانهٔ p و به پیمانهٔ q به صورت جداگانه، معادل هستند یا خیر. برای این که نشان دهیم ، دو حالت را در نظر می‌گیریم: اگر ، آن گاه m، ضریبی از p است؛ بنابراین ، ضریبی از p است، بنابراین اگر اینجا از قضیه کوچک فرما استفاده کردیم تا را با ۱ جایگزین کنیم. برای این که تأیید کنیم ، کاملاً مشابه عمل می‌کنیم: اگر ، آن گاه m، ضریبی از q است؛ بنابراین ، ضریبی از q است، بنابراین اگر در این نقطه، اثبات می‌شود که برای هر عدد صحیح m و عدد صحیح e و d که ، اثبات از طریق قضیه اویلر اگرچه در مقالهٔ اصلی ریوست، شمیر و آدلمن، از قضیهٔ کوچک فرما برای توضیح چگونگی کارکرد RSA استفاده کردند، شایع است که از اثبات‌های مبتنی بر قضیهٔ اویلر هم استفاده بشود. می‌خواهیم نشان دهیم که وقتی که n = pq است، حاصل ضرب دو عدد عول است و e و d اعداد صحیح مثبتی هستند که در معادلهٔ صدق می‌کنند. از آن جایی که e و d مثبت هستند، می‌توانیم به ازای یک مقدار نامنفی صحیح h بنویسیم . در صورتی که فرض کنیم m نسبت به n اول است، داریم: در دومین آخرین تساوی در معادله بالا، عبارت داخل پرانتز شرایط قضیه اویلر را دارد و بنابر این در تساوی بعدی با ۱ جایگزین می‌شود. به صورت کلی تر، برای هر e و d که در معادلهٔ صدق می‌کنند می‌توان نتیجه مشابهی را با استفاده از تعمیم قضیهٔ اویلر توسط کارمایکل، که بیان می‌کند برای همهٔ mهایی که نسبت به n اولند : ، گرفت. اما احتمال وقوع این امر بسیار پایین است (تنها اعداد این ویژگیرا دارند)، اما حتی در این حالت هم، معادلهٔ مذکور صادق است. اجزای سامانه رمزنگاری کلید رمزنگاری الگوریتم رمزنگاری کلید رمزگشایی الگوریتم رمزگشایی اگر از یک کلید برای رمزنگاری و رمزگشایی استفاده شود سامانه رمزنگاری متقارن است و در غیر اینصورت، نامتقارن خواهد بود. انواع روش‌های رمزنگاری مبتنی بر کلید الگوریتم‌های کلید متقارن: رمزنگاری و رمزگشایی با یک کلید انجام می‌گیرد. الگوریتم‌های کلید نامتقارن (کلید عمومی): هر فرد یک کلید عمومی و یک کلید خصوصی دارد. کلیدهای این نوع از الگوریتم‌ها (نامتقارن) بسیار طولانی‌تر از الگوریتم‌های مرسوم (کلید متقارن) هستند. شکستن الگوریتم واقعیت آن است که همه روش‌های رمزنگاری قابل شکستن است، اما نکته مهم آن است که در چه مدت زمان و با چه امکاناتی این اطلاعات باید رمزگشایی شوند. در ارتباط با الگوریتم RSA باید گفت روش‌های محدودی برای شکستن متن رمزنگاری شده توسط آن وجود دارد که در اینجا به مواردی از آن اشاره می‌کنیم. تجزیه n به عوامل اول نخستین روش، آن است که بتوان کلید خصوصی را حدس زد یا پیدا کرد. در این صورت رخنه‌گر می‌تواند همه متن‌های تهیه شده با کلید عمومی را رمزگشایی کند و بخواند یا می‌تواند از امضای الکترونیک صاحب کلید استفاده کند. فرض بر این است که فردی که قصد حدس زدن کلید خصوصی را دارد، از جمله افرادی است که کلید عمومی را دارا است. روش مؤثر برای محاسبه ریشه e ام برای بازکردن رمز پیام‌هایی که با الگوریتم RSA رمزنگاری شده‌اند روش‌های محاسبه ریاضی عملاً راه به جایی نمی‌برند و در مواردی که متن کوچک باشد شاید حدس زدن متن اصلی ساده‌ترین روش برای رمزگشایی باشد. راه‌های مقابله با حمله زمانی به RSA استفاده از به توان رساندن با زمان ثابت محاسباتی. تابع باید به ازای همه ورودی‌ها زمان ثابتی به طول بینجامد قرار دادن اعمال اضافی و گمراه‌کننده در بین محاسبات ضرب کردن متن رمزنگاری شده در یک عدد تصادفی قبل از عملیات به توان رسانی اضافه کردن تاخیرهای تصادفی لایه گذاری حمله به RSA ساده چندین نوع حمله به RSA ساده وجود دارد که در پاینن توضیح می‌دهیم هنگامی که رمز گذاری با توان رمز گذاری پایین مانند e برابر۳ و مقادید کوچک برای m یعنی (m <n1/e) استفاده می‌کند این نتیجه می‌شود که me به شدت از ضریب n کوچک‌تر شود، که این باعث می‌شود که متن رمز شده بتوان به راحتی رمزگشایی شود به وسیلهٔ گرفتن جذر e ام برروی اعداد صحیح به دست آید اگر متن یکسانی به e یا بیشتر گیرنده فرستاده شود به به صورت رمز شده فرستاده شود و گیرنده‌ها توان e ی یکسانی داشته باشند اما p و q و طبیعتاً n متفاوتی داشته باشند، در آن زمان به راحتی می‌توان متن اصلی را با استفاده از روش قضیه باقی‌مانده چینی به دست آورد. یوان هواستاد متوجه شد که این حمله ممکن است حتی اگر متن رمز نشده یکسان نباشد اما حمله کنند ارتباط بین آن‌ها را بداند. برای اطلاعات بیشتر حمله مسگر را ببینید به علت اینکه رمز نگاری RSA الگوریتم قطعی است (به عنوان مثال هیچ بخش تصادفی‌ای ندارد) حمله کننده می‌تواند به راحتی حمله با متن اصلی منتخب را بر روی سیستم رمز نگاری اجرا کند. یک سیستم رمز نگاری امنیت معنایی خوانده می‌شود اگر حمله کننده نتواند دو رمز نگاری را حتی اگر متن اصلی را بداند تمایز قائل شود. به عنوان مثال حمله کننده که خواستار متن رمزنشدهٔ یک متن رمزشدهٔ (c ≡ me (mod n می‌تواند از دارندهٔ کلید خصوصی بخواهد که یک متن غیر مشکوک رمز شده را (c′ ≡ cre (mod n را برای مقدار r که توسط حمله کننده انتخاب شده‌است رمز گشایی کند. طرح لایه بندی برای دوری از این مشکل‌ها RSA کاربردی در پیاده‌سازی معمولاً یک ساحتار رندوم از لایه‌ها را در مقدار m قبل از رمزنگاری تعبیه می‌کند. این لایه بندی تضمین می‌کند که m در بازهٔ متن‌های غیر امن نمی‌افتد و متن داده شده وقتی در لایه قرار می‌گیرد مز می‌شود به یکی از تعداد زیادی حالات ممکن برای رمز شده اش. استانداردهایی مانند PKCS_1 حیلی محتاتانه طراحی شدند برای خیلی امن لایه کردن مسیج به رمز RSA. به خاطر اینکه طرح‌های لایه بندی برای متن رمز نشدهٔ m، چند بیت اضافی می‌کند، طول متن لایه نشدهٔ m باید کوتاه‌تر باشد. | ## بخش 3: آراس‌ای | طرح لایه بندی RSA باید با دقت طراحی شود که بتواند جلوگیری کند از حمله‌های پیچیده که ممکن است کند حدث زدن متن ساختار یافته شده. اولین ورژن استاندارد PKCS_1 (تا ورژن ۱٫۵) از ساختاری که به نظر می‌رسیتد RSA را از نظر معنایی ایمن می‌کرد استفاده می‌کرد. همین‌طور OAEP باید استفاده کند از برنامهٔ جدیدی و لایهٔ PKCS#1 ورژن ۱٫۵ باید جایگزین شود در سریع‌ترین زمان ممکن. استاندارد PKCS#1 همچنین شامل پردازش لایه‌های طراحی شده برای فراهم کردم امنیت بیشتر در امضای RSA. طراحی لایه بندی امن مانند RSA-PSS نیاز اساسی برای امنیت امضای مسیج‌هایی که رمز می‌شوند هستند. دقت کنید که استفاده از جفت کلیدهای RSA متفاوت برای رمزنگاری و امضا بلقوه امنیت بیشتری دارد. ملاحظات امنیتی و عملی استفاده از الگوریتم باقی ماندهٔ چینی برای بهینگی خیلی از کتاب‌خانه‌های معروف رمز نگاری مانند OpenSSL ازقضیه باقی‌مانده چینی برای بهینه‌سازی در رمزگشایی و امضا زدن استفاده می‌کنند. این کار خیلی بهینه تر است از توان‌رسانی دودویی حتی اگر دو پیمانهٔ نمایی استفاده شود. به این علت که دو پیمانهٔ نمایی خود از دو توان و پیمانهٔ کوچیک تر استفاده می‌کنند. کل رمزگشایی رمزنگاری RSA غیرقابل نفوذ پنداشته می‌شد بر فرض سخت بودن این ۲ مسئله یعنی هیچ الگوریتم بهینه ای برای حل آن‌ها موجود نبود. در حال حاضر بهترین الگوریتم ارائه شده برای حل کردن مسئلهٔ RSA استفاده از تجزیه بر مبنای n است. با این توانایی بازیابی اعداد اول، حمله کننده می‌تواند توان مخفی d را از کلید (n,e) محاسبه کند و سپس c را با استفاده از روش استاندارد رمزگشایی کند. برای دستیابی به این هدف، حمله کننده باید عوامل n به p و q را به دست آورد و سپس بزرگترین مضرب مشترک آنان را به دست آورد که به او اجازهٔ تعیین d و e را می‌دهد. هیچ راه غیر چند جمله ای برای این کار تجزیهٔ اعداد طبیعی بزرگ بر روی کامپیوترهای معمولی هنوز پیدا نشده‌است، اما اثبات نشده‌است که وجود ندارد. روش خطی مرتبه دو ی چندگانه (MPQS) می‌تواند برای پیدا کردن تجزیهٔ عدد عمومی n استفاده شود. تعداد بیتزمان (ثانیه)۱۲۸کمتر از ۲۱۹۲۱۶۲۵۶۲۱۰۰۲۶۰۳۶۰۰ ابزاری به اسم YAFU می‌تواند برای تسریع این برنامه استفاده شود. با این برنامه می‌توان در ۵۷۲۰ ثانیه عدد n ای که ۳۲۰ بیت دارد را بر روی همان کامپیوتر تجزیه کرد. کمتر از ۵ گیگا بایت از حافظهٔ داخلی اش و در حدود ۲٫۵ گیگا بایت از حافظهٔ رم سیستم اش برای اینکار استفاده کرد. اگر چه ریوست، شمیر و آدلمن متوجه شدند در بخش IX/D در مقاله یشان، آن‌ها اثباتی برای برابری میزان سختی تجزیه و معکوس کردن RSA پیدا نکردند. تا سال ۲۰۱۹، بزرگترین عدد تجزیه شده RSA ۷۹۵ بیت طول داشت(۲۴۰ رقم در مبنای ۱۰، برای اطلاعات بیشتر RSA-240 را مطالعه کنید). این تجزیه با پیشرفته‌ترین حالت پیاده‌سازی جداگانه انجام شده بود و در حدود ۹۰۰ پردازنده سال زمان برد. اهمیت ساخت عدد تصادفی طولانی به صورت رمزنگاری ی تولید اعداد تصادفی قوی، که به خوبی کار می‌کند باید از اعداد اول p و q استفاده کند. یک ضعف خاص در سیستم رمزنگاری با تجزیهٔ اعداد طبیعی پیدا شده‌است که به این صورت است که اگر n=pq یک کلید عمومی و n′ = p′q′ کلید عمومی دیگری باشد اگر اتفاقاً p = p′ باشد اما q مخالف 'q باشد آن گاه بزرگترین مضرب مشترک کلیدها p است که تجزیهٔ هر دو کلید هست. هنینگر می‌گوید کلید بد تقریباً در هر برنامه ای رخ داده‌است مانند firewalls، روترها و وی‌پی‌ان‌ها و … تولید کلید معیوب یافتن اعداد اول بزرگ p و q معمولاً توسط آزمایش عددهای تصادفی با اندازهٔ درست و توسط تست‌های اول بودن احتمالی انجام می‌شود که به سرعت تقریباً همه ی اعداد غیر اول را حذف می‌کند. اعداد p و q نباید خیلی نزدیک هم باشند، تا مبادا روش تجزیه فرما برای n، موفقیت‌آمیز باشد. در صورتی که p-1 کم‌تر از باشد، (مقدار n، برابر با p*q است که حتی برای مقادیر کم ۱۰۲۴ بیتی هم، برابر با است) یافتن p و q بدیهی است. علاوه بر این اگر p-1 یا q-1 فقط دارای فاکتورهای کوچک اول باشند، n می‌تواند به سرعت توسط الگوریتم پی-۱ پولارد تجزیه شود و بنابراین این گونه مقادیر برای p و q به کلی نباید انتخاب شوند. حائز اهمیت است که d به اندازهٔ کافی بزرگ باشد، مایکل واینر نشان داد که اگر p بین q و 2q باشد، (که امری بسیار معمول است) و ، آن گاه n به راحتی می‌توانند از مقادیر n و e به دست بیاید. هیچ حمله شناخته شده‌ای علیه مقادیر کوچک عمومی مانند e = ۳ وجود ندارد، مشروط بر اینکه از لایه گذاری مناسب استفاده شود. حمله مسگر کاربردهای زیادی در حمله به RSA دارد به خصوص اگر نمایندهٔ عمومی e، کوچک باشد و اگر متن رمز شده کوتاه باشد و لایه گذاری شده نباشد. این مقدار در واقع یک سازشی بین جلوگیری از حملات احتمالی کوچک و امکان وجود رمزگذاری مؤثر یا تأیید امضا است. حمله‌های زمانی کوچر در سال ۱۹۹۵، یک حملهٔ جدید روی RSA تعریف کرد، اگر Eve که یک حمله کننده است، سخت‌افزار آلیس را با جزئیات کافی بشناسد و قادر به اندازه‌گیری زمان رمزگشایی برای تعداد زیادی از متن‌های رمز شده‌ای که برای او شناخته باشد، اوو می‌تواند به سرعت کلید رمزگشایی d را پیدا کند. در سال ۲۰۰۳، دان بونه و دیوید بروملیحملهٔ عملی تری را نشاند دادند که قادر به بازیابی تجزیه‌های RSA بر روی یک اتصال به شبکه بود. (به عنوان مثال، روی یک وب سرور که قابلیت اجرای لایهٔ سوکت‌های امن (ssl) را دارد). این حمله از اطلاعات فاش شده از بهینه‌سازی با قضیهٔ باقی ماندهٔ چینی که توسط بسیاری از پیاده‌سازی‌های RSA استفاده می‌شود، استفاده می‌کند. یک روش خنثی سازی این حمله‌ها این است که مطمئن شد عملیات رمزگشایی یک زمان ثابتی را برای هر متن رمز شده‌ای طول می‌کشد. به جای آن، اکثر پیاده‌سازی‌های RSA از یک تکنیک جایگزین به نام کور کنندگی استفاده می‌کنند. آلیس به جای این که را محاسبه کند، ابتدا یک مقدار تصادفی مخفی مانند r را انتخاب می‌کند و را محاسبه می‌کند. نتیجهٔ این محاسبه پس از اعمال قضیهٔ اویلر می‌باشد و بنابراین تأثیر r می‌تواند با ضرب در معکوس آن از بین برود. وقتی کورکنندگی اعمال می‌شود، زمان رمزگشایی دیگر به مقدار ورودی متن رمز شده هم بسته نیست و بنابراین حمله زمانی با شکست مواجه می‌شود. حملهٔ انطباقی متن رمزنگاری انتخابی در سال ۱۹۹۸، بلیچنباخر اولین حملهٔ انطباقی متن رمزنگاری انتخابیعملی را در مقابله با متن‌های رمزنگاری شده توسط RSA، که از pkcs #1 v1 استفاده می‌کردند، معرفی کرد. به دلیل نقوص طرح pkcs #1، بلیچنباخر قادر شد حمله ای علیه پیاده‌سازی‌های پروتکل لایه‌های امنی که با استفاده از RSA پیاده‌سازی شده بود را اجرا کند و کلیدهای session را بازیابی کند. به عنوان نتیجهٔ این کار، رمزنگاران امروزه پیشنهاد می‌کنند تا از طرح‌های لایه گذاری بسیار ایمن مانند لایه گذاری رمزنگاری متقارن بهینه و RSA Laborat استفاده شود. حملات تحلیل کانال جانبی یک حملهٔ تحلیل کانال جانبی از تحلیل پیش‌بینی شاخه (BPA) توضیح داده شده‌است. خیلی از پردازنده‌ها از پیش‌بینی شاخه برای فهمیدن اینکه آیا یک شاخه شرطی است و یک جریان دستورات آیا رخ می‌دهد یا نه استفاده می‌کنند. حملهٔ تحلیل کانال جانبی از یک پروسس جاسوس برای پیدا کردن کلید خصوصی از لحاظ آماری هنگامی که با این پردازنده‌ها استفاده می‌شود استفاده می‌کند. تحلیل پیش‌بینی شاخه ساده (SBPA) ادعا می‌کند که کار تحلیل پیش‌بینی شاخه در راه غیر آماری انجام می‌دهد. | ## جمع‌بندی | حملهٔ جدول رنگین کمانی اعداد اول ساخته شده می‌تواند حملهٔ جدول رنگین کمانی ایجاد کند به این خاطر که اعداد تصادفی ساخته شده ثابت اند.