Ehsan M
16th February 2012, 03:43 PM
هش چیست؟
هش (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 ها کلا موارد استفاده کمی دارند که ما در ادامه بحث آن ها را بیان می کنیم:
تشخیص درستی یک فایل Verifying file integrity
برای مثال زمانی که یک فایل با حجم بالا را دانلود می نماییم می توانیم با به دست آوردن مقدار MD5 آن فایل توسط دستور md5sum و مقایسه آن با مقدار Md5 داده شده توسط سایت مورد نظر از درستی فایلمان اطمینان حاصل کنیم.
hash کردن کلمه عبور Hashing passwords
قبلا به طور مفصل بحث شد.
نشانه گذاری اسناد به روش digitally (امضاهای digitally)
که نحوه انجام ان به وضوح در شکل زیر نشان داده شده است:
Collision (تصادم) در Hash
زمانی که مقدار Hash دو ورودی متفاوت یکسان باشند می گوییم Collision رخ داده است.
اما تا کنون هیچ موردی از Collision دیده نشده است . این امر از این حقیقت ناشی می شود که تعداد مقادیر یک الگوریتم hash بسیار زیاد می باشند.برای مثال یک Hash 128 بیتی میتواند 3.4 x 1038
مقدار ممکن داشته باشد.که معادل 340,282,366,920,938,463,463,374,607,431,768,211,45 6 میباشد.
انواع هش
MD4 (http://en.wikipedia.org/wiki/MD4) (128 bits, obsolete)
MD5 (http://en.wikipedia.org/wiki/MD5) (128 bits)
RIPEMD-160 (http://en.wikipedia.org/wiki/RIPEMD-160) (160 bits)
SHA-1 (http://en.wikipedia.org/wiki/SHA1) (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 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 ها کلا موارد استفاده کمی دارند که ما در ادامه بحث آن ها را بیان می کنیم:
تشخیص درستی یک فایل Verifying file integrity
برای مثال زمانی که یک فایل با حجم بالا را دانلود می نماییم می توانیم با به دست آوردن مقدار MD5 آن فایل توسط دستور md5sum و مقایسه آن با مقدار Md5 داده شده توسط سایت مورد نظر از درستی فایلمان اطمینان حاصل کنیم.
hash کردن کلمه عبور Hashing passwords
قبلا به طور مفصل بحث شد.
نشانه گذاری اسناد به روش digitally (امضاهای digitally)
که نحوه انجام ان به وضوح در شکل زیر نشان داده شده است:
Collision (تصادم) در Hash
زمانی که مقدار Hash دو ورودی متفاوت یکسان باشند می گوییم Collision رخ داده است.
اما تا کنون هیچ موردی از Collision دیده نشده است . این امر از این حقیقت ناشی می شود که تعداد مقادیر یک الگوریتم hash بسیار زیاد می باشند.برای مثال یک Hash 128 بیتی میتواند 3.4 x 1038
مقدار ممکن داشته باشد.که معادل 340,282,366,920,938,463,463,374,607,431,768,211,45 6 میباشد.
انواع هش
MD4 (http://en.wikipedia.org/wiki/MD4) (128 bits, obsolete)
MD5 (http://en.wikipedia.org/wiki/MD5) (128 bits)
RIPEMD-160 (http://en.wikipedia.org/wiki/RIPEMD-160) (160 bits)
SHA-1 (http://en.wikipedia.org/wiki/SHA1) (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) را خواهیم داشت!