رمزنگاری الجمل - ویکی‌پدیا، دانشنامهٔ آزاد

رمزنگاری الجمل (به انگلیسی: 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». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۱ بهمن ۹۲.

پیوند به بیرون[ویرایش]