پروژه مقایسه چهار طرح ضرب كننده RNS

چکیده ی بخشهایی از متن با فهرست:

چكیده

هدف از این پروژه مقایسه چهارطرح ضرب كننده RNS می باشد. بدین منظور با بهره گیری از پیاده سازی این چهار طرح با نرم افزار VHDL به مقایسه آنها می‌پردازیم. RNS یك روش نمایش اعداد است كه در آن هر عدد به وسیله باقی مانده‌های تقسیم آن بر مجموعه ای از اعداد دو به دو نسبت به هم اول نمایش داده
می شود. با كمك قضیه باقی مانده چینی، اثبات می شود كه در RNS نمایش هر عدد منحصر به فرد می باشد برای ضرب در RNS نیاز به ضرب پیمانه ای خواهد بود. روشهای ضرب پیمانه ای برحسب اینكه كاهش به پیمانه، در كدام مرحله ضرب انجام گیرد. به دو دسته «كاهش در حین ضرب (RDM)» و «كاهش بعد از ضرب (RAM)» تقسیم می شوند. دو طرح اول این پروژه با تكنیك RAM و دو طرح دوم با تكنیك RDM كار می‌كنند.

فهرست مطالب

عنوان                        صفحه

1- مقدمه............................. 1

  1-1 سیستم عددی باقیمانده........... 1

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

  1-3 كاربردهای RNS............................... 3

2- روشهای ضرب پیمانه ای ............. 5

  2-1 روش مونتگمری................... 5

  2-2 بررسی اجمالی روشهای موجود پیاده سازی ضرب در RNS 6

  2-3 نكاتی پیرامون چهار طرح مورد نظر 7

3- طرح اول........................... 8

  3-1 مقدمه.......................... 8

  3-2 بررسی سوابق.................... 8

  3-3 الگوریتم....................... 9

  3-4 پیاده سازی سخت افزاری.......... 10

  3-5 محاسبه پیچیدگی مساحت و تأخیر طرح اول 13

4- طرح دوم........................... 15

  4-1 مقدمه.......................... 15

  4-2 بررسی سوابق ................... 15

  4-3 الگوریتم....................... 15

  4-4 پیاده سازی سخت افزاری.......... 18

  4-5 محاسبه پیچیدگی مساحت و تأخیر طرح دوم 20

5- طرح سوم........................... 21

  5-1 تبدیل سیستم RNS (Residue Conversion)... 28

  5-2 پیاده سازی سخت افزاری.......... 30

   5-2-1 پیاده سازی تبدیل RNS........ 31

    5-2-2 پیاده سازی بخش اصلی الگوریتم (الگوریتم مونتگمری با RNS)  34

  5-3- محاسبه پیچیدگی مساحت و تأخیر طرح سوم    36

   5-3-1 عناصر وابسته به ROM........ 36

   5-3-2 عناصر ریاضی................. 36

   5-3-3 تأخیر و مساحت تبدیل كننده RNS استاندارد  37

   5-3-4 محاسبه مساحت و تأخیر تبدیل كننده RNS سریع 44

   5-3-5 مساحت و تأخیر طرح سوم....... 50

  5-4 نتایج پیاده سازی در طرح سوم ... 56

6- طرح چهارم......................... 58

  6-1 بیان مقاله در مورد سیستم RNS ......... 59   

  6-2 بیان مقاله از ضرب پیمانه ای بدون تقسیم (روش مونتگمری)............. 60

  6-3 بررسی صحت الگوریتم............. 62

  6-4 روش تبدیل RNS.................. 66

  6-5 پیاده سازی سخت افزاری.......... 67

   6-5-1 تبدیل RNS ناقص.............. 68

   6-5-2 پیاده سازی بخش اصلی طرح چهارم (الگوریتم مونتگمری)............... 68

  6-6 محاسبه پیچیدگی تأخیر و مساحت طرح چهارم   70

   6-6-1 محاسبه تأخیر و مساحت تبدیل RNSناقص    70

   6-6-2 محاسبه تأخیر و مساحت در طرح چهارم 72

  6-7 نتایج شبیه سازی در طرج چهارم... 80

7- مقایسه  طرح ها وجمع بندی ......... 81

  7-1- مقایسه چهار طرح............... 81

  7-2- جمع بندی ..................... 98

8- مراجع.............................

9- ضمائم ............................

  الف – كدهای VHDL طرح اول...........

  ب – كدهای VHDL طرح دوم.............

  ج – كدهای VHDL طرح سوم.............

  د – كدهای VHDL طرح چهارم...........

  هـ – MOMA

==============

فصل اول

1- مقدمه

همانطور كه می دانیم ضرب پیمانه ای در علم رمزنگاری نقش مهمی ایفا می كند. از جمله روشهای رمزنگاری كه به ضرب كننده پیمانه ای سریع نیاز دارد، روش رمزنگاری 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 تایی از اعداد صحیح مثبت یا منفی متوالی را با این سیستم عددی باقیمانده نمایش داد.

...

فصل چهارم

طرح دوم

6-5- پیاده سازی سخت افزاری

اصول اصلی پیاده سازی طرح چهارم كاملاً مشابه با طرح سوم می باشد. در واقع در اینجا هم عملیاتها به دو دسته اصلی تبدیل RNS و عملیات مونتگمری قابل تقسیم هستند. و همچنین از تمام عناصر بكار رفته در طرح سوم (بجز RESCONVS كه بصورت تنها اصلاح شده و در شكل دیگر مورد استفاده قرار می گیرد) مورد استفاده قرار گرفته اند و یك عنصر مبتنی بر ROM به این مجموعه اضافه می شود. تفاوت اصلی این الگوریتم با الگوریتم سوم در انتهای آن است. در واقع جهت محاسبه ضریب خطای T از مقادیر بدست آمده از تبدیل RNS استفاده می شود كه نتیجه را از RNS كمكی به RNS اولیه منتقل می كند. در واقع فرض می شود كه نتیجه نهایی را در همان RNS كه شروع كردیم بیان كنیم. ولی اگر بخاطر داشته باشید در طرح سوم نتیجه نهایی در همان RNS كمكی باقی ماند و توضیح داریم كه این مسئله برای ما مشكل ایجاد نمی كند. پس برای مقایسه این دو طرح فرض را بر همان روش سوم قرار می دهیم. پس در واقع دیگر به تبدیل RNS دوم برای بازگشتن به RNS اولیه بطور كامل احتیاج نیست و فقط بخشی از آن كه ما را دریافتن T یاری می كند مورد استفاده قرار گرفته.

یك نكته دیگر عدم  استفاده این طرح از روش ابتكاری طرح سوم (تبدیل RNS اصلاح شده) است كه می توانست بهبود بخش سرعت عملیات باشد. همانگونه كه گفتیم در اینجا از همان روش تبدیل RNS طرح سوم استفاده شده پس پیاده سازی هم دقیقاً مثل تبدیل RNS طرح سوم است. دو بخش دیگر یعنی تبدیل RNS ناقص (برای محاسبه T) و اصل طرح چهارم در زیر مورد بررسی قرار می گیرند.

6-5-1- تبدیل ناقصRNS

در این بخش در واقع فقط یك عملیات ضرب داخلی باید صورت بگیرد یعنی عملیاتی بشكل

پس در واقع به دو عنصر یكی ROM جهت ضرب در عدد ثابت Cverr و یك جمع كننده چند عملوندی احتیاج داریم. تعریف Cverr مشابه تعریف  در بخش 5-2-1 می باشد.

شكل 6-2: شكل بلوكی تبدیل ناقص RNS

6-5-2- پیاده سازی بخش اصلی طرح چهارم (الگوریتم مونتگمری):

حال پیاده سازی خود طرح چهارم را بررسی می كنیم. اصول كلی كار با نگاه به بلوك دیگرام طرح كه در شكل (6-2) آمده مشخص می شود. كل عملیات بسیار شبیه طرح سوم است با مقایسه آنها چند تفاوت مشاهده می شود كه در زیر بیان می شود یكی وجود یك تبدیل استاندارد RNS برای تبدیل q_w به q_v می باشد. درواقع در اینجا از شكل اصلی RNS استفاده شده و از RNS اصلاح شده استفاده نكردیم. ثانیاً در این طرح نیاز به یك ضرب جمع كننده پیمانه‌ای با اعداد ثابت داریم كه آنرا نیز پیاده كرده ایم و در نهایت استفاده از تبدیل RNS ناقص برای محاسبه خطا و كم كردن آن از نتیجه نیز در بلوك دیاگرام دیده می شود.

====================