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

رمزنگاری گلدواسر-میکالی (به انگلیسی: Goldwasser–Micali cryptosystem)یکی از روش های رمزنگاری کلید عمومی است که در سال ۱۹۸۲ توسط شافی گلدواسر و سیلویو میکالی معرفی شده است. این روش اولین روش احتمالاتی کلید عمومی است که در آن می توان با داشتن مفروضات استاندارد رمزنگاری امنیت را اثبات نمود. این روش ممکن است بهینه نباشد چرا که در روش گلدواسر-میکالی متن رمزشده می تواند تا چند صد برابر بزرگتر از متن آشکار باشد. گلدواسر و میکالی برای اثبات امنیت این سیستم از مفهوم امنیت معنایی بهره جسته اند.
الگوریتم های کلید نامتقارن
کلید عمومی
کلید خصوصی
الگوریتم های کلید متقارن
سیتم رمزنگاری گلدواسر-میکالی بر اساس پیچیدگی مسئله مانده مربعی به پیمانه عدد مرکب N = pq که p و q عدد اول بزرگ هستند، به صورت معنایی امن است. این فرض بیان می کند که با داشتن زوج (x, N)، تعیین این مسئله که آیا x یک مانده مربعی به پیمانه N است مسئله دشواری می باشد. مسئله مانده مربعی با فرض معلوم بودن N به راحتی حل می شود چراکه مانده مربعی را می توان با استفاده از تجزیه به راحتی محاسبه نمود.این الگوریتم پیام را گسترش می دهد، به این مفهوم که به ازای هر بیت عددی به پیمانه N ارسال می کند و این عدد با توجه به بزرگی اعداد اول p و q بسیار بزرگ می باشد. این الگوریتم احتمالاتی است یعنی با داشتن متن اصلی خاص، می توان تعداد بسیار زیادی متن رمزشده متفاوت تولید نمود بدون اینکه کلید عمومی یا سایر پارامترها تغییر کنند. این مسئله باعث می شود دشمن نتواند پیام دریافتی را با مقایسه با لغت نامه متن های رمزشده شناخته شده، تشخیص دهد.
روش مذکور از سه الگوریتم تشکیل شده است. الگوریتم اول به تولید کلید می پردازد و کلیدی عمومی و نیز یک کلید عمومی تولید می کند. الگوریتم دوم روشی احتمالاتی برای رمزگذاری ارائه می دهد و نهایتاً الگوریتم سوم شیوه رمزگشایی را بیان می کند. در روش گلدواسر-میکالی بررسی می گردد که آیامقدار معلوم x به پیمانه N با فرض معلوم بودن تجزیه N مربعی می شود یا نه. این مسئله را می توان با فرایند زیر تحقیق نمود:
گلدواسر-میکالی از روشی مشابه آراس ای برای تولید کلید بهره می گیرد.