تشفير ElGamal

يقوم الطرف الأول، أليس، بإنشاء زوج من المفاتيح على النحو التالي:

• قم بإنشاء وصف فعال لمجموعة حلقية${\displaystyle G\,}$من النظام${\displaystyle q\,}$مع مولد كهربائي${\displaystyle g}$. يترك${\displaystyle e}$يمثل عنصر الهوية لـ${\displaystyle G}$.

  ليس من الضروري إنشاء مجموعة ومولد لكل مفتاح جديد. في الواقع، قد يتوقع المرء أن يكون تطبيق ElGamal مُبرمجًا مسبقًا لاستخدام مجموعة معينة، أو مجموعة من حزمة معينة. يعتمد اختيار المجموعة في الغالب على حجم المفاتيح التي ترغب في استخدامها.

• اختر عددًا صحيحًا${\displaystyle x}$عشوائياً من${\displaystyle \{1,\ldots ,q-1\}}$.
• الحوسبة${\displaystyle h:=g^{x}}$.
• يتكون المفتاح العام من القيم${\displaystyle (G,q,g,h)}$تنشر أليس هذا المفتاح العام وتحتفظ به${\displaystyle x}$باعتبارها مفتاحها الخاص، والذي يجب أن يبقى سراً.

يقوم طرف ثانٍ، يُدعى بوب، بتشفير رسالة${\displaystyle M}$إلى أليس تحت مفتاحها العام${\displaystyle (G,q,g,h)}$على النحو التالي:

• قم بتصنيف الرسائل${\displaystyle M}$إلى عنصر${\displaystyle m}$ل${\displaystyle G}$باستخدام دالة تعيين قابلة للعكس.
• اختر عددًا صحيحًا${\displaystyle y}$عشوائياً من${\displaystyle \{1,\ldots ,q-1\}}$.
• الحوسبة${\displaystyle s:=h^{y}}$يُطلق على هذا اسم السر المشترك .
• الحوسبة${\displaystyle c_{1}:=g^{y}}$.
• الحوسبة${\displaystyle c_{2}:=m\cdot s}$.
• بوب يرسل النص المشفر${\displaystyle (c_{1},c_{2})}$إلى أليس.

لاحظ أنه إذا كان المرء يعرف النص المشفر${\displaystyle (c_{1},c_{2})}$والنص الأصلي${\displaystyle m}$يمكن للمرء بسهولة العثور على السر المشترك${\displaystyle s}$، منذ${\displaystyle c_{2}\cdot m^{-1}=s}$لذلك، جديد${\displaystyle y}$وبالتالي جديد${\displaystyle s}$يتم إنشاء هذا الإجراء لكل رسالة لتحسين الأمان. ولهذا السبب،${\displaystyle y}$ويُطلق عليه أيضاً اسم المفتاح المؤقت .

أليس تفك شفرة نص مشفر${\displaystyle (c_{1},c_{2})}$بمفتاحها الخاص${\displaystyle x}$على النحو التالي:

• الحوسبة${\displaystyle s:=c_{1}^{x}}$. منذ${\displaystyle c_{1}=g^{y}}$،${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$وبالتالي فهو نفس السر المشترك الذي استخدمه بوب في التشفير.
• الحوسبة${\displaystyle s^{-1}}$، عكس${\displaystyle s}$في المجموعة${\displaystyle G}$يمكن حساب ذلك بإحدى الطرق العديدة. إذا${\displaystyle G}$هي مجموعة جزئية من مجموعة ضربية من الأعداد الصحيحة بتردد ${\displaystyle n}$، أين${\displaystyle n}$إذا كان العدد أوليًا، فيمكن حساب معكوسه الضربي المعياري باستخدام خوارزمية إقليدس الموسعة . وثمة بديل آخر وهو حساب${\displaystyle s^{-1}}$مثل${\displaystyle c_{1}^{qx}}$هذا هو عكس${\displaystyle s}$بسبب نظرية لاغرانج ، بما أن${\displaystyle s\cdot c_{1}^{qx}=g^{xy}\cdot g^{(qx)y}=(g^{q})^{y}=e^{y}=e}$.
• الحوسبة${\displaystyle m:=c_{2}\cdot s^{-1}}$ينتج عن هذه العملية الحسابية الرسالة الأصلية${\displaystyle m}$، لأن${\displaystyle c_{2}=m\cdot s}$؛ لذلك${\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}$.
• رسم خريطة${\displaystyle m}$العودة إلى الرسالة النصية العادية${\displaystyle M}$.

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