آراس‌ای

Rivest–Shamir–Adleman آراس‌اِی ریوست-شمیر-ادلمن (RSA) [persian-alpha 1] از اولین شیوه های رمزنگاری به روش کلید عمومی (Public Key Cryptography PKC) است که به صورت گسترده برای تامین امنیت انتقال داده استفاده می شود. در این چنین سیستم های رمزنگاری، کلید رمزگذاری عمومی است و از کلید رمزگشایی که مخفی است، جداست. در آراس‌اِی، این عدم تقارن مبتنی بر این است که تجزیه از عددی که ضرب دو عدد اول بزرگ است در عمل بسیار دشوار است.

این روش، نخستین روش مورد اعتماد در بین روش‌های رمزنگاری دیگر است و یکی از بزرگ‌ترین پیشرفت‌ها در زمینهٔ رمزنگاری به حساب می‌آید. آراس‌ای همچنان به صورت گسترده‌ای در تبادلات الکترونیکی استفاده می‌شود و در صورت استفاده درست با کلیدهای طولانی کاملاً امن به نظر می‌رسد.

حروف اولیه RSA، حروف اولیه نام های خانوادگی Ron RIvest ، Adi Shamir و Adleman است که در سال 1977 این الگوریتم را به طور عمومی معرفی کردند. یک ریاضی دان انگلیسی به نام Clifford Cocks، که برای ستاد ارتباطات دولت بریتانیا کار می کرد، سیستمی معادل این سیستم را در سال 1973 پیاده سازی کرده بود، که تا سال 1973 به صورت محرمانه باقی ماند.

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

RSA به صورت نسبی، الگوریتم کندی است و به همین علت، کمتر برای رمزگذاری مستقیم اطلاعات کاربر استفاده می شود. بیشتر اوقات، RSA کلید رمزگشایی شده را برای الگوریتم کلید متقارن انتقال می دهد که در عوض قادر است توده ای از عملیات رمزگذاری-رمزگشایی را با سرعتی بسیار بالاتر انجام دهد.

تاریخچه

ایده ی کلید عمومی-خصوصی نام متقارن در سال ۱۹۷۶ (میلادی) توسط وایتفیلد دیف (Whitfield Diffie) و مارتین هلمن (Martin Hellman) دانشجویان دانشگاه استنفورد معرفی و به ثبت رسانده شد. در این روش که به روش رمزنگاری نامتقارن (asymmetric encryption) نیز شناخته می‌شود از دو کلید برای رمزنگاری اطلاعات استفاده می‌کند. در روش‌های قدیمی‌تر از یک کلید استفاده می‌شد که به آن رمزنگاری متقارن (symmetric encryption) گفته می‌شد. آن ها هم چنین امضای مجازی را معرفی کردند و تلاش کردند تا نظریه اعداد را نیز اعمال کنند. آن‌ها مقاله خود را با نام Transactions on Information Theory در یکی از شماره‌های سال ۱۹۷۶ مجله مؤسسه مهندسان برق و الکترونیک (IEEE) منتشر کردند که خیلی زود انقلابی در صنعت رمزنگاری در جهان به وجود آورد. رمزنگاری به روش کلید عمومی به معنی استفاده از کلید عمومی برای رمزنگاری و پنهان کردن اطلاعات است. در این روش هر کاربر برای رمزنگاری یا باز کردن رمز، دو کلید، یکی کلید عمومی (Public) و یکی کلید خصوصی (Private) در اختیار دارد. ویژگی این روش آن است که هر کدام از این کلیدها می‌توانند اطلاعاتی را که کلید دیگر رمزنگاری کرده‌است رمزگشایی کند.

رونالد ریوست، ادی شامیر، و لئونارد آدلمن در مؤسسه فناوری ماساچوست (اِم‌آی‌تی) تلاش های بسیاری برای ساختن یک تابع یک طرفه که معکوس کردن آن بسیار دشوار بود کردند. ریوست و شمیر که دانشمند حوزه علوم کامپیوتر بودند توابع بسیاری را پیشنهاد دادند در حالی که آدلمن که یک ریاضی دان بود، مسئول یافتن نقاط ضعف این توابع بود. آن ها رویکرد های متعددی از جمله رویکردی بر اساس مسئله ی کوله پشتی و "جایگشت چند جمله ای" را امتحان کردند. برای مدتی به نظر می رسید یافتن تابعی که در جستجوی آن هستند، ناممکن است. در آوریل سال 1977، پس از این که از یک جمع دانشجویی باز گشتند و مقداری نوشیده بودند، ریوست که نمی توانست بخوابد روی مبل دراز کشید و شروع به مطالعه ی یک کتاب ریاضی کرد و کل شب را به تفکر راجع به تابع مذکور کرد. روز بعد، مقدار زیادی از مقاله ای که منتشر کردند آماده بود.

الگوریتم RSA در سال ۱۹۷۷ (میلادی) پایه‌گذاری و به این نام شناخته شد.

هرچند روش‌های اولیه آن پیشتر در سال ۱۹۷۳ (میلادی) توسط فردی به نام کلیفورد کاکس که در ستاد روابط دولت بریتانیا بدست آمده بود اما تا سال ۱۹۷۷ اولاً الگورتیم رمزنگاری او کاملاً محرمانه بود و دوم اینکه به سادگی آنچه در سال ۱۹۷۶ مطرح شد نبود. گرچه این الگوریتم در زمانی که توسط کاکس کشف شد به علت هزینه ی بسیار زیاد کامپیوتر هایی که برای پیاده سازی آن لازم بودند، هیچ گاه پیاده سازی نشد.

RSA کودکان یا kid-RSA، یک الگوریتم رمزگشایی کلید عمومی ساده سازی شده است که در سال 1997، برای اهداف آموزشی معرفی شد. بعضی افراد معتقدند که مطالعه ی این الگوریتم، برای فهم RSA دید می دهد.

ثبت اختراع

اختراع 4،405،829 در سال 1983 به موسسه ی فناوری ماساچوست یا MIT با عنوان "سیستم و روش ارتباطات رمزنگاری" که در سال 1983از این الگوریتم استفاده کرد، اهدا شد.

چگونگی کارکرد

کلیات

RSA شامل 4 مرحله است: ساخت کلید، توزیع کلید، رمزنگاری و رمزگشایی.

یک اصل اساسی در RSA این است که یافتن سه عدد صحیح مثبت بسیار بزرگ مانند e, n و d که رابطه ی زیر برایشان بر قرار باشد، عملی است.

${\displaystyle (m^{d})^{e}\equiv m(\mod n\qquad )}$

و با دانستن این که e و n و یا حتی m، یافتن d می تواند بسیار مشکل باشد.

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

کلید عمومی توسط اعداد صحیح n و e نمایش داده میشود و کلید خصوصی، توسط عدد صحیح d( گرچه n در فرایند رمزگشایی هم استفاده می شود بنا بر این ممکن است قسمتی از کلید خصوصی هم در نظر گرفته شود). m، نمایان گر پیام است که از قبل توسط یک تکنیک خاص آماده شده است و در ادامه این تکنیک شرح داده شده است.

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

آراس‌ای مبتنی بر توان‌رسانی پیمانه‌ای است و از اعداد طبیعی خیلی بزرگ استفاده می‌کند. مستندات آراس‌ای تحت عنوان PKCS 1 استاندارد شده‌اند.

ساخت کلید

مراحل زیر برای ساخت کلید طی می‌شود:

1. دو عدد اول بزرگ ${\displaystyle p}$ و ${\displaystyle q}$ را به صورت تصادفی بیابید به‌طوری‌که ${\displaystyle p\neq q}$.

• برای اهداف امنیتی، p و q باید به صورت تصادفی انتخاب شوند، و در اندازه مشابه باشند اما طول آن ها در حد چند رقم متفاوت باشد تا تجزیه را کمی دشوار تر کند. اعداد صحیح اول می توانند به صورت کارآمد توسط یک تست اول بودن یافت شوند.
• p و q پنهان باقی می مانند.

2.عدد n را محاسبه کنید به‌طوری‌که ${\displaystyle n=pq}$.

• n به عنوان پیمانه برای هر دو کلید خصوصی و عمومی استفاده می شود. طول کلید، تعداد بیت های n، طول کلید را مشخص می کند.

3.تابع ${\displaystyle \lambda (n)}$ را محاسبه کنید که ${\displaystyle \lambda }$ Carmichael function است . از آن جایی که n=pq، ${\displaystyle \lambda (n)=lcm(lambda(p),lambda(q))}$ و از آن جایی که p و q اول هستند، ${\displaystyle \lambda (p)=\phi (p)=p-1}$ و به همین روال ${\displaystyle \lambda (q)=q-1}$. بنابراین ${\displaystyle \lambda (n)=lcm(p-1,q-1)}$

• این مقدار مخفی باقی می ماند.
• مقدار lcm ممکن است از طریق الگوریتم اقلیدسی محاسبه شود، از آن جایی که ${\displaystyle lcm(a,b)=|ab|/\gcd(a,b)}$

4.عدد ${\displaystyle e}$ را انتخاب کنید به‌طوری‌که ${\displaystyle 1<e<\lambda (n)}$ و نسبت به ${\displaystyle \lambda (n)\,}$ اول باشد.

• عدد ${\displaystyle e}$ به عنوان توان کلید عمومی منتشر می‌شود.
• e با داشتن تعداد کم بیت و وزن وزن همینگ کم، منجر به رمزگذاری کارآمد تری می شود. معمول ترین مقدار انتخاب شده برای e، حدود عدد۲^۱۶ یک که برابر با 65536 است می باشد. کوچک ترین و سریع ترین مقدار ممکن برای e ، عدد 3 است اما چنین مقدار کمی نشان داده است که در بعضی ساختار ها امنیت کم تری را ایجاد می کند.

5.عدد ${\displaystyle d}$ که ${\displaystyle d\equiv e^{-}1(\mod \lambda (n))}$ را به دست بیاورید.

• عدد ${\displaystyle d}$ به عنوان توان کلید خصوصی محافظت می‌شود.
• در واقع ${\displaystyle de\equiv 1{\pmod {\lambda (n)}}}$ . این مقدار می تواند به صورت کارآمدی توسط الگوریتم تعمیم‌یافته اقلیدس پیدا شود از آن جایی که d و ${\displaystyle \lambda (n)}$ اول هستند،این معادله یک فرمی از قضیه بزو است که در آن d یکی از ضریب ها است.

دو عدد اول می‌توانند توسط روش پیدا کردن اعداد اول احتمالی پیدا شوند.

• کلید عمومی تشکیل می‌شود از:
  • عدد n (عدد مشترک)
  • عدد e (عدد عمومی)
• کلید خصوصی تشکیل می‌شود از:
  • عدد n (عدد مشترک)
  • عدد d (عدد خصوصی)
• کلید خصوصی به صورت‌های دیگری غیر از ${\displaystyle d}$ ممکن است نگهداری شود.
  • ${\displaystyle p\,}$ و ${\displaystyle q\,}$: اعداد اول برای ساختن کلید.
  • ${\displaystyle d\mod (p-1)\,}$ و ${\displaystyle d\mod (q-1)\,}$،
  • ${\displaystyle q^{-1}\mod (p)\,}$.
• در تمام مراحل باید اجزای کلید خصوصی سری نگه داشته شود، دو عدد ${\displaystyle p}$ و ${\displaystyle q}$ اگر به عنوان صورتی از کلید خصوصی نگهداری نشود بهتر است به شیوه‌ای امن نابود شوند. زیرا با این دو عدد تمام اعداد ${\displaystyle n}$ و ${\displaystyle e}$، ${\displaystyle d}$ قابل محاسبه خواهند بود.

توزیع کلید

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

رمزنگاری پیام

حالا که باب کلید عمومی آلیس را دریافت کرد، قصد دارد پیام M را به توسط الگوریتم RSA به آلیس بفرستد. با باید پیام خود را در قالب یک عدد (m) در بیاورد به‌طوری‌که این فرایند برگشت‌پذیر بوده و روی آن توافق شده باشد و شناخته شده باشد. به این فرایند طرح لایه گذاری گفته می شود.عدد باب باید از n کوچک‌تر باشد. بدیهی است اگر پیام بزرگ‌تر از حد معمول باشد آن را در بسته‌های جداگانه می‌فرستیم. او اکنون عدد C را محاسبه می‌کند به‌طوری ‌که

${\displaystyle c=m^{e}\mod {n}}$

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

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

رمز گشایی پیام

آلیس c را دریافت کرده است و کلید خصوصی خود را در دسترس دارد. حال می تواند عدد m را که معادل پیام اصلی است از C ،n، و d بازیابی کند.

${\displaystyle m=c^{d}\mod {n}}$

نمونه

1. انتخاب دو عدد اول مانند:

   ${\displaystyle p=61}$ and ${\displaystyle q=53}$

2. محاسبه n = pq:

   ${\displaystyle n=61\times 53=3233}$

3. محاسبه تابع فی اویلر با ساخت φ(n) = (p − 1)(q − 1) خواهدشد:

   ${\displaystyle \varphi (3233)=(61-1)(53-1)=3120}$

4. انتخاب هر عددی ${\displaystyle 1<e<3120}$ که نسبت به ۳۱۲۰ اول باشد.

   ${\displaystyle e=17}$ در نظر می‌گیریم

5. محاسبه d, the وارون ضربی (هم‌نهشتی) e (mod φ(n)) ,

   ${\displaystyle d=2753}$

   ${\displaystyle e\times d\;\operatorname {mod} \;\varphi (n)=1}$

   ${\displaystyle 17\times 2753\;\operatorname {mod} \;3120=1}$

کلید عمومی (n = 3233, e = ۱۷) برای پیام m هست. بنابران تابع رمز به صورت زیر است:

${\displaystyle c(m)=m^{17}\;\operatorname {mod} \;3233}$

کلید خصوصی (d = ۲۷۵۳) هست. برای متن رمز c تابع رمزگشایی به صورت زیر خواهد بود:

${\displaystyle m(c)=c^{2753}\;\operatorname {mod} \;3233}$

برای نمونه در رمزنگاری m = ۶۵, را حساب می‌کنیم.

${\displaystyle c=65^{17}\;\operatorname {mod} \;3233=2790}$

برای رمزگشایی c = ۲۷۹۰ را حساب می‌کنیم.

${\displaystyle m=2790^{2753}\;\operatorname {mod} \;3233=65}$

نمونه دیگر

● تهیه کلیدهای عمومی و خصوصی به‌طور خلاصه روش کار برای تهیه کلیدها به شرح زیر است: ۱- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام‌های p و q را انتخاب می‌کنیم، بهتر است این اعداد از لحاظ سایز نزدیک به یکدیگر باشند. ۲- عدد دیگری به نام n را معادل با حاصلضرب p در q تعریف می‌کنیم: n = p x q ۳- عدد چهارم یعنی m را معادل حاصلضرب p-۱ در q-۱ تعریف می‌کنیم: (m = (p-۱) x (q-۱ ۴- عدد e را که از m کوچکتر است آنگونه پیدا می‌کنیم که بزرگترین مقسوم علیه مشترک این دو یک باشد به عبارتی نسبت به هم اول باشند. ۵- عددی مانند d را پیدا کنید که باقی‌مانده حاصلضرب d در e تقسیم بر m مساوی عدد ۱ باشد، یعنی: d x e) mod m = ۱) حال پس از طی این مراحل شما می‌توانید از e و n به عنوان کلید عمومی و از d و n به عنوان کلید اختصاصی استفاده کنید.

● روش پنهان کردن و آشکار کردن برای رمزنگاری اطلاعات کافی است عدد منتصب به هر کاراکتر - مثلاً 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 = ۱) صادق باشد اعداد ۱٬۲,۳٬۴,۵ و... را امتحان می‌کنیم، بنظر می‌رسد که عدد ۷ برای اینکار مناسب باشد چرا که ۷x۳=۲۱ باقی‌مانده‌ای معادل ۱ بر m=۲۰ دارد. حال می‌توانیم از زوج (۳۳٬۳) به عنوان کلید عمومی و از زوج (۳۳٬۷) به عنوان کلید خصوصی استفاده کنیم. حال اگر از فرمول‌هایی که در مطلب قبل برای رمزنگاری و آشکارسازی استفاده کنیم برای اعداد ۱ تا ۱۶۳۲ به جدول زیر خواهیم رسید. m: ۰ ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ c: ۰ ۱ ۸ ۲۷ ۳۱ ۲۶ ۱۸ ۱۳ ۱۷ ۳ ۱۰ ۱۱ ۱۲ ۱۹ ۵ ۹ ۴ m: ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ c: ۲۹ ۲۴ ۲۸ ۱۴ ۲۱ ۲۲ ۲۳ ۳۰ ۱۶ ۲۰ ۱۵ ۷ ۲ ۶ ۲۵ ۳۲ بنابراین هم‌اکنون شما یک جدول تبدیل کد دارید که با کمک کلید عمومی اعداد صفر تا ۳۲ را به اعدادی کد شده و در همین رنج تبدیل کرده‌اید. اما اگر دقت کنید تعدادی از اعداد دقیقاً به همان عدد خود تبدیل شده‌اند که به این‌ها unconcealed یا مخفی نشده گفته می‌شود. اولآ باید بدانیم که ۰ و ۱ همواره به همین اعداد تبدیل می‌شوند و مطلب دیگر اینکه اگر رنج دو عدد اول ابتدایی را بزرگ در نظر بگیریم دیگر مشکلی پیش نخواهد آمد. حال کافی است فرض کنیم A=۲، B=۳، C=۴ و... Z=۲۷ و جملات مربوطه را کد نماییم. دقت کنید که معمولاً از ۰ و ۱ برای رمزنگاری استفاده نمی‌شود.

کد

'use strict';

/**
 * RSA hash function reference implementation.
 * Uses BigInteger.js https://github.com/peterolson/BigInteger.js
 * Code originally based on https://github.com/kubrickology/Bitcoin-explained/blob/master/RSA.js
 */
const RSA = {};

/**
 * Generates a k-bit RSA public/private key pair
 * https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Code
 *
 * @param   {keysize} int, bitlength of desired RSA modulus n (should be even)
 * @returns {array} Result of RSA generation (object with three bigInt members: n, e, d)
 */
RSA.generate = function(keysize) {
  /**
   * Generates a random k-bit prime greater than √2 × 2^(k-1)
   *
   * @param   {bits} int, bitlength of desired prime
   * @returns {bigInt} a random generated prime
   */
  function randomPrime(bits) {
    const min = bigInt(6074001000).shiftLeft(bits - 33);  // min ≈ √2 × 2^(bits - 1)
    const max = bigInt.one.shiftLeft(bits).minus(1);  // max = 2^(bits) - 1
    for (;;) {
      const p = bigInt.randBetween(min, max);  // WARNING: not a cryptographically secure RNG!
      if (p.isProbablePrime(256)) {
        return p;
      }
    }
  }

  // set up variables for key generation
  const e = bigInt(65537);  // use fixed public exponent
  let p;
  let q;
  let lambda;

  // generate p and q such that λ(n) = lcm(p − 1, q − 1) is coprime with e and |p-q| >= 2^(keysize/2 - 100)
  do {
    p = randomPrime(keysize / 2);
    q = randomPrime(keysize / 2);
    lambda = bigInt.lcm(p.minus(1), q.minus(1));
  } while (bigInt.gcd(e, lambda).notEquals(1) || p.minus(q).abs().shiftRight(
      keysize / 2 - 100).isZero());

  return {
    n: p.multiply(q),  // public key (part I)
    e: e,  // public key (part II)
    d: e.modInv(lambda),  // private key d = e^(-1) mod λ(n)
  };
};

/**
 * Encrypt
 *
 * @param   {m} int / bigInt: the 'message' to be encoded
 * @param   {n} int / bigInt: n value returned from RSA.generate() aka public key (part I)
 * @param   {e} int / bigInt: e value returned from RSA.generate() aka public key (part II)
 * @returns {bigInt} encrypted message
 */
RSA.encrypt = function(m, n, e) {
  return bigInt(m).modPow(e, n);
};

/**
 * Decrypt
 *
 * @param   {c} int / bigInt: the 'message' to be decoded (encoded with RSA.encrypt())
 * @param   {d} int / bigInt: d value returned from RSA.generate() aka private key
 * @param   {n} int / bigInt: n value returned from RSA.generate() aka public key (part I)
 * @returns {bigInt} decrypted message
 */
RSA.decrypt = function(c, d, n) {
  return bigInt(c).modPow(d, n);
};

امضای پیام

فرض کنید آلیس از کلید عمومی باب برای ارسال پیام رمزگذاری شده برای وی استفاده می کند. در این پیام، او می تواند ادعا کند که آلیس است، اما باب هیچ راهی برای تایید این که این پیام واقعا از طرف آلیس است ندارد، چرا که هر کس می تواند از کلید عمومی باب برای ارسال پیام های رمز گذاری شده به وی استفاده کند. برای تایید منشاء پیام، می توان از RSA برای امضا کردن یک پیام استفاده کرد.

فرض کنید آلیس مایل است پیام امضا شده ای را به باب ارسال کند. او می تواند برای این کار از کلید خصوصی خود استفاده کند. برای این کار، او مقدار هش پیام مورد نظر خود را محاسبه می کند، آن را به توان d می رساند( در پیمانه ی n)(همان طور که هنگام رمزگشایی یک پیام این کار را انجام می دهد) و آن را به عنوان "امضا" به پیام خود الصاق می کند. هنگامی که باب این پیام امضا شده را دریافت می کند، او هم از همان تابع هش در رابطه با کلید عمومی آلیس استفاده می کند. او این امضا را به توان e (در پیمانه ی m ) می رساند ( همان طور که این کار را هنگام رمزگشایی یک پیام نیز انجام می دهد) و مقدار هش حاصل را با مقدار هش واقعی پیام مقایسه می کند. اگر این دو با هم توافق داشته باشیند، او می داند که نویسده پیام کلید خصوصی آلیس را در اختیار داشته است و پیام از آن زمان دست نخورده باقی مانده است.

این روش به دلیل قوانین به توان رسانی، کار می کند:

${\displaystyle h=hash(m)}$

${\displaystyle (h^{e})^{d}=h^{ed}=(h^{d})^{e}\equiv h(\mod n)}$

بنابر این ، کلید خصوصی می تواند برای :

1. رمزگشایی یک پیام که برای یک گیرنده فرستاده شده است، که می تواند توسط هر فردی که دارای کلید عمومی است، برای رمزنگاری استفاده شود.
2. رمزنگاری یک پیام که ممکن است توسط هر کس رمزگشایی شود، اما فقط توسط یک نفر می تواند رمزنگاری شود، این استفاده، امضای دیجیتال را ممکن می سازد.

اثبات درستی

اثبات با استفاده از قضیه کوچک فرما

اثبات درستی الگوریتم RSA بر اساس قضیه کوچک فرما است که بیان می کند که اگر یک عدد p اول و a عددی صحیح باشد که ${\displaystyle {\displaystyle p\not |a}}$در این صورت${\displaystyle {\displaystyle a^{p-1}\equiv 1{\pmod {p}}}{\displaystyle a^{p-1}\equiv 1{\pmod {p}}}.}$ .

ما می خواهیم نشان دهیم که برای هر عدد صحیح m در صورتی که p و q اعداد اول مجزا از هم هستند و e و e اعداد صحیح مثبتی هستند که مقدار آن ها در معادله ی ${\displaystyle ed\equiv 1(\mod \lambda (pq)).}$ صدق می کند :

${\displaystyle {\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}}}$

از آن جایی که ${\displaystyle \lambda (pq)=Icm(p-1,q-1)}$ به علت ساختارش، هم بر p-1 و هم بر q-1 بخش پذیر است، می توان به ازای یک مقدار غیر منفی h و k نوشت :

${\displaystyle {\displaystyle ed-1=h(p-1)=k(q-1)}}$

برای بررسی این که آیا دو عدد مانند ${\displaystyle m^{d}}$ و m، به پیمانه ی pq معادل هستند یا خیر، بررسی می کنیم که آیا آن ها به پیمانه ی p و به پیمانه ی q به صورت جداگانه ، معادل هستند یا خیر. اگر بودند ، به پیمانه ی pq هم معادلند.

برای این که نشان دهیم ${\displaystyle m^{ed}\equiv m(\mod p)}$، دو حالت را در نظر می گیریم :

1. اگر ${\displaystyle m\equiv 0(\mod p)}$، آن گاه m، ضریبی از p است. بنابراین ${\displaystyle m^{ed}}$ ، ضریبی از p است، بنابراین ${\displaystyle m^{ed}\equiv m\equiv 0(\mod p)}$
2. اگر ${\displaystyle m\not \equiv 0(\mod p)}$

${\displaystyle {\displaystyle m^{ed}=m^{ed-1}m=m^{h(p-1)}m=(m^{p-1})^{h}m\equiv 1^{h}m\equiv m{\pmod {p}},}}$

اینجا از قضیه کوچک فرما استفاده کردیم تا ${\displaystyle m^{p-1}\mod p}$ را با 1 جایگزین کنیم.

برای این که تایید کنیم ${\displaystyle m^{ed}\equiv m(\mod q)}$، کاملا مشابه عمل می کنیم :

1. اگر ${\displaystyle m\equiv 0(\mod q)}$، آن گاه m، ضریبی از q است. بنابراین ${\displaystyle m^{ed}}$ ، ضریبی از q است، بنابراین ${\displaystyle m^{ed}\equiv m\equiv 0(\mod q)}$
2. اگر ${\displaystyle m\not \equiv 0(\mod q)}$

${\displaystyle {\displaystyle m^{ed}=m^{ed-1}m=m^{k(q-1)}m=(m^{q-1})^{k}m\equiv 1^{k}m\equiv m{\pmod {q}}.}}$

در این نقطه ، اثبات می شود که برای هر عدد صحیح m و عدد صحیح e و d که ${\displaystyle ed\equiv 1(\mod \lambda (pq)).}$،

${\displaystyle {\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}.}}$

اثبات از طریق قضیه اویلر

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

می خواهیم نشان دهیم که ${\displaystyle m^{ed}\equiv m(\mod n)}$ وقتی که n = pq است، حاصل ضرب دو عدد عول است و e و d اعداد صحیح مثبتی هستند که در معادله ی ${\displaystyle ed\equiv 1(\mod \phi (n))}$ صدق می کنند. از آن جایی که e و d مثبت هستند، می توانیم به ازای یک مقدار نامنفی صحیح h بنویسیم ${\displaystyle ed=1+h\phi (n)}$. در صورتی که فرض کنیم m نسبت به n اول است، داریم:

${\displaystyle {\displaystyle m^{ed}=m^{1+h\varphi (n)}=m(m^{\varphi (n)})^{h}\equiv m(1)^{h}\equiv m{\pmod {n}}}}$

در دومین آخرین تساوی در معادله بالا، عبارت داخل پرانتز شرایط قضیه اویلر را دارد و بنابر این در تساوی بعدی با 1 جایگزین می شود.

به صورت کلی تر، برای هر e و d که در معادله ی ${\displaystyle ed\equiv 1(\mod \lambda (pq)).}$ صدق می کنند می توان نتیجه مشابهی را با استفاده از تعمیم قضیه ی اویلر توسط کارمایکل، که بیان می کند برای همه ی m هایی که نسبت به n اولند : ${\displaystyle m^{\lambda (n)}\equiv 1(\mod n)}$، گرفت.

هنگامی که m نسبت به n اول نیست، نتیجه گیری بالا نا معتبر است. اما احتمال وقوع این امر بسیار پایین است (تنها ${\displaystyle 1/p+1/q-1/{pq}}$ اعداد این ویژگیرا دارند)، اما حتی در این حالت هم، معادله ی مذکور صادق است.

یا ${\displaystyle m\equiv 0(\mod p)}$ یا ${\displaystyle m\not \equiv 0(\mod q)}$، که در هر کدام از این موارد، می توان اثبات قبلی را به کار گرفت.

اجزای سامانه رمزنگاری

• کلید رمزنگاری
• الگوریتم رمزنگاری
• کلید رمزگشایی
• الگوریتم رمزگشایی
• اگر از یک کلید برای رمزنگاری و رمزگشایی استفاده شود سامانه رمزنگاری متقارن است و در غیر اینصورت، نامتقارن خواهد بود.

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

الگوریتم‌های کلید متقارن:

رمزنگاری و رمزگشایی با یک کلید انجام می‌گیرد.

الگوریتم‌های کلید نامتقارن (کلید عمومی):

هر فرد یک کلید عمومی و یک کلید خصوصی دارد.

دفی هلمن و RSA نمونه‌ای از این الگوریتم‌ها است.

کاربرد در امضای دیجیتال.

کلیدهای این نوع از الگوریتم‌ها (نامتقارن) بسیار طولانی‌تر از الگوریتم‌های مرسوم (کلید متقارن) هستند.

شکستن الگوریتم

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

تجزیه n به عوامل اول

نخستین روش، آن است که بتوان کلید خصوصی را حدس زد یا پیدا کرد. در این صورت رخنه‌گر می‌تواند همه متن‌های تهیه شده با کلید عمومی را رمزگشایی کند و بخواند یا می‌تواند از امضای الکترونیک صاحب کلید استفاده کند. فرض بر این است که فردی که قصد حدس زدن کلید خصوصی را دارد، از جمله افرادی است که کلید عمومی را دارا است. در این حالت او n و e را در دسترس دارد.

روش مؤثر برای محاسبه ریشه e ام

برای باز کردن رمز پیام‌هایی که با الگوریتم RSA رمزنگاری شده‌اند روش‌های محاسبه ریاضی عملاً راه به جایی نمی‌برند و در مواردی که متن کوچک باشد شاید حدس زدن متن اصلی ساده‌ترین روش برای رمزگشایی باشد.

راه‌های مقابله با حمله زمانی به RSA

استفاده از به توان رساندن با زمان ثابت محاسباتی.

تابع باید به ازای همه ورودی‌ها زمان ثابتی به طول بینجامد

قرار دادن اعمال اضافی و گمراه‌کننده در بین محاسبات

ضرب کردن متن رمزنگاری شده در یک عدد تصادفی قبل از عملیات به توان رسانی

اضافه کردن تاخیرهای تصادفی

لایه گذاری

حمله به RSA ساده

چندین نوع حمله به RSA ساده وجود دارد که در پاینن توضیح می‌دهیم

• هنگامی که رمز گذاری با توان رمز گذاری پایین مانند e برابر۳ و مقادید کوچک برای m یعنی (m < n^1/e) استفاده می‌کند این نتیجه می‌شود که m^e به شدت از ضریب n کوچک تر شود، که این باعث می‌شود که متن رمز شده بتوان به راحتی رمزگشایی شود به وسیله‌ی گرفتن جذر e ام برروی اعداد صحیح به دست آید
• اگر متن یکسانی به e یا بیشتر گیرنده فرستاده شود به به صورت رمز شده فرستاده شود و گیرنده ها توان e ی یکسانی داشته باشند اما p و q و طبیعتا n متفاوتی داشته باشند، در آن زمان به راحتی می‌توان متن اصلی را با استفاده از روش قضیه باقی‌مانده چینی به دست آورد. یوان هواستاد متوجه شد که این حمله ممکن است حتی اگر متن رمز نشده یکسان نباشد اما حمله کنند ارتباط بین آن‌ ها را بداند. این حمله بعد توسط دان کاپرسمیت پیشرفته تر شد. برای اطلاعات بیشتر حمله مسگر را ببینید
• به علت اینکه رمز نگاری RSA الگوریتم قطعی است (به عنوان مثال هیچ بخش تصادفی‌ای ندارد) حمله کننده می‌تواند به راحتی حمله با متن اصلی منتخب را بر روی سیستم رمز نگاری اجرا کند. با رمز کردن متن‌های احتمالی با کلید عمومی و تست کردن برابری با متن رمز شده. یک سیستم رمز نگاری امنیت معنایی خوانده می‌شود اگر حمله کننده نتواند دو رمز نگاری را حتی اگر متن اصلی را بداند تمایز قائل شود. بر همین اساس RSA بدون لایه گذاری به صورت قطعی امن نیست.
• RSA یک ویژگی دارد که متن رمز شده‌ی ۲ متن برابر است با محصول به ترتیب ۲ متن رمز‌نشده‌یشان. یعنی ( m₁^em₂^e ≡ (m₁m₂)^e (mod n. به علت ویژگی ضرب RSA، حمله با متن رمز منتخب ممکن است. به عنوان مثال حمله کننده که خواستار متن رمز‌نشده ی یک متن رمزشده‌ی (c ≡ m^e (mod n می تواند از دارنده ی کلید خصوصی بخواهد که یک متن غیر مشکوک رمز شده را (c′ ≡ cr^e (mod n را برای مقدار r که توسط حمله کننده انتخاب شده است رمز گشایی کند . به خاطر ویژگی ضرب 'c رمز شده ی (mr (mod n است. بنابر این اگر حمله گر موفق باشد در حمله. او مقدار (mr (mod n را می فهمد و می تواند به وسیله‌ی آن پیام m را با ضرب در mr با پیمانه‌ی برعکس r پیمانه ی n به دست آورد.

طرح لایه بندی

برای دوری از این مشکل ها 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 بر اساس دو مسئله ی ریاضی هست، تجزیه اعداد طبیعی و RSA problem.

کل رمزگشایی رمزنگاری RSA غیر قابل نفوذ پنداشته می شد بر فرض سخت بودن این ۲ مسئله یعنی هیچ الگوریتم بهینه ای برای حل آن‌ها موجود نبود. که فراهم کردن امنیت در برابر رمزگشایی جزئی ممکن است نیازمند اضافه کردن Padding_cryptography امن باشد.

مسئله ی RSA تعریف شده به عنوان کار گرفتن e امین ریشه‌ی مرکب n:

بازیابی مقدار m به طوری که (c ≡ m^e (mod n در حالی که (n, e) همان کلید عمومی RSA است و c متن رمز شده‌ی RSA است. در حال حاضر بهترین الگوریتم ارائه شده برای حل کردن مسئله‌ی RSA استفاده از تجزیه بر مبنای n است. با این توانایی بازیابی اعداد اول، حمله کننده می‌تواند توان مخفی d را از کلید (n,e) محاسبه کند و سپس c را با استفاده از روش استاندارد رمزگشایی کند. برای دستیابی به این هدف، حمله کننده باید عوامل n به p و q را به دست آورد و سپس بزرگترین مضرب مشترک آنان را به دست آورد که به او اجازه ی تعیین d و e را می دهد. هیچ راه غیر چند جمله ای برای این کار تجزیه ی اعداد طبیعی بزرگ بر روی کامپیوتر های معمولی هنوز پیدا نشده است، اما اثبات نشده است که وجود ندارد. برای مطالعه‌ی بیشتر تجزیه اعداد طبیعی را بحوانید.

روش خطی مرتبه‌ دو ی چندگانه (MPQS) می تواند برای پیدا کردن تجزیه ی عدد عمومی n استفاده شود. زمان لازم برای محاسبه‌ی n ای که 128 بیت و ۲۵۶ بیت است بر روی کامپیوتر خانگی (پردازنده: Intel Dual-Core i7-4500U 1.80GHz) به ترتیب ۲ ثانیه و ۳۵ ثانیه است.

تعداد بیت	زمان(ثانیه)
128	کمتر از ۲
192	۱۶
256	۲۱۰۰
260	۳۶۰۰

ابزاری به اسم YAFU می تواند برای تسریع این برنامه استفاده شود. با این برنامه می توان در ۵۷۲۰ ثانیه عدد n ای که ۳۲۰ بیت دارد را بر روی همان کامپیوتر تجزیه کرد.

تعداد بیت	زمان	حافظه ی مورد استفاده
128	0.4886 ثانیه	0.1 MiB
192	3.9979 ثانیه	0.5 MiB
256	103.1746 ثانیه	3 MiB
300	1175.7826 ثانیه	10.9 MiB

در سال ۲۰۰۹، بنجامین مودی یک 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 کم تر از ${\displaystyle 2n^{1/4}}$ باشد، ( مقدار n ، برابر با p*q است که حتی برای مقادیر کم 1024 بیتی هم، برابر با ${\displaystyle 3*10^{7}}$ است ) یافتن p و q بدیهی است. علاوه بر این اگر p-1 یا q-1 فقط دارای فاکتور های کوچک اول باشند، n می تواند به سرعت توسط الگوریتم پی-۱ پولارد تجزیه شود و بنابراین این گونه مقادیر برای p و q به کلی نباید انتخاب شوند.

حائز اهمیت است که d به اندازه ی کافی بزرگ باشد، مایکل واینر نشان داد که اگر p بین q و 2q باشد، (که امری بسیار معمول است) و ${\displaystyle d<n^{1/4}/3}$، آن گاه n به راحتی می توانند از مقادیر n و e به دست بیاید. هیچ حمله شناخته شده ای علیه مقادیر کوچک عمومی مانند e = 3 وجود ندارد ، مشروط بر اینکه از لایه گذاری مناسب استفاده شود.حمله مسگر کاربرد های زیادی در حمله به RSA

دارد به خصوص اگر نماینده ی عمومی e، کوچک باشد و اگر متن رمز شده کوتاه باشد و لایه گذاری شده نباشد. مقدار 65537 مقداری است که زیاد برای مقدار e استفاده می شود. این مقدار در واقع یک سازشی بین جلوگیری از حملات احتمالی کوچک و امکان وجود رمزگذاری موثر یا تایید امضا است.

حمله های زمانی

کوچر در سال 1995، یک حمله ی جدید روی RSA تعریف کرد، اگر Eve که یک حمله کننده است، سخت افزار آلیس را با جزئیات کافی بشناسد و قادر به اندازه گیری زمان رمزگشایی برای تعداد زیادی از متن های رمز شده ای که برای او شناخته باشد، اوو می تواند به سرعت کلید رمزگشایی d را پیدا کند. این حمله همچنین می تواند برای طرح امضای RSA هم استفاده شود. در سال 2003، دان بونه و دیوید بروملیحمله ی عملی تری را نشاند دادند که قادر به بازیابی تجزیه های RSA بر روی یک اتصال به شبکه بود. ( به عنوان مثال، روی یک وب سرور که قابلیت اجرای لایهٔ سوکت‌های امن (ssl) را دارد) . این حمله از اطلاعات فاش شده از بهینه سازی با قضیه ی باقی مانده ی چینی که توسط بسیاری از پیاده سازی های RSA استفاده می شود، استفاده می کند.

یک روش خنثی سازی این حمله ها این است که مطمئن شد عملیات رمزگشایی یک زمان ثابتی را برای هر متن رمز شده ای طول می کشد. اگرچه این رویکرد به شدت باعث کاهش کارایی می شود. به جای آن، اکثر پیاده سازی های RSA از یک تکنیک جایگزین به نام کور کنندگی استفاده می کنند. کور نندگی RSA ، از ویژگی ضرب RSA استفاده می کند. آلیس به جای این که ${\displaystyle c^{d}(\mod n)}$ را محاسبه کند، ابتدا یک مقدار تصادفی مخفی مانند r را انتخاب می کند و ${\displaystyle (r^{e}c)^{d}(\mod n)}$ را محاسبه می کند. نتیجه ی این محاسبه پس از اعمال قضیه ی اویلر ${\displaystyle rc^{d}(\mod n)}$ می باشد و بنابراین تاثیر r می تواند با ضرب در معکوس آن از بین برود. حال مقدار جدیدی برای r برای هر متن رمز شده انتخاب می شود. وقتی کورکنندگی اعمال می شود، زمان رمزگشایی دیگر به مقدار ورودی متن رمز شده هم بسته نیست و بنابراین حمله زمانی با شکست مواجه می شود.

حمله ی انطباقی متن رمزنگاری انتخابی

در سال 1998، بلیچنباخر اولین حمله ی انطباقی متن رمزنگاری انتخابیعملی را در مقابله با متن های رمزنگاری شده توسط RSA، که از pkcs #1 v1 استفاده می کردند،معرفی کرد. به دلیل نقوص طرح pkcs #1، بلیچنباخر قادر شد حمله ای بر علیه پیاده سازی های پروتکل لایه های امنی که با استفاده از RSA پیاده سازی شده بود را اجرا کند و کلید های session را بازیابی کند. به عنوان نتیجه ی این کار، رمزنگاران امروزه پیشنهاد می کنند تا از طرح های لایه گذاری بسیار ایمن مانند لایه گذاری رمزنگاری متقارن بهینه و RSA Laborat استفاده شود.

حملات تحلیل کانال جانبی

یک حمله ی تحلیل کانال جانبی از تحلیل پیش بینی شاخه (BPA) توضیح داده شده است. خیلی از پردازنده ها از پیش بینی شاخه برای فهمیدن اینکه آیا یک شاخه شرطی است و یک جریان دستورات آیا رخ می‌دهد یا نه استفاده می‌کنند. این پردازنده ها همچنین چندرشتگی همزمان را پیاده سازی می‌کنند. حمله ی تحلیل کانال جانبی از یک پروسس جاسوس برای پیدا کردن کلید خصوصی از لحاظ آماری هنگامی که با این پردازنده ها استفاده می‌شود استفاده می‌کند.

تحلیل پیش بینی شاخه ساده (SBPA) ادعا می کند که کار تحلیل پیش بینی شاخه در راه غیر آماری انجام می‌دهد. در مقاله ‌ی On the Power of Simple Branch Prediction Analysis، نویسنده‌ی SBPA ادعا می‌کند که ۵۰۸ بیت از ۵۱۲ بیت کلید RSA را در ۱۰ دوره پیدا کرده است.

حمله‌ی جدول رنگین کمانی

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

پانویس

منابع

• R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. ۲۱ (۲)، pp.120–126. 1978. Previously released as an MIT "Technical Memo" in April ۱۹۷۷. انتشار اولیه روش رمزنگاری آر اس ای.
• توماس اچ کورمن، Charles E. Leiserson، رونالد ریوست، و کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها، Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.7: The RSA public-key cryptosystem, pp.۸۸۱–۸۸۷.

1. رونالد ریوست -لئونارد آدلمن-ادی شامیر