> ## Content Index
> Fetch the complete content index at: https://arabroot.io/llms.txt
> Use this file to discover other available public pages before exploring further.

# رياضيات RSA: الأعداد الأولية Primes والحساب المعياري Modular
- URL: https://arabroot.io/articles/الرياضيات-خلف-rsa-الاعداد-الاولية-والحساب-المعياري/
- Published: 2026-10-30T12:54:32.000Z
- Updated: 2026-10-30T17:49:00.000Z
- Description: نبني مفتاح RSA بأيدينا من عددين أوليين صغيرين، ثم نقرأ مفتاح OpenSSL حقيقياً رقماً رقماً، لنفهم لماذا يعود النص بعد فك التشفير ولماذا لا يصلح RSA بدون حشو.
- Author: فريق عرب رووت
- Tags: الأدلة التقنية, أساسيات الحاسب والبرمجة

إذا قمت يوماً بتشغيل الأمر `openssl pkey -in key.pem -text -noout` على مفتاح RSA خاص بسيرفرك أو بشهادة TLS، فقد رأيت شاشة كاملة من الأرقام بالـ Hex تحت ثمانية أسماء: `modulus` و`publicExponent` وقيمته غالباً 65537، ثم `privateExponent` و`prime1` و`prime2` و`exponent1` و`exponent2` و`coefficient`. وأغلب المطورين يتعاملون مع هذا الملف كصندوق مغلق: ينشئونه ويحمونه ويضعون مساره في إعدادات ال Reverse Proxy ثم ينسونه، وهذا كاف في العمل اليومي، ولكنه لا يجيب عن أسئلة تظهر عاجلاً أو آجلاً: لماذا يقال إن RSA يعتمد على صعوبة تحليل الأعداد، وما علاقة هذا بالأرقام الثمانية؟ ولماذا 65537 تحديداً؟ ولماذا تقول كل مكتبة تشفير إن RSA بدون حشو Padding خطير، مع أن المعادلة نفسها لم تتغير؟ ولماذا وجد باحثون آلاف المفاتيح على الانترنت يمكن استخراج مفتاحها الخاص في أجزاء من الثانية؟

في مقال [التشفير للمطورين](https://arabroot.io/articles/%D8%A7%D9%84%D8%AA%D8%B4%D9%81%D9%8A%D8%B1-%D9%84%D9%84%D9%85%D8%B7%D9%88%D8%B1%D9%8A%D9%86-%D8%A7%D9%84%D9%87%D8%A7%D8%B4-%D9%88%D9%83%D9%84%D9%85%D8%A7%D8%AA-%D8%A7%D9%84%D9%85%D8%B1%D9%88%D8%B1-%D9%88%D8%A7%D9%84%D9%85%D9%81%D8%A7%D8%AA%D9%8A%D8%AD/) عرفنا متى نستخدم RSA ومتى نستخدم المنحنيات البيضاوية، وما أطوال المفاتيح المقبولة، وكيف ندير المفاتيح، وفي مقال [الشهادات الرقمية](https://arabroot.io/articles/%D8%A7%D9%84%D8%B4%D9%87%D8%A7%D8%AF%D8%A7%D8%AA-%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A%D8%A9-tls-%D9%88-x509-%D9%88%D8%B5%D9%8A%D8%BA-pem-%D9%88-der/) عرفنا صيغ الملفات PEM وDER وأين يوضع كل ملف. أما هذا المقال فينزل طبقة أخرى إلى الرياضيات نفسها، وهو من مرحلة [الرياضيات التي يحتاجها المبرمج فعلاً](https://arabroot.io/start/#stage-cs-math)، والهدف منه أن تفهم كل رقم في ملف المفتاح، وأن تحسب RSA بيدك على أرقام صغيرة ثم تتحقق من نفس المعادلات على مفتاح حقيقي أنشأه OpenSSL، وكل الأرقام في المقال خرجت من تجربة عملية تستطيع تشغيلها في Container واحد. وسوف نناقش في هذا المقال ما يلي:

- الأعداد الأولية Prime Numbers وكم يوجد منها قرب 21024، ولماذا يحتاج RSA إلى عددين منها.
- الحساب المعياري Modular Arithmetic بمثال الساعة ثم بأرقام حقيقية، والفرق بين `%` في Python وفي JavaScript.
- القاسم المشترك الأكبر GCD وخوارزمية إقليدس الموسعة Extended Euclidean Algorithm، والمعكوس المعياري Modular Inverse.
- مبرهنة فيرما الصغرى ودالة أويلر Euler's Totient، ولماذا يعيد فك التشفير الرسالة نفسها.
- RSA بيدك بالعددين 61 و53، ثم الأس السريع Square-and-Multiply وعدد خطواته الفعلي.
- كيف نجد عدداً أولياً من 1024 بت باختبار Miller-Rabin، ولماذا يخدعك اختبار فيرما.
- قراءة مفتاح OpenSSL حقيقي رقماً رقماً، والتحقق من كل معادلة عليه في Python، وتسريع فك التشفير بمبرهنة الباقي الصيني CRT.
- لماذا يصعب تحليل n، مع قياس زمن التحليل وهو يكبر.
- RSA المجرد Textbook RSA وثلاث هجمات عليه، ولماذا وجد الحشو OAEP وPSS، وما هو هجوم Bleichenbacher وROBOT.
- مفاتيح تبدو سليمة وتكشف أسرارها: عامل أولي مشترك بين مفتاحين، وعددان أوليان متقاربان.

## تجهيز التجربة العملية Lab

كل ما نحتاجه هو Python وأمر `openssl`، والـ Image الرسمية `python:3.13.17-slim` فيها الاثنان، فلا نحتاج إلى تثبيت أي شيء، والسبب في استخدام Container أن المفاتيح التي سوف ننشئها مفاتيح تجربة لا نريدها أن تبقى على جهازك، فهي تكتب في المجلد `/tmp/rsa` داخل ال Container وتختفي معه. احفظ الملفات التي سوف نعرضها في الأقسام القادمة في مجلد واحد، وهي `toy_rsa.py` و`primes.py` و`check_key.py` و`textbook.py` و`factor_time.py` و`weak_keys.py`، ومعها السكربت `run.sh` الذي يشغلها بالترتيب، والسكربت `tamper.sh` الذي نشغله وحده في قسم الحشو، ثم شغل التجربة كاملة بالأمر التالي من داخل المجلد:

```bash
docker run --rm --name scm-rsa-lab -v "$PWD:/lab:ro" -w /lab python:3.13.17-slim sh run.sh
```

والسطران الأولان من المخرج يبينان الإصدارات التي عملنا عليها:

```text
Python 3.13.17
OpenSSL 3.5.7 9 Jun 2026 (Library: OpenSSL 3.5.7 9 Jun 2026)
```

لاحظ أن المجلد مربوط للقراءة فقط `:ro`، لذلك لا يكتب ال Container أي ملف داخل مجلدك، والخيار `--rm` يحذفه بعد انتهاء التشغيل فلا يبقى منه شيء. وفي كل قسم سوف نعرض جزء المخرج الذي يخصه، ونشرح كل سطر فيه.

## ما الذي يحتاجه RSA من الرياضيات؟

فكرة التشفير بالمفتاح العام Public Key Cryptography أن يكون لديك قفل يستطيع أي شخص أن يغلقه، ومفتاح واحد فقط يفتحه، وبلغة الرياضيات نحتاج إلى دالة سهلة الحساب في اتجاه واحد، وصعبة جداً في الاتجاه المعاكس، إلا لمن يملك معلومة سرية صغيرة تسمى الباب الخلفي Trapdoor. وقد يتساءل البعض: هل توجد دالة بهذه الصفات أصلاً؟ والإجابة أن الضرب هو المرشح الطبيعي، فضرب عددين أوليين من 1024 بت يأخذ أجزاء من المللي ثانية، بينما لا يعرف أحد طريقة عملية لاستعادة العددين من حاصل الضرب إذا كانا كبيرين بما يكفي، كما سوف نقيس بأنفسنا في قسم التحليل.

ولكن الضرب وحده لا يعطي تشفيراً، فنحن نحتاج إلى عملية تحول الرسالة إلى رقم يبدو عشوائياً، ثم تعيده عملية أخرى إلى الرسالة الأصلية، وهنا يأتي دور الحساب المعياري، حيث يرفع RSA الرسالة إلى أس معين ثم يأخذ باقي القسمة على حاصل ضرب العددين الأوليين، ويرفع الناتج إلى أس آخر فيعود إلى الرسالة نفسها. وهذا ما نشره Rivest وShamir وAdleman في [ورقتهم الأصلية سنة 1978](https://people.csail.mit.edu/rivest/Rsapaper.pdf?ref=arabroot.io)، وكل ما في ملف المفتاح هو أرقام هذه المعادلة. ولكي نصل إليها نحتاج إلى خمس أدوات رياضية فقط، وكل قسم من الأقسام القادمة يضيف أداة واحدة منها: الأعداد الأولية، والحساب المعياري، وخوارزمية إقليدس، والمعكوس المعياري، ومبرهنة أويلر.

## الأعداد الأولية Prime Numbers: كم يوجد منها؟

العدد الأولي هو العدد الأكبر من 1 الذي لا يقبل القسمة إلا على 1 وعلى نفسه، مثل 2 و3 و5 و61 و53، وأهم حقيقة عنها في RSA هي المبرهنة الأساسية في الحساب Fundamental Theorem of Arithmetic، والتي تقول إن كل عدد صحيح أكبر من 1 يكتب بطريقة واحدة فقط كحاصل ضرب أعداد أولية، فالعدد 3233 مثلاً يساوي 61 × 53 ولا يوجد تحليل آخر له. وهذا يعني أن من يملك n يملك نظرياً كل المعلومات عن p وq، والحماية كلها تأتي من أن استخراجهما يحتاج إلى وقت لا يملكه أحد، وليس من أنهما مخفيان رياضياً.

والسؤال العملي الأول الذي يسأله المطور: إذا كان المفتاح يحتاج إلى عددين أوليين من 1024 بت، فهل يوجد منها ما يكفي حتى لا يختار جهازان نفس العدد؟ والإجابة في مبرهنة الأعداد الأولية Prime Number Theorem، والتي تقول إن احتمال أن يكون عدد عشوائي قرب N أولياً هو تقريباً `1 / ln(N)`. وقرب 21024 قيمة `ln(N)` نحو 710، أي أن عدداً واحداً من كل 710 أعداد أولي، وإذا استبعدنا الأعداد الزوجية من البداية يصبح عدداً من كل 355 عدداً فردياً، وهذا يعني أن عدد الأعداد الأولية من 1024 بت يقارب 21014، وهو رقم أكبر بكثير من عدد الذرات في الكون المرئي، فلا يوجد خطر أن تنفد، والخطر الحقيقي كما سوف نرى في آخر المقال يأتي من مولد عشوائية ضعيف يختار نفس العدد مرتين.

وقد جربنا هذه النسبة في السكربت `primes.py`، حيث يختار أعداداً فردية عشوائية من 1024 بت ويختبرها حتى يجد عشرين عدداً أولياً، والمخرج كان كما يلي:

```text
1024-bit odd candidates tried: 5560, primes found: 20, one prime per 278 odd candidates, expected about 355
time: 54.71 s, 2735 ms per prime
```

في المخرج أعلاه لاحظ التالي:

- السكربت جرب 5560 عدداً فردياً حتى وجد عشرين عدداً أولياً، أي عدداً من كل 278، والقيمة المتوقعة 355، والفرق طبيعي مع عينة صغيرة من عشرين عدداً فقط، فالمسافة بين الأعداد الأولية عشوائية حول متوسطها.
- كل عدد أولي أخذ نحو 2.7 ثانية في Python، وهذا بطيء جداً، والسبب أن السكربت يختبر كل مرشح باختبار Miller-Rabin كاملاً دون أي تصفية مسبقة، وسوف نعود إلى هذا الرقم عندما نقارنه بزمن OpenSSL.

## الحساب المعياري Modular Arithmetic: حساب الساعة

أبسط مثال للحساب المعياري هو الساعة التي على الحائط، فإذا كانت الساعة 10 وأضفت 5 ساعات فالساعة لن تقول 15 وإنما 3، لأنها تعود إلى البداية كلما وصلت إلى 12، وبلغة الرياضيات نكتب `10 + 5 ≡ 3 (mod 12)`، ونقرؤها: 15 و3 متكافئان بالمقياس 12، أي أن باقي قسمتهما على 12 واحد. والعدد 12 هنا يسمى المقياس Modulus، وهو نفس الاسم `modulus` الذي رأيته في أول سطر من ملف المفتاح، والفرق أن ساعة RSA فيها 22048 رقماً تقريباً بدلاً من 12.

![ساعة بالمقياس 12 تبين أن 10 زائد 5 يساوي 3 وأن 7 ضرب 8 يساوي 8 وأن سالب 1 يساوي 11، وبجانبها ساعة RSA الصغيرة بالمقياس 3233 حيث يتحول 65 بالأس 17 إلى 2790 ثم يعود إلى 65 بالأس 2753](https://arabroot.io/content/images/2026/10/crypto-math-rsa-01-clock.webp)

الحساب المعياري هو حساب الساعة: كل نتيجة تعود إلى المجال من 0 إلى n ناقص 1

والميزة التي تجعل هذا الحساب مفيداً للتشفير أن الجمع والطرح والضرب تبقى صحيحة إذا أخذت الباقي في أي خطوة، فتستطيع أن تضرب ثم تأخذ الباقي، أو تأخذ الباقي من كل عدد ثم تضرب ثم تأخذ الباقي مرة أخرى، والنتيجة واحدة، وهذا هو ما يسمح بحساب أرقام مثل `652753` دون أن يكبر الرقم أبداً عن حجم المقياس. والسكربت `toy_rsa.py` يبدأ بهذه الأمثلة الثلاثة:

```text
== 1. clock arithmetic
10 + 5 mod 12 = 3
7 * 8 mod 12  = 8
-1 mod 12     = 11
```

السطر الأول هو مثال الساعة نفسه، والثاني يبين الضرب: 7 × 8 = 56، و56 فيها أربع دورات كاملة من 12 أي 48، والباقي 8\. أما السطر الثالث فيستحق التوقف عنده، لأن Python أعطت 11 لسالب واحد، وهذا هو الجواب الرياضي الصحيح، فساعة تعود ساعة واحدة إلى الخلف من 12 تصل إلى 11\. ولكن ليست كل اللغات كذلك، والمثال التالي في Node.js يبين الفرق:

```bash
node -e "console.log(-1 % 12, ((-1 % 12) + 12) % 12, -367 % 3120)"
```

والمخرج سوف يكون كما يلي:

```text
-1 11 -367
```

لاحظ أن المعامل `%` في JavaScript، ومثله في C وJava وC#، يعطي باقياً بنفس إشارة العدد المقسوم، فيعيد `-1` بدلاً من 11، ولذلك إذا نقلت كوداً رياضياً من Python إلى إحدى هذه اللغات فيجب أن تصحح الناتج السالب بإضافة المقياس ثم أخذ الباقي مرة أخرى كما في القيمة الثانية، وإلا ظهر خطأ صامت في أول عملية يكون فيها الناتج سالباً، والرقم الثالث `-367` ليس مثالاً عشوائياً، فهو الرقم الذي سوف يخرج من خوارزمية إقليدس بعد قليل، وفيه يظهر هذا الخطأ بالضبط. وفي [مقال الأنظمة العددية](https://arabroot.io/articles/%D8%A7%D9%84%D8%A7%D9%86%D8%B8%D9%85%D8%A9-%D8%A7%D9%84%D8%B9%D8%AF%D8%AF%D9%8A%D8%A9-%D9%88%D8%A7%D9%84%D8%AB%D9%86%D8%A7%D8%A6%D9%8A-%D9%84%D9%84%D9%85%D8%A8%D8%B1%D9%85%D8%AC%D9%8A%D9%86/) رأينا كيف تخزن الأعداد السالبة في البتات، وهذا الاختلاف في `%` قرار من كل لغة وليس من العتاد.

وهناك عملية واحدة لا تعمل كما تتوقع في الحساب المعياري، وهي القسمة، فلا يوجد معنى لـ `3 / 17` بالمقياس 3120 بالطريقة المعتادة، وإنما نبحث عن عدد إذا ضربناه في 17 أعطى 1 بالمقياس 3120، وهذا العدد يسمى المعكوس المعياري، وهو قلب RSA كله، ولكي نجده نحتاج إلى خوارزمية عمرها أكثر من ألفي سنة.

## القاسم المشترك الأكبر GCD وخوارزمية إقليدس

القاسم المشترك الأكبر Greatest Common Divisor لعددين هو أكبر عدد يقسمهما معاً، فالقاسم المشترك الأكبر لـ 12 و18 هو 6، وإذا كان القاسم المشترك الأكبر 1 نقول إن العددين أوليان فيما بينهما Coprime، حتى لو لم يكن أي منهما أولياً بذاته، مثل 8 و15\. والطريقة البسيطة لحسابه أن تحلل كل عدد إلى عوامله ثم تأخذ المشترك، ولكن هذه الطريقة تحتاج إلى التحليل، وهو بالضبط ما قلنا إنه صعب على الأعداد الكبيرة، لذلك لا تصلح إطلاقاً لأعداد RSA.

أما خوارزمية إقليدس Euclidean Algorithm فتعتمد على ملاحظة بسيطة: القاسم المشترك لـ a وb هو نفسه القاسم المشترك لـ b وباقي قسمة a على b، فتستبدل العددين في كل خطوة بعددين أصغر حتى يصبح الباقي صفراً، وآخر باق غير الصفر هو الجواب، وعدد الخطوات يتناسب مع عدد خانات العدد وليس مع قيمته، لذلك تحسب القاسم المشترك لعددين من 2048 بت في أجزاء من المللي ثانية كما سوف نرى في قسم المفاتيح الضعيفة. والنسخة الموسعة Extended Euclidean Algorithm تفعل شيئاً إضافياً مهماً: تحفظ في كل خطوة معاملين x وy بحيث يبقى `a·x + b·y` مساوياً للباقي الحالي، فعندما تنتهي تعطيك القاسم المشترك ومعه المعاملين اللذين يكتبانه، وهذه هي الدالة في السكربت:

```python
def egcd(a, b):
    """Extended Euclid, printing each row: returns (g, x, y) with a*x + b*y = g."""
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1
    print(f"{'q':>4} {'r':>6} {'x':>6} {'y':>6}")
    print(f"{'':>4} {old_r:>6} {old_x:>6} {old_y:>6}")
    while r:
        k = old_r // r
        old_r, r = r, old_r - k * r
        old_x, x = x, old_x - k * x
        old_y, y = y, old_y - k * y
        print(f"{k:>4} {old_r:>6} {old_x:>6} {old_y:>6}")
    return old_r, old_x, old_y
```

وعندما نشغلها على العددين 3120 و17، وهما العددان اللذان سوف نحتاجهما في مفتاحنا الصغير بعد قليل، يكون المخرج كما يلي:

```text
   q      r      x      y
       3120      1      0
 183     17      0      1
   1      9      1   -183
   1      8     -1    184
   8      1      2   -367
gcd=1: 3120*(2) + 17*(-367) = 1
```

اقرأ الجدول من الأعلى إلى الأسفل، وكل سطر خطوة واحدة:

- السطر الأول هو نقطة البداية: الباقي 3120، ومعاملاه 1 و0، لأن `3120 × 1 + 17 × 0 = 3120`.
- في الخطوة الأولى يدخل 17 كباق، ومعاملاه 0 و1\. والعمود q فيه 183، وهو ناتج القسمة الصحيحة لـ 3120 على 17، وهو الرقم الذي نستخدمه لحساب الصف التالي.
- بعد ذلك 3120 ناقص 183 × 17 يعطي الباقي 9، ومعاملاه 1 و-183، وتستطيع أن تتحقق بيدك: `3120 − 183 × 17 = 9`.
- ثم 17 على 9 يعطي ناتجاً 1 وباقياً 8، ثم 9 على 8 يعطي ناتجاً 1 وباقياً 1، ثم 8 على 1 يعطي ناتجاً 8 وباقياً صفراً فتتوقف الحلقة.
- آخر باق غير الصفر هو 1، أي أن 3120 و17 أوليان فيما بينهما، ومعه المعاملان 2 و-367، والسطر الأخير يتحقق منهما: `3120 × 2 + 17 × (−367) = 1`.

أربع خطوات فقط للوصول إلى الجواب، وهذه المعادلة الأخيرة تسمى متطابقة بيزو Bézout's Identity، وهي التي تعطينا المعكوس المعياري مباشرة كما في القسم التالي.

## المعكوس المعياري Modular Inverse

خذ المعادلة الأخيرة `3120 × 2 + 17 × (−367) = 1` وانظر إليها بالمقياس 3120، فالحد الأول من مضاعفات 3120 فيختفي، ويبقى `17 × (−367) ≡ 1 (mod 3120)`، أي أن −367 هو العدد الذي إذا ضربته في 17 أعطاك 1، وهذا هو تعريف المعكوس المعياري. ولأننا نريد عدداً موجباً نضيف إليه المقياس، فنحصل على 2753، وهنا بالضبط يظهر خطأ `%` الذي رأيناه في JavaScript، فلو كتبت `-367 % 3120` هناك لحصلت على −367 بدلاً من 2753، وأي مفتاح يحسب بهذا الشكل لن يفك التشفير أبداً. والسطر التالي من المخرج يبين الحساب في Python:

```text
d = y mod phi = 2753 | check e*d mod phi = 1 | pow(e,-1,phi) = 2753
```

لاحظ أن Python تعطيك المعكوس المعياري مباشرة بالدالة `pow(e, -1, phi)`، وهذه الإمكانية أضيفت إلى الدالة [pow في Python 3.8](https://docs.python.org/3/library/functions.html?ref=arabroot.io#pow)، وهي تستخدم نفس فكرة إقليدس الموسعة من الداخل، والنتيجة 2753 هي نفس ما حسبناه بالجدول. والشرط الوحيد لوجود المعكوس هو أن يكون العددان أوليين فيما بينهما، فإذا كان القاسم المشترك أكبر من 1 فلا يوجد معكوس، وتعطيك Python الخطأ `ValueError: base is not invertible for the given modulus`، ولهذا السبب يشترط RSA أن يكون الأس العام e أولياً مع `(p−1)` و`(q−1)`، وهو الشرط الذي رأيته في السطر الأول من المفتاح الصغير `gcd(e,phi)=1`.

## مبرهنة فيرما Fermat ومبرهنة أويلر Euler: لماذا تعود الرسالة؟

بقيت الأداة الأخيرة، وهي التي تجيب عن السؤال الأهم: لماذا إذا رفعنا الرسالة إلى الأس e ثم رفعنا الناتج إلى الأس d نعود إلى الرسالة نفسها؟ والبداية مع مبرهنة فيرما الصغرى Fermat's Little Theorem، والتي تقول إن p إذا كان أولياً وa لا يقبل القسمة عليه فإن `ap−1 ≡ 1 (mod p)`، أي أنك إذا رفعت أي عدد إلى الأس p−1 ثم أخذت الباقي على p فسوف تحصل على 1 دائماً. وفكر فيها كساعة غريبة: مهما كان العدد الذي تبدأ منه، فإن ضربه في نفسه p−1 مرة يعيدك إلى 1.

ثم جاء أويلر Euler وعمم الفكرة لأي مقياس n، وليس فقط للأعداد الأولية، فعرف الدالة φ(n)، وتسمى دالة أويلر Euler's Totient Function، وهي عدد الأعداد من 1 إلى n التي ليس بينها وبين n أي عامل مشترك، ومبرهنة أويلر تقول إن `aφ(n) ≡ 1 (mod n)` لكل a أولي مع n. وحساب φ(n) سهل جداً إذا عرفت تحليل n، فإذا كان `n = p × q` فإن `φ(n) = (p−1)(q−1)`، وصعب جداً إذا لم تعرفه، وهذا هو الباب الخلفي الذي كنا نبحث عنه: من يعرف p وq يعرف φ، ومن يعرف φ يستطيع حساب d، ومن لا يعرفهما لا يستطيع.

والآن نجمع الأدوات: نختار e وd بحيث `e × d = 1 + k × φ(n)` لعدد صحيح k، أي أن d هو المعكوس المعياري لـ e بالمقياس φ، وعندها:

```text
(m^e)^d = m^(e·d) = m^(1 + k·φ(n)) = m · (m^φ(n))^k ≡ m · 1^k = m   (mod n)
```

هذا كل RSA في سطر واحد. والسكربت يتحقق من المبرهنتين على أرقامنا الصغيرة:

```text
== 3. Fermat and Euler
pow(2, 60, 61) = 1 (Fermat: a^(p-1) = 1 mod p)
pow(2, phi, n) = 1 | pow(2, lambda, n) = 1
pow(61, phi, n) = 1220 (61 shares a factor with n, Euler does not apply)
```

في المخرج أعلاه لاحظ التالي:

- السطر الأول هو فيرما: 2 مرفوعة إلى الأس 60 بالمقياس 61 تساوي 1، لأن 61 أولي.
- السطر الثاني هو أويلر: 2 مرفوعة إلى φ = 3120 بالمقياس 3233 تساوي 1\. وفيه قيمة ثانية هي λ، وتسمى دالة كارمايكل Carmichael Function، وهي المضاعف المشترك الأصغر LCM لـ `(p−1)` و`(q−1)`، وقيمتها هنا 780، أي ربع φ، وهي أصغر أس يحقق نفس النتيجة لكل الأعداد، ولها دور مهم في المفتاح الحقيقي كما سوف نرى.
- السطر الثالث يبين شرط المبرهنة: العدد 61 يشترك مع 3233 في العامل 61، فلا تنطبق عليه مبرهنة أويلر وكان الناتج 1220 وليس 1\. وقد يتساءل البعض: هل يعني هذا أن RSA يفشل إذا كانت الرسالة من مضاعفات p؟ والإجابة لا، فالمعادلة `med ≡ m` تبقى صحيحة لكل m باستخدام مبرهنة الباقي الصيني التي سوف نراها في المفتاح الحقيقي، ولكن احتمال أن تقع رسالة عشوائية على مضاعف لعدد أولي من 1024 بت معدوم عملياً، ولو وقعت لكشفت تحليل n بحساب قاسم مشترك واحد.

## RSA بيدك: مفتاح من العددين 61 و53

الآن نملك كل الأدوات، فلنبن مفتاحاً كاملاً بأرقام صغيرة نستطيع التحقق منها بالآلة الحاسبة، والخطوات كما يلي:

1. نختار عددين أوليين: `p = 61` و`q = 53`.
2. نحسب المقياس `n = p × q = 3233`، وهو الذي ينشر للجميع.
3. نحسب `φ = (p−1)(q−1) = 60 × 52 = 3120`، و`λ = lcm(60, 52) = 780`، وهذان سريان.
4. نختار الأس العام `e = 17`، ونتحقق من أن `gcd(17, 3120) = 1`.
5. نحسب الأس الخاص d كمعكوس معياري لـ e بالمقياس φ، وهو 2753 كما حسبناه بخوارزمية إقليدس.
6. المفتاح العام هو الزوج `(n, e) = (3233, 17)`، والمفتاح الخاص هو `d = 2753` ومعه p وq.

والمخرج من السكربت يؤكد الأرقام ويشفر الرسالة 65 ثم يفكها:

```text
== 2. key generation
p=61 q=53 n=3233 phi=3120 lambda=780 gcd(e,phi)=1
...
d from lambda = 413 | e*d mod lambda = 1
== 4. encrypt and decrypt m = 65
c = 65^17 mod 3233 = 2790
c^d mod n         = 65
c^d_lambda mod n  = 65
```

الرسالة 65 تحولت بالمفتاح العام إلى 2790، وهو رقم لا يشبه 65 في شيء، ثم أعادها المفتاح الخاص إلى 65\. ولاحظ السطر `d from lambda = 413`: إذا حسبت المعكوس بالمقياس λ بدلاً من φ تحصل على أس خاص أصغر بكثير هو 413، والسطر الأخير يبين أنه يفك التشفير أيضاً، والسبب أن λ هو أصغر أس يعيد كل الأعداد إلى 1، فأي d يحقق `e × d ≡ 1 (mod λ)` يكفي، ولذلك يوجد أكثر من أس خاص صحيح لنفس المفتاح العام، وهذه الملاحظة سوف تفسر مشكلة واجهناها مع مفتاح OpenSSL الحقيقي.

وهذا ليس مثالاً جديداً في الحقيقة، فالورقة الأصلية لـ RSA سنة 1978 فيها مثال من نفس النوع بالعددين 47 و59 والأس الخاص 157، وقد أضفناه إلى السكربت لنتحقق منه:

```text
== 6. the example in the 1978 RSA paper: p=47, q=59, d=157
n=2773 phi=2668 e=17 | 920^e mod n = 948 | 948^d mod n = 920
```

والأرقام مطابقة لما في الورقة: المقياس 2773، والأس العام 17 الذي حسبه المؤلفون بخوارزمية إقليدس من 157، والكتلة الأولى من رسالتهم 920 تتشفر إلى 948 وتعود إلى 920\. والصورة التالية تجمع خطوات مفتاحنا الصغير في مكان واحد:

![خطوات بناء مفتاح RSA صغير: العددان الأوليان 61 و53، ثم n يساوي 3233 وفاي يساوي 3120 ولامدا يساوي 780، ثم e يساوي 17 وd يساوي 2753 من خوارزمية إقليدس، ثم المفتاح العام والمفتاح الخاص، وفي الأسفل الرسالة 65 تتحول إلى 2790 بالمفتاح العام وتعود إلى 65 بالمفتاح الخاص](https://arabroot.io/content/images/2026/10/crypto-math-rsa-02-toy-rsa.webp)

مفتاح RSA كامل بأرقام صغيرة: كل رقم هنا له مقابل في ملف مفتاح OpenSSL الحقيقي

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

## الأس السريع Square-and-Multiply

الطريقة البسيطة لحساب `cd mod n` هي أن تضرب c في نفسه d−1 مرة، وفي مثالنا الصغير هذا يعني 2752 عملية ضرب، وهو رقم معقول، ولكن في المفتاح الحقيقي الذي أنشأناه كان d من 2045 بتاً، أي رقماً من 616 خانة عشرية، ولو كان كل حاسوب على الأرض يجري مليارات العمليات في الثانية منذ بداية الكون لما اقترب من هذا العدد من عمليات الضرب. لذلك هذه الطريقة غير مناسبة إطلاقاً، والحل خوارزمية الأس السريع Square-and-Multiply، وتسمى أيضاً Binary Exponentiation.

والفكرة أن تكتب الأس بالثنائي، ثم تمر على بتاته من اليسار إلى اليمين: عند كل بت تربع الناتج الحالي، وإذا كان البت 1 تضربه أيضاً في الأساس، وتأخذ الباقي على n بعد كل عملية حتى لا يكبر الرقم. والسبب أن تربيع الناتج يضاعف الأس الذي وصلت إليه، وضربه في الأساس يضيف 1 إليه، وهاتان العمليتان معاً تبنيان أي أس بت بعد بت، تماماً كما تقرأ رقماً ثنائياً وتحوله إلى عشري. وهذه الدالة في السكربت تطبع كل خطوة:

```python
def trace_pow(base, exp, mod):
    """Square-and-multiply from the most significant bit, printing each step."""
    bits = bin(exp)[2:]
    acc, sq, mul = 1, 0, 0
    print(f"exponent {exp} = {bits} in binary")
    for i, b in enumerate(bits):
        if i:
            acc = acc * acc % mod
            sq += 1
        if b == "1":
            acc = acc * base % mod
            mul += 1
        print(f"  bit {b}: acc = {acc}")
    print(f"  squarings={sq} multiplications={mul} (naive would need {exp - 1} multiplications)")
    return acc
```

والمخرج لتشفير 65 بالأس 17 كما يلي:

```text
exponent 17 = 10001 in binary
  bit 1: acc = 65
  bit 0: acc = 992
  bit 0: acc = 1232
  bit 0: acc = 1547
  bit 1: acc = 2790
  squarings=4 multiplications=2 (naive would need 16 multiplications)
```

الأس 17 بالثنائي `10001`، فالبت الأول 1 يضع الأساس 65 في الناتج، ثم ثلاثة أصفار، وفي كل منها نربع فقط: 65 تربيع بالمقياس 3233 يعطي 992، ثم 1232، ثم 1547، وفي البت الأخير نربع ثم نضرب في 65 فنصل إلى 2790، وهو نفس الناتج الذي رأيناه في التشفير. أربع عمليات تربيع وعمليتا ضرب بدلاً من 16 عملية ضرب. أما فك التشفير بالأس 2753 فكان كما يلي:

```text
exponent 2753 = 101011000001 in binary
  bit 1: acc = 2790
  bit 0: acc = 2269
  ...
  bit 1: acc = 65
  squarings=11 multiplications=5 (naive would need 2752 multiplications)
decrypted: 65
```

الأس من 12 بتاً، فاحتجنا إلى 11 عملية تربيع و5 عمليات ضرب، أي 16 عملية بدلاً من 2752\. والقاعدة العامة أن عدد عمليات التربيع يساوي عدد بتات الأس ناقص واحد، وعدد عمليات الضرب يساوي عدد البتات التي قيمتها 1، وفي المفتاح الحقيقي الذي سوف نقرؤه كان d من 2045 بتاً منها 1018 بتاً قيمتها 1، أي 2044 عملية تربيع و1018 عملية ضرب، فتحول العدد المستحيل إلى نحو ثلاثة آلاف عملية على أرقام من 2048 بت.

![بتات الأس 17 وهي 10001 من اليسار إلى اليمين، وتحت كل بت عملية تربيع أو تربيع وضرب وقيمة الناتج 65 ثم 992 ثم 1232 ثم 1547 ثم 2790، وجدول يقارن عدد العمليات بالطريقة البسيطة وبالأس السريع للأسس 17 و2753 وأس المفتاح الحقيقي من 2045 بتاً](https://arabroot.io/content/images/2026/10/crypto-math-rsa-03-square-multiply.webp)

الأس السريع يمر على بتات الأس: تربيع عند كل بت، وضرب إضافي عند كل 1

وهذا يفسر أيضاً لماذا يختار الجميع الأس العام `65537`، فهو بالثنائي `10000000000000001`، أي 17 بتاً ليس فيها إلا بتان قيمتهما 1، فيحتاج التشفير والتحقق من التوقيع إلى 16 عملية تربيع وعمليتي ضرب فقط، وهذا يجعل العمليات العامة سريعة جداً، بينما يبقى الأس الخاص كبيراً وعشوائياً. وقد يتساءل البعض: لماذا لا نختار 3 فيكون أسرع؟ والإجابة أن الأس الصغير جداً كان سبباً في هجمات على RSA المجرد كما سوف نرى في قسم الحشو، ولذلك يشترط المعيار [FIPS 186-5](https://csrc.nist.gov/pubs/fips/186-5/final?ref=arabroot.io) أن يكون e فردياً وأكبر من 216، و65537 هو أول عدد أولي يحقق ذلك.

⚠️

الدالة `trace_pow` أعلاه للتعليم فقط، فهي تضرب فقط عندما يكون البت 1، وبالتالي يختلف زمنها بحسب بتات الأس الخاص، ومن يقيس زمن عدد كبير من عمليات فك التشفير يستطيع أن يستنتج شيئاً عن هذه البتات، وهذا ما يسمى هجوم التوقيت Timing Attack. المكتبات الحقيقية مثل OpenSSL تستخدم أساليب زمنها ثابت Constant Time، وتخلط الرسالة بعدد عشوائي قبل العملية Blinding، لذلك لا تكتب عمليات RSA بنفسك في كود الإنتاج.

## كيف تجد عدداً أولياً من 1024 بت؟ اختبار Miller-Rabin

رأينا أن عدداً من كل 355 عدداً فردياً من 1024 بت أولي، لذلك فطريقة توليد العدد الأولي بسيطة: اختر عدداً فردياً عشوائياً واختبره، وإذا لم يكن أولياً اختر غيره. والمشكلة كلها في الاختبار، فالطريقة البسيطة هي القسمة على كل الأعداد حتى الجذر التربيعي، والجذر التربيعي لعدد من 1024 بت هو عدد من 512 بت، وهذا مستحيل كما سوف نرى في قسم التحليل.

والفكرة الثانية التي تخطر على البال هي استخدام مبرهنة فيرما بالعكس: إذا كان p أولياً فإن `ap−1 mod p = 1`، فإذا اختبرت عدداً ولم تحصل على 1 فهو بالتأكيد ليس أولياً، وإذا حصلت على 1 فهو على الأغلب أولي. وهذا الاختبار سريع جداً لأنه أس سريع واحد، ولكن فيه مشكلة رئيسية: توجد أعداد مركبة تجتاز اختبار فيرما لكل الأساسات الأولية معها، وتسمى أعداد كارمايكل Carmichael Numbers، وأصغرها 561 = 3 × 11 × 17، والسكربت `primes.py` يبين ذلك:

```text
561 = 3*11*17
  Fermat with bases 2,5,7,13: True
  Miller-Rabin               : False
  1105: Fermat=True MR=False
  1729: Fermat=True MR=False
  2465: Fermat=True MR=False
  2821: Fermat=True MR=False
  6601: Fermat=True MR=False
```

كل الأعداد في المخرج مركبة، ومع ذلك قال اختبار فيرما عنها جميعاً `True`، أي أنها أولية، بينما رفضها Miller-Rabin كلها. والفرق أن Miller-Rabin لا يكتفي بالنتيجة النهائية، وإنما ينظر إلى الطريق إليها: يكتب `n − 1 = 2s × d` حيث d فردي، ثم يحسب `ad` ويربعه s مرة، وفي عدد أولي لا يمكن أن تظهر قيمة تربيعها 1 إلا إذا كانت 1 أو n−1، أما في العدد المركب فيظهر غالباً جذر تربيعي آخر للواحد، فيكشف أن العدد مركب. وهذه الدالة في السكربت:

```python
def miller_rabin(n, rounds=40, rng=random.SystemRandom()):
    if n < 4:
        return n in (2, 3)
    if n % 2 == 0:
        return False
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(rounds):
        a = rng.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True
```

والمعروف عن هذا الاختبار أن العدد المركب لا يجتاز الجولة الواحدة باحتمال أكبر من ربع مهما كان، فإذا اجتاز 40 جولة بأساسات عشوائية مستقلة فاحتمال أن يكون مركباً أقل من `4−40`، وفي الحقيقة أقل من ذلك بكثير للأعداد العشوائية الكبيرة، ولهذا يعتمده المعيار FIPS 186-5 في الملحق B.3، ويحدد في الجدول B.1 الحد الأدنى لعدد الجولات بحسب طول العدد. ولاحظ أن الاختبار احتمالي، فهو لا يثبت أن العدد أولي وإنما يجعل الخطأ أقل احتمالاً من أي عطل في العتاد نفسه.

وتذكر رقم Python الذي رأيناه في قسم الأعداد الأولية: 2.7 ثانية لكل عدد أولي من 1024 بت. بينما أنشأ OpenSSL مفتاحاً كاملاً من 2048 بت، أي عددين أوليين من 1024 بت مع كل الحسابات، في 262 مللي ثانية فقط في نفس ال Container، والفرق ليس فقط أن OpenSSL مكتوب بلغة C، وإنما أنه يقسم كل مرشح أولاً على الأعداد الأولية الصغيرة، وهذا يستبعد أغلب المرشحين قبل أن يصلوا إلى Miller-Rabin المكلف، ويصف المعيار هذه الخطوة في الملحقين B.7 وB.8 باسم القسمة التجريبية Trial Division والغربال Sieve.

## نقرأ مفتاح OpenSSL الحقيقي رقماً رقماً

الآن نعود إلى الأرقام الثمانية التي بدأنا بها المقال. الأوامر التالية من `run.sh` تنشئ مفتاحاً من 2048 بت، ثم تطبع محتواه كنص، والتوثيق الكامل لهما في صفحتي [openssl genpkey](https://docs.openssl.org/3.5/man1/openssl-genpkey/?ref=arabroot.io) و[EVP\_PKEY-RSA](https://docs.openssl.org/3.5/man7/EVP%5FPKEY-RSA/?ref=arabroot.io):

```bash
t0=$(date +%s%N); openssl genpkey -quiet -algorithm RSA -pkeyopt rsa_keygen_bits:2048 -out /tmp/rsa/key.pem; echo "openssl genpkey 2048: $(( ($(date +%s%N) - t0) / 1000000 )) ms"
openssl pkey -in /tmp/rsa/key.pem -text -noout > /tmp/rsa/key.txt
head -n 4 /tmp/rsa/key.txt
grep -E '^[a-zA-Z]' /tmp/rsa/key.txt
```

والمخرج سوف يكون كما يلي:

```text
openssl genpkey 2048: 262 ms
Private-Key: (2048 bit, 2 primes)
modulus:
    00:d9:22:5a:86:de:1e:f7:68:59:d4:58:55:de:e9:
    b3:fa:f5:38:9a:eb:b5:9a:c0:5d:03:8a:a3:5b:5c:
Private-Key: (2048 bit, 2 primes)
modulus:
publicExponent: 65537 (0x10001)
privateExponent:
prime1:
prime2:
exponent1:
exponent2:
coefficient:
```

السطر الأول هو الزمن الذي قسناه حول الأمر، ثم السطر `(2048 bit, 2 primes)` الذي يقول إن المقياس من 2048 بت ومبني من عددين أوليين، فـ OpenSSL يدعم أيضاً مفاتيح من أكثر من عددين أوليين Multi-Prime RSA، ولكن العدد الافتراضي 2\. ثم يبدأ المقياس بالـ Hex، والبايت الأول `00` ليس جزءاً من القيمة، وإنما يضاف لأن البايت الذي يليه `d9` بته الأعلى 1، فيمنع الصفر قراءة الرقم كعدد سالب. وبعد ذلك الأسماء الثمانية، والجدول التالي يربط كل اسم بالرقم الذي حسبناه بيدنا في المفتاح الصغير:

| الاسم في OpenSSL | الرمز | المعنى                                      | في المفتاح الصغير                 |
| ---------------- | ----- | ------------------------------------------- | --------------------------------- |
| modulus          | n     | المقياس، حاصل ضرب العددين الأوليين، وهو عام | 3233                              |
| publicExponent   | e     | الأس العام                                  | 17                                |
| privateExponent  | d     | الأس الخاص، معكوس e                         | 413 بالمقياس λ أو 2753 بالمقياس φ |
| prime1 وprime2   | p وq  | العددان الأوليان                            | 61 و53                            |
| exponent1        | dP    | d mod (p−1)                                 | 413 mod 60 = 53                   |
| exponent2        | dQ    | d mod (q−1)                                 | 413 mod 52 = 49                   |
| coefficient      | qInv  | معكوس q بالمقياس p                          | معكوس 53 بالمقياس 61 = 38         |

والسكربت `check_key.py` يقرأ هذه الأرقام من النص الذي طبعه OpenSSL، ويتحقق من كل معادلة شرحناها، والدالة `field` فيه تأخذ الأسطر التي تحت كل اسم وتحذف النقطتين والمسافات ثم تحول الـ Hex إلى عدد صحيح:

```python
# check_key.py: read the numbers OpenSSL printed for a real RSA key and check the math of the article on them.
#   python3 check_key.py key.txt
import sys, re, time
from math import gcd, lcm
from primes import miller_rabin

text = open(sys.argv[1]).read()

def field(name):
    m = re.search(rf"^{name}:\s*\n((?:\s+[0-9a-f:]+\n)+)", text, re.M)
    return int(re.sub(r"[\s:]", "", m.group(1)), 16)

n, d = field("modulus"), field("privateExponent")
p, q = field("prime1"), field("prime2")
dP, dQ, qInv = field("exponent1"), field("exponent2"), field("coefficient")
e = int(re.search(r"publicExponent: (\d+)", text).group(1))

short = lambda v: f"{str(v)[:12]}...{str(v)[-6:]} ({v.bit_length()} bits)"
print("n   =", short(n))
print("p   =", short(p))
print("q   =", short(q))
print("e   =", e)
print("n == p*q                 :", n == p * q)
print("p, q prime (Miller-Rabin):", miller_rabin(p), miller_rabin(q))
phi, lam = (p - 1) * (q - 1), lcm(p - 1, q - 1)
print("gcd(p-1, q-1)            :", gcd(p - 1, q - 1))
print("e*d mod lambda           :", e * d % lam)
print("e*d mod phi              :", short(e * d % phi))
print("phi / lambda             :", phi // lam)
print("d == pow(e,-1,lambda)    :", d == pow(e, -1, lam))
print("d == pow(e,-1,phi)       :", d == pow(e, -1, phi))
print("dP == d mod (p-1)        :", dP == d % (p - 1))
print("dQ == d mod (q-1)        :", dQ == d % (q - 1))
print("qInv*q mod p             :", qInv * q % p)

m = int.from_bytes(b"arabroot", "big")
c = pow(m, e, n)
t0 = time.perf_counter()
for _ in range(200):
    plain = pow(c, d, n)
t_full = (time.perf_counter() - t0) / 200
t0 = time.perf_counter()
for _ in range(200):
    m1, m2 = pow(c, dP, p), pow(c, dQ, q)
    h = qInv * (m1 - m2) % p
    plain_crt = m2 + h * q
t_crt = (time.perf_counter() - t0) / 200
print("decrypt with d           :", plain.to_bytes(8, "big"), f"{t_full * 1000:.2f} ms")
print("decrypt with CRT         :", plain_crt.to_bytes(8, "big"), f"{t_crt * 1000:.2f} ms")
print(f"CRT speed-up             : {t_full / t_crt:.1f}x")
print("bits in d                :", d.bit_length(), "| ones in d:", bin(d).count("1"))
```

والمخرج سوف يكون كما يلي:

```text
n   = 274106525792...787499 (2048 bits)
p   = 166944818078...337263 (1024 bits)
q   = 164189897564...207173 (1024 bits)
e   = 65537
n == p*q                 : True
p, q prime (Miller-Rabin): True True
gcd(p-1, q-1)            : 2
e*d mod lambda           : 1
e*d mod phi              : 1...1 (1 bits)
phi / lambda             : 2
d == pow(e,-1,lambda)    : True
d == pow(e,-1,phi)       : True
dP == d mod (p-1)        : True
dQ == d mod (q-1)        : True
qInv*q mod p             : 1
decrypt with d           : b'arabroot' 55.92 ms
decrypt with CRT         : b'arabroot' 19.07 ms
CRT speed-up             : 2.9x
bits in d                : 2045 | ones in d: 1018
```

وهذا المخرج يستحق القراءة سطراً سطراً:

- الأسطر الأربعة الأولى تختصر الأرقام الكبيرة إلى أولها وآخرها مع عدد بتاتها: المقياس من 2048 بت، وكل من العددين الأوليين من 1024 بت بالضبط، والأس العام 65537.
- `n == p*q` صحيح، فالمقياس فعلاً حاصل ضرب prime1 وprime2، وMiller-Rabin بأربعين جولة يقبل الاثنين كأعداد أولية.
- `gcd(p-1, q-1)` يساوي 2، وهذا متوقع لأن العددين الأوليين فرديان، فكل من `p−1` و`q−1` زوجي، ولذلك يكون φ ضعف λ على الأقل، كما يقول السطر `phi / lambda : 2`.
- `e*d mod lambda` يساوي 1، فالأس الخاص هو معكوس e بالمقياس λ، وفي هذا المفتاح تحديداً كان أيضاً معكوسه بالمقياس φ، والسبب سوف نشرحه في القسم التالي لأنه كان مشكلة حقيقية.
- الأسطر الثلاثة التالية تؤكد معنى exponent1 وexponent2 وcoefficient كما في الجدول: `dP` و`dQ` هما d مختصراً بالمقياس `p−1` و`q−1`، و`qInv × q` بالمقياس p يساوي 1.
- سطرا فك التشفير يبينان أن الرسالة `arabroot` عادت بالطريقتين، الأولى بالأس d مباشرة في 55.92 مللي ثانية، والثانية بمبرهنة الباقي الصيني في 19.07 مللي ثانية، أي أسرع بنحو 2.9 مرة. والأرقام هنا لـ Python، وOpenSSL أسرع بكثير منها، ولكن النسبة هي المهمة.
- السطر الأخير يبين حجم الأس الخاص: 2045 بتاً منها 1018 بتاً قيمتها 1، وهي الأرقام التي استخدمناها في حساب عدد عمليات الأس السريع.

### لماذا يحفظ المفتاح خمسة أرقام إضافية؟ مبرهنة الباقي الصيني CRT

لو كان المفتاح الخاص يحتاج فقط إلى n وd، فلماذا يحفظ OpenSSL معهما p وq وdP وdQ وqInv؟ والإجابة هي السرعة. فمبرهنة الباقي الصيني Chinese Remainder Theorem تقول إنك إذا عرفت باقي عدد ما على p وباقيه على q، وكان p وq أوليين فيما بينهما، فإنك تستطيع استعادة باقيه على `p × q` بطريقة واحدة فقط. لذلك بدلاً من حساب أس واحد كبير بالمقياس n من 2048 بت، يحسب المفتاح أسين صغيرين: `cdP mod p` و`cdQ mod q`، كل منهما بمقياس من 1024 بت وأس من 1024 بت، ثم يجمعهما بمعادلة Garner التي تستخدم qInv، وهي الأسطر الثلاثة في الحلقة الثانية من السكربت.

وقد يتساءل البعض: لماذا أصبح أسرع بثلاث مرات تقريباً وليس بمرتين؟ والسبب أن تكلفة ضرب عددين تزيد أسرع من حجمهما، فضرب عددين بنصف الحجم أرخص بأكثر من النصف، وعدد عمليات الأس السريع أيضاً نصف العدد لأن الأس نصف الطول، فتربح من الجهتين ثم تدفع ثمن عمليتين بدلاً من واحدة. وهذا ما يصفه المعيار [PKCS #1 الإصدار 2.2 في RFC 8017](https://www.rfc-editor.org/rfc/rfc8017?ref=arabroot.io)، حيث يعرف المفتاح الخاص بصيغتين: الزوج `(n, d)`، أو الخماسية التي تحوي p وq وdP وdQ وqInv، ولذلك يحفظ OpenSSL الصيغتين معاً في نفس الملف.

🛑

هذا يعني أن أي رقم من prime1 أو prime2 يكفي وحده لاستخراج كل المفتاح الخاص، فإذا عرفت p تقسم n عليه فتحصل على q، ثم تحسب d. لذلك لا تطبع مخرج `openssl pkey -text` لمفتاح حقيقي في سجلات CI أو في تذكرة دعم، ولا تنسخ منه "الأرقام العامة فقط" دون أن تعرف أي حقل منها عام، فالعام هو modulus وpublicExponent فقط.

### مشكلة واجهناها: الأس الخاص لا يساوي معكوس e بالمقياس φ

في التشغيل الأول للتجربة كان السكربت يتحقق فقط من `e*d mod phi`، لأن هذا ما يذكره أغلب الشرح المبسط لـ RSA، وكانت النتيجة عدداً من مئات الخانات بدلاً من 1، وطبع السطر `d == pow(e,-1,phi) : False`. ولكن `n == p*q` كان صحيحاً، فالمشكلة لم تكن في قراءة الأرقام من ملف OpenSSL، وفك التشفير بالأس d كان يعيد الرسالة، وفي ذلك المفتاح كان `gcd(p-1, q-1)` يساوي 142 وليس 2\. والسبب كما رأينا في مثال 61 و53 أن OpenSSL يحسب d بالمقياس λ وليس φ، وهذا ما يشترطه المعيار FIPS 186-5 صراحة في الملحق A.1.1، حيث يجب أن يكون `d = e−1 mod LCM(p−1, q−1)`، وأن يكون d أكبر من 2nlen/2. وعندما يكون `gcd(p−1, q−1)` كبيراً يكون λ أصغر من φ بكثير، فيختلف المعكوسان، أما عندما يكون 2 فقط كما في المفتاح الذي عرضناه، فإن φ يساوي 2λ، ومعكوس e بالمقياس φ هو إما d نفسه أو `d + λ`، فيتطابقان في نصف المفاتيح تقريباً، وهذا ما حدث في التشغيل الثاني. لذلك أضفنا إلى السكربت السطرين اللذين يتحققان بالمقياس λ ويطبعان النسبة بين φ وλ، والدرس العملي أن التحقق الصحيح من مفتاح RSA يكون بـ `e × d mod λ = 1`، وليس بـ φ.

## لماذا يصعب تحليل n؟ نقيس بأنفسنا

كل حماية RSA تقوم على أن استخراج p وq من n صعب، فلنقس هذه الصعوبة بدلاً من أن نصدقها. السكربت `factor_time.py` ينشئ أعداداً بنفس طريقة RSA، أي حاصل ضرب عددين أوليين عشوائيين بنفس الطول، ويبدأ من عددين من 12 بتاً ثم يزيد الطول، ويحلل كل عدد بطريقتين: القسمة التجريبية Trial Division، وهي قسمة n على كل عدد فردي حتى الجذر التربيعي، وخوارزمية Pollard Rho، وهي طريقة أذكى تعتمد على مسألة يوم الميلاد Birthday Problem، حيث تولد سلسلة أرقام شبه عشوائية بالمقياس n، وتنتظر أن يتكرر رقمان بالمقياس p المجهول، فيكشف القاسم المشترك بين فرقهما وn العامل p، وهذا يحدث بعد نحو `√p` خطوة بدلاً من p:

```python
def pollard_rho(n):
    """Pollard's rho with Floyd cycle detection and batched gcd."""
    if n % 2 == 0:
        return 2
    c = 1
    while True:
        x = y = 2
        g, prod, k = 1, 1, 0
        while g == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n
            y = (y * y + c) % n
            prod = prod * abs(x - y) % n
            k += 1
            if k % 128 == 0:
                g = math.gcd(prod, n)
        if g != n:
            return g
        c += 1
```

والمخرج كان كما يلي:

```text
n bits   trial division  pollard rho
    24         0.0003 s     0.0002 s
    31         0.0165 s     0.0002 s
    40         0.3856 s     0.0005 s
    48         2.7044 s     0.0086 s
    56          skipped     0.0058 s
    64          skipped     0.0573 s
    72          skipped     0.3339 s
    80          skipped     0.8063 s
    87          skipped     7.3032 s
```

في المخرج أعلاه لاحظ التالي:

- القسمة التجريبية تضاعف زمنها نحو مرة كل بتين إضافيين في n، لأن عدد القسمات يتناسب مع `√n`، فمن 40 بتاً إلى 48 بتاً قفز الزمن من 0.39 ثانية إلى 2.7 ثانية، ولذلك أوقفناها عند 48 بتاً، فعدد من 64 بتاً كان سوف يأخذ دقائق، ومن 128 بتاً أطول من عمر أي حاسوب.
- Pollard Rho أسرع بكثير لأن خطواته تتناسب مع `n1/4`، فحلل عدداً من 87 بتاً في 7.3 ثانية. ولاحظ أن الأرقام لا تزيد بانتظام، فعدد 56 بتاً أخذ وقتاً أقل من 48 بتاً، والسبب أن هذه الخوارزمية احتمالية، وزمنها يعتمد على متى يحدث التكرار في السلسلة، فقد يأتي مبكراً أو متأخراً.
- ولكن حتى Pollard Rho يتضاعف زمنه نحو مرة كل 4 بتات، فإذا مددت الاتجاه من 87 بتاً إلى 2048 بتاً فأنت تتحدث عن مئات المضاعفات المتتالية، وهو رقم بلا معنى عملي.

والخوارزمية الأسرع المعروفة اليوم للأعداد الكبيرة هي غربال حقل الأعداد العام General Number Field Sieve، وزمنها أسرع من أي أس ثابت مثل `n1/4` وأبطأ من أي كثيرة حدود في عدد البتات، لذلك تحلل أعداداً أكبر بكثير مما رأينا، ولكن بموارد ضخمة. وأشهر إنجاز موثق بها هو [تحليل الرقم RSA-768](https://eprint.iacr.org/2010/006?ref=arabroot.io)، أي عدد من 768 بتاً، الذي نشره فريق من عدة جامعات سنة 2010 بعد عمل على مجموعات كبيرة من الحواسيب، وهذا من أسباب خروج المفاتيح من 1024 بت من الاستخدام، فالفرق بينها وبين 768 بتاً لم يعد هامشاً مريحاً. والصورة التالية ترسم أرقامنا:

![رسم بياني بمقياس لوغاريتمي لزمن تحليل n من 24 إلى 87 بتاً: القسمة التجريبية ترتفع بسرعة حتى 2.7 ثانية عند 48 بتاً، وPollard Rho يبقى تحت ثانية حتى 80 بتاً ثم 7.3 ثانية عند 87 بتاً، ومقارنة بأطوال RSA الحقيقية 768 و2048 و3072 بتاً](https://arabroot.io/content/images/2026/10/crypto-math-rsa-05-factoring.webp)

زمن التحليل الحقيقي في Python: كل بت إضافي في n يرفع التكلفة، و2048 بتاً بعيدة جداً عن هذه الأرقام

وأطوال المفاتيح المقبولة اليوم ليست موضوع هذا المقال، فقد شرحنا جدول NIST وقوة الأمان Security Strength لكل طول في [مقال التشفير للمطورين](https://arabroot.io/articles/%D8%A7%D9%84%D8%AA%D8%B4%D9%81%D9%8A%D8%B1-%D9%84%D9%84%D9%85%D8%B7%D9%88%D8%B1%D9%8A%D9%86-%D8%A7%D9%84%D9%87%D8%A7%D8%B4-%D9%88%D9%83%D9%84%D9%85%D8%A7%D8%AA-%D8%A7%D9%84%D9%85%D8%B1%D9%88%D8%B1-%D9%88%D8%A7%D9%84%D9%85%D9%81%D8%A7%D8%AA%D9%8A%D8%AD/)، والخلاصة منه أن 2048 بتاً تعطي قوة 112 بتاً المقبولة حتى نهاية 2030 بحسب [NIST SP 800-57](https://csrc.nist.gov/pubs/sp/800/57/pt1/r5/final?ref=arabroot.io)، وأن الأنظمة الجديدة تبدأ من 3072 بتاً. ويجب أن تعرف أيضاً أن الحاسوب الكمي الكبير، إذا بني، يستطيع تحليل n بخوارزمية Shor في وقت معقول، وهذا ما يجعل الجهات المعيارية تخطط للانتقال إلى خوارزميات ما بعد الحوسبة الكمية، كما ذكرنا في المقال نفسه.

## RSA المجرد Textbook RSA: ثلاث هجمات لا تحتاج إلى تحليل n

كل ما سبق يعطينا ما يسمى RSA المجرد Textbook RSA، أي المعادلة `c = me mod n` كما هي، وقد يبدو أن الأمان كله في صعوبة التحليل، ولكن الحقيقة أن هذه المعادلة وحدها غير آمنة إطلاقاً حتى مع مفتاح من 4096 بت، لأن المهاجم لا يحتاج إلى استخراج المفتاح، وإنما يستغل خصائص المعادلة نفسها. والسكربت `textbook.py` يجرب ثلاث هجمات على المفتاح الحقيقي، وهذا جزؤه الأول:

```python
n, e, d = load(sys.argv[1])
enc = lambda m: pow(m, e, n)
dec = lambda c: pow(c, d, n)

print("== 1. deterministic: the same message gives the same ciphertext")
yes = int.from_bytes(b"yes", "big")
c1, c2 = enc(yes), enc(yes)
print("c(yes) first :", hex(c1)[:26])
print("c(yes) second:", hex(c2)[:26], "| equal:", c1 == c2)
seen = enc(int.from_bytes(b"no", "big"))  # a ciphertext the attacker intercepted
for guess in (b"yes", b"no"):
    print(f"attacker tries {guess!r}: match = {enc(int.from_bytes(guess, 'big')) == seen}")

print("== 2. malleable: multiply ciphertexts, the plaintexts multiply")
amount = 100
c = enc(amount)
c_forged = c * enc(5) % n  # no private key needed
print("bank decrypts the forged ciphertext:", dec(c_forged))

print("== 3. signatures multiply too")
s1, s2 = pow(6, d, n), pow(7, d, n)
s42 = s1 * s2 % n
print("forged signature of 42 verifies:", pow(s42, e, n) == 42)
s = 123456789  # any number, called a signature
print("existential forgery: s^e mod n is a 'message' signed by s:", hex(pow(s, e, n))[:26], "...")
```

والمخرج سوف يكون كما يلي:

```text
== 1. deterministic: the same message gives the same ciphertext
c(yes) first : 0x9f83bdc85b07c9173424ba9e
c(yes) second: 0x9f83bdc85b07c9173424ba9e | equal: True
attacker tries b'yes': match = False
attacker tries b'no': match = True
== 2. malleable: multiply ciphertexts, the plaintexts multiply
bank decrypts the forged ciphertext: 500
== 3. signatures multiply too
forged signature of 42 verifies: True
existential forgery: s^e mod n is a 'message' signed by s: 0x9ca18af84576aa9a0ac06008 ...
```

### الهجمة الأولى: التشفير الحتمي Deterministic لنفس الرسالة

شفرنا الكلمة `yes` مرتين فحصلنا على نفس الرقم بالضبط، وهذا طبيعي لأن المعادلة لا تحوي أي عنصر عشوائي. والمشكلة أن المفتاح العام متاح للجميع، فإذا كان المهاجم يعرف أن الرسالة واحدة من مجموعة صغيرة، مثل نعم أو لا، أو مبلغ من قائمة، أو رقم هوية من عشرة أرقام، فإنه يشفر كل الاحتمالات بنفسه ويقارنها بالرقم الذي اعترضه، وهذا ما فعله السطران الأخيران: جرب المهاجم `yes` فلم تطابق، ثم جرب `no` فطابقت، فعرف الرسالة دون أن يقترب من المفتاح الخاص. وهذا يخالف الشرط الأول لأي تشفير حديث، وهو أن تشفير نفس الرسالة مرتين يجب أن يعطي نتيجتين مختلفتين.

### الهجمة الثانية: قابلية التلاعب Malleability دون معرفة الرسالة

RSA المجرد له خاصية ضرب: `m1e × m2e = (m1 × m2)e`، فإذا اعترض المهاجم رسالة مشفرة فيها المبلغ 100، وهو لا يعرف أنها 100، فإنه يستطيع أن يضربها في تشفير العدد 5 بالمفتاح العام، فيفك صاحب المفتاح الخاص الرسالة الجديدة فيجد 500، وهذا ما طبعه السطر `bank decrypts the forged ciphertext: 500`. وتسمى هذه الخاصية قابلية التلاعب Malleability، وهي أخطر مما تبدو، لأنها أساس هجمات أكبر سوف نراها مع Bleichenbacher.

### نفس المشكلة في التوقيع الرقمي Digital Signature

التوقيع في RSA المجرد هو العملية المعاكسة: `s = md mod n`، والتحقق `se mod n = m`، ولذلك ينطبق عليه نفس الضرب: من يملك توقيعين لـ 6 و7 يستطيع أن يصنع توقيعاً صالحاً لـ 42 دون المفتاح الخاص، وهذا ما أكده السطر `forged signature of 42 verifies: True`. والسطر الأخير أسوأ، فالمهاجم يختار أي رقم ويسميه توقيعاً، ثم يرفعه إلى e بالمفتاح العام، فيحصل على "رسالة" يتحقق منها هذا التوقيع، وصحيح أن الرسالة هنا أرقام بلا معنى، ولكن هذا كاف ليقول إن التوقيع المجرد لا يثبت شيئاً عن مصدر الرسالة.

### الهجمة الثالثة: e = 3 ورسالة قصيرة

هنا نعود إلى سؤال لماذا لا نستخدم الأس 3\. أنشأ السكربت `run.sh` مفتاحاً ثانياً بالأس العام 3 باستخدام الخيار `rsa_keygen_pubexp:3`، وشفر به الجملة القصيرة `attack at dawn`:

```python
n3, e3, d3 = load(sys.argv[2])
msg = b"attack at dawn"
m = int.from_bytes(msg, "big")
c3 = pow(m, e3, n3)
print("e =", e3, "| m^3 < n:", m ** 3 < n3, "| c == m^3 (no reduction):", c3 == m ** 3)

def icbrt(x):
    lo, hi = 0, 1 << ((x.bit_length() + 2) // 3 + 1)
    while lo < hi:
        mid = (lo + hi) // 2
        if mid ** 3 < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

print("integer cube root of c:", i2b(icbrt(c3)))
```

والمخرج سوف يكون كما يلي:

```text
publicExponent: 3 (0x3)
== 4. e = 3 and a short message: the cube root needs no key
e = 3 | m^3 < n: True | c == m^3 (no reduction): True
integer cube root of c: b'attack at dawn'
```

الجملة 14 بايت، أي عدد من نحو 112 بتاً، ومكعبها من نحو 336 بتاً، وهذا أصغر بكثير من المقياس الذي طوله 2048 بتاً، فلم يحدث أي التفاف حول الساعة، وكان الرقم المشفر هو المكعب العادي للرسالة كما يقول السطر `c == m^3 (no reduction): True`. وبالتالي يكفي حساب الجذر التكعيبي الصحيح بالبحث الثنائي Binary Search لاستعادة الرسالة، دون أي حاجة إلى المفتاح الخاص ولا إلى التحليل. والأس 65537 يمنع هذا الهجوم بالذات، لأن أي رسالة قيمتها 2 أو أكثر تتجاوز المقياس عند رفعها إلى هذا الأس فتلتف حوله، ولكنه لا يعالج المشكلتين الأوليين، فالمعالجة الحقيقية للثلاث هي الحشو.

![ثلاث بطاقات لهجمات RSA المجرد بأرقام التجربة: تشفير yes مرتين يعطي نفس الرقم فيخمن المهاجم no، وضرب تشفير 100 في تشفير 5 يجعل البنك يقرأ 500، ورسالة attack at dawn بالأس 3 تستعاد بالجذر التكعيبي، وفي الأسفل OAEP يعطي رقمين مختلفين لنفس الرسالة](https://arabroot.io/content/images/2026/10/crypto-math-rsa-04-textbook.webp)

RSA المجرد يتنبأ به المهاجم ويتلاعب به، والحشو العشوائي يغلق الثغرات الثلاث

## لماذا يحتاج RSA إلى الحشو Padding؟

الحشو Padding في RSA ليس إضافة أصفار لإكمال الطول كما قد يوحي الاسم، وإنما طريقة لتحويل الرسالة قبل التشفير إلى عدد كبير بحجم المقياس تقريباً، فيه جزء عشوائي وجزء ثابت يتحقق منه الطرف الآخر، وهذا يغلق المشكلات الثلاث: العشوائية تجعل كل تشفير مختلفاً، والحجم الكامل يمنع هجوم الجذر، والبنية التي يتحقق منها فك التشفير تجعل أي تلاعب بالرقم يفسد الرسالة كلها بدلاً من أن يضربها في 5.

### الحشو القديم PKCS#1 v1.5 وهجوم Bleichenbacher

أول حشو انتشر هو PKCS#1 v1.5 للتشفير، وبنيته بسيطة: البايتان `00 02` ثم بايتات عشوائية غير صفرية ثم بايت صفر ثم الرسالة. وكان هذا كافياً لإيقاف الهجمات الثلاث التي رأيناها، إلى أن نشر Daniel Bleichenbacher في مؤتمر CRYPTO سنة 1998 [ورقة تبين أن هذا الحشو قابل للهجوم](https://link.springer.com/chapter/10.1007/BFb0055716?ref=arabroot.io) إذا كان السيرفر يخبرك هل الحشو صحيح أم لا، حتى لو كان ذلك فقط من رسالة خطأ مختلفة أو زمن رد مختلف. والفكرة تستخدم خاصية الضرب نفسها التي رأيناها: يضرب المهاجم الرسالة المشفرة في `se` لأرقام s يختارها، ويرسلها إلى السيرفر، وكل جواب "الحشو صحيح" يخبره أن ناتج `m × s mod n` يبدأ بالبايتين `00 02`، فيضيق المجال الذي فيه m، وبعد عدد كبير من المحاولات يحصل على الرسالة كاملة، وفي TLS القديم كانت هذه الرسالة هي السر الذي تشتق منه مفاتيح الجلسة.

والقصة لم تنته في 1998، ففي سنة 2017 نشر Hanno Böck وJuraj Somorovsky وCraig Young هجوم [ROBOT](https://robotattack.org/?ref=arabroot.io)، واسمه اختصار Return Of Bleichenbacher's Oracle Threat، وبينوا فيه أن تنويعات بسيطة على نفس الهجوم ما زالت تعمل ضد سيرفرات HTTPS تدعم تبادل المفاتيح بـ RSA، ووجدوا تطبيقات معرضة من سبع جهات على الأقل منها F5 وCitrix وCisco، ونطاقات فرعية معرضة في 27 من أكبر 100 نطاق في ذلك الوقت. والدرس هنا أن الحشو القديم لا يحمي إلا إذا كان كل كود يفك التشفير لا يكشف أي معلومة عن صحة الحشو، وهذا صعب جداً في التطبيق، ولذلك أزال TLS 1.3 تبادل المفاتيح بـ RSA كلياً.

### OAEP للتشفير وPSS للتوقيع

الحل الحديث للتشفير هو OAEP، اختصار Optimal Asymmetric Encryption Padding، ويخلط الرسالة مع بذرة عشوائية Seed بدالتي هاش بطريقة تجعل أي تغيير في الرقم المشفر يفسد البنية كلها، وللتوقيع PSS، اختصار Probabilistic Signature Scheme، ويضيف ملحاً Salt عشوائياً إلى هاش الرسالة قبل التوقيع. والمعيار RFC 8017 واضح في ذلك: OAEP مطلوب REQUIRED في التطبيقات الجديدة، وPKCS#1 v1.5 للتشفير موجود فقط للتوافق مع التطبيقات القديمة، ونفس الكلام عن PSS في التوقيع. والجزء التالي من `run.sh` يجرب OAEP وPSS بأوامر OpenSSL، والتوثيق في صفحة [openssl pkeyutl](https://docs.openssl.org/3.5/man1/openssl-pkeyutl/?ref=arabroot.io):

```bash
openssl pkey -in $K/key.pem -pubout -out $K/pub.pem
printf 'yes' > $K/m.txt
for i in 1 2; do
  openssl pkeyutl -encrypt -pubin -inkey $K/pub.pem -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 -in $K/m.txt -out $K/c$i.bin
  echo "OAEP ciphertext $i: $(od -An -tx1 -N12 $K/c$i.bin | tr -d ' \n')..."
done
openssl pkeyutl -decrypt -inkey $K/key.pem -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 -in $K/c1.bin; echo
openssl pkeyutl -decrypt -inkey $K/key3.pem -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 -in $K/c1.bin 2>&1 | head -n 2 || true
echo "-- textbook RSA through openssl (no padding)"
openssl pkeyutl -encrypt -pubin -inkey $K/pub.pem -pkeyopt rsa_padding_mode:none -in $K/m.txt -out $K/raw.bin 2>&1 | head -n 2 || true
for i in 1 2; do
  openssl dgst -sha256 -sign $K/key.pem -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:32 -out $K/s$i.sig $K/m.txt
  echo "PSS signature $i: $(od -An -tx1 -N12 $K/s$i.sig | tr -d ' \n')..."
done
openssl dgst -sha256 -verify $K/pub.pem -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:32 -signature $K/s1.sig $K/m.txt
```

والمخرج سوف يكون كما يلي:

```text
OAEP ciphertext 1: 468462a89e959c9f60544689...
OAEP ciphertext 2: b80dffffdafc97080d63e3a9...
yes
Public Key operation error
40175898007F0000:error:02000079:rsa routines:RSA_padding_check_PKCS1_OAEP_mgf1:oaep decoding error:../crypto/rsa/rsa_oaep.c:332:
-- textbook RSA through openssl (no padding)
Public Key operation error
40278823177F0000:error:0200007A:rsa routines:RSA_padding_add_none:data too small for key size:../crypto/rsa/rsa_none.c:29:
PSS signature 1: b0acc53e9ba924798ae5e8ef...
PSS signature 2: 8562f696f99b276df2fcfb37...
Verified OK
```

في المخرج أعلاه لاحظ التالي:

- نفس الكلمة `yes` بنفس المفتاح أعطت رقمين مختلفين تماماً مع OAEP، فالهجمة الأولى لم تعد ممكنة، فالمهاجم الذي يشفر `yes` بنفسه سوف يحصل على رقم ثالث لا يطابق أياً منهما.
- فك التشفير بالمفتاح الصحيح أعاد `yes`، أما محاولة فكه بالمفتاح الثاني فأعطت `oaep decoding error`، لأن الرقم الناتج لم يحمل بنية OAEP، وهذا ما يحدث أيضاً لو غير المهاجم بتاً واحداً في الرقم المشفر أو ضربه في `5e`.
- توقيعا PSS لنفس الرسالة مختلفان بسبب الملح العشوائي، وكلاهما صالح، والسطر `Verified OK` يؤكد التحقق من الأول بالمفتاح العام.

وقد يتساءل البعض: هل يرفض OAEP فعلاً حيلة الضرب التي جعلت البنك يقرأ 500؟ لنجربها مباشرة على رقم مشفر بـ OAEP. السكربت `tamper.sh` ينشئ مفتاحاً جديداً، ويشفر النص `amount=100` بـ OAEP، ثم يصنع نسختين معدلتين من الرقم المشفر: الأولى مضروبة في `5e mod n` كما فعل المهاجم في RSA المجرد، والثانية بتغيير بت واحد في آخرها، ثم يحاول فك الثلاثة:

```bash
docker run --rm --name scm-rsa-tamper -v "$PWD:/lab:ro" -w /lab python:3.13.17-slim sh tamper.sh
```

والمخرج سوف يكون كما يلي:

```text
wrote c5.bin (c * 5^e mod n) and c1bit.bin (last bit flipped)
-- original
amount=100
-- multiplied by 5^e
40F757AFC07F0000:error:02000079:rsa routines:RSA_padding_check_PKCS1_OAEP_mgf1:oaep decoding error:../crypto/rsa/rsa_oaep.c:332:
-- one bit flipped
40575818E57F0000:error:02000079:rsa routines:RSA_padding_check_PKCS1_OAEP_mgf1:oaep decoding error:../crypto/rsa/rsa_oaep.c:332:
```

الرقم الأصلي عاد إلى `amount=100`، أما النسختان المعدلتان فرفضهما OpenSSL بنفس الخطأ `oaep decoding error`. والسبب أن ضرب الرقم المشفر ما زال يضرب الرسالة المحشوة في 5 كما في الرياضيات، ولكن ناتج الضرب لم يعد يحمل البنية التي يتحقق منها OAEP بعد فك التشفير، فيرفضه بدلاً من أن يعيد رسالة معدلة. ولاحظ أن الخطأ واحد في الحالتين، وهذا مقصود، فالرسالة المختلفة لكل نوع من الأخطاء هي بالضبط ما استغله Bleichenbacher في الحشو القديم.

أما السطران اللذان تحت `textbook RSA through openssl` فكانا مشكلة حقيقية واجهناها: أردنا أن نجرب RSA المجرد بأمر OpenSSL مباشرة بالخيار `rsa_padding_mode:none`، فرفض الأمر بالخطأ `data too small for key size`. والسبب أن OpenSSL في وضع عدم الحشو يشترط أن تكون الرسالة بنفس طول المقياس بالضبط، أي 256 بايتاً لمفتاح من 2048 بت، وليس 3 بايتات، فهو لا يضيف أي شيء من عنده ولا يقبل رسالة قصيرة. وكان أمامنا خياران: أن نصنع ملفاً من 256 بايتاً بأصفار في أوله، أو أن نجري RSA المجرد في Python كما فعلنا في `textbook.py`، واخترنا الثاني لأنه يبين المعادلة بوضوح، وأبقينا الخطأ في التجربة لأنه رسالة مفيدة: إذا رأيت `rsa_padding_mode:none` في كود إنتاج فتوقف عنده، لأن من كتبه غالباً يبني حشوه بنفسه أو لا يحشو أصلاً.

## ماذا يحدث إذا…؟ مفاتيح تبدو سليمة وتكشف أسرارها

كل ما سبق يفترض أن p وq اختيرا بشكل صحيح، فماذا يحدث إذا لم يكونا كذلك، مع أن المفتاح يبدو طبيعياً تماماً بطول 2048 بت؟ جربنا حالتين حدثتا فعلاً على الانترنت في السكربت `weak_keys.py`:

```python
print("== 1. two 2048-bit keys that share one prime (bad randomness at boot)")
shared = rand_prime(1024)
n1 = shared * rand_prime(1024)
n2 = shared * rand_prime(1024)
t0 = time.perf_counter()
g = math.gcd(n1, n2)
print(f"gcd(n1, n2) has {g.bit_length()} bits, equals the shared prime: {g == shared}, "
      f"time {(time.perf_counter() - t0) * 1000:.3f} ms")
print("n1 factored:", n1 == g * (n1 // g), "| n2 factored:", n2 == g * (n2 // g))

print("== 2. p and q too close to each other: Fermat's method")
p = rand_prime(1024)
q = next_prime(p + 2)
n = p * q
print("q - p =", q - p, "| n bits:", n.bit_length())
t0 = time.perf_counter()
a = math.isqrt(n)
if a * a < n:
    a += 1
steps = 0
while True:
    b2 = a * a - n
    b = math.isqrt(b2)
    steps += 1
    if b * b == b2:
        break
    a += 1
print(f"Fermat found p and q after {steps} step(s) in {(time.perf_counter() - t0) * 1000:.3f} ms:",
      {a - b, a + b} == {p, q})
```

والمخرج سوف يكون كما يلي:

```text
== 1. two 2048-bit keys that share one prime (bad randomness at boot)
gcd(n1, n2) has 1024 bits, equals the shared prime: True, time 0.077 ms
n1 factored: True | n2 factored: True
== 2. p and q too close to each other: Fermat's method
q - p = 550 | n bits: 2048
Fermat found p and q after 1 step(s) in 0.084 ms: True
```

### الحالة الأولى: عامل أولي مشترك Shared Prime بين مفتاحين

مفتاحان من 2048 بت، كل منهما سليم إذا نظرت إليه وحده، ولكنهما يشتركان في عدد أولي واحد، فحساب القاسم المشترك الأكبر بخوارزمية إقليدس، التي شرحناها في بداية المقال، أعطى العدد المشترك في 0.077 مللي ثانية، ومنه حللنا المفتاحين معاً. وهذا ليس افتراضاً نظرياً، ففي سنة 2012 جمع فريق من الباحثين المفاتيح العامة لملايين السيرفرات على الانترنت، وحسبوا القاسم المشترك بين كل زوج منها، ونشروا النتيجة في [بحث Mining Your Ps and Qs](https://factorable.net/?ref=arabroot.io): استطاعوا استخراج المفاتيح الخاصة لـ 0.50% من سيرفرات TLS و0.03% من سيرفرات SSH، وكان السبب أجهزة مدمجة مثل الراوترات تنشئ مفاتيحها عند أول تشغيل قبل أن يجمع نظام التشغيل عشوائية كافية، فتختار أجهزة كثيرة نفس العدد الأولي الأول ثم تختلف في الثاني. والدرس أن جودة المولد العشوائي جزء من الرياضيات نفسها، وقد شرحنا في [مقال التشفير للمطورين](https://arabroot.io/articles/%D8%A7%D9%84%D8%AA%D8%B4%D9%81%D9%8A%D8%B1-%D9%84%D9%84%D9%85%D8%B7%D9%88%D8%B1%D9%8A%D9%86-%D8%A7%D9%84%D9%87%D8%A7%D8%B4-%D9%88%D9%83%D9%84%D9%85%D8%A7%D8%AA-%D8%A7%D9%84%D9%85%D8%B1%D9%88%D8%B1-%D9%88%D8%A7%D9%84%D9%85%D9%81%D8%A7%D8%AA%D9%8A%D8%AD/) الفرق بين المولد العادي والمولد الآمن تشفيرياً CSPRNG.

### الحالة الثانية: عددان أوليان متقاربان وتحليل فيرما Fermat Factorization

في الحالة الثانية اختار السكربت q كأول عدد أولي بعد p، فكان الفرق بينهما 550 فقط، والمقياس من 2048 بت كما هو مطلوب. وطريقة فيرما للتحليل تكتب n كفرق بين مربعين `n = a2 − b2 = (a − b)(a + b)`، حيث a هو منتصف المسافة بين p وq، وإذا كان العددان متقاربين فإن a قريب جداً من الجذر التربيعي لـ n، فتبدأ من الجذر وتزيد واحداً حتى يصبح `a2 − n` مربعاً كاملاً، وهنا وجدته في خطوة واحدة وفي 0.084 مللي ثانية. وهذا أيضاً حدث فعلاً، ففي سنة 2022 طبق Hanno Böck [طريقة فيرما على مجموعات كبيرة من المفاتيح العامة](https://fermatattack.secvuln.info/?ref=arabroot.io) ووجد مفاتيح معرضة تنشئها طابعات من Canon وFujifilm، وسجلت الثغرة باسم [CVE-2022-26320](https://nvd.nist.gov/vuln/detail/CVE-2022-26320?ref=arabroot.io) في وحدة التشفير التي تستخدمها هذه الأجهزة. ولهذا السبب يشترط المعيار FIPS 186-5 أن يكون الفرق بين p وq أكبر من `2nlen/2 − 100`، أي أن تختلف البتات المئة الأولى من العددين على الأقل.

![حالتان لمفاتيح ضعيفة: سيرفران يشتركان في العدد الأولي p فيكشفه القاسم المشترك الأكبر في 0.077 مللي ثانية، مع نتيجة بحث 2012 أن 0.50% من سيرفرات TLS تأثرت، وعددان أوليان الفرق بينهما 550 فتجدهما طريقة فيرما في خطوة واحدة، مع ثغرة طابعات Canon وFujifilm سنة 2022](https://arabroot.io/content/images/2026/10/crypto-math-rsa-06-weak-keys.webp)

مفتاحان من 2048 بت يبدوان سليمين، وكل منهما يتحلل في أقل من مللي ثانية

وقد يتساءل البعض: هل أحتاج إلى فحص مفاتيحي بهذه الطرق؟ والإجابة أن المفتاح الذي تنشئه بأداة حديثة مثل OpenSSL على نظام تشغيل عادي سليم من الحالتين في الغالب، لأن OpenSSL يأخذ العشوائية من نظام التشغيل، وقد رأينا في التجربة أنه يحسب d بالطريقة التي يشترطها المعيار، والخطر الحقيقي في الأجهزة المدمجة والأنظمة التي تنشئ مفاتيحها في أول ثانية من التشغيل، وفي أي كود يولد المفاتيح بنفسه، وفي المفاتيح القديمة التي أنشئت بأدوات فيها ثغرات معروفة، وهذه تفحصها بأدوات مخصصة لفحص المفاتيح المعروفة بضعفها مثل مشروع badkeys الذي ذكره نفس الباحث.

## أخطاء شائعة

1. **كتابة RSA بنفسك:** المعادلة سهلة كما رأيت، ولهذا يغري كتابتها، ولكن كل ما يجعلها آمنة موجود خارجها: الحشو، والزمن الثابت، وال Blinding، وفحص المدخلات، فاستخدم مكتبة معروفة دائماً واجعل تجارب هذا المقال للفهم فقط.
2. **استخدام `%` في لغة غير Python مع أرقام قد تكون سالبة:** النتيجة السالبة لا تعطي خطأً، وإنما مفتاحاً أو حساباً خاطئاً بصمت، فأضف المقياس ثم خذ الباقي، أو استخدم دوال الأعداد الكبيرة في لغتك مثل `BigInteger.mod` في Java التي تعيد قيمة موجبة دائماً.
3. **التحقق من المفتاح بـ φ بدلاً من λ:** كما رأينا في المشكلة التي واجهناها، OpenSSL والمعيار يحسبان d بالمقياس λ، فإذا كتبت فحصاً لمفاتيح مستوردة بـ φ فسوف يرفض نصف المفاتيح السليمة تقريباً.
4. **التشفير بدون حشو أو بالحشو القديم:** `rsa_padding_mode:none` أو PKCS#1 v1.5 للتشفير في كود جديد، والصحيح OAEP مع SHA-256، وPSS للتوقيع.
5. **رسائل خطأ مختلفة عند فشل فك التشفير:** هذا ما يحول السيرفر إلى أداة لهجوم Bleichenbacher، فاجعل كل فشل في فك التشفير يعطي نفس الرد ونفس الزمن، ويفضل ألا تفك تشفير RSA على طلب من المستخدم أصلاً.
6. **توليد المفاتيح في أول تشغيل لجهاز مدمج:** قبل أن يجمع النظام عشوائية كافية، وهي الحالة التي كشفها بحث 2012، فأنشئ المفتاح بعد أن يصبح مصدر العشوائية جاهزاً، أو في المصنع بمولد موثوق.
7. **اختيار e صغير مثل 3:** لا يضيف سرعة تذكر على 65537، ويفتح هجوم الجذر إذا فشل الحشو، ولا يقبله FIPS 186-5.
8. **الظن أن 2048 بت كافية إلى الأبد:** طول المفتاح قرار له تاريخ صلاحية، وقد شرحنا الجدول الزمني في مقال التشفير للمطورين.

## قائمة تحقق Checklist وجدول قرار Decision Table

الجدول التالي يجمع الأسئلة التي تظهر عملياً عندما تتعامل مع RSA، والجواب المختصر لكل منها:

| الموقف                                        | القرار                                                                          | والسبب                                                  |
| --------------------------------------------- | ------------------------------------------------------------------------------- | ------------------------------------------------------- |
| تحتاج إلى تشفير بيانات قصيرة بمفتاح عام       | RSA-OAEP مع SHA-256 من مكتبة معروفة                                             | العشوائية والبنية تمنعان التخمين والتلاعب               |
| تحتاج إلى تشفير ملف أو بيانات كبيرة           | شفر البيانات بمفتاح متماثل، وشفر المفتاح المتماثل بـ RSA-OAEP                   | RSA يشفر أقل من طول المقياس، وهو أبطأ بكثير             |
| تحتاج إلى توقيع                               | RSA-PSS، أو Ed25519 إذا لم يفرض عليك RSA                                        | PSS عشوائي وله إثبات أمني، والتوقيع المجرد قابل للتزوير |
| تراجع كوداً قديماً يستخدم PKCS#1 v1.5 للتشفير | خطط للانتقال إلى OAEP، وتأكد أن الأخطاء لا تكشف صحة الحشو                       | Bleichenbacher وROBOT                                   |
| تستورد مفاتيح من مصدر خارجي                   | تحقق من n = p × q وe × d mod λ = 1 وطول n والأس العام                           | هذه الشروط التي يطبقها المعيار                          |
| تولد مفاتيح على جهاز مدمج                     | انتظر جاهزية مصدر العشوائية، وافحص المفاتيح المنشأة بأدوات فحص المفاتيح الضعيفة | العوامل المشتركة والأعداد المتقاربة                     |
| تحتاج إلى طول مفتاح لنظام جديد                | 3072 بتاً على الأقل                                                             | 2048 بت مقبولة حتى نهاية 2030 فقط                       |

وقبل أن تعتمد أي كود يتعامل مع RSA، مر على النقاط التالية:

- لا توجد عملية `pow` مكتوبة يدوياً على المفتاح الخاص في كود الإنتاج.
- الحشو محدد صراحة: OAEP للتشفير وPSS للتوقيع، ودالة الهاش SHA-256 أو أقوى.
- الأس العام 65537، وطول المقياس 3072 بتاً للأنظمة الجديدة.
- كل فشل في فك التشفير يعطي نفس الرسالة ونفس الزمن.
- مخرج `openssl pkey -text` لا يظهر في السجلات أو التذاكر.
- المفاتيح تنشأ بأداة معروفة على نظام فيه مصدر عشوائية جاهز.

## تدريب عملي

- ابن مفتاحاً صغيراً بالعددين 47 و59 والأس العام 17 كما في ورقة 1978، واحسب d بجدول إقليدس بيدك، ثم قارنه بـ 157 وبـ `pow(17, -1, lcm(46, 58))`، وفسر لماذا يختلفان.
- عدل `trace_pow` لتحسب عدد العمليات فقط دون طباعة، ثم مررها على 65537 وعلى أس خاص من مفتاح حقيقي، وتحقق من قاعدة "عدد البتات ناقص واحد زائد عدد الآحاد".
- في `textbook.py`، اختر رسالة من 100 بايت وشفرها بالمفتاح الذي أسه 3، ثم جرب الجذر التكعيبي، وفسر لماذا فشل هذه المرة.
- غير `next_prime(p + 2)` في `weak_keys.py` إلى `next_prime(p + 2**600)`، وراقب عدد خطوات طريقة فيرما، ثم قارن الفرق بشرط FIPS 186-5.

## الخلاصة

وصلنا لنهاية الموضوع، وأهم ما فيه:

- RSA معادلة واحدة: `c = me mod n` و`m = cd mod n`، وتعمل بسبب مبرهنة أويلر لأن `e × d ≡ 1` بالمقياس λ أو φ.
- الأدوات خمس: الأعداد الأولية، والحساب المعياري، وخوارزمية إقليدس الموسعة، والمعكوس المعياري، ومبرهنة أويلر، وكلها سريعة لمن يعرف p وq، والباب الخلفي هو φ.
- الأس السريع يحول الأس المستحيل إلى نحو ثلاثة آلاف عملية لمفتاح 2048 بت، و65537 يجعل العمليات العامة 18 عملية فقط.
- Miller-Rabin يجد الأعداد الأولية الكبيرة بثقة عالية، بينما يخدعك اختبار فيرما مع أعداد كارمايكل مثل 561.
- ملف مفتاح OpenSSL يحفظ n وe وd وp وq وdP وdQ وqInv، والخمسة الأخيرة لتسريع فك التشفير بمبرهنة الباقي الصيني، وأي واحد من p أو q يكشف المفتاح كله.
- OpenSSL يحسب d بالمقياس λ كما يشترط FIPS 186-5، فتحقق من المفاتيح بـ λ.
- التحليل يزداد صعوبة بسرعة كبيرة مع طول n، ولكن RSA المجرد يسقط دون أي تحليل: ثابت وقابل للتلاعب وقابل للجذر مع e صغير، والحشو OAEP وPSS هو ما يجعله آمناً.
- مفتاح يبدو سليماً قد يكون ضعيفاً إذا شارك عدداً أولياً مع مفتاح آخر أو كان عدداه متقاربين، والسبب غالباً عشوائية ضعيفة أو مولد مفاتيح خاطئ.

وفي مرحلة [الرياضيات التي يحتاجها المبرمج فعلاً](https://arabroot.io/start/#stage-cs-math) يأتي هذا المقال بعد مقالي [الإحصاء للتقنيين](https://arabroot.io/articles/%D8%A7%D9%84%D8%A7%D8%AD%D8%B5%D8%A7%D8%A1-%D9%84%D9%84%D9%85%D9%87%D9%86%D8%AF%D8%B3%D9%8A%D9%86-%D8%A7%D9%84%D9%85%D8%AA%D9%88%D8%B3%D8%B7-%D9%88%D8%A7%D9%84%D9%88%D8%B3%D9%8A%D8%B7-%D9%88%D8%A7%D9%84%D9%85%D8%A6%D9%8A%D9%86-p99/) و[الاحتمالات للمبرمجين](https://arabroot.io/articles/%D8%A7%D9%84%D8%A7%D8%AD%D8%AA%D9%85%D8%A7%D9%84%D8%A7%D8%AA-%D9%84%D9%84%D9%85%D8%A8%D8%B1%D9%85%D8%AC%D9%8A%D9%86-%D8%AA%D8%B5%D8%A7%D8%AF%D9%85-%D8%A7%D9%84%D9%85%D8%B9%D8%B1%D9%81%D8%A7%D8%AA-%D9%88%D8%A7%D9%84%D9%87%D8%A7%D8%B4-%D9%88%D8%AA%D9%88%D9%81%D8%B1-%D8%A7%D9%84%D8%A7%D9%86%D8%B8%D9%85%D8%A9/)، وفي الثاني تجد مسألة يوم الميلاد التي استخدمتها Pollard Rho هنا. وهذه المقالات المنشورة التي يعتمد عليها هذا المقال أو يكملها:

[![](https://arabroot.io/content/images/2026/10/crypto-for-devs-cover-cover.webp)دليلالتشفير للمطورين: ماذا تستخدم ولماذا لا تخترع خوارزميتكأي هاش تستخدم لكلمات المرور، ومتى تحتاج التشفير المتماثل أو غير المتماثل، وأين تحفظ المفاتيح بأمان في تطبيقك.](https://arabroot.io/articles/%D8%A7%D9%84%D8%AA%D8%B4%D9%81%D9%8A%D8%B1-%D9%84%D9%84%D9%85%D8%B7%D9%88%D8%B1%D9%8A%D9%86-%D8%A7%D9%84%D9%87%D8%A7%D8%B4-%D9%88%D9%83%D9%84%D9%85%D8%A7%D8%AA-%D8%A7%D9%84%D9%85%D8%B1%D9%88%D8%B1-%D9%88%D8%A7%D9%84%D9%85%D9%81%D8%A7%D8%AA%D9%8A%D8%AD/)[![](https://arabroot.io/content/images/2026/10/certificates-cover-cover.webp)دليلالشهادات الرقمية TLS للمبتدئين وصيغ ملفاتهاكيف يعرف المتصفح أنه يتحدث مع الموقع الحقيقي، وماذا يوجد داخل الشهادة، ولماذا تأتي ملفاتها بأكثر من صيغة.](https://arabroot.io/articles/%D8%A7%D9%84%D8%B4%D9%87%D8%A7%D8%AF%D8%A7%D8%AA-%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A%D8%A9-tls-%D9%88-x509-%D9%88%D8%B5%D9%8A%D8%BA-pem-%D9%88-der/)[![](https://arabroot.io/content/images/2026/10/number-systems-cover-cover.webp)دليلالأنظمة العددية للمبرمجين: من Binary إلى Floating Pointلماذا يظهر القرص 465 بدل 500، ويصبح العداد سالباً فجأة، ولا يساوي 0.1 + 0.2 القيمة 0.3؟ الإجابة في طريقة تخزين الأرقام.](https://arabroot.io/articles/%D8%A7%D9%84%D8%A7%D9%86%D8%B8%D9%85%D8%A9-%D8%A7%D9%84%D8%B9%D8%AF%D8%AF%D9%8A%D8%A9-%D9%88%D8%A7%D9%84%D8%AB%D9%86%D8%A7%D8%A6%D9%8A-%D9%84%D9%84%D9%85%D8%A8%D8%B1%D9%85%D8%AC%D9%8A%D9%86/)[![](https://arabroot.io/content/images/2026/10/floating-point-cover-cover.webp)دليلFloating Point من الداخل: كيف يخزن الحاسب الكسوركيف يحفظ معيار IEEE 754 الكسور في البتات، ولماذا تكبر الفجوة بين الأرقام وتضيع خانات المعرفات، ومتى تحتاج النوع العشري.](https://arabroot.io/articles/%D8%A7%D9%84%D8%A3%D8%B1%D9%82%D8%A7%D9%85-%D8%A7%D9%84%D8%B9%D8%B4%D8%B1%D9%8A%D8%A9-floating-point-%D9%85%D9%86-%D8%A7%D9%84%D8%AF%D8%A7%D8%AE%D9%84/)[![](https://arabroot.io/content/images/2026/10/unique-ids-cover-cover.webp)دليلالرقم المتسلسل أم UUID؟ كيف تختار المعرف الفريدلماذا يفشل الرقم المتسلسل في الروابط وعند تعدد السيرفرات، وكيف يؤثر نوع المعرف الذي تختاره على فهرس قاعدة البيانات.](https://arabroot.io/articles/%D8%A7%D9%84%D9%85%D8%B9%D8%B1%D9%81%D8%A7%D8%AA-%D8%A7%D9%84%D9%81%D8%B1%D9%8A%D8%AF%D8%A9-uuid-%D9%88-ulid-%D9%88-snowflake/)

## سجل التحديثات

- أكتوبر 2026: كتابة المقال، وتنفيذ التجربة في Container من `python:3.13.17-slim` مع Python 3.13.17 وOpenSSL 3.5.7، ومثال المعامل `%` في Node.js 22.