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

يتم توليد مفاتيح نظام التشفير رابين على النحو التالي:

1. اختر عددين أوليين كبيرين مختلفين${\displaystyle p}$و${\displaystyle q}$بحيث${\displaystyle p\equiv 3{\bmod {4}}}$و${\displaystyle q\equiv 3{\bmod {4}}}$.
2. الحوسبة${\displaystyle n=pq}$.

ثم${\displaystyle n}$المفتاح العام والزوج${\displaystyle (p,q)}$هو المفتاح الخاص.

رسالة${\displaystyle M}$يمكن تشفيرها عن طريق تحويلها أولاً إلى رقم${\displaystyle m<n}$باستخدام عملية تحويل قابلة للعكس، ثم الحساب${\displaystyle c=m^{2}{\bmod {n}}}$النص المشفر هو${\displaystyle c}$.

الرسائل${\displaystyle m}$يمكن استعادتها من النص المشفر${\displaystyle c}$بأخذ الجذر التربيعي باقي القسمة${\displaystyle n}$على النحو التالي.

1. احسب الجذر التربيعي لـ${\displaystyle c}$modulo${\displaystyle p}$و${\displaystyle q}$باستخدام هذه الصيغ:

   ${\displaystyle {\begin{aligned}m_{p}&=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}\\m_{q}&=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}\end{محاذاة}}}$

2. استخدم خوارزمية إقليدس الموسعة لإيجاد${\displaystyle y_{p}}$و${\displaystyle y_{q}}$بحيث${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$.
3. استخدم نظرية الباقي الصينية لإيجاد الجذور التربيعية الأربعة لـ${\displaystyle c}$modulo${\displaystyle n}$:

   ${\displaystyle {\begin{aligned}r_{1}&=\left(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{2}&=n-r_{1}\\r_{3}&=\left(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{4}&=n-r_{3}\end{aligned}}}$

إحدى هذه القيم الأربع هي النص الأصلي${\displaystyle m}$، على الرغم من أنه لا يمكن تحديد أي من الخيارات الأربعة هو الصحيح بدون معلومات إضافية.

على سبيل المثال، خذ${\displaystyle p=7}$و${\displaystyle q=11}$، ثم${\displaystyle n=77}$. يأخذ${\displaystyle m=20}$كنصنا الأصلي. وبالتالي، يكون النص المشفر ${\displaystyle c=m^{2}{\bmod {n}}=400{\bmod {77}}=15}$.

تتم عملية فك التشفير على النحو التالي:

1. الحوسبة${\displaystyle m_{p}=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}=15^{2}{\bmod {7}}=1}$و${\displaystyle m_{q}=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}=15^{3}{\bmod {11}}=9}$.
2. استخدم خوارزمية إقليدس الموسعة للحساب${\displaystyle y_{p}=-3}$و${\displaystyle y_{q}=2}$يمكننا التأكيد على ذلك${\displaystyle y_{p}\cdot p+y_{q}\cdot q=(-3\cdot 7)+(2\cdot 11)=1}$.
3. احسب المرشحين الأربعة للنص الأصلي:

   ${\displaystyle {\begin{aligned}r_{1}&=(-3\cdot 7\cdot 9+2\cdot 11\cdot 1){\bmod {77}}=64\\r_{2}&=77-64=13\\r_{3}&=(-3\cdot 7\cdot 9-2\cdot 11\cdot 1){\bmod {77}}=\mathbf {20} \\r_{4}&=77-20=57\end{aligned}}}$

ونرى ذلك${\displaystyle r_{3}}$النص الأصلي المطلوب. لاحظ أن جميع المرشحين الأربعة هي جذور تربيعية للعدد 15 بتردد 77. أي، بالنسبة لكل مرشح،${\displaystyle r_{i}^{2}{\bmod {77}}=15}$لذلك كل${\displaystyle r_{i}}$يتم التشفير إلى نفس القيمة، 15.

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

إذا كان النص الأصلي يُمثل رسالة نصية، فإن التخمين ليس صعبًا؛ أما إذا كان يُمثل قيمة عددية، فإن هذه المسألة تُصبح مشكلةً يجب حلها باستخدام آليةٍ ما لإزالة الغموض. يُمكن اختيار نصوص أصلية ذات بنى خاصة، أو إضافة حشو ، للتخلص من هذه المشكلة. وقد اقترح بلوم وويليامز طريقةً لإزالة غموض الانعكاس: حيث يقتصر العددان الأوليان المستخدمان على الأعداد الأولية المتطابقة مع 3 بتردد 4، ويقتصر نطاق التربيع على مجموعة البواقي التربيعية. هذه القيود تجعل دالة التربيع تبديلًا ذا بابٍ خلفي ، مما يُزيل الغموض. ^{[ 8 ]}

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

لفك التشفير، يتم تطبيق نظرية الباقي الصينية ، بالإضافة إلى عمليتي رفع أسّ معياريتين . وتكون الكفاءة هنا مماثلة لكفاءة RSA.

لقد ثبت أنه يمكن استخدام أي خوارزمية تجد أحد النصوص الأصلية المحتملة لكل نص مشفر مشفر باستخدام خوارزمية رابين لتحليل المعامل.${\displaystyle n}$وبالتالي، فإن فك تشفير رابين لنص عادي عشوائي لا يقل صعوبة عن مشكلة تحليل الأعداد الصحيحة إلى عواملها الأولية، وهو أمر لم يُثبت بعد بالنسبة لخوارزمية RSA. ويُعتقد عمومًا أنه لا توجد خوارزمية ذات زمن متعدد الحدود لتحليل الأعداد إلى عواملها الأولية، مما يعني أنه لا توجد خوارزمية فعالة لفك تشفير قيمة مشفرة باستخدام رابين عشوائيًا دون المفتاح الخاص.${\displaystyle (p,q)}$.

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

يُعد نظام رابين للتشفير غير آمن ضد هجوم النص المشفر المُختار (حتى عند اختيار رسائل التحدي عشوائيًا وبشكل متساوٍ من فضاء الرسائل). ^{[ 6 ] : 214.} بإضافة تكرارات، مثل تكرار آخر 64 بت، يمكن جعل النظام يُنتج جذرًا واحدًا. هذا يُحبط هجوم النص المشفر المُختار هذا تحديدًا، لأن خوارزمية فك التشفير تُنتج حينها الجذر الذي يعرفه المهاجم مُسبقًا فقط. إذا طُبقت هذه التقنية، يفشل إثبات التكافؤ مع مسألة التحليل إلى عوامل، لذا فإنه من غير المؤكد حتى عام 2004 ما إذا كان هذا المتغير آمنًا. مع ذلك، يعتبر كتاب "دليل التشفير التطبيقي" لمينيزيس وأورشوت وفانستون هذا التكافؤ مُحتملًا، طالما أن إيجاد الجذور يظل عملية من جزأين (1. الجذور).${\displaystyle {\bmod {p}}}$و${\displaystyle {\bmod {q}}}$و2. تطبيق نظرية الباقي الصينية).