رمزنگاری الجمل

مولد کلید این‌گونه کار می‌کند:

• آلیس توسط مولد ${\displaystyle g}$ یک گروه دوری ضربی بهینۀ ${\displaystyle G}$ با مرتبۀ ${\displaystyle q}$ تولید می‌کند.این گروه باید شرایطی داشته باشد که در ادامه به آن‌‌ها اشاره می‌کنیم.
• آلیس به تصادف یک ${\displaystyle x}$ از ${\displaystyle \{1,\ldots ,q-1\}}$ انتخاب می‌کند.
• آلیس ${\displaystyle h=g^{x}\,}$ را محاسبه می‌کند.
• آلیس ${\displaystyle h}$ را به همراه ${\displaystyle G}$ ،${\displaystyle q}$ و ${\displaystyle g}$ به عنوان کلید عمومی منتشر می‌کند و ${\displaystyle x}$ را به عنوان کلید خصوصی نزد خود نگه می‌دارد.

برای رمز کردن پیام ${\displaystyle m}$ تحت کلید ${\displaystyle (G,q,g,h)\,}$ این‌گونه عمل می‌کنیم:

• باب به تصادف یک ${\displaystyle y}$ از ${\displaystyle \{1,\ldots ,q-1\}}$ انتخاب می‌کند و ${\displaystyle c_{1}=g^{y}\,}$ را حساب می‌کند.
• باب رمز مشترک ${\displaystyle s=h^{y}}$ (که باید مخفی بماند) را محاسبه می‌کند.
• باب پیام ${\displaystyle m}$ را به یک عضو از ${\displaystyle G}$ مثل ${\displaystyle m'}$ تبدیل می‌کند.
• باب سپس ${\displaystyle c_{2}=m'\cdot s}$ را محاسبه می‌کند.
• باب در نهایت پیام رمزشدۀ ${\displaystyle (c_{1},c_{2})=(g^{y},m'\cdot h^{y})=(g^{y},m'\cdot (g^{x})^{y})\,}$ را برای آلیس می‌فرستد.

در اینجا اگر شخصی ${\displaystyle m'}$ را بداند به‌راحتی می‌تواند ${\displaystyle h^{y}}$ را به‌دست آورد. به همین دلیل برای بالا بردن امنیت برای هر پیغام، یک ${\displaystyle y}$ جدید تولید می‌شود که به آن کلید موقتی یا کلید بی‌دوام (به انگلیسی: ephemeral key) می‌گویند.

برای رمزگشایی پیام رمزی ${\displaystyle (c_{1},c_{2})\,}$ به‌وسیلۀ کلید خصوصی ${\displaystyle x}$ این‌گونه عمل می‌کنیم:

• آلیس رمز مشترک را محاسبه می‌کند: ${\displaystyle s=c_{1}^{x}}$
• سپس آلیس ${\displaystyle m'=c_{2}\cdot s^{-1}\,}$ را محاسبه می‌کند که به وسیلۀ آن می‌تواند ${\displaystyle m}$ را به‌دست آورد. در این‌جا ${\displaystyle s^{-1}}$ عضو وارون ${\displaystyle s}$ در ${\displaystyle G}$ می‌باشد.

این الگوریتم درست کار می‌کند زیرا: ${\displaystyle c_{2}\cdot s^{-1}=m'\cdot h^{y}\cdot (g^{xy})^{-1}=m'\cdot g^{xy}\cdot g^{-xy}=m'}$

برای رمز کردن یک متن توسط الجمل به دو عنصر ${\displaystyle g^{y}}$ و ${\displaystyle h^{y}}$ نیاز داریم که با توجه به این که این عناصر مستقل از متن هستند، می‌توان آن‌ها را از قبل محاسبه کرد.

در مرحلۀ رمزگشایی برای به‌دست آوردن متن اصلی از متن رمزی ${\displaystyle (c_{1},c_{2})}$ به‌وسیلۀ کلید خصوصی ${\displaystyle x}$، ما نیاز به ${\displaystyle s^{-1}}$ داشتیم. برای به‌دست آوردن بهینۀ ${\displaystyle s^{-1}}$ می‌توان از روش زیر استفاده کرد:

${\displaystyle s'=c_{1}^{q-1-x}=g^{y(q-1-x)}=g^{-xy}}$

(در این‌جا محاسبات توانی به پیمانۀ ${\displaystyle q-1}$ انجام شده‌اند). حالا با توجه به‌این‌که ${\displaystyle s=c_{1}^{x}=(g^{y})^{x}=g^{xy}}$ پس:

${\displaystyle s\cdot s'=g^{xy}\cdot g^{-xy}=1\Rightarrow s'=s^{-1}}$