بخشی از مقاله
چکیده
الگوریتم رمزنگاری AES یا رایندال - Rijndael - یکی از متداولترین الگوریتمهای رمزنگاری متقارن است. به علت قابلیتهای این الگوریتم، آن را میتوان بر روی بسترهای مختلفی ازجمله بر روی بسترهای سختافزاری پیادهسازی کردمعمولاً. در پیادهسازیهای سختافزاری افزایش گذردهی طراحی و کاهش میزان منابع مصرفی دو هدف اصلی میباشد. ازآنجاکه در این الگوریتم قسمت S-Box بخش بحرانی جهت دستیابی به این اهداف است، مقالات متعددی به ارائه راهکارهایی جهت پیادهسازی این بخش پرداختهاند.
این مقاله نیز به ارائه یک مدار ترکیبی بهمنظور پیادهسازی S-Box استفادهشده در تبدل جایگشت بایت در الگوریتم رایندال میپردازد. نتایج حاصل در مرحله Place & Route نشان میدهد که این معماری میزان 47 slices مصرف کرده و بیشترین فرکانس پالس ساعتی که قادر است با آن عمل کند بر روی تراشه Virtex4 FPGA - xc4vlx25 - ، برابر با 350.14 MHz میباشد. همچنین این نتایج با استفاده از نرمافزار بهدستآمده است.
-1 مقدمه
در سال 2001 میلادی الگوریتم رایندال به دنبال فراخوانی که NIST2 انجام داد، بهعنوان الگوریتم رمزنگاری استاندارد تصویب و جایگزین الگوریتم DES 3 شد.[1] در حالت کلی پیادهسازی رایندال به دودسته پیادهسازی نرمافزاری و پیادهسازی سختافزاری قابلتقسیم است. محدودیتهایی ازجمله وابستگی دادهها در طول پردازش، در اختیار نداشتن منابع موردنیاز در هرلحظه و خاصیت تکپردازندهایی و اجرای پیدرپی دستورها باعث میشوند که نتوان در پیادهسازی نرمافزاری الگوریتم رایندال به سرعتهای بالادست یافت.
همچنین در پیادهسازیهای سختافزاری این الگوریتم بسته به کاربردهای مختلف، راهکارهای متفاوتی میتوان ارائه نمود، راهکارهایی که میتوانند منجر به افزایش گذردهی شوند مانند [3,2]، و یا منجر به کاهش منابع مصرفی شوند مانند[6-4]، و یا منجر به کاهش مصرف توان شوند مانند.[7] در این الگوریتم بخش جایگشت بایت و معکوس آن4 پیچیدهترین بخش الگوریتم در عملیات رمزگذاری و رمزگشایی دادهها میباشد.
در این بخش هر یک بایت داده با یک بایت متناظر جایگزین میشود. درواقع این عمل جایگزینی با توجه به جدول S-Box 5 صورت میگیرد. لازم به ذکر است که جهت پیادهسازی سختافزاری این الگوریتم یکی از مهمترین بخشها در تعیین میزان گذردهی و مصرف منابع، همین بخش جایگشت بایت و یا بهعبارتدیگر نحوه محاسبه یک بایت جایگزین میباشد. به همین علت اکثر تلاشهای صورت گرفته باهدف کاهش مصرف منابع و افزایش گذردهی موتور رمزنگاری AES6 بر روی این بخش بوده است.
بهمنظور پیادهسازی سختافزاری این بخش و یافتن یک بایت جایگزین سه راهکار اولیه پیش رو میباشد. راهحل اول محاسبه تمامی مقادیر ممکن برای 8 بیت داده ورودی و ذخیره نتایج در یک جدول مراجعه LUT7 و پیادهسازی این جدول با استفاده از گیتهای داخلی FPGA8 می-باشد. راهحل دوم استفاده از بلاکهای حافظه در داخل FPGA و قرار دادن این جدول در این حافظه میباشد. راهحل سوم نیز پیادهسازی این بخش بهصورت مدار ترکیبی است، یعنی بهجای محاسبه مقادیر از پیش و قرار دادن نتایج در یک جدول، هر بار مقدار 8 بیت خروجی متناظر با 8 بیت ورودی را با استفاده از یک مدار ترکیبی محاسبه کنیم.
بهعنوان یک مقایسه میان این سه راهحل میتوان به این نکات اشاره کرد که راهحل اول در حین سادگی سریع است و میتواند با فرکانس بالاتری نسبت به راهحل دوم عمل کند اما نسبت به راهحل سوم کندتر میباشد. همچنین این راهحل به میزان زیادی منابع سختافزاری مصرف میکند و برای کاربردهای پرسرعت مانند اترنت مناسب نمیباشد. راهحل دوم نیز به دلیل استفاده از حافظهها و خصوصیات زمانبندی ویژه آنها برای خواندن، کندتر از راهحلهای اول و سوم است. راهحل سوم درواقع راهکاری است که یکی از طراحان این الگوریتم برای انجام محاسبات این بخش ارائه داده است .[8]
وی راهکاری بهینه برای انجام محاسبات این بخش در میدانهای مرکب GF - - 24 - 2 - و GF - - - 2 - 2 - 2 - بهجای میدان اصلی GF - 28 - پیشنهاد داده است. اهمیت این راهکار در این است که موجب کاهش پیچیدگی در انجام محاسبات این بخش میشود. ازجمله مزایای پیادهسازی این بخش بهصورت مدار ترکیبی این است که بسته به کاربرد میتوان چنین مداری را بهصورت چندطبقه خط لوله طراحی کرد تا به میزان فرکانس بیشتری دستیافت، هرچند که با افزایش رجیسترهای خط لوله میزان مصرف منابع نیز افزایش مییابد.
لازم به ذکر است که این راهحل در مقایسه با دو راهحل اول برای پیادهسازی سختافزاری بخش S-Box میزان منابع کمتری مصرف میکند و برای کاربردهای پرسرعت مناسب میباشد. همچنین محققان بسیاری بهمنظور دستیابی به مدار بهینه، به ارائه طراحیهای مختلفی از این بخش بر پایه محاسبات میدان محدود گالوا GF - 28 - و میدانهای مرکب معادل پرداختهاند. در ادامه برخی از این کارها را مرور میکنیم.
مقاله [9] به ارائه یک مدار ترکیبی از S-Box بر روی FPGA پرداخته است، نویسنده باهدف کاهش تأخیر به سادهسازی جدول درستی توابع منطقی پرداخته و S-Box را با استفاده از گیتهای پایه مانند AND، OR، NOT و مالتیپلکسر پیادهسازی کرده است. مقاله [10] یک طراحی مبتنی بر FPGA است که به ارزیابی سربار برای مقابله با حملات DPA9 در AES پرداخته است. مقاله [11] به ارائه یک پیادهسازی از S-Box با حداقل کردن هزینه محاسبات در میدان محدود GF - 28 - و حداقل کردن هزینه در نگاشت بر روی FPGA، پرداخته است.
نتایج این مقاله در طراحی S-Box با استفاده از میدان GF - - - 2 - 2 - 2 - نشان میدهد که بهاندازه %81 تعداد گیت کمتری در مقایسه با پیادهسازی LUT و به میزان %23 کارایی بهتری داشته و همچنین بهاندازه %3 در مقایسه با میدان GF - - 24 - 2 - سریعتر بوده است. مقاله [12] به ارائه یک S-Box بر پایه ریاضیات میدانهای ترکیبی مناسب برای معماریهای پرسرعت پرداخته است. مقاله [13] نیز بهمنظور کاهش توان داینامیک به پیادهسازی مدار ترکیبی معادلات ریاضی در تبدیل S-Box پرداخته است.
در این مقاله نیز ما با توجه به اهمیت بخش جایگشت بایت در الگوریتم رمزنگاری AES بهمنظور دستیابی به فرکانس بالا و درنتیجه گذردهی بالا در موتور رمزنگار، به ارائه مداری ترکیبی برای بخش S-Box میپردازیم و درنهایت نتایج حاصل از این طراحی را با برخی از کارهای صورت گرفته مقایسه میکنیم. در این مقاله پس از مقدمه، در بخش 2 معرفی قسمت جایگشت بایت آورده خواهد شد.
سپس در زیر بخش این قسمت توضیح مختصری در مورد میدان محدود گالوا خواهیم آورد. در بخش 3 به ارائه معماری پیشنهادی برای پیادهسازی S-Box بر روی FPGA پرداخته و درنهایت در بخش 4 به ارزیابی معماری ارائهشده و مقایسه نتایج باکارهای انجامشده میپردازیم. در بخش 5 نیز بهعنوان نتیجهگیری، مطالب مقاله مرور و پیشنهادهایی جهت بهبود و ادامه کار بیان خواهد شد. پسازآن نیز منابعی که در این مقاله از آنها استفادهشده است آورده میشود.
-2 تبدیل جایگشت بایت در الگوریتم رایندال
الگوریتم رمزنگاری رایندال شامل سه تبدیل مهم MixColumn - - و ShiftRow - - و SubByte - - است که اولی یک تابع جایگزینی غیرخطی و تأمینکننده امنیت سیستم است، دومی و سومی نیز توابعی خطی برای افزایش گسترش و اختلاط الگوریتماند. در این بخش تبدیل SubByte را موردبررسی قرار میدهیم. طراحی یک S-Box فشرده اساسیترین مشکل در طراحی سختافزاری این الگوریتم بهمنظور دستیابی به حداقل منابع مصرفی و حتی دستیابی به فرکانس پالس ساعت بالا میباشد. واحد SubByte با استفاده از جدول S-Box مقادیر ورودی را با مقادیر جدیدی جانشین میکند.
وظیفه این واحد انجام عملیات غیرخطی بر روی دادهها جهت امنیت سیستم است. همانگونه کهقبلاً نیز ذکر شد در این واحد با توجه به جدول S-Box هر یک بایت داده از ماتریس ورودی به یک بایت متناظر تبدیل میشود. لازم به ذکر است که در این الگوریتم کوچکترین واحد اطلاعات یک بایت و یا معادل هشت بیت است. درواقع در الگوریتم AES داده ورودی به بلاکهای 128 بیتی تقسیم میشود، هر بلاک داده نیز به 16 بایت تقسیمشده - یک ماتریس 4×4 از بایتها - و عملیات S-Box بر روی هر بایت بهصورت مجزا اعمال میشود. شکل - 1 - گویای این عملیات است.
جدول S-Box درواقع با اجرای دو عمل متوالی تولید میشود، ابتدا با انجام معکوس حاصلضرب در میدان محدود گالوا GF - 28 - بر روی داده ورودی و سپس با انجام تبدیل Affine بر روی نتایج حاصل از عملیات قبلی. در زیر نمایش ماتریسی این تبدیل آورده شده است. ازآنجاکه میدان گالوا زیرمجموعهای از مجموعه چندجملهایها میباشد، در این حوزه نیز اعداد بهصورت چندجملهای نشان داده میشوند. بهعنوانمثال مقدار {10001011}2 بر مبنای 2 با چندجملهای q7+q3+q+1 در میدان GF - 28 - نشان داده میشود. همانگونه که گفتیم از مهم-ترین عملیات در این بخش انجام معکوس حاصلضرب در میدان GF - 28 - میباشد.
در نمایش چندجملهای برای بایتها، عمل جمع دو بایت با XOR ضرایب جملههای همتوان انجام میگیرد. اما برخلاف عمل جمع که با XOR ساده انجام میگیرد، پیادهسازی عمل ضرب پیمانهای در میدان GF - 28 - بهسادگی قابل پیادهسازی در سطح بایت نخواهد بود. عمل ضرب چندجملهایها در میدان GF - 28 - بهصورت ضرب چندجملهای متناظر با بایتها در پیمانه یک چندجملهای تحویلناپذیر - m - x - - 10 از درجه 8 تعبیر میشود.
ازآنجاکه حاصلضرب دو چندجملهای که بزرگترین توان هر یک از آنها میتواند از مرتبه x7 باشد، حداکثر دارای درجه - x14 - 14 است، لذا باید حاصلضرب را به پیمانه m - x - کاهش داد تا در هشت بیت قابلنمایش باشد. همانگونه که میدانیم یکی از اصول الگوریتمهای رمزنگاری عدم افزایش حجم دادهها در طی فرآیند رمزگذاری میباشد. تحویلناپذیر بودن یک چندجملهای بدان معناست که نمیتوان آن را بهصورت حاصلضرب دو چندجملهای از درجه کوچکتر نوشت.
در اینجا لازم به ذکر این نکته است که تحویلناپذیر بودن m - x - ایجاب میکند که عمل ضرب وارونپذیر باشد. همچنین میدانیم که وارونپذیری یک اصل در الگوریتمهای رمزنگاری میباشد زیرا باید رمزگشایی دادهها تضمین شود. در رمزنگاری AES عمل ضرب دو بایت در میدان GF - 28 - به پیمانه m - x - =x8+x4+x3+x+1 که تحویلناپذیر است انجام میگیرد.
