पियर्सन हैशिंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Fast 8-bit hash function}} | {{short description|Fast 8-bit hash function}} | ||
'''पियर्सन हैशिंग''' एक [[हैश फंकशन|हैश]] फ़ंक्शन है जिसे 8-बिट [[प्रोसेसर रजिस्टर]] वाले प्रोसेसर पर तेजी से निष्पादन के लिए डिज़ाइन किया गया है। किसी भी संख्या में बाइट्स वाले इनपुट को देखते हुए, यह आउटपुट के रूप में एक बाइट उत्पन्न करता है जो इनपुट के प्रत्येक बाइट पर दृढ़ता से निर्भर होता है। इसके कार्यान्वयन के लिए केवल कुछ निर्देशों की आवश्यकता होती है, साथ ही एक 256-बाइट लुकअप | '''पियर्सन हैशिंग''' एक [[हैश फंकशन|हैश]] फ़ंक्शन है जिसे 8-बिट [[प्रोसेसर रजिस्टर]] वाले प्रोसेसर पर तेजी से निष्पादन के लिए डिज़ाइन किया गया है। किसी भी संख्या में बाइट्स वाले इनपुट को देखते हुए, यह आउटपुट के रूप में एक बाइट उत्पन्न करता है जो इनपुट के प्रत्येक बाइट पर दृढ़ता से निर्भर होता है। इसके कार्यान्वयन के लिए केवल कुछ निर्देशों की आवश्यकता होती है, साथ ही एक 256-बाइट लुकअप टेबल जिसमें 0 से 255 तक के मानों का क्रमपरिवर्तन होता है।<ref name=acmref>{{Citation | ||
|title= Fast Hashing of Variable-Length Text Strings | |title= Fast Hashing of Variable-Length Text Strings | ||
|first= Peter K. | |first= Peter K. | ||
| Line 18: | Line 18: | ||
}}</ref> | }}</ref> | ||
यह हैश फ़ंक्शन एक CBC-MAC है जो एक प्रतिस्थापन | यह हैश फ़ंक्शन एक CBC-MAC है जो एक प्रतिस्थापन टेबल के माध्यम से कार्यान्वित 8-बिट प्रतिस्थापन सिफर का उपयोग करता है। 8-बिट सिफर में नगण्य क्रिप्टोग्राफ़िक सुरक्षा होती है, इसलिए पियर्सन हैश फ़ंक्शन क्रिप्टोग्राफ़िक रूप से प्रबल नहीं है, लेकिन यह हैश टेबल्स को लागू करने या डेटा अखंडता जांच कोड के रूप में उपयोगी है, जिसके लिए यह निम्नलिखित लाभ प्रदान करता है: | ||
*यह अत्यंत सरल है. | *यह अत्यंत सरल है. | ||
* यह संसाधन-सीमित प्रोसेसर पर शीघ्रता से निष्पादित होता है। | * यह संसाधन-सीमित प्रोसेसर पर शीघ्रता से निष्पादित होता है। | ||
* इनपुट का कोई सरल वर्ग नहीं है जिसके लिए हैश | * इनपुट का कोई सरल वर्ग नहीं है जिसके लिए हैश संघर्ष (कल्लिसिओं) (समान आउटपुट) विशेष रूप से संभावित हैं। | ||
* इनपुट के एक लघु, विशेषाधिकार प्राप्त सेट (उदाहरण के लिए, एक कंपाइलर के लिए आरक्षित शब्द) को देखते हुए, क्रमपरिवर्तन | * इनपुट के एक लघु, विशेषाधिकार प्राप्त सेट (उदाहरण के लिए, एक कंपाइलर के लिए आरक्षित शब्द) को देखते हुए, क्रमपरिवर्तन टेबल को समायोजित किया जा सकता है ताकि उन इनपुटों से अलग-अलग हैश मान प्राप्त हों, जो कि एक आदर्श हैश फ़ंक्शन कहलाता है। | ||
* बिल्कुल एक अक्षर से भिन्न दो इनपुट स्ट्रिंग कभी | * बिल्कुल एक अक्षर से भिन्न दो इनपुट स्ट्रिंग कभी कल्लिसिओं नहीं हैं।<ref name="univ">{{Citation | ||
|title= The universality of iterated hashing over variable-length strings | |title= The universality of iterated hashing over variable-length strings | ||
|first= Daniel | |first= Daniel | ||
| Line 36: | Line 36: | ||
|arxiv= 1008.1715|doi= 10.1016/j.dam.2011.11.009}}</ref> उदाहरण के लिए, एबीसी और एईसी स्ट्रिंग्स पर एल्गोरिदम लागू करने से कभी भी समान मान उत्पन्न नहीं होगा। | |arxiv= 1008.1715|doi= 10.1016/j.dam.2011.11.009}}</ref> उदाहरण के लिए, एबीसी और एईसी स्ट्रिंग्स पर एल्गोरिदम लागू करने से कभी भी समान मान उत्पन्न नहीं होगा। | ||
8-बिट प्रोसेसर के लिए डिज़ाइन किए गए अन्य हैशिंग एल्गोरिदम के साथ तुलना करने पर इसकी कमियों में से एक सुझाई गई 256-बाइट लुकअप | 8-बिट प्रोसेसर के लिए डिज़ाइन किए गए अन्य हैशिंग एल्गोरिदम के साथ तुलना करने पर इसकी कमियों में से एक सुझाई गई 256-बाइट लुकअप टेबल है, जो सैकड़ों बाइट्स के क्रम में प्रोग्राम मेमोरी आकार वाले एक छोटे माइक्रोकंट्रोलर के लिए निषेधात्मक रूप से बड़ी हो सकती है। इसका समाधान यह है कि प्रोग्राम मेमोरी में संग्रहीत टेबल के बजाय एक सरल क्रमपरिवर्तन फ़ंक्शन का उपयोग किया जाए। हालाँकि, बहुत सरल फ़ंक्शन का उपयोग करना, जैसे कि <code>T[i] = 255-i</code> हैश फ़ंक्शन के रूप में उपयोगिता को आंशिक रूप से ख़राब कर देता है क्योंकि एनाग्राम के परिणामस्वरूप समान हैश वैल्यू होगा; दूसरी ओर, अत्यधिक काम्प्लेक्स फ़ंक्शन का उपयोग करने से गति पर नकारात्मक प्रभाव पड़ेगा। टेबल के बजाय किसी फ़ंक्शन का उपयोग करने से भी ब्लॉक आकार को बढ़ाया जा सकता है। ऐसे फ़ंक्शन स्वाभाविक रूप से उनके टेबल वेरिएंट की तरह, विशेषणात्मक होने चाहिए। | ||
एल्गोरिथ्म को निम्नलिखित स्यूडोकोड द्वारा वर्णित किया जा सकता है, जो क्रमपरिवर्तन | एल्गोरिथ्म को निम्नलिखित स्यूडोकोड द्वारा वर्णित किया जा सकता है, जो क्रमपरिवर्तन टेबल T का उपयोग करके संदेश C के हैश की गणना करता है: | ||
'''algorithm''' pearson hashing '''is''' | '''algorithm''' pearson hashing '''is''' | ||
| Line 57: | Line 57: | ||
== उदाहरण कार्यान्वयन == | == उदाहरण कार्यान्वयन == | ||
=== | ===C#, 8-बिट === | ||
<syntaxhighlight lang="csharp" line> | <syntaxhighlight lang="csharp" line> | ||
public class PearsonHashing | public class PearsonHashing | ||
| Line 80: | Line 80: | ||
==यह भी देखें== | ==यह भी देखें== | ||
* | * गैर-क्रिप्टोग्राफ़िक हैश फ़ंक्शंस | ||
==संदर्भ == | ==संदर्भ == | ||
Revision as of 21:51, 18 July 2023
पियर्सन हैशिंग एक हैश फ़ंक्शन है जिसे 8-बिट प्रोसेसर रजिस्टर वाले प्रोसेसर पर तेजी से निष्पादन के लिए डिज़ाइन किया गया है। किसी भी संख्या में बाइट्स वाले इनपुट को देखते हुए, यह आउटपुट के रूप में एक बाइट उत्पन्न करता है जो इनपुट के प्रत्येक बाइट पर दृढ़ता से निर्भर होता है। इसके कार्यान्वयन के लिए केवल कुछ निर्देशों की आवश्यकता होती है, साथ ही एक 256-बाइट लुकअप टेबल जिसमें 0 से 255 तक के मानों का क्रमपरिवर्तन होता है।[1]
यह हैश फ़ंक्शन एक CBC-MAC है जो एक प्रतिस्थापन टेबल के माध्यम से कार्यान्वित 8-बिट प्रतिस्थापन सिफर का उपयोग करता है। 8-बिट सिफर में नगण्य क्रिप्टोग्राफ़िक सुरक्षा होती है, इसलिए पियर्सन हैश फ़ंक्शन क्रिप्टोग्राफ़िक रूप से प्रबल नहीं है, लेकिन यह हैश टेबल्स को लागू करने या डेटा अखंडता जांच कोड के रूप में उपयोगी है, जिसके लिए यह निम्नलिखित लाभ प्रदान करता है:
- यह अत्यंत सरल है.
- यह संसाधन-सीमित प्रोसेसर पर शीघ्रता से निष्पादित होता है।
- इनपुट का कोई सरल वर्ग नहीं है जिसके लिए हैश संघर्ष (कल्लिसिओं) (समान आउटपुट) विशेष रूप से संभावित हैं।
- इनपुट के एक लघु, विशेषाधिकार प्राप्त सेट (उदाहरण के लिए, एक कंपाइलर के लिए आरक्षित शब्द) को देखते हुए, क्रमपरिवर्तन टेबल को समायोजित किया जा सकता है ताकि उन इनपुटों से अलग-अलग हैश मान प्राप्त हों, जो कि एक आदर्श हैश फ़ंक्शन कहलाता है।
- बिल्कुल एक अक्षर से भिन्न दो इनपुट स्ट्रिंग कभी कल्लिसिओं नहीं हैं।[2] उदाहरण के लिए, एबीसी और एईसी स्ट्रिंग्स पर एल्गोरिदम लागू करने से कभी भी समान मान उत्पन्न नहीं होगा।
8-बिट प्रोसेसर के लिए डिज़ाइन किए गए अन्य हैशिंग एल्गोरिदम के साथ तुलना करने पर इसकी कमियों में से एक सुझाई गई 256-बाइट लुकअप टेबल है, जो सैकड़ों बाइट्स के क्रम में प्रोग्राम मेमोरी आकार वाले एक छोटे माइक्रोकंट्रोलर के लिए निषेधात्मक रूप से बड़ी हो सकती है। इसका समाधान यह है कि प्रोग्राम मेमोरी में संग्रहीत टेबल के बजाय एक सरल क्रमपरिवर्तन फ़ंक्शन का उपयोग किया जाए। हालाँकि, बहुत सरल फ़ंक्शन का उपयोग करना, जैसे कि T[i] = 255-i हैश फ़ंक्शन के रूप में उपयोगिता को आंशिक रूप से ख़राब कर देता है क्योंकि एनाग्राम के परिणामस्वरूप समान हैश वैल्यू होगा; दूसरी ओर, अत्यधिक काम्प्लेक्स फ़ंक्शन का उपयोग करने से गति पर नकारात्मक प्रभाव पड़ेगा। टेबल के बजाय किसी फ़ंक्शन का उपयोग करने से भी ब्लॉक आकार को बढ़ाया जा सकता है। ऐसे फ़ंक्शन स्वाभाविक रूप से उनके टेबल वेरिएंट की तरह, विशेषणात्मक होने चाहिए।
एल्गोरिथ्म को निम्नलिखित स्यूडोकोड द्वारा वर्णित किया जा सकता है, जो क्रमपरिवर्तन टेबल T का उपयोग करके संदेश C के हैश की गणना करता है:
algorithm pearson hashing is
h := 0
for each c in C loop
h := T[ h xor c ]
end loop
return h
हैश वैरिएबल (h) को अलग ढंग से प्रारंभ किया जा सकता है, उदा. डेटा की लंबाई तक (C) मॉड्यूलो 256; इस विशेष विकल्प का उपयोग नीचे दिए गए पायथन कार्यान्वयन उदाहरण में किया गया है।
उदाहरण कार्यान्वयन
C#, 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
