بخشی از مقاله
چکیده
MD5 یک روش رمزنگاری است که به عنوان تابع درهمساز رمزنگارانه استفاده میشود. این الگوریتم یک رشته با طول متفاوت را به عنوان ورودی میگیرد و یک خلاصه پیام امدی5 یا اثر انگشت با طول 128بیت میسازد. هش های MD5 به لحاظ تئوری مستقیما قابل برگشت نیستند اما راه هایی برای رمزگشایی پسوردهای MD5وجود دارد. الگوریتم های رمزنگاری هش یکی از مهمترین توابع در امنیت اطلاعات می باشد.
از مهمترین خصوصیات این توابع یک طرفه بودن آنهاست یعنی با روش معکوس نمی توان به متن اصلی رمز شده دست پیدا کرد.برای رمزگشایی از هش ها دو رو روش وجود دارد .اولین روش که به نام بروت فورس شناخته میشود ، در این روش مقادیر هش تولید میشوند و یک به یک با مقدار مورد نظر ما مقایسه میشوند .این روش زمان بر می باشدو با افزایش طول پیام زمان محاسبه هم افزایش می یابد.روش بعدی به نام روش معاوضه زمان-حافظه شناخته می شود دراین روش مقادیر هش از پیش محاسبه شده و برای جستجوهای بعدی ذخیره می شوداین روش به مقدار زیادی حافظه نیاز دارد.
واحد پردازش گرافیکی - - GPU در ابتدا جهت انجام کارهای گرافیکی کامپپیوتر و کم کردن کارهای CPU طراحی گردید ولی چندی بعد، به دلیل داشتن هسته های بسیار زیاد که هریک قادر به انجام کارهای کوچک ولی به صورت همزمان می بودند، جهت انجام کارهای محاسباتی پیشرفته نیز استفاده شد، به هممن دلیل، GPUها می توانند برنامه هایی که قادر به تفکیک به قسمتهای کوچک میباشند را به صورت موازی، با سرعت بیشتری نسبت به CPU اجرا کنند. برای برنامه نویسی بر روی GPU، از دو زبان برنامه نویسی CUDAو OpenCL استفاده میکنند.
CUDA یک معماری محاسبات موازی است که توسط شرکت Nvidia ارائه شده است و فقط بر روی کارت گرافیکهای همین شرکت اجرا میشود، که در سطح نرمافزاری، شامل یک سری دستورالعمل و در سطح سختافزار شامل موتور پردازش موازی در GPU است. CUDA هم واسطهای برنامه نویسی سطح پایین و هم واسطهای برنامه نویسی سطح بالا را فراهم میکند. به همین دلیل سرعت برنامه هایی که با CUDAنوشته میشود از زبان برنامه نویسی دیگر یعنی OpenCL بیشتر میباشد.در این مقاله ما سعی داریم پیاده سازی های مختلفی از معکوس MD5 ، را بر روی GPU بررسی کنیم.
-1 مقدمه
هش - - Hash, Digest, Message Digest را می توان به صورت اثر انگشت دیجیتالی یک داده در نظر گرفت. با این روش می توان رشته ای با اندازه-ثابت - fixed length - از یک داده به دست آورد که با روش های ریاضی به صورت "یک طرفه" رمزنگاری شده است. کشف رشته اصلی از رشته هش آن - عملیات معکوس - به صورت کارا تقریبا غیر ممکن است. نکته دیگر اینکه هر داده یک رشته هش شده کاملا منحصر به فرد ایجاد می کند. این خواص ، هش کردن را به روشی کارا و ایده آل برای ذخیره سازی کلمات عبور تبدیل می کند. در اینجا در مقالات بررسی شده الگوریتم های متعدد روش بروت فورس را با استفاده از GPU برای شکستن رمز MD5 مرور می کنیم.
-2 توضیحات الگوریتمMD5
فرض کنید ما b بیت پیام به عنوان ورودی داریم و تصمیم داریم خلاصه پیام آن را بدست آوریم b .در اینجا یک عدد نا منفی و صحیح است، bمیتواند مقدار صفر داشته باشد و هیچ محدودیتی برای مضرب هشت بودن آن نیست و به هر اندازه میتواند بزرگ باشد. فرض کنید بیتهای این پیام را بشود به صورت زیر نوشت: برای آوردن خلاصه پیام 5 مرحله زیر را انجام میدهیم.
:1 اضافه کردن بیتهای نرم کننده
طول پیام مورد نظر به 448 به پیمانه 512 توسعه پیدا میکند به این معنی که اگر به طول پیام 64 بیت اضافه شود، طولش مضربی از 512 خواهد بود. عمل توسعه دادن همیشه اجرا میشود مگر اینکه طول پیام به صورت 448 به پیمانه 512 باشد. عمل توسعه پیام یا نرم کردن آن به صورت زیر انجام میشود: یک بیت [1] سپس تعدادی بیت [0] به پیام اضافه میشود. اضافه شدن بیتهای 0 تا زمانی که طول رشته به 448 بر پایه 512 برسد، ادامه پیدا میکند. در این عمل حداقل یک بیت و حداکثر 512 بیت اضافه خواهد شد.
:2افزایش طول
یک نمایش 64 بیتی از b بیت پیام اولیه به آخر نتیجه گام قبل اضافه میشود. در بدترین حالت، bبزرگتر از 64 بیت خواهد بود. در این حالت فقط 64 بیت کم ارزش b استفاده خواهد شد. هم اکنون طول پیام بدست آمده دقیقاً معادل مضربی از 512 خواهد بود. مشابه اینکه بگوییم، این پیام طولی معادل مضربی از16 کلمه دارد اجازه بدهید M[0…1-1] را نمایانگر کلمات پیام بدست آمده بدانیم - N .مضربی از 16 میباشد.
:3تعیین بافر برای MD5
برای محاسبه خلاصه پیام یک بافر 4 کلمهای - A,B,C,D - استفاده میشود. هر کدام ازA ، B، Cو D یک ثبات 32 بیتی میباشند. این ثباتها مطابق جدول زیر مقدار دهی میشوند - بایتهای کم ارزش در ابتدا قرار دارند.
:4 پردازش پیام در بلاک های 16 کلمه ای
ابتدا 4 تابع کمکی تعریف میکنیم که هر کدام به عنوان ورودی سه کلمه 32 بیتی میگیرد و برای خروجی یک کلمه 32 بیتی تولید میکند. در هر موقعیت بیتی، Fبه عنوان شرط عمل میکند: اگر X آنگاه Y در غیر این صورت Z. تابع F میتوانست طوری تعریف شود که به جای استفاده از v از + استفاده کند چون XY و - not - X هرگز یکهایی در موقعیت بیتی یکسان نخواهد داشت. جالب است به یاد داشته باشید که اگر بیتهایX ، Yو Z مستقل و غیر مرتبط باشند، هر بیت از - F - X, Y, Z مستقل و غیر مرتبط خواهد بود. توابعG ، Hو I شبیه تابع F هستند، به طوری که آنها در "توازی بیتی" کار میکنند تا خروجی شان را از بیتهایX ، Yو Z تولید کنند. در چنین روشی اگر بیتهای متناظرX ، Yو Z مستقل و غیر مرتبط باشند، آنگاه هر بیت از - - G - X, Y, Z ، H - X, Y, Zو - I - X, Y, Z مستقل و غیر مرتبط خواهند بود.
:5خروجی
خلاصه پیامی که به عنوان خروجی تولید میشود و عبارت است ازA ، B، CوD ، که ما با کم ارزشترین بیت A شروع میکنیم و به با ارزشترین بیت D خاتمه میدهیم. این تعریف MD5 را کامل میکند. در ادامه سه مقاله از مجموعه مقالاتی که در زمینه پیاده سازی معکوس الگوریتم MD5 ارائه شده است، بررسی میگردد: 2-1 محاسبه MD5 و رمزگشایی آن با استفاده از openMP روی [1] GPU در این مقاله با استفاده از OpenMp الگوریتم چند نخی برای MD5 نوشته شده است.OpenMPیک API است که میتواند از برنامهنویسی چندپردازندهای بهصورت »حافظه اشتراکی-» - Shared memory - رویC++ ، C، فرترن و درمعماریهای مختلفی از جمله پلتفرمهای ویندوز و یونیکس پشتیبانی کند. البته، تولیدکنندگان کامپایلر برای زبانهای دیگر از جمله جاوا نیز امکان نوشتن برنامه با رابط OpenMP رافراهم کردهاند.
