رمزنگاری گلدواسر-میکالی

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

رمزنگاری گلدواسر-میکالی (به انگلیسی: Goldwasser–Micali cryptosystem)یکی از روشهای رمزنگاری کلید عمومی است که در سال ۱۹۸۲ توسط شافی گلدواسر و سیلویو میکالی معرفی شده است[۱]. این روش اولین روش احتمالاتی کلید عمومی است که در آن می‌توان با داشتن مفروضات استاندارد رمزنگاری امنیت را اثبات نمود. این روش ممکن است بهینه نباشد چرا که در روش گلدواسر-میکالی متن رمزشده می‌تواند تا چند صد برابر بزرگتر از متن آشکار باشد. گلدواسر و میکالی برای اثبات امنیت این سیستم از مفهوم امنیت معنایی بهره جسته‌اند.

پس زمینه[ویرایش]

سیتم رمزنگاری گلدواسر-میکالی بر اساس پیچیدگی مساله مانده مربعی به پیمانه عدد مرکب N = pq که p و q عدد اول بزرگ هستند، به صورت معنایی امن است. این فرض بیان می‌کند که با داشتن زوج (x, N)، تعیین این مساله که آیا x یک مانده مربعی به پیمانه N است مساله دشواری می‌باشد. مساله مانده مربعی با فرض معلوم بودن N به راحتی حل می‌شود چراکه مانده مربعی را می‌توان با استفاده از تجزیه به راحتی محاسبه نمود. این الگوریتم پیام را گسترش می‌دهد، به این مفهوم که به ازای هر بیت عددی به پیمانه N ارسال می‌کند و این عدد با توجه به بزرگی اعداد اول p و q بسیار بزرگ می‌باشد. این الگوریتم احتمالاتی است یعنی با داشتن متن اصلی خاص، می‌توان تعداد بسیار زیادی متن رمزشده متفاوت تولید نمود بدون اینکه کلید عمومی یا سایر پارامترها تغییر کنند. این مساله باعث می‌شود دشمن نتواند پیام دریافتی را با مقایسه با لغت نامه متن‌های رمزشده شناخته شده، تشخیص دهد.

معرفی روش رمزنگاری گلدواسر-میکالی[ویرایش]

روش مذکور از سه الگوریتم تشکیل شده است. الگوریتم اول به تولید کلید می‌پردازد و کلیدی عمومی و نیز یک کلید عمومی تولید می‌کند. الگوریتم دوم روشی احتمالاتی برای رمزگذاری ارایه می‌دهد و نهایتاً الگوریتم سوم شیوه رمزگشایی را بیان می‌کند. در روش گلدواسر-میکالی بررسی می‌گردد که آیامقدار معلوم x به پیمانه N با فرض معلوم بودن تجزیه N مربعی می‌شود یا نه. این مساله را می‌توان با فرایند زیر تحقیق نمود:

  1. محاسبه xp = x mod p و xq = x mod q.
  2. اگر x_p^{(p-1)/2} \equiv 1\pmod{p} و x_q^{(q-1)/2} \equiv 1\pmod{q}، سپس x مانده مربعی به پیمانه N باشد.

تولید کلید[ویرایش]

گلدواسر-میکالی از روشی مشابه آراس ای برای تولید کلید بهره می گیرد.

  1. آذر دو عدد اول بزرگ و مستقل p و q در نظر می گیرد.
  2. آذر حاصلضرب دو عدد فوق را محاسبه کرده و آن را N می نامد.
  3. آذر عدد نامانده x را پیدا می کند که نماد لژاندر آن برابر \left(\frac{x}{p}\right)=\left(\frac{x}{q}\right)=-1 باشد. بدیهی است که نماد ژاکوبی \left(\frac{x}{N}\right)برابر 1+ خواهد شد.

کلید عمومی از (xN) تشکیل شده است و کلید رمز برابر تجزیه (pq) می باشد.

رمزگذاری پیام[ویرایش]

فرض کنید بابک بخواهد پیام m را به آذر بدهد.

  1. بابک ابتدا پیام m را به رشته های (m1, ..., mn) تقسیم می کند.
  2. به ازای هر بیت بابک عدد تصادفی y را به گونه ای انتخاب می کند که GCD(y,N) = 1 و سپس عدد c_i = y^2 x^{m_i}\pmod{N} را به ازای هر بیت تولید می کند.

بابک متن رمزشده (c1, ..., cn) را می فرستد.

رمزگشایی پیام[ویرایش]

آذر (c1, ..., cn) را دریافت می کند. سپس او طبق فرایند زیر m را ستخراج می کند.

  1. به ازای هر i او با توجه به تجزیه (p, q) تصمیم می گیرد که آیا ci مانده مربعی است یا نه. در صورتی که مانده مربعی باشد، mi = 0 وگرنه mi = 1.

خروجی برابر m = (m1, ..., mn) خواهد بود.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  1. http://en.wikipedia.org/wiki/Goldwasser–Micali_cryptosystem
  • S. Goldwasser, S. Micali (1982). "Probabilistic encryption and how to play mental poker keeping secret all partial information". Proc. 14th Symposium on Theory of Computing: 365–377. doi:10.1145/800070.802212. 
  • S. Goldwasser, S. Micali (1984). "Probabilistic encryption". Journal of Computer and System Sciences 28 (2): 270–299. doi:10.1016/0022-0000(84)90070-9.