ما هي وظيفة التجزئة الجيدة؟

Question

ما هي وظيفة التجزئة الجيدة؟لقد رأيت الكثير من وظائف وتطبيقات التجزئة في دورات هياكل البيانات الخاصة بي في الكلية، لكنني أدركت في الغالب أنه من الصعب جدًا إنشاء وظيفة تجزئة جيدة.وكقاعدة عامة لتجنب الاصطدامات قال أستاذي ما يلي:

function Hash(key)
  return key mod PrimeNumber
end

(mod هو عامل التشغيل % في لغة C واللغات المشابهة)

مع أن يكون الرقم الأولي هو حجم جدول التجزئة.أفهم أن هذه وظيفة جيدة إلى حد ما لتجنب الاصطدامات وهي وظيفة سريعة، ولكن كيف يمكنني إنشاء وظيفة أفضل؟هل هناك وظائف تجزئة أفضل لمفاتيح السلسلة مقابل المفاتيح الرقمية؟

Answer 1

لإجراء عمليات بحث في جدول التجزئة "العادي" على أي نوع من البيانات بشكل أساسي - يعد هذا البحث الذي أجراه Paul Hsieh أفضل ما استخدمته على الإطلاق.

http://www.azillionmonkeys.com/qed/hash.html

إذا كنت تهتم بالتشفير الآمن أو أي شيء آخر أكثر تقدمًا، إذن YMMV.إذا كنت تريد فقط وظيفة تجزئة للأغراض العامة للبحث في جدول التجزئة، فهذا هو ما تبحث عنه.

Answer 2

لا يوجد شيء اسمه "وظيفة تجزئة جيدة" للتجزئة العامة (ed.نعم، أعلم أن هناك شيئًا مثل "التجزئة العامة" ولكن هذا ليس ما أقصده).اعتمادًا على السياق، تحدد معايير مختلفة جودة التجزئة.لقد ذكر شخصان بالفعل SHA.هذا تجزئة تشفير وهو ليس جيدًا على الإطلاق لجداول التجزئة، وهو ما تقصده على الأرجح.

جداول التجزئة لها متطلبات مختلفة جدًا.ولكن لا يزال من الصعب العثور على دالة تجزئة جيدة عالميًا لأن أنواع البيانات المختلفة تكشف معلومات مختلفة يمكن تجزئتها.وكقاعدة عامة، من الجيد أن نأخذها بعين الاعتبار الجميع المعلومات التي يحملها النوع متساوية.وهذا ليس بالأمر السهل دائمًا أو حتى ممكنًا.ولأسباب تتعلق بالإحصاءات (وبالتالي الاصطدام)، من المهم أيضًا إنشاء انتشار جيد على مساحة المشكلة، أي.جميع الكائنات الممكنة.هذا يعني أنه عند تجزئة الأرقام بين 100 و1050، ليس من الجيد السماح للرقم الأكثر أهمية بلعب دور كبير في التجزئة لأنه بالنسبة لحوالي 90% من الكائنات، سيكون هذا الرقم 0.من الأهم بكثير السماح للأرقام الثلاثة الأخيرة بتحديد التجزئة.

وبالمثل، عند تجزئة السلاسل، من المهم مراعاة جميع الأحرف - إلا عندما يكون معروفًا مسبقًا أن الأحرف الثلاثة الأولى من جميع السلاسل ستكون هي نفسها؛النظر في هذه إذن هو مضيعة.

هذه في الواقع إحدى الحالات التي أنصح فيها بقراءة ما يقوله كنوث فن برمجة الكمبيوتر, ، المجلد.3.قراءة جيدة أخرى هي كتاب جوليان ووكر فن التجزئة.

Answer 3

هناك غرضان رئيسيان لوظائف التجزئة:

• لتفريق نقاط البيانات بشكل موحد إلى n بت.
• لتحديد البيانات المدخلة بشكل آمن.

من المستحيل التوصية بالتجزئة دون معرفة الغرض الذي تستخدمه من أجله.

إذا كنت تقوم فقط بإنشاء جدول تجزئة في أحد البرامج، فلا داعي للقلق بشأن مدى قابلية الخوارزمية للعكس أو الاختراق...SHA-1 أو AES غير ضروريين على الإطلاق لهذا الغرض، فمن الأفضل أن تستخدم ملف اختلاف FNV.يحقق FNV تشتتًا أفضل (وبالتالي عدد أقل من الاصطدامات) مقارنة بالنموذج الأساسي البسيط كما ذكرت، كما أنه أكثر قدرة على التكيف مع أحجام الإدخال المختلفة.

إذا كنت تستخدم التجزئة لإخفاء المعلومات العامة والمصادقة عليها (مثل تجزئة كلمة المرور أو المستند)، فيجب عليك استخدام إحدى خوارزميات التجزئة الرئيسية التي تم فحصها بواسطة التدقيق العام. صالة وظيفة التجزئة مكان جيد للبدء.

Answer 4

هذا مثال جيد ومثال أيضًا على سبب عدم رغبتك في كتابة واحدة أبدًا.إنها تجزئة Fowler / Noll / Vo (FNV) وهي عبارة عن أجزاء متساوية من عبقرية علوم الكمبيوتر والفودو النقي:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

يحرر:

• يوصي Landon Curt Noll بـ موقعه خوارزمية FVN-1A عبر خوارزمية FVN-1 الأصلية:تعمل الخوارزمية المحسنة على توزيع البايت الأخير في التجزئة بشكل أفضل.لقد قمت بتعديل الخوارزمية وفقًا لذلك.

Answer 5

أود أن أقول إن القاعدة الأساسية هي عدم التدحرج بنفسك.حاول استخدام شيء تم اختباره بدقة، على سبيل المثال، SHA-1 أو شيء من هذا القبيل.

Answer 6

دالة التجزئة الجيدة لها الخصائص التالية:

1. نظرًا لتجزئة رسالة ما، فمن غير الممكن حسابيًا للمهاجم العثور على رسالة أخرى بحيث تكون تجزئاتها متطابقة.

2. بالنظر إلى زوج من الرسائل، m' وm، فمن غير الممكن حسابيًا العثور على اثنتين بحيث يكون h(m) = h(m')

الحالتين هما لا نفس الشيء.في الحالة الأولى، هناك تجزئة موجودة مسبقًا تحاول العثور على تصادم لها.في الحالة الثانية، أنت تحاول العثور عليه أي رسالتان تتصادمان.المهمة الثانية أسهل بكثير بسبب "مفارقة" عيد الميلاد.

عندما لا يكون الأداء مشكلة كبيرة، يجب عليك دائمًا استخدام وظيفة التجزئة الآمنة.هناك هجمات ذكية للغاية يمكن تنفيذها عن طريق فرض الاصطدامات في التجزئة.إذا استخدمت شيئًا قويًا منذ البداية، فسوف تؤمن نفسك ضده.

لا تستخدم MD5 أو SHA-1 في التصميمات الجديدة.معظم خبراء التشفير، بما فيهم أنا، يعتبرونها معطلة.المصدر الرئيسي للضعف في كلا هذين التصميمين هو أن الخاصية الثانية، التي ذكرتها أعلاه، لا تنطبق على هذه الإنشاءات.إذا تمكن أحد المهاجمين من إنشاء رسالتين، m وm'، بحيث يتم تجزئتهما بنفس القيمة، فيمكنهما استخدام هذه الرسائل ضدك.يعاني SHA-1 وMD5 أيضًا من هجمات امتدادات الرسائل، والتي يمكن أن تضعف تطبيقك بشكل قاتل إذا لم تكن حذرًا.

يعد التجزئة الأكثر حداثة مثل Whirpool خيارًا أفضل.إنه لا يعاني من هجمات امتداد الرسائل ويستخدم نفس الرياضيات التي يستخدمها AES لإثبات الأمان ضد مجموعة متنوعة من الهجمات.

امل ان يساعد!

Answer 7

ما تقوله هنا هو أنك تريد أن يكون لديك جهاز يستخدم مقاومة الاصطدام.حاول استخدام SHA-2.أو حاول استخدام تشفير كتلة (جيد) في وظيفة ضغط أحادية الاتجاه (لم تجرب ذلك من قبل)، مثل AES في وضع Miyaguchi-Preenel.المشكلة في ذلك هي أنك تحتاج إلى:

1) لديك IV.حاول استخدام أول 256 بت من الأجزاء الكسرية لثابت خينشين أو شيء من هذا القبيل.2) لديك مخطط الحشو.سهل.استخرجها من تجزئة مثل MD5 أو SHA-3 (Keccak [تنطق 'ket-chak']).إذا كنت لا تهتم بالأمن (قال عدد قليل من الآخرين هذا)، فانظر إلى FNV أو lookup2 بواسطة Bob Jenkins (في الواقع أنا أول من يوصي بـ lookup2) جرب أيضًا MurmurHash، فهو سريع (حدد هذا:.16 سي بي بي).