چکیده
تقریباً تمامی سیستم های رمز کلید-عمومی کنونی (PKCها) بر اساس تئوری اعداد، مانند مسئله فاکتوربندی عدد صحیح و مسئله لگاریتم گسسته هستند (که در چندجمله ای-زمانی بعد از ظهور کامپیوترهای کوانتوم حل خواهد شد). در حالیکه McEliece PKC بر اساس تئوری دیگری است، یعنی تئوری کدگذاری، در مقابل چندین حمله عملی مستعد است. در این مقاله، ما به دقت حملات کنونی شناخته شده برای McEliece PKC را بازنگری می کنیم و سپس نشان می دهیم که بدون هر پیشگویی آشکارسازی یا هر دانش جزئی در مورد پیام عادی مهنادار پیام رمزی چالش، هیچ الگوریتم زمانی چندجمله ای برای تبدیل McEliece PKC وجود ندارد که پارامترهای آن به دقت انتخاب شده باشند. تحت این فرض که این مسئله تبدیل سخت است، ما به طور مختصر نسخه های اصلاح شده McEliece PKC را پیشنهاد می دهیم که می تواند در مدل پیشگویی تصادفی که باید به طور معنادار در مقابل حملات پیام متنی-انتخاب شده تطبیقی امن شود، اثبات شود. تبدیلات ما می تواند کاهش داده های افزونه را به 3/1 ~ 4/1 در مقایسه با تبدیلات ذاتی برای پارامترهای عملی حاصل نماید.
1 مقدمه
از زمانی که مفهوم سیستم رمز کلید عمومی (PKC) توسط Diffie and Hellman [5], مطرح شد، بسیاری از محققان PKCهای متعددی را بر اساس مسائل مختلف، مانند فاکتوربندی عدد صحیح، لگاریتم گسسته، کدگشایی کد خطی بزرگ، کوله پشتی، تبدیل معادلات چندجمله ای و غیره پیشنهاد نمودند. در حالیکه برخی از آنها هنوز حاضر هستند، بیشتر آنها توسط رمزنویس به علت تحلیل رمز شدید شکسته شدند. به عنوان نتیجه، تقریباً تمامی سیستم های امن کنونی، فقط یک کلاس کوچک از PKCها، مانند RSA و سیستم های رمز منحنی بیضوی را به کار می گیرند که همه بر اساس مسئله فاکتوربندی عدد صحیح (IFP) یا مسئله لگاریتم گسسته (DLP) هستند. این وضعیت سبب مسئله ای جدی می شود بعد از اینکه کسی یک الگوریتم عملی را کشف کند که IFP و DLP را به چند جمله ای-زمانی بشکند. هیچ کس نمی تواند بگوید که چنین الگوریتمی هرگز یافت نشود. واقعاً، Shor قبلاً یک الگوریتم (احتمالی) چندجمله ای-زمانی را در [25] کشف نموده است، حتی اگر نیاز به کامپیوتر کوانتوم داشته باشد که تا به حال غیرعملی بوده است. به منظور آماده سازی برای آن وضعیت تاسف بار، ما نیاز به یافتن نقشه امن دیگری داریم که روی IFP و DLP تکیه می کند.
McEliece PKC که توسط R.J McElice در [18] پیشنهاد شده است، یکی از جایگزین های معدود برای PKCهای مبتنی بر IFP یا DLP است. این مورد مبتنی بر مسئله کدگشایی کد خطی بزرگ بدون هیچ ساختار مرئی است که به عنوان یک مسئله کامل-NP حدس زده می شود. در حالیکه هیچ الگوریتم زمانی-چندجمله ای تا کنون برای کدگشایی یک کد خطی دلخواه با طول بزرگ بدون ساختار مرئی کشف نشده است، بسیاری از حملات (برخی از آنها در چندجمله ای-زمانی کار می کنند) برای McEliece PKC شناخته شده اند [1,3,4,12,15,28,17,13].
- این مقاله در نشریه اسپرینگر منتشر شده و ترجمه آن با عنوان رمز کلید عمومی در سایت ای ترجمه به صورت رایگان قابل دانلود می باشد. جهت دانلود رایگان مقاله فارسی و انگلیسی روی عنوان فارسی (آبی رنگ) کلیک نمایید.
منبع:
Semantically Secure McEliece Public-Key Cryptosystems - Conversions for McEliece PKC -
