بخشی از مقاله
طراحی و پیاده سازی یک پردازنده رمز برای الگوریتمهای رمز کلید خصوصی
چکیده
هلاف این مقاله طراحی و پیاده ساری پردازندهای ویژه الگوریتمهای رمر قطعههای کلید خصوصی است. بدین منظور ابتلا با آنالیر رفتاری پنج الگوریتمهای رمر کلید خصوصی فینالیست مسابقه ABS، عملیات اصلی و مورد تاکید آنها و عوامل موثر در افزایش باردهی اجرایشان شناسایی شسله است. نیر نقاط قوت و ضعف یکسری ار پردازندههای RISC همه منظوره در پیاده ساری عملیات اصلی الگوریتمهای رمزنگاری بررسی شده است. بر مبنای این ارربابیها، یک پردازنده رمر RISC با مجموعه دستورات ویژه عملیات رمزنگاری و واحدهای عملیاتی خاصی طراحی و پیادهسازی نسله که می تواند. در مورد الگوریتم Rijnddel، برنده مسابقه AESی با کاهش تعداد دستورات تا بیشری ار ۵۰%ر، به Speedttp می برابر ۲ برسد.
کلمات کلیدی: پردازنده خاصی، پردازنده رمز، AES، رایندا ل
۱. مقدمه
ایجاد ارتباط بین دو نقطه همواره می تواند مفاهیمی چون محرمانگی، درستی و دسترسی پذیری را به دنبال داشته باشد. هر چند مفهوم داشتن امنیت داده به زمان های بسیار دورتر از جهانی شدن ارتباطات بر میگردد، ولی امروزه با رشد و توسعه اینترنت، بزرگترین واسطه ارتباطی حاضر، و بوجود آمدن کاربردهایی نظیر تجارت الکترونیک و ... و در نظر داشتن اینکه همیشه بخشی از مسیر ارتباطی بین کاربرهای مختلف مشترک است اهمیت ارسال محرمانه و امن داده بیشتر مشخص می شود.
حجم بالایی از پردازش های مربوط به تامین این امنیت را رمزنگاری تشکیل میدهد. عمل اصلی در رمزنگاری، عمل رمر، یا تبدیل داده با معنی به فرم بدون معنی مشخص است. این کار به گونه ای انجام می شود که بدست اوردن داده اصلی از داده رمز شده برای غیر از گیرنده که پارامترهای رمز را نمیداند کاری مشکل و تا حدی نشدنی باشد. میتوان از الگوریتمهای رمز به عنوان یکی از اجزای اساسی سیستمهای اطلاعاتی نوین نام برد. با توجه به نیاز روزافزون به افزایش پهنای باند ارتباط امن و نیز اهمیت این الگوریتمها در کاربردهایی مثل کاربردهای نظامی و غیره، پیادهسازی بهینه و با بازدهی بالای این الگوریتم ها، ضروری و مهم بنظر میرسد. الگوریتمهای رمز به سه روش کلی پیادهسازی می شوند:
۱) کاملا نرم افزاری: در این روش الگوریتم به زبانهای سطح بالا مثل C، جاوا و... یا سطح پایین مثل زبان اسمبلی، نوشته شده و روی پردازنده های همه منظوره اجرا می شود {۱} و {۲]. از مزیتهای این روش می توان به سهولت و کم هزینه بودن پیادهسازی، داشتن قابلیت انعطاف در تغییر و بروزرسانی الگوریتم، جابجایی سریع بین الگوریتمهای گوناگون در یک سیستم امنیتی اشاره کرد. در مقابل سرعت اجرای پایین و امنیت فیزیکی کم بدلیل قابل دسترس بودن محل ذخیره کلیدها، از عیوب این روش است.
۲) کاملاً سختافزاری: در این روش، سختافزار ویژهای برای انجام تمام مراحل یک الگوریتم طراحی می شود. شاخصهٔ این روش، بالابردن سرعت رمزنگاری (تعداد بیت رمز شده در واحد زمان) است ۳ و ۴ از نکات مثبت این شیوهٔ پیادهسازی، بازدهی و امنیت بالا است که بدلیل ذخیره تمام دادهها به صورت فیزیکی در سختافزار عملاً دستیابی به آنها به طور مستقیم امکان ندارد. از معایب ان می توان به هزینهٔ بالا و غیر قابل انعطاف بودن ساختار پیادهسازی شده، طراحی مشکل و پرهزینه بودن پیادهسازی جابجایی سریع حین کار بین الگوریتم های مختلف اشاره کرد.
۳) پردازندههای رمز - Crypto ProceSSOr
در این روش پردازندههای ویژهای به منظور انجام عملیات رمزنگاری طراحی می شوند. در این ساختارها، کل وظایف یک سیستم رمز بین دو بخش نرم افزار و سختافزار تقسیم شده و واحدهای عملیاتی خاصی برای تسریع برخی از اعمالی که در الگوریتمها کاربرد بیشتری دارد پیادهسازی می شود. پردازندههای رمز را می توان به دو نوع اصلی تقسیم کرد: دسته اول، پردازنده هایی که به صورت سختافزارهای قابل پیکربندی طراحی می شوند. غالبا این پردازندهها از دو قسمت، یک هستهٔ نرم افزاری برای انجام عملیاتی مثل تولید کلید ارتباط با عملیات بیرون پردازنده و یک بخش سختافزاری برای انجام بخشی از یک یا چند الگوریتم رمز تشکیل شده اند [۵] و [۶. دسته دوم، نگاه مبنایی تری به پیاده سازی الگوریتم ها دارند. این دسته پردازندهها، مجموعه دستورات و معماری شان بگونه ای طراحی می شود که بتواند بازدهی خوبی بدست دهند [۷] و [۸ . نکته کلیدی در بدست آوردن بازدهی و کارایی در این ساختارها، ویژه کردن" است. معماری های خاص یک کاربرد با حذف جنبههای اضافی و خاص کردن طراحی پتانسیل زیادی برای افزایش بازدهی کاربردها دارند. بازدهی این نوع پیاده سازی ارتباط مستقیم با میزان خاصی کردن آن برای انجام یک وظیفه مشخص دارد. از این رو در سال های اخیر تاکید از پردازنده های همه منظوره به پردازنده هایی معطوف شده است که برای انجام عملیات خاص یک کاربرد بهینه شدهاند. بدین ترتیب پردازنده های ویژه یک کاربرد (ASP)، پردازنده هایی با معماری بهینه شده و مجموعه دستورات ویژه کاربرد، هم از قابلیت انعطاف پردازندههای همه منظوره در جهت ایجاد تغییرات دلخواه استفاده می کنند و هم اینکه با استفاده از بخشی از سختافزار که برای انجام عملیات خاصی تعبیه شده بازدهی و کارایی بالا میرود.ASP ها از معماری های مورد توجه امروزی هستند. هدف این مقاله، طراحی یک پردازنده خاص برای اجرای بهینه الگوریتم های رمزنگاری کلید خصوصی است. پردازنده ای که مجموعه دستورات و معماری بهینه ای برای اجرای این دسته از الگوریتمها داشته باشد. الگوریتمهای رمز کلید خصوصی که رمزهای کلید متقارن هم نامیده می شوند، از یک کلید مشترک برای رمز، تبدیل دادهٔ اصلی به دادهٔ غیر قابل تشخیصی، و ترجمه رمز، بدست آوردن داده اولیه از دادهٔ رمز شده، استفاده می کنند. این نوع الگوریتمهای رمز ارتباط بسیار سریعتری نسبت به نوع مقابلشان الگوریتم های رمز کلید عمومی یا رمزهای کلید نامتقارن، میتوانند ایجاد کنند. البته لازم است کلید خصوصی قبل از شروع یک ارتباط امن بین دو طرف ارتباط، به صورت امن مبادله شود. برای طراحی یک پردازنده خاص مراحل زیر باید طی شود: ۱. آنالیز کاربرد : برای بدست آوردن ویژگیهای شاخص و نیازهای ان در پیادهسازی سریع (بررسی رفتاری کاربرد). ۲. تعیین مجموعه دستورات : برای تامین نیازهای مشخص شده. ۳. تعیین ساختار معماری سیستم ۴. سنتز سختافزار: نوشتن کد، و بررسی آن از لحاظ صحت عملکرد، پس از این مقدمه در بخش دوم، با آنالیز رفتاری تعدادی الگوریتم رمز کلید خصوصی، شناختی از طبیعتشان بدست اورده، ویژگی های شاخص آنها را تعیین می کنیم، اینکه از چه جزه های عملیاتی تشکیل شدهاند و چه اعمالی در آنها مورد تاکید بیشتری است و ارزش بهینهسازی دارد. نیز بررسی می کنیم که این اجزا روی پردازنده های RISC همه منظوره چگونه اجرا می شوند تا نقاط قوت و ضعف این پردازندهها در اجرای الگوریتم های رمز بدست آید. با استفاده از این ویژگی ها و ارزیابی های انجام شده، در بخش سه پردازندهای RISC با مجموعه دستورات بهینه شده برای کاربردهای رمزنگاری ارائه شده و ساختار آن بررسی می شود. بخش چهارم به بررسی نتایج بدست آمده اختصاصی دارد.
۲ بررسی رفتاری رمزهای کلید خصوصی
الگوریتمهای رمز قطعه ای کلید خصوصی، ساختاری متقارن دارند. متن اولیه ورودی به این الگوریتم ها، ابتدا به بلاکهای داده با طولی های یکسان، مطابق با استاندارد الگوریتم، تقسیم می شود سپس عملیات رمز روی این قطعه های داده به طور مستقل از هم یا وابسته به یکدیگر، بسته به مد کاری و اهمیت کاربرد، انجام می شود. خروجی، بلاک دادهای برابر با طول قطعه ورودی است. از بین الگوریتم های موجود، پنج فینالیست مسابقه AES،]MARS,WOFISH,RIJNDAEL,RC6,SERPENT ۱۳] را به عنوان نمونه های شاخصی از الگوریتم های رمز قطعه ای کلید خصوصی که در رقابتی در تأمین امنیت، کارایی و بازدهی به برتریهایی نسبت به سایر الگوریتمهای کلید خصوصی رسیده اند مورد بررسی قرار خواهیم داد. هر چند عملیات به کار رفته در این الگوریتمها تمام حالات ممکن نیست ولی میتواند به عنوان نمونه هایی پرکاربرد، برتر و مورد توجه در نظر گرفته شوند. در ابتدا با انالیز الگوریتمها اجزای عملیاتی شان را مشخص می کنیم، نیز با دسته بندی عملیات درجه فراوانی هر عمل را بدست می آوریم تا شاخصه های اجرای الگوریتمها بدست آید. بدین منظور برای هر الگوریتم شبه کد اسمبلی با دستورات ساده و کاملا ابتدایی دو اپراندی که عموما در همه پردازندهها وجود دارد مثل دستورات منطقی (OR ،AND XOR و ... )، شیفت به چاپ و راست ثابت، دستورات مراجعه به حافظه Sub (add) -al, cl.ae clyst us (load, store) mmul) نوشته شده است. mmul یک دستور فرضی برای ضرب دو رجیستر ۳۲ بیتی به پیمانه"۲ است. از پیادهسازی های گوناگون هر یک از الگوریتمها، پیادهسازی بهینه برای پردازندههای ۳۲بیتی که در تعریف الگوریتمها امده، انتخاب شده است. همه ارزیابی ها برای رمز بلاک داده ورودی با طول ۱۲۸ بیت و ورودی کلید ۱۲۸ بیت انجام گرفته است. داده ورودی و زیر کلیدهای لازم در رجیسترها فرض شده و از عملیات مربوط به اماده سازی آنها صرفنظر شده است. برای بدست اوردن ماگزیمم بهینه سازی در این مرحله تعداد رجیسترها را نامحدود فرض می کنیم. ارزیابی به صورت دستی انجام گرفته و دو هدف اصلی را دنبال می کند: ۱. اجزای عملیاتی کلی تشکیل دهنده یک الگوریتم چیست و سهم هر یک از آنها در رمز یک بلاک داده چقدر است ۲. چه دستوراتی برای انجام هر عملی از اجزای کلی تشکیل دهنده الگوریتم لازم است و تعداد انها چقدر است نمودار شکل ۱ اعمال اصلی تشکیل دهنده الگوریتم و نسبت بین دستورات لازم برای اجرای آنها را نشان میدهد. بطور مثال در مورد الگوریتم رایندال در پیادهسازی ویژه این الگوریتم برای پردازنده های ۳۲ بیتی فقط از دو عمل SbOX و دستورات منطقی استفاده شده که از این میان حدود ۷۸٪ کل پردازشی مربوط به عملیات SbOX است. این دو عمل با استفاده 4-3 L XOR 3 AND shift load 2:l) ei lx | فراوانی مشخص شده پیادهسازی شدهاند. یا الگوریتم RC6 از چهار دسته عمل ضرب پیمانه ای، دوران وابسته به داده، جمع و عملیات منطقی تشکیل شده است.
شکل ۱: اجزا عملیاتی تشکیل دهنده الگوریتمها
با توجه به نتایج، عملیات اصلی که در الگوریتمهای رمز کلید خصوصی وجود دارند را میتوان به انواع زیر تقسیم کرد: - عملیات دسترسی به حافظه (LOad/Store) : قسمت عمده این عملیات مربوط به جداول Sbox" و قرار دادن مقادیر جداول از حافظه به رجیسترهاست. سهم کمتری هم مربوط به قرار دادن بلاک های داده و زیر کلیدها از حافظه در رجیسترها پردازنده و ذخیره کردن بلاک رمز شده خروجی (گاه ریز کلیدهای محاسبه شده) از رجیستر به حافظه است. - عملیات منطقی : XOR یکی از عملیات مهم و ساده در ایجاد آشفتگی در الگوریتم های رمز است که برای نویزی کردن داده و بالا بردن مقاومت در برابر حملهٔ جستجوی کلید استفاده می شود. اعمال دیگر مثل AND و OR و ... که برای عملیات استخراج بیتها و ... بکار می روند. - عملیات ریاضی: جمع و تفریق: این عملیات به صورت پیمانهای انجام می شوند. مانند XOR از عملیات سادهای هستند که آشفتگی را در دادهها ایجاد می کنند.
ضربا: دو نوع ضرب پیمانهای صحیح و ضرب گالوافیلد در الگوریتم ها استفاده می شود. ضرب از جمله عملیاتی است که امنیت بالایی را به الگوریتم میدهد زیرا آنالیز یک حاصل ضرب به دو کلمهٔ داده عملیات سختی است. اما از آنجا که چه در پیادهسازی نرمافزاری و چه سختافزاری، ضرب عمل هزینه بری است، طراحان الگوریتم برای بالا بردن بازدهی و سرعت الگوریتمهای خود کمتر یا به شکلهای سادهتر آنرا بکار می گیرند. بطور مثال در الگوریتم رمز MARS، ۲۶ ضرب به پیمانه "۲ انجام می شود که در مقایسه با IDEA هم تعداد به نصف رسیده و هم در پیمانه سادهتری (۱+۲) انجام میگیرد. - دوران و شیفت : دو نوع وابسته به داده و ثابت از دوران و شیفت در الگوریتم ها استفاده شده است. این عمل در ترکیب با عملیات ریاضی (مثل جمع) میتواند مقاومت مناسب و مؤثری در برابر تحلیل رمز خطی یا تحلیل رمز تفاضلی ایجاد کند. شیفت و دوران وابسته به داده در برخی از پردازنده ها پیادهسازی نشده و با ترکیبی از چند دستور اجرا می شود ولی شیفت و دوران ثابت از جمله عملیاتی هستند که غالبا در مجموعه دستورات اکثر پردازنده وجود دارند. عمل شیفت در پیادهسازی الگوریتمها غالباً برای جابجایی بیتهای داده برای قرار گرفتن در موقعیت مناسب (مثلاً استخراج بایتهای خاص) هم بکار میرود. - Permutation : یکی از روش های ایجاد آشفتگی در الگوریتمهای رمز، جابجایی بیتها و بدست آوردن ترتیب مشخص دیگری از آنهاست. این عمل بدلیل زمانبر بودن در الگوریتمهایی که اخیراً طراحی می شوند کمتر استفاده می شود. در مجموعه دستورات پردازنده ها هم کمتر به چنین دستوری پرداخته شده است. در پیادهسازی نرمافزاری، سادهترین راه جابجایی یک یک بیتهاست. با پردازندههای -Word Oriented امروزی انجام این عمل در سطح بیت با چهار دستور برای هر بیت انجام میشود: تولید MaSk برای تعیین موقعیت بیت، AND با رجیستر مبدا جهت استخراج بیت، Shift به موقعیت جدید و OR با بیتهای قبلی رجیستر مقصد. در برخی پردازندهها دستوراتی برای عملیات بیتی در نظر گرفته شده است، مثل EXtract یا DepOSit در پردازنده -PA RISC که به وسیله آنها می توان با دو دستور یک بیت را جابجا کرد. به این ترتیب، برای انجام عمل جابجایی روی یک رجیستر n بیتی به 2n تا 4n دستور نیازمندیم. هر چند اعمال جابجایی خاصی می توانند با دستورات کمتری انجام شوند. یک راه کاهش دستورات، استفاده از جداول LOOkup است. برای انجام عمل جابجایی روی رجیستر n بیتی که به m قسمت تقسیم شده به m جدول با ۲۶ خانه n بیتی نیاز است. تعداد دستوراتی که از این روش استفاده می کند بستگی به تعداد بخش ها دارد. هر چه تعداد بخش ها کمتر باشد دستور کمتری لازم است ولی در عوض میزان حافظه مورد نیاز جداول بالاتر میرود. این روش هر چند روش سریع تری نسبت به حالت قبلی است ولی در پردازنده های همه منظوره بدلیل مسائل مربوط به حافظه، نبودن داده در حافظه نهانگاهی، ممکن است سیکل های
بیشتری تلف کند و زمانبر باشد. R. Lee برای اولین بار دو دستور MiX و PerTmute را ویژه این عملی ||۱۴|| مطرح کرد. او در [۱۵] و [۱۶]، چند دستور دیگر نیز برای انجام جابجاییهای در سطح بیت برای کاربردهای مولتیمدیا و رمزنگاری معرفی کرده است. سریع ترین و پربازده ترین دستور برای اعمال رمزنگاری، دستوری به نام GRP است که میتواند جابجایی ۳۲ بیتی را در حداقل پنج سیکل انجام دهد و قابل پیاده سازی روی پردازندههای همه منظوره و پردازنده های رمز خاصی است. تنها عیب ان مصرف زیاد سختافزار است. - اعمال کنترلی پردازنده : مثل Branch وJump که برای کنترل مسیر برنامه استفاده می شود. همانطور که از نمودار شکل ۱ مشخص است، در هر یک از الگوریتمها برخی عملیات مهمتر از بقیه هستند و حجم بیشتری از کل پردازشی مربوط به رمز یک بلاک داده را به خود اختصاص میدهند. به طور مثال در الگوریتم MarS دو عملی تبدیل SbOX و چرخشی وابسته به داده، در RC6 ضرب و چرخشی وابسته به داده، در TWOfish عملیات SbOX فراوانی بالایی دارند. الگوریتمی مثل Rijndael نیز که کاملا وابسته به SbOX است. در مورد الگوریتم Serpent هر چند با توجه به نمودار این الگوریتم از دستهٔ وابسته به SbOX بنظر میرسد ولی SbOXها با توابع جبر بول نیز پیادهسازی می شوند. به همین دلیل معمولا این الگوریتم را نمی توان بطور مشخص متعلق به این دسته دانست. بنابراین پیاده سازی بهینه و سریع هر یک از این اجزا عملیاتی موثر در یک پردازنده ۳۲ بیتی میتواند اثر قابل ملاحظهای در اجرای سریع الگوریتمها داشته باشد. Mars » Twofish Rijndael Uka U-KU1 2 که بخش عمده ای از عملیاتشان را SbOX ها تشکیل میدهند شیوه دسترسی به حافظه داده در یک پردازنده یا افزایش پهنای باند اهمیت زیادی در افزایش نرخ خروجیشان دارد. در مورد الگوریتمهایی نظیر RCO که درصد عملیات محاسباتی مثل جمع، ضرب ، دوران و... در آنها بالاست وجود سخت افزارهای سریع و برای انجام این عملیات در یک پردازنده مهم است. در ۱۷] بررسی کاملی از اثر مدهای مختلف آدرس دهی در یک پردازنده روی سه الگوریتم TWOfish Rijndael و MarS شده است. نشان داده شده که به طور مثالی برای الگوریتمی مثل Rijndael اگر سه عمل مربوط به محاسبه آدرس موثر(استخراج بایت اندیس از رجیستر، اضافه شدن اندیس به اندازه مناسب در جداولی که سایز هر خانه اش بزرگتر از یک خانهٔ حافظه داده باشد، Scaling و جمع با آدرس پایه، آدرس خانه صفر SbOX) و استخراج داده یک خانه از جدول به
جای استفاده از چهار دستور با یک دستور و در یک کلاک انجام بگیرد نرخ خروجی تا ۲/۳ برابر می شود. از جهت دیگر در بررسی که از اجرای این الگوریتمها روی پردازنده های RISC همه منظوره موجود انجام دادیم، با عواملی محدود کنندهای بدلیل خاصی نبودن واحدهای اجرایی برمیخوریم. به عنوان مثال در مورد عمل دوران ، در برخی از پردازنده ها این عمل باید با دستورات شیفت شبیه سازی میشود مثل مجموعه دستورات SPARCV9 در پردازنده - ULTRA SPARC و یا در پردازنده Alphal که در این صورت حداقل سه سیکل صرف می شود. در پردازنده Itanium [۱۸] دوران یا شیفت متغیر در واحد MMX آن انجام می شود که بجز جابجایی داده سه سیکلی latency دارد. در پردازندههای RISC موجود عمل ضرب یا در واحد مخصوص ضرب کننده انجام می شود که در پردازنده Alpha هفت سیکل طول میکشد و یا اینکه با استفاده از شیفت و جمع های متوالی و یا با استفاده از دستورات ویژه مولتی مدیا انجام می گیرد(Itanium). که در همه این موارد سیکلهای زیادی تلف می شود. مشکل اصلی این پردازندهها در مورد SbOX نبودن داده در حافظهٔ نهانگاهی است که بین ۳ تا ۵ سیکل یا بیشتر (بسته به نوع پردازنده و سطح بندی حافظهٔ نهانگاهی) زمان تلف می کند. در مقابل می توان به نکات مثبتی در اجرای الگوریتم ها روی پردازنده های RISC همه منظوره نظیر برخوردار بودن از قابلیت موازی سازی و تعداد iSSue بالای دستورات ها مثل 64-LA تعداد زیاد رجیسترهای همه منظوره که اثر مهمی در کاهش میزان دستیابی به حافظه دارد، داشتن دستورات با سه عملگر ورودی پردازنده ARM و داشتن مجموعه دستورات ویژه، مثل دستورات ویژه مولتی مدیا با امکان عملیات موازی روی یک کلمهٔ پردازنده زیر اشاره کرد. الگوریتم های رمز در رابطه با دستورات شاخه رفتار متفاوتی نسبت به سایر کاربردها نشان میدهند، ساختار این الگوریتمها به گونه ای است که غالبا نیازی به استفاده از دستورات شاخه برای پیادهسازی عملیات یک مرحله رمز ندارد و فقط برای کنترل تعداد مراحل اجرا شده در انتهای هر مرحله استفاده می شوند، برای یک الگوریتم n مرحله ای، دستور شاخه انتهایی، 1-n مرتبه پذیرفته شده و یک مرتبه Not Taken می شود، مثلا در الگوریتم های طراحی شده AES، که تعداد مراحل 10=n است در ٪۹۰ حالات دستور شاخه انجام می شود.بدین ترتیب با بکارگیری تکنیکهای ساده پیش بینی دستورات شاخه مثل BTB" یا BPB" می تواند در ٪۸۰
