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

طاهر الجمل

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

الگوریتم

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

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

تولید کلید

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

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

الگوریتم رمزنگاری

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

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

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

الگوریتم رمزگشایی

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

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

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

امنیت

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

کاربرد عملی

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

کارایی

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

رمزنگاری

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

رمزگشایی

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

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

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

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

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

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

منابع

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