Skip to main content
SUPERVISOR
SiyedMohammad DakhilAlian,Morteza Esmaeili
سیدمحمد دخیل علیان (استاد راهنما) مرتضی اسمعیلی (استاد مشاور)
 
STUDENT
Mostafa Esmaeili
مصطفی اسمعیلی

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1388

TITLE

McEliece Cryptosystem with LDPC Codes
With the wide spread of communications, demands for reliable and secure data transmission is growing. A reliable communication can be obtained via channel coding. Designing channel codes started in 1948 with Shannon’s theorem. In this theorem, it is proven that codes with rates arbitrarily close to the channel capacity exist with error decoding probability arbitrarily close to zero. In 1960, codes with sparse parity check matrices were introduced, but were mostly ignored in the next 30 years. These codes were re-discovered in the 1990’s and have been subject to many research projects. Some classes of these codes (e.g. QC-LDPC codes) have been used in standards in Mobile Wireless WAN. Secure transmission of data is achieved via cryptography. Although there exist many secure cryptosystems, a system which could combine encoding/encryption (decoding/decryption) would be very useful in communication systems. The first system of this kind was introduced by McEliece in 1978, known as the McEliece public key cryptosystem. The security of this system is based on the fact that, generally, decoding a linear code is a NP problem. In this system the bits of a plain-text are scrambled, bits of the codeword associated with it are permuted and some of them are randomly changed. Two main drawbacks of the McEliece cryptosystem is its large key size in order to hide the generator matrix of the applied code in the public key and low information rate. During the last 33 years many variants of the McEliece cryptosystem have been introduced; some have changed the code used in it, others have changed the structure of the scrambler and permutation matrices and some have changed the method of changing the bits of the codeword. But in all of these systems either one of the two problems remain unsolved or the cryptosystem has a low level of security. In this thesis a new symmetric key cryptosystem based on randomly puncturing a QC-LDPC code is proposed. A pseudo-random number generator is applied to determine which bits of a codeword should be punctured. One of the advantages of this cryptosystem is that with the absence of a permutation and scrambler matrices, the key size has been reduced and codes with rates as high as 0.875 can be used which also increases the information rate. Based on computer simulations of a parent code and its associated punctured code, suggested amounts of how many bits can be punctured is provided. It is shown that even with small amounts of punctures the system is secure. It is also shown that if an eavesdropper is provided with the code that is used, the system can remain secure. This is a unique characteristic that previous algebraic coded cryptosystems did not possess. In similar cryptosystems if the applied code is revealed, the system is broken. This is why the generator (or parity check matrix) of the applied code is part of the key (or part of the private key in public key algebraic coded cryptosystems). Key Words Coding, cryptography, LDPC codes, puncturing, pseudo-random number generator.
با افزایش حجم ارتباطات و دسترسی همگانی به وسایل ارتباط جمعی، انتقال مطمئن و امن اطلاعات اهمیت فراوانی یافته است. انتقال مطمئن اطلاعات از طریق کدگذاری کانال انجام می¬گیرد. طراحی کدهای کانال از سال 1948 با نظریه شانون شروع شد. در این نظریه، شانون ثابت کرد که کدهایی با نرخ به قدر دلخواه نزدیک به ظرفیت کانال وجود دارند که احتمال خطای کدگشایی در گیرنده به قدر دلخواه نزدیک به صفر است. در سال 1960 کدهای LDPC که دارای ماتریس بررسی توازن خلوت هستند معرفی شدند. ولی به دلیل نبود امکانات لازم در آن زمان، به مدت 30 سال به فراموشی سپرده شدند. در اوایل دهه 1990، این کدها مجددا مورد توجه قرار گرفتند و تا به امروز تحقیقات زیادی روی آنها انجام گرفته است و برخی از کلاس¬های آنها مانند کدهای QC-LDPC در استانداردهای مختلف ارتباطی به کار برده شده¬اند. انتقال امن اطلاعات از طریق یک کانال ناامن بوسیله سیستم¬های رمزنگاری صورت می¬گیرد. علیرغم وجود سیستم¬های مختلف رمزنگاری که امنیت قابل قبولی دارند، سیستمی که بتواند دو عمل کدگذاری و رمزگذاری را با هم ترکیب کند در سیستم¬های مخابراتی بسیار کاربردی خواهد بود. اولین سیستمی که چنین عملی را انجام می¬داد در سال 1978 توسط مک¬آلیس معرفی شد که به سیستم رمزنگاری کلید عمومی مک¬آلیس معروف است. امنیت این سیستم مبتنی بر این است که بدون اطلاع از ساختار جبری یک کد کانال، کدگشایی آن یک مسئله NP خواهد بود. در این سیستم رمزنگاری مولفه¬های یک متن ساده درهم ریخته، مولفه¬های کدکلمه متناظر با یک متن ساده جایگشت و برخی از آنها به طور تصادفی تغییر داده می¬شوند. ولی این سیستم به دو دلیل هنوز کاربردی نشده است؛ (1) اندازه کلید آن بزرگ است و (2) نرخ ارسال اطلاعات در آن پایین می¬باشد. در طول 33 سال گذشته، تغییرات زیادی روی پارامترهای این سیستم داده شد تا معایب آن برطرف شوند. برخی از این تغییرات در کد مورد استفاده، در ساختار ماتریس¬های جایگشت و درهم¬ریز و مجموعه بردارهای خطای تصادفی بوده است. ولی در هر کدام از سیستم¬های جدید یکی از دو معایب سیستم مک¬آلیس باقی مانده بود و یا از امنیت قابل قبولی برخوردار نبودند. در این پایان¬نامه یک سیستم رمزنگاری کلید متقارن جدید مبتنی بر حذف تصادفی برخی از مولفه¬های یک کد QC-LDPC ارائه شده است. در این سیستم از یک مولد شبه تصادفی اعداد برای مشخص کردن مولفه¬هایی که باید حذف گردند استفاده شده است. یکی از مزایای این سیستم نسبت به سیستم¬های مشابه پیشین آن است که با حذف ماتریس¬های جایگشت و درهم-ریز اندازه کلید کاهش یافته و امکان استفاده از کدهایی با نرخ بالا فراهم شده است. این مزیت سبب رفع مشکل نرخ ارسال اطلاعات پایین در سیستم رمزنگاری مک¬آلیس خواهد شد. مقادیر پیشنهادی برای تعداد مولفه¬هایی که می¬توانند حذف گردند ارائه شده و نشان داده شده است که عملکرد کد با حذف این تعداد مولفه قابل قبول باقی می¬ماند. همچنین از دیگر مزایای این سیستم آن است که اگر به هر دلیلی کد مورد استفاده در سیستم رمزنگاری در اختیار فرد سوم قرار گیرد، سیستم می¬تواند امن باقی بماند. این مزیت تا به حال در هیچکدام از سیستم¬های رمزنگاری پیشین وجود نداشته است، یعنی اگر کد مورد استفاده به هر دلیلی فاش می¬شد، سیستم رمزنگاری شکسته شده محسوب می¬شد. کلمات کلیدی: رمزنگاری، کدگذاری، کدهای LDPC، حذف مولفه، مولد شبه تصادفی اعداد.

ارتقاء امنیت وب با وف بومی