هش کردن چیست؟ - قسمت دوم

مترجم: احمد رجعتی

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

بهترین سناریو: پاسخ خود را در اولین تلاش خود دریافت کنید. برای اینکه این اتفاق بیفتد، باید خوش شانس‌ترین فرد در جهان باشید. شانس چنین اتفاقی نجومی است.
بدترین سناریو: شما پس از 2^128-1 بار به پاسخ درست می‌رسید. یعنی پاسخ خود را در پایان تمام داده‌ها پیدا خواهید کرد.
سناریو بینابینی: جوابتان را در جایی در وسط پیدا خواهید کرد و اساسا پس از 2^128/2 = 2^127 بار به نتیجه خواهید رسید. به عبارت دیگر این عدد برابر با 2^127 = 1.7 X 10^38 است که عدد بسیار بزرگی است.

بنابراین هرچند این‌که بتوانیم از این روش به جواب برسیم ممکن است، اما زمان رسیدن به جواب آنقدر زیاد است که عملا نمیتوان از این روش استفاده کرد.

یکی دیگر از ویژگی‌های توابع هش این است که تغییرات کوچکی در ورودی، مقدار هش را نیز تغییر می‌دهد. حتی اگر در ورودی خود تغییر کوچکی ایجاد کنید، تغییراتی که در هش منعکس می‌شود بزرگ خواهد بود. بیایید آن را با استفاده از SHA-256 تست کنیم:

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

ویژگی آخر توابع هش، Collision Resistant بودن آنهاست. با توجه به دو ورودی مختلف A و B که در آن H (A) و H (B) هش مربوط به آنها هستند، غیرممکن است که H (A) برابر با H (B) باشد. این موضوع به این معنی است که در اکثر مواقع هر ورودی دارای هش خاص خود است. چرا «اکثر مواقع»؟ بیایید در مورد یک مفهوم جالب به نام «پارادوکس تولد» صحبت کنیم.

پارادوکس روز تولد چیست؟

شانس اینکه روز تولد شما با روز تولد فرد غریبه‌ای که در خیابان می‌بیند یکسان باشد کم است. در حقیقت، فرض بر این است که تمام روزهای سال برای روز تولد احتمالی یکسان دارد، شانس اینکه فرد دیگری روز تولدش با شما برابر باشد 1/365 است که 0.27٪ است که واقعا کم است.

با این حال، اگر شما 20 تا 30 نفر تا در یک اتاق جمع کنید شانس اینکه دو نفر از آن ها روز تولد یکسانی داشته باشند بسیار افزایش می‌یابد. در حقیقت، شانسی 50-50 برای این که دو نفر روز تولد یکسانی داشته باشند وجود دارد.

چرا چنین اتفاقی می‌افتد؟ این موضوع به دلیل قانون ساده‌ای در احتمال است. فرض کنید N حالت مختلف از یک واقعه وجود دارد، شما باید به اندازه ریشه دوم N مورد مختلف را به طور تصادفی بررسی کنید تا یک تشابه با شانس 50-50 پیدا کنید.

با استفاده از این تئوری، در مورد روز تولد ما 365 حالت مختلف داریم لذا با انتخاب 23 فرد (که ریشه دوم 365 است) شانس اینکه دو نفر با روز تولد یکسان پیدا کنیم، یکسان است.

این موضوع چه استفاده‌ای در هش دارد؟

فرض کنید یک هش 128 بیتی دارید که 2^128 حالت مختلف دارد. با استفاده از پارادوکس روز تولد، شما با آزمایش 2^64 حالت، 50 درصد شانس پیدا کردن یک تشابه را دارید.

همان طور که می‌بینید، مقاومت در برابر برخورد با شکست خوردن بسیار راحت‌تر است. هیچ تابع هشی خالی از تصادم (Collision) نیست، اما معمولا کشف یک برخورد مدت زیادی زمان نیاز دارد. بنابراین، اگر از یک تابع مثل SHA-256 استفاده میکنید، فرض می‌شود که اگر H (A) = H (B) آنگاهA = B است.

منبع: blockgeeks