हैश कल्लिसिओं: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 4 users not shown)
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 समान है, जिससे हैश संघट्‍टन होता है।]][[कंप्यूटर विज्ञान]] में, '''हैश संघट्‍टन''' या हैश संघट्‍टन <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>


किसी समय में हैश टकराव की संभावना का एक अन्य कारण गणित में [[जन्मदिन की समस्या|जन्मदिन विरोधाभास]] के विचार से उत्पन्न होता है। यह समस्या n संख्या वाले लोगों में से यादृच्छिक रूप से चुने गए दो लोगों के समूह का जन्मदिन समान होने की संभावना को देखती है।<ref>{{Cite book|last=Soltanian |first=Mohammad Reza Khalifeh |url=http://worldcat.org/oclc/1162249290|title=DDoS हमलों से बचाव के लिए सैद्धांतिक और प्रायोगिक तरीके|date=10 November 2015|isbn=978-0-12-805399-7|oclc=1162249290}}</ref> इस विचार के कारण ही जन्मदिन का हमला कहा गया है। इस हमले का आधार यह है कि ऐसा जन्मदिन खोजना कठिन है जो विशेष रूप से आपके जन्मदिन या किसी विशिष्ट जन्मदिन से मेल खाता हो, किंतु मेल खाने वाले जन्मदिन वाले किन्हीं दो लोगों का एक सेट खोजने की संभावना बहुत बढ़ जाती है। ख़राब अभिनेता इस दृष्टिकोण का उपयोग करके किसी विशिष्ट मान की खोज करने के अतिरिक्त किसी अन्य हैश मान से टकराने वाले हैश मानों को खोजना आसान बना सकते हैं।<ref>{{Citation|last1=Conrad|first1=Eric|title=Domain 3: Security Engineering (Engineering and Management of Security)|date=2016|url=http://dx.doi.org/10.1016/b978-0-12-802437-9.00004-7|work=CISSP Study Guide|pages=103–217|publisher=Elsevier|access-date=2021-12-08|last2=Misenar|first2=Seth|last3=Feldman|first3=Joshua|doi=10.1016/b978-0-12-802437-9.00004-7|isbn=9780128024379}}</ref>
किसी समय में हैश संघट्‍टन की संभावना का एक अन्य कारण गणित में [[जन्मदिन की समस्या|उत्पत्ति विरोधाभास]] के विचार से उत्पन्न होता है। यह समस्या n संख्या वाले लोगों में से यादृच्छिक रूप से चुने गए दो लोगों के समूह का उत्पत्ति समान होने की संभावना को देखती है।<ref>{{Cite book|last=Soltanian |first=Mohammad Reza Khalifeh |url=http://worldcat.org/oclc/1162249290|title=DDoS हमलों से बचाव के लिए सैद्धांतिक और प्रायोगिक तरीके|date=10 November 2015|isbn=978-0-12-805399-7|oclc=1162249290}}</ref> इस विचार के कारण ही उत्पत्ति का हमला कहा गया है। इस हमले का आधार यह है कि ऐसा उत्पत्ति खोजना कठिन है जो विशेष रूप से आपके उत्पत्ति या किसी विशिष्ट उत्पत्ति से मेल खाता हो, किंतु मेल खाने वाले उत्पत्ति वाले किन्हीं दो लोगों का एक सेट खोजने की संभावना बहुत बढ़ जाती है। ख़राब अभिनेता इस दृष्टिकोण का उपयोग करके किसी विशिष्ट मान की खोज करने के अतिरिक्त किसी अन्य हैश मान से टकराने वाले हैश मानों को खोजना आसान बना सकते हैं।<ref>{{Citation|last1=Conrad|first1=Eric|title=Domain 3: Security Engineering (Engineering and Management of Security)|date=2016|url=http://dx.doi.org/10.1016/b978-0-12-802437-9.00004-7|work=CISSP Study Guide|pages=103–217|publisher=Elsevier|access-date=2021-12-08|last2=Misenar|first2=Seth|last3=Feldman|first3=Joshua|doi=10.1016/b978-0-12-802437-9.00004-7|isbn=9780128024379}}</ref>


टकरावों का प्रभाव अनुप्रयोग पर निर्भर करता है। जब हैश फ़ंक्शंस और फ़िंगरप्रिंट का उपयोग समान डेटा की पहचान करने के लिए किया जाता है, जैसे कि [[होमोलॉजी (जीव विज्ञान)]] [[डीएनए]] अनुक्रम या समान ऑडियो फ़ाइलें, तो फ़ंक्शंस को स्थानीय-संवेदनशील हैशिंग जैसी तकनीकों का उपयोग करके अलग-अलग किंतु समान डेटा के बीच टकराव की संभावना को अधिकतम करने के लिए डिज़ाइन किया गया है। .<ref name="MOMD">{{cite web|last1=Rajaraman|first1=A.|last2=Ullman|first2=J.|author2-link=Jeffrey Ullman|year=2010|title=Mining of Massive Datasets, Ch. 3.|url=http://infolab.stanford.edu/~ullman/mmds.html}}</ref> दूसरी ओर[[ अंततः, | अंततः,]] को बहुत अलग इनपुट के बीच टकराव की परवाह किए बिना, समान इनपुट के बीच टकराव की संभावना को कम करने के लिए डिज़ाइन किया गया है।<ref name="crypto">{{Cite conference|last1=Al-Kuwari|first1=Saif|last2=Davenport|first2=James H.|last3=Bradford|first3=Russell J.|date=2011|title=Cryptographic Hash Functions: Recent Design Trends and Security Notions|url=https://eprint.iacr.org/2011/565|conference=Inscrypt '10}}</ref> ऐसे उदाहरण जहां बुरे अभिनेता हैश टकराव बनाने या खोजने का प्रयास करते हैं उन्हें टकराव हमले के रूप में जाना जाता है।<ref>{{Cite book|last=Schema|first=Mike|title=वेब ऐप्स को हैक करना|year=2012}}</ref>
संघट्‍टन का प्रभाव अनुप्रयोग पर निर्भर करता है। जब हैश फ़ंक्शंस और फ़िंगरप्रिंट का उपयोग समान डेटा की पहचान करने के लिए किया जाता है, जैसे कि [[होमोलॉजी (जीव विज्ञान)]] [[डीएनए]] अनुक्रम या समान ऑडियो फ़ाइलें, तो फ़ंक्शंस को स्थानीय-संवेदनशील हैशिंग जैसी तकनीकों का उपयोग करके अलग-अलग किंतु समान डेटा के बीच संघट्‍टन की संभावना को अधिकतम करने के लिए डिज़ाइन किया गया है। .<ref name="MOMD">{{cite web|last1=Rajaraman|first1=A.|last2=Ullman|first2=J.|author2-link=Jeffrey Ullman|year=2010|title=Mining of Massive Datasets, Ch. 3.|url=http://infolab.stanford.edu/~ullman/mmds.html}}</ref> दूसरी ओर[[ अंततः, | अंततः,]] को बहुत अलग इनपुट के बीच संघट्‍टन की परवाह किए बिना, समान इनपुट के बीच संघट्‍टन की संभावना को कम करने के लिए डिज़ाइन किया गया है।<ref name="crypto">{{Cite conference|last1=Al-Kuwari|first1=Saif|last2=Davenport|first2=James H.|last3=Bradford|first3=Russell J.|date=2011|title=Cryptographic Hash Functions: Recent Design Trends and Security Notions|url=https://eprint.iacr.org/2011/565|conference=Inscrypt '10}}</ref> ऐसे उदाहरण जहां बुरे अभिनेता हैश संघट्‍टन बनाने या खोजने का प्रयास करते हैं उन्हें संघट्‍टन हमले के रूप में जाना जाता है।<ref>{{Cite book|last=Schema|first=Mike|title=वेब ऐप्स को हैक करना|year=2012}}</ref>


वास्तव में, सुरक्षा-संबंधित एप्लिकेशन क्रिप्टोग्राफ़िक हैश एल्गोरिदम का उपयोग करते हैं, जो इतने लंबे होते हैं कि यादृच्छिक मिलान की संभावना नहीं होती है, इतना तेज़ होता है कि उन्हें कहीं भी उपयोग किया जा सकता है, और इतना सुरक्षित होता है कि टकराव खोजना अधिक कठिन होता है।<ref name="crypto" />
वास्तव में, सुरक्षा-संबंधित एप्लिकेशन क्रिप्टोग्राफ़िक हैश एल्गोरिदम का उपयोग करते हैं, जो इतने लंबे होते हैं कि यादृच्छिक मिलान की संभावना नहीं होती है, इतना तेज़ होता है कि उन्हें कहीं भी उपयोग किया जा सकता है, और इतना सुरक्षित होता है कि संघट्‍टन खोजना अधिक कठिन होता है।<ref name="crypto" />
== घटित होने की प्रायिकता ==
== घटित होने की प्रायिकता                                                                       ==


हैश टकराव संयोग से हो सकता है और कई हैश एल्गोरिदम के लिए जानबूझकर बनाया जा सकता है। इस प्रकार हैश टकराव की संभावना एल्गोरिदम के आकार, हैश मानों के वितरण पर निर्भर करती है, और यह विशिष्ट टकराव बनाने के लिए गणितीय रूप से ज्ञात और कम्प्यूटेशनल रूप से व्यवहार्य है या नहीं है।
हैश संघट्‍टन संयोग से हो सकता है और कई हैश एल्गोरिदम के लिए जानबूझकर बनाया जा सकता है। इस प्रकार हैश संघट्‍टन की संभावना एल्गोरिदम के आकार, हैश मानों के वितरण पर निर्भर करती है, और यह विशिष्ट संघट्‍टन बनाने के लिए गणितीय रूप से ज्ञात और कम्प्यूटेशनल रूप से व्यवहार्य है या नहीं है।


निम्नलिखित हैश एल्गोरिदम को ध्यान में रखें - सीआरसी-32, एमडी5, और एसएचए-1 ये टकराव के जटिल कार्यो के विभिन्न स्तरों के साथ सामान्य हैश एल्गोरिदम हैं।<ref>{{cite book |last1=Altheide |first1=Cory |last2=Carvey |first2=Harlan |title=ओपन सोर्स टूल्स के साथ डिजिटल फोरेंसिक|date=2011 |url=http://dx.doi.org/10.1016/b978-1-59749-586-8.00001-7 |pages=1–8 |publisher=Elsevier |access-date=2021-12-08 |doi=10.1016/b978-1-59749-586-8.00001-7 |isbn=9781597495868}}</ref>
निम्नलिखित हैश एल्गोरिदम को ध्यान में रखें - सीआरसी-32, एमडी5, और एसएचए-1 ये संघट्‍टन के जटिल कार्यो के विभिन्न स्तरों के साथ सामान्य हैश एल्गोरिदम हैं।<ref>{{cite book |last1=Altheide |first1=Cory |last2=Carvey |first2=Harlan |title=ओपन सोर्स टूल्स के साथ डिजिटल फोरेंसिक|date=2011 |url=http://dx.doi.org/10.1016/b978-1-59749-586-8.00001-7 |pages=1–8 |publisher=Elsevier |access-date=2021-12-08 |doi=10.1016/b978-1-59749-586-8.00001-7 |isbn=9781597495868}}</ref>
 
=== सीआरसी-32                                                                                                                                                                                         ===
 
सीआरसी-32 में हैश संघट्‍टन का सबसे अधिक जटिल है। यह हैश फ़ंक्शन समान्यत: उपयोग के लिए अनुशंसित नहीं है। यदि किसी हब में 77,163 हैश मान हों, तो हैश संघट्‍टन होने की संभावना 50% है, जो अन्य विधियों की तुलना में बहुत अधिक है।<ref name=":1">{{cite book |last1=Linstedt |first1=Daniel |last2=Olschimke |first2=Michael |chapter=Scalable Data Warehouse Architecture |date=2016 |url=http://dx.doi.org/10.1016/b978-0-12-802510-9.00002-7 |title=Building a Scalable Data Warehouse with Data Vault 2.0 |pages=17–32 |publisher=Elsevier |access-date=2021-12-07 |doi=10.1016/b978-0-12-802510-9.00002-7 |isbn=9780128025109}}</ref>
=== सीआरसी-32 ===
सीआरसी-32 में हैश टकराव का सबसे अधिक जटिल है। यह हैश फ़ंक्शन समान्यत: उपयोग के लिए अनुशंसित नहीं है। यदि किसी हब में 77,163 हैश मान हों, तो हैश टकराव होने की संभावना 50% है, जो अन्य विधियों की तुलना में बहुत अधिक है।<ref name=":1">{{cite book |last1=Linstedt |first1=Daniel |last2=Olschimke |first2=Michael |chapter=Scalable Data Warehouse Architecture |date=2016 |url=http://dx.doi.org/10.1016/b978-0-12-802510-9.00002-7 |title=Building a Scalable Data Warehouse with Data Vault 2.0 |pages=17–32 |publisher=Elsevier |access-date=2021-12-07 |doi=10.1016/b978-0-12-802510-9.00002-7 |isbn=9780128025109}}</ref>
=== [[एमडी5]] ===
=== [[एमडी5]] ===


[[एमडी5]] सबसे अधिक उपयोग किया जाता है और जब अन्य दो हैश फ़ंक्शंस की तुलना की जाती है, तो यह हैश टकराव जटिल के स्थिति में मध्य मार्ग का प्रतिनिधित्व करता है। हैश टकराव होने की 50% संभावना प्राप्त करने के लिए, हब में 5.06 बिलियन से अधिक रिकॉर्ड होने चाहिए।<ref name=":1" />
[[एमडी5]] सबसे अधिक उपयोग किया जाता है और जब अन्य दो हैश फ़ंक्शंस की तुलना की जाती है, तो यह हैश संघट्‍टन जटिल के स्थिति में मध्य मार्ग का प्रतिनिधित्व करता है। हैश संघट्‍टन होने की 50% संभावना प्राप्त करने के लिए, हब में 5.06 बिलियन से अधिक रिकॉर्ड होने चाहिए।<ref name=":1" />
=== एसएचए-1 ===
=== एसएचए-1 ===


एसएचए-1 हैश टकराव के लिए सबसे कम जटिल प्रदान करता है। एसएचए-1 फ़ंक्शन के लिए हैश टकराव होने की 50% संभावना के लिए, हब में 1.42 × 10{{sup|24}} रिकॉर्ड होने चाहिए। ध्यान दें, इन उदाहरणों में उल्लिखित रिकॉर्ड की संख्या एक ही हब में होनी चाहिए।<ref name=":1" />
एसएचए-1 हैश संघट्‍टन के लिए सबसे कम जटिल प्रदान करता है। एसएचए-1 फ़ंक्शन के लिए हैश संघट्‍टन होने की 50% संभावना के लिए, हब में 1.42 × 10{{sup|24}} रिकॉर्ड होने चाहिए। ध्यान दें, इन उदाहरणों में उल्लिखित रिकॉर्ड की संख्या एक ही हब में होनी चाहिए।<ref name=":1" />


कम संख्या में रिकॉर्ड वाला हब होने से इन सभी हैश फ़ंक्शंस में हैश टकराव की संभावना कम हो सकती है, चूँकि सदैव एक मामूली जटिल उपस्थित रहेगा जो अपरिहार्य है, जब तक कि टकराव रिज़ॉल्यूशन तकनीकों का उपयोग नहीं किया जाता है।
कम संख्या में रिकॉर्ड वाला हब होने से इन सभी हैश फ़ंक्शंस में हैश संघट्‍टन की संभावना कम हो सकती है, चूँकि सदैव एक सामान्य जटिल उपस्थित रहेगा जो अपरिहार्य है, जब तक कि संघट्‍टन रिज़ॉल्यूशन तकनीकों का उपयोग नहीं किया जाता है।


== टकराव समाधान ==
== संघट्‍टन समाधान ==
{{Main Article|हैश तालिका या टकराव समाधान}}
{{Main Article|हैश तालिका या टकराव समाधान}}


चूँकि हैश टकराव अपरिहार्य हैं, हैश तालिकाओं में उनसे निपटने के तंत्र होते हैं, जिन्हें टकराव समाधान के रूप में जाना जाता है। सबसे आम रणनीतियों में से दो हैं [[ खुला संबोधन | विवर्त संबोधन]] और अलग चेनिंग कैश-सचेत टकराव रिज़ॉल्यूशन एक और रणनीति है जिस पर स्ट्रिंग हैश तालिकाओं के लिए अतीत में चर्चा की गई है।
चूँकि हैश संघट्‍टन अपरिहार्य हैं, हैश तालिकाओं में उनसे निपटने के तंत्र होते हैं, जिन्हें संघट्‍टन समाधान के रूप में जाना जाता है। सबसे समान्य रणनीतियों में से दो हैं [[ खुला संबोधन |विवर्त संबोधन]] और अलग चेनिंग कैश-सचेत संघट्‍टन रिज़ॉल्यूशन एक और रणनीति है जिस पर स्ट्रिंग हैश तालिकाओं के लिए अतीत में चर्चा की गई है।


[[File:HASHTB12.svg|thumb|275x275px|जॉन स्मिथ और सैंड्रा डी दोनों को एक ही सेल में निर्देशित किया जा रहा है। ओपन एड्रेसिंग के कारण हैश टेबल सैंड्रा डी को किसी अन्य सेल पर रीडायरेक्ट कर देगी।]]
[[File:HASHTB12.svg|thumb|275x275px|जॉन स्मिथ और सैंड्रा डी दोनों को एक ही सेल में निर्देशित किया जा रहा है। ओपन एड्रेसिंग के कारण हैश टेबल सैंड्रा डी को किसी अन्य सेल पर रीडायरेक्ट कर देगी।]]


=== विवर्त संबोधन ===
=== विवर्त संबोधन ===
{{main|विवर्त  संबोधन}}
{{main|विवर्त  संबोधन}}


हैश तालिका में कोशिकाओं को इस विधि में तीन स्थितियों में से एक सौंपा गया है - अधिकृत कर लिया गया है, जो की रिक्त किया गया है, या फिर हटा दिया गया है। यदि हैश टकराव होता है, तो रिकॉर्ड को एक वैकल्पिक सेल में ले जाने के लिए तालिका की जांच की जाएगी जिसे रिक्त बताया गया है। जब हैश टकराव होता है तो विभिन्न प्रकार की जांच होती है और इस पद्धति को प्रयुक्त किया जाता है। जांच के कुछ प्रकार [[रैखिक जांच]], [[डबल हैशिंग]] और [[द्विघात जांच]] हैं।<ref name=":2">{{Cite journal|last1=Nimbe|first1=Peter|last2=Ofori Frimpong|first2=Samuel |last3=Opoku |first3=Michael |date=2014-08-20 |title=हैश टेबल्स में टकराव समाधान के लिए एक कुशल रणनीति|url=http://dx.doi.org/10.5120/17411-7990 |journal=International Journal of Computer Applications |volume=99|issue=10|pages=35–41|doi=10.5120/17411-7990 |bibcode=2014IJCA...99j..35N|issn=0975-8887|doi-access=free}}</ref> ओपन एड्रेसिंग को क्लोज्ड हैशिंग के नाम से भी जाना जाता है।<ref>{{cite web |title=बंद हैशिंग|work=CSC241 Data Structures and Algorithms |url=https://www.cs.wcupa.edu/rkline/ds/closed-hashing.html |access-date=2022-04-06 |first=Robert |last=Kline |publisher=West Chester University}}</ref>
हैश तालिका में कोशिकाओं को इस विधि में तीन स्थितियों में से एक सौंपा गया है - अधिकृत कर लिया गया है, जो की रिक्त किया गया है, या फिर हटा दिया गया है। यदि हैश संघट्‍टन होता है, तो रिकॉर्ड को एक वैकल्पिक सेल में ले जाने के लिए तालिका की जांच की जाएगी जिसे रिक्त बताया गया है। जब हैश संघट्‍टन होता है तो विभिन्न प्रकार की जांच होती है और इस पद्धति को प्रयुक्त किया जाता है। जांच के कुछ प्रकार [[रैखिक जांच]], [[डबल हैशिंग]] और [[द्विघात जांच]] हैं।<ref name=":2">{{Cite journal|last1=Nimbe|first1=Peter|last2=Ofori Frimpong|first2=Samuel |last3=Opoku |first3=Michael |date=2014-08-20 |title=हैश टेबल्स में टकराव समाधान के लिए एक कुशल रणनीति|url=http://dx.doi.org/10.5120/17411-7990 |journal=International Journal of Computer Applications |volume=99|issue=10|pages=35–41|doi=10.5120/17411-7990 |bibcode=2014IJCA...99j..35N|issn=0975-8887|doi-access=free}}</ref> ओपन एड्रेसिंग को क्लोज्ड हैशिंग के नाम से भी जाना जाता है।<ref>{{cite web |title=बंद हैशिंग|work=CSC241 Data Structures and Algorithms |url=https://www.cs.wcupa.edu/rkline/ds/closed-hashing.html |access-date=2022-04-06 |first=Robert |last=Kline |publisher=West Chester University}}</ref>
 
 
=== अलग शृंखला ===
=== अलग शृंखला ===
{{further|हैश टेबल या अलग चेनिंग}}
{{further|हैश टेबल या अलग चेनिंग}}


यह रणनीति हैश तालिका की कोशिकाओं में एक से अधिक रिकॉर्ड को जोड़ने की अनुमति देती है। यदि दो रिकॉर्ड एक ही सेल में निर्देशित किए जा रहे हैं, तो दोनों एक लिंक्ड सूची के रूप में उस सेल में जाएंगे। यह कुशलतापूर्वक हैश टकराव को होने से रोकता है क्योंकि समान हैश मान वाले रिकॉर्ड एक ही सेल में जा सकते हैं, किंतु इसके अपने हानि हैं। इतनी सारी सूचियों पर नज़र रखना कठिन है और जो भी उपकरण उपयोग किया जा रहा है वह बहुत धीमा हो सकता है।<ref name=":2" /> अलग चेनिंग को ओपन हैशिंग के रूप में भी जाना जाता है।<ref>{{cite web |url=https://www.log2base2.com/algorithms/searching/open-hashing.html |title=ओपन हैशिंग या अलग चेनिंग|work=Log{{sub|2}}2}}</ref>
यह रणनीति हैश तालिका की सेल में एक से अधिक रिकॉर्ड को जोड़ने की अनुमति देती है। यदि दो रिकॉर्ड एक ही सेल में निर्देशित किए जा रहे हैं, तो दोनों एक लिंक्ड सूची के रूप में उस सेल में जाएंगे। यह कुशलतापूर्वक हैश संघट्‍टन को होने से रोकता है क्योंकि समान हैश मान वाले रिकॉर्ड एक ही सेल में जा सकते हैं, किंतु इसके अपने हानि हैं। इतनी सारी सूचियों पर नज़र रखना कठिन है और जो भी उपकरण उपयोग किया जा रहा है वह बहुत धीमा हो सकता है।<ref name=":2" /> अलग चेनिंग को ओपन हैशिंग के रूप में भी जाना जाता है।<ref>{{cite web |url=https://www.log2base2.com/algorithms/searching/open-hashing.html |title=ओपन हैशिंग या अलग चेनिंग|work=Log{{sub|2}}2}}</ref>
 
=== कैश-सचेत संघट्‍टन संकल्प ===
 
=== कैश-सचेत टकराव संकल्प ===
 
चूँकि पिछले दो की तुलना में बहुत कम उपयोग किया गया है, अस्किटिस और ज़ोबेल (2005) ने 2005 में [[कैश (कंप्यूटिंग)]]-सचेत टकराव समाधान विधि प्रस्तावित की है।<ref>{{cite conference |conference=International Symposium on String Processing and Information Retrieval |last1=Askitis|first1=Nikolas |last2=Zobel |first2=Justin |title=स्ट्रिंग हैश टेबल्स में कैश-सचेत टकराव संकल्प|date=2005 |work=String Processing and Information Retrieval SPIRE 2005 |pages=91–102 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |series=Lecture Notes in Computer Science |volume=3772 |doi=10.1007/11575832_11| isbn=978-3-540-29740-6 |editor1-last=Consens |editor1-first=M. |editor2-last=Navarro |editor2-first=G.}}</ref> यह अलग-अलग श्रृंखलाबद्ध विधियों के समान विचार है, चूँकि इसमें तकनीकी रूप से श्रृंखलाबद्ध सूचियाँ सम्मिलित नहीं हैं। इस स्थिति में, श्रृंखलाबद्ध सूचियों के अतिरिक्त , हैश मानों को वस्तुओं की एक सन्निहित सूची में दर्शाया जाता है। यह स्ट्रिंग हैश तालिकाओं के लिए उत्तम उपयुक्त है और संख्यात्मक मानों के लिए उपयोग अभी भी अज्ञात है।<ref name=":2" />
 


चूँकि पिछले दो की तुलना में बहुत कम उपयोग किया गया है, अस्किटिस और ज़ोबेल (2005) ने 2005 में [[कैश (कंप्यूटिंग)]]-सचेत संघट्‍टन समाधान विधि प्रस्तावित की है।<ref>{{cite conference |conference=International Symposium on String Processing and Information Retrieval |last1=Askitis|first1=Nikolas |last2=Zobel |first2=Justin |title=स्ट्रिंग हैश टेबल्स में कैश-सचेत टकराव संकल्प|date=2005 |work=String Processing and Information Retrieval SPIRE 2005 |pages=91–102 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |series=Lecture Notes in Computer Science |volume=3772 |doi=10.1007/11575832_11| isbn=978-3-540-29740-6 |editor1-last=Consens |editor1-first=M. |editor2-last=Navarro |editor2-first=G.}}</ref> यह अलग-अलग श्रृंखलाबद्ध विधियों के समान विचार है, चूँकि इसमें तकनीकी रूप से श्रृंखलाबद्ध सूचियाँ सम्मिलित नहीं हैं। इस स्थिति में, श्रृंखलाबद्ध सूचियों के अतिरिक्त , हैश मानों को वस्तुओं की एक सन्निहित सूची में दर्शाया जाता है। यह स्ट्रिंग हैश तालिकाओं के लिए उत्तम उपयुक्त है और संख्यात्मक मानों के लिए उपयोग अभी भी अज्ञात है।<ref name=":2" />
== यह भी देखें ==
== यह भी देखें ==


Line 65: Line 57:
==संदर्भ==
==संदर्भ==
{{Reflist}}
{{Reflist}}
[[Category: हैशिंग]]
{{DEFAULTSORT:Hash_Collision}}
{{DEFAULTSORT:Hash_Collision}}


 
[[Category:Articles with hatnote templates targeting a nonexistent page|Hash_Collision]]
 
[[Category:Created On 10/07/2023|Hash_Collision]]
[[Category: Machine Translated Page]]
[[Category:Lua-based templates|Hash_Collision]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page|Hash_Collision]]
[[Category:Pages with script errors|Hash_Collision]]
[[Category:Templates Vigyan Ready|Hash_Collision]]
[[Category:Templates that add a tracking category|Hash_Collision]]
[[Category:Templates that generate short descriptions|Hash_Collision]]
[[Category:Templates using TemplateData|Hash_Collision]]
[[Category:हैशिंग|Hash_Collision]]

Latest revision as of 10:22, 27 July 2023

जॉन स्मिथ और सैंड्रा डी का हैश मान 02 समान है, जिससे हैश संघट्‍टन होता है।

कंप्यूटर विज्ञान में, हैश संघट्‍टन या हैश संघट्‍टन [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]

कम संख्या में रिकॉर्ड वाला हब होने से इन सभी हैश फ़ंक्शंस में हैश संघट्‍टन की संभावना कम हो सकती है, चूँकि सदैव एक सामान्य जटिल उपस्थित रहेगा जो अपरिहार्य है, जब तक कि संघट्‍टन रिज़ॉल्यूशन तकनीकों का उपयोग नहीं किया जाता है।

संघट्‍टन समाधान

Main article: हैश तालिका या टकराव समाधान

चूँकि हैश संघट्‍टन अपरिहार्य हैं, हैश तालिकाओं में उनसे निपटने के तंत्र होते हैं, जिन्हें संघट्‍टन समाधान के रूप में जाना जाता है। सबसे समान्य रणनीतियों में से दो हैं विवर्त संबोधन और अलग चेनिंग कैश-सचेत संघट्‍टन रिज़ॉल्यूशन एक और रणनीति है जिस पर स्ट्रिंग हैश तालिकाओं के लिए अतीत में चर्चा की गई है।

जॉन स्मिथ और सैंड्रा डी दोनों को एक ही सेल में निर्देशित किया जा रहा है। ओपन एड्रेसिंग के कारण हैश टेबल सैंड्रा डी को किसी अन्य सेल पर रीडायरेक्ट कर देगी।

विवर्त संबोधन

Main article: विवर्त संबोधन

हैश तालिका में कोशिकाओं को इस विधि में तीन स्थितियों में से एक सौंपा गया है - अधिकृत कर लिया गया है, जो की रिक्त किया गया है, या फिर हटा दिया गया है। यदि हैश संघट्‍टन होता है, तो रिकॉर्ड को एक वैकल्पिक सेल में ले जाने के लिए तालिका की जांच की जाएगी जिसे रिक्त बताया गया है। जब हैश संघट्‍टन होता है तो विभिन्न प्रकार की जांच होती है और इस पद्धति को प्रयुक्त किया जाता है। जांच के कुछ प्रकार रैखिक जांच, डबल हैशिंग और द्विघात जांच हैं।[12] ओपन एड्रेसिंग को क्लोज्ड हैशिंग के नाम से भी जाना जाता है।[13]

अलग शृंखला

Further information: हैश टेबल या अलग चेनिंग

यह रणनीति हैश तालिका की सेल में एक से अधिक रिकॉर्ड को जोड़ने की अनुमति देती है। यदि दो रिकॉर्ड एक ही सेल में निर्देशित किए जा रहे हैं, तो दोनों एक लिंक्ड सूची के रूप में उस सेल में जाएंगे। यह कुशलतापूर्वक हैश संघट्‍टन को होने से रोकता है क्योंकि समान हैश मान वाले रिकॉर्ड एक ही सेल में जा सकते हैं, किंतु इसके अपने हानि हैं। इतनी सारी सूचियों पर नज़र रखना कठिन है और जो भी उपकरण उपयोग किया जा रहा है वह बहुत धीमा हो सकता है।[12] अलग चेनिंग को ओपन हैशिंग के रूप में भी जाना जाता है।[14]

कैश-सचेत संघट्‍टन संकल्प

चूँकि पिछले दो की तुलना में बहुत कम उपयोग किया गया है, अस्किटिस और ज़ोबेल (2005) ने 2005 में कैश (कंप्यूटिंग)-सचेत संघट्‍टन समाधान विधि प्रस्तावित की है।[15] यह अलग-अलग श्रृंखलाबद्ध विधियों के समान विचार है, चूँकि इसमें तकनीकी रूप से श्रृंखलाबद्ध सूचियाँ सम्मिलित नहीं हैं। इस स्थिति में, श्रृंखलाबद्ध सूचियों के अतिरिक्त , हैश मानों को वस्तुओं की एक सन्निहित सूची में दर्शाया जाता है। यह स्ट्रिंग हैश तालिकाओं के लिए उत्तम उपयुक्त है और संख्यात्मक मानों के लिए उपयोग अभी भी अज्ञात है।[12]

यह भी देखें

संदर्भ

  1. ↑ Thomas, Cormen (2009), Introduction to Algorithms, MIT Press, p. 253, ISBN 978-0-262-03384-8
  2. ↑ 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
  3. ↑ 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.
  4. ↑ साइबर सुरक्षा और अनुप्रयुक्त गणित. 2016. doi:10.1016/c2015-0-01807-x. ISBN 9780128044520.
  5. ↑ Soltanian, Mohammad Reza Khalifeh (10 November 2015). DDoS हमलों से बचाव के लिए सैद्धांतिक और प्रायोगिक तरीके. ISBN 978-0-12-805399-7. OCLC 1162249290.
  6. ↑ 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
  7. ↑ Rajaraman, A.; Ullman, J. (2010). "Mining of Massive Datasets, Ch. 3".
  8. ↑ 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.
  9. ↑ Schema, Mike (2012). वेब ऐप्स को हैक करना.
  10. ↑ 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. ↑ 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. ↑ 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.
  13. ↑ Kline, Robert. "बंद हैशिंग". CSC241 Data Structures and Algorithms. West Chester University. Retrieved 2022-04-06.
  14. ↑ "ओपन हैशिंग या अलग चेनिंग". Log22.
  15. ↑ 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हैश_कल्लिसिओं&oldid=226615’