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

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

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

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

تولید کلید

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

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

کلید عمومی از (x, N) تشکیل شده‌است و کلید رمز برابر تجزیه (p, q) می‌باشد.

رمزگذاری پیام

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

1. بابک ابتدا پیام m را به رشته‌های (m₁, ..., m_n) تقسیم می‌کند.
2. به ازای هر بیت بابک عدد تصادفی y را به گونه‌ای انتخاب می‌کند که GCD(y,N) = 1 و سپس عدد ${\displaystyle c_{i}=y^{2}x^{m_{i}}{\pmod {N}}}$
   را به ازای هر بیت تولید می‌کند.

بابک متن رمزشده (c₁, ..., c_n) را می فرستد.

رمزگشایی پیام

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

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

خروجی برابر m = (m₁, ..., m_n) خواهد بود.

• الگوریتم‌های کلید نامتقارن
• کلید عمومی
• کلید خصوصی
• الگوریتم‌های کلید متقارن

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.