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

This article is about गणितीय क्रिप्टोग्राफी कार्य. For सुरक्षा को दरकिनार करने का विधि, see पिछले दरवाजे (कंप्यूटिंग).

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

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

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

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

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

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

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

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

परिभाषा

ट्रैपडोर कार्य एक तरफ़ा कार्य { f_k : D_k → R_k } (k ∈ K), का एक संग्रह है, जिसमें सभी K, D_k, R_k बाइनरी स्ट्रिंग्स {0, 1}* के उपसमुच्चय हैं, जो निम्नलिखित नियमो को पूरा करते हैं:

• वहाँ एक संभाव्य बहुपद समय (पीपीटी) नमूना एल्गोरिथ्म जेन सेंट उपस्थित है। Gen s.t. Gen(1ⁿ) = (k, t_k) के साथ k ∈ K ∩ {0, 1}ⁿ और t_k ∈ {0, 1} संतुष्ट करता है |t_k | < p (n), जिसमें पी कुछ बहुपद है। प्रत्येक t_k को k के अनुरूप ट्रैपडोर कहा जाता है। प्रत्येक ट्रैपडोर का कुशलतापूर्वक नमूना लिया जा सकता है।
• दिए गए इनपुट k में, एक पीपीटी एल्गोरिथ्म भी उपस्थित है जो x ∈ D_k को आउटपुट करता है अर्थात् प्रत्येक D_k कुशलता से नमूना लिया जा सकता है।
• किसी भी k ∈ K के लिए, एक पीपीटी एल्गोरिथ्म उपस्थित है जो f_k की सही गणना करता है
• किसी भी k ∈ K के लिए, एक पीपीटी एल्गोरिथम A st उपस्थित है। किसी भी x ∈ D_k, के लिए चलो y = A ( k, f_k(x), t_k ) और फिर हमारे पास f_k(y) = f_k(x) यानी ट्रैपडोर दिया गया है, इसे विपरीत करना आसान है।
• किसी भी k ∈ K, के लिए, ट्रैपडोर t_k के बिना किसी भी पीपीटी एल्गोरिथम के लिए, f_k को सही विधि से विपरीत करने की संभावना (अर्थात, दिया गया f_k(x) एक पूर्व-छवि x' खोजें, जैसे कि f_k(x' ) = f_k(x)) नगण्य है।

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

उदाहरण

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

आरएसए धारणा

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

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

यदि $n=pq$ का गुणनखंड ज्ञात है, तो $\phi (n)=(p-1)(q-1)$ की गणना की जा सकती है। इसके साथ $e$ के व्युत्क्रम $d$ की गणना की जा सकती है $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}}$ और विरोधी के लिए गोपनीय रखा। समस्या यह है कि दिए गए $a$ के अनुसार $z$ की गणना करना $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