संघट्टन प्रतिरोध: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 2: Line 2:
[[क्रिप्टोग्राफी]] में, '''कोलीजन रेजिस्टेंस''' [[क्रिप्टोग्राफ़िक हैश फ़ंक्शंस]] की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। <ref name=GoldwasserBellare>[[Shafi Goldwasser|Goldwasser, S.]] and [[Mihir Bellare|Bellare, M.]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"]. Summer course on cryptography, MIT, 1996-2001</ref>{{rp|136}} पिजनहोल प्रिंसिपल का अर्थ है कि आउटपुट से अधिक इनपुट वाले किसी भी हैश फ़ंक्शन में आवश्यक रूप से ऐसी कोलीजन होंगी; <ref name=GoldwasserBellare />{{rp|136}} उन्हें ढूंढना जितना कठिन होगा, हैश फ़ंक्शन उतना ही अधिक क्रिप्टोग्राफ़िक रूप से सुरक्षित होगा।
[[क्रिप्टोग्राफी]] में, '''कोलीजन रेजिस्टेंस''' [[क्रिप्टोग्राफ़िक हैश फ़ंक्शंस]] की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। <ref name=GoldwasserBellare>[[Shafi Goldwasser|Goldwasser, S.]] and [[Mihir Bellare|Bellare, M.]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"]. Summer course on cryptography, MIT, 1996-2001</ref>{{rp|136}} पिजनहोल प्रिंसिपल का अर्थ है कि आउटपुट से अधिक इनपुट वाले किसी भी हैश फ़ंक्शन में आवश्यक रूप से ऐसी कोलीजन होंगी; <ref name=GoldwasserBellare />{{rp|136}} उन्हें ढूंढना जितना कठिन होगा, हैश फ़ंक्शन उतना ही अधिक क्रिप्टोग्राफ़िक रूप से सुरक्षित होगा।


[[जन्मदिन विरोधाभास|बर्थडे पैराडॉक्स]] कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2<sup>''N''/2</sup> (या <math>\scriptstyle \sqrt{ 2^N}</math>) की गणना करता है '''रैंडम इनपुट पर हैश संचा'''लन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि जानवर-बल के हमले की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे आमतौर पर हैश फ़ंक्शन में दोष माना जाता है।<ref name=Lecture21Collision>Pass, R. [https://www.cs.cornell.edu/courses/cs6830/2009fa/scribes/lecture21.pdf "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme"]. Course on Cryptography, Cornell University, 2009</ref>
[[जन्मदिन विरोधाभास|बर्थडे पैराडॉक्स]] कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2<sup>''N''/2</sup> (या <math>\scriptstyle \sqrt{ 2^N}</math>) की गणना करता है '''रैंडम इनपुट पर हैश सं'''चालन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि जानवर-बल के हमले की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे आमतौर पर हैश फ़ंक्शन में दोष माना जाता है।<ref name=Lecture21Collision>Pass, R. [https://www.cs.cornell.edu/courses/cs6830/2009fa/scribes/lecture21.pdf "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme"]. Course on Cryptography, Cornell University, 2009</ref>
[[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] आमतौर पर कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से [[MD5]] और [[SHA-1]] दोनों ने कोलीजन का पता लगाने के लिए पाशविक बल की तुलना में अधिक कुशल तकनीकें प्रकाशित की हैं।<ref>{{Cite web|url=http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf|title=How to Break MD5 and Other Hash Functions|author1=Xiaoyun Wang|author2=Hongbo Yu|accessdate=2009-12-21|archive-url=https://web.archive.org/web/20090521024709/http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf|archive-date=2009-05-21|url-status=dead}}</ref><ref>{{cite conference |author1=Xiaoyun Wang |author2=Yiqun Lisa Yin|author2-link= Yiqun Lisa Yin |author3=Hongobo Yu |title=पूर्ण SHA-1 में टकराव ढूँढना|url=http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf |conference=CRYPTO 2005 |doi=10.1007/11535218_2}}</ref> हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रमाण है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय समस्या (जैसे [[पूर्णांक गुणनखंडन]] या [[असतत लघुगणक]]) जितना कठिन है। उन फ़ंक्शंस को [[प्रमाणित रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] कहा जाता है।<ref name=Lecture21Collision />
[[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] आमतौर पर कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से [[MD5]] और [[SHA-1]] दोनों ने कोलीजन का पता लगाने के लिए पाशविक बल की तुलना में अधिक कुशल तकनीकें प्रकाशित की हैं।<ref>{{Cite web|url=http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf|title=How to Break MD5 and Other Hash Functions|author1=Xiaoyun Wang|author2=Hongbo Yu|accessdate=2009-12-21|archive-url=https://web.archive.org/web/20090521024709/http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf|archive-date=2009-05-21|url-status=dead}}</ref><ref>{{cite conference |author1=Xiaoyun Wang |author2=Yiqun Lisa Yin|author2-link= Yiqun Lisa Yin |author3=Hongobo Yu |title=पूर्ण SHA-1 में टकराव ढूँढना|url=http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf |conference=CRYPTO 2005 |doi=10.1007/11535218_2}}</ref> हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रमाण है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय समस्या (जैसे [[पूर्णांक गुणनखंडन]] या [[असतत लघुगणक]]) जितना कठिन है। उन फ़ंक्शंस को [[प्रमाणित रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] कहा जाता है।<ref name=Lecture21Collision />




==परिभाषा==
==परिभाषा==
कार्यों का एक परिवार {h<sub>''k''</sub> : {0, 1}<sup>एम(के)</sup> → {0, 1}<sup>l(k)</sup>} कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक परिवार है, यदि |m(k)| > |एल(के)| किसी भी k के लिए, अर्थात, h<sub>''k''</sub> इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक h<sub>''k''</sub> k दिए गए बहुपद समय के भीतर गणना की जा सकती है, लेकिन किसी भी संभाव्य बहुपद एल्गोरिथ्म ए के लिए, हमारे पास है
कार्यों का एक परिवार {''h<sub>k</sub>'' : {0, 1}<sup>''m''(''k'')</sup> → {0, 1}<sup>''l''(''k'')</sup>} कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक परिवार है, यदि |m(k)| > |एल(के)| किसी भी k के लिए, अर्थात, h<sub>''k''</sub> इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक h<sub>''k''</sub> k दिए गए बहुपद समय के भीतर गणना की जा सकती है, लेकिन किसी भी संभाव्य बहुपद एल्गोरिथ्म ए के लिए, हमारे पास है


: पीआर [के ← जी(1<sup>n</sup>), (x<sub>1</sub>, एक्स<sub>2</sub>) ← ए(के, 1<sup>n</sup>) एस.टी. एक्स<sub>1</sub> ≠ एक्स<sub>2</sub> लेकिन एच<sub>''k''</sub>(एक्स<sub>1</sub>) = एच<sub>''k''</sub>(एक्स<sub>2</sub>)] < उपेक्षा(n),
: Pr [''k'' ← ''G''(1<sup>''n''</sup>), (''x''<sub>1</sub>, ''x''<sub>2</sub>) ← ''A''(''k'', 1<sup>''n''</sup>) s.t. ''x''<sub>1</sub> ≠ ''x''<sub>2</sub> but ''h<sub>k</sub>''(''x''<sub>1</sub>) = ''h<sub>k</sub>''(''x''<sub>2</sub>)] < negl(''n''),


जहां negl(·) कुछ नगण्य फ़ंक्शन को दर्शाता है, और n सुरक्षा पैरामीटर है।<ref>{{cite web|last1=Dodis|first1=Yevgeniy|title=Lecture 12 of Introduction to Cryptography|url=http://cs.nyu.edu/courses/fall08/G22.3210-001/lect/lecture12.pdf|accessdate=3 January 2016}}, def 1.</ref>
जहां negl(·) कुछ नगण्य फ़ंक्शन को दर्शाता है, और n सुरक्षा पैरामीटर है।<ref>{{cite web|last1=Dodis|first1=Yevgeniy|title=Lecture 12 of Introduction to Cryptography|url=http://cs.nyu.edu/courses/fall08/G22.3210-001/lect/lecture12.pdf|accessdate=3 January 2016}}, def 1.</ref>

Revision as of 13:36, 5 August 2023

क्रिप्टोग्राफी में, कोलीजन रेजिस्टेंस क्रिप्टोग्राफ़िक हैश फ़ंक्शंस की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। [1]: 136  पिजनहोल प्रिंसिपल का अर्थ है कि आउटपुट से अधिक इनपुट वाले किसी भी हैश फ़ंक्शन में आवश्यक रूप से ऐसी कोलीजन होंगी; [1]: 136  उन्हें ढूंढना जितना कठिन होगा, हैश फ़ंक्शन उतना ही अधिक क्रिप्टोग्राफ़िक रूप से सुरक्षित होगा।

बर्थडे पैराडॉक्स कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2N/2 (या ) की गणना करता है रैंडम इनपुट पर हैश संचालन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि जानवर-बल के हमले की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे आमतौर पर हैश फ़ंक्शन में दोष माना जाता है।[2] क्रिप्टोग्राफ़िक हैश फ़ंक्शन आमतौर पर कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से MD5 और SHA-1 दोनों ने कोलीजन का पता लगाने के लिए पाशविक बल की तुलना में अधिक कुशल तकनीकें प्रकाशित की हैं।[3][4] हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रमाण है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय समस्या (जैसे पूर्णांक गुणनखंडन या असतत लघुगणक) जितना कठिन है। उन फ़ंक्शंस को प्रमाणित रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन कहा जाता है।[2]


परिभाषा

कार्यों का एक परिवार {hk : {0, 1}m(k) → {0, 1}l(k)} कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक परिवार है, यदि |m(k)| > |एल(के)| किसी भी k के लिए, अर्थात, hk इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक hk k दिए गए बहुपद समय के भीतर गणना की जा सकती है, लेकिन किसी भी संभाव्य बहुपद एल्गोरिथ्म ए के लिए, हमारे पास है

Pr [k ← G(1n), (x1, x2) ← A(k, 1n) s.t. x1 ≠ x2 but hk(x1) = hk(x2)] < negl(n),

जहां negl(·) कुछ नगण्य फ़ंक्शन को दर्शाता है, और n सुरक्षा पैरामीटर है।[5]


तर्क

कोलीजन रेजिस्टेंस कई कारणों से वांछनीय है।

  • कुछ डिजिटल हस्ताक्षर प्रणालियों में, एक पक्ष दस्तावेज़ के हैश पर सार्वजनिक कुंजी हस्ताक्षर प्रकाशित करके दस्तावेज़ को प्रमाणित करता है। यदि एक ही हैश के साथ दो दस्तावेज़ तैयार करना संभव है, तो एक हमलावर एक पक्ष से एक को प्रमाणित करवा सकता है, और फिर दावा कर सकता है कि पार्टी ने दूसरे को प्रमाणित कर दिया है।
  • कुछ वितरित सामग्री प्रणालियों में, पार्टियां यह सुनिश्चित करने के लिए फ़ाइलों के क्रिप्टोग्राफ़िक हैश की तुलना करती हैं कि उनका संस्करण समान है। एक हमलावर जो एक ही हैश के साथ दो फ़ाइलें तैयार कर सकता है, उपयोगकर्ताओं को यह विश्वास दिला सकता है कि उनके पास फ़ाइल का एक ही संस्करण है जबकि वास्तव में ऐसा नहीं था।

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001
  2. ↑ 2.0 2.1 Pass, R. "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme". Course on Cryptography, Cornell University, 2009
  3. ↑ Xiaoyun Wang; Hongbo Yu. "How to Break MD5 and Other Hash Functions" (PDF). Archived from the original (PDF) on 2009-05-21. Retrieved 2009-12-21.
  4. ↑ Xiaoyun Wang; Yiqun Lisa Yin; Hongobo Yu. पूर्ण SHA-1 में टकराव ढूँढना (PDF). CRYPTO 2005. doi:10.1007/11535218_2.
  5. ↑ Dodis, Yevgeniy. "Lecture 12 of Introduction to Cryptography" (PDF). Retrieved 3 January 2016., def 1.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=संघट्टन_प्रतिरोध&oldid=239937’