خلاصه

ضرب روی میدانهای گالوا مهمترین عملگر در حوزه میدانهای محدود میباشد. معماریهای مختلفی برای پیادهسازی سختافزاری الگوریتم ضرب کنندهی میدان گالوای مبتنی بر چندجملهای های AOP بیان شده است که به مرور زمان شاهد ارتقای سطح کارایی آنها، افزایش سرعت و کاهش المانهای موجود در این معماریها بودهایم. با توجه به اهمیت ضرب کنندهها در میدانهای محدود، در این مقاله سعی شده است تا با استفاده از الگوریتمهای مبتنی بر چندجملهایهای AOP، معماریهایی که توانایی انجام عمل ضرب را به صورت کارا و بهینه دارند مورد مطالعه قرار دهیم. اکثر ضرب کنندههای میدان گالوای مبتنی بر چندجملهایهای AOP دارای ورودیهای بیت- سریال هستند که تأخیر در آنها بسیار زیاد است و مسیر بحرانی طولانی است. میتوان نشان داد که با تغییر ورودیهای بیت- سریال به بیت- موازی نیز سرعت انجام محاسبات بالا رفته و مسیر بحرانی آن کاهش پیدا خواهد کرد. در راستای این هدف به بررسی روشی خواهیم پرداخت که در آن با استفاده از تکنیک پردازش خط لوله، مسیر بحرانی را به مرتبه O(1) رسانده و تأخیر در مدار به مقدار قابل توجهی کاهش یافته است.

کلمات کلیدی: میدانهای گالوا، جملهایهای AOP، مسیر بحرانی، خط لوله

.۱ مقدمه

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

۱

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

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

محدود انجام میپذیرد. در ادامه به بررسی معماری بهینه و سریع ضرب کننده AB بر روی میدان گالوای مبتنی بر چند جمله ایهای [۵] AOP میپردازیم.

.۲ چند جمله ایها ی AOP

AOP ، چند جملهای هایی هستند که در میدانهای محدود GF(2m) کاربرد بسیاری دارند. یک AOP از درجهی m همهی جملات از x0 تا xm ، با ضرایب ۱ را دارا میباشد. و به شکل زیر نوشته میشود :

(۱)

همچنین m+1 باید یک عدد اول باشد.[۶] اگر α ریشهی P(x) باشد و P(x) یک چند جملهای تحویل ناپذیر (AOP) از درجهی m باشد ، به عبارتی:

(۲)

روی GF(2) میباشد. بنابراین هر به شکل پایهی چند جملهای نمایش داده میشود :

(۳)

(۴)

چون α ریشهی P(x) است داریم :

P(α) = ۰ (۵)

بر طبق رابطهی (۱) میتوان نوشت :

(۶)

با ضرب α در طرفین رابطهی بالا داریم :