نظام التشفير ناكاش-ستيرن

• اختر عائلة من k أعداد أولية صغيرة ومختلفة p ₁ ,..., p _k .
• قسّم المجموعة إلى نصفين وحدد${\displaystyle u=\prod _{i=1}^{k/2}p_{i}}$و${\displaystyle v=\prod _{k/2+1}^{k}p_{i}}$.
• تعيين${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i}}$
• اختر عددين أوليين كبيرين a و b بحيث يكون كل من p = 2 au +1 و q =2 bv +1 أوليين.
• اجعل n = pq .
• اختر قيمة عشوائية g mod n بحيث يكون ترتيب g هو φ( n )/4.

المفتاح العام هو الأرقام (σ، n ، g ) والمفتاح الخاص هو الزوج ( p ، q ).

تُعتبر الأعداد الأولية (p1 _, ..., pk ₎ عامة فعليًا، إذ يُمكن استعادتها بكفاءة من القيمة العامة σ = Πpi، بشرط أن تكون صغيرة. وتُستخدم هذه الأعداد الأولية أثناء فك التشفير، حيث تُجرى العمليات الحسابية بتردد كل pi _{لاستعادة} الرسالة.

عندما k = 1، يكون هذا في الأساس نظام التشفير Benaloh .

يسمح هذا النظام بتشفير رسالة m في المجموعة${\displaystyle \mathbb {Z} /\sigma \mathbb {Z} }$.

• اختر عشوائياً${\displaystyle x\in \mathbb {Z} /n\mathbb {Z} }$.
• احسب${\displaystyle E(m)=x^{\sigma }g^{m}\mod n}$

إذن E(m) هو تشفير للرسالة m .

لفك التشفير، نجد أولاً m mod p _i لكل i ، ثم نطبق نظرية الباقي الصينية لحساب m mod${\displaystyle \sigma }$.

بفرض وجود نص مشفر c ، لفك تشفيره، نقوم بحساب

• ${\displaystyle c_{i}\equiv c^{\phi (n)/p_{i}}\mod n}$. هكذا

${\displaystyle {\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}}$

أين${\displaystyle m_{i}\equiv m\mod p_{i}}$.

• بما أن _قيمة pᵢ مختارة لتكون صغيرة، _فإنه يمكن استعادة mᵢ عن طريق البحث الشامل، أي عن طريق المقارنة${\displaystyle c_{i}}$ل${\displaystyle g^{j\phi (n)/p_{i}}}$لكل j من 1 إلى p _i -1.
• بمجرد معرفة قيمة m _i لكل i ، يمكن استعادة m من خلال تطبيق مباشر لنظرية الباقي الصينية.