نظام التشفير RSA

يتم توليد مفاتيح خوارزمية RSA بالطريقة التالية:

1. اختر عددين أوليين كبيرين مختلفين p و q .
   • لجعل عملية التحليل إلى عوامل أولية غير ممكنة، يجب اختيار p و q عشوائيًا من مجموعة كبيرة من الاحتمالات، مثل جميع الأعداد الأولية بين 2^ ¹⁰²³ و 2^ ¹⁰²⁴ (المقابلة لمفتاح 2048 بت). تُستخدم العديد من الخوارزميات المختلفة لاختيار الأعداد الأولية في الممارسة العملية. ^{[ 29 ]}
   • يتم إبقاء p و q سراً.
2. احسب n = pq .
   • يُستخدم n كمعامل لكل من المفتاح العام والمفتاح الخاص. طوله، الذي يُعبر عنه عادةً بالبتات، هو طول المفتاح .
   • يتم إصدار n كجزء من المفتاح العام.
3. احسب λ ( n ) ، حيث λ هي دالة كارمايكل . بما أن n = pq ، فإن λ ( n ) = المضاعف المشترك الأصغر ( λ ( p ), λ ( q ))  ، وبما أن p و q عددان أوليان، فإن λ ( p ) = φ ( p ) = p - 1 ، وبالمثل λ ( q ) = q - 1. ومن ثم، فإن λ ( n ) = المضاعف المشترك الأصغر ( p - 1, q - 1) .
   • يمكن حساب المضاعف المشترك الأصغر من خلال خوارزمية إقليدس ، حيث أن lcm ( a , b ) = | ab | / gcd( a , b ) .  
   • يتم إبقاء λ ( n )
4. اختر عددًا صحيحًا e بحيث يكون 1 < e < λ ( n ) و gcd ( e , λ ( n )) = 1 ؛ أي أن e و λ ( n ) أوليان فيما بينهما .
   • يؤدي استخدام طول بت قصير ووزن هامينغ صغير لـ e إلى تشفير أكثر كفاءة - القيمة الأكثر شيوعًا لـ e هي 2 ^{^16} + 1 = ٦٥٥٣٧. أصغر قيمة ممكنة (وأسرعها) لـ e هي ٣، ولكن هذه القيمة الصغيرة لـ e قد تكشف عن ثغرات أمنية في أنظمة الحشو غير الآمنة. ^{[ ٣٠ ] [ أ ]}
   • يتم إصدار e كجزء من المفتاح العام.
5. حدد d على أنه d ≡ e ⁻¹ (mod λ ( n ) ) ؛ أي أن d هو المعكوس الضربي المعياري لـ e modulo λ ( n ) .
   • وهذا يعني: حل المعادلة de ≡ 1 (mod λ ( n ) ) ؛ يمكن حساب d بكفاءة باستخدام خوارزمية إقليدس الموسعة ، لأنه بفضل كون e و λ ( n ) أوليين فيما بينهما، فإن المعادلة المذكورة هي شكل من أشكال هوية بيزو ، حيث d هو أحد المعاملات.
   • يتم الاحتفاظ بـ d سراً باعتباره أس المفتاح الخاص .

يتكون المفتاح العام من المعامل n والأس العام e . أما المفتاح الخاص فيتكون من الأس الخاص d ، والذي يجب الحفاظ على سريته. كما يجب الحفاظ على سرية p و q و λ ( n ) لأنها تُستخدم لحساب d . في الواقع، يمكن حذفها جميعًا بعد حساب d . ^{[ 31 ]}

في ورقة RSA الأصلية ^{[ 3 ]} ، تُستخدم دالة أويلر φ ( n ) = ( p − 1)( q − 1) بدلاً من λ ( n ) لحساب الأس الخاص d . ولأن φ ( n ) تقبل القسمة دائمًا على λ ( n ) ، فإن الخوارزمية تعمل بكفاءة. وتنتج إمكانية استخدام دالة أويلر أيضًا من نظرية لاغرانج المطبقة على المجموعة الضربية للأعداد الصحيحة بتردد pq . وبالتالي، فإن أي قيمة لـ d تحقق d ⋅ e ≡ 1 (mod φ ( n )) تحقق أيضًا d ⋅ e ≡ 1 (mod λ ( n )) . مع ذلك، قد ينتج عن حساب d بتردد φ ( n ) أحيانًا نتيجة أكبر من اللازم (أي d > λ ( n ) ). تقبل معظم تطبيقات خوارزمية RSA الأسس المُولَّدة باستخدام أيٍّ من الطريقتين (إذا كانت تستخدم الأس الخاص d ، بدلاً من استخدام طريقة فك التشفير المُحسَّنة القائمة على نظرية الباقي الصينية الموضحة أدناه)، ولكن قد تشترط بعض المعايير، مثل FIPS  186-4 (القسم B.3.1)، أن يكون d < λ ( n ) . ويمكن دائمًا اختزال أي أسس خاصة "كبيرة" لا تستوفي هذا المعيار بتردد λ ( n ) للحصول على أس مكافئ أصغر.

ملاحظة: قام مؤلفو ورقة RSA الأصلية بتوليد المفتاح عن طريق اختيار d ثم حساب e كمعكوس ضربي معياري لـ d modulo φ ( n ) ، بينما تقوم معظم التطبيقات الحالية لـ RSA، مثل تلك التي تتبع PKCS#1 ، بالعكس - أي اختيار e وحساب d منه. بما أن e يمكن أن يكون صغيرًا وثابتًا بأمان، بينما يجب اختيار d من فضاء كبير بما يكفي لمقاومة الهجوم، فإن النهج الحديث يمكن أن يقلل من تكلفة عملية المفتاح العام دون فقدان الأمان. ^{[ 3 ] [ 32 ]}

لنفترض أن بوب يريد إرسال رسائل سرية إلى أليس ، أو التحقق من صحة رسائلها. إذا قررا استخدام خوارزمية RSA، فيجب على بوب معرفة المفتاح العام لأليس لتشفير رسائله السرية أو التحقق من صحة رسائلها، ويجب على أليس استخدام مفتاحها الخاص لفك تشفير رسائل بوب السرية أو توقيع رسائلها.

لتمكين بوب من إرسال رسائله المشفرة أو التحقق من رسائلها المستقبلية، تُرسل أليس مفتاحها العام ( n , e ) إلى بوب عبر مسار موثوق، ولكنه ليس بالضرورة سريًا. أما مفتاح أليس الخاص ( d ) فلا يُوزع أبدًا.

بعد أن يحصل بوب على المفتاح العام لأليس، يمكنه إرسال رسالة M إلى أليس.

للقيام بذلك، يقوم أولاً بتحويل M إلى عدد صحيح m ، وهو النص الأصلي المُضاف إليه الحشو ، بحيث يكون 0 ≤ m < n ، وذلك باستخدام بروتوكول عكسي متفق عليه يُعرف باسم مخطط الحشو . ثم يحسب النص المشفر c ، باستخدام المفتاح العام e الخاص بأليس ، كما يلي:

$${\displaystyle c\equiv m^{e}{\pmod {n}}.}$$

يمكن إنجاز ذلك بسرعة معقولة، حتى للأعداد الكبيرة جدًا، باستخدام الأسس المعيارية . ثم يرسل بوب قيمة c إلى أليس. لاحظ أن تسع قيم على الأقل لـ m ستُنتج نصًا مشفرًا c يساوي m ، ^{[ b ]،} ولكن من غير المرجح حدوث ذلك عمليًا.

تستطيع أليس استعادة m من c باستخدام مفتاحها الخاص، الأس d، عن طريق الحساب.

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

بفرض m ، يمكنها استعادة الرسالة الأصلية M عن طريق عكس مخطط الحشو، أو تجاهلها باعتبارها تالفة إذا كان الحشو غير صالح.

يجب على أليس تجاهل الرسالة m إذا كانت الحشوة غير صالحة: فإذا كشفت عن أي معلومات حول m عندما تكون الحشوة غير صالحة، يمكن للمهاجم استغلال ذلك لفك تشفير (أو توقيع) الرسائل دون معرفة المفتاح الخاص، وذلك عن طريق إرسال نصوص مشفرة عشوائية أو مصممة بشكل خبيث إليها ومراقبة كيفية استجابتها. ^{[ 33 ]}

فيما يلي مثال على تشفير وفك تشفير RSA، مع تجاهل تفاصيل الحشو: ^{[ ج ]}

1. اختر عددين أوليين مختلفين، مثل

   ${\displaystyle p=61}$و${\displaystyle q=53}$.

2. احسب n = pq، مما يعطي

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

3. احسب دالة كارمايكل للضرب على النحو التالي: λ ( n ) = lcm ( p - 1, q - 1) مما يعطي

   ${\displaystyle \lambda (3233)=\operatorname {lcm} (60,52)=780.}$

4. اختر أي عدد 1 < e < 780 يكون أوليًا نسبيًا مع 780. باختيار عدد أولي لـ e ، يبقى علينا فقط التحقق من أن e ليس قاسمًا لـ 780.

   يترك${\displaystyle e=17}$.

5. احسب d ، وهو المعكوس الضربي المعياري لـ e (mod λ ( n )) ، مما ينتج عنه$${\displaystyle d=413,}$$مثل${\displaystyle 1=(17\times 413){\bmod {7}}80.}$

المفتاح العام هو ( n = 3233، e = 17) . بالنسبة لرسالة نصية عادية مُبطّنة m ، تكون دالة التشفير هي $${\displaystyle {\begin{aligned}c(m)&=m^{e}{\bmod {n}}\\&=m^{17}{\bmod {3}}233.\end{aligned}}}$$

المفتاح الخاص هو ( n = 3233، d = 413) . بالنسبة للنص المشفر c ، فإن دالة فك التشفير هي $${\displaystyle {\begin{aligned}m(c)&=c^{d}{\bmod {n}}\\&=c^{413}{\bmod {3}}233.\end{aligned}}}$$

على سبيل المثال، لتشفير m = 65 ، يتم حساب $${\displaystyle c=65^{17}{\bmod {3}}233=2790.}$$

لفك تشفير c = 2790 ، يتم حساب $${\displaystyle m=2790^{413}{\bmod {3}}233=65.}$$

يمكن إجراء كلا الحسابين بكفاءة باستخدام خوارزمية التربيع والضرب للأس المعياري . في الواقع، ستكون الأعداد الأولية المختارة أكبر بكثير؛ في مثالنا، سيكون من السهل تحليل العدد n = 3233 (المستخرج من المفتاح العام المتاح مجانًا) إلى العددين الأوليين p و q . ثم يُقلب العدد e ، المستخرج أيضًا من المفتاح العام، للحصول على d ، ومن ثم الحصول على المفتاح الخاص.

تستخدم التطبيقات العملية نظرية الباقي الصينية لتسريع الحساب باستخدام معيار العوامل (mod pq باستخدام mod p و mod q ).

يتم حساب القيم d _p و d _q و q _inv ، التي تشكل جزءًا من المفتاح الخاص، على النحو التالي: $${\displaystyle {\begin{aligned}d_{p}&=d{\bmod {(}}p-1)=413{\bmod {(}}61-1)=53,\\d_{q}&=d{\bmod {(}}q-1)=413{\bmod {(}}53-1)=49,\\q_{\text{inv}}&=q^{-1}{\bmod {p}}=53^{-1}{\bmod {6}}1=38\\&\Rightarrow (q_{\text{inv}}\times q){\bmod {p}}=38\times 53{\bmod {6}}1=1.\end{aligned}}}$$

إليك كيفية استخدام d _p و d _q و q _inv لفك التشفير بكفاءة (يكون التشفير فعالاً باختيار زوج مناسب من d و e ): $${\displaystyle {\begin{aligned}m_{1}&=c^{d_{p}}{\bmod {p}}=2790^{53}{\bmod {6}}1=4,\\m_{2}&=c^{d_{q}}{\bmod {q}}=2790^{49}{\bmod {5}}3=12,\\h&=(q_{\text{inv}}\times (m_{1}-m_{2})){\bmod {p}}=(38\times -8){\bmod {6}}1=1,\\m&=m_{2}+h\times q=12+1\times 53=65.\end{aligned}}}$$

لنفترض أن أليس ترغب في إرسال رسالة موقعة m إلى بوب. تقوم بإنشاء قيمة تجزئة h = hash( m ) للرسالة m ، وترفعها إلى قوة d (modulo n )، وترفق s = h ^d mod n كـ "توقيع" للرسالة.

عندما يتلقى بوب الرسالة m والتوقيع s ، فإنه يستخدم نفس خوارزمية التجزئة بالاقتران مع المفتاح العام لأليس لحساب h = hash( m ) . ثم يرفع التوقيع s إلى قوة e (باقي القسمة على n )، ويقارن قيمة التجزئة الناتجة بقيمة تجزئة الرسالة.$${\displaystyle s^{e}\mathrel {\stackrel {?}{\equiv }} h{\pmod {n}}}$$إذا اتفق الاثنان، فإنه يعلم أن كاتب الرسالة كان يمتلك المفتاح الخاص بأليس وأن الرسالة لم يتم التلاعب بها منذ إرسالها.

تتحقق هذه المعادلة عندما يكون s = h ^d mod n بسبب قواعد الأس : $${\displaystyle s^{e}=(h^{d})^{e}=h^{de}=h^{ed}=(h^{e})^{d}\equiv h{\pmod {n}}.}$$

تعتمد عملية الأسس المعيارية للتوقيع والتحقق على نفس الرياضيات الأساسية المستخدمة في فك التشفير والتشفير، ولكن جميع التفاصيل الأخرى المتعلقة بنظام الحشو لتشفير المفتاح العام الآمن والتجزئة للتوقيع الرقمي الآمن تختلف. ^{[ 32 ]}

إن استخدام التجزئة، الذي اقترحه مايكل أو. رابين لأول مرة في عام 1978 في خوارزمية توقيع رابين ذات الصلة ، ^{[ 34 ] [ 35 ]} وأمن التجزئة، أمر ضروري لأمن التوقيع: ^{[ 36 ] [ 37 ]} إذا تخطيت أليس وبوب التجزئة، وقام بوب بالتحقق من s ^e ≡ m (mod n ) بدلاً من ذلك ، _{فإنه يمكن} لأي شخص تزوير التوقيع s = 1 على الرسالة m = 1 ، أو أخذ رسالتين موقعتين ( m1 , s1 ) و ( m2 , _{s2 ) من} أليس ثم تزوير رسالة ثالثة عن طريق الضرب، ( m1 _m2 , s1 _{s2 )} ، دون معرفة المفتاح الخاص.

يستند برهان صحة RSA إلى نظرية فيرما الصغرى ، التي تنص على أن a ^{p − 1} ≡ 1 (mod p ) لأي عدد صحيح a وعدد أولي p ، لا يقسم a . ^{[ ملاحظة 1 ]}

نريد أن نوضح ذلك $${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}}$$ لكل عدد صحيح m عندما يكون p و q عددين أوليين مختلفين و e و d عددين صحيحين موجبين يحققان ed ≡ 1 (mod λ ( pq )) .

بما أن λ ( pq ) = lcm ( p - 1, q - 1) يقبل القسمة على كل من p - 1 و q - 1 بحسب التعريف ، يمكننا كتابة $${\displaystyle ed-1=h(p-1)=k(q-1)}$$ لبعض الأعداد الصحيحة غير السالبة h و k . ^{[ ملاحظة 2 ]}

للتحقق مما إذا كان عددان، مثل m ^ed و m ، متطابقين بتردد pq  ، يكفي (وهو في الواقع متكافئ) التحقق من تطابقهما بتردد p  وتردد q بشكل  منفصل. ^{[ ملاحظة 3 ]}

لإثبات أن m ^ed ≡ m (mod p ) ، نأخذ في الاعتبار حالتين:

1. إذا كان m ≡ 0 (mod p ) ، فإن m مضاعف لـ p . وبالتالي فإن m ^ed مضاعف لـ p . إذن m ^ed ≡ 0 ≡ m (mod p ) .
2. إذا كان m ≢ 0 (mod p ) ،

   ${\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}},}$

   حيث استخدمنا نظرية فيرما الصغرى لاستبدال m ^{p −1} mod p بـ 1.

يتم التحقق من أن m ^ed ≡ m (mod q ) بطريقة مماثلة تمامًا:

1. إذا كان m ≡ 0 (mod q ) ، فإن m ^ed هو مضاعف لـ q . لذا فإن m ^ed ≡ 0 ≡ m (mod q ) .
2. إذا كان m ≢ 0 (mod q ) ،

   ${\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 بحيث يكون ed ≡ 1 (mod λ ( pq )) ، $${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}.}$$

على الرغم من أن الورقة الأصلية لريفست وشامير وأدلمان استخدمت نظرية فيرما الصغيرة لشرح سبب نجاح RSA، إلا أنه من الشائع العثور على براهين تعتمد بدلاً من ذلك على نظرية أويلر .

نريد أن نُثبت أن ed ≡ ^m (mod n ) ، حيث n = pq هو حاصل ضرب عددين أوليين مختلفين، و e و d عددان صحيحان موجبان يحققان ed ≡ 1 (mod φ ( n )) . بما أن e و d موجبان، يمكننا كتابة ed = 1 + h φ ( n ) لعدد صحيح غير سالب h . بافتراض أن m أولي نسبيًا مع n ، لدينا $${\displaystyle m^{ed}=m^{1+h\varphi (n)}=m(m^{\varphi (n)})^{h}\equiv m(1)^{h}\equiv m{\pmod {n}},}$$

حيث يتبع التطابق قبل الأخير من نظرية أويلر .

وبشكل أكثر عمومية، بالنسبة لأي e و d يحقق ed ≡ 1 (mod λ ( n )) ، فإن نفس النتيجة تتبع من تعميم كارمايكل لنظرية أويلر ، والتي تنص على أن m ^{λ (n)} ≡ 1 (mod n ) لجميع m أولية نسبياً مع n .

عندما لا يكون m أوليًا نسبيًا مع n ، فإن الحجة المذكورة آنفًا غير صالحة. هذا أمرٌ مستبعدٌ للغاية (نسبةٌ فقط من الأعداد التي تحقق هذا الشرط هي 1/ p + 1/ q − 1/( pq )) ، ولكن حتى في هذه الحالة، يظل التطابق المطلوب صحيحًا. إما أن يكون m ≡ 0 (mod p ) أو m ≡ 0 (mod q ) ، ويمكن معالجة هاتين الحالتين باستخدام البرهان السابق.

هناك عدد من الهجمات ضد RSA العادي كما هو موضح أدناه.

• عند التشفير باستخدام أسس تشفير منخفضة (مثل e = 3 ) وقيم صغيرة لـ m (أي m < n ^{1/ e} )، تكون نتيجة m ^e أقل من المعامل n . في هذه الحالة، يمكن فك تشفير النصوص المشفرة بسهولة عن طريق حساب الجذر النوني للنص المشفر على الأعداد الصحيحة.
• إذا أُرسلت نفس الرسالة النصية الواضحة إلى e أو أكثر بطريقة مشفرة، وكان للمستلمين نفس الأس e ، ولكن قيم p و q و n مختلفة ، فمن السهل فك تشفير الرسالة النصية الواضحة الأصلية باستخدام نظرية الباقي الصينية . لاحظ يوهان هاستاد أن هذا الهجوم ممكن حتى لو لم تكن النصوص الواضحة متساوية، ولكن المهاجم يعرف علاقة خطية بينها. ^{[ 38 ]} وقد حسّن دون كوبرسميث هذا الهجوم لاحقًا (انظر هجوم كوبرسميث ). ^{[ 39 ]}
• نظرًا لأن تشفير RSA خوارزمية تشفير حتمية (أي لا تحتوي على عنصر عشوائي)، يمكن للمهاجم شن هجوم نص عادي مُختار بنجاح ضد نظام التشفير، وذلك بتشفير نصوص عادية محتملة باستخدام المفتاح العام واختبار ما إذا كانت تُطابق النص المُشفّر. يُوصف نظام التشفير بأنه آمن دلاليًا إذا لم يتمكن المهاجم من التمييز بين تشفيرين، حتى لو كان المهاجم على دراية بالنصوص العادية المُقابلة (أو اختارها بنفسه). لا يُعد تشفير RSA بدون حشو آمنًا دلاليًا. ^{[ 40 ]}
• _{تتميز خوارزمية} RSA بخاصية أن حاصل ضرب نصين مشفرين يساوي تشفير حاصل ضرب النصين الأصليين. أي أن m₁e ₌ ^{m₂e ≡} ( m₁m₂ ) ^e (mod n ) . وبسبب هذه الخاصية الضربية، _يصبح هجوم النص المشفر المختار ممكنًا. على سبيل المثال، قد يطلب مهاجم يريد معرفة فك تشفير نص مشفر c ≡ m ^e (mod n ) من حامل المفتاح الخاص d فك تشفير نص مشفر يبدو غير مثير للريبة c ′ ≡ cr ^e (mod n ) لقيمة r يختارها المهاجم. وبسبب الخاصية الضربية، فإن c ′ هو تشفير mr (mod n ) . وبالتالي، إذا نجح المهاجم في هجومه، فسيعرف mr (mod n )، ومن ثم يمكنه استنتاج الرسالة m بضرب mr في المعكوس المعياري لـ r modulo n . ^{[ 33 ] [ 41 ]}
• بمعرفة الأس الخاص d ، يمكن تحليل المعامل n = pq بكفاءة . وبمعرفة تحليل المعامل n = pq ، يمكن الحصول على أي مفتاح خاص ( d ', n ) مُولّد باستخدام مفتاح عام ( e ', n ). ^{[ 30 ]}  

لتجنب هذه المشاكل، عادةً ما تُضمّن تطبيقات RSA العملية نوعًا من الحشو المُهيكل والعشوائي في القيمة m قبل تشفيرها. يضمن هذا الحشو ألا تقع m ضمن نطاق النصوص غير الآمنة، وأن الرسالة المُعطاة، بعد إضافة الحشو إليها، ستُشفّر إلى واحد من عدد كبير من النصوص المُشفّرة المُحتملة.

صُممت معايير مثل PKCS#1 بعناية فائقة لتأمين حشو الرسائل قبل تشفيرها باستخدام خوارزمية RSA. ولأن هذه الأنظمة تُضيف عددًا من البتات الإضافية إلى النص الأصلي m ، يجب أن يكون حجم الرسالة M غير المُحشوة أصغر نسبيًا. يجب تصميم أنظمة حشو RSA بعناية لمنع الهجمات المعقدة التي قد تُسهّلها بنية الرسالة المتوقعة. استخدمت الإصدارات الأولى من معيار PKCS#1 (حتى الإصدار 1.5) بنيةً تبدو ظاهريًا أنها تجعل RSA آمنًا دلاليًا. مع ذلك، في مؤتمر Crypto 1998، أظهر بليشنباخر أن هذا الإصدار عُرضة لهجوم عملي مُتكيف على النص المشفر المُختار . علاوة على ذلك، في مؤتمر Eurocrypt 2000، أظهر كورون وآخرون ^{[ 42 ]} أن هذا الحشو لا يُوفر مستوى أمان كافيًا لبعض أنواع الرسائل. تتضمن الإصدارات اللاحقة من المعيار حشو التشفير غير المتماثل الأمثل (OAEP)، الذي يمنع هذه الهجمات. لذا، ينبغي استخدام بروتوكول OAEP في أي تطبيق جديد،  واستبدال حشو PKCS#1 v1.5 كلما أمكن ذلك. كما يتضمن معيار PKCS#1 أنظمة معالجة مصممة لتوفير أمان إضافي لتوقيعات RSA، مثل نظام التوقيع الاحتمالي لـ RSA ( RSA-PSS ).

تُعدّ أنظمة الحشو الآمنة، مثل RSA-PSS، ضرورية لأمن توقيع الرسائل تمامًا كما هي ضرورية لتشفيرها. مُنحت براءتا اختراع أمريكيتان لتقنية PSS ( براءة الاختراع الأمريكية رقم 6,266,771 وبراءة الاختراع الأمريكية رقم 7,036,014 )، إلا أن صلاحيتهما انتهت في 24 يوليو 2009 و25 أبريل 2010 على التوالي. ويبدو أن استخدام PSS لم يعد مقيدًا ببراءات الاختراع. تجدر الإشارة إلى أن استخدام أزواج مفاتيح RSA مختلفة للتشفير والتوقيع قد يكون أكثر أمانًا. ^{[ 43 ]}

لتحقيق الكفاءة، تستخدم العديد من مكتبات التشفير الشائعة (مثل OpenSSL و Java و .NET ) التحسين التالي لفك التشفير والتوقيع، استنادًا إلى نظرية الباقي الصينية . ^{[ 44 ]} يتم حساب القيم التالية مسبقًا وتخزينها كجزء من المفتاح الخاص:

• ${\displaystyle p}$و${\displaystyle q}$ – الأعداد الأولية من الجيل الرئيسي،
• ${\displaystyle d_{P}=d{\pmod {p-1}},}$
• ${\displaystyle d_{Q}=d{\pmod {q-1}},}$
• ${\displaystyle q_{\text{inv}}=q^{-1}{\pmod {p}}.}$

تسمح هذه القيم للمستلم بحساب الأس m = c ^d (mod pq ) بكفاءة أكبر على النحو التالي:   ${\displaystyle m_{1}=c^{d_{P}}{\pmod {p}}}$،   ${\displaystyle m_{2}=c^{d_{Q}}{\pmod {q}}}$،   ${\displaystyle h=q_{\text{inv}}(m_{1}-m_{2}){\pmod {p}}}$، ^{[ د ]}  ${\displaystyle m=m_{2}+hq}$.

هذه الطريقة أكثر كفاءة من حساب الأس بالتربيع ، على الرغم من ضرورة حساب عمليتي أس معياريتين. والسبب هو أن هاتين العمليتين تستخدمان أسًا أصغر وقيمة مطلقة أصغر.

يعتمد أمان نظام تشفير RSA على مسألتين رياضيتين: مسألة تحليل الأعداد الكبيرة إلى عواملها الأولية، ومسألة RSA نفسها. يُعتقد أن فك تشفير نص RSA بالكامل غير ممكن عمليًا، بافتراض أن كلتا المسألتين صعبتان ، أي أنه لا توجد خوارزمية فعالة لحلهما. قد يتطلب توفير الحماية ضد فك التشفير الجزئي إضافة نظام حشو آمن . ^{[ 45 ]}

تُعرَّف مشكلة RSA بأنها مهمة إيجاد الجذر e للعدد المركب n بتردده : استعادة قيمة m بحيث يكون c ≡ m ^e (mod n ) ، حيث ( n , e ) هو المفتاح العام لـ RSA، و c هو النص المشفر لـ RSA. حاليًا، يُعدّ تحليل العدد n إلى عوامله الأولية النهج الأكثر فعالية لحل مشكلة RSA . فبفضل القدرة على استعادة العوامل الأولية، يستطيع المهاجم حساب الأس السري d من المفتاح العام ( n , e ) ، ثم فك تشفير c باستخدام الإجراء القياسي. ولتحقيق ذلك، يُحلل المهاجم n إلى p و q ، ويحسب المضاعف المشترك الأصغر (lcm( p − 1, q − 1)) الذي يسمح بتحديد d من e . لم يتم التوصل بعد إلى طريقة ذات زمن متعدد الحدود لتحليل الأعداد الصحيحة الكبيرة على حاسوب تقليدي، ولكن لم يُثبت عدم وجودها؛ انظر تحليل الأعداد الصحيحة إلى عواملها الأولية لمناقشة هذه المشكلة.

استُخدمت مئات الحواسيب في أول عملية تحليل لمفتاح RSA-512 عام 1999، واستغرقت ما يعادل 8400 مليون سنة حسابية في الثانية، على مدى سبعة أشهر تقريبًا. ^{[ 46 ]} وبحلول عام 2009، تمكن بنجامين مودي من تحليل مفتاح RSA بطول 512 بت في 73 يومًا فقط باستخدام برنامج عام (GGNFS) وحاسوبه المكتبي ( معالج Athlon64 ثنائي النواة بتردد 1900  ميجاهرتز). تطلّب الأمر أقل من 5  جيجابايت من مساحة التخزين على القرص، وحوالي 2.5  جيجابايت من ذاكرة الوصول العشوائي (RAM) لعملية الفرز.

أشار ريفست وشامير وأدلمان ^{[ 3 ]} إلى أن ميلر قد أثبت أنه - بافتراض صحة فرضية ريمان الموسعة - فإن إيجاد قيمة d من n و e لا يقل صعوبة عن تحليل n إلى p و q (مع مراعاة فرق زمني متعدد الحدود). ^{[ 47 ]} ومع ذلك، أشار ريفست وشامير وأدلمان، في القسم التاسع/د من بحثهم، إلى أنهم لم يجدوا برهانًا على أن عكس RSA لا يقل صعوبة عن التحليل إلى عوامل.

اعتبارًا من عام 2020كان أكبر عدد RSA معروف علنًا، بعد تحليله إلى عوامله الأولية، يتكون من 829  بت (250 رقمًا عشريًا، RSA-250 ). ^{[ 48 ]} استغرق تحليله، باستخدام أحدث تقنيات الحوسبة الموزعة، حوالي 2700 سنة معالجة. عمليًا، يتراوح طول مفاتيح RSA عادةً بين 1024 و4096 بت. في عام 2003، قدّرت شركة RSA Security أن مفاتيح 1024 بت ستصبح قابلة للاختراق بحلول عام 2010. ^{[ 49 ]} حتى عام 2020، لم يُعرف بعد ما إذا كان من الممكن اختراق هذه المفاتيح، ولكن التوصيات الدنيا ارتفعت إلى 2048 بت على الأقل  . ^{[ 50 ]} يُفترض عمومًا أن RSA آمن إذا كان n كبيرًا بما يكفي، خارج نطاق الحوسبة الكمومية.

إذا كان طول n يساوي 300 بت أو أقل، فيمكن تحليله إلى عوامله الأولية في غضون ساعات قليلة على جهاز كمبيوتر شخصي ، باستخدام برامج متاحة مجانًا. وقد ثبت عمليًا إمكانية اختراق مفاتيح 512 بت في عام 1999، عندما تم تحليل RSA-155 باستخدام مئات أجهزة الكمبيوتر، ويتم الآن تحليلها في غضون أسابيع قليلة باستخدام أجهزة شائعة. وتم الإبلاغ عن ثغرات أمنية تستغل شهادات توقيع التعليمات البرمجية 512 بت، والتي ربما تم تحليلها، في عام 2011. ^{[ 51 ]} وقد شكك جهاز نظري يُدعى TWIRL ، وصفه شامير وترومر في عام 2003، في أمان مفاتيح 1024 بت. ^{[ 49 ]}  

في عام 1994، أظهر بيتر شور أن الكمبيوتر الكمومي - إذا أمكن إنشاء واحد عمليًا لهذا الغرض - سيكون قادرًا على تحليل الوقت متعدد الحدود ، مما يؤدي إلى كسر RSA؛ انظر خوارزمية شور .

عادة ما يتم إيجاد الأعداد الأولية الكبيرة p و q عن طريق اختبار الأرقام العشوائية ذات الحجم الصحيح باستخدام اختبارات أولية احتمالية تعمل على إزالة جميع الأعداد غير الأولية تقريبًا بسرعة.

يجب ألا يكون العددان p و q متقاربين جدًا، وإلا سيفشل تحليل فيرما للعدد n . إذا كان p − q أقل من 2n 1/4 (حيث n = p ⋅ q) ، وهو ما ^ينطبق حتى على قيم n "الصغيرة" ذات 1024 بت(3 × 10⁷⁷ )، ^لذا فإن إيجاد قيمتي p و q أمرٌ بسيط. علاوة على ذلك، إذا كان للعدد p − 1 أو q − 1 عوامل أولية صغيرة فقط، فيمكن تحليل n بسرعة باستخدام خوارزمية بولارد p − 1 ، وبالتالي يجب استبعاد هذه القيم لـ p أو q .

من المهم أن يكون الأس الخاص d كبيرًا بما يكفي. وقد أظهر مايكل ج. وينر أنه إذا كانت قيمة p بين q و 2q (وهو أمر شائع جدًا) و d < n ^1/4 /3 ، فإنه يمكن حساب d بكفاءة من n و e . ^{[ 52 ]} 

لا توجد هجمات معروفة ضد الأسس العامة الصغيرة مثل e = 3 ، شريطة استخدام الحشو المناسب. لهجوم كوبرسميث تطبيقات عديدة في مهاجمة خوارزمية RSA، خاصةً إذا كان الأس العام e صغيرًا وكانت الرسالة المشفرة قصيرة وغير محشوة. 65537 قيمة شائعة الاستخدام لـ e ؛ ويمكن اعتبار هذه القيمة حلاً وسطًا بين تجنب هجمات الأسس الصغيرة المحتملة والسماح في الوقت نفسه بعمليات تشفير فعالة (أو التحقق من التوقيع). لا يسمح منشور المعهد الوطني للمعايير والتكنولوجيا (NIST) الخاص بأمن الحاسوب (SP 800-78 Rev. 1، أغسطس 2007) باستخدام أسس عامة e أصغر من 65537، ولكنه لا يذكر سببًا لهذا التقييد.   

في أكتوبر 2017، أعلن فريق من الباحثين من جامعة ماساريك عن ثغرة أمنية تُعرف باسم ROCA ، والتي تؤثر على مفاتيح RSA المُولّدة بواسطة خوارزمية مُدمجة في مكتبة من شركة إنفينون تُعرف باسم RSALib. وقد تبيّن أن عددًا كبيرًا من البطاقات الذكية ووحدات النظام الأساسي الموثوقة (TPM) مُتأثرة بهذه الثغرة. ويمكن تحديد مفاتيح RSA المُعرّضة للخطر بسهولة باستخدام برنامج اختبار أصدره الفريق. ^{[ 53 ]}

يجب استخدام مولد أرقام عشوائية قوي تشفيرياً ، مُهيأ بشكل صحيح بكمية كافية من الإنتروبيا، لتوليد العددين الأوليين p و q . أُجري تحليلٌ لمقارنة ملايين المفاتيح العامة التي جُمعت من الإنترنت في أوائل عام 2012 من قِبل أرجين ك.  لينسترا ، وجيمس ب.  هيوز، وماكسيم أوجييه، وجوب و.  بوس، وثورستن كلاينجونج، وكريستوف واشتر. وقد تمكنوا من تحليل 0.2% من المفاتيح باستخدام خوارزمية إقليدس فقط. ^{[ 54 ] [ 55 ]}

استغلوا ثغرةً فريدةً في أنظمة التشفير القائمة على تحليل الأعداد الصحيحة إلى عواملها الأولية. إذا كان n = pq مفتاحًا عامًا، و n ′ = p′q ′ مفتاحًا عامًا آخر، فإذا صادف أن p = p ′ (ولكن q لا يساوي q ′)، فإن حساب القاسم المشترك الأكبر لـ n و n ′ = p يُحلل كلاً من n و n ′ إلى عواملهما الأولية، مما يُعرّض كلا المفتاحين للخطر. ويشير لينسترا وزملاؤه إلى إمكانية تقليل هذه المشكلة باستخدام بذرة عشوائية قوية بطول بتات يساوي ضعف مستوى الأمان المطلوب، أو باستخدام دالة حتمية لاختيار q بمعلومية p ، بدلاً من اختيار p و q بشكل مستقل.

كانت ناديا هينينجر جزءًا من مجموعة أجرت تجربة مماثلة. استخدموا فكرة دانيال ج. بيرنشتاين لحساب القاسم المشترك الأكبر لكل مفتاح RSA n مقابل حاصل ضرب جميع المفاتيح الأخرى n ' التي عثروا عليها (عدد مكون من 729 مليون رقم)، بدلاً من حساب كل قاسم مشترك أكبر ( n , n ') على حدة، مما حقق تسريعًا كبيرًا جدًا، لأنه بعد عملية قسمة واحدة كبيرة، تصبح مشكلة القاسم المشترك الأكبر ذات حجم طبيعي.

تقول هينينجر في مدونتها إن المفاتيح المعيبة ظهرت بشكل شبه كامل في التطبيقات المدمجة، بما في ذلك "جدران الحماية، وأجهزة التوجيه، وأجهزة الشبكات الافتراضية الخاصة (VPN)، وأجهزة إدارة الخوادم عن بُعد، والطابعات، وأجهزة العرض، وهواتف بروتوكول نقل الصوت عبر الإنترنت (VoIP)" من أكثر من 30 شركة مصنعة. وتوضح هينينجر أن مشكلة العدد الأولي المشترك التي كشفت عنها المجموعتان ناتجة عن حالات يكون فيها مولد الأرقام العشوائية الزائفة ضعيف التهيئة في البداية، ثم يُعاد تهيئته بين توليد العددين الأوليين الأول والثاني. ومن المفترض أن يحل استخدام بذور ذات إنتروبيا عالية كافية، يتم الحصول عليها من توقيتات ضغطات المفاتيح أو ضوضاء الصمام الثنائي الإلكتروني أو الضوضاء الجوية من جهاز استقبال لاسلكي مضبوط بين المحطات، هذه المشكلة. ^{[ 56 ]}

يُعدّ توليد أرقام عشوائية قوية أمرًا بالغ الأهمية في جميع مراحل التشفير بالمفتاح العام. فعلى سبيل المثال، إذا استُخدم مولد أرقام عشوائية ضعيف للمفاتيح المتناظرة التي يوزعها نظام RSA، فسيتمكن المتنصت من تجاوز نظام RSA وتخمين المفاتيح المتناظرة مباشرةً.

وصف كوخر هجومًا جديدًا على خوارزمية RSA عام 1995: إذا كان المهاجم إيف على دراية كافية بمواصفات جهاز أليس، وقادرًا على قياس أوقات فك التشفير لعدة نصوص مشفرة معروفة، فإنه يستطيع استنتاج مفتاح فك التشفير d بسرعة. يمكن تطبيق هذا الهجوم أيضًا على نظام توقيع RSA. في عام 2003، عرض بونيه وبروملي هجومًا أكثر عملية قادرًا على استعادة تحليلات RSA عبر اتصال شبكي (مثلًا، من خادم ويب مُفعّل بتقنية طبقة المقابس الآمنة ( SSL)). ^{[ 57 ]} يستغل هذا الهجوم المعلومات المُسرّبة من خلال تحسين نظرية الباقي الصينية المستخدمة في العديد من تطبيقات RSA.

إحدى طرق إحباط هذه الهجمات هي ضمان أن تستغرق عملية فك التشفير وقتًا ثابتًا لكل نص مشفر. مع ذلك، قد يؤدي هذا الأسلوب إلى انخفاض الأداء بشكل ملحوظ. لذا، تستخدم معظم تطبيقات RSA تقنية بديلة تُعرف باسم " التعمية التشفيرية" . تستفيد التعمية في RSA من خاصية الضرب في RSA. فبدلًا من حساب c ^d (mod n ) ، تختار أليس أولًا قيمة عشوائية سرية r، ثم تحسب ( r ^e c ) ^d (mod n ) . نتيجة هذا الحساب، بعد تطبيق نظرية أويلر ، هي rc ^d (mod n ) ، وبالتالي يمكن إزالة تأثير r بضربها في معكوسها. تُختار قيمة جديدة لـ r لكل نص مشفر. مع تطبيق التعمية، لا يعود وقت فك التشفير مرتبطًا بقيمة النص المشفر المُدخل، وبالتالي تفشل هجمة التوقيت.

في عام ١٩٩٨، وصف دانيال بليشنباخر أول هجوم عملي مُتكيف على الرسائل المُشفرة باستخدام خوارزمية RSA، وذلك باستخدام نظام حشو  PKCS #1  v1 (وهو نظام حشو يُضفي عشوائية وبنية على الرسالة المُشفرة باستخدام RSA، مما يُتيح تحديد ما إذا كانت الرسالة المُفككة صالحة). ونظرًا لوجود ثغرات في نظام PKCS #1، تمكن بليشنباخر من شن هجوم عملي على تطبيقات RSA لبروتوكول طبقة المقابس الآمنة (SSL) واستعادة مفاتيح الجلسة. ونتيجةً لهذا العمل، يُوصي خبراء التشفير الآن باستخدام أنظمة حشو آمنة بشكل مُثبت، مثل حشو التشفير غير المتماثل الأمثل (OPT) ، وقد أصدرت مختبرات RSA إصدارات جديدة من PKCS #1 غير قابلة للاختراق بهذه الهجمات.  

وقد ظهر نوع مختلف من هذا الهجوم، أطلق عليه اسم "BERserk"، في عام 2014. ^{[ 58 ] [ 59 ]} وقد أثر على مكتبة Mozilla NSS Crypto، والتي تم استخدامها بشكل ملحوظ بواسطة Firefox وChrome.

تم وصف هجوم القناة الجانبية باستخدام تحليل التنبؤ بالتفرع (BPA). تستخدم العديد من المعالجات مُتنبئًا بالتفرع لتحديد ما إذا كان من المحتمل تنفيذ تفرع شرطي في مسار تعليمات البرنامج أم لا. غالبًا ما تُنفذ هذه المعالجات أيضًا تقنية تعدد الخيوط المتزامنة (SMT). تستخدم هجمات تحليل التنبؤ بالتفرع عملية تجسس لاكتشاف المفتاح الخاص (إحصائيًا) عند معالجتها بواسطة هذه المعالجات.

يدّعي تحليل التنبؤ البسيط للفروع (SBPA) تحسين تحليل التنبؤ بالفروع (BPA) بطريقة غير إحصائية. في ورقتهم البحثية بعنوان "حول قوة تحليل التنبؤ البسيط للفروع" ^{[ 60 ]} ، يدّعي مؤلفا SBPA (أونور أتشيكمز وجتين كايا كوتش) اكتشاف 508 بت من أصل 512  بت من مفتاح RSA في 10 تكرارات.

تم وصف هجوم انقطاع الطاقة على تطبيقات RSA في عام 2010. ^{[ 61 ]} استعاد المؤلف المفتاح عن طريق تغيير جهد طاقة وحدة المعالجة المركزية خارج الحدود؛ تسبب هذا في حدوث أعطال طاقة متعددة على الخادم.

يُعدّ تطبيق CRT حساسًا لهجمات حقن الأخطاء . فإذا تمكّن المهاجم من الحصول على توقيع خاطئ واحد، يُمكنه حساب المفتاح الخاص. ^{[ 62 ]}

هناك العديد من التفاصيل التي يجب مراعاتها لتطبيق خوارزمية RSA بشكل آمن ( مولد أرقام عشوائية زائفة قوي ، ومعامل عام مقبول، إلخ). وهذا ما يجعل تطبيقها صعبًا، لدرجة أن كتاب "التشفير العملي باستخدام لغة Go" يقترح تجنب استخدام RSA قدر الإمكان. ^{[ 63 ]}