خانه / دانستنی‌ها / نحوه کارکرد الگوریتم‌های درهم‌سازی

نحوه کارکرد الگوریتم‌های درهم‌سازی

اگر رمزنگاری رو به بدن انسان تشبیه کنیم، الگوریتم درهم‌سازی در نقش قلب آن خواهد بود. اگر رمزنگاری یک ماشین باشد، الگوریتم درهم‌سازی موتور آن خواهد بود. اگر رمزنگاری یک فیلم سینمایی باشد، الگوریتم درهم‌سازی ستاره آن فیلم خواهد بود. اگر رمزنگاری منظومه شمسی باشد، الگوریتم درهم‌سازی خورشید خواهد بود.

خیلی خب، احتمالا زیاده‌روی کردیم اما حتما متوجه منظورمون شدید. درسته؟ قبل از اینکه بفهمیم «الگوریتم درهم‌سازی» چیست، چرا هست و چطور کار می‌کند، مهم است که اصول اولیه و جزییات فنی آن را به خوبی درک کنیم. به این منظور، ابتدا با مفهوم درهم‌سازی شروع می‌کنیم.

درهم‌سازی چیست؟

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

با استفاده از یک الگوریتم انتخابیِ درهم‌سازی، داده‌ها به یک سایز ثابت فشرده می‌شوند. با یک مثال بهتر متوجه می‌شویم. اگر جمله “Donkeys live a long time” را در نظر بگیریم و الگوریم درهم‌سازی joaat را بر روی آن اعمال کنیم، خروجی ۶e04f289 خواهد بود. این خروجی به عنوان یک مقدار درهم‌سازی (hash) شناخته می‌شود.

زمانی که قصد تایید یا مقایسه فایل‌ها یا پایگاه‌داده‌ها را دارید، استفاده از مقادیر درهم‌سازی بسیار مناسب است. علاوه بر مقایسه داده‌ها با فرم اصلی و اولیه‌شان، مقایسه مقادیر درهم‌سازی با یکدیگر نیز برای کامپیوترها بسیار ساده‌تر است.

در اساس، درهم‌سازی با دو ویژگی یکتایی و تغییرناپذیری تعریف می‌شود. تغییرناپذیری به این معنی است که یک بار که چیزی را درهم کردید، دیگر نمی‌توانید به حالت قبل آن را بازگردانید. در واقع، برخلاف رمزنگاری و رمزگشایی، نمی‌توانید یک پیام یا داده را de-hash کنید. یکتایی هم به این معنی است که برای دو تکه‌داده‌ی متفاوت، هیچ‌گاه مقدار درهم‌سازی یکسانی نخواهیم داشت. در واقع اگر برای دو تکه‌داده متفاوت، مقدار درهم‌سازی یکسان در بیاید، می‌گوییم تداخل (collision) درهم‌سازی رخ داده و الگوریتم بی‌استفاده می‌شود.

(نکته: در این مقاله برای کوتاهی و درک راحت‌تر، از الگوریتم درهم‌سازی joaat استفاده شده است. اما امروزه الگوریتم‌های پیچیده‌تر و طولانی‌تری مورد استفاده قرار می‌گیرند.)

تابع درهم‌سازی: هسته الگوریتم درهم‌سازی

“پشت هر مرد موفق، یک زن فوق‌‎العاده قرار دارد.” — Groucho Marx

“پشت هر الگوریتم درهم‌سازی موفق، یک تابع درهم‌سازی فوق‌العادی قرار دارد.” — همین الان از خودمون در آوردیم!

تابع درهم‌سازی، یک تابع ریاضیاتی است که مقدار ورودی را به یک مقدار عددی فشرده یا همان مقدار درهم‌سازی تبدیل می‌کند. اساسا، یک واحد پردازشی، داده‌های با سایز دلخواه را دریافت می‌کند و خروجی‌هایی با سایز ثابت (مقادیر درهم‌سازی) به ما می‌دهد.

طول مقدار درهم‌سازی، به الگوریتم درهم‌سازی بستگی دارد. به صورت کلی اگر بخواهیم بگوییم، بیشتر الگوریتم‌ها یا تابع‌های محبوب درهم‌سازی، مقدار درهم‌سازی‌ای که تولید می‌کنند، در بازه ۱۵۰ تا ۵۱۲ بیت است. حالا به قسمتی می‌رسیم که احتمالا منتظرش بودید.

الگوریتم درهم‌سازی چیست و چه کار می‌کند؟

همانطور که بحث کردیم، تابع درهم‌سازی نقش قلب الگوریتم درهم‌سازی را ایفا می‌کند. اما، برای داشتن مقدار درهم‌سازی با طول از پیش تعیین‌شده، ابتدا باید داده ورودی را به بلاک‌هایی با سایزهای یکسان تقسیم کنید. دلیلش این است که تابع درهم‌سازی، داده‌هایی با طول ثابت را به عنوان ورودی دریافت می‌کند. این بلاک‌ها، “بلاک‌های داده‌ای” نامیده می‌شوند.

سایز بلاک‌های داده‌ای، در الگوریتم‌های مختلف، متفاوت است اما برای یک الگوریتم خاص، سایز بلاک‌های داده‌ای کاملا یکسان است. برای مثال، الگوریتم SHA-1، پیام و داده‌ها را تنها در بلاک‌های ۵۱۲بیتی دریافت می‌کند. پس اگر سایز پیام دقیقا ۵۱۲ بیت باشد، تابع درهم‌سازی دقیقا یکبار اجرا می‌شود. همچنین، اگر سایز پیام، ۱۰۲۴ بیت باشد، به دو بلاک ۵۱۲ بیتی شکسته می‌شود و تابع درهم‌سازی دوبار اجرا می‌شود. اگرچه، در ۹۹ درصد مواقع، سایز پیام دقیقا مضربی از ۵۱۲ بیت نیست. در چنین مواقعی (تقریبا همه مواقع)، از تکنیکی به نام padding استفاده می‌شود. با این روش، پیام به بلاک‌هایی با سایز یکسان تقسیم می‌شود و تابع درهم‌سازی به تعداد این بلاک‌ها اجرا می‌شود. به شکل زیر توجه کنید:

همان‌طور که در شکل بالا دیده می‌شود، بلاک‌ها یکی پس از دیگری پردازش می‌شوند. نکته قابل توجه این است که خروجی اجرای تابع‌ درهم‌ساز بر روی بلاک اول، در کنار بلاک دوم به عنوان ورودی در پردازش دوم داده می‌شود. به همین ترتیب، خروجی پردازش دوم، به عنوان ورودی پردازش سوم داده می‌شود و همینطور الی آخر. بنابراین، خروجی نهایی، ترکیبی از مقدار تمام بلاک‌ها است. اگز تنها یک بیت از پیام اولیه را تغییر دهید، کل مقدار درهم‌سازی تغییر خواهد کرد. به این اتفاق “تاثیر پروانه‌ای” می‌گویند.

الگوریتم‌های محبوب درهم‌سازی

  • Message Digest (MD) Algorithm
  • (Secure Hash Algorithm (SHA
  • (RACE Integrity Primitives Evaluation Message Digest (RIPEMD
  • Whirlpool
  • RSA

.

.

منبع

.

.

.

با ما همراه باشید

آدرس کانال تلگرام: JavaCupIR@

آدرس اکانت توییتر: JavaCupIR@

آدرس صفحه اینستاگرام: javacup.ir

آدرس گروه لینکدین: Iranian Java Developers

 

 


درباره سردبیر

همچنین بررسی کنید

ترس از کاهش وابستگی

اگر زمانی که پای برنامه‌نویسی شی‌گرا به میان بیاید، از حذف وابستگی‌های بین اشیا واهمه …

یک نظر

  1. موضوع اصلی این است که الگوریتمهای درهم سازی به هیچ وجه مقدار یکتا تولید نمیکنند، به چند دلیل:
    ۱- طول خروجی ثابت است! پس حداکثر تعداد داده ثابتی (مثل ۲ بتوان ۵۱۲ حالت) داده میتواند داشته باشد، و داده های با طول بیش از این مطمیئنن خروجی تکراری تولید میکند.
    ۲- در غیر اینصورت تابع ۲ طرفه میشد.

    مساله مهم فاصله hamming است. یعنی با تغییر کم در مقدار ورودی خروجیها خیلی با هم متفاوت هستند، در نتیجه در صورت تغییر محدود در پیام ورودی خروجی درهم سازی خیلی زاید خواهد بود.

    یک راهکار امن که بسیار متداول است، استفاده از چند روش درهم سازی است، مثلن یک فایل برای دانلود هم کد MD5 و هم SHA1 را دارد، در این حالت احتمال تولید ۲ درهمسازی یکسان برای داده تغییر داده شده خیلی خیلی کمتر می شود.

     

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *