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

رمزنگاری الجمال (به انگلیسی: ElGamal encryption) در رمزنگاری سیستم رمزنگاری الجمل یک الگوریتم رمزنگاری کلید عمومی است که بر پایه پروتکل تبادل کلید دیفی-هلمن ساخته شده‌است. این الگوریتم توسط طاهر الجمل در سال ۱۹۸۴ معرفی شد. الگوریتم الجمل در برنامه‌هایی مانند گنو پرایوسی گارد یا نسخه‌های اخیر PGP و سایر نرم‌افزارهای رمزنگاری استفاده می‌شود. الگوریتم الجمل می‌تواند بر روی هر گروه دوری مانند ${\displaystyle G}$ تعریف شود. امنیت آن بستگی به سختی مسئله‌ای خاص در ${\displaystyle G}$ مربوط به محاسبۀ لگاریتم گسسته دارد.

الگوریتم

الگوریتم الجمل از سه قسمت تشکیل شده‌است.

• تولید کلید
• الگوریتم رمزنگاری
• الگوریتم رمزگشایی

تولید کلید

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

• آلیس توسط مولد ${\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}$ و همچنین روش پد کردن پیغام بستگی دارد. اگر فرض دیفی-هلمن محاسباتی(CDH) بر روی گروه دوری ${\displaystyle G}$ برقرار باشد، آن‌گاه تابع رمزنگاری یک‌طرفه است. اگر فرض دیفی-هلمن تصمیمی(DDH) بر روی ${\displaystyle G}$ برقرار باشد، آن‌گاه الجمل دارای امنیت معنایی خواهد بود. امنیت معنایی را نمی‌توان به تنهایی از فرض دیفی-هلمن محاسباتی به‌دست آورد. رمزنگاری الجمل نرمش‌پذیر است، بنابراین در برابر حملۀ متن رمزی انتخابی امن نیست. برای مثال توسط متن رمزی ${\displaystyle (c_{1},c_{2})}$ از پیام ${\displaystyle m}$ می‌توان به‌راحتی پیام ${\displaystyle 2m}$ را توسط ${\displaystyle (c_{1},2c_{2})}$ به‌دست آورد. برای به‌دست آوردن امنیت متن رمزی انتخابی باید روش رمزنگاری را تغییر دهیم، یا این‌که از یک روش پد مناسب استفاده کنیم. بسته به نوع تغییرات فرض دیفی-هلمن تصمیمی می‌تواند مورد نیاز باشد یا نباشد.

کاربرد عملی

سیستم رمزنگاری الجمل معمولاً در سیستم‌های رمزنگاری هیبریدی استفاده می‌شود. برای مثال، پیام توسط یک سیستم رمزنگاری متقارن رمز می‌شود و سپس از سیستم الجمل برای رمز کردن کلید متقارن استفاده می‌شود. زیرا سیستم‌های رمزنگاری نامتقارن مثل الجمل نسبت به سیستم‌های متقارن معمولاً سرعت پایین‌تری دارند و بنابراین با توجه به این‌که نسبت اندازۀ کلید به متن بسیار کوچک‌تر است این‌ کار از لحاظ زمانی بسیار بهینه‌تر است.

کارایی

الگوریتم الجمل احتمالاتی کار می‌کند؛ به‌این معنی که رمزشدۀ یک متن ثابت، می‌تواند متن‌های متفاوتی باشد و دلیل آن‌هم انتخاب تصادفی مقدار ${\displaystyle y}$ در مرحلۀ رمزگذاری می‌باشد.

رمزنگاری

برای رمز کردن یک متن توسط الجمل به دو عنصر ${\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}}$

جستارهای وابسته

• توابع درهم‌ساز
• الگوریتم‌های رمز استاندارد
• الگوریتم‌های کلید نامتقارن
• کلید عمومی
• کلید خصوصی
• الگوریتم‌های کلید متقارن
• امضای رقومی
• لگاریتم گسسته
• فرض دیفی-هیلمن
• رمزنگاری هیل
• اصول ششگانه کرکهف

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «ElGamal encryption». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۱ بهمن ۹۲.