फ़िंगरप्रिंट (कंप्यूटिंग): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 29: Line 29:


=== राबिन का एल्गोरिथ्म ===
=== राबिन का एल्गोरिथ्म ===
राबिन फ़िंगरप्रिंट या राबिन फ़िंगरप्रिंटिंग एल्गोरिथम<ref name="rabin">M. O. Rabin Fingerprinting by random polynomials. Center for Research in Computing Technology Harvard University Report TR-15-81 (1981)</ref> वर्ग का प्रोटोटाइप है। यह तेजी से और प्रयुक्त करने में आसान है, कंपाउंडिंग की अनुमति देता है, और टकराव की संभावना के गणितीय रूप से स्पष्ट विश्लेषण के साथ आता है। अर्थात्, दो तार r और s की समान w-बिट फ़िंगरप्रिंट उत्पन्न करने की संभावना अधिकतम(|''r''|,|''s''|)/2<sup>''w''-1</sup> से अधिक नहीं है, जहां |r| बिट्स में r की लंबाई को दर्शाता है। एल्गोरिथ्म को w-बिट आंतरिक कुंजी के पिछले विकल्प की आवश्यकता होती है, और यह गारंटी तब तक बनी रहती है जब तक कि कुंजी के ज्ञान के बिना स्ट्रिंग्स r और s को चुना जाता है।
राबिन फ़िंगरप्रिंट या राबिन फ़िंगरप्रिंटिंग एल्गोरिथम<ref name="rabin">M. O. Rabin Fingerprinting by random polynomials. Center for Research in Computing Technology Harvard University Report TR-15-81 (1981)</ref> वर्ग का प्रोटोटाइप है। यह तेजी से और प्रयुक्त करने में आसान है, कंपाउंडिंग की अनुमति देता है, और टकराव की संभावना के गणितीय रूप से स्पष्ट विश्लेषण के साथ आता है। अर्थात्, दो तार r और s की समान w-बिट फ़िंगरप्रिंट उत्पन्न करने की संभावना अधिकतम(|''r''|,|''s''|)/2<sup>''w''-1</sup> से अधिक नहीं है, जहां |r| बिट्स में r की लंबाई को दर्शाता है। एल्गोरिथ्म को w-बिट आंतरिक कुंजी के पिछले विकल्प की आवश्यकता होती है, और यह गारंटी तब तक बनी रहती है जब तक कि कुंजी के ज्ञान के बिना स्ट्रिंग्स r और s को चुना जाता है।


दुर्भावनापूर्ण हमलों के विरुद्ध राबिन की विधि सुरक्षित नहीं है। एक विरोधी एजेंट आसानी से कुंजी की खोज कर सकता है और अपने फिंगरप्रिंट को बदले बिना फ़ाइलों को संशोधित करने के लिए इसका उपयोग कर सकता है।
दुर्भावनापूर्ण हमलों के विरुद्ध राबिन की विधि सुरक्षित नहीं है। एक विरोधी एजेंट आसानी से कुंजी की खोज कर सकता है और अपने फिंगरप्रिंट को बदले बिना फ़ाइलों को संशोधित करने के लिए इसका उपयोग कर सकता है।
Line 45: Line 45:
फ़िंगरप्रिंटिंग वर्तमान में सामग्री समानता का पता लगाने के लिए सबसे व्यापक रूप से प्रयुक्त दृष्टिकोण है। यह विधि कई सबस्ट्रिंग (एन-ग्राम) के एक सेट का चयन करके दस्तावेज़ों का प्रतिनिधि डाइजेस्ट बनाती है। सेट उंगलियों के निशान का प्रतिनिधित्व करते हैं और उनके तत्वों को सूक्ष्मदर्शी कहा जाता है।
फ़िंगरप्रिंटिंग वर्तमान में सामग्री समानता का पता लगाने के लिए सबसे व्यापक रूप से प्रयुक्त दृष्टिकोण है। यह विधि कई सबस्ट्रिंग (एन-ग्राम) के एक सेट का चयन करके दस्तावेज़ों का प्रतिनिधि डाइजेस्ट बनाती है। सेट उंगलियों के निशान का प्रतिनिधित्व करते हैं और उनके तत्वों को सूक्ष्मदर्शी कहा जाता है।


किसी संदिग्ध दस्तावेज़ की साहित्यिक चोरी के लिए उसके फ़िंगरप्रिंट की गणना करके और संदर्भ संग्रह के सभी दस्तावेज़ों के लिए फ़िंगरप्रिंट के पूर्व-गणना किए गए सूचकांक के साथ निकटता को क्वेरी करके जाँच की जाती है। अन्य दस्तावेज़ों के साथ मेल खाने वाले सूक्ष्म विवरण साझा पाठ खंडों को इंगित करते हैं और संभावित साहित्यिक चोरी का सुझाव देते हैं यदि वे चयनित समानता सीमा से अधिक हो जाते हैं। कम्प्यूटेशनल संसाधन और समय फ़िंगरप्रिंटिंग के कारकों को सीमित कर रहे हैं, यही कारण है कि यह विधि सामान्यतः गणना को गति देने और इंटरनेट जैसे बहुत बड़े संग्रह में चेक की अनुमति देने के लिए केवल सूक्ष्मताओं के सबसेट की तुलना करती है।{{excerpt|Content similarity detection|Fingerprinting}}
किसी संदिग्ध दस्तावेज़ की साहित्यिक चोरी के लिए उसके फ़िंगरप्रिंट की गणना करके और संदर्भ संग्रह के सभी दस्तावेज़ों के लिए फ़िंगरप्रिंट के पूर्व-गणना किए गए सूचकांक के साथ निकटता को क्वेरी करके जाँच की जाती है। अन्य दस्तावेज़ों के साथ मेल खाने वाले सूक्ष्म विवरण साझा पाठ खंडों को इंगित करते हैं और संभावित साहित्यिक चोरी का सुझाव देते हैं यदि वे चयनित समानता सीमा से अधिक हो जाते हैं। कम्प्यूटेशनल संसाधन और समय फ़िंगरप्रिंटिंग के कारकों को सीमित कर रहे हैं, यही कारण है कि यह विधि सामान्यतः गणना को गति देने और इंटरनेट जैसे बहुत बड़े संग्रह में चेक की अनुमति देने के लिए केवल सूक्ष्मताओं के सबसेट की तुलना करती है।{{excerpt|Content similarity detection|Fingerprinting}}


== यह भी देखें ==
== यह भी देखें ==

Revision as of 17:27, 30 June 2023

कंप्यूटर विज्ञान में, फ़िंगरप्रिंटिंग एल्गोरिद्म एक ऐसी प्रक्रिया है, जो इच्छानुसार से बड़े डेटा (कंप्यूटिंग) आइटम (जैसे कंप्यूटर फ़ाइल (कंप्यूटिंग)) को एक बहुत छोटे बिट (कंप्यूटिंग) स्ट्रिंग, इसके 'फ़िंगरप्रिंट में मैप (गणित) करती है। जो विशिष्ट रूप से सभी व्यावहारिक उद्देश्यों के लिए मूल डेटा की पहचान करता है[1] ठीक वैसे ही जैसे मानव उंगलियों के निशान व्यावहारिक उद्देश्यों के लिए विशिष्ट रूप से लोगों की पहचान करते हैं। इस फ़िंगरप्रिंट का उपयोग डेटा डुप्लिकेशन उद्देश्यों के लिए किया जा सकता है। इसे फ़ाइल फ़िंगरप्रिंटिंग, डेटा फ़िंगरप्रिंटिंग या संरचित डेटा फ़िंगरप्रिंटिंग के रूप में भी जाना जाता है।

फ़िंगरप्रिंट का उपयोग सामान्यतः भारी डेटा की तुलना और प्रसारण से बचने के लिए किया जाता है। उदाहरण के लिए, एक वेब ब्राउज़र या प्रॉक्सी सर्वर कुशलतापूर्वक जांच कर सकता है कि रिमोट फ़ाइल को संशोधित किया गया है या नहीं, केवल अपनी अंगुली की छाप प्राप्त करके और इसे पहले प्राप्त की गई प्रति के साथ तुलना करते है।[2][3][4][5][6]

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

ऑडियो फिंगरप्रिंटिंग और वीडियो फिंगरप्रिंटिंग के लिए विशेष एल्गोरिदम उपस्थित हैं।

काम पर एक हैश कार्य

गुण

आभासी विशिष्टता

अपने इच्छित उद्देश्यों को पूरा करने के लिए एक फ़िंगरप्रिंटिंग एल्गोरिदम को आभासी निश्चितता के साथ फ़ाइल की पहचान को कैप्चर करने में सक्षम होना चाहिए। दूसरे शब्दों में, हैश टकराव की संभावना - एक ही फिंगरप्रिंट देने वाली दो फाइलें - नगण्य होनी चाहिए, घातक त्रुटियों के अन्य अपरिहार्य कारणों की संभावना की तुलना में (जैसे युद्ध या उल्कापिंड द्वारा प्रणाली को नष्ट किया जा रहा है): कहते हैं, 10−20 या उससे कम होता है।

यह आवश्यकता कुछ सीमा तक अंततः, फ़ंक्शन के समान है, किंतु अधिक कठोर है। आकस्मिक डेटा दूषण या संचरण त्रुटियों का पता लगाने के लिए, यह पर्याप्त है कि मूल फ़ाइल और किसी भी दूषित संस्करण के चेकसम निश्चित रूप से भिन्न होंगे, त्रुटियों के लिए कुछ सांख्यिकीय मॉडल दिए गए हैं। विशिष्ट स्थितियों में, यह लक्ष्य आसानी से 16- या 32-बिट चेकसम के साथ प्राप्त किया जाता है। इसके विपरीत, फ़ाइल फ़िंगरप्रिंट को कम से कम 64-बिट कंप्यूटिंग | 64-बिट लंबा होना चाहिए ताकि बड़ी फ़ाइल सिस्टम में आभासी विशिष्टता की गारंटी दी जा सके (जन्मदिन का दौरा देखें)।

उपरोक्त आवश्यकता को सिद्ध करते समय, किसी को यह ध्यान रखना चाहिए कि फ़ाइलें अत्यधिक गैर-यादृच्छिक प्रक्रियाओं द्वारा उत्पन्न होती हैं जो फ़ाइलों के बीच जटिल निर्भरताएँ उत्पन्न करती हैं। उदाहरण के लिए, एक विशिष्ट व्यावसायिक नेटवर्क में सामान्यतः दस्तावेजों के कई जोड़े या समूह मिलते हैं जो केवल सामान्य संपादन या अन्य सामान्य संशोधनों से भिन्न होते हैं। एक अच्छे फ़िंगरप्रिंटिंग एल्गोरिदम को यह सुनिश्चित करना चाहिए कि ऐसी "प्राकृतिक" प्रक्रियाएं निश्चितता के वांछित स्तर के साथ, अलग-अलग फ़िंगरप्रिंट उत्पन्न करती हैं।

कंपाउंडिंग

कंप्यूटर फ़ाइलों को अधिकांशतः विभिन्न विधि से संयोजित किया जाता है, जैसे संयोजन (संग्रह फ़ाइल में) या प्रतीकात्मक समावेशन (सी प्रीप्रोसेसर के साथ) #include निर्देश) कुछ फ़िंगरप्रिंटिंग एल्गोरिदम एक समग्र फ़ाइल के फ़िंगरप्रिंट को उसके घटक भागों के फ़िंगरप्रिंट से गणना करने की अनुमति देते हैं। यह कंपाउंडिंग गुण कुछ अनुप्रयोगों में उपयोगी हो सकता है, जैसे कि यह पता लगाना कि किसी प्रोग्राम को कब पुन: संकलित करने की आवश्यकता है।

एल्गोरिदम

राबिन का एल्गोरिथ्म

राबिन फ़िंगरप्रिंट या राबिन फ़िंगरप्रिंटिंग एल्गोरिथम[7] वर्ग का प्रोटोटाइप है। यह तेजी से और प्रयुक्त करने में आसान है, कंपाउंडिंग की अनुमति देता है, और टकराव की संभावना के गणितीय रूप से स्पष्ट विश्लेषण के साथ आता है। अर्थात्, दो तार r और s की समान w-बिट फ़िंगरप्रिंट उत्पन्न करने की संभावना अधिकतम(|r|,|s|)/2w-1 से अधिक नहीं है, जहां |r| बिट्स में r की लंबाई को दर्शाता है। एल्गोरिथ्म को w-बिट आंतरिक कुंजी के पिछले विकल्प की आवश्यकता होती है, और यह गारंटी तब तक बनी रहती है जब तक कि कुंजी के ज्ञान के बिना स्ट्रिंग्स r और s को चुना जाता है।

दुर्भावनापूर्ण हमलों के विरुद्ध राबिन की विधि सुरक्षित नहीं है। एक विरोधी एजेंट आसानी से कुंजी की खोज कर सकता है और अपने फिंगरप्रिंट को बदले बिना फ़ाइलों को संशोधित करने के लिए इसका उपयोग कर सकता है।

क्रिप्टोग्राफ़िक हैश फ़ंक्शंस

मेनस्ट्रीम क्रिप्टोग्राफी ग्रेड हैश फ़ंक्शंस सामान्यतः उच्च-गुणवत्ता वाले फ़िंगरप्रिंट फ़ंक्शंस के रूप में काम कर सकते हैं, क्रिप्टएनालिसिस से गहन जांच के अधीन हैं, और इसका लाभ यह है कि उन्हें दुर्भावनापूर्ण हमलों के विरुद्ध सुरक्षित माना जाता है।

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

आवेदन उदाहरण

एनआईएसटी एक सॉफ्टवेयर रेफरेंस लाइब्रेरी, अमेरिकन राष्ट्रीय सॉफ्टवेयर संदर्भ पुस्तकालय वितरित करता है, जो क्रिप्टोग्राफिक हैश फ़ंक्शंस का उपयोग फ़िंगरप्रिंट फ़ाइलों के लिए करता है और उन्हें सॉफ़्टवेयर उत्पादों में मैप करता है। नेशनल ड्रग इंटेलिजेंस सेंटर द्वारा अनुरक्षित हैशकीपर डेटाबेस, नियम प्रवर्तन अनुप्रयोगों (जैसे जब्त डिस्क ड्राइव की सामग्री का विश्लेषण) में उपयोग के लिए अच्छी और ज्ञात खराब कंप्यूटर फ़ाइलों के फिंगरप्रिंट का संचय है।

सामग्री समानता का पता लगाना

फ़िंगरप्रिंटिंग वर्तमान में सामग्री समानता का पता लगाने के लिए सबसे व्यापक रूप से प्रयुक्त दृष्टिकोण है। यह विधि कई सबस्ट्रिंग (एन-ग्राम) के एक सेट का चयन करके दस्तावेज़ों का प्रतिनिधि डाइजेस्ट बनाती है। सेट उंगलियों के निशान का प्रतिनिधित्व करते हैं और उनके तत्वों को सूक्ष्मदर्शी कहा जाता है।

किसी संदिग्ध दस्तावेज़ की साहित्यिक चोरी के लिए उसके फ़िंगरप्रिंट की गणना करके और संदर्भ संग्रह के सभी दस्तावेज़ों के लिए फ़िंगरप्रिंट के पूर्व-गणना किए गए सूचकांक के साथ निकटता को क्वेरी करके जाँच की जाती है। अन्य दस्तावेज़ों के साथ मेल खाने वाले सूक्ष्म विवरण साझा पाठ खंडों को इंगित करते हैं और संभावित साहित्यिक चोरी का सुझाव देते हैं यदि वे चयनित समानता सीमा से अधिक हो जाते हैं। कम्प्यूटेशनल संसाधन और समय फ़िंगरप्रिंटिंग के कारकों को सीमित कर रहे हैं, यही कारण है कि यह विधि सामान्यतः गणना को गति देने और इंटरनेट जैसे बहुत बड़े संग्रह में चेक की अनुमति देने के लिए केवल सूक्ष्मताओं के सबसेट की तुलना करती है।

Page 'Content similarity detection' not found

यह भी देखें

संदर्भ

  1. A. Z. Broder. Some applications of Rabin's fingerprinting method. In Sequences II: Methods in Communications, Security, and Computer Science, pages 143--152. Springer-Verlag, 1993
  2. Detecting duplicate and near-duplicate files. US Patent 6658423 Issued on December 2, 2003
  3. A. Z. Broder (1997). "On the Resemblance and Containment of Documents". Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171). pp. 21–27. CiteSeerX 10.1.1.24.779. doi:10.1109/SEQUEN.1997.666900. ISBN 978-0-8186-8132-5. S2CID 11748509. {{cite book}}: |journal= ignored (help)
  4. Brin, S. and Davis, J. and Garcia-Molina, H. (1995) Copy Detection Mechanisms for Digital Documents. In: ACM International Conference on Management of Data (SIGMOD 1995), May 22–25, 1995, San Jose, California, from stanford.edu. Archived 18/08/2016. Retrieved 11/01/2019.
  5. L. Fan, P. Cao, J. Almeida and A. Broder, Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol, IEEE/ACM Transactions on Networking, vol. 8, No. 3 (2000)
  6. U. Manber, Finding Similar Files in a Large File System. Proceedings of the USENIX Winter Technical Conf. (1994)
  7. M. O. Rabin Fingerprinting by random polynomials. Center for Research in Computing Technology Harvard University Report TR-15-81 (1981)