آراس‌ای
Rivest–Shamir–Adleman آراس‌اِی ریوست-شمیر-ادلمن (RSA) از اولین شیوه‌های رمزنگاری به روش کلید عمومی (Public Key Cryptography PKC) است که به صورت گسترده برای تأمین امنیت انتقال داده استفاده می‌شود. در این چنین سیستم‌های رمزنگاری، کلید رمزگذاری عمومی است و از کلید رمزگشایی که مخفی است، جداست. در آراس‌اِی، این عدم تقارن مبتنی بر این است که تجزیه از عددی که ضرب دو عدد اول بزرگ است در عمل بسیار دشوار است.
این روش، نخستین روش مورد اعتماد در بین روش‌های رمزنگاری دیگر است و یکی از بزرگ‌ترین پیشرفت‌ها در زمینهٔ رمزنگاری به حساب می‌آید. آراس‌ای همچنان به صورت گسترده‌ای در تبادلات الکترونیکی استفاده می‌شود و در صورت استفاده درست با کلیدهای طولانی کاملاً امن به نظر می‌رسد.
حروف اولیه RSA، حروف اولیه نام‌های خانوادگی Ron RIvest , Adi Shamir و Adleman است که در سال ۱۹۷۷ این الگوریتم را به‌طور عمومی معرفی کردند. یک ریاضی‌دان انگلیسی به نام Clifford Cocks، که برای ستاد ارتباطات دولت بریتانیا کار می‌کرد، سیستمی معادل این سیستم را در سال ۱۹۷۳ پیاده‌سازی کرده بود، که تا سال ۱۹۷۳ به صورت محرمانه باقی ماند.
یک کاربر RSA، یک کلید عمومی را بر اساس دو عدد اول بزرگ را همراه با یک مقدار تصادفی ساخته و به صورت عمومی منتشر می‌کند. هر کسی می‌تواند از این کلید عمومی برای رمزگذاری یک پیام استفاده کند، اما تنها کسی که آن دو عدد اولی که کلید بر اساس آن‌ها ساخته شده را می‌داند، قادر به رمزگشایی پیام است. شکستن رمزگذاری RSA به مسئلهٔ RSA معروف است. تاکنون هیچ روشی برای شکست دادن این سیستم (در صورت استفادهٔ کلید به اندازهٔ کافی بزرگ) منتشر نشده‌است.
RSA به صورت نسبی، الگوریتم کندی است و به همین علت، کمتر برای رمزگذاری مستقیم اطلاعات کاربر استفاده می‌شود. بیشتر اوقات، RSA کلید رمزگشایی شده را برای الگوریتم کلید متقارن انتقال می‌دهد که در عوض قادر است توده ای از عملیات رمزگذاری-رمزگشایی را با سرعتی بسیار بالاتر انجام دهد.
ایدهٔ کلید عمومی-خصوصی نام متقارن در سال ۱۹۷۶ (میلادی) توسط وایتفیلد دیف (Whitfield Diffie) و مارتین هلمن (Martin Hellman) دانشجویان دانشگاه استنفورد معرفی و به ثبت رسانده شد. در این روش که به روش رمزنگاری نامتقارن (asymmetric encryption) نیز شناخته می‌شود از دو کلید برای رمزنگاری اطلاعات استفاده می‌کند. در روش‌های قدیمی‌تر از یک کلید استفاده می‌شد که به آن رمزنگاری متقارن (symmetric encryption) گفته می‌شد. آن‌ها هم چنین امضای مجازی را معرفی کردند و تلاش کردند تا نظریه اعداد را نیز اعمال کنند. آن‌ها مقاله خود را با نام Transactions on Information Theory در یکی از شماره‌های سال ۱۹۷۶ مجله مؤسسه مهندسان برق و الکترونیک (IEEE) منتشر کردند که خیلی زود انقلابی در صنعت رمزنگاری در جهان به وجود آورد. رمزنگاری به روش کلید عمومی به معنی استفاده از کلید عمومی برای رمزنگاری و پنهان کردن اطلاعات است. در این روش هر کاربر برای رمزنگاری یا بازکردن رمز، دو کلید، یکی کلید عمومی (Public) و یکی کلید خصوصی (Private) در اختیار دارد. ویژگی این روش آن است که هر کدام از این کلیدها می‌توانند اطلاعاتی را که کلید دیگر رمزنگاری کرده‌است رمزگشایی کند.
رونالد ریوست، ادی شامیر، و لئونارد آدلمن در مؤسسه فناوری ماساچوست (اِم‌آی‌تی) تلاش‌های بسیاری برای ساختن یک تابع یک طرفه که معکوس کردن آن بسیار دشوار بود کردند. ریوست و شمیر که دانشمند حوزه علوم کامپیوتر بودند توابع بسیاری را پیشنهاد دادند در حالی که آدلمن که یک ریاضی‌دان بود، مسئول یافتن نقاط ضعف این توابع بود. آن‌ها رویکردهای متعددی از جمله رویکردی بر اساس مسئلهٔ کوله پشتی و «جایگشت چند جمله ای» را امتحان کردند. برای مدتی به نظر می‌رسید یافتن تابعی که در جستجوی آن هستند، ناممکن است. در آوریل سال ۱۹۷۷، پس از این که از یک جمع دانشجویی بازگشتند و مقداری نوشیده بودند، ریوست که نمی‌توانست بخوابد روی مبل دراز کشید و شروع به مطالعهٔ یک کتاب ریاضی کرد و کل شب را به تفکر راجع به تابع مذکور کرد. روز بعد، مقدار زیادی از مقاله ای که منتشر کردند آماده بود.
الگوریتم RSA در سال ۱۹۷۷ (میلادی) پایه‌گذاری و به این نام شناخته شد.
هرچند روش‌های اولیه آن پیشتر در سال ۱۹۷۳ (میلادی) توسط فردی به نام کلیفورد کاکس که در ستاد روابط دولت بریتانیا بدست آمده بود اما تا سال ۱۹۷۷ اولاً الگورتیم رمزنگاری او کاملاً محرمانه بود و دوم اینکه به سادگی آنچه در سال ۱۹۷۶ مطرح شد نبود. گرچه این الگوریتم در زمانی که توسط کاکس کشف شد به علت هزینهٔ بسیار زیاد کامپیوترهایی که برای پیاده‌سازی آن لازم بودند، هیچ‌گاه پیاده‌سازی نشد.
RSA کودکان یا kid-RSA، یک الگوریتم رمزگشایی کلید عمومی ساده‌سازی شده‌است که در سال ۱۹۹۷، برای اهداف آموزشی معرفی شد. بعضی افراد معتقدند که مطالعهٔ این الگوریتم، برای فهم RSA دید می‌دهد.
اختراع ۴٬۴۰۵٬۸۲۹ در سال ۱۹۸۳ به موسسهٔ فناوری ماساچوست یا MIT با عنوان «سیستم و روش ارتباطات رمزنگاری» که در سال ۱۹۸۳از این الگوریتم استفاده کرد، اهدا شد.
RSA شامل ۴ مرحله است: ساخت کلید، توزیع کلید، رمزنگاری و رمزگشایی.
یک اصل اساسی در RSA این است که یافتن سه عدد صحیح مثبت بسیار بزرگ مانند e, n و d که رابطهٔ زیر برایشان بر قرار باشد، عملی است.
formula_1
و با دانستن این که e و n یا حتی m، یافتن d می‌تواند بسیار مشکل باشد.
آراس‌ای به‌طور کلی از دو کلید تشکیل می‌شود. کلید عمومی و کلید خصوصی. کلید، عددی ثابت است که در محاسبات رمزنگاری استفاده می‌شود. کلید عمومی برای همه معلوم بوده و برای رمزنگاری پیام استفاده می‌شود. این پیام فقط توسط کلید خصوصی باز می‌شود. به بیان دیگر همه می‌توانند یک پیام را رمز کنند اما فقط صاحب کلید خصوصی می‌تواند پیام را باز کند و بخواند.
کلید عمومی توسط اعداد صحیح n و e نمایش داده می‌شود و کلید خصوصی، توسط عدد صحیح d(گرچه n در فرایند رمزگشایی هم استفاده می‌شود بنا بر این ممکن است قسمتی از کلید خصوصی هم در نظر گرفته شود). m، نمایان گر پیام است که از قبل توسط یک تکنیک خاص آماده شده‌است و در ادامه این تکنیک شرح داده شده‌است.
هر چند از لحاظ ریاضی کلیدهای عمومی و خصوصی با یکدیگر ارتباط دارند اما تقریباً محال است که کسی بتواند حتی با تجیهزات پیشرفته و صرف وقت زیاد با داشتن یکی از کلیدها، دیگری را تشخیص دهد. در واقع می‌توان گفت که با توجه به سطح دانش کنونی و سامانه‌های رایانه‌ای موجود، الگوریتم رمزنگاری و ارتباط میان کلیدها تقریباً غیرقابل شکستن است.
آراس‌ای مبتنی بر توان‌رسانی پیمانه‌ای است و از اعداد طبیعی خیلی بزرگ استفاده می‌کند. مستندات آراس‌ای تحت عنوان PKCS 1 استاندارد شده‌اند.
مراحل زیر برای ساخت کلید طی می‌شود:
۲. عدد n را محاسبه کنید به‌طوری‌که formula_5.
۳. تابع formula_6 را محاسبه کنید که formula_7 Carmichael function است. از آن جایی که n=pq, formula_8 و از آن جایی که p و q اول هستند، formula_9 و به همین روال formula_10. بنابراین formula_11
۴. عدد formula_13 را انتخاب کنید به‌طوری‌که formula_14 و نسبت به formula_15 اول باشد.
۵. عدد formula_17 که formula_18 را به دست بیاورید.
دو عدد اول می‌توانند توسط روش پیدا کردن اعداد اول احتمالی پیدا شوند.
فرض کنید که باب می‌خواهد اطلاعاتی را به آلیس بفرستد. اگر آن‌ها تصمیم بگیرند که از RSA استفاده کنند، باب باید کلید عمومی آلیس را برای رمز گذاری پیام بداند و آلیس باید از کلید خصوصی ای که در اختیار دارد استفاده کند تا پیام را رمزگشایی نماید. بنابر این برای این که باب قادر باشد پیام رمز شده اش را ارسال کند، آلیس کلید عمومی (n,e) خود را توسط یک مسیر مطمئن ولی نه لزوماً مخفی به باب منقل می‌کند. کلید خصوصی آلیس(d) هرگز منتقل نمی‌شود.
حالا که باب کلید عمومی آلیس را دریافت کرد، قصد دارد پیام M را به توسط الگوریتم RSA به آلیس بفرستد. باب باید پیام خود را در قالب یک عدد (m) در بیاورد به‌طوری‌که این فرایند برگشت‌پذیر بوده و روی آن توافق شده باشد و شناخته شده باشد. به این فرایند طرح لایه گذاری گفته می‌شود. عدد باب باید از n کوچک‌تر باشد. بدیهی است اگر پیام بزرگ‌تر از حد معمول باشد آن را در بسته‌های جداگانه می‌فرستیم. او اکنون عدد C را محاسبه می‌کند به‌طوری که
formula_33
این کار با استفاده از به توان رسانی پیمانه ای می‌تواند خیلی سریع انجام شود، حتی برای اعداد خیلی بزرگ.
حال باب می‌تواند c را به آلیس بفرستد و آلیس توسط کلید خصوصی اش آن را رمزگشایی کند و آن را بفهمد.
آلیس c را دریافت کرده‌است و کلید خصوصی خود را در دسترس دارد. حال می‌تواند عدد m را که معادل پیام اصلی است از C ,n، و d بازیابی کند.
formula_34کلید عمومی (, ) برای پیام m هست. بنابران تابع رمز به صورت زیر است:
کلید خصوصی () هست. برای متن رمز c تابع رمزگشایی به صورت زیر خواهد بود:
برای نمونه در رمزنگاری , را حساب می‌کنیم.
برای رمزگشایی را حساب می‌کنیم.کد 'use strict'; const RSA = {}; RSA.generate = function(keysize) {
}; RSA.encrypt = function(m, n, e) {
RSA.decrypt = function(c, d, n) {
فرض کنید آلیس از کلید عمومی باب برای ارسال پیام رمزگذاری شده برای وی استفاده می‌کند. در این پیام، او می‌تواند ادعا کند که آلیس است، اما باب هیچ راهی برای تأیید این که این پیام واقعاً از طرف آلیس است ندارد، چرا که هر کس می‌تواند از کلید عمومی باب برای ارسال پیام‌های رمز گذاری شده به وی استفاده کند. برای تأیید منشأ پیام، می‌توان از RSA برای امضا کردن یک پیام استفاده کرد.
فرض کنید آلیس مایل است پیام امضا شده‌ای را به باب ارسال کند. او می‌تواند برای این کار از کلید خصوصی خود استفاده کند. برای این کار، او مقدار هش پیام مورد نظر خود را محاسبه می‌کند، آن را به توان d می‌رساند (در پیمانهٔ n)(همان‌طور که هنگام رمزگشایی یک پیام این کار را انجام می‌دهد) و آن را به عنوان «امضا» به پیام خود الصاق می‌کند. هنگامی که باب این پیام امضا شده را دریافت می‌کند، او هم از همان تابع هش در رابطه با کلید عمومی آلیس استفاده می‌کند. او این امضا را به توان e (در پیمانهٔ m) می‌رساند (همان‌طور که این کار را هنگام رمزگشایی یک پیام نیز انجام می‌دهد) و مقدار هش حاصل را با مقدار هش واقعی پیام مقایسه می‌کند. اگر این دو با هم توافق داشته باشیند، او می‌داند که نویسده پیام کلید خصوصی آلیس را در اختیار داشته‌است و پیام از آن زمان دست نخورده باقی مانده‌است.
این روش به دلیل قوانین به توان رسانی، کار می‌کند:
formula_48
formula_49
بنابر این، کلید خصوصی می‌تواند برای:
اثبات درستی الگوریتم RSA بر اساس قضیه کوچک فرما است که بیان می‌کند که اگر یک عدد p اول و a عددی صحیح باشد که formula_50در این صورتformula_51 .
ما می‌خواهیم نشان دهیم که برای هر عدد صحیح m در صورتی که p و q اعداد اول مجزا از هم هستند و e و e اعداد صحیح مثبتی هستند که مقدار آن‌ها در معادلهٔ formula_52 صدق می‌کند:
formula_53
از آن جایی که formula_54 به علت ساختارش، هم بر p-1 و هم بر q-1 بخش پذیر است، می‌توان به ازای یک مقدار غیر منفی h و k نوشت:
formula_55
برای بررسی این که آیا دو عدد مانند formula_56 و m، به پیمانهٔ pq معادل هستند یا خیر، بررسی می‌کنیم که آیا آن‌ها به پیمانهٔ p و به پیمانهٔ q به صورت جداگانه، معادل هستند یا خیر. اگر بودند، به پیمانهٔ pq هم معادلند.
برای این که نشان دهیم formula_57، دو حالت را در نظر می‌گیریم:
formula_62
اینجا از قضیه کوچک فرما استفاده کردیم تا formula_63 را با ۱ جایگزین کنیم.
برای این که تأیید کنیم formula_64، کاملاً مشابه عمل می‌کنیم:
formula_69
در این نقطه، اثبات می‌شود که برای هر عدد صحیح m و عدد صحیح e و d که formula_52،
formula_71
اگرچه در مقالهٔ اصلی ریوست، شمیر و آدلمن، از قضیهٔ کوچک فرما برای توضیح چگونگی کارکرد RSA استفاده کردند، شایع است که از اثبات‌های مبتنی بر قضیهٔ اویلر هم استفاده بشود.
می‌خواهیم نشان دهیم که formula_72 وقتی که n = pq است، حاصل ضرب دو عدد عول است و e و d اعداد صحیح مثبتی هستند که در معادلهٔ formula_73 صدق می‌کنند. از آن جایی که e و d مثبت هستند، می‌توانیم به ازای یک مقدار نامنفی صحیح h بنویسیم formula_74. در صورتی که فرض کنیم m نسبت به n اول است، داریم:
formula_75
در دومین آخرین تساوی در معادله بالا، عبارت داخل پرانتز شرایط قضیه اویلر را دارد و بنابر این در تساوی بعدی با ۱ جایگزین می‌شود.
به صورت کلی تر، برای هر e و d که در معادلهٔ formula_52 صدق می‌کنند می‌توان نتیجه مشابهی را با استفاده از ، که بیان می‌کند برای همهٔ mهایی که نسبت به n اولند : formula_77، گرفت.
هنگامی که m نسبت به n اول نیست، نتیجه‌گیری بالا نا معتبر است. اما احتمال وقوع این امر بسیار پایین است (تنها formula_78 اعداد این ویژگیرا دارند)، اما حتی در این حالت هم، معادلهٔ مذکور صادق است.
یا formula_58 یا formula_68، که در هر کدام از این موارد، می‌توان اثبات قبلی را به کار گرفت.الگوریتم‌های کلید متقارن:
رمزنگاری و رمزگشایی با یک کلید انجام می‌گیرد.
الگوریتم‌های کلید نامتقارن (کلید عمومی):
هر فرد یک کلید عمومی و یک کلید خصوصی دارد.
دفی هلمن و RSA نمونه‌ای از این الگوریتم‌ها است.
کاربرد در امضای دیجیتال.
کلیدهای این نوع از الگوریتم‌ها (نامتقارن) بسیار طولانی‌تر از الگوریتم‌های مرسوم (کلید متقارن) هستند.
واقعیت آن است که همه روش‌های رمزنگاری قابل شکستن است، اما نکته مهم آن است که در چه مدت زمان و با چه امکاناتی این اطلاعات باید رمزگشایی شوند. در ارتباط با الگوریتم RSA باید گفت روش‌های محدودی برای شکستن متن رمزنگاری شده توسط آن وجود دارد که در اینجا به مواردی از آن اشاره می‌کنیم.
نخستین روش، آن است که بتوان کلید خصوصی را حدس زد یا پیدا کرد. در این صورت رخنه‌گر می‌تواند همه متن‌های تهیه شده با کلید عمومی را رمزگشایی کند و بخواند یا می‌تواند از امضای الکترونیک صاحب کلید استفاده کند. فرض بر این است که فردی که قصد حدس زدن کلید خصوصی را دارد، از جمله افرادی است که کلید عمومی را دارا است. در این حالت او n و e را در دسترس دارد.
برای بازکردن رمز پیام‌هایی که با الگوریتم RSA رمزنگاری شده‌اند روش‌های محاسبه ریاضی عملاً راه به جایی نمی‌برند و در مواردی که متن کوچک باشد شاید حدس زدن متن اصلی ساده‌ترین روش برای رمزگشایی باشد.
استفاده از به توان رساندن با زمان ثابت محاسباتی.
تابع باید به ازای همه ورودی‌ها زمان ثابتی به طول بینجامد
قرار دادن اعمال اضافی و گمراه‌کننده در بین محاسبات
ضرب کردن متن رمزنگاری شده در یک عدد تصادفی قبل از عملیات به توان رسانی
اضافه کردن تاخیرهای تصادفی
چندین نوع حمله به RSA ساده وجود دارد که در پاینن توضیح می‌دهیم
برای دوری از این مشکل‌ها RSA کاربردی در پیاده‌سازی معمولاً یک ساحتار رندوم از لایه‌ها را در مقدار m قبل از رمزنگاری تعبیه می‌کند. این لایه بندی تضمین می‌کند که m در بازهٔ متن‌های غیر امن نمی‌افتد و متن داده شده وقتی در لایه قرار می‌گیرد مز می‌شود به یکی از تعداد زیادی حالات ممکن برای رمز شده اش.
استانداردهایی مانند PKCS_1 حیلی محتاتانه طراحی شدند برای خیلی امن لایه کردن مسیج به رمز RSA.
به خاطر اینکه طرح‌های لایه بندی برای متن رمز نشدهٔ m، چند بیت اضافی می‌کند، طول متن لایه نشدهٔ m باید کوتاه‌تر باشد. طرح لایه بندی RSA باید با دقت طراحی شود که بتواند جلوگیری کند از حمله‌های پیچیده که ممکن است کند حدث زدن متن ساختار یافته شده. اولین ورژن استاندارد PKCS_1 (تا ورژن ۱٫۵) از ساختاری که به نظر می‌رسیتد RSA را از نظر معنایی ایمن می‌کرد استفاده می‌کرد. اگر چه در Crypto در سال ۱۹۹۸ Bleichenbacher نشان داد که این ورژن بسیار آسیب‌پذیر است در برابر Adaptive chosen ciphertext attack. علاوه بر این در crypto در سال ۲۰۰۰ Coron et al نشان داد که برای برخی از انواع پیام این لایه بندی میزان لازم از امنیت را فراهم نمی‌کند. ورژن‌های بعدی این استاندارد شامل OAEP شد، که جلوگیری می‌کند از این حمله. همین‌طور OAEP باید استفاده کند از برنامهٔ جدیدی و لایهٔ PKCS#1 ورژن ۱٫۵ باید جایگزین شود در سریع‌ترین زمان ممکن. استاندارد PKCS#1 همچنین شامل پردازش لایه‌های طراحی شده برای فراهم کردم امنیت بیشتر در امضای RSA. به عنوان مثال امضای احتمالی طراحی برای RSA.
طراحی لایه بندی امن مانند RSA-PSS نیاز اساسی برای امنیت امضای مسیج‌هایی که رمز می‌شوند هستند. ۲ ثبت اختراع در آمریکا بر روی PSS ثبت شده‌است. اگر چه این اختراعات در تاریخ ۲۴ ژوئیه ۲۰۰۹ و ۲۵ آوریل ۲۰۱ منقضی شدند. استفاده از PSS دیگر نیازمند ثبت اختراع نیست. دقت کنید که استفاده از جفت کلیدهای RSA متفاوت برای رمزنگاری و امضا بلقوه امنیت بیشتری دارد.
برای بهینگی خیلی از کتاب‌خانه‌های معروف رمز نگاری مانند OpenSSL ازقضیه باقی‌مانده چینی برای بهینه‌سازی در رمزگشایی و امضا زدن استفاده می‌کنند.
این کار خیلی بهینه تر است از توان‌رسانی دودویی حتی اگر دو پیمانهٔ نمایی استفاده شود. به این علت که دو پیمانهٔ نمایی خود از دو توان و پیمانهٔ کوچیک تر استفاده می‌کنند.
امنیت سیستم رمزنگاری RSA بر اساس دو مسئلهٔ ریاضی هست، تجزیه اعداد طبیعی و RSA problem.
کل رمزگشایی رمزنگاری RSA غیرقابل نفوذ پنداشته می‌شد بر فرض سخت بودن این ۲ مسئله یعنی هیچ الگوریتم بهینه ای برای حل آن‌ها موجود نبود. که فراهم کردن امنیت در برابر رمزگشایی جزئی ممکن است نیازمند اضافه کردن Padding_cryptography امن باشد.
مسئلهٔ RSA تعریف شده به عنوان کار گرفتن e امین ریشهٔ مرکب n:
بازیابی مقدار m به طوری که ("c" ≡ "m" (mod "n" در حالی که ("n", "e") همان کلید عمومی RSA است و c متن رمز شدهٔ RSA است. در حال حاضر بهترین الگوریتم ارائه شده برای حل کردن مسئلهٔ RSA استفاده از تجزیه بر مبنای n است. با این توانایی بازیابی اعداد اول، حمله کننده می‌تواند توان مخفی d را از کلید (n,e) محاسبه کند و سپس c را با استفاده از روش استاندارد رمزگشایی کند. برای دستیابی به این هدف، حمله کننده باید عوامل n به p و q را به دست آورد و سپس بزرگترین مضرب مشترک آنان را به دست آورد که به او اجازهٔ تعیین d و e را می‌دهد. هیچ راه غیر چند جمله ای برای این کار تجزیهٔ اعداد طبیعی بزرگ بر روی کامپیوترهای معمولی هنوز پیدا نشده‌است، اما اثبات نشده‌است که وجود ندارد. برای مطالعهٔ بیشتر تجزیه اعداد طبیعی را بحوانید.
روش خطی مرتبه دو ی چندگانه (MPQS) می‌تواند برای پیدا کردن تجزیهٔ عدد عمومی n استفاده شود. زمان لازم برای محاسبهٔ n ای که ۱۲۸ بیت و ۲۵۶ بیت است بر روی کامپیوتر خانگی (پردازنده: Intel Dual-Core i7-4500U 1.80GHz) به ترتیب ۲ ثانیه و ۳۵ ثانیه است.
ابزاری به اسم YAFU می‌تواند برای تسریع این برنامه استفاده شود. با این برنامه می‌توان در ۵۷۲۰ ثانیه عدد n ای که ۳۲۰ بیت دارد را بر روی همان کامپیوتر تجزیه کرد.
در سال ۲۰۰۹، بنجامین مودی یک RSA با ۵۱۲ بیت را در ۷۳ روز با نرم‌افزارهای عمومی (GGNFS) و کامپیوتر شخصی اش (dual-core Athlon64 with a 1,900 MHz cpu) رمزگشایی کرد. کمتر از ۵ گیگا بایت از حافظهٔ داخلی اش و در حدود ۲٫۵ گیگا بایت از حافظهٔ رم سیستم اش برای اینکار استفاده کرد. در RSA ی ۵۱۲ بیتی اولیه در سال ۱۹۹۹ تجزیه نیازمند ۸٫۴۰۰ سال اجرا با سرعت ۱ میلیون دستور در ثانیه(8,400 MIPS years) در طول ۷ ماه نیازمند بود.
ریوست، شمیر و آدلمن متوجه شدند که میلر نشان داده که - بر این فرض که Generalized Riemann hypothesis درست است - پیدا کردن d از n و e به اندازهٔ تجزیهٔ n به p و q (تا حداکثر فاصله زمانی چند جمله ای) سخت است. اگر چه ریوست، شمیر و آدلمن متوجه شدند در بخش IX/D در مقاله یشان، آن‌ها اثباتی برای برابری میزان سختی تجزیه و معکوس کردن RSA پیدا نکردند.
تا سال ۲۰۱۹، بزرگترین عدد تجزیه شده RSA ۷۹۵ بیت طول داشت(۲۴۰ رقم در مبنای ۱۰، برای اطلاعات بیشتر RSA-240 را مطالعه کنید). این تجزیه با پیشرفته‌ترین حالت پیاده‌سازی جداگانه انجام شده بود و در حدود ۹۰۰ پردازنده سال زمان برد. دیگر کلید RSA به عنوان تجزیه شده شناخته شده‌است.
به صورت رمزنگاری ی تولید اعداد تصادفی قوی، که به خوبی کار می‌کند باید از اعداد اول p و q استفاده کند.
یک ضعف خاص در سیستم رمزنگاری با تجزیهٔ اعداد طبیعی پیدا شده‌است که به این صورت است که اگر n=pq یک کلید عمومی و n′ = p′q′ کلید عمومی دیگری باشد اگر اتفاقاً "p" = "p"′ باشد اما q مخالف 'q باشد آن گاه بزرگترین مضرب مشترک کلیدها p است که تجزیهٔ هر دو کلید هست.
هنینگر می‌گوید کلید بد تقریباً در هر برنامه ای رخ داده‌است مانند firewalls، روترها و وی‌پی‌ان‌ها و …
یافتن اعداد اول بزرگ p و q معمولاً توسط آزمایش عددهای تصادفی با اندازهٔ درست و توسط تست‌های اول بودن احتمالی انجام می‌شود که به سرعت تقریباً همهم ی اعداد غیر اول را حذف می‌کند.
اعداد p و q نباید خیلی نزدیک هم باشند، تا مبادا ر برای n، موفقیت‌آمیز باشد. در صورتی که p-1 کم‌تر از formula_81 باشد، (مقدار n، برابر با p*q است که حتی برای مقادیر کم ۱۰۲۴ بیتی هم، برابر با formula_82 است) یافتن p و q بدیهی است. علاوه بر این اگر p-1 یا q-1 فقط دارای فاکتورهای کوچک اول باشند، n می‌تواند به سرعت توسط الگوریتم پی-۱ پولارد تجزیه شود و بنابراین این گونه مقادیر برای p و q به کلی نباید انتخاب شوند.
حائز اهمیت است که d به اندازهٔ کافی بزرگ باشد، مایکل واینر نشان داد که اگر p بین q و 2q باشد، (که امری بسیار معمول است) و formula_83، آن گاه n به راحتی می‌توانند از مقادیر n و e به دست بیاید. هیچ حمله شناخته شده‌ای علیه مقادیر کوچک عمومی مانند e = ۳ وجود ندارد، مشروط بر اینکه از لایه گذاری مناسب استفاده شود. حمله مسگر کاربردهای زیادی در حمله به RSA
دارد به خصوص اگر نمایندهٔ عمومی e، کوچک باشد و اگر متن رمز شده کوتاه باشد و لایه گذاری شده نباشد. مقدار ۶۵۵۳۷ مقداری است که زیاد برای مقدار e استفاده می‌شود. این مقدار در واقع یک سازشی بین جلوگیری از حملات احتمالی کوچک و امکان وجود رمزگذاری مؤثر یا تأیید امضا است.
در سال ۱۹۹۵، یک حملهٔ جدید روی RSA تعریف کرد، اگر Eve که یک حمله کننده است، سخت‌افزار آلیس را با جزئیات کافی بشناسد و قادر به اندازه‌گیری زمان رمزگشایی برای تعداد زیادی از متن‌های رمز شده‌ای که برای او شناخته باشد، اوو می‌تواند به سرعت کلید رمزگشایی d را پیدا کند. این حمله همچنین می‌تواند برای طرح امضای RSA هم استفاده شود. در سال ۲۰۰۳، دان بونه و دیوید حملهٔ عملی تری را نشاند دادند که قادر به بازیابی تجزیه‌های RSA بر روی یک اتصال به شبکه بود. (به عنوان مثال، روی یک وب سرور که قابلیت اجرای لایهٔ سوکت‌های امن (ssl) را دارد). این حمله از اطلاعات فاش شده از بهینه‌سازی با قضیهٔ باقی ماندهٔ چینی که توسط بسیاری از پیاده‌سازی‌های RSA استفاده می‌شود، استفاده می‌کند.
یک روش خنثی سازی این حمله‌ها این است که مطمئن شد عملیات رمزگشایی یک زمان ثابتی را برای هر متن رمز شده‌ای طول می‌کشد. اگرچه این رویکرد به شدت باعث کاهش کارایی می‌شود. به جای آن، اکثر پیاده‌سازی‌های RSA از یک تکنیک جایگزین به نام کور کنندگی استفاده می‌کنند. کور نندگی RSA، از ویژگی ضرب RSA استفاده می‌کند. آلیس به جای این که formula_84 را محاسبه کند، ابتدا یک مقدار تصادفی مخفی مانند r را انتخاب می‌کند و formula_85 را محاسبه می‌کند. نتیجهٔ این محاسبه پس از اعمال قضیهٔ اویلر formula_86 می‌باشد و بنابراین تأثیر r می‌تواند با ضرب در معکوس آن از بین برود. حال مقدار جدیدی برای r برای هر متن رمز شده انتخاب می‌شود. وقتی کورکنندگی اعمال می‌شود، زمان رمزگشایی دیگر به مقدار ورودی متن رمز شده هم بسته نیست و بنابراین حمله زمانی با شکست مواجه می‌شود. در سال ۱۹۹۸، اولین عملی را در مقابله با متن‌های رمزنگاری شده توسط RSA، که از pkcs #1 v1 استفاده می‌کردند، معرفی کرد. به دلیل نقوص طرح pkcs #1، بلیچنباخر قادر شد حمله ای علیه پیاده‌سازی‌های پروتکل لایه‌های امنی که با استفاده از RSA پیاده‌سازی شده بود را اجرا کند و کلیدهای session را بازیابی کند. به عنوان نتیجهٔ این کار، رمزنگاران امروزه پیشنهاد می‌کنند تا از طرح‌های لایه گذاری بسیار ایمن مانند لایه گذاری رمزنگاری متقارن بهینه و RSA Laborat استفاده شود.
یک حملهٔ تحلیل کانال جانبی از تحلیل پیش‌بینی شاخه (BPA) توضیح داده شده‌است. خیلی از پردازنده‌ها از پیش‌بینی شاخه برای فهمیدن اینکه آیا یک شاخه شرطی است و یک جریان دستورات آیا رخ می‌دهد یا نه استفاده می‌کنند. این پردازنده‌ها همچنین چندرشتگی همزمان را پیاده‌سازی می‌کنند. حملهٔ تحلیل کانال جانبی از یک پروسس جاسوس برای پیدا کردن کلید خصوصی از لحاظ آماری هنگامی که با این پردازنده‌ها استفاده می‌شود استفاده می‌کند.
تحلیل پیش‌بینی شاخه ساده (SBPA) ادعا می‌کند که کار تحلیل پیش‌بینی شاخه در راه غیر آماری انجام می‌دهد. در مقالهٔ On the Power of Simple Branch Prediction Analysis، نویسندهٔ SBPA ادعا می‌کند که ۵۰۸ بیت از ۵۱۲ بیت کلید RSA را در ۱۰ دوره پیدا کرده‌است.
اعداد اول ساخته شده می‌تواند حملهٔ جدول رنگین کمانی ایجاد کند به این خاطر که اعداد تصادفی ساخته شده ثابت اند.