ट्रैपडोर फंक्शन

This article is about the mathematical cryptography function. For the method of bypassing security, see Backdoor (computing).

ट्रैपडोर फ़ंक्शन का विचार। एक ट्रैपडोर फ़ंक्शन f इसके ट्रैपडोर टी के साथ एक एल्गोरिथम 'जेन' द्वारा उत्पन्न किया जा सकता है। f की कुशलतापूर्वक गणना की जा सकती है, अर्थात, संभाव्य बहुपद समय में। हालाँकि, f के व्युत्क्रम की गणना आम तौर पर कठिन होती है, जब तक कि ट्रैपडोर t नहीं दिया जाता है।

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

गणितीय शब्दों में, यदि f एक ट्रैपडोर फ़ंक्शन है, तो कुछ गुप्त सूचना t मौजूद है, जैसे कि f(x) और t दिया गया है, x की गणना करना आसान है। एक ताला और उसकी चाबी पर विचार करें। ताला तंत्र में झोंपड़ी को धकेल कर, कुंजी का उपयोग किए बिना पैडलॉक को खुले से बंद में बदलना तुच्छ है। पैडलॉक को आसानी से खोलने के लिए, हालांकि, उपयोग की जाने वाली कुंजी की आवश्यकता होती है। यहां की टी ट्रैपडोर है और पैडलॉक ट्रैपडोर फंक्शन है।

एक सरल गणितीय ट्रैपडोर का एक उदाहरण 6895601 है जो दो अभाज्य संख्याओं का गुणनफल है। वे संख्याएँ क्या हैं? एक विशिष्ट पशुबल का आक्रमण |ब्रूट-फोर्स समाधान उत्तर खोजने तक 6895601 को कई अभाज्य संख्याओं से विभाजित करने का प्रयास करना होगा। हालाँकि, अगर किसी को बताया जाए कि 1931 संख्याओं में से एक है, तो वह किसी भी कैलकुलेटर में 6895601 ÷ 1931 दर्ज करके उत्तर पा सकता है। यह उदाहरण एक मजबूत ट्रैपडोर फ़ंक्शन नहीं है - आधुनिक कंप्यूटर एक सेकंड के भीतर सभी संभावित उत्तरों का अनुमान लगा सकते हैं - लेकिन इस नमूना समस्या को पूर्णांक गुणनखंडन द्वारा सुधारा जा सकता है।

1970 के दशक के मध्य में व्हिटफ़ील्ड डिफी, मार्टिन हेलमैन और राल्फ मर्कल द्वारा असममित कुंजी एल्गोरिदम | असममित (या सार्वजनिक कुंजी) एन्क्रिप्शन तकनीकों के प्रकाशन के साथ ट्रैपडोर फ़ंक्शंस क्रिप्टोग्राफी में प्रमुखता से आए। वास्तव में, Diffie & Hellman (1976) शब्द गढ़ा। कई कार्य वर्गों का प्रस्ताव किया गया था, और जल्द ही यह स्पष्ट हो गया कि ट्रैपडोर कार्यों को शुरू में जितना सोचा गया था, उससे कहीं अधिक कठिन है। उदाहरण के लिए, एक प्रारंभिक सुझाव सबसेट योग समस्या के आधार पर योजनाओं का उपयोग करना था। यह अनुपयुक्त होने के बजाय जल्दी निकला।

As of 2004, सबसे प्रसिद्ध ट्रैपडोर फ़ंक्शन (परिवार) उम्मीदवार RSA (एल्गोरिदम) और राबिन क्रिप्टोसिस्टम ऑफ़ फ़ंक्शंस हैं। दोनों को घातांक मॉडुलो के रूप में एक समग्र संख्या के रूप में लिखा गया है, और दोनों प्रधान गुणनखंड की समस्या से संबंधित हैं।

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

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

परिभाषा

ट्रैपडोर फ़ंक्शन एक तरफ़ा फ़ंक्शन {f का एक संग्रह है_k : डी_k → आर_k } (k ∈ K), जिसमें सभी K, D_k, आर_k बाइनरी स्ट्रिंग्स {0, 1} के सबसेट हैं^*, निम्नलिखित शर्तों को पूरा करते हैं:

• एक संभाव्य बहुपद समय (पीपीटी) नमूना एल्गोरिदम जेन सेंट मौजूद है। जनरल (1ⁿ) = (के, टी_k) k ∈ K ∩ {0, 1} के साथ^एन और टी_k ∈ {0, 1}^* संतुष्ट | टी_k | <पी (एन), जिसमें पी कुछ बहुपद है। प्रत्येक टी_k k के अनुरूप ट्रैपडोर कहा जाता है। प्रत्येक ट्रैपडोर का कुशलतापूर्वक नमूना लिया जा सकता है।
• दिए गए इनपुट k में, एक PPT एल्गोरिथ्म भी मौजूद है जो x ∈ D को आउटपुट करता है_k. यानी प्रत्येक डी_k कुशलता से नमूना लिया जा सकता है।
• किसी भी k ∈ K के लिए, एक PPT एल्गोरिथ्म मौजूद है जो f की सही गणना करता है_k.
• किसी भी k ∈ K के लिए, एक PPT एल्गोरिथम A st मौजूद है। किसी भी एक्स ∈ डी के लिए_k, चलो y = ए (के, एफ_k(एक्स), टी_k ), और फिर हमारे पास f_k(वाई) = एफ_k(एक्स)। यानी ट्रैपडोर दिया गया है, इसे पलटना आसान है।
• किसी भी के ∈ के लिए, ट्रैपडोर टी के बिना_k, किसी भी पीपीटी एल्गोरिथ्म के लिए, एफ को सही ढंग से उलटने की संभावना_k (यानी, दिया गया एफ_k(एक्स), एक पूर्व-छवि एक्स 'इस तरह खोजें कि एफ_k(एक्स ') = च_k(x)) नगण्य है।

यदि उपरोक्त संग्रह में प्रत्येक कार्य एक तरफ़ा क्रमचय है, तो संग्रह को ट्रैपडोर क्रमचय भी कहा जाता है।

उदाहरण

निम्नलिखित दो उदाहरणों में, हम हमेशा मानते हैं कि एक बड़ी समग्र संख्या का गुणनखंड करना कठिन है (पूर्णांक गुणनखंड देखें)।

आरएसए धारणा

इस उदाहरण में, उलटा $d$ का $e$ मापांक $\phi (n)$ (यूलर का कुल कार्य $n$) ट्रैपडोर है:

$f(x)=x^{e}\mod n$

यदि का गुणनखंडन $n=pq$ जाना जाता है, तो $\phi (n)=(p-1)(q-1)$ गणना की जा सकती है। इसके साथ उलटा $d$ का $e$ गणना की जा सकती है $d=e^{-1}\mod {\phi (n)}$, और फिर दिया $y=f(x)$ हम ढूंढ सकते हैं $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$. इसकी कठोरता आरएसए धारणा से होती है।

राबिन का द्विघात अवशेष अनुमान

होने देना $n$ एक बड़ी समग्र संख्या हो जैसे कि $n=pq$, कहाँ $p$ और $q$ बड़े अभाज्य हैं जैसे कि $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$, और विरोधी के लिए गोपनीय रखा। समस्या गणना करना है $z$ दिया गया $a$ ऐसा है कि $a\equiv z^{2}{\pmod {n}}$. ट्रैपडोर का गुणनखंड है $n$. ट्रैपडोर के साथ, z का समाधान इस प्रकार दिया जा सकता है $cx+dy,cx-dy,-cx+dy,-cx-dy$, कहाँ $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$. अधिक विवरण के लिए चीनी शेष प्रमेय देखें। ध्यान दें कि प्राइम्स दिए गए हैं $p$ और $q$, हम ढूंढ सकते हैं $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ और $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$. यहाँ शर्तें $p\equiv 3{\pmod {4}}$ और $q\equiv 3{\pmod {4}}$ गारंटी है कि समाधान $x$ और $y$ अच्छी तरह से परिभाषित किया जा सकता है।

यह भी देखें

• वन-वे फंक्शन

संदर्भ

• Diffie, W.; Hellman, M. (1976), "New directions in cryptography" (PDF), IEEE Transactions on Information Theory, 22 (6): 644–654, CiteSeerX 10.1.1.37.9720, doi:10.1109/TIT.1976.1055638
• Pass, Rafael, A Course in Cryptography (PDF), retrieved 27 November 2015
• Goldwasser, Shafi, Lecture Notes on Cryptography (PDF), retrieved 25 November 2015
• Ostrovsky, Rafail, Foundations of Cryptography (PDF), retrieved 27 November 2015
• Dodis, Yevgeniy, Introduction to Cryptography Lecture Notes (Fall 2008), retrieved 17 December 2015
• Lindell, Yehuda, Foundations of Cryptography (PDF), retrieved 17 December 2015