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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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