Montgomery Part Three

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

حال برای شناخت بیشتر الگوریتم مونتگمری به بررسی این استفاده و در ابتدا آشنایی نسبی با الگوریتم رمز منحنی های بیضوی می پردازیم.

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

رمزنگاری کلید عمومی مبتنی بر اشکالات برخی از مسائل ریاضی است. در اوایل سیستم‌های مبتنی بر کلید عمومی با این فرض که پیدا کردن دو یا بیشتر از دو عامل اول بزرگ برای یک عدد صحیح بزرگ مشکل است امن تلقی می‌شدند. برای پروتکل های مبتنی بر منحنی بیضوی، فرض بر این است که پیدا کردن لگاریتم گسسته از یک عنصر تصادفی منحنی بیضوی با توجه به یک نقطه پایهٔ عمومی شناخته شده غیر عملی می‌باشد. اندازه منحنی بیضوی تعیین کننده سختی مسئله‌است. مزیت اصلی که توسط ECC وعده داده می‌شد یک کلید با اندازه کوچکتر بود، که این موضوع به معنی کاهش ذخیره سازی و انتقال مورد نیاز است، به این معنی که، یک سیستم منحنی بیضوی می‌تواند همان سطح از امنیت را که یک سیستم مبتنی بر RSA  با ماژول های بزرگ و طول بلند کلید فراهم می‌کند را ایجاد کند، به عنوان مثال، یک کلید عمومی ۲۵۶ بیتی مبتنی بر ECC می‌بایست امنیت قابل مقایسه‌ای با یک کلید عمومی ۳۰۷۲ بیتی مبتنی بر RSA داشته باشد. برای اهداف امروزی رمزنگاری، منحنی بیضوی یک منحنی مسطح است که متشکل از نقاط رضایت بخش معادله می‌باشد.

همراه با یک نقطه برجسته در بی نهایت (نشان داده شده به شکل ∞)(مختصات در اینجا از یک حوزه ثابت متناهی از مشخصه که با ۲ یا ۳ برابر نیست انتخاب می‌شوند، و یا اینکه معادله منحنی تا حدودی پیچیده تر خواهد بود.) این مجموعه همراه با عملیات گروهی از نظریه گروه بیضوی از گروه Abelian، با نقطه‌ای در بینهایت به عنوان عنصر هویت می‌باشند. ساختار گروه از گروه مقسوم علیه تنوع جبری زیرین ارث بری می‌کند. همانطور که برای دیگر سیستم‌های رمزنگاری کلید عمومی محبوب، بدون اثبات ریاضی برای امنیت ECC از سال ۲۰۰۹ منتشر شد. با این حال، آژانس امنیت ملی ایالات متحده ECC و از جمله طرح‌های مبتنی بر آن را در سوئیت B خود قرار داد، که مجموعه‌ای از الگوریتم‌های توصیه شده بود و با این کار این الگوریتم را تایید کرد و اجازه داد تا از آن برای حفاظت ازاطلاعات طبقه بندی شده و محرمانه با کلید ۳۸۴ بیتی استفاده شود. در حالی که حق ثبت اختراع RSA در سال ۲۰۰۰ منقضی می‌شد، سیستم‌های ثبت اختراع به شدت در حال ثبت برخی از ویژگی‌های تکنولوژی ECC بودند. هر چند برخی استدلال می‌کردند که امضای دیجیتال منحنی بیضوی استاندارد فدرال (ECDSA NIST FIPS 186-3) و برخی طرح‌های تبادل کلید قابل انجام مبتنی بر ECC (شامل ECDH) را می توان بدون نقض این حقوق نیز استفاده نمود.

منطق تقسیم پیمانه ای برای حل ضرب پیمانه ای در معادله های رمز منحنی های کروی :

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

چون پیمانه عددی فرد و اول است ، اگر Y عددی زوج باشد بزرگ ترین مقسوم علیه مشترک بین مقسوم علیه و پیمانه برابر بزرگ ترین مقسوم علیه مشترک بین نصف مقسوم علیه و پیمانه است و اگر عددی فرد باشد حاصل جمع یا حاصل تفریق آن با پیمانه بر 4  بخش پذیر خواهد بود و داریم :

 این دستورات تا زمانی که A=0 شود ادامه پیدا می کند. برای این منظور p  را برابر تعداد بیت های عدد A تعریف کرده و تا زمانی که مخالف صفر باشد دستورات بالا تکرار می شوند. در زیر به شبه کد الگوریتم اشاره شده است :

با توجه به الگوریتم بالا به راحتی می توان دید که

 همان طور که در فرضیات الگوریتم مشخص است gcd ( Y , M ) = 1 پس اگر A=0 باشد B=-1 یا B=1 خواهد بود. در مرحله نهایی الگوریتم

می باشد.

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

با دانستن gcd ( R . M ) =1 و با کمک گرفتن از دو عدد R به توان منفی 1  ( معکوس R در پیمانه M ) و M’ ( یک پیمانه کمکی ) به طوری که :

 اگر عدد صحیح X کوچک تر از M انتخاب شود ، آن گاه تبدیل یافته مونتگمری آن به صورت زیر می شود.

می توان ثابت کرد که مجموعه {i.R(modM) | 0<=i<=M-1 | } مجموعه کامل باقی مانده هاست. بنابراین یک رابطه یک به یک بین عددی که بین 0 تا M-1 است و مجموعه فوق وجود دارد. الگوریتم مونتگمری از این خاصیت استفاده کرده و روش سریع تری را برای ضرب پیمانه ای ارائه می کند. اگر X مد و Y مد را در نظر بگیریم ، رابطه ضرب مونتگمری به صورت زیر بیان می شود.

 و با دانستن قوانین

شبه کد الگوریتم مونتگمری پیمانه ای دو دویی به صورت زیر می باشد :

حلقه While پس از n  بار تکرار پایان می یابد. برای بهبود الگوریتم اول ، می توان از منطق استفاده شده در الگوریتم تقسیم پیمانه ای کمک گرفت. بنابراین یک شرط لازم است ، در واقع نیاز به چک کردن بیت های کم ارزش A است. در صورتی که دو بیت کم ارزش آن برابر صفر بود بدین معنی است که ، A بر 4 بخش پذیر است. در غیر این صورت اگر فقط کم ارزش ترین بیت آن صفر ( عدد زوج ) بود A بر 2 بخش پذیر است و در حالت سوم ، کم ارزش ترین بیت آن برابر یک ( عدد فرد ) است. در اعداد زوج A := A/2 یا A := A/4 خواهد شد. در صورت فرد بودن عدد با قرار دادن معادل حقیقی آن به حالات زیر می رسد :

برای حالاتی که مقدار حقیقی A  برابر 1 و -3 است ، در صورت جمع با عدد منفی یک و در غیر این صورت با کم کردن از عدد 1 مضربی از 4 خواهند شد. با قرار دادن عدد -1 در کم ارزش ترین بیت متغیر کمکی B می توان این قسمت از الگوریتم را پیاده سازی نمود.

 در الگوریتم ضرب مونتگمری بالا ، محاسبات تبدیل به یکسری عملیات جمع و تفریق و شیفت شد. الگوریتمی برای جمع نقلی بدون انتشار رقم نقلی مطرح می باشد. در این روش اعداد به صورت بیتی A = { a_n a_n-1 … a0 } و a_i  عضو -1 و صفر و یک نمایش داده می شوند و انجام عمل جمع هم به صورت بیت به بیت دو عدد بوده. در حالتی که دو بیت برابر باشند جمع معمولی و در غیر این صورت یعنی حالتی که یکی از آن ها صفر باشد با کمک متغیر کمکی C , S , Y   و S و Y ، C   نقطه در بالا و قرار دادن مقدار اولیه C=0 ، Y=Y و S=X . حاصل جمع S=X+Y به صورت جدول نمایش بیتی جمع سریع محاسبه می شود.

_در صورتی که دو بیت ورودی جمع کننده با هم مساوی ( طبق خاصیت CSA ) رقم نقلی فقط در مرحله بعدی اثر گذاشته و در کل مدار منتشر نمی شود ، در نتیجه تغییر خاصی ایجاد نکرده و جمع بیتی معمولی انجام می شود. مانند فرمول بالا ... . ولی اگر این دو بیت با هم برابر نباشند ، یکی از دو بیت صفر و دیگری یک یا منفی یک است ، تنها فقط وقتی تغییر روش داریم که یکی از دو بیت صفر و دیگری یک باشد که در این حالت هر دو بیت و بیت متناظر در S , Y , C با نقطه در بالا برابر یک شده و حاصل جمع در این مرحله هم برابر جمع دو بیت :

_تقریق بیتی با :

خواهد بود! برای واضح تر شدن کار مدار جمع کننده را در شکل زیر مشاهده نمایید :

 _{پس شبه کد} جمع سریع به صورت زیر خواهد بود :

_تصمیم گیری مبتنی بر کم ارزش ترین بیت A می باشد.

_و در غیر این صورت برای حالتی که A عددی فرد است  ، به مجموعه حالات زیر می رسد :

 در حالتی که A برابر -1 و یا 3 باشد. برای اینکه عدد مضربی از 4 باشد کافی است با عدد یک جمع شود. وقتی عدد A برابر 1 و منفی 3 باشد ، عدد با منفی یک جمع خواهد شد. برای درک سریع و کامل الگوریتم بهبود یافته ضرب مونتگمری با کمک جمع سریع مجموعه حالت جدول زیر را خواهیم داشت :

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

در دو بررسی فوق مشاهده کردید که چطور الگوریتم مونتگمری با انعطاف پذیری توانسته جای پایش را در دنیای معماری کامپیوتر باز کند! الگوریتمی که پیوسته برای کم تر کردن پردازش ها و سطح مقطع و هر سودی که از این دو پدید می آید در حال بهبود است.

الگوریتم مونتگمری در بسیاری از معماری های دیگر نیز کاربرد دارد که در این مقاله فرصتی برای بررسی آن ها پیش نیامد ، اما سازمان هایی مانند IEEE داکیومنت های بسیاری درباره آن ها منتشر نموده اند که این مقاله نیز با استناد و تکیه به آن ها و چند مقاله فارسی ترجمه شده از آن ها و همچنین ویکی پدیا پدید آمد.