هش (Hash, Hash Code, Digest, Message Digest هم نامیده می شود) را می توان به صورت اثر انگشت دیجیتالی یک داده در نظر گرفت. با این روش شما می توانید رشته ای اندازه-ثابت (fixed length) از یک داده به دست آورید که با روش های ریاضی به صورت "یک طرفه" رمزنگاری شده است. کشف رشته اصلی از رشته هش آن (عملیات معکوس) به صورت کارا تقریبا  غیر ممکن است. نکته دیگر اینکه هر داده یک رشته هش شده کاملا  منحصر به فرد ایجاد می کند( احتمال یکی شدن رشته های هش دو رشته متفاوت در الگوریتم MD5 یک در 3.4028236692093846346337460743177e+38 می باشد..  این خواص ، هش کردن را به روشی کارا و ایده آل برای ذخیره سازی کلمات عبور در برنامه های شما تبدیل می کند. چرا؟ برای این که حتی اگر یک نفوذگر(Hacker) بتواند به سیستم و بانک اطلاعاتی شما نفوذ کند و بخشی از اطلاعات شما را به دست آورد (شامل کلمات عبور هش شده) نمی تواند کلمات عبور اولیه را از روی آن ها بازیابی کند.

یکی از دو خصوصیت الگوریتم های   HASHاینه که معکوس پذیر نیستند! دومی اینه که هرگز دو ورودی متفاوت به خروجی یکسان منجر نمی شوند. هر یک از این دو خصوصیت اگر نقض بشه می گیم الگوریتم شکسته!!!

شناسایی اعضا با استفاده از Hash  

تا کنون نشان داده ایم که بازیابی کلمه عبور اصلی از روی رشته هش تقریبا غیر ممکن است ، خب چگونه برنامه های ما تشخیص دهند که کلمه عبور وارد شده توسط کاربر صحیح است ؟ به سادگی ! با تولید رشته هش کلمه عبور وارد شده توسط کاربر و مقایسه آن با رشته هش ذخیره شده در رکورد  بانک اطلاعاتی مربوط به کاربر می توانید متوجه شوید که آیا دو رشته با هم برابرند یا نه. بگذارید با ذکر یک مثال این بحث را ادامه دهیم.

Hashes are "digests", not "encryption"

Hash یک عمل خلاصه سازی (digest ) را روی جریان  ورودی انجام می دهد نه یک عمل رمز نگاری (encryption) .

Encryption داده را از یک متن صریح (Clear text) به یک متن برمز در آورده تبدیل می کند (Cipher text). encryption  ک عمل دو طرفه می باشد . که هرچه حجمClear text  بیشتر باشد حجم Cipher text نیز بیشتر می شود.

که این ارتباط در شکل زیر به خوبی بیان شده است:

 Encryption - a two-way operation

Hashe ها جریان داده ورودی را به یک خلاصه کوچک تبدیل می کنند. که این یک عمل یک طرفه(غیر قابل بازگشت) می باشد. و  جریان داده ورودی آنها با هر حجمی که باشد خروجی یک مقدار ثابت میشود.

شکل بعدی این ارتباط را در خلاصه سازی توسط الگوریتم  MD5  به خوبی نشان می دهد.

Hashing - a one-way operation

موارد استفاده از Hash  ها

Hash ها کلا موارد استفاده کمی دارند که ما در ادامه بحث آن ها را بیان می کنیم:

1.                  تشخیص درستی یک فایل Verifying file integrity

برای مثال زمانی که یک فایل با حجم بالا را دانلود می نماییم می توانیم با به دست آوردن مقدار MD5 آن فایل توسط دستور md5sum  و مقایسه آن  با مقدار Md5  داده شده توسط سایت مورد  نظر  از درستی فایلمان اطمینان حاصل کنیم.

2.hash  کردن کلمه عبور Hashing passwords

قبلا به طور مفصل بحث شد.

3.                  نشانه گذاری  اسناد به روش digitally (امضاهای digitally)

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

Collision (تصادم) در Hash

زمانی که مقدار  Hash  دو ورودی متفاوت یکسان باشند می گوییم Collision  رخ داده است.

اما تا کنون هیچ موردی از Collision دیده نشده است . این امر از این حقیقت  ناشی می شود که تعداد مقادیر یک الگوریتم  hash بسیار زیاد می باشند.برای مثال یک Hash  128 بیتی میتواند 3.4 x 10³⁸

مقدار ممکن داشته باشد.که معادل 340,282,366,920,938,463,463,374,607,431,768,211,456 میباشد.

انواع هش

• MD4 (128 bits, obsolete)
• MD5 (128 bits)
• RIPEMD-160 (160 bits)
• SHA-1 (160 bits)
• SHA-256, SHA-384, and SHA-512 (longer versions of SHA-1, with slightly different designs)

انواع مختلفی از الگوریتم های قوی هش کردن برای استفاده در برنامه های کاربردی موجود هستند، محبوب ترین آنها که مورد استفاده برنامه نویسان هستند MD5 و SHA-1(Secure hash algorithm)می باشند. سیستم های قدیمی تر از( DES(Data Encryption Standard استفاده می کردند. این روش 56 بیتی دیگر  یک روش قوی هش کردن محسوب نمی گردد. ، الگوریتم های قوی تری مانند SHA-256 و SHA-512  برای موارد خاص مانند امضاهای دیجیتالی توصیه می گردد ولی برای هش کردن کلمات عبوردر برنامه های امروزی SHA-1 هنوز سطح امنیت بسیار خوبی را فراهم می کند.

Hash Table

همانطور که در جستجوی دودویی دیده شد با استفاده از یک ساختمان داده به خصوص به اسم درخت جستجوی دودویی کارایی جستجو را بهبود بخشید یم.

 رسیدیم. O(logn) به جستجوی دودویی با O(n) در واقع از جستجوی خطی با

حال می خواهیم یک ساختمان داده جدید به نام جدول هش را معرفی کنیم که کارایی عمل جستجو را تا افزایش می دهد.O(1)

یک جدول هش از دو قسمت تشکیل شده : یک آرایه (جدول واقعی جایی که دادهایی که جستجو می شود  ) که به آن تابع هش می گویند.mapping function در آن ذخیره می شود ) و یک تابع  نگاشت (

اندیس های آرایه که  (integer space ) تابع هش نگاشتی است از فضای ورودی به فضای اعداد صحیح را مشخص می کند . به عبارت دیگر تابع هش روشی را فراهم می کند  برای اختصاص دادن اعداد به داده های ورودی به گونه ای که سپس داده  ورودی می تواند در اندیس آرایه مطابق باعدد تخصیص داده ذخیره شود.در ادامه مثالی در این رابطه  بیان می کنیم:

مثال را آغاز می کنیم. یعنی از رشته ها به عنوان داده هایی ابتدا با یک آرایه جدول هش از رشته ها که ذخیره و جستجو می شوند استفاده می کنیم . اندازه جدول هش را در این مثال 12 می گیریم.

The empty hash table of strings

در مرحله بعد ما به یک تابع هش نیاز دارم. راههای زیادی برای ساختن یک تابع هش وجود دارد. در حال حاضر یک تابع هش ساده را در نظر می گیریم. که یک رشته را به عنوان ورودی میگیرد. مقدار هش برگشتی از تابع برابر مجموع  کاراکتر های اسکی است که رشته ورودی را می سازند به پیمانه اندازه جدول:

int hash(char *str, int table_size)

{

               int sum;

               /* Make sure a valid string passed in */

               if (str==NULL) return -1;

               /* Sum up all the characters in the string */

               for( ; *str; str++) sum += *str;

               /* Return the sum mod the table size */

               return sum % table_size;

}

  اجرا می کنیم که مقدار 3 حاصل می شود.("Steve",12) تابع هش را باپارامتر های

.  را در جدول ذخیره می کنیم Steve  حال رشته

The hash table after inserting "Steve"

   اجرا میکنیم("Spark",12) تابع هش را با پارامتر های ."Spark"  بیایید رشته دیگری را امتحان کنیم:

که عدد 6 حاصل می شود. سپس آن را نیز در جدول ذخیره میکنیم.

The hash table after inserting "Spark"

  اجرا میکنیم . که این بار نیز مقدار 3 حاصل می شود.("Notes",12)  حال تابع هش را با پارامتر های

را نیز در جدول درج می کنیم. Notesرشته

A hash table collision

مشاهده می شود که  دو ورودی متفاوت مقدارهش  یکسانی دارند و هر دو عنصر باید در یک مکان در آرایه درج شوند که این مساله غیر ممکن است . و همانطور که قبلا نیز ذکر شد به این مساله تصادم گفته (linear probing) می شود. در رابطه با تصادم الگوریتم های زیادی وجود دارد از قبیل اکتشاف خطی  و زنجیرسازی جداگانه.

بررسی می کنیم. ر ا  (Separate Chaining) که ما در اینجا زنجیره سازی جداگانه

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

بیایید مثال بالا را این بار با ساختمان داده تغییر یافته مان بررسی نماییم :

Modified table for separate chaining

دوباره  Steve را با مقدار هش 3 به جدولمان اضافه میکنیم:

After adding "Steve" to the table

هم چنین Spark با مقدار هش 6 را نیز به جدولمان اضافه می کنیم:

After adding "Spark" to the table

حال Notes با مقدار هش 3 (همانند مقدار هش Steve) را اضافه می کنیم:

Collision solved - "Notes" added to table

مراحل جستجو مشابه با عمل درج در جئول می باشد. ما مقدار هش داده ای را که می خواهیم جستجو شود  را به دست می آوریم. سپس به ان مکان از آرایه می رویم. لیستی که از آن مکان سرچشمه می گیرد (آغاز میشود) را بررسی می کنیم. و می بینیم که چیزی که به دنبال آن هستیم در لیست وجود دارد یا نه .

=>تعداد مراحل O(1) می باشد.

زنجیره سازی جداگانه Separate chaining)  ) به ما این امکان را می دهد که مساله تصادم را در یک روش ساده و قدرتمند حل نماییم . با این حال هنوز مشکلاتی وجود دارد . حالتی را فرض کنید که تمام داده های ورودی دارای یک مقدار هش باشند. در این مورد برای جستجوی یک داده باید یک جستجوی خطی با O(n) در لیست  پیوندی انجام دهیم .  پس در بدترین حالت این روش O(n) را خواهیم داشت که احتمال آن بسیار کم است . در حال که در بهترین حالت و حالت متوسط O(1) را خواهیم داشت!

Hash رمزگذاری بدون بازگشت

تابع hash به تابعی مانند H میگویند که ورودی m را بگیرد و رشته‌ای با طول ثابت مانند h به عنوان خروجی بازگرداند. (h=H(m . اما وقتی که در زمینه رمزگذاری از hash نامبرده میشود باید خصوصیات دیگری هم داشته باشد.
-ورودی میتواند هر طولی داشته باشد
-خروجی طول ثابت دارد.
-محاسبه hash برای هر رشته ای باید نسبتا ساده باشد.
-یک طرفه باشد. فقط از m بتوان h را بدست آورد نه برعکس.
-و در نهایت اینکه یک به یک باشد. برای هر m یک h منحصر به فرد وجود داشته باشد. در صورتی که هیچ m و n ای وجود نداشته باشند که (H(m)=H(n باشد H قویا یک به یک است. ( فکر کنم با توجه به شرطهای اول و دوم و اصل لانه کبوتر بتوان گفت که این شرط امکانپذیر نیست اما احتمال تصادم در الگریتم‌هایی مانند MD5 خیلی کم است.)
خوب حتما متوجه شدید که یکی از الگریتم‌های معروف Hash الگریتم MD5 است.
اما وقتی نمیتوان عبارت رمز شده را رمزگشایی کرد این رمزگشایی چه فایده‌ای دارد؟
اگر کاربر بجای اینکه پسورد خودش را برای سرور بفرستد فقط hash آن را بفرستد چه اتفاقی می‌افتد؟ در حقیقت اطلاعاتی فرستاده شده که با گرفتن آن نمیتوان به پسورد اصلی دست پیدا کرد. و در طرف دیگ سرور پسورد کاربر را در بانک اطلاعاتی خودش ذخیره نمیکند بلکه فقط hash آن را نگه میدارد. به این ترتیب hash فرستاده شده با hash ذخیره شده مقایسه میشود و در صورت برابر بودن کاربر اجازه ورود دریافت میکند.
حال درصورتی که کسی به بانک سرور هم دسترسی پیدا کند نمیتواند پسوردها را بدزدد. اما یک مشکل کوچک هم هست. اگر کاربر پسوردش را فراموش کند سرور هم نمیتواند پسوردش را به او بدهد! مگر اینکه مانند Yahoo یک پسورد جدید برای کاربر درست کند.
این روش (احتمالا با کمی محکم کاری) در ویندوز NT هم برای ذخیره کردن پسورد استفاده میشود.
البته توصیه میشود که خود hash نیز قبل از فرستادن رمزگذاری شود (ترجیحا با یک الگریتم نامتقارن مانند RSA) که مهمانهای ناخوانده نتوانند از hash استفاده غیر مجاز کنند.

مثال کار کردن با این الگریتم ها در VB.Net را میتوانید download کنید.(بدون exe)

تفاوت Hash و Code و Encryption

عامه توسعه گران تفاوت Hash و Code و Encryption رو نميدونن و اغلب اين سه عنوان كه مطلقا" به هم ربطي ندارن بجاي ديگري بكار ميرن !

 Hash : هش يا چكيدهء پيام يا هر اسم ديگه اي كه روش ميگذارن ، روشي براي توليد چكيده و خلاصه از يك پيام ، فايل و ... است . هش با استفاده از قواعد و الگوريتمهاي مخصوص به خودش تلاش ميكنه ، از هر چيزي كه بهش داده ميشه ، يك چكيده با طولي هميشه ثابت توليد كنه . به عنوان مثال الگوريتم MD5 كه يكي از روشهاي متداول توليد هش است ، به ازاي هر نوع ورودي كه دريافت كنه ( چه يك حرف باشه چه يك فايل ده گيگا بايتي ) هميشه ، فقط و فقط 128 بيت خروجي توليد ميكنه . اين خروجي 128 بيتي ، تا وقتي فايل يا پيام تغيير نكرده باشه ، هميشه ثابت خواهد بود . نتيجه : استفاده از هش براي توليد چكيده ميتونه روش خوبي براي بررسي تغيير يا عدم تغيير در يك پيام يا فايل باشه . نتيجه بعد : خروجي توليد شده توسط يك الگوريتم هش هرگز به موجوديت اوليه قابل بازگرداني نيست . كاربرد : توليد امضاي ديجيتال . حوزه كاربرد : عموما" سيستمهاي مبتني بر PKI .

Code : كد يا درهم ريزي يا هر اسم ديگه اي كه روش ميگذارن ، از يك جفت الگوريتم تشكيل ميشه . اولي پيام يا فايل رو encode ميكنه ( مثلا" : غير قابل خواندن ) و دومي اون رو decode ميكنه ( مثلا" : قابل خواندن ) . يعني يك روش توليد و استفاده از Code هميشه از دو جزء متقارن تشكيل ميشه كه با داشتن يكي ، توليد اون يكي كار دشواري نخواهد بود . اگر شما يك فايل رو بگيرين و به هر كاراكتر 12 تا اضافه كنين و خروجي رو براي فرد ديگري بفرستين كه او با خوندن هر كاراكتر و كسر 12 تا از هر كدوم ، بتونه به فايل اصلي دست پيدا كنه ، شما coding انجام دادين . نتيجه : كد صرفا" شكل پيام يا فايل رو بصورتي متقارن تغيير ميده . نتيجه بعدي : كد لزوما از دو قسمت قرينه هم تشكيل ميشه . كاربرد : انتقال پيام يا فايل روي محيطهائي كه براي پردازش حروف و علائم از كدپيجهاي متفاوت استفاده ميكنن ، يا انتقال وصله هاي ايميلها و ... . حوزه كاربرد : انتقال اطلاعات .

نتيجه اول : هش و كد ارتباط مستقيمي با رمزنگاري ندارند . هيچكدام يك روش رمزنگاري محسوب نميشن و وجودشون در يك سيستم رمزنگاري الزامي نيست .

نتيجه دوم : هش به موجوديت اوليه قابل بازگرداني نيست . به هيچ وجه . كد به حالت اوليه قابل بازگرداني است . به سادگي .

Encryption : رمزنگاري ، به معناي تغيير شكل و محتواي يك پيام يا فايل با استفاده از حداقل يك الگوريتم و حداقل يك كليد است . نتيجه اوليه : تا وقتي حداقل يك كليد نداريم ، يعني رمزنگاري نداريم . روشهاي رمزنگاري بصورت عمده به دو دسته تقسيم ميشن . روشهاي متقارن و روشهاي غير متقارن .

روشهاي متقارن رمزنگاري : اين روشهاي از لزوما" يك الگوريتم و حداقل يك كليد استفاده ميكنن . مثال : DES

روشهاي غير متقارن : اين روشها از حداقل يك الگوريتم و حداقل دو كليد استفاده ميكنن . مثال : RSA .