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

پروژه کارشناسی ارشد

چکیده

- مقدمه

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

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

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

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

اثبات این که هر عدد صحیح موجود در محدوده، نمایش منحصر به فردی در این سیستم دارد به کمک قضیه باقی‌مانده های چینی(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 را پیاده‌سازی و با هم مورد مقایسه قرار دهیم. این مقایسه براساس حجم و تاخیر طرح ها می‌باشد. در پیاده سازی سعی شده است که از پیشنهادات مقالات جهت عناصر بکار رفته استفاده شود (بخصوص در دو طرح اول) و در مواقعی که پیشنهاد خاصی انجام نشده (مثل طرح های سوم و چهارم) پیشنهاد مناسب از لحاظ خود من انجام شده است.

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

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

این روشها را می توان به دو دسته کلی تقسیم کرد. در دسته اول ابتدا عمل ضرب به صورت کامل انجام می شود و سپس کاهش به پیمانه روی نتیجه آخر اعمال می شود. این روشها را Reduction After Multiplication (RAM) می نامند. در دسته دوم عمل کاهش به پیمانه در هر مرحله ضرب و با هر حاصلضرب جزئی انجام می شود که به این روشها Reduction During Multiplication (RDM) می گویند[38]. از میان طرحهای مورد نظر ما دو طرح اول به دسته اول و دو طرح بعدی به دسته دوم تعلق دارند.

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

در روش RDM چون روش کاهش به پیمانه به دفعات تکرار می شود باید این عمل را سرعت بخشید. یکی از تکنیک های پر طرفدار برای اینکار که در طرحهای ما نیز به کار رفته روش مونتگمری [2] در کاهش پیمانه است.

پیمانه N را در نظر بگیرید. عدد R را که نسبت به N اول است و N

function      REDC(T):

if

بدین ترتیب با به کارگیری عدد کمکی R، عمل کاهش T به پیمانه N سریعتر انجام می شود.

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

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

مجموعه اول:

از تعداد خاصی از پیمانه ها مثل  استفاده می کنند. در این مجموعه n می تواند مقادیر کوچک، متوسط و گاهی بزرگ داشته باشد. در پیاده سازی این طرح ها عمدتاً فقط از مدارات منطقی استفاده شده و از ROM استفاده نمی شود. در هر حال این طرحها به پیمانه های خاصی محدود هستند و به همین دلیل کاربردهای محدودی دارند[3]. به طور مثال می توان به طرحهای [13],[12],[11] مراجعه کرد.

مجموعه دوم:

توانایی کار با هر پیمانه ای را دارند ولی پیاده سازی این گروه، راه حلهایی بر اساس ROM دارند و معمولاً از مدارات منطقی دیگر استفاده چندانی نمی کند. اندازه حافظه با افزایش n به سرعت رشد می کند که طرح را برای پیمانه‌ای بزرگ غیر عملی می سازد. به طور مثال می توان طرحهای [10],[9],[8],[7] را ذکر کرد.

مجموعه سوم:

جهت پیمانه های متوسط و بزرگ طراحی می شوند. معمولاً به صورت هیبرید هستند و از عناصر ریاضی پایه مثل ضرب و جمع کننده های باینری که به صورت موازی عمل می کنند به همراه چندین ROM با اندازه کوچک و عناصری منطقی استفاده می کند. طرحهای مورد نظر ما در این دسته قرار می گیرند. همچنین می توان به طرحهای [18],[17],[16],[15],[14] اشاره کرد.

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

این طرحها از مقالات [6],[5],[4],[3] انتخاب شده اند. دو طرح با تکنیک RAM کار می کنند و از تکنیک های ابتکاری سود می جویند و امکان پیاده سازی دقیق و در سطح گیت آنها وجود دارد. دو طرح بعدی با هدف بهبود الگوریتم رمزنگاری RSA انتشار یافته اند و طرحهای ضرب برای RNS به روش RDM پیشنهاد داده اند.

3- طرح اول:

3-1- مقدمه

این طرح در مرجع [4] یعنی مقاله “RNS Arithmatic Multiplier for Medium and large Moduli”  بیان شده. در مقدمه آن اشاره شده است که طرحهای بر اساس ROM برای پیمانه های کوچک مفید هستند ولی برای پیمانه های متوسط و بزرگ باید از طرحهایی که هم از ROMهای کوچک و هم از عناصر ریاضی بهره می برند استفاده کرد که طرح مورد نظر چنین حالتی دارد.

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

برای ضرب پیمانه ای می توان از ضرب و تبدیل های متوالی استفاده کرد [21],[20] که اصلاً روش بهینه ای نیست. بهمین دلیل جستجو برای روشهای بهتر در جریان است. عمده کارهای انجام شده بر روی پیمانه های خاص مثل  یا پیمانه های کوچک می باشد [31]-[22]. طرح [22] پیاده سازی ضرب کننده ای است که پیمانه های آن اعداد اول بشکل k

مرجع [25] ضرب کننده با پیمانه های بزرگ به شکل () را مطرح کرد. [29] ضرب کننده پیمانه ای را مطرح کرده از Factored decomposition بهره گرفته و در آن پیمانه ها می توانند اعداد غیر اول باشد.

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

دو باقیمانده Y, X (Residue) را در نظر بگیرید هدف محاسبه |XY|m (حاصلضرب X و Y در پیمانه m) می باشد. هر دو عدد را می توان با n بیت نمایش داد:

که در آن ها n برابر است:

(فرمول در فایل اصلی موجود است)

و  و  بیت های باینری X و Y می باشند. حاصلضرب X و Y را می توان به صورت زیر نمایش داد.

با بسط عبارت فوق داریم:

که می توان نوشت:

(3-1)(فرمول در فایل اصلی موجود است)

حالا  را به صورت زیر تعریف می کنیم:

vj =                           (3-2)

بنابراین رابطه (3-1) به صورت زیر بازنویسی می شود:

                       (فرمول در فایل اصلی موجود است)                                                             (3-3)

و برای محاسبه  معادله بالا به صورت زیر در می آید:

                            (فرمول در فایل اصلی موجود است)                                                  (3-4)

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

شکل بلوکی سخت افزار این طرح را در شکل (3-1) مشاهده می کنید. همانطور که مشاهده می شود، طرح پیشنهادی در چهارطبقه پیاده شده است.

با دقت در رابطه (3-4) در می یابیم که برای پیاده سازی این طرح باید تمام  را محاسبه کرده و در انتها به صورت پیمانه ای با هم جمع کنیم. بررسی vj در رابطه (3-2) مشخص می کند که vj تعداد یک های نمایش باینری عبارت  می باشد.

(شکل در فایل اصلی موجود است)

شکل 3-1: شکل بلوکی طرح اول

پس برای محاسبه باید هر دو بیت  را با هم AND کنیم تا  ایجاد شود. پس برای هر vj، pj گیت AND مورد نیاز است که :

پس کل گیت های AND مورد نیاز در این طبقه برابر است با :

پس طبقه اول تمام بیت های X و Y را با هم AND می کند.

در مرحله بعد Pj بیت هر vj را به طبقه کدگزار (Encoder) اعمال می کنیم. هر کدگذار تعداد یک های موجود در ورودی خود را به صورت باینری محاسبه میکند. پس خروجی هر کدگذار به  بیت احتیاج دارد. با توجه به این که P1=1 و  می باشند، برای این دو حالت نیازی به کدگزار نیست. درنتیجه تعداد کل کدگزارهای مورد نیاز 2n-3 می باشد.

طبقه سوم، آرایه ای است از 2n-1، ROM .ROM موجود در محل jام خروجیهای j امین کدگزار را دریافت کرده و  را ایجاد می کند. در نتیجه خروجی این طبقه 2n-1 عدد در پیمانه m می باشد که باید با هم جمع شوند.

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

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

مساحت (A) بر اساس تعداد گیت های به کار رفته بیان می شود. در مورد ROM هم هر سلول حافظه یک گیت فرض می شود. واضح است که پیچیدگی یک تمام جمع کننده هشت گیت و یک مولتی پلکسر (2به1) سه گیت می باشد[19],[15].

برای محاسبه تأخیر، تأخیر هر گیت را Tg فرض می کنیم. برای ROM نیز زمان دسترسی به یک ROM،  بیت 2bTg درنظر گرفته می شود. تاخیر تمام جمع کننده 2.Tg  و تاخیر مولتی پلکس (2به1) هم 2.Tg فرض شده است [19],[15].

اولین طبقه شامل n2 گیت AND می باشد. در نتیجه مساحت آن n2 گیت و تأخیر آن Tg میباشد. طبقه دوم 2n-3 کدگزار با اندازه های مختلف دارد. هر کدگزار با Pj بیت ورودی حداکثر به اندازه Pj تمام جمع کننده یا هشت Pj گیت را اشغال می کند. تأخیر موردنیاز حداکثر  تأخیر یک تمام جمع کننده یا به طور متناظر PjT­g می‌باشد[33]. چون تعداد کل گیت های AND،  می باشد در نتیجه در این طبقه  تمام جمع کننده یا به طور متناظر گیت برای طبقه کدگزار مورد نیاز است. حداکثر تأخیر این طبقه مربوط به بزرگترین کدگزار که متناسب با Pj=n است می باشد در نتیجه تأخیر این مرحله nTg است.

سومین طبقه شامل 2n-1، ROM می باشد که هر کدام اندازه ای برابر  دارند. پس فضای حافظه موردنیاز برحسب گیت برابر است؛

تأخیر این مرحله بر حسب بدترین حالت مربوط بهPj=n میباشد، که برابر است با:

طبقه آخر طرح پیشنهادی یک MOMA است. همانطور که درمقاله [8] اثبات شده است، تعداد گیت های لازم برای این MOMA برابر است با :

و تأخیر این مرحله Tg.(4n+25) می باشد.

پس در جمع:

و تأخیر کلی برابر است:

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

                     (فرمول در فایل اصلی موجود است)                                   (3-5)

                          (فرمول در فایل اصلی موجود است)                           (3-6)