تابع هش چیست و چه کاربردی دارد؟
تابع هش
تابع هش یا تابع درهَمَک‌ساز یا تابع چکیده‌ساز به هر رویه خوش تعریف یا تابع ریاضی می‌گویند که حجم زیادی از داده (احتمالاً حجم نامشخصی از داده) را به یک عدد طبیعی تبدیل کند. عدد طبیعی حاصل از تابع درهم‌سازی به عنوان اندیس یک آرایه مورد استفاده قرار می گیرد. مقادیر حاصل از این تابع را معمولاً مقدار هش یا فقط هش یا درهَمَک می‌خوانند. این توابع کاربردهای وسیعی در علوم کامپیوتر از جمله حفظ یکپارچگی داده ها دارند. تابع درهم‌سازی کامل
توابع هش کامل ممکن است برای پیاده‌سازی جدول جستجوی با بدترین زمان دسترسی استفاده شود. یک تابع هش کامل دارای بسیاری از کاربردهای مشابه توابع هش دیگر است، با این برتری که نیازی به بررسی مشکل برخورد ندارد. علاوه بر این، اگر کلیدها داده نباشند، لازم نیست کلیدها در جدول جستجو ذخیره شوند و موجب صرفه جویی در حافظه می‌شوند.
تابع هش رمزنگاری
پیدا کردن دو پیام متقاوت m1 و m2 با در نظر گرفتن تساوی hash("m"1) = hash("m"2) مشکل است. این جفت «برخورد هش رمزنگاری نامیده می‌شوند». این ویژگی بعضاً «مقاومت قوی در برابر برخورد» اطلاق می‌شود. حداقل نیاز به مقدار هش دو برابر اولیه دارد تا اینکه به مقاومت تصویر پردازش نشده دست پیدا کند. در غیراینصورت برخوردها می‌توانند جزو حمله روز تولد (حمله ای بدون تغییر معنی اولیه مورد حمله شده) طبقه‌بندی شوند (۴). نرم (ریاضیات)
نُرم یا هَنج در ریاضی و رشته‌های مربوط به آن در مواردی استفاده دارد که عناصر به مقادیر مثبت محدود باشند. تابع حقیقی formula_1 تعریف شده بر فضای برداری formula_2 را نُرم نامیم اگر در سه خاصیت زیر صدق کند: تابع هش رمزنگاری
مقاومت در برابر برخورد، دلالت ضمنی بر مقاومت تصویر اولیه و پردازش نشده دوم دارد، اما نه مقاومت اولیه آن (۵). فرضیه ضعیف تر همیشه در رمزنگاری نظری غالب است، اما عملاً، تابع درهمی که تنها مقاومت در برابر تصویر پردازش نشده دوم است، ناامن تلقی شده و در این صورت برای کاربردهای واقعی توصیه نمی‌شود. قضیه کوشی
ابتدا تابع h را به شکل زیر تعریف می‌کنیم که تمام خواص تابع f را نیز دارد : h(x)=f(x)-k g(x) تابع اسیدی
تابع اسیدی تابعی ریاضیاتی است که جهت پیدا کردن میزان قدرت اسید به کار می رود.بر اساس نظریه لوری برونستد، قدرت اسید با میزان توانایی آن برای آزاد سازی پروتون سنجیده می شود.روابط مربوط به محاسبه پی اچ روش خوبی برای سنجش قدرت اسید در محلول های آبی رقیق است.همچنین برای برخی شرایط از تابع اسیدی هامت ("H") استفاده می شود. تابع هیون
formula_144 ساختار مرکل–دمگارد
برای مقاوم تر شدن بیشتر هش، نتیجه نهایی گاهی اوقات از طریق تابع نهایی تغذیه می‌شود. تابع نهایی می‌تواند چندین هدف از قبیل فشرده کردن یک حالت داخلی بزرگ‌تر را داشته باشد (آخرین نتیجه) به یک اندازه هش کوچک‌تر، یا تضمین یک اثر مخلوط سازی بهتر و ی بر روی بیت‌های جمع هش باشد. تابع نهایی اغلب با استفاده از تابع فشرده‌سازی ساخته می‌شود؛ که در بعضی از اسناد اصطلاحات متفاوتی به کار رفته‌است: عمل لایه گذاری «نهایی کردن» نامیده می‌شود. ساختار مرکل–دمگارد
محبوبیت این ساخت و ساز به دلیل واقعیتی است که توسط مرکل و دمگارد ثابت شده‌است که اگر عملکرد یک طرفه فشرده سازی "f" در برابر برخورد مقاومت داشته باشد، بنابراین عملکرد هش با استفاده از آن نیز ساخته شده‌است. متأسفانه، این ساخت و ساز چندین ویژگی نامطلوب نیز دارد: تابع هیون
formula_109 جدول درهمک‌سازی
این‌ها تنها مثال‌هایی از روش‌های متعددی هستند که برای سامان دادن به جداول هش به کار می‌روند. روش‌هایی مبتنی بر کارهایی به جز قرار دادن مقدارها در خود آرایه و در لیست پیوندی هم وجود دارند، اما این‌ها متداول‌ترین روش‌ها هستند. گفتنی‌ست که در همهٔ روش‌ها تلاش بر این است که تابع هش طوری باشد که احتمال یکی شدن کلید ویژه دو مقدار متفاوت به کمترین حد خود برسد. انتخاب این تابع هش مناسب گاه بسیار مشکل است. توابع هش معروف بسیاری از جمله تابع هش ضربی محبوب ارائه‌شده توسط دانلد کنوت در کتاب هنر برنامه‌نویسی رایانه دارای خصوصیات پخشی مناسبی هستند. معادلات کوشی-ریمان
فرض کنید "f"("x" + "iy") = "u" + "iv" یک تابع از یک مجموعه باز از اعداد مختلط formula_3 به formula_3 باشد که در آن formula_5 ،formula_6 ،formula_1 و formula_2 حقیقی اند (formula_1 و formula_2 توابع حقیقی-مقدار تعریف شده بر یک زیر مجموعه باز از formula_11. آنگاه formula_12 هلوموفیک است اگر و تنها اگر formula_1 و formula_2 به‌طور پیوسته مشتق پذیر باشند و مشتقات جزئی آن‌ها در معادلات کوشی ریمان که و هستند، صدق کنند. با یک فرمول بندی مختلط طبیعی، بینش هندسی بهتری به وجود می‌آید: با توجه به معالات، اگر formula_1 و formula_2 دو بار مشتق پذیر باشند آنگاه مادامی که در معادلات لاپلاس صدق می‌کنند باید توابع همساز باشند؛ بنابراین معدلات می‌توانند به صورتی شرایطی بر روی یک جفت تابع همساز دیده شوند که بتوانند به عنوان بخش‌های حقیقی و موهومی یک تابع مختلط تحلیلی به کار روند. برای یک تابع داده شدهٔ همساز formula_1، یک تابع همساز نظیر مانند formula_2، یک همساز توأم نامیده می‌شود. اگر وجود داشته باشد، حداکثر یا یک عبارت ثابت منحصر بفرد است. جدول درهمک‌سازی
در قلب یک جدول درهم‌سازی، یک آرایهٔ ساده از عناصر وجود دارد؛ که معمولاً به سادگی جدول هش نامیده می‌شود. جدول هش اندیس یک کلید را محاسبه می‌کند و از آن اندیس برای جای دادن آن کلید در جدول استفاده می‌کند. تابع هش رمزنگاری
الگوریتم‌های مجموع مقابله ای یا جمع کنترلی، مثل CRC32 و سایر کنترل‌های افزونگی دوره ای برای پوشش دادن الزامات ضعیف تر طراحی می‌شوند و بطور کالی مناسب توابع درهم ساز رمزنگارانه نیستند. برای مثال، CRC برای یکپارچه سازی پیام طبق استاندارد رمزنویسی VEP استفاده شد، امادر یک حمله می‌توان راحتی از حالت خطی جمع کنترلی خبر دار شد. تابع هش
formula_2 تابع هش رمزنگاری
در عمل رمزنویسی، بطور کلی غیرمحتمل است که تقریباً اطمینان بدست آورد که رقیب یا دشمن به اطلاعات دسترسی پیدا نخواهد کرد باید تا زمانی که فرض می‌شود امنیت سیستم از اهمیت حیاتی برخوردار است، از ورود او به سیستم باید جلوگیری کرد؛ بنابراین، مفهوم این اصطلاح تاحدی به کاربردش بستگی دارد از آنجاییکه کاری که یک عامل خطرناک یا متخاصم انجام می‌دهد معمولاً به نسبت سود مورد انتظارش از این کار سنجیده می‌شود. هرچنأ، از آنجاییکه معمولاً تلاش مضاعف برای دست پیدا کردن به پیامی با طول چکیده مضاعف است، حتی مزیت چندین برابر در قدرت پردازش با اضافه کردن بیت‌های متعدد به حروف، می‌تواند خنثی شود. علم‌سنجی
شاخص اچ (شاخص هرش):از شاخص‌های جدید این علم است که در سال ۲۰۰۵ معرفی شد و آن برای محاسبه برون داد علمی محققان به کار می‌رود.شاخص اچ یک محقق عبارت است از hتعداد از مقالات وی که به هر کدام حداقل hبار استناد شده باشد. با توجه به سادگی استفاده این شاخص بیشتر مورد توجه متخصصین علم سنجی قرار گرفته‌است. با توجه به امکاناتی که web of science فراهم کرده‌است با استفاده از آن سریعتر و با دقت بیشتر این شاخص محاسبه می‌شود. باید به این نکته توجه نمود بسته به اینکه چه ابزاری برای محاسبه مورد استفاده قرار می‌گیرد ممکن است مقدار این شاخص تحت تأثیر قرار گیرد. تابع هش رمزنگاری
چند روش برای استفاده از «رمزنگاری بلوکی» برای ساخت تابع درههم ساز رمزنگار بویژه «تابع فشرده یک سویه» وجود دارد. صورت نرمال هسه
صورت نرمال هسه ()، که به افتخار اتو هسه نامگذاری شده‌است، معادله‌ای است که در هندسه تحلیلی به‌کار می‌رود و نمایانگر یک خط در فضای دوبعدی، یک صفحه در فضای سه‌بعدی، یا یک ابرصفحه در ابعاد بالاتر است. این معادله در اصل برای محاسبهٔ فاصله (فاصلهٔ نقطه از خط و نقطه از صفحه) به کار می‌رود و در نشان‌گذاری بردار به صورت زیر نوشته می‌شود: تابع هش رمزنگاری
خروجی‌های «الحاقی» از چند تابع درهم، مقاومت به برخورد را به خوبی قوی‌ترین الگوریتم‌ها با نتایج بهم پیوسته ایجاد می‌کنند. برای مثال، نسخه‌های قدیمی امنیت لایه انتقال (TLS) و لایه سوکت‌های امنیتی (SSL) از مجموع بهم پیوسته MD5 و SHA-1 استفاده می‌کنند (۱۴٫۱۵). این کار تضمین می‌کند که روش شنسایی برخورد در یکی از توابع درهمه، از داده‌های حفاظت شده توسط هر دو تابع درهم را مانع نمی‌شود. تابع هش رمزنگاری
«سازنده‌های عدد تصادفی ساختگی» (PRNG) را می‌توان با استفاده از توابع درهم ساخت. این کار با بنیان تصادفی (رمزی) با شمارنده و درهم کردن آن انجام داد. تابع هش رمزنگاری
با توجه به مقدار ورودی m1، پیدا کردن ورودی متفاوت m2 باید مشکل باشد با تساوی مقابل: hash("m"1) = hash("m"2). این ویژگی بعضاً "مقاومت تصادم ضعیف نامیده می‌شود. توابعی که از این ویژگی برخوردار نباشند، نسبت به حملات تصویر پردازش نشده دوم آسیب‌پذیر هستند. تابع تصادفی
بنابراین می‌توان تابع تصادفی را نقشه هریک از ورودی‌ها به‌طور مستقل و تصادفی به هر یک از خروجی‌های ممکن در نظر گرفت. تماشای این راه یک ایده‌آل‌سازی از یک تابع هش رمزنگاری است تابع تصادفی یک بلوک ساختمانی مفید در اختیار پروتکل رمز نگاری است با این وجود سناریوهایی وجود دارد که احتمالاتی برای گروه‌های بدگمان دوطرف برای توافق بر سر یک تابع تصادفی را رد می‌کند. بنابراین رمزنگاران مدلهایی که به صراحت اجازه می‌دهند که توابع را به صورت تصادفی یا یک تابع مربوط رااستفاده کنند را مطالعه می‌کنند.random oracle model و common reference string model را مشاهده کنید. اثر انگشت (رایانش)
توابع هشی که در رمزنگاری به کار می‌روند می‌توانند به عنوان تابع انگشت نگاری با کیفیت بالا مورد استفاده قرار گیرد، زیرا برای سخت‌تر کردن رمزگشایی مورد استفاده قرار می‌گیرند و باور بر این است که در مقابل حملات مخرب، ایمن هستند. ماتریس هسین
در ریاضیات، ماتریس هسین یا هسین، ماتریسی مربعی از مشتقات جزئی مرتبه دوم یک تابع اسکالر-مقدار است (به تابع اسکالر-مقدار، میدان بردای نیز می گویند). این ماتریس، خمیدگی موضعی یک تابع چند متغیره را توصیف می کند. ماتریس هسین در قرن نوزدهم توسط ریاضیدان آلمانی لودویگ اتو هسه توسعه یافت که بعد اسم او را بر این ماتریس نهادند. هسه، خود اولین بار از عبارت "دترمینان‌های تابعی" برای توصیف این اشیاء استفاده کرد. تابع هش رمزنگاری
درست مثل "رمزنگارهای بلوکی که می‌توانند برای ساخت توابع درهم استفاده شوند، توابع درهم را می‌توان برای ساخت رمزهای بلوکی استفاده کرد. ساخت Luby-Rackoff با استفاده از توابع درهم را زمانی می‌توان ایمن تلقی کرد که توابع درهم اصلی ایمن باشند. هم چنین، بسیاری از توابع درهم ساز (مثل SHA-1 و SHA-2) با استفاده از رمزنگاری بلوکی با یک هدف-ویژه در سازه Davies–Meyer یا سازه دیگر ساخته می‌شوند. هم چنین از حروف رمزی می‌توان در حالت عملیات رایج بدون تضمین امنیت یکسان استفاده کرد. به SHACAL, BEAR و LION مراجعه کنید. جدول درهم‌سازی توزیع‌شده
هنگامی که این اجزا در جای خود قرار گرفتند، استفاده معمولی از DHT برای ذخیره‌سازی و بازیابی ممکن است به شرح زیر انجام شود. فرض کنید فضای کلید مجموعه ای از رشته‌های ۱۶۰ بیتی است. برای نمایه سازی فایل با داده شده و در DHT، هش SHA-1 تولید می‌شود و یک کلید ۱۶۰ بیتی تولید می‌شود و یک پیام به هر گره ای که در DHT شرکت می‌کند ارسال می‌شود. پیام از طریق شبکه همپوشانی از گره ای به گره دیگر ارسال می‌شود تا زمانی که به گره تکی مسئول کلید که توسط پارتیشن‌بندی فضای کلید مشخص شده‌است برسد. سپس آن گره کلید و داده‌ها را ذخیره می‌کند. سپس هر کلاینت دیگری می‌تواند محتویات فایل را با هش کردن مجدد برای تولید و درخواست از هر گره DHT برای یافتن داده‌های مرتبط با با پیام بازیابی کند. پیام دوباره از طریق پوشش به گره مسئول هدایت می‌شود که با ذخیره شده پاسخ می‌دهد. تابع هیون
formula_127 تابع هیون
formula_102 تابع هش
یک تابع درهم‌سازی خوب تابعی است که ساده و یک‌نوا باشد، در ادامه یکی روشهای سادهٔ مختلف را برای طراحی تابع درهم‌سازی را بیان می‌کنیم. جدول درهمک‌سازی
اما اگر بخواهیم همین داده‌ها را با جدول هش ذخیره کنیم، وضع طور دیگری خواهدبود. برای این کار تابع هش‌مان را چنین تعریف می‌کنیم که برای هریک از مقدارها (نام‌های افراد) کلید ویژه‌شان را برابر با باقی‌مانده تقسیم عدد حاصل از کنار هم قرار گرفتن کدهای اسکی نویسه‌های تشکیل‌دهنده آن رشته بر صدهزار قرار می‌دهیم. به این ترتیب هرکدام از این ده‌هزار نام با یک عدد صحیح بین ۰ تا ۹۹۹۹۹ مرتبط می‌شوند. تابع هش
formula_8 جدول درهمک‌سازی
وقتی زیرمجموعه‌ای تصادفی از یک مجموعهٔ بزرگ اعداد را درهم‌سازی می‌کنیم، جلوگیری از رخ دادن تصادم عملاً غیرممکن خواهد بود. برای مثال اگر بخواهیم ۲۵۰۰ کلید را در یک میلیون خانه هش کنیم، ۹۵٪ احتمال وجود دارد که حداقل دو کلید در یک مکان هش شوند. بنابر این، بسیاری از پیاده‌سازی‌های توابع هش، استراتژی خاصی برای تحلیل مسئله تصادم در نظر می‌گیرند تا این قبیل پیشامدها را کنترل کنند. تعدادی ازاستراتژی‌های رایج در زیر توصیف خواهند شد. همهٔ این متدها احتیاج دارند که تمام کلیدها یا ارجاعات آن‌ها به همراه مقدار هش آن‌ها با هم در جدول ذخیره شوند. جدول درهمک‌سازی
حال باز هم برای ذخیره کردن نام‌ها آرایه‌ای می‌سازیم اما این بار هر مقدار را در خانه متناظر با کلید ویژه‌اش در آرایه قرار می‌دهیم. مثلاً اگر کلید ویژه مربوط به یک نام برابر با ۲۵۰۰۰ باشد، آن را در خانه ۲۵۰۰۰ آرایه می‌ریزیم. در این‌جاست که ویژگی اصلی جدول هش خودش را نشان می‌دهد. در این جدول اگر بخواهیم نامی را پیدا کنیم، لازم نیست همه جدول را بپیماییم. کافی‌ست که با تابع هش مربوطه کلید ویژه آن نام را پیدا کنیم و ببینیم در آن خانه از جدول که متناظر با شماره‌اش برابر با عدد این کلید است چنان نامی وجود دارد یا نه. توجه کنید که در مثال خام بدون استفاده از جدول هش هم‌خانه‌های آرایه از روی شماره‌شان قابل دسترسی بودند اما این شماره‌ها ارزشی نداشتند چون چیز معناداری را نشان نمی‌دادند. همچنین دقت به این نکته مهم است که ما در مقابل بالا بردن سرعت جستجو در این راه حل مجبور شدیم فضای حافظه بیشتری مصرف کنیم. (صدهزار به جای ده هزار) این برای آن بود که احتمال آن که دو مقدار دارای کلید ویژه یکسان شوند پایین بیاید. ریاضیات گسسته
فرض کنید یک شماره شناسایی مشتری به طول ده رقم است. برای بازیابی سریع فایل‌های مشتری، نمی‌خواهیم با استفاده از رکورد مشتری، یک خانهٔ حافظه اختصاص دهیم. در عوض، می‌خواهیم از یک عدد صحیح کوچکتر مربوط به شماره شناسایی استفاده کنیم. اینکار را می‌توان با تابع درهم‌ساز (hashing function) معروف است انجام داد. پی‌اچ
پی‌اچ یا پ هاش مقیاسی برای تعیین میزان اسیدی یا بازی بودن یک محلول آبی است. هرچه محلول اسیدی تر باشد عدد pH کوچکتر، و هر چه بازی تر باشد،عدد pH بزرگتری خواهد داشت. در دمای اتاق (۲۵ درجه سلسیوس)، آب خالص نه خاصیت اسیدی و نه خاصیت بازی دارد و در نتیجه،عدد pH آن برابر ۷ خواهد بود. Stdarg.h
stdarg.h یک فایل سرایند در کتابخانه استاندارد سی است که به توابع اجازه می‌دهد تا آرگومان‌هایی به تعداد نامعین و دلخواه دریافت کنند. در حالت کلی، در زبان برنامه‌نویسی سی، تعداد پارامترهای یک تابع صریحاً در هنگام اعلان تابع مشخص می‌شود و در هنگام فراخوانی تابع باید دقیقاً به تعداد پارامترها، آرگومان به تابع ارسال شود. اما در برخی مواقع نیاز است تا یک تابع تعداد نامشخصی آرگومان دریافت کند. به کمک امکاناتی که توسط این فایل سرایند محیا شده، می‌توان چنین توابعی را اعلان کرد. از جمله پرکاربردترین توابع از این نوع، تابع printf است. اصطلاحاً به این گونه توابع، توابع متغیر گفته می‌شود. جدول درهمک‌سازی
اگر تمام کلیدها در یک زمان پیش‌بینی شده معلوم شوند، جدول هش کامل می‌تواند مورد استفاده قرار گیرد تا یک جدول هش کامل ساخته شود که در آن هیچ تصادمی رخ ندهد. اگر جدول کامل کمینه استفاده شود، تمام مکانهای جدول هش به خوبی استفاده خواهند شد. زمان جستجو در هش کامل در بدترین حالت بر خلاف متدهای زنجیرواری و آدرس دهی باز مقدار ثابتی است. اما با وجود اینکه زمان متوسط جستجودر اینجا کو تاه است، ممکن است در مواردی (به تناسب اعداد ورودی) برای مجموعه‌ای از اعداد بسیار بزرگ شود. تابع هش رمزنگاری
MD5 توسط Ronald Rivest در سال ۱۹۹۱ برای جایگزین کردن آن با تابع درهم اولیه MD4 طراحی شده بود و در سال ۱۹۹۲ به عنوان RFC 1321 معرفی شد. برخوردها در برابر MD5 را می‌توان در چند ثانیه محاسبه کرد که باعث می‌شود این الگوریتم در اکثر موارد کابرد مناسبی نداشته باشد در اینجا به تابع درهم رمزنگاری احتیاج داریم. MD5 چکیده ۱۲۸ بیتی تولید می‌کند (۱۶ بایت). زنجیره درهمسازی
زنجیره درهمسازی یا زنجیره هش اعمال پیوسته تابع درهمساز رمزنگارانه بر روی تعدادی داده‌است. در امنیت رایانه از زنجیره درهمسازی برای بدست آوردن تعداد زیادی رمز یکبار مصرف از روی یک رمز استفاده می‌شود. برای برقراری شرط غیرقابل انکار بودن یک تابع درهمسازی (هش) می‌تواند به بخش‌های مختلف اطلاعات اعمال گردد تا تاریخچه‌ای از داده‌ها و اطلاعات در دسترس باشد. تابع درهم‌سازی کامل
یک تابع درهم سازی کامل برای یک مجموعه خاص می‌تواند در زمان ثابت تعیین شود. یا با مقادیر موجود در یک محدوده کوچک، توسط یک الگوریتم تصادفی در تعدادی از عملیات‌ها که (که تعداد آن متناسب با اندازه S می‌باشد) می‌تواند جستجو شود. روش ساختن از یک طرح دو سطحی استفاده می‌کند تا یک مجموعه از عنصر به طیف وسیعی از شاخص مرتبط (نقشه) کند، و پس از آن هر شاخص به طیف وسیعی از مقادیر هش مرتبط می‌شود. سطح اول ساخت آنها، یک اول بسیار بزرگ (بزرگتر از اندازه مجموعه ای که از آن ترسیم شده‌است)، و یک پارامتر انتخاب می‌کند و هر عنصر از را به نمایه (اندیس) خودش مرتبط می‌کند. ریاضیات گسسته
در عمل، تابع‌ها ی در هم ساز مختلفی وجود دارد اما یکی از متداول‌ترین آن‌ها به شکل h(k)=k mod m است که در آن m تعداد خانه‌های حافظه موجود است. تابع‌های در هم ساز به راحتی ارزیابی می‌شوند طوری‌که مکان فایل‌ها را به سرعت می‌توان مشخص کرد. تابع در هم ساز h(k) ای نیاز را برطرف می‌کند. برای یافتن h(k) لازم است باقی‌مانده تقسیم k بر m را بدست آوریم. همچینی این تابع پوشا نیز هست. جدول درهمک‌سازی
جدول درهمک‌سازی یا جدول چکیده‌سازی یا جدول هش ، در علوم رایانه، نوعی ساختمان داده است که مقدارهایی که باید ذخیره شوند را به وسیله تابع هش (درهم سازی) با کلیدهای ویژه‌ای مرتبط می‌سازد. عملیات اولیه‌ای که این جدول تسهیل می‌کند عمل مراجعه است. به این معنی که کاربر می‌تواند با سرعتی کارآمد داده مورد نظرش را در آن بیابد. در جدول‌های هش همچنین افزودن داده‌های جدید در زمان کم امکان‌پذیر است. زمان لازم برای جستجو و افزودن وابسته به نوع جدول و میزان داده‌ها هستند. این زمان می‌تواند با انتخاب جدول مناسب به مرتبه زمانی برسد. تابع هش رمزنگاری
عملاً مقاومت در برابر برخورد، در خیلی از کاربردهای عملی کافی بنظر نمی‌رسد. علاوه بر مقاومت در برابر برخورد، باید پیدا کردن دو پیام با چکیده یا خلاصه‌های کاملاً مشابه توسط رقیب، غیرممکن باشد، یا استنباط هر گونه اطلاعات مفید در مورد داده‌ها. بویژه، تابع درهم باید تا حد ممکن مثل «تابع تصادفی» عمل کند (که در گواه امنیتی، اوراکل تصادفی نامیده می‌شود) در عین حال از نظر محاسباتی قطعی و مؤثر باشد. این توابعی مثل تابع SWIFFT را غیرمحتمل می‌شمارد، و اثبات شده که می‌تواند مقاومت برخورد داشته باشد بااین فرض که مسائل معین روی شبکه‌های ایده‌آل، به سختی قابل محاسبه هستند، اما در قالب تابع خطی این ویژگی‌های اضافی قابل پوشش دادن نیستند (۷). جدول درهمک‌سازی
جداول هش برای پیاده‌سازی آرایه‌های انجمنی، به خصوص در زبان‌های برنامه‌نویسی تفسیری مانند AWK، پرل، پی‌اچ‌پی به کار می‌روند. جدول درهم‌سازی توزیع‌شده
در هش قرار ملاقات که هش با بالاترین وزن تصادفی (HRW) نیز نامیده می شود، همه مشتریان از یک تابع هش استفاده می کنند. formula_18 (انتخاب زودتر از زمان) برای مرتبط کردن یک کلید به یکی از "n" سرور موجود. هر مشتری فهرست یکسانی از شناسه‌های , یکی برای هر سرور. با توجه به کلید "k" ، یک کلاینت "n" وزن هش را محاسبه می کند. مشتری آن کلید را با سرور مربوط به بالاترین وزن هش برای آن کلید مرتبط می کند. سرور با شناسه formula_19 همه کلیدها را در اختیار دارد formula_5 که برای آن وزن هش formula_21 از وزن هش هر گره دیگری برای آن کلید بیشتر است. جدول درهم‌سازی توزیع‌شده
به عنوان مثال، Chord DHT از هش ثابت استفاده می کند، که گره ها را به عنوان نقاط روی یک دایره در نظر می گیرد، و formula_1 مسافتی است که در جهت عقربه های ساعت به دور دایره از آن طی می شود formula_2 به formula_3 . بنابراین، فضای کلید دایره‌ای به بخش‌های پیوسته تقسیم می‌شود که نقاط پایانی آن‌ها شناسه گره هستند. اگر formula_11 و formula_12 دو شناسه مجاور، با فاصله کمتر در جهت عقربه های ساعت از formula_11 به formula_12 ، سپس گره با شناسه formula_12 مالک تمام کلیدهایی است که بین آنها قرار می گیرند formula_11 و formula_12 . جدول رنگین‌کمانی
هش چین تکنیکی برای کاهش این فضای درخواست شده می‌باشد. ایدهٔ مشخص کردن یک تابع کاهشی R می‌باشد که میزان هش را به میزان ولیوها در P تقلیل دهد. به یاد داشته باشید، تابع کاهشی درواقع معکوسی از تابع درهم ساز نیست، بلکه بیشتر یک تابع متفاوت با دامنهٔ تابع و با دامنهٔ مشترک درهم ساز می‌باشد. با تناوبی کردن تابع درهم ساز با تابع کاهشی (reduction function) زنجیره‌هایی از کدهای متناوب هش ولیو هایی (یا میزانی از هش) شکل می‌گیرد. برای مثال اگر p یک سری پسوردهای شش حرفی با حروف کوچ بود و هش ولیوها ۳۲ بیتی بودند، این زنجیره به این شکل درمی‌آمد: بازی هگز
هگز بازی دو نفره ایست که یک بازیکن مهره‌های سفید و دو ضلع مقابل در متوازی‌اضلاع و دیگری مهره‌های سیاه و دو ضلع مقابل دیگر را در اختیار دارد و در ابتدا صفحه بازی خالی است. بازی به صورت نوبتی انجام می‌شود و هر بازیکن با هدف رسیدن از یکی از ضلع‌های خود به ضلع دیگر خود، مهره‌های خود را در خانه‌های شش ضلعی می‌گذارد. مسلماً طرف مقابل نیز با حرکات خود یا باید این هدف را دنبال کند یا جلوی اتصال دوضلع حریف را بهم بگیرد. چرا که برنده بازی کسی است که دو ضلع مربوط به خود را با زنجیره پیوسته از مهره‌های خود به هم متصل کند. در تصویر متحرک مقابل نحوه بازی نمایش داده‌شده‌است.برای بازی آنلاین می‌توانید به این سایت مراجعه کنید. تابع هش
اگر دو رکورد در توابع درهم سازی به یک مکان در فایل انتقال یابند به آن برخورد می‌گویند. روش ایدئال برای مقابله با برخوردها این است که بتوان الگوریتم تبدیلی پیدا کرد که به طور کلی از وقوع برخوردها جلوگیری کند. تابع هش
یک خانواده از توابع درهم ساز به اسم H را فرض کنید. تابع هیون
formula_100 تابع هش
روش دیگری نیز برای برطرف کردن برخورد به نام روش زنجیره‌ای وجود دارد که در ادامه بیان خواهد شد. لازم نیست تعداد باکت‌ها با تعداد کلیدها برابر باشد. برای مثال، اگر به دو رقم آخر درهم‌سازی کنیم، تعداد باکت‌ها باید ۱۰۰ باشد؛ ولی، می‌توانیم ۱۰۰۰، ۲۰۰، ۱۰۰ یا هر تعداد کلید را نگهداری کنیم. البته هر چه تعداد کلیدهایی که نگهداری کنیم بیشتر باشد، احتمال وجود برخورد بیشتر است. اگر تعداد کلیدها بزرگتر از تعداد باکت‌ها باشد، حتماً برخورد داریم. چون باکت فقط یک اشاره‌گر را نگهداری می‌کند، فضای چندانی با اختصاص دادن به باکت اتلاف نمی‌شود؛ بنابراین، غالباً منطقی است که تعداد باکت‌ها به اندازه تعداد کلیدها باشد. هنگام جستجو به‌دنبال یک کلید، باید یک جستجوی ترتیبی در میان باکت (لیست پیوندی) حاوی کلید انجام دهیم. اگر همه کلیدها در یک باکت درهم‌سازی شوند، جستجو تا حد جستجوی ترتیبی تنزل می‌یابد. احتمال رخ‌دادن آن چقدر است؟ اگر ۱۰۰ کلید و ۱۰۰ باکت داشته باشیم، احتمال آن‌که کلیدها همگی به یک باکت ختم شوند، عبارت است از: الگوریتم اثبات کار
یک سیستم معروف که در هش کش استفاده میشود، با استفاده از مقداری hash معکوس ثابت میکند کار انجام شده است و یک ایمیل به عنوان نشانه خوب ارسال میکند.به عنوان نمونه هدری که در ادامه قرار دارد تقریباً یک هش 2 محاسباتی است که پیامی را برای ایمیل زیر درتاریخ 19 ژانویه ، 2038 ارسال میکند.  با یک محاسبات تکی از طریق تابع اس اچ ای-1 هش تمبری که معتبرشده است(در مثال بالا نام هدر codice_1که شامل دونقطه میباشد و هرچه فضای خالی بعد از آن تا شماره 1 حذف میشود) حمله بازپخش
به‌طور مثال، فرض کنید آلیس می‌خواهد هویت خود را به باب اثبات کند. باب هم مثلاً رمز عبور آلیس را به عنوان مدرکی برای اثبات هویت از او درخواست می‌کند، و آلیس هم قبول می‌کند. در همین حال فرد سومی مشغول استراق سمع است و رمز عبور یا تابع هش را می‌دزدد و نگه می‌دارد. پس از اینکه مبادلهٔ اطلاعات به اتمام رسید، اکنون حمله‌کننده خود را به جای آلیس جا می‌زند و با باب ارتباط برقرار می‌کند؛ و زمانی که باب از او مدرک اثبات هویتش را می‌خواهد حمله‌کننده رمز عبور یا تابع هش آلیس را که پیش خود نگه داشته‌است، برای باب می‌فرستد و او هم می‌پذیرد و بدین‌گونه حملهٔ تکرار صورت می‌پذیرد. تابع هش رمزنگاری
«کدهای تأیید پیام» (MAC) (که توابع درهم کلیدی نیز نامیده می‌شوند) اغلب از توابع درهم ساخته می‌شوند. HAMC مثل MAC است. تابع هش رمزنگاری
در ضمن، کوتاه سازی خروجی هش طولانی، مثل خروجی استفاده شده در SHA-512/256 نیز در برابر حملات متعددی دفاع می‌کند (۱۳). تابع هش
formula_1 تابع هش رمزنگاری
تابع درهم ساز رمزنگارانه باید قادر به رویارویی با همه نوع حملات کشف نوشته رمزی باشد. در رمزنویسی نظری، سطح امنیت تابع درهم ساز رمزنگارانه با استفاده از مشخصه‌های زیر تعریف می‌شود: تابع هش رمزنگاری
در اصل، SHA-2 دو الگوریتم درهم دارد: SHA-256 و SHA-512. SHA-224، واریانت یا متغیره SHA-256 با مقادیر آغازین و خروجی کوتاه شده متفاوت می‌باشد. SHA-384 و SHA-512/224 و SHA-512/256 کمتر شناخته شده، همه از واریانت‌های SHA-512 بشمار می‌روند. SHA-512 امن تر از SHA-256 است و معمولاً در ماشین‌های ۶۴ بیتی مثل AMD64، سریعتر از SHA-256 می‌باشد. تابع هیون
formula_122 تابع هش
در طراحی این درهم سازی باید مقدار formula_11 نسبت به m اول باشد تا اینکه کلیهٔ درایه‌های جدول وارسی شوند. یک روش مناسب انتخاب m به صورت توان ۲ و طراحی g به طوری است که همیشه یک عدد فرد تولید کند. یک روش دیگر آن است که m عدد اول باشد و g همیشه یک عدد صحیح و مثبت کوچکتر از m را تولید کند. تابع هش رمزنگاری
کاربرد ساده سازه فوق که در آن اندازه خروجی هش برابر است با اندازه حالت داخلی (بین هر مرحله فشرده سازی)، به طراحی هش "لوله یا میله-باریک" منجر می‌شود. این طراحی دارای عیب‌های ذاتی متعددی می‌باشد، مثل "کشیده کردن طول"، چندبرخوردی (۹)، حملات پیام طولانی (۱۰)، حملات تولید و paste، ولی نمی‌توانند جفت یا برابر شوند. در نتیجه، توابع درهم پیشرفته روی سازه لوله-پهن ساخته می‌شوند که دارای اندازه حالت داخلی بزرگتری است- و دامنه آن از پیچ ساه فوق تا سازه‌های جدید نظیر "سازه ابر" و سازه HAIFA گستر ده شده‌است (۱۱). هیچ‌یک از ورودی‌های "رقابت تابع درهم NIST" از سازه قدیمی Merkle–Damgård استفاده نمی‌کنند. تابع همانی
تابع همانی (با دامنهٔ اعداد حقیقی) یک تابع خطّی با شیب ۱ و عرض از مبدأ صفر است. اصل لانه کبوتری
اصل لانه کبوتری در علوم کامپیوتر به کار می‌رود برای مثال تداخل در جدول هش اجتناب ناپذیر است زیرا تعداد کلیدهای امکان‌پذیر از تعداد اندیسهای آرایه بیشتر است. الگوریتم هش از این تداخل‌ها نمی‌تواند جلوگیری کند. این اصل می‌تواند برای اثبات الگوریتم فشرده‌سازی بی‌اتلاف داده‌ها استفاده شود، به صورتی که داده‌های ورودی را کوچکتر می‌کند همچنین برخی از داده‌ها را بزرگتر می‌کند. به‌طور دیگر مجموعهٔ همهٔ رشته‌های ورودی به میزان طول داده شدهٔ " L" می‌توانند به مجموعه‌ای از همهٔ رشته‌ها به طول کمتر از "L "و بدون تداخل نگاشته شوند. تابع هش رمزنگاری
SHA-1 به عنوان بخشی از پروژه «اصلی» دولت آمریکا معرفی شده بود. مشخصه اصلی آن که در حال حاضر با SHA-0 شناخته می‌شود- الگوریتمش در سال ۱۹۹۳ تحت استاندارد هش امن، FIPS PUB 180 توسط نهاد استاندارد دولتی آمریکا NIST (مؤسسه ملی استاندارد و فناوری) منتشر شده بود. مدت کوتاهی بعد از انتشار آن توسط NSA رد شد و با نسخه بازبینی شده (تجدید نظر شده) آن جایگزینش شد و در سال ۱۹۹۵ در FIPS PUB 180-1 چاپ شد و با SHA-1 شناخته شد. برخورد در برابر الگوریتم کامل SHA-1 را می‌توان با استفاده از «حمله خرد شده» تولید کرد و باید تابع درهم را شکسته در نظر گرفت. SHA-1 چکیده درهم ۱۶۰بیتی (۲۰ بایتی) تولید می‌کند. ساختار مرکل–دمگارد
اکنون این مقدار کمی هدر رفته‌است زیرا به معنی ایجاد یک بلوک کامل برای یک مقدار طول است؛ بنابراین یک بهینه‌سازی سرعت جزئی وجود دارد که اکثر الگوریتم‌های هش از آن استفاده می‌کنند. اگر فضای کافی در بین صفرهای منتهی به آخرین بلوک وجود داشته باشد، در عوض می‌توان مقدار طول را در آنجا پر کرد. تشخیص و تصحیح خطا
تشخیص خطا اغلب با یک تابع درهم‌سازی مناسب صورت می‌گیرد یک تابع هش برچسب‌هایی باطول ثابت را به پیام می‌افزاید و که گیرنده را قادر می‌سازد که پیام دریافتی را با بررسی برچسب صحت آن را تأیید کند. طرح‌های بسیار زیادی برای تابع‌های هشی وجود دارد اما استفاده از آن‌ها بسته به سادگی یا مناسب بودن برای تشخیص نوع خاصی از خطاهست. تکنولوژی آشکارساز دستکاری
از سند، ایمیل یا فایلی که باید محافظت شود، برای تولید یک تابع هش امضاشده که عدد تولیدشده از محتوای سند است، استفاده می‌شود. هرگونه تغییری در سند، هرچند بی‌اهمیت مانند تغییر تنها یک بیت از ۱ به ۰، منجر به ایجاد هش متفاوتی می‌شود که امضا را نامعتبر می‌کند. با فرض آن‌که تابع هش و برنامه‌ای که آن را اجرا می‌کند به‌طور مناسبی طراحی شده باشند، تغییر یک سند در حالی که همان هش را حفظ کند کار بسیار مشکلی است. اثر بهمن و را نگاه کنید. رفاه ازدست‌رفته
در محاسبهٔ رفاه از دست رفته باید به این مورد توجه کرد که ما از کدام تابع تقاضا استفاده می‌کنیم. در تابع تقاضای مارشالی از مفهوم مازاد مصرف‌کننده استفاده می‌شود. در این روش برای بیان و محاسبه رفاه از دست رفته، از تابع تقاضا استفاده می‌شود. به عنوان مثال در حالتی که تابع عرضه کل کاملاً بدون کشش باشد، رفاه از دست رفته صفر است. اما در روش هیکسی تحلیل رفاه از دست رفته از طریق منحنی‌های بی‌تفاوتی انجام می‌شود. نتیجه جالبی که حاصل می‌شود این است که در منحنی‌های تقاضای مارشالی که کاملاً بدون کشش هستند، رفاه از دست رفته برابر اثر جانشینی است، که این اثر جانشینی خود حاصل دخالت دولت در بازار کامل و تغییر قیمت نسبی در آن است. تابع هش
(٪ به معنای باقی‌مانده تقسیم کلید بر ۱۰۰ است) این تابع صرفاً دو رقم آخر کلید را بازمی‌گرداند. اگر یک کلید درهم‌سازی، به i درهم‌سازی شود، کلید و رکورد آن را در [S[i نگهداری می‌کنیم. این راهبرد کلیدها را به ترتیب نگهداری نمی‌کند، یعنی این تابع فقط در صورتی قابل استفاده‌است که هرگز نیاز به بازیابی کارآمد داده‌ها به صورت ترتیبی نباشد. اگر نیاز به این کار باشد، یکی از روش‌های بحث شده در قبل را باید به کار برد. اگر هیچ دو کلیدی به یک اندیس یکسان درهم‌سازی نشوند، این روش به خوبی عمل می‌کند. ولی هنگامی که تعداد قابل ملاحظه‌ای کلید وجود داشته باشد، به ندرت چنین می‌شود. برای مثال، اگر ۱۰۰ کلید وجود داشته باشد تعداد حالاتی که هیچ دو کلیدی به یک اندیس یکسان درهم‌سازی نشوند نسبت به تعداد حالاتی که هر کلید به هر یک از ۱۰۰ اندیس درهم‌سازی شود، ، عبارت است از: تابع درهم‌سازی کامل
یک تابع درهم سازی کامل حداقلی یک نوع تابع درهم سازی کامل است که کلید را به عدد صحیح متوالی - معمولاً اعداد از تا یا از تا مرتبط می‌سازد (نقشه یا هش می‌کند). یک روش معمول برای اجرای این موارد: اجازه دهید و عناصر برخی از مجموعه محدود باشند. یک تابع هش کامل حداقلی است اگر و تنها اگر دلالت بر (تزریق) کند و یک عدد صحیح مانند وجود داشته باشد طوری که برد F برابر می‌باشد. ثابت شده‌است که برد هدف اصلی یک تابع درهم سازی کامل حداقل به ۱٫۴۴ بیت / کلید نیاز دارد. در صورت اختصاص زمان کافی، بهترین توابع درهم سازی کامل حداقلی شناخته شده در حال حاضر با استفاده کمتر از ۲٫۱ بیت / کلید ارائه شده‌است. تابع هش
فرض کنید کلیدها اعداد صحیحی از یک تا ۱۰۰ باشند و حدود ۱۰۰ رکورد وجود دارد. یک روش کارآمد برای مرتب‌سازی رکوردها، ایجاد آرایه S با ۱۰۰ عنصر و نگهداری رکوردی با کلید i در [S[i است. بازیابی، بدون درنگ صورت می‌پذیرد و مقایسه کلیدها صورت نمی‌پذیرد. اگر حدود ۱۰۰ رکورد وجود داشته باشد و کلیدها، شماره‌های شناسایی ۹ رقمی باشند، همین راهبرد را می‌توان به کار برد ولی به لحاظ حافظه، کارایی بسیار کمی دارد زیرا آرایه‌ای با یک میلیارد عنصر برای نگهداری تنها ۱۰۰ رکورد مورد نیاز است. به طریق دیگر، می‌توانیم آرایه‌ای با تنها ۱۰۰ عنصر که از ۰ تا ۹۹ اندیس‌گذاری می‌شود، ایجاد کنیم و هر کلید را به مقداری میان ۰ تا ۹۹ درهم‌سازی کنیم. تابع درهم‌سازی تابعی است که هر کلید را به یک اندیس تبدیل می‌کند و استفاده از تابع درهم‌سازی در مورد یک کلید خاص را «کلید درهم‌سازی» می‌گویند. در مورد شماره‌های شناسایی، یک تابع درهم‌سازی ممکن، عبارت‌است از: تابع هش رمزنگاری
اندازه‌های قابل پیکربندی خروجی نیز با استفاده از توابع SHAKE-128 و SHAKE-256 بدست می‌آیند. در اینجا الحاقی‌های ۱۲۸- و ۲۵۶- دلالت ضمنی بر توان امنیتی تابع به نسبت اندازه خروجی در بیت‌ها دارند. تابع پله‌ای هویساید
این تابع در انتگرال‌گیری و همچنین اثبات دلایل تجزیه کسری کاربرد دارد. تابع هیون
formula_104 رابطه هم‌ارزی
با توجه به آن‌چه گفته شد، یکی از راه‌هایی که برای نمایش رابطهٔ ترتیب استفاده می‌شود به نمودار هسه موسوم است. شیوهٔ ترسیم این نمودار به این صورت است که ابتدا گراف جهت‌دار نمایش رابطه را مشخص می‌کنیم. حال از آن‌جا که می‌دانیم رابطهٔ ترتیب بازتابی است، نیازی نیست که طوقه‌ها را نیز در نمودار باقی بگذاریم. پس آن‌ها را حذف می‌کنیم. از طرفی می‌دانیم که رابطهٔ ترتیب ترایایی نیز هست؛ بنابراین محتاج به رسم یال‌هایی که این رابطه را نشان می‌دهند نیز نیستیم. پس می‌شود آن‌ها را هم حذف کرد. آن‌چه که پس از این روال به دست می‌آید، نمودار هسه خوانده می‌شود. برای مثال فرض کنید می‌خواهیم رابطهٔ بخش‌پذیری را روی مجموعه {۱٬۳،۴٬۶،۱۲} نمایش دهیم. این کار چنان که می‌بینید به کمک یک گراف جهت‌دار امکان‌پذیر است. حال اگر روال گفته‌شده را روی این گراف اعمال کنیم، نمودار هسه به دست می‌آید. تابع همانی
تابع همانی یک تابعی است که هر عدد حقیقی را به خود ان عدد نظیر می‌کند. حمله تصادم
امضای دیجیتال: از آنجا که الگوریتم‌های امضای دیجیتالی نمی‌توانند مقدار زیادی از داده‌ها را به شکل کارآمد امضا کنند. برای امضا اکثر پیاده‌سازی با استفاده از یک تابع هش (فشرده ساز)به منظور کاهش مقدار داده‌های تا یک حد ممکن به منظور رسیدن به یک سایز ثابت صورت می‌گیرد. برنامه‌های امضای دیجیتال، اغلب در معرض تصادم هش هستند، مگر اینکه از روش‌های مانند هش تصادفی استفاده شود. توجه داشته ب شید که همه گواهی‌های کلید عمومی، مانند گواهی SSL، بر امنیت امضای دیجیتال تکیه می‌کنند و توسط تصادم هش به خطر میوفتند. نمودار هسه
مثال‌های زیر نشان دهنده ی این موضوع است. که یک مجموعه ی توانی همراه چهار عضو توسط رابطه زیر مجموعه بودن تنظیم شده‌اند. هر عضو از زیر مجموعه توانی به صورت باینری نشانه گذاری شده اند و نشان دهنده این است که یک عضو خاص در زیرمجموعه، یک است یا صفر. تابع هش رمزنگاری
در فوریه ۲۰۰۵، حمله ای روی SHA-1 گزارش شد که در حدود عملیات درهمسازی ۲۶۹ را شامل می‌شد، به جای مقدار مورد انتظار ۲۸۰ برای تابع درهم ۱۶۰ بیتی. در آگوست ۲۰۰۵، حمله دیگر روی SHA-1 گزارش شد که برخورد در ۲۶۳ عملیات را نشان می‌داد. نقاط ضعف نظری دیگر SHA-1 از این قرارند: (۲۱، ۲۲) و در فوریه ۲۰۱۷ گوگل خبر از برخورد در SHA-1 داد (۲۳). محققین حوزه امنیت توصیه کردند که اپلیکیشن‌های جدید می‌توانند با استفاده از اعضای خانواده SHA این مشکلات را برطرف کنند، مثل SHA-2 یا استفاده از تکنیک‌هایی نظیر درهم سازی تصادفی (۲۱)(۱) که نیازی به مقاومت در برابر برخورد ندارد. تابع هش رمزنگاری
برخی از توابع درهم نظیر Skein, Keccak و RadioGatún یک دنباله یا مسیر طولانی اختیاری را تولید می‌کنند و می‌توانند به عنوان «رمزهای دنباله ای» استفاده شوند. هم چنین رمزهای دنباله ای را می‌توان از از توابع درهم با چکیده طول-ثابت استفاده کرد. اغلب این کار با اولین ساخت «سازنده اعداد تصادفی ساختگی امن از نظر رمزنگاری» و سپس با استفاده از دنباله بایت‌های تصادفی مثل keystream انجام می‌شود. SEAL یک رمزنگار دنباله ای است که از SHA-1 برای تولید جداول داخلی استفاده می‌کند و سپس در سازنده keystream بکار گرفته می‌شود که به الگوریتم درهم مرتبط یا غیرمرتبط است. SEAL را نمی‌توان مثل SHA-1 قوی یا ضعیف تضمین کرد. بطور مشابه، گسترش کلید رمزنگارهای دنباله ای HC-128 و HC-256 استفاده زیاد از تابع درهم SHA-256 را به دنبال دارد. تابع هش رمزنگاری
چکیده پیام نیز به عنوان ابزاری برای شناسایی معتبر یک فایل استفاده می‌شود. چند سیستم «مدیریت رمز سورس» مثل Git, Mercurial, Monotone از sha1sum انواع مختلف محتوا (محتوای فایل، درخت‌های راهنما، اطلاعات پیشینیان و غیره) برای شناسایی تک به تک آنها استفاده می‌کنند. هش‌ها برای شناسایی فایل‌ها روی شبکه‌های به اشتراک گذاری فایل ههمتا استفاده می‌شوند. برای مثال، در لینک ed2k، تابع درهم متغیر-MD4 با اندازه فایل ترکیب می‌شود و اطلاعات کافی برای پیدا کردن مکان سورس‌های فایل، دانلود فایل و تأیید محتوای آن فراهم می‌کند. «لینک‌های مگنت» مثال دیگری از این دست می‌باشند. این هش‌های فایل بیشتر هش بالا «فهرست هش» یا «درخت هش» هستند که مزایای زیادی دارند. تابع هش
در روش زنجیره‌ای عناصری را که به وسیله تابع درهم‌سازی به یک درایه از جدول درهم‌سازی- مثلاً iS- نگاشته می‌شوند به صورت یک لیست خطی یک‌سویه درمی‌آوریم و آدرس شروع آن را در همان درایه، یعنی قرار می‌دهیم. در حالت کلی عناصر با کلیدهای مختلف k که مقدار آن‌ها برابر است در لیست پیوندی قرار می‌گیرند و درایه‌های خالی جدول هم لیست‌های تهی هستند، به چنین جدولی، جدول درهم‌سازی با روش زنجیره‌ای می‌گوییم. در این روش اعمال درج در زمان انجام می‌شود، اما عمل جستجو و حذف با یک عمل جستجوی عنصر همراه است که در بدترین حالت هزینه‌ای متناسب با طول لیست دارد. آژانس امنیت ملی
توابع هش (درهم‌ساز) اس‌اچ‌ای-۱ و اس‌اچ‌ای-۲ که به طور گسترده، مورد استفاده هستند را آژانس امنیت ملی، طراحی کرده است. اس‌اچ‌ای-۱ که اصلاح جزئی الگوریتم ضعیفتر اس‌اچ‌ای-۰ است را نیز آژانس امنیت ملی در سال ۱۹۹۳ طراحی کرد. این اصلاح جزئی از اس‌اچ‌ای-۰ به اس‌اچ‌ای-۱ را آژانس امنیت ملی، ۲ سال پس از اس‌اچ‌ای-۰ بدون هیچ توجیهی مگر برای افزایش امنیت، پیشنهاد داده بود. بین سال‌های ۱۹۹۸ و ۲۰۰۵ رمزنگاران دانشگاهی، یک حمله به اس‌اچ‌ای-۰ را پیدا کردند که بر الگوریتم اصلاح شده، عمل نمی‌کرد. به دلیل ضعف و محدودیت طول کلید اس‌اچ‌ای-۱، مؤسسه ملی فناوری و استانداردها استفاده از آنرا برای امضای دیجیتال، منع کرده و از سال ۲۰۱۳ تنها، الگوریتم‌های اس‌اچ‌ای-۲ را برای چنین کاربردهایی تایید می‌کند. تابع هش رمزنگاری
اندازه خروجی بیت‌ها، با تعمیم نام "SHA" مشخص می‌شود، بنابراین SHA-224 دارای اندازه خروجی ۲۲۴ بیتی (۲۸ بایتی) است، SHA-256 32 بایت، SHA-384 48 بایت و نهایتاً SHA-512 64 بایت تولید می‌کنند. تابع چبیشف
formula_1 تابع هش
می‌گوییم H یک خانواده از توابع درهم ساز سراسری است اگر: در ازای هر دو کلید k1 و k2 که عضو مجموعهٔ کلیدهای مورد نظر ما هستند، تعداد توابع درهم ساز مانند h که عضو H هستند به طوری که formula_12 حداکثر برابر formula_13 باشد. تابع هش رمزنگاری
- مقاومت در برابر تصویر اولیه و پردازش نشده تابع هش
که در آن توابع h و g تابه‌های درهم ساز کمکی هستند. اولین وارسی در formula_9 انجام می‌شود و وارسی‌های بعدی به درایه‌ای با فاصله formula_10 می‌رود. مثالی از این درج در شکل زیر آمده‌است، در این مثال، m=۱۳ و و است. تابع هش رمزنگاری
یکی از کاربردهای اصلی «تابع درهم» جستجوی سریع داده در «جدول درهم» است. توابع درهم رمزنگار بعنوان توابع درهم از یک نوع خاص، خودشان کاربردهای متنوعی دارند. تابع هش رمزنگاری
SHA-2 (الگوریتم درهم ایمن ۲) مجموعه توابع درهم رمزنگارانه می‌باشد که توسط آژانس امنیت ملی ایالات متحده (NSA) طراحی شده بود، و اولین بار در سال ۲۰۰۱ منتشر گردید. آنها با استفاده از ساختار Merkle–Damgård، از خود تابع فشرده یک سویه با استفاده از سازه Davies–Meyer از رمزنگار بلوکی تخصصی (طبقه‌بندی شده) ساخته می‌شوند. تابع هش رمزنگاری
چکیده‌های هش MD5, SHA1 یا SHA2 بعضاً روی وب سایت‌ها برای تأیید درستی فایل‌های دانلود شده منتشر می‌شوند (۸)، که شامل فایل‌های بازیابی شده با استفاده از «به اشتراک گذاری فایل» مثل «معکوس نمودن» می‌شود. این عمل یک زنجیره اطمینان می‌سازد تا زمانیکه هش‌ها روی سایت مطمئنی پست شوند- معمولاً سایتی که با پسوند معتبر HTTPS تأیید شود. با استفاده از تابع درهم ساز رمزنگاری و زنجیره اطمینان، تغییرات خطرناک فایل تشخیص داده می‌شوند. سایر «کدهای تشخیص خطا» مثل «کنترل افزونگی دوره ای» تنها از تغییرات غیرخطرناک فایل جلوگیری به عمل می‌آورند. کاوش خطی
با ترکیب این دو عامل می‌توان به عملکرد بهتر حافظه نهان کمک کرد. کاوش خطی یک جزء از برنامه‌های آدرس دهی باز برای استفاده از یک جدول درهم ساز برای حل مشکل فرهنگ لغت است. در مشکل فرهنگ لغت، داده ساختار باید بتواند یک مجموعه ای از کلید-مقدار را که عملیات اضافه و حذف را روی جفت موضوع‌ها هم کلید و هم مقدار حفظ کند و جستجو را برای مقدار مرتبط با یک کلید داده شده برقرار کند. در راه حل‌های آدرس دهی باز برای این مشکل، داده ساختار یک آرایه T (جدول درهم ساز) است که سلول‌های [ T [ i (هنگام غیر خالی) هر یک از جفت کلید-مقدار را ذخیره می‌کنند. یک تابع درهم ساز برای نشان دادن هر کلید به سلول T استفاده می‌شود که این کلید باید ذخیره شود، به‌طور کلی کلیدهای کلاسیک را کپی می‌کند تا کلیدهایی با مقادیر مشابه در کنار یکدیگر در جدول قرار نداشته باشند. هنگامی که تابع درهم ساز یک کلید را به یک سلول که قبلاً توسط یک کلید دیگر اشغال شده‌است نگاشت می‌کند، یک برخورد هش به‌ وجود می‌آید. کاوش خطی راه حلی برای حل این برخوردها می‌باشد.که با قرار دادن کلید جدید در نزدیک‌ترین سلول خالی زیرین، این برخورد و تصادفات را حل می‌کند. ساختار مرکل–دمگارد
با توجه به ضعف ساختاری سازه‌های مرکل - دمگارد به خصوص مشکل گسترش طول و حملات مالتی‌کالیژنی، استفان لاکس استفاده از هش لوله گسترده را پیشنهاد کرد، به جای این که به ساختار مرکل دمگارد، درهم سازی لوله گسترده بسیار شبیه ساختار مرکل - دمگارد است اما دارای اندازه داخلی بزرگ‌تر است، به این معنی که طول بیتی که از داخل استفاده می‌شود بزرگ‌تر از طول بیت خروجی است. اگر یک هش از n بیت مورد نظر باشد، تابع فشرده‌سازی f مقدار 2n بیت از ارزش زنجیره‌ای و m بیت پیام را می‌گیرد و این مقدار را به خروجی 2n بیت فشرده می‌کند. کشف گذرواژه
در عمل رمزگذاری توابع هشی همانند bcrypt که در مدیریت حریم شخصی یک کاربر بسیار بهتر از توابعی از قبیل MD5 و SHA عمل می‌کند. براساس قواعد NIST پسوردهای انتخابی یک کاربر می‌تواند هشت کاراکتری به صورت ترکیبی از اعداد، نمادها یا گذر واژه‌های معمول انتخاب شده ویا موارد موجود در فرهنگ لغت‌های فیلتر شده در الگوریتم کد باشد وتاحدود ۳۰ بیت برسد. اگر چندین تابع هش برای بازگردانی هش تولیدشده به رمز اولیه وجود داشته باشد پسورد مورد نظر در عرض چند ثانیه رمزگشایی می‌شود. اگر چندین رایانه شخصی به‌طور هم‌زمان شروع به حمله برای شکستن یک رمز عبورکنند توانایی کرک پسورد به میزان قابل توجهی بیشتر از انجام این عمل توسط botnet می‌شود. پردازنده‌های گرافیکی می‌توانند در مقایسه با رایانه‌های معمولی ۵۰ تا ۱۰۰ برابر سرعت کرک پسورد را افزایش دهند. تابع هیون
formula_105 تابع هش
formula_3 به ازای i = ۰ , ۱ , … m-1 به ازای یک کلید k، ابتداformula_4 را وارسی می‌کنیم سپس به formula_5 و بعد به formula_6 می‌رویم و این کار را به صورت حلقوی ادامه می‌دهیم تا به formula_7 برسیم. در این حالت فقط m دنبالهٔ وارسی مجزا تولید می‌شود. درهم سازی دوگانه یک روش وارسی است که در آن توابع در هم سازی به صورت زیر است: تابع هش رمزنگاری
تابع هش رمزنگاری (CHF) یک الگوریتم ریاضی است که داده‌هایی با اندازه اختیاری (به آن «پیام» گفته می‌شود) را به یک آرایه بیتی با اندازه ثابت (به آن «درهَمَک»، «هش» یا «چکیده پیام» گفته می‌شود) نگاشت می‌دهد. ویژگی مهم این تابع «یک‌طرفه بودن» آن است و این یعنی تابعی است که وارون‌سازی آن از نظر عملی اجراپذیر نیست. از نظر ایده‌آل تنها روش یافتن پیامی که یک هش معین را ساخته‌است، انجام یک جستجوی غیرهوشمندانه روی همه ورودی‌های ممکن است تا ببینیم که آیا همخوانی دارند یا نه، روش دیگر استفاده از یک جدول رنگین‌کمانی از درهمک‌های همخوان است. توابع درهمک‌ساز رمزنگاری، یکی از ابزارهای اساسی در رمزنگاری مدرن هستند. مجموعه (نوع داده انتزاعی)
بعلاوه ، در زبانهایی که از نقشه پشتیبانی می کنند اما مجموعه نیستند ، می توان مجموعه ها را از نظر نقشه پیاده سازی کرد. به عنوان مثال ، اصطلاح رایج برنامه نویسی در Perl که آرایه ای را به هش تبدیل می کند که مقادیر آن مقدار نگهبان 1 است ، برای استفاده به عنوان یک مجموعه ، این است: my %elements = map { $_ => 1 } @elements; از دیگر روشهای معروف می توان به آرایه ها اشاره کرد . به طور خاص می توان زیرمجموعه ای از عددهای صحیح 1 .. "n" را به عنوان یک آرایه بیتی "n-" bit به طور کارآمد پیاده سازی کرد ، که همچنین از عملکردهای بسیار کارآمد اتحاد و تقاطع پشتیبانی می کند. نقشه بلوم با استفاده از یک نمایش بسیار فشرده اما با احتمال کمی احتمال مثبت کاذب در نمایش داده ها ، یک مجموعه را به صورت احتمالاتی پیاده سازی می کند. تابع هش رمزنگاری
هرچند، در مقایسه با توابع درهم استاندارد، توابع درهم ساز رمزنگارانه، هزینه محاسبات بالایی دارند. بهمین دلیل، آنها در زمینه‌هایی کاربرد دارند که در آنها حفاظت کاربران در برابر جعل اسناد و امضاء سازی (تولید داده با یک چکیده به شکل داده مد نظر) ضروری می‌باشد.