دانلود پایان نامه:مقایسه چهار طرح ضرب کننده RNS

اختصاصی از سورنا فایل دانلود پایان نامه:مقایسه چهار طرح ضرب کننده RNS دانلود با لینک مستقیم و پر سرعت .

 

– مقدمه

همانطور که می دانیم ضرب پیمانه ای در علم رمزنگاری نقش مهمی ایفا می کند. از جمله روشهای رمزنگاری که به ضرب کننده پیمانه ای سریع نیاز دارد، روش رمزنگاری RSA می باشد که در آن نیاز به توان رساندن اعداد بزرگ در پیمانه های بزرگ می باشد. معمولاً برای نمایش اعداد در این حالات از سیستم باقی مانده (RNS) استفاده می شود و ضرب (به عنوان هسته توان رسانی) در این سیستم به کار می رود.

در اینجا برای آشنایی بیشتر به توضیح سیستم عددی باقی مانده می پردازیم و به کاربردها و فواید آن اشاراتی خواهیم داشت.

1-1 سیستم عددی باقیمانده (Residue Number System (RNS))

در حدود 1500 سال پیش معمایی به صورت شعر توسط یک شاعر چینی به صورت زیر بیان شد. «آن چه عددی است که وقتی بر اعداد 3،5و7 تقسیم می شود باقیمانده های 2،3و2 بدست می آید؟» این معما یکی از قدیمی ترین نمونه های سیستم عددی باقی مانده است.

در RNS یک عدد توسط لیستی از باقیمانده هایش برn  عدد صحیح مثبت m₁ تا m_n که این اعداد دو به دو نسبت به هم اولند (یعنی بزرگترین مقسوم علیه مشترک دوبدوشان یک است) به نمایش در می آید. به اعداد m₁ تا m_n پیمانه (moduli)
می گویند. حاصلضرب این nعدد،  تعداد اعدادی که می توان با این پیمانه ها نشان داد را بیان می کند. هر باقیمانده x_i را به صورت x_i=Xmod m_i نمایش می دهند. در مثال بالا عدد مربوطه به صورت X=(2/3/2)_RNS(7/5/3) به نمایش در می آید که X mod7=2 و X mod5=3 و X mod3=2. تعداد اعداد قابل نمایش در این مثال  می باشد. می توان هرمجموعه 105 تایی از اعداد صحیح مثبت یا منفی متوالی را با این سیستم عددی باقیمانده نمایش داد.

اثبات این که هر عدد صحیح موجود در محدوده، نمایش منحصر به فردی در این سیستم دارد به کمک قضیه باقی‌مانده های چینی(Chinese Remainder Theorem (CRT)) امکان پذیر است. این قضیه به صورت زیر بیان می شود:

1-2 قضیه باقی مانده های چینی:

اعداد صحیح مثبت  را که نسبت به هم دو به دو اول هستند در نظر بگیرید و M را حاصلضرب  فرض کنید. همچنین اعداد  را فرض کنید. اثبات می شود که فقط و فقط یک عدد صحیح U وجود دارد که شرایط زیر دارد:

,         ,

که U برابر است با:

اعمال ریاضی جمع، تفریق و ضرب به راحتی و به صورت زیر در این سیستم انجام می شود.

,

در فرمول بالا به جای علامت می توان هر کدام از علائم +،-،* را قرار داد.

سه عمل ریاضی (+،-،*) در این سیستم عددی راحت‌تر از سیستم نمایش عادی اعداد انجام می شود، زیرا هنگام انجام این عمل در این سیستم رقم نقلی (carry) بین بخشها رد و بدل نمی شود. در واقع انجام عملیات مربوط به مانده های هر پیمانه تاثیری روی دیگر عمل ها ندارد. یعنی محاسبه “” می تواند بطور مستقل (و در واقع موازی) انجام شود و نتیجه آن تاثیری در بقیه “”ها ندارد. بدین ترتیب عملیات ریاضی سریعتر (بعلت موازی شدن) و راحت تر (بعلت عدم تاثیرگذاری محاسبات مربوط به هر مانده برهم) انجام می شود.

1-3- کاربردهای RNS

سیستم عددی باقی مانده در چند دهه اخیر مورد توجه قرار گرفته، زیرا می توان بعضی از اعمال ریاضی را تحت RNS به صورت چند مجموعه زیر عمل ریاضی تقسیم کرد. ولی به دلیل اینکه این اعمال فقط شامل ضرب، جمع و تفریق هستند از RNS در محاسبات “خاص منظوره” استفاده می شود. RNS در پیاده سازی سریع مسائلی که شامل تصحیح و تشخیص خطا در سیستم های Fault-tolerant و سیستم‌های پردازش سیگنال هستند کاربرد دارد. کاربردهایی از قبیل تبدیل فوریه سریع، فیلتر دیجیتال و پردازش تصویر از اعمال ریاضی سریع RNS استفاده می کند. RNS راه خود را در کاربردهایی مثل تبدیلات تئوری اعداد و تبدیل فوریه گسسته پیدا کرده است. همچنین مستقل بودن رقم های باقیمانده باعث می شود که رخ دادن خطا در یک رقم به رقم های بعدی منتقل نشوند که این مسأله، باعث ایجاد یک معماری Fault-tolerant خواهد شد. [35],[20]

سیستم عددی RNS در رمزنگاری و به خصوص در روش RSA کاربرد زیادی دارد[35]. البته در RSA از ضرب پیمانه ای جهت عملیات توان رسانی استفاده می‌شود.

در این پروژه سعی می شود که چهار طرح از رویکردهای ضرب RNS را پیاده‌سازی و با هم مورد مقایسه قرار دهیم. این مقایسه براساس حجم و تاخیر طرح ها می‌باشد. در پیاده سازی سعی شده است که از پیشنهادات مقالات جهت عناصر بکار رفته استفاده شود (بخصوص در دو طرح اول) و در مواقعی که پیشنهاد خاصی انجام نشده (مثل طرح های سوم و چهارم) پیشنهاد مناسب از لحاظ خود من انجام شده است.