पियर्सन हैशिंग
पियर्सन हैशिंग एक हैश फंकशन है जिसे 8-बिट प्रोसेसर रजिस्टर वाले प्रोसेसर पर तेजी से निष्पादन के लिए डिज़ाइन किया गया है। किसी भी संख्या में बाइट्स वाले इनपुट को देखते हुए, यह आउटपुट के रूप में एक बाइट उत्पन्न करता है जो इनपुट के प्रत्येक बाइट पर दृढ़ता से निर्भर होता है। इसके कार्यान्वयन के लिए केवल कुछ निर्देशों की आवश्यकता होती है, साथ ही एक 256-बाइट लुकअप तालिका जिसमें 0 से 255 तक मानों का क्रमपरिवर्तन होता है।[1] यह हैश फ़ंक्शन एक सीबीसी-मैक है जो एस-बॉक्स के माध्यम से कार्यान्वित 8-बिट [[प्रतिस्थापन सिफ़र ]] का उपयोग करता है। 8-बिट सिफर में नगण्य क्रिप्टोग्राफ़िक सुरक्षा होती है, इसलिए उत्तम हैश फ़ंक्शन क्रिप्टोग्राफ़िक रूप से मजबूत नहीं है, लेकिन यह हैश तालिकाओं को लागू करने या अंततः, के रूप में उपयोगी है, जिसके लिए यह ये लाभ प्रदान करता है:
- यह अत्यंत सरल है.
- यह संसाधन-सीमित प्रोसेसर पर शीघ्रता से निष्पादित होता है।
- इनपुट का कोई सरल वर्ग नहीं है जिसके लिए हैश टकराव (समान आउटपुट) विशेष रूप से संभावित हैं।
- इनपुट के एक छोटे, विशेषाधिकार प्राप्त सेट (उदाहरण के लिए, एक संकलक के लिए आरक्षित शब्द) को देखते हुए, क्रमपरिवर्तन तालिका को समायोजित किया जा सकता है ताकि वे इनपुट अलग-अलग हैश मान उत्पन्न करें, जो एक आदर्श हैश फ़ंक्शन कहलाता है।
- बिल्कुल एक अक्षर से भिन्न दो इनपुट स्ट्रिंग कभी टकराती नहीं हैं।[2] उदाहरण के लिए, एबीसी और एईसी स्ट्रिंग्स पर एल्गोरिदम लागू करने से कभी भी समान मान उत्पन्न नहीं होगा।
8-बिट प्रोसेसर के लिए डिज़ाइन किए गए अन्य हैशिंग एल्गोरिदम के साथ तुलना करने पर इसकी कमियों में से एक सुझाई गई 256 बाइट लुकअप तालिका है, जो सैकड़ों बाइट्स के क्रम में प्रोग्राम मेमोरी आकार वाले एक छोटे microcontroller के लिए निषेधात्मक रूप से बड़ी हो सकती है। इसका एक समाधान प्रोग्राम मेमोरी में संग्रहीत तालिका के बजाय एक सरल क्रमपरिवर्तन फ़ंक्शन का उपयोग करना है। हालाँकि, बहुत सरल फ़ंक्शन का उपयोग करना, जैसे कि T[i] = 255-i, हैश फ़ंक्शन के रूप में प्रयोज्यता को आंशिक रूप से पराजित करता है क्योंकि अनाग्राम के परिणामस्वरूप समान हैश मान होगा; दूसरी ओर, अत्यधिक जटिल फ़ंक्शन का उपयोग करने से गति पर नकारात्मक प्रभाव पड़ेगा। तालिका के बजाय फ़ंक्शन का उपयोग करने से ब्लॉक आकार को बढ़ाने की भी अनुमति मिलती है। ऐसे कार्यों को स्वाभाविक रूप से उनके तालिका वेरिएंट की तरह, विशेषण होना चाहिए।
एल्गोरिदम को निम्नलिखित छद्मकोड द्वारा वर्णित किया जा सकता है, जो क्रमपरिवर्तन तालिका टी का उपयोग करके संदेश सी के हैश की गणना करता है:
'एल्गोरिदम' पियर्सन हैशिंग 'है'
एच := 0
'प्रत्येक के लिए' सी 'इन' सी 'लूप'
एच := टी[एच 'एक्सओआर' सी ]
'अंत पाश'
'वापसी' ज
हैश वैरिएबल (h) को अलग ढंग से प्रारंभ किया जा सकता है, उदा. डेटा की लंबाई तक (C) मॉड्यूलो 256; इस विशेष विकल्प का उपयोग नीचे दिए गए पायथन कार्यान्वयन उदाहरण में किया गया है।
उदाहरण कार्यान्वयन
सी शार्प (प्रोग्रामिंग भाषा)|सी#, 8-बिट
public class PearsonHashing
{
public byte Hash(string input)
{
const byte[] T = { /* Permutation of 0-255 */ };
byte hash = 0;
byte[] bytes = Encoding.UTF8.GetBytes(input);
foreach (var b in bytes)
{
hash = T[(byte)(hash ^ b)];
}
return hash;
}
}
यह भी देखें
संदर्भ
- ↑ Pearson, Peter K. (June 1990), "Fast Hashing of Variable-Length Text Strings" (PDF), Communications of the ACM, 33 (6): 677, doi:10.1145/78973.78978, archived from the original (PDF) on 2012-07-04, retrieved 2013-07-13
- ↑ Lemire, Daniel (2012), "The universality of iterated hashing over variable-length strings", Discrete Applied Mathematics, 160 (4–5): 604–617, arXiv:1008.1715, doi:10.1016/j.dam.2011.11.009
