|
تعریف
این الگوریتم یک رشته با طول متفاوت را به عنوان ورودی میگیرد و یک خلاصه پیام MD5 یا اثر انگشت با طول 128 بیت می سازد.
در این روش اینکه دو پیام مختلف دارای یک خلاصه پیام باشند پیش خواهد آمد (علت آن است که چون پیام های کوتاه طول یکسان دارند پس تمامی کلمات مثلا 400 حرفی نمیتوانند یک خلاصه منحصر بفرد داشته باشند چون تعداد پیام های کوتاه محدود به 2 بتوان طول خلاصه شده ها میباشد. اگر زمانی همه عبارات یک خلاصه مربوط به خود را بدست آورند که هرگز، در آن صورت شما میتوانید اطلاعات یک هارد 80 گیگابایت را در یک فلاپی ذخیره کنید !!!) ولی اینکه یک رشته از روی یک خلاصه پیام ساخته شود غیر ممکن میباشد. این الگوریتم برای امضاهای دیجیتال مناسب است، جایی که احتیاج به خلاصه کردن یک فایل بزرگ در یک رشتهء امن و فشرده، قبل از کد کردن آن متن، در سیستم های کدینگ، با کلید های خصوصی و عمومی آن سیستم مانند RSA (Rivest Shamir Adelman) الگوریتم MD5 برای داشتن سرعت بالا در ماشین های 32 بیتی طراحی شده است در عین حال احتیاجی به جانشینی ها در جداول بزرگ ندارد. این الگوریتم را با کدهای بسیار کمی میتوان نوشت.
الگوریتم MD5 توسعهای از الگوریتم MD4 میباشد با این تفاوت که MD5 کمی کندتر از MD4 عمل میکند اما در طراحی آن بسیار محافظه کارانه عمل شده است.
MD5 به این دلیل طراحی شد که حس کردند MD4 به علّت سرعت بالایی که داشت پذیرفته شده و از امنیت بالایی در شرایط بحرانی برخوردار نمیباشد. MD4 برای سرعت بالا طراحی شده ولی احتمال شکست آن در رمز کردنی موفق وجود دارد. MD5 کمی در سرعت کند شده با این تفاوت که بیشترین امنیت را داراست. این الگوریتم حاصل تأثیر دادن نظرات تعدادی از استفاده کنندگان MD4 به همراه مقادیری تغییر در ساختار الگوریتم برای افزایش سرعت و قدرت آن میباشد. الگوریتم MD5 در این مکان عمومی قرارگرفته تا از آن استفاده و در صورت امکان استاندارد شود. شرایط و نکات لازم
در این متن منظور از « کلمه» تعداد 32 بیت و «بایت» تعداد 8 بیت داده میباشد. یک صف از بیت ها دارای خصوصیات طبیعی یک صف از بایتها میباشند که هر گروه هشت تایی متوالی از بیتها یک بایت را تشکیل میدهند که پرارزش ترین بیت در ابتدا قرار دارد. یک صف از بایت ها دقیقا مشابه یک صف 32 بیتی از کلمات پردازش میشود. جایی که گروهی 4 تایی از توالی بایتها پردازش میشوند، کم ارزش ترین بایت اولین بایت میباشد.
اجازه بدهید از x_i بجای xi (x اندیس i ) استفاده کنیم و اگر مقدار اندیس یک عبارت محاسباتی بود آن را در {} محدود می کنیم، مانند: x_{i-1} . همچنین از ^ به عنوان علامت توان استفاده می کنیم، پس x^i یعنیx به توان i .
اجازه بدهید از علامت «+» برای اضافه کردن دو کلمه به هم استفاده کنیم. از x<<<5 به عنوان عملگر چرخش بیتی در کلمات استفاده میشود کهx به اندازه 5 بیت به چپ چرخش میکند.
از not (x) به عنوان عملگر نقیض بیتی، از X v Y به عنوان عملگر فصل (or) و از X xor Y به عنوان عملگر exclusive or و از XY به عنوان عملگر عطف (and) استفاده می کنیم.
توضیحات الگوریتم MD5
فرض کنید ما b بیت پیام به عنوان ورودی داریم و تصمیم داریم خلاصه پیام آن را بدست آوریم. b در اینجا یک عدد نا منفی و صحیح است، b میتواند مقدار صفر داشته باشد و هیچ محدودیتی برای مضرب هشت بودن آن نیست و به هر اندازه میتواند بزرگ باشد. فرض کنید بیت های این پیام را بشود به صورت زیر نوشت:
m0m1...mb − 1
برای آوردن خلاصه پیام 5 مرحله زیر را انجام می دهیم: اضافه کردن بیتهای نرم کننده: طول پیام مورد نظر به 448 به پیمانه 512 توسعه پیدا میکند به این معنی که اگر به طول پیام 64 بیت اضافه شود، طولش مضربی از 512 خواهد بود. عمل توسعه دادن همیشه اجرا میشود مگر اینکه طول پیام به صورت 448 به پیمانه 512 باشد.
عمل توسعه پیام یا نرم کردن آن به صورت زیر انجام میشود:
یک بیت [1] سپس تعدادی بیت [0] به پیام اضافه میشود.اضافه شدن بیت های 0 تا زمانی که طول رشته به 448 بر پایه 512 برسد، ادامه پیدا میکند. در این عمل حداقل یک بیت و حداکثر 512 بیت اضافه خواهد شد. افزایش طول:
یک نمایش 64 بیتی از b بیت پیام اولیه به آخر نتیجه گام قبل اضافه میشود. در بدترین حالت، b بزرگتر از 64 بیت خواهد بود. در این حالت فقط 64 بیت کم ارزش b استفاده خواهد شد.
هم اکنون طول پیام بدست آمده دقیقا معادل مضربی از 512 خواهد بود. مشابه اینکه بگوییم، این پیام طولی معادل مضربی از16 کلمه دارد اجازه بدهید M[0…N-1] را نمایانگر کلمات پیام بدست آمده بدانیم. (N مضربی از 16 میباشد.) تعیین بافر برای MD:
برای محاسبه خلاصه پیام یک بافر 4 کلمهای (A,B,C,D) استفاده میشود. هر کدام از A، B، Cو D یک ثبات 32 بیتی میباشند. این ثبات ها مطابق جدول زیر مقدار دهی میشوند ( بایتهای کم ارزش در ابتدا قرار دارند )
wordA:01234567
wordB:89abcdef
wordC:fedcba98
wordD:76543210 پردازش پیام در بلاک های 16 کلمه ای:
در ابتدا 4 تابع کمکی تعریف می کنیم که هر کدام به عنوان ورودی سه کلمهء 32 بیتی میگیرد و برای خروجی یک کلمهء 32 بیتی تولید میکند. F(X,Y,Z) = XYvnot(X)Z
G(X,Y,Z) = XZvYnot(Z)
H(X,Y,Z) = XxorYxorZ
I(X,Y,Z) = Yxor(Xvnot(Z)) در هر موقعیت بیتی، 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) مستقل و غیر مرتبط خواهند بود. توجه داشته باشید که تابع H، تابع XOR یا توازن بیتی از ورودی هایش است. این گام از یک جدول 64 عنصری T[1…64] ساخته شده از یک تابع مثلثاتی، استفاده میکند. اجازه دهید T[i]، I-امین عنصر جدول را مشخص میکند که برابر است با قسمت صحیح حاصلضرب 4294967296 در abs(sin(i))، به طوری که I به رادیان باشد. کارهای زیر را انجام می دهید:
/* Process each 16-word block. */
For i = 0 to N/16-1 do /* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */ /* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B
CC = C
DD = D /* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] /* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] /* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48] /* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64] /* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD end /* of loop on i */ خروجی:
خلاصه پیامی که به عنوان خروجی تولید میشود و عبارت است از A، B، C و D، که ما با کم ارزش ترین بیت A شروع می کنیم و به با ارزش ترین بیت D خاتمه می دهیم. این تعریف MD5 را کامل میکند. نتیجه
الگوریتم خلاصه پیام MD5 به سادگی قابل اجرا میباشد و یک "اثر انگشت" یا "خلاصه پیام" از پیام با طول اختیاری تولید میکند. گمان برده میشود که امکان مواجه شدن با دو پیام که خلاصه پیام مشابهی دارند از رتبهء 64^2 و برای هر پیامی که به آن یک خلاصه پیام داده شده است از رتبهء 128^2 میباشد.
الگوریتم MD5 *برای نقاط ضعف به دقت بررسی شده است. به هر حال این الگوریتم نسبتاً جدید است و تحلیل امنیتی بیشتری را طلب میکند، مشابه طرح های مشابه در این رده.
|
