हैश कल्लिसिओं: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Hash function phenomenon}} | {{Short description|Hash function phenomenon}} | ||
[[File:Hash table 4 1 1 0 0 1 0 LL.svg|thumb|254x254px|जॉन स्मिथ और सैंड्रा डी का हैश मान 02 समान है, जिससे हैश टकराव होता है।]][[कंप्यूटर विज्ञान]] में, हैश टकराव या हैश टकराव<ref>{{Citation|last=Thomas|first=Cormen|title=Introduction to Algorithms |date=2009|pages=253|publisher=MIT Press|isbn=978-0-262-03384-8}}</ref> यह तब होता है जब [[हैश तालिका]] में डेटा के दो टुकड़े समान हैश मान साझा करते हैं। इस स्थिति में हैश मान एक [[हैश फंकशन]] से प्राप्त होता है जो डेटा इनपुट लेता है और बिट्स की एक निश्चित लंबाई लौटाता है।<ref>{{Citation|last=Stapko|first=Timothy|title=Embedded Security|date=2008|url=http://dx.doi.org/10.1016/b978-075068215-2.50006-9|work=Practical Embedded Security|pages=83–114|publisher=Elsevier|doi=10.1016/b978-075068215-2.50006-9|isbn=9780750682152|access-date=2021-12-08}}</ref> | [[File:Hash table 4 1 1 0 0 1 0 LL.svg|thumb|254x254px|जॉन स्मिथ और सैंड्रा डी का हैश मान 02 समान है, जिससे हैश टकराव होता है।]]<math>\vec{a} </math>[[कंप्यूटर विज्ञान]] में, हैश टकराव या हैश टकराव<ref>{{Citation|last=Thomas|first=Cormen|title=Introduction to Algorithms |date=2009|pages=253|publisher=MIT Press|isbn=978-0-262-03384-8}}</ref> यह तब होता है जब [[हैश तालिका]] में डेटा के दो टुकड़े समान हैश मान साझा करते हैं। इस स्थिति में हैश मान एक [[हैश फंकशन]] से प्राप्त होता है जो डेटा इनपुट लेता है और बिट्स की एक निश्चित लंबाई लौटाता है।<ref>{{Citation|last=Stapko|first=Timothy|title=Embedded Security|date=2008|url=http://dx.doi.org/10.1016/b978-075068215-2.50006-9|work=Practical Embedded Security|pages=83–114|publisher=Elsevier|doi=10.1016/b978-075068215-2.50006-9|isbn=9780750682152|access-date=2021-12-08}}</ref> | ||
चूँकि हैश एल्गोरिदम [[टकराव प्रतिरोध]] के आशय से बनाए गए हैं, फिर भी वे कभी-कभी एक ही हैश में अलग-अलग डेटा को मैप कर सकते हैं (पिजनहोल सिद्धांत के आधार पर) दुर्भावनापूर्ण उपयोगकर्ता इसका लाभ उठाकर डेटा की प्रतिलिपि कर सकते हैं, उस तक पहुंच बना सकते हैं या उसमें बदलाव कर सकते हैं।<ref>{{cite web|last1=Schneier|first1=Bruce|author-link1=Bruce Schneier|title=Cryptanalysis of MD5 and SHA: Time for a New Standard|url=https://www.schneier.com/essays/archives/2004/08/cryptanalysis_of_md5.html|url-status=dead|archive-url=https://web.archive.org/web/20160316114109/https://www.schneier.com/essays/archives/2004/08/cryptanalysis_of_md5.html|archive-date=2016-03-16|access-date=2016-04-20|website=Computerworld|quote=Much more than encryption algorithms, one-way hash functions are the workhorses of modern cryptography.}}</ref> | चूँकि हैश एल्गोरिदम [[टकराव प्रतिरोध]] के आशय से बनाए गए हैं, फिर भी वे कभी-कभी एक ही हैश में अलग-अलग डेटा को मैप कर सकते हैं (पिजनहोल सिद्धांत के आधार पर) दुर्भावनापूर्ण उपयोगकर्ता इसका लाभ उठाकर डेटा की प्रतिलिपि कर सकते हैं, उस तक पहुंच बना सकते हैं या उसमें बदलाव कर सकते हैं।<ref>{{cite web|last1=Schneier|first1=Bruce|author-link1=Bruce Schneier|title=Cryptanalysis of MD5 and SHA: Time for a New Standard|url=https://www.schneier.com/essays/archives/2004/08/cryptanalysis_of_md5.html|url-status=dead|archive-url=https://web.archive.org/web/20160316114109/https://www.schneier.com/essays/archives/2004/08/cryptanalysis_of_md5.html|archive-date=2016-03-16|access-date=2016-04-20|website=Computerworld|quote=Much more than encryption algorithms, one-way hash functions are the workhorses of modern cryptography.}}</ref> | ||
[[डेटा प्रबंधन]] और [[कंप्यूटर सुरक्षा]] (विशेष रूप से, [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]]) में हैश टकराव के संभावित नकारात्मक अनुप्रयोगों के कारण, टकराव से बचाव कंप्यूटर सुरक्षा में एक महत्वपूर्ण विषय बन गया है। | [[डेटा प्रबंधन]] और [[कंप्यूटर सुरक्षा]] (विशेष रूप से, [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]]) में हैश टकराव के संभावित नकारात्मक अनुप्रयोगों के कारण, टकराव से बचाव कंप्यूटर सुरक्षा में एक महत्वपूर्ण विषय बन गया है। | ||
== पृष्ठभूमि == | == पृष्ठभूमि == | ||
किसी सेट में ऑब्जेक्ट की संख्या के आधार पर हैश टकराव अपरिहार्य हो सकता है और जिस बिट स्ट्रिंग पर उन्हें मैप किया गया है वह लंबाई में अधिक लंबी है या नहीं है जब n वस्तुओं का एक सेट होता है, यदि n |R| से बड़ा है, जो इस स्थिति में R हैश मान की सीमा है, तो हैश टकराव होने की संभावना 1 है, जिसका अर्थ है कि ऐसा होने की आश्वासन देता है।<ref name=":0">{{Cite book|date=2016|title=साइबर सुरक्षा और अनुप्रयुक्त गणित|url=http://dx.doi.org/10.1016/c2015-0-01807-x|doi=10.1016/c2015-0-01807-x|isbn=9780128044520}}</ref> | किसी सेट में ऑब्जेक्ट की संख्या के आधार पर हैश टकराव अपरिहार्य हो सकता है और जिस बिट स्ट्रिंग पर उन्हें मैप किया गया है वह लंबाई में अधिक लंबी है या नहीं है जब n वस्तुओं का एक सेट होता है, यदि n |R| से बड़ा है, जो इस स्थिति में R हैश मान की सीमा है, तो हैश टकराव होने की संभावना 1 है, जिसका अर्थ है कि ऐसा होने की आश्वासन देता है।<ref name=":0">{{Cite book|date=2016|title=साइबर सुरक्षा और अनुप्रयुक्त गणित|url=http://dx.doi.org/10.1016/c2015-0-01807-x|doi=10.1016/c2015-0-01807-x|isbn=9780128044520}}</ref> | ||
| Line 13: | Line 13: | ||
वास्तव में, सुरक्षा-संबंधित एप्लिकेशन क्रिप्टोग्राफ़िक हैश एल्गोरिदम का उपयोग करते हैं, जो इतने लंबे होते हैं कि यादृच्छिक मिलान की संभावना नहीं होती है, इतना तेज़ होता है कि उन्हें कहीं भी उपयोग किया जा सकता है, और इतना सुरक्षित होता है कि टकराव खोजना अधिक कठिन होता है।<ref name="crypto" /> | वास्तव में, सुरक्षा-संबंधित एप्लिकेशन क्रिप्टोग्राफ़िक हैश एल्गोरिदम का उपयोग करते हैं, जो इतने लंबे होते हैं कि यादृच्छिक मिलान की संभावना नहीं होती है, इतना तेज़ होता है कि उन्हें कहीं भी उपयोग किया जा सकता है, और इतना सुरक्षित होता है कि टकराव खोजना अधिक कठिन होता है।<ref name="crypto" /> | ||
== घटित होने की प्रायिकता | == घटित होने की प्रायिकता == | ||
हैश टकराव संयोग से हो सकता है और कई हैश एल्गोरिदम के लिए जानबूझकर बनाया जा सकता है। इस प्रकार हैश टकराव की संभावना एल्गोरिदम के आकार, हैश मानों के वितरण पर निर्भर करती है, और यह विशिष्ट टकराव बनाने के लिए गणितीय रूप से ज्ञात और कम्प्यूटेशनल रूप से व्यवहार्य है या नहीं है। | हैश टकराव संयोग से हो सकता है और कई हैश एल्गोरिदम के लिए जानबूझकर बनाया जा सकता है। इस प्रकार हैश टकराव की संभावना एल्गोरिदम के आकार, हैश मानों के वितरण पर निर्भर करती है, और यह विशिष्ट टकराव बनाने के लिए गणितीय रूप से ज्ञात और कम्प्यूटेशनल रूप से व्यवहार्य है या नहीं है। | ||
Revision as of 12:08, 16 July 2023
कंप्यूटर विज्ञान में, हैश टकराव या हैश टकराव[1] यह तब होता है जब हैश तालिका में डेटा के दो टुकड़े समान हैश मान साझा करते हैं। इस स्थिति में हैश मान एक हैश फंकशन से प्राप्त होता है जो डेटा इनपुट लेता है और बिट्स की एक निश्चित लंबाई लौटाता है।[2]
चूँकि हैश एल्गोरिदम टकराव प्रतिरोध के आशय से बनाए गए हैं, फिर भी वे कभी-कभी एक ही हैश में अलग-अलग डेटा को मैप कर सकते हैं (पिजनहोल सिद्धांत के आधार पर) दुर्भावनापूर्ण उपयोगकर्ता इसका लाभ उठाकर डेटा की प्रतिलिपि कर सकते हैं, उस तक पहुंच बना सकते हैं या उसमें बदलाव कर सकते हैं।[3]
डेटा प्रबंधन और कंप्यूटर सुरक्षा (विशेष रूप से, क्रिप्टोग्राफ़िक हैश फ़ंक्शन) में हैश टकराव के संभावित नकारात्मक अनुप्रयोगों के कारण, टकराव से बचाव कंप्यूटर सुरक्षा में एक महत्वपूर्ण विषय बन गया है।
पृष्ठभूमि
किसी सेट में ऑब्जेक्ट की संख्या के आधार पर हैश टकराव अपरिहार्य हो सकता है और जिस बिट स्ट्रिंग पर उन्हें मैप किया गया है वह लंबाई में अधिक लंबी है या नहीं है जब n वस्तुओं का एक सेट होता है, यदि n |R| से बड़ा है, जो इस स्थिति में R हैश मान की सीमा है, तो हैश टकराव होने की संभावना 1 है, जिसका अर्थ है कि ऐसा होने की आश्वासन देता है।[4]
किसी समय में हैश टकराव की संभावना का एक अन्य कारण गणित में जन्मदिन विरोधाभास के विचार से उत्पन्न होता है। यह समस्या n संख्या वाले लोगों में से यादृच्छिक रूप से चुने गए दो लोगों के समूह का जन्मदिन समान होने की संभावना को देखती है।[5] इस विचार के कारण ही जन्मदिन का हमला कहा गया है। इस हमले का आधार यह है कि ऐसा जन्मदिन खोजना कठिन है जो विशेष रूप से आपके जन्मदिन या किसी विशिष्ट जन्मदिन से मेल खाता हो, किंतु मेल खाने वाले जन्मदिन वाले किन्हीं दो लोगों का एक सेट खोजने की संभावना बहुत बढ़ जाती है। ख़राब अभिनेता इस दृष्टिकोण का उपयोग करके किसी विशिष्ट मान की खोज करने के अतिरिक्त किसी अन्य हैश मान से टकराने वाले हैश मानों को खोजना आसान बना सकते हैं।[6]
टकरावों का प्रभाव अनुप्रयोग पर निर्भर करता है। जब हैश फ़ंक्शंस और फ़िंगरप्रिंट का उपयोग समान डेटा की पहचान करने के लिए किया जाता है, जैसे कि होमोलॉजी (जीव विज्ञान) डीएनए अनुक्रम या समान ऑडियो फ़ाइलें, तो फ़ंक्शंस को स्थानीय-संवेदनशील हैशिंग जैसी तकनीकों का उपयोग करके अलग-अलग किंतु समान डेटा के बीच टकराव की संभावना को अधिकतम करने के लिए डिज़ाइन किया गया है। .[7] दूसरी ओर अंततः, को बहुत अलग इनपुट के बीच टकराव की परवाह किए बिना, समान इनपुट के बीच टकराव की संभावना को कम करने के लिए डिज़ाइन किया गया है।[8] ऐसे उदाहरण जहां बुरे अभिनेता हैश टकराव बनाने या खोजने का प्रयास करते हैं उन्हें टकराव हमले के रूप में जाना जाता है।[9]
वास्तव में, सुरक्षा-संबंधित एप्लिकेशन क्रिप्टोग्राफ़िक हैश एल्गोरिदम का उपयोग करते हैं, जो इतने लंबे होते हैं कि यादृच्छिक मिलान की संभावना नहीं होती है, इतना तेज़ होता है कि उन्हें कहीं भी उपयोग किया जा सकता है, और इतना सुरक्षित होता है कि टकराव खोजना अधिक कठिन होता है।[8]
घटित होने की प्रायिकता
हैश टकराव संयोग से हो सकता है और कई हैश एल्गोरिदम के लिए जानबूझकर बनाया जा सकता है। इस प्रकार हैश टकराव की संभावना एल्गोरिदम के आकार, हैश मानों के वितरण पर निर्भर करती है, और यह विशिष्ट टकराव बनाने के लिए गणितीय रूप से ज्ञात और कम्प्यूटेशनल रूप से व्यवहार्य है या नहीं है।
निम्नलिखित हैश एल्गोरिदम को ध्यान में रखें - सीआरसी-32, एमडी5, और एसएचए-1 ये टकराव के जटिल कार्यो के विभिन्न स्तरों के साथ सामान्य हैश एल्गोरिदम हैं।[10]
सीआरसी-32
सीआरसी-32 में हैश टकराव का सबसे अधिक जटिल है। यह हैश फ़ंक्शन समान्यत: उपयोग के लिए अनुशंसित नहीं है। यदि किसी हब में 77,163 हैश मान हों, तो हैश टकराव होने की संभावना 50% है, जो अन्य विधियों की तुलना में बहुत अधिक है।[11]
एमडी5
एमडी5 सबसे अधिक उपयोग किया जाता है और जब अन्य दो हैश फ़ंक्शंस की तुलना की जाती है, तो यह हैश टकराव जटिल के स्थिति में मध्य मार्ग का प्रतिनिधित्व करता है। हैश टकराव होने की 50% संभावना प्राप्त करने के लिए, हब में 5.06 बिलियन से अधिक रिकॉर्ड होने चाहिए।[11]
एसएचए-1
एसएचए-1 हैश टकराव के लिए सबसे कम जटिल प्रदान करता है। एसएचए-1 फ़ंक्शन के लिए हैश टकराव होने की 50% संभावना के लिए, हब में 1.42 × 1024 रिकॉर्ड होने चाहिए। ध्यान दें, इन उदाहरणों में उल्लिखित रिकॉर्ड की संख्या एक ही हब में होनी चाहिए।[11]
कम संख्या में रिकॉर्ड वाला हब होने से इन सभी हैश फ़ंक्शंस में हैश टकराव की संभावना कम हो सकती है, चूँकि सदैव एक सामान्य जटिल उपस्थित रहेगा जो अपरिहार्य है, जब तक कि टकराव रिज़ॉल्यूशन तकनीकों का उपयोग नहीं किया जाता है।
टकराव समाधान
चूँकि हैश टकराव अपरिहार्य हैं, हैश तालिकाओं में उनसे निपटने के तंत्र होते हैं, जिन्हें टकराव समाधान के रूप में जाना जाता है। सबसे आम रणनीतियों में से दो हैं विवर्त संबोधन और अलग चेनिंग कैश-सचेत टकराव रिज़ॉल्यूशन एक और रणनीति है जिस पर स्ट्रिंग हैश तालिकाओं के लिए अतीत में चर्चा की गई है।
विवर्त संबोधन
हैश तालिका में कोशिकाओं को इस विधि में तीन स्थितियों में से एक सौंपा गया है - अधिकृत कर लिया गया है, जो की रिक्त किया गया है, या फिर हटा दिया गया है। यदि हैश टकराव होता है, तो रिकॉर्ड को एक वैकल्पिक सेल में ले जाने के लिए तालिका की जांच की जाएगी जिसे रिक्त बताया गया है। जब हैश टकराव होता है तो विभिन्न प्रकार की जांच होती है और इस पद्धति को प्रयुक्त किया जाता है। जांच के कुछ प्रकार रैखिक जांच, डबल हैशिंग और द्विघात जांच हैं।[12] ओपन एड्रेसिंग को क्लोज्ड हैशिंग के नाम से भी जाना जाता है।[13]
अलग शृंखला
यह रणनीति हैश तालिका की कोशिकाओं में एक से अधिक रिकॉर्ड को जोड़ने की अनुमति देती है। यदि दो रिकॉर्ड एक ही सेल में निर्देशित किए जा रहे हैं, तो दोनों एक लिंक्ड सूची के रूप में उस सेल में जाएंगे। यह कुशलतापूर्वक हैश टकराव को होने से रोकता है क्योंकि समान हैश मान वाले रिकॉर्ड एक ही सेल में जा सकते हैं, किंतु इसके अपने हानि हैं। इतनी सारी सूचियों पर नज़र रखना कठिन है और जो भी उपकरण उपयोग किया जा रहा है वह बहुत धीमा हो सकता है।[12] अलग चेनिंग को ओपन हैशिंग के रूप में भी जाना जाता है।[14]
कैश-सचेत टकराव संकल्प
चूँकि पिछले दो की तुलना में बहुत कम उपयोग किया गया है, अस्किटिस और ज़ोबेल (2005) ने 2005 में कैश (कंप्यूटिंग)-सचेत टकराव समाधान विधि प्रस्तावित की है।[15] यह अलग-अलग श्रृंखलाबद्ध विधियों के समान विचार है, चूँकि इसमें तकनीकी रूप से श्रृंखलाबद्ध सूचियाँ सम्मिलित नहीं हैं। इस स्थिति में, श्रृंखलाबद्ध सूचियों के अतिरिक्त , हैश मानों को वस्तुओं की एक सन्निहित सूची में दर्शाया जाता है। यह स्ट्रिंग हैश तालिकाओं के लिए उत्तम उपयुक्त है और संख्यात्मक मानों के लिए उपयोग अभी भी अज्ञात है।[12]
यह भी देखें
संदर्भ
- ↑ Thomas, Cormen (2009), Introduction to Algorithms, MIT Press, p. 253, ISBN 978-0-262-03384-8
- ↑ Stapko, Timothy (2008), "Embedded Security", Practical Embedded Security, Elsevier, pp. 83–114, doi:10.1016/b978-075068215-2.50006-9, ISBN 9780750682152, retrieved 2021-12-08
- ↑ Schneier, Bruce. "Cryptanalysis of MD5 and SHA: Time for a New Standard". Computerworld. Archived from the original on 2016-03-16. Retrieved 2016-04-20.
Much more than encryption algorithms, one-way hash functions are the workhorses of modern cryptography.
- ↑ साइबर सुरक्षा और अनुप्रयुक्त गणित. 2016. doi:10.1016/c2015-0-01807-x. ISBN 9780128044520.
- ↑ Soltanian, Mohammad Reza Khalifeh (10 November 2015). DDoS हमलों से बचाव के लिए सैद्धांतिक और प्रायोगिक तरीके. ISBN 978-0-12-805399-7. OCLC 1162249290.
- ↑ Conrad, Eric; Misenar, Seth; Feldman, Joshua (2016), "Domain 3: Security Engineering (Engineering and Management of Security)", CISSP Study Guide, Elsevier, pp. 103–217, doi:10.1016/b978-0-12-802437-9.00004-7, ISBN 9780128024379, retrieved 2021-12-08
- ↑ Rajaraman, A.; Ullman, J. (2010). "Mining of Massive Datasets, Ch. 3".
- ↑ 8.0 8.1 Al-Kuwari, Saif; Davenport, James H.; Bradford, Russell J. (2011). Cryptographic Hash Functions: Recent Design Trends and Security Notions. Inscrypt '10.
- ↑ Schema, Mike (2012). वेब ऐप्स को हैक करना.
- ↑ Altheide, Cory; Carvey, Harlan (2011). ओपन सोर्स टूल्स के साथ डिजिटल फोरेंसिक. Elsevier. pp. 1–8. doi:10.1016/b978-1-59749-586-8.00001-7. ISBN 9781597495868. Retrieved 2021-12-08.
- ↑ 11.0 11.1 11.2 Linstedt, Daniel; Olschimke, Michael (2016). "Scalable Data Warehouse Architecture". Building a Scalable Data Warehouse with Data Vault 2.0. Elsevier. pp. 17–32. doi:10.1016/b978-0-12-802510-9.00002-7. ISBN 9780128025109. Retrieved 2021-12-07.
- ↑ 12.0 12.1 12.2 Nimbe, Peter; Ofori Frimpong, Samuel; Opoku, Michael (2014-08-20). "हैश टेबल्स में टकराव समाधान के लिए एक कुशल रणनीति". International Journal of Computer Applications. 99 (10): 35–41. Bibcode:2014IJCA...99j..35N. doi:10.5120/17411-7990. ISSN 0975-8887.
- ↑ Kline, Robert. "बंद हैशिंग". CSC241 Data Structures and Algorithms. West Chester University. Retrieved 2022-04-06.
- ↑ "ओपन हैशिंग या अलग चेनिंग". Log22.
- ↑ Askitis, Nikolas; Zobel, Justin (2005). Consens, M.; Navarro, G. (eds.). स्ट्रिंग हैश टेबल्स में कैश-सचेत टकराव संकल्प. International Symposium on String Processing and Information Retrieval. String Processing and Information Retrieval SPIRE 2005. Lecture Notes in Computer Science. Vol. 3772. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 91–102. doi:10.1007/11575832_11. ISBN 978-3-540-29740-6.
