تابع درهم‌ساز رمزنگارانه (به انگلیسی: Cryptographic Hash Function) (CHF)، تابع درهم‌سازی است که مناسب برای رمزنویسی است. در واقع یک الگوریتم ریاضی است که داده‌هایی با اندازه اختیاری یا متغیر (که اغلب «پیام» اطلاق می‌شوند) را دریافت می‌کند و به یک رشتهٔ بیتی با اندازهٔ ثابت (مقدار درهم، هش، «اثر انگشت» یا «خلاصه پیام») تبدیل می‌کند. یک تابع یک طرفه است و قابل برگشت نیست. MD5 و خانوادهٔ SHA، دو مورد از الگوریتم‌های معروف و پرکاربرد جهت Hash هستند.
MD5 مخفف Message-Digest algorithm 5 می‌باشد و این الگوریتم یک ورودی می‌گیرد و یک خلاصه پیام یا اثر انگشت با طول ۱۲۸ بیت تولید می‌کند. چون با هر ۴ بیت می‌توان یک رقم هگزادسیمال ایجاد کرد، بنابراین ۱۲۸ بیت MD5 را می‌توان به ۳۲ رقم هگزادسیمال تبدیل کرد. معمولا چکیده پیام‌ها به صورت هگزادسیمال نمایش داده می‌شوند. چون هر بیت ۲ حالت دارد (صفر یا یک) و MD5 یک اثر انگشت ۱۲۸ بیتی می‌سازد (یا هر رقم هگزادسیمال ۱۶ حالت دارد و MD5 یک اثر انگشت با ۳۲ رقم هگزادسیمال می‌سازد)، بنابراین ۲۱۲۸ (یا ۱۶۳۲) حالت وجود دارد؛ و طبق اصل لانه کبوتری اگر ۱ + ۲۱۲۸ دادهٔ مختلف داشته باشیم، احتمال بروز تصادم در آن صددرصد است.
SHA1 یک ورودی می‌گیرد و یک مقدار درهم ۱۶۰ بیتی خلاصه پیام را تولید می‌کند، که معمولا به عنوان یک عدد ۴۰ رقمی هگزادسیمال نمایش داده می‌شود. بنابراین طبق اصل لانه کبوتری اگر ۱ + ۲۱۶۰ دادهٔ مختلف داشته باشیم، احتمال بروز تصادم در آن صددرصد است.
SHA256 یک ورودی می‌گیرد و یک مقدار درهم ۲۵۶ بیتی خلاصه پیام را تولید می‌کند، که معمولا به عنوان یک عدد ۶۴ رقمی هگزادسیمال نمایش داده می‌شود. بنابراین طبق اصل لانه کبوتری اگر ۱ + ۲۲۵۶ دادهٔ مختلف داشته باشیم، احتمال بروز تصادم در آن صددرصد است.
کد زیر یک برنامه‌ی تولیدکنندهٔ خلاصه پیام MD5 است. این برنامه بدون استفاده از هرگونه کتابخانه‌ی تولیدکنندهٔ هش نوشته شده است.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
typedef union uwb
{
unsigned w;
unsigned char b[4];
} WBunion;
typedef unsigned Digest[4];
unsigned f0(unsigned abcd[]) {return (abcd[1] & abcd[2]) | (~abcd[1] & abcd[3]);}
unsigned f1(unsigned abcd[]) {return (abcd[3] & abcd[1]) | (~abcd[3] & abcd[2]);}
unsigned f2(unsigned abcd[]) {return abcd[1] ^ abcd[2] ^ abcd[3];}
unsigned f3(unsigned abcd[]) {return abcd[2] ^ (abcd[1] | ~abcd[3]);}
typedef unsigned(*DgstFctn) (unsigned a[]);
unsigned *calcKs(unsigned *k)
{
double s, pwr;
int i;
pwr = pow(2, 32);
for(i = 0; i < 64; i++)
{
s = fabs(sin(1 + i));
k[i] = (unsigned)(s * pwr);
}
return k;
}
// Rotate v Left by amt bits
unsigned rol(unsigned v, short amt)
{
unsigned msk1 = (1 << amt) - 1;
return ((v >> (32 - amt)) & msk1) | ((v << amt) & ~msk1);
}
unsigned *md5(const char *msg, int mlen)
{
static Digest h0 = {0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476};
// static Digest h0 = {0x01234567, 0x89ABCDEF, 0xFEDCBA98, 0x76543210};
static DgstFctn ff[] = {&f0, &f1, &f2, &f3};
static short M[] = {1, 5, 3, 7};
static short O[] = {0, 1, 5, 0};
static short rot0[] = {7, 12, 17, 22};
static short rot1[] = {5, 9, 14, 20};
static short rot2[] = {4, 11, 16, 23};
static short rot3[] = {6, 10, 15, 21};
static short *rots[] = {rot0, rot1, rot2, rot3};
static unsigned kspace[64];
static unsigned *k;
static Digest h;
Digest abcd;
DgstFctn fctn;
short m, o, g;
unsigned f;
short *rotn;
union
{
unsigned w[16];
char b[64];
} mm;
int os = 0;
int grp, grps, q, p;
unsigned char *msg2;
if(k == NULL) k = calcKs(kspace);
for(q = 0; q < 4; q++) h[q] = h0[q]; // initialize
{
grps = 1 + (mlen + 8) / 64;
msg2 = malloc(64 * grps);
memcpy(msg2, msg, mlen);
msg2[mlen] = (unsigned char)0x80;
q = mlen + 1;
while(q < 64 * grps) {msg2[q] = 0; q++;}
{
// unsigned char t;
WBunion u;
u.w = 8 * mlen;
// t = u.b[0]; u.b[0] = u.b[3]; u.b[3] = t;
// t = u.b[1]; u.b[1] = u.b[2]; u.b[2] = t;
q -= 8;
memcpy(msg2 + q, &u.w, 4);
}
}
for(grp = 0; grp < grps; grp++)
{
memcpy(mm.b, msg2 + os, 64);
for(q = 0; q < 4; q++) abcd[q] = h[q];
for(p = 0; p < 4; p++)
{
fctn = ff[p];
rotn = rots[p];
m = M[p]; o = O[p];
for(q = 0; q < 16; q++)
{
g = (m * q + o) % 16;
f = abcd[1] + rol(abcd[0] + fctn(abcd) + k[q + 16 * p] + mm.w[g], rotn[q % 4]);
abcd[0] = abcd[3];
abcd[3] = abcd[2];
abcd[2] = abcd[1];
abcd[1] = f;
}
}
for(p = 0; p < 4; p++)
h[p] += abcd[p];
os += 64;
}
if(msg2) free(msg2);
return h;
}
int main(int argc, char *argv[])
{
int j, k;
const char *msg = "Hello world!";
unsigned *d = md5(msg, strlen(msg));
WBunion u;
for(j = 0; j < 4; j++)
{
u.w = d[j];
for(k = 0; k < 4; k++) printf("%02x", u.b[k]);
}
printf("\n");
return 0;
}خروجی:
86fb269d190d2c85f6e0468ceca42a20
با اندکی تغییر در تابع main می‌توانیم کاری کنیم که یک توالی دلخواه در خلاصه پیام قرار گیرد. برای اینکار باید یک Salt به رشته اضافه کنیم و با آزمون و خطا به رشتهٔ هدف برسیم. به عنوان مثال می‌خواهیم رشته‌ای پیدا کنیم که شش رقم آخر خلاصه پیام MD5 آن 111111 باشد. برای اینکار تابع main زیر را با تابع main موجود در کد بالا جابجا کنید و سپس برنامه را اجرا نمایید.
int main(int argc, char *argv[])
{
char msg[200] = "Site: alef39.ir, a39.ir; Email: ab.roshan39@gmail.com; Salt: ";
char salt[50];
char str1[33];
char str2[] = "111111";
unsigned *d;
int i, j, k;
int msgLen = strlen(msg);
WBunion u;
i = 0;
while(str2[i])
{
str2[i] = tolower(str2[i]);
i++;
}
i = 0;
while(1)
{
char *buffer = str1;
sprintf(salt, "%d", i);
strcpy(msg + msgLen, salt);
d = md5(msg, strlen(msg));
for(j = 0; j < 4; j++)
{
u.w = d[j];
for(k = 0; k < 4; k++) buffer += sprintf(buffer, "%02x", u.b[k]);
}
printf("%d\n", i++);
// if(strncmp(str1, str2, strlen(str2)) == 0) break; // Search a string from head
if(strncmp(str1 + strlen(str1) - strlen(str2), str2, strlen(str2)) == 0) break; // Search a string from tail
}
printf("\nThe String is:\n %s\n\nThe MD5 is:\n %s\n", msg, str1);
return 0;
}خروجی:
The String is:
Site: alef39.ir, a39.ir; Email: ab.roshan39@gmail.com; Salt: 13135113
The MD5 is:
85689f80d6e9330b480bbf35fd111111
خواهید دید که برنامه بالا بعد از 13135113 (حدود ۱۳ میلیون!) چرخشِ حلقه، بالاخره به هدف می‌رسد؛ و رشته‌ای تولید می‌کند که شش رقم آخر MD5 آن 111111 است. اگر رشتهٔ زیر را درون Notepad ذخیره کنید و MD5 از آن بگیرید، نتیجهٔ آن را خواهید دید.
Site: alef39.ir, a39.ir; Email: ab.roshan39@gmail.com; Salt: 13135113
پایتون دارای کتابخانه‌ای به نام hashlib است، که بوسیلهٔ آن می‌توانید کد بالا را براحتی و تنها در چند خط، جهت approach مشابه در پایتون، پیاده‌سازی کنید.
import hashlib
i = 0
while True:
i = i + 1
msg = 'Site: alef39.ir, a39.ir; Email: ab.roshan39@gmail.com; Salt: ' + str(i)
md = hashlib.md5()
md.update(msg.encode('utf-8'))
hash = md.hexdigest()
print(i)
if hash[-6:] == '111111':
print('\nThe String is:\n', msg)
print('\nThe MD5 is:\n', hash)
breakشش رقم اول MD5 رشتهٔ زیر، 111111 است. این رشته بعد از 25705915 (حدود ۲۵ میلیون!) چرخش حلقه بدست می‌آید.
Site: alef39.ir, a39.ir; Email: ab.roshan39@gmail.com; Salt: 25705915
The MD5 is:
111111027536c2d063b503a2ceb08c19
سه رقم اول و همچنین سه رقم آخر MD5 رشتهٔ زیر، a39 است. این رشته بعد از 15664529 (حدود ۱۵ میلیون!) چرخش حلقه بدست می‌آید.
Site: alef39.ir, a39.ir; Email: ab.roshan39@gmail.com; Salt: 15664529
The MD5 is:
a3940f62e8671ab3e4d2836382e4aa39
کتابخانه‌هایی هم وجود دارند که دارای انواع مختلف الگوریتم، برای تولید خلاصه پیام هستند؛ و می‌توانید با استفاده از آن‌ها براحتی خلاصه پیام ایجاد کنید. یکی از این کتابخانه‌ها، OpenSSL است. در مثال زیر با استفاده از الگوریتم SHA256 موجود در این کتابخانه، هش (خلاصه پیام) تولید شده است.
شش رقم آخر SHA256 رشتهٔ زیر، 111111 است. این رشته بعد از 45859517 (حدود ۴۵ میلیون!) چرخش حلقه بدست می‌آید.
Site: alef39.ir, a39.ir; Email: ab.roshan39@gmail.com; Salt: 45859517
The SHA256 is:
77ea74439da4310257c8cdf999142344d1ac9d71a3edf7186fc740736a111111
برنامه‌های بالا درون فایل ضمیمهٔ زیر موجود هستند. همچنین در فایل ضمیمهٔ زیر با ارائه‌ی چند مثال، نحوهٔ استفاده از کتابخانهٔ OpenSSL نیز توضیح داده شده است.
MD5 checksum:
66ab53e8d6bdea3413fefd0f75588745 *Cryptographic-Hash-Function.zip
