دانلود رایگان مقاله سیستم رمز کلید عمومی McEliece امن معنایی

چکیده

      تقریباً تمامی سیستم های رمز کلید-عمومی کنونی (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].

       در این مقاله ما به دقت این حملات را در بخش [3] بازنگری می کنیم و سپس نشان می دهیم که تمام حملات جمله ای زمانی به McEliece PKC نیاز به پیشگویی ها رمزگشایی یا دانش جزئی در مورد متن مهنادار متناظر متن رمزی چالش دارد. و در نتیجه بدون آنها، حمله جمله ای-زمانی برای تبدیل McEliece PKC شناخته شده است (که پارامترهای آن به دقت انتخاب می شوند). تحت این فرض که این مسئله تبدیل سخت است، ما این مسئله را به McEliece PKC معنادار امن در مقابل حملات متن رمزی-انتخاب شده تطبیقی (CCA2) تبدیل می کنیم، با معرفی برخی از تبدیلات مناسب. ما بررسی می کنیم که تبدیلات برای McEliece PKC در بخش [4] متناسب هستند. در حالیکه برخی از تبدیلات عام پیشنهاد شده در [24,9] نیز برای McEliece PKC قابل کاربرد هستند، آنها دارای عیبی در افزونگی داده ها هستند (که توسط اختلاف بین اندازه متن رمزی و اندازه متن مهنادار تعریف می شود). میزان زیادی از داده های افزونه برای تبدیلات عام نیاز می شود زیرا اندازه بلوک McEliece PKC نسبتاً بزرگ است. تبدیلات ما در بخش 4.4 نیاز به داده های افزونه کمتری نسبت به موارد عام دارند.

2 سیستم های رمز کلید عمومی McEliece 

در این بخش، ما به طور مختصر McEliece PKC را توصیف می کنیم.

تولید کلید: سه ماتریس کلید G,S,P زیر را ایجاد کنید:

       G= k*n ماتریس تولیدکننده یک کد Goppa دودویی که می تواند t خطا را تصحیح نماید و برای آن یک الگوریتم کدگشایی کارامد شناخته شده است. پارامتر t ارائه می شود که در ان dmin مینیمم فاصله Hamming برای کد است.

3 حملات به McEliece PKC

در این بخش، ما حملات کنونی شناخته شده به McEliece PKC را بازنگری می کنیم.

       در حالیکه هیچ الگوریتم کارامدی تاکنون برای تجزیه G’ به (S,G,P) [19] کشف نشده است، حمله ساختاری در [17] کشف شده است. این حمله بخشی از ساختار G’ ضعیف را نشان می دهد که از چندجمله ای Goppa دودویی ایجاد می شود. هرچند، از این حمله می توان به سادگی با اجتناب از استفاده از کلیدهای عمومی ضعیف اجتناب نمود. (این نشان می دهد که G نباید یک کد BCH باشد از اینرو معادل کد Goppa است که چندجمله ای Goppa آن   یعنی دودویی است). مورد بعدی که باید در نظر بگیریم اینست که یک کد Goppa معادل برای G’ (که لزوماً G نیست) و الگوریتم کدگشایی آن شناخته شده است اتفاق می افتد. این احتمال در [1.10] تخمین زده می شود و آنگاه کوچک و قابل چشمپوشی نشان داده می شود.

        تمام حملات دیگر شناخته شده برای رمزگشایی متون رمزی بدون شکستن کلیدهای عمومی هستند. ما آنها را به دو رده زیر، حملات بحرانی و حملات غیربحرانی مطابق با اینکه آیا این حملات می توانند به سادگی با بزرگ نمودن اندازه پارامتر اجتناب شوند یا خیر، رده بندی می کنیم. اگر اجتناب صورت گیرد، ما آن را در حملات غیربحرانی رده بندی می کنیم. در غیراینصورت، در موارد بحرانی. از آن جالب تر، تمام حملات بحرانی نیاز به اطلاعات اضافی دارند، مانند دانش جزئی در مورد متون مهنادار هدف یا پیشگویی رمزگشایی که می تواند به طور دلخواه متون رمزی را به جز متون رمزی چالش رمزگشایی نماید. و آنگاه بدون این اطلاعات اضافی و این قابلیت، هیچ الگوریتم کارامدی برای رمزگشایی متن رمزی معین دلخواه برای McEliece PKC شناخته شده نیست.

3.1 حملات غیربحرانی

        دو حمله زیر می تواند به سادگی با بزرگ نمودن اندازه پارامتر یا با اعمال اصلاح Loidreau [16] بدون بزرگ نمایی اندازه پارامتر اجتناب شود. بنابراین غیربحرانی است.

3.2 حملات بحرانی

       از حملات زیر نمی توان توسط بزرگنمایی اندازه پارامتر یا با اعمال اصلاح Loidreau اجتناب نمود [16]. بنابراین بحرانی است.

Abstract

       Almost all of the current public-key cryptosystems (PKCs) are based on number theory, such as the integer factoring problem and the discrete logarithm problem (which will be solved in polynomial-time after the emergence of quantum computers). While the McEliece PKC is based on another theory, i.e. coding theory, it is vulnerable against several practical attacks. In this paper, we carefully review currently known attacks to the McEliece PKC, and then point out that, without any decryption oracles or any partial knowledge on the plaintext of the challenge ciphertext, no polynomial-time algorithm is known for inverting the McEliece PKC whose parameters are carefully chosen. Under the assumption that this inverting problem is hard, we propose slightly modified versions of McEliece PKC that can be proven, in the random oracle model, to be semantically secure against adaptive chosen-ciphertext attacks. Our conversions can achieve the reduction of the redundant data down to 1/3 ∼ 1/4 compared with the generic conversions for practical parameters.

1 Introduction

       Since the concept of public-key cryptosystem (PKC) was introduced by Diffie and Hellman [5], many researchers have proposed numerous PKCs based on various problems, such as integer factoring, discrete logarithm, decoding a large linear code, knapsack, inverting polynomial equations and so on. While some of them are still alive, most of them were broken by cryptographers due to their intensive cryptanalysis. As a result, almost all of the current (so-called) secure systems employ only a small class of PKCs, such as RSA and elliptic curve cryptosystems, which are all based on either integer factoring problem (IFP) or discrete logarithm problem (DLP). This situation would cause a serious problem after someone discovers one practical algorithm which breaks both IFP and DLP in polynomial-time. No one can say that such an algorithm will never be found. Actually, Shor has already found a (probabilistic) polynomial-time algorithm in [25], even though it requires a quantum computer that is impractical so far. In order to prepare for that unfortunate situation, we need to find another secure scheme relying on neither IFP nor DLP.

       The McEliece PKC, proposed by R.J. McEliece in [18], is one of few alternatives1 for PKCs based on IFP or DLP. It is based on the decoding problem of a large linear code with no visible structure which is conjectured to be an NP-complete problem.2 While no polynomial-time algorithm has been discovered yet for decoding an arbitrary linear code of large length with no visible structure, a lot of attacks (some of them work in polynomial-time) are known to the McEliece PKC [1,3,4,12,15,28,17,13].

        In this paper, we carefully review these attacks in Section 3, and then point out that all the polynomial-time attacks to the McEliece PKC require either decryption oracles or partial knowledge on the corresponding plaintext of the challenge ciphertext. And then without them, no polynomial-time attack is known to invert the McEliece PKC (whose parameters are carefully chosen). Under the assumption that this inverting problem is hard, we convert this problem into semantically secure McEliece PKCs against adaptive chosen-ciphertext attacks (CCA2) by introducing some appropriate conversions. We discuss which conversions are appropriate for the McEliece PKC in Section 4. While some of the generic conversions proposed in [24,9] are also applicable to the McEliece PKC, they have a disadvantage in data redundancy (which is defined by the difference between the ciphertext size and the plaintext size). A large amount of redundant data is needed for the generic conversions since the block size of the McEliece PKC is relatively large. Our conversions in Section 4.4 need less redundant data than the generic ones.

2 McEliece Public-Key Cryptosystem

In this section, we briefly describe the McEliece PKC.

Key generation: Generate the following three matrices G,S,P:

      G: k × n generator matrix of a binary Goppa code which can correct up to t errors, and for which an efficient decoding algorithm is known. The parameter t is given by
dmin−1 2 where dmin denotes the minimum Hamming distance of the code.

3 Attacks to McEliece PKC

In this section, we review currently known attacks to the McEliece PKC.

       While no efficient algorithm has been discovered yet for decomposing G into (S, G, P) [19], a structural attack has been discovered in [17]. This attack reveals part of structure of a weak G which is generated from a “binary” Goppa polynomial. However, this attack can be avoided simply by avoiding the use of such weak public keys. (This implies G should not be a BCH code since it is equivalent to a Goppa code whose Goppa polynomial is 1 · x2t , i.e. “binary”. 3) Next case we have to consider is that an equivalent Goppa code of G (which is not necessarily G) and whose decoding algorithm is known happens to be found. This probability is estimated in [1][10], and then shown to be negligibly small.

       All the other known attacks are for decrypting ciphertexts without breaking public-keys. We categorize them into the following two categories, critical attacks and non-critical attacks, according to whether these attacks can be avoided simply by enlarging the parameter size or not. If avoided, we categorize it in the non-critical attacks. Otherwise, in the critical ones. Interestingly, all the critical attacks require either additional information, such as partial knowledge on the target plaintexts, or an decryption oracle which can decrypt arbitrarily given ciphertexts except the challenge ciphertexts. And then without this additional information and this ability, no efficient algorithm is known to decrypt an arbitrarily given ciphertext of the McEliece PKC.

3.1 Non-critical Attacks

        The following two attacks can be avoided simply by enlarging the parameter size or by applying Loidreau’s modification [16] without enlarging the parameter size. Thus, not critical.

3.2 Critical Attacks

       The following attacks cannot be avoided by enlarging the parameter size or by applying Loidreau’s modification [16]. Therefore critical.

چکیده

1 مقدمه

2 سیستم های رمز کلید عمومی McEliece 

3 حملات به McEliece PKC

3.1 حملات غیربحرانی

3.2 حملات بحرانی

4 تبدیلات برای McEliece PKC

4.1 دستورات

4.2 تبدیلات نامناسب برای McEliece PKC

4.3 تبدیلات عام قابل کاربرد برای McEliece PKC

4.4 تبدیلات خاص ما

5 نتیجه گیری

Abstract

1 Introduction

2 McEliece Public-Key Cryptosystem

3 Attacks to McEliece PKC

3.1 Non-critical Attacks

3.2 Critical Attacks

4 Conversions for McEliece PKC

4.1 Notations

4.2 Insufficient Conversions for McEliece PKC

4.3 Generic Conversions Being Applicable to McEliece PKC

4.4 Our Specific Conversions

5 Conclusion

Acknowledgments

References