آراس‌ای

ایدهٔ کلید عمومی-خصوصی نام متقارن در سال ۱۹۷۶ (میلادی) توسط وایتفیلد دیف (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 که رابطهٔ زیر برایشان بر قرار باشد، عملی است.

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

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

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

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

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

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

ساخت کلید

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

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

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

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

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

۳. تابع ${\displaystyle \lambda (n)}$

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

۴. عدد ${\displaystyle e}$

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

۵. عدد ${\displaystyle d}$

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

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

• کلید عمومی تشکیل می‌شود از:
  • عدد n (عدد مشترک)
  • عدد e (عدد عمومی)
• کلید خصوصی تشکیل می‌شود از:
  • عدد n (عدد مشترک)
  • عدد d (عدد خصوصی)
• کلید خصوصی به صورت‌های دیگری غیر از ${\displaystyle d}$
  ممکن است نگهداری شود.
  • ${\displaystyle p}$
    و ${\displaystyle q}$
    : اعداد اول برای ساختن کلید.
  • ${\displaystyle d\mathrm{mod}(p-1)}$
    و ${\displaystyle d\mathrm{mod}(q-1)}$
    ،
  • ${\displaystyle q^{-1}\mathrm{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\mathrm{mod}n}$

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

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

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

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

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

نمونه

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

   ${\displaystyle p=61}$

   and ${\displaystyle q=53}$

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

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

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

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

4. انتخاب هر عددی
   که نسبت به ۳۱۲۰ اول باشد.

   ${\displaystyle e=17}$

   در نظر می‌گیریم

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

   ${\displaystyle d=2753}$

   ${\displaystyle e\times d\mathrm{mod}\phi (n)=1}$

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

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

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

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

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

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

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

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

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

نمونه دیگر

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

۱- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام‌های 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 به عنوان کلید اختصاصی استفاده کنید.

• روش پنهان کردن و آشکار کردن برای رمزنگاری اطلاعات کافی است عدد منتصب به هر کاراکتر - مثلاً 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: ۲۹ ۲۴ ۲۸ ۱۴ ۲۱ ۲۲ ۲۳ ۳۰ ۱۶ ۲۰ ۱۵ ۷ ۲ ۶ ۲۵ ۳۲ بنابراین هم‌اکنون شما یک جدول تبدیل کد دارید که با کمک کلید عمومی اعداد صفر تا ۳۲ را به اعدادی کد شده و در همین رنج تبدیل کرده‌اید. اما اگر دقت کنید تعدادی از اعداد دقیقاً به همان عدد خود تبدیل شده‌اند که به این‌ها 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(\mathrm{mod}n)}$

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

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

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

اثبات درستی الگوریتم RSA بر اساس قضیه کوچک فرما است که بیان می‌کند که اگر یک عدد p اول و a عددی صحیح باشد که ${\displaystyle {\displaystyle p\text{⧸}|a}}$

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

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

از آن جایی که ${\displaystyle \lambda (pq)=Icm(p-1,q-1)}$

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

برای بررسی این که آیا دو عدد مانند ${\displaystyle m^d}$

برای این که نشان دهیم ${\displaystyle m^{ed}\equiv m(\mathrm{mod}p)}$

1. اگر ${\displaystyle m\equiv 0(\mathrm{mod}p)}$
   ، آن گاه m، ضریبی از p است؛ بنابراین ${\displaystyle m^{ed}}$
   ، ضریبی از p است، بنابراین ${\displaystyle m^{ed}\equiv m\equiv 0(\mathrm{mod}p)}$
2. اگر ${\displaystyle m\not\equiv 0(\mathrm{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(\mathrm{mod}p),}}$

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

برای این که تأیید کنیم ${\displaystyle m^{ed}\equiv m(\mathrm{mod}q)}$

1. اگر ${\displaystyle m\equiv 0(\mathrm{mod}q)}$
   ، آن گاه m، ضریبی از q است؛ بنابراین ${\displaystyle m^{ed}}$
   ، ضریبی از q است، بنابراین ${\displaystyle m^{ed}\equiv m\equiv 0(\mathrm{mod}q)}$
2. اگر ${\displaystyle m\not\equiv 0(\mathrm{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(\mathrm{mod}q).}}$

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

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

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

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

می‌خواهیم نشان دهیم که ${\displaystyle m^{ed}\equiv m(\mathrm{mod}n)}$

${\displaystyle {\displaystyle m^{ed}=m^{1+h\phi (n)}=m(m^{\phi (n)}{)}^h\equiv m(1{)}^h\equiv m(\mathrm{mod}n)}}$

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

به صورت کلی تر، برای هر e و d که در معادلهٔ ${\displaystyle ed\equiv 1(\mathrm{mod}\lambda (pq)).}$

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

یا ${\displaystyle m\equiv 0(\mathrm{mod}p)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

حمله به RSA ساده

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

• هنگامی که رمز گذاری با توان رمز گذاری پایین مانند e برابر۳ و مقادید کوچک برای m یعنی (m <n) استفاده می‌کند این نتیجه می‌شود که m به شدت از ضریب n کوچک‌تر شود، که این باعث می‌شود که متن رمز شده بتوان به راحتی رمزگشایی شود به وسیلهٔ گرفتن جذر e ام برروی اعداد صحیح به دست آید
• اگر متن یکسانی به e یا بیشتر گیرنده فرستاده شود به به صورت رمز شده فرستاده شود و گیرنده‌ها توان e ی یکسانی داشته باشند اما p و q و طبیعتاً n متفاوتی داشته باشند، در آن زمان به راحتی می‌توان متن اصلی را با استفاده از روش قضیه باقی‌مانده چینی به دست آورد. یوان هواستاد متوجه شد که این حمله ممکن است حتی اگر متن رمز نشده یکسان نباشد اما حمله کنند ارتباط بین آن‌ها را بداند. این حمله بعد توسط دان کاپرسمیت پیشرفته تر شد. برای اطلاعات بیشتر حمله مسگر را ببینید
• به علت اینکه رمز نگاری RSA الگوریتم قطعی است (به عنوان مثال هیچ بخش تصادفی‌ای ندارد) حمله کننده می‌تواند به راحتی حمله با متن اصلی منتخب را بر روی سیستم رمز نگاری اجرا کند. با رمز کردن متن‌های احتمالی با کلید عمومی و تست کردن برابری با متن رمز شده. یک سیستم رمز نگاری امنیت معنایی خوانده می‌شود اگر حمله کننده نتواند دو رمز نگاری را حتی اگر متن اصلی را بداند تمایز قائل شود. بر همین اساس RSA بدون لایه گذاری به صورت قطعی امن نیست.
• RSA یک ویژگی دارد که متن رمز شدهٔ ۲ متن برابر است با محصول به ترتیب ۲ متن رمزنشده‌یشان؛ یعنی (m₁m₂ ≡ (m₁m₂) (mod n. به علت ویژگی ضرب RSA، حمله با متن رمز منتخب ممکن است. به عنوان مثال حمله کننده که خواستار متن رمزنشدهٔ یک متن رمزشدهٔ (c ≡ m (mod n می‌تواند از دارندهٔ کلید خصوصی بخواهد که یک متن غیر مشکوک رمز شده را (c′ ≡ cr (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 (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 کم‌تر از ${\displaystyle 2n^{1/4}}$

حائز اهمیت است که d به اندازهٔ کافی بزرگ باشد، مایکل واینر نشان داد که اگر p بین q و 2q باشد، (که امری بسیار معمول است) و

دارد به خصوص اگر نمایندهٔ عمومی e، کوچک باشد و اگر متن رمز شده کوتاه باشد و لایه گذاری شده نباشد. مقدار ۶۵۵۳۷ مقداری است که زیاد برای مقدار e استفاده می‌شود. این مقدار در واقع یک سازشی بین جلوگیری از حملات احتمالی کوچک و امکان وجود رمزگذاری مؤثر یا تأیید امضا است.

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

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

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

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

در سال ۱۹۹۸، بلیچنباخر اولین حملهٔ انطباقی متن رمزنگاری انتخابیعملی را در مقابله با متن‌های رمزنگاری شده توسط 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. ↑ رونالد ریوست -لئونارد آدلمن-ادی شامیر

1. ↑ «Metriks Analytics». XMetriks (به انگلیسی). دریافت‌شده در ۲۰۲۱-۰۸-۳۱.