انتقال پیام‌ها به شکل امن ، یعنی روشی برای رساندن پیام به صورتی که توسط مهاجم در بین راه غیر قابل فهم باشد یکی از دغدغه های همیشگی دنیای ارتباطات بوده و هست.
در طول تاریخ دو روش رمزنگاری ابداع شد. یکی روش رمز نگاری متقارن و دیگری نامتقارن. در روش رمز نگاری متقارن ، اطلاعات توسط یک کلید خصوصی کد می‌شوند و در طرف دیگر توسط کلید خصوصی مشابهی دی کد می شوند. و در شیوه نامتقارن ، رمزنگاری اطلاعات توسط کلید عمومی و خواندن آن‌ها توسط کلید خصوصی امکان‌پذیر خواهد بود.
یکی از الگوریتم های کلید نامتقارن امن RSA است.که کاربرد آن
انتقال اطلاعات محرمانه از
جمله کلید ها و امضای دیجیتال است. پیاده‌سازی های سخت
افزاری برای این
نوع رمزنگاری با استفاده از الگوریتم مونتگمری برای حساب مدولار انجام می شود.
موضوع بحث این مقاله به طور خاص الگوریتم
مونتگمری است.
در ابتدا با توضیح چرایی پیاده‌سازی RSA با الگوریتم مونتگمری ، الگوریتم را توضیح خواهیم داد.
توضیح این چرایی
در سؤالی اساسی‌تر نهفته است. چرا برای حساب
مدولار از الگوریتم مونتگمری
استفاده کنیم؟
حتماً تا به حال درباره راهبرد تیک و تاک اینتل شنیده اید.
راهبردی که کمپانی های
دیگری نیز از آن به شیوه‌های
مختلف و به اجبار برای همگام شدن با سیر سریع پیشرفت تکنولوژی استفاده می کنند. تیک بخش اول این استراتژی است و با معرفی یک نسل جدید که نسبت به نسل
پیشین معماری کوچک‌تری
دارد، عملیاتی می‌شود؛ برای مثال
آمدن معماری 32 نانومتری به جای 45 نانومتری جز راهبرد تیک است. و
تاک نیز با طراجی یک معماری جدید به وقوع می پیوندد. تیک و تاک مکمل یکدیگرند.
حال ببینیم که RSA چگونه باعث می‌شود که همان ترکیباتی که در فرآیند رمزنگاری استفاده می‌شوند قابل استفاده در فرایند رمزگشایی نیز باشند. یعنی یک راه دو طرفه داشته باشیم.
در‌واقع به همین دلیل است که برای پیاده‌سازی سخت افزاری RSA
از حساب مدولار استفاده می کنیم. زیرا
حساب مدولار دارای ویژگی جابه جایی پذیری است و دلیل آن تقارن در حساب مدولار است.
چون به دلیل
ویژگی جابه جایی پذیری، ماشین رمزگذاری هر
دو عملیات
رمزنگاری و رمزگشایی را در حداقل ممکن مساحت سخت‌افزار انجام می دهد و این کاهش مساحت باعث کاهش
هزینه‌های تولید ، کاهش
مصرف انرژی و کاهش وزن نهایی محصول ، زیبایی و در نهایت کوچکی محصول نهایی و کولینگ آسان‌تر خواهد شد.
بله ، الگوریتم ها و خلاقیت استفاده از
آن‌ها در هر محاسبه خاص در این حد تأثیر شگرفی بر فناوری و پیشرفت‌های فناوری دارند.
الگوریتم مونتگمری سریع‌ترین روش شناخته شده برای محاسبه توان پیمانه ای است که در سال 1985 توسط پیتر مونتگمری ابداع شد. پیتر مونتگمری در حال حاضر در بخش تحقیق و
توسعه مایکروسافت به عنوان محقق در گروه
رمزگذاری مشغول کار است.
کاربرد استفاده الگوریتم مونتگمری در RSA
به زبان ساده زمانی است که قصد داریم با استفاده از حساب‌های مدولار ، ضریب یا پیمانه های بسیار بزرگ را که گاهی به صدها بیت می‌رسند محاسبه کنیم.
در RSA عمل توان رسانی پیمانه ای برای رمز کردن و باز
کردن رمز به صورت زیر
استفاده می‌شود :
پس به ضرب های متوالی پیمانه ای احتیاج
خواهیم داشت.
به خاطر تأمین
امنیت RSA طول عملوند ها را بیش از 1024 بیت
در نظر خواهیم گرفت.
در نتیجه به دلیل
انجام محاسبه با عددهای
بزرگ دست یافتن به نرخ ارسال بالا در این شیوه محدود خواهد شد.
الگوریتم ضرب مونتگمری بهترین و سریع‌ترین روش برای حل این معادلات است. مکانیزم عمل الگوریتم مونتگمری به این صورت است که ضرب و محاسبه باقیمانده اش را به جمع و تقسیم بر توانی از دو تبدیل می کند و این نیز یکی از علت‌های دیگری است که نشان می‌دهد چرا این کار برای پیاده‌سازی سخت افزاری سودمند تر است.
برای بالا بردن سرعت در الگوریتم موتنگمری از معماری هایی استفاده می‌شود که انتشار رقم نقلی در جمع های انجام شده را کاهش دهد.برای مثال یک معماری
، جمع های موجود در الگوریتم
مونتگمری را به قسمت‌های q بیتی
تقسیم می‌کند و هر کدام از این قسمت‌ها با روش معمولی با هم جمع می شوند. و برای جمع کلی قسمت‌ها با استفاده از CSA از انتشار رقم نقلی در طول بیت‌ها جلوگیری می شود. و هر انتشار عدد نقلی فقط در q بیت خاص خودش انجام
خواهد شد.
سختی این روش یافتن مقدار مناسی برای q است. برای یافتن مقدار آن با توجه به پیاده‌سازی مقصد بایستی مقداری را تعیین نمود.
به همین دلیل این معماری انعطاف پذیری کمی دارد.
و نمی‌تواند گسترش
یابد. بهترین
روش استفاده از CSA
در الگوریتم
مونتگمری معماری پنج به دو است.چرا که علاوه بر سرعت بالا از انعطاف پذیری بسیاری نیز برخوردار است.
اگر تعداد بیت‌های عملوند K بیت
در نظر گرفته شوند ، آن گاه برای یک ضرب پیمانه ای در این معماری به
K+1 سیکل ساعت نیاز خواهیم داشت.
همه دستور العمل هایی که در حافظه فلش رام قرار دارند می بایست به اصطلاح فِتچ شوند. به قرار گرفتن دستورالعمل ها در حافظه و سپس فِتچ آن‌ها یک سیکل دستورالعمل می گویند.و هر سیکل دستورالعمل از تعدادی سیکل ساعت تشکیل می شود.
با توجه به اینکه
در هر سیستم دیجیتال اطلاعات
بین هزاران دروازه و حافظه و واحد های دیگر در جریان است و پالس ساعت هماهنگی آن‌ها را به عهده دارد ، نقش پالس ساعت و لزوم محاسبه آن بسیار پر‌رنگ است.
اینکه چه مدت زمان ، کلاک پالس یک
باشد و چه مدت صفر
، به نیازهای مدار و قطعات بر میگردد . معمولا کلاک پالس ۵۰ درصد یک هست و ۵۰ درصد صفر . حال طراحان
مدارهای الکترونیکی ، قطعات را طوری
طراحی می کنند که با هر بار یک شدن و یا
صفر شدن کلاک پالس ، اطلاعات جابه جا شود . به همین علت سرعت صفر و یک شدن کلاک پالس
اهمیت خواهد داشت .
از معماری پنج به دو می‌توان به
راحتی برای پیاده‌سازی یک سیستم رمز
RSA استفاده کرد اما در انتها چون نتیجه به صورت CSA نشان داده خواهد شد نیاز به مصرف پالس ساعت به اندازه طول عملوند جهت نیل به نتیجه
نهایی است.
با استفاده از واحد محاسبه ضرب
مونتگمری می‌توان این تعداد پالس را
به یک سوم و یک
ششم تبدیل نمود.
همان‌طور که در قبل نیز اشاره شد پیتر
مونتگمری برای محاسبه R=a.b mod n روشی را
مطرح کرد که به معادله مونتگمری مشهور شد.
در این روش به جای انجام محاسبه
در پیمانه n محاسبات را موقت در پیمانه دیگری به
نام r که در اینجا نسبت r به n اول
است و همچنین محاسبات در آن ساده‌تر است انجام می‌دهیم.
در این روش دو مقدار جدید آ پریم و ب پریم
با توجه به مقدارهای آ و ب که از n کوچک‌تر
هستند به صورت زیر تعریف می‌شوند :
و الگوریتم مقدار آر پریم را که مطابق شکل زیر است برمی گرداند :
آر پریم در اینجا بیان کننده معکوس آر در پیمانه
n می‌باشد. مشاهده می‌کنید که
خروجی الگوریتم به راحتی قابل
تبدیل به باقیمانده حقیقی است ، زیرا :
بنابراین می‌توانیم خروجی را در معکوس r ضرب کنیم تا تنیجه
نهایی را به دست آوریم. با
توجه به این مطالب الگوریتم ضرب مونتگمری به این صورت خواهد بود :
روش مونتگمری برای یک ضرب تنها کارایی شگفت انگیزی ندارد و کارایی خود را در ضرب های متوالی مانند آنچه در توان رسانی پیمانه ای است نشان می دهد.
الگوریتم مبنای دو مونتگمری برای محاسبه ضرب دو عدد
A و
B در پیمانه n روش بسیار کارآمدی در پیاده‌سازی سخت افزاری است.
در این روش اگر r را
دو بیت بیشتر از n در نظر بگیریم ، خواهیم توانست مرحله مقایسه با n را حذف کنیم و الگوریتم ساده شده زیر را به دست آوریم :
Kدر الگوریتم برابر تعداد بیت‌های عملوند ها می‌باشد
واضح است که طولانی‌ترین زمان مصرفی به دلیل انتشار رقم نقلی در طول بیت‌های زیاد مربوط به محاسبه زیر می‌باشد :
با استفاده از معماری CSA
می‌توانیم
این زمان را کوتاه و از انتشار رقم نقلی جلوگیری کنیم. حاصل جمع و رقم نقلی در سی اس ای به صورت زیر محاسبه می‌شوند :
No comments:
Post a Comment