دالة تجزئة غير مشفرة

تُعدّ دوال التجزئة غير المشفرة ( NCHFs ^{[ 1 ]} ) دوال تجزئة مُصممة للتطبيقات التي لا تتطلب متطلبات الأمان الصارمة لدوال التجزئة المشفرة (مثل مقاومة الصورة الأصلية ) ، وبالتالي يمكن أن تكون أسرع وأقل استهلاكًا للموارد. ^{[ 2 ]} من الأمثلة النموذجية على دوال التجزئة غير المشفرة المُحسّنة لوحدة المعالجة المركزية: FNV-1a و Murmur3 . ^{[ 3 ]} تُستخدم بعض دوال التجزئة غير المشفرة في التطبيقات المشفرة (عادةً بالاشتراك مع عناصر تشفيرية أخرى)؛ وفي هذه الحالة تُوصف بأنها دوال تجزئة شاملة . ^{[ 4 ]}

من بين الاستخدامات الشائعة لدوال التجزئة غير المشفرة مرشحات بلوم ، وجداول التجزئة ، ومخططات العد . تتطلب هذه التطبيقات، بالإضافة إلى السرعة، توزيعًا منتظمًا وخصائص الانهيار . ^{[ 3 ]} تُعد مقاومة التصادم ميزة إضافية مفيدة ضد هجمات إغراق التجزئة ؛ فدوال التجزئة غير المشفرة البسيطة، مثل فحص التكرار الدوري (CRC)، تفتقر أساسًا إلى مقاومة التصادم ^{[ 5 ]} ، وبالتالي لا يمكن استخدامها مع مدخلات قابلة للتلاعب من قِبل المهاجم.

تُستخدم خوارزميات NCHF في أنظمة متنوعة: محللات المفردات ، والمترجمات ، وقواعد البيانات ، وشبكات الاتصالات ، وألعاب الفيديو، وخوادم نظام أسماء النطاقات ، وأنظمة الملفات - أي مكان في الحوسبة حيث توجد حاجة للعثور على المعلومات بسرعة كبيرة (ويفضل أن يكون ذلك في زمن O(1) ، مما سيحقق أيضًا قابلية توسع مثالية ). ^{[ 6 ]}

إستيبانيز وآخرون. قم بإدراج "أهم" NCHFs: ^{[ 7 ]}

• تم ابتكار دالة التجزئة فاولر-نول-فو (FNV) بواسطة غلين فاولر وفونغ فو عام 1991 بمساهمات من لاندون كورت نول . وتُستخدم دالة FNV، بنسختيها FNV-1 وFNV-1a، على نطاق واسع في أنظمة تشغيل لينكس ، وفري بي إس دي ، وخوادم نظام أسماء النطاقات (DNS)، وشبكة ملفات الشبكة (NFS) ، وتويتر ، وبلاي ستيشن 2 ، وإكس بوكس ، وغيرها.
• تم إنشاء دالة التجزئة lookup3 بواسطة روبرت جينكينز . وتُستخدم هذه الدالة على نطاق واسع ويمكن العثور عليها في PostgreSQL وLinux و Perl و Ruby و Infoseek .
• ابتكر بول هسيه خوارزمية SuperFastHash مستوحياً أفكارها من FNV و lookup3، وكان من أهدافها تحقيق تأثير تراكمي عالٍ. تُستخدم هذه الخوارزمية في WebKit (جزء من متصفحي Safari و Google Chrome ).
• تم إنشاء MurmurHash 2 بواسطة أوستن أبلبي في عام 2008 ويتم استخدامه في libmemcached و Maatkit و Apache Hadoop .
• DJBX33A ("دانيال ج. بيرنشتاين، الضرب في 33 مع الجمع"). اقترح دانيال ج. بيرنشتاين هذه الدالة البسيطة جدًا للضرب والجمع . تتميز هذه الدالة بالسرعة والكفاءة أثناء التهيئة. تستخدم العديد من بيئات البرمجة المبنية على PHP 5 و Python و ASP.NET متغيرات من هذه الدالة. إلا أن هذه الدالة عرضة للاختراق ، مما يعرض الخوادم للخطر.
• تم إنشاء BuzHash بواسطة روبرت أوزغاليس في عام 1992. وهو مصمم حول جدول استبدال ويمكنه تحمل التوزيعات المنحرفة للغاية على المدخلات.
• DEK هو تجزئة ضربية مبكرة تعتمد على اقتراح من دونالد كنوث، وهو أحد أقدم أنواع التجزئة التي لا تزال قيد الاستخدام.

تتضمن دوال التجزئة غير المشفرة المُحسّنة للبرمجيات غالبًا عملية الضرب. ونظرًا لأن الضرب في الأجهزة يستهلك موارد كثيرة ويحد من التردد، فقد اقتُرحت تصميمات أكثر ملاءمة لدوائر ASIC ، بما في ذلك SipHash (التي تتميز بميزة إضافية تتمثل في إمكانية استخدام مفتاح سري للتحقق من صحة الرسائل )، وNSGAhash، وXORhash. على الرغم من إمكانية استخدام التشفير الخفيف تقنيًا لنفس التطبيقات، إلا أن زمن استجابة خوارزمياته عادةً ما يكون مرتفعًا جدًا بسبب كثرة عدد الجولات . ^{[ 3 ]} يقترح ساتيسان وآخرون استخدام إصدارات ذات عدد جولات أقل من دوال التجزئة والتشفير الخفيفة كدوال تجزئة غير مشفرة. ^{[ 2 ]}

تتميز العديد من خوارزميات NCHF بحجم نتيجة صغير نسبيًا (على سبيل المثال، 64 بت لخوارزمية SipHash أو حتى أقل): لا يؤدي حجم النتيجة الكبير إلى زيادة أداء التطبيقات المستهدفة، ولكنه يبطئ الحساب، حيث يلزم توليد المزيد من البتات. ^{[ 8 ]}

• ساتيسان، أريش؛ بيسمانز، جيلي؛ كلايسن، توماس؛ فليجن، جو؛ مينتنز، نيلي (أبريل 2023). "خوارزميات وهياكل مُحسَّنة لوظائف التجزئة السريعة غير المشفرة في الأجهزة" (ملف PDF) . المعالجات الدقيقة والأنظمة الدقيقة . 98 104782. doi : 10.1016/j.micpro.2023.104782 . ISSN 0141-9331 . 
• إستيبانيز، سيزار؛ سايز، ياجو؛ ريسيو، جوستافو؛ إيساسي ، بيدرو (28 يناير 2013). "أداء وظائف التجزئة غير المشفرة الأكثر شيوعًا" (PDF) . البرمجيات: الممارسة والخبرة . 44 (6): 681-698 . دوى : 10.1002/spe.2179 . ISSN 0038-0644 . 
• ستامب، مارك (8 نوفمبر 2011). "التجزئات غير المشفرة" . أمن المعلومات: المبادئ والتطبيق (  الطبعة الثانية). جون وايلي وأولاده. ISBN 978-1-118-02796-7. OCLC 1039294381 . 
• باتجيري، ريبون؛ ناياك، سابوزيما؛ موبالانيني، ناريش بابو (25 أبريل 2023). مرشح بلوم: بنية بيانات لشبكات الحاسوب، والبيانات الضخمة، والحوسبة السحابية، وإنترنت الأشياء، والمعلوماتية الحيوية، وما وراءها . دار النشر الأكاديمية. الصفحات 37-38 . ISBN  978-0-12-823646-8. OCLC 1377693258 . 
• ميتلباخ، أرنو؛ فيشلين، مارك (2021). "التجزئة غير المشفرة". نظرية دوال التجزئة والأوراكل العشوائية . تشام: دار نشر سبرينغر الدولية. ص 303-334 . doi : 10.1007/978-3-030-63287-8_7 . ISBN  978-3-030-63286-1.