मैंने बिटकॉइन को कैसे क्रैक करने की कोशिश की

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

विचार

यह माना जाता है कि विपरीत दिशा में कुछ कार्य काम नहीं करते हैं। लेख में विकिपीडिया ऐसी अवधारणा का उपयोग "कम्प्यूटेशनल असंभव" के रूप में करता है। कैमरों में से एक में, उन्होंने एक उदाहरण के रूप में फ़ंक्शन का हवाला दिया

एक्स = ए मोड बी

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

मान लीजिए कि हमारे पास बिट चर हैं a, b, c। आपको यह भी बता दें कि ए और बी लेने के परिणामस्वरूप हमें 0 मिला, और बिट "सी" सूत्र में भाग नहीं लिया। आइए इस सूत्र को विपरीत दिशा में "खोने" का प्रयास करें। हम जानते हैं कि ऑपरेशन और हमें अंत में शून्य देता है, अगर इसके इनपुट पर पहुंचने वाले ऑपरेंड में से कम से कम एक शून्य है। इस प्रकार, एबीसी के संभावित मूल्य, जैसा कि वे ऑपरेंड "ए" में दिखाई देते हैं, को एक रेगीज़ 0 ** की सूची के रूप में दर्शाया जा सकता है। जहाँ तारांकन का अर्थ है 0 या 1. चर के संभावित मान, जैसा कि वे ऑपरेंड "b" में दिखाई देते हैं, को regexp * 0 * की सूची से दर्शाया जा सकता है। हमें एक सूची की आवश्यकता है क्योंकि बड़े अभिव्यक्तियों में एक regexp हमारे लिए पर्याप्त नहीं है। रेगेक्सपी के द्वारा, मैं पारंपरिक नियमित अभिव्यक्ति को नहीं, बल्कि इसके छंटे हुए संस्करण को समझता हूं, जिसमें तारांकन का मतलब संबंधित बिट के किसी भी मूल्य से है।

जब हम इनपुट्स पर आने वाली सूचियों के बारे में तार्किक "I" लेते हैं, तो हमें प्रत्येक आवक regexp को बाईं ओर आने वाले प्रत्येक के साथ दाएं इनपुट में संयोजित करने की आवश्यकता होती है। इस कार्य में, हमारे लिए यह आसान है - केवल एक regexp शामिल है, इसलिए हम उन्हें संयोजित करते हैं। "और" के लिए, यदि आपको आउटपुट पर 0 प्राप्त करने की आवश्यकता है, तो हम बस दाईं ओर बाईं सूची को पूरक करते हैं। योजना के अनुसार, मैंने चित्र में इसे एक ग्राफ के रूप में दिखाया:

स्पष्टीकरण। परिणाम f को नीचे से आउटपुट तक आपूर्ति की जाती है, और अंतिम दिशा में आने तक, नोड्स पर द्विभाजन करते हुए, तीर के विपरीत दिशा में उगता है। अंतिम चर परिणाम प्राप्त करने के लिए आवश्यक चर (इस चर की स्थिति से देखा जाता है) के संभावित मूल्यों की एक सूची बनाता है। चर "a" के लिए यह 0 ** है, चर "b" के लिए यह * 0 * है। वास्तव में, ये सभी तारांकन हैं, लेकिन उनमें से केवल एक, चर की स्थिति में, आने वाली एफ द्वारा प्रतिस्थापित किया जाता है। इसके अलावा, यह सूची अन्य समान सूचियों के साथ नोड्स में संयोजन करते हुए, नीचे जाती है। मैंने "ग" चर को विशेष रूप से यह दिखाने के लिए जोड़ा कि जो चर अभिव्यक्ति में भाग नहीं लेते हैं वे हमें परेशान नहीं करते हैं, लेकिन उनके मूल रूप में नीचे जाते हैं। आउटपुट में, हमें एक सूची मिली, जिसमें दो regexps शामिल थे। प्रत्येक regexp संभावित मानों के एक सेट को परिभाषित करता है, जो यदि वांछित है, तो हम आसानी से इस regexp से उत्पन्न कर सकते हैं। यह उत्तर है।

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

अब एक ही बात है, लेकिन केवल f = 1 के लिए। हमें एक = 1 **, बी = * 1 * मिलता है। एसोसिएशन का नियम, अगर "और" के लिए हमें आउटपुट पर 1 प्राप्त करने की आवश्यकता है, तो यह अधिक कठिन है। हमें नए regexp की सूची बनाते समय, दाएं और बाएं भागों के साथ सुसंगत regexp को जोड़ना चाहिए। मुझे निम्नलिखित अंतिम नियम मिले:

Regexps को बिट द्वारा देखा जाता है। दाईं ओर और बाईं ओर बिट्स के मूल्यों के आधार पर, हम सबसे विशिष्ट मान का चयन करते हैं, या यदि हम एक-दूसरे के विरोधाभासी बिट्स का सामना करते हैं, तो regexp की इस जोड़ी को त्याग दें।

इस नियम के अनुसार इनपुट संसाधित करने के बाद, हम प्राप्त करते हैं:


मुझे लगता है कि विचार स्पष्ट है। "OR" और "NOT" के लिए आप समान नियम बना सकते हैं:

यहाँ यह भी दिखाया गया है कि "NOT" लॉग के लिए हम regex सूचियों के साथ काम नहीं कर रहे हैं, बल्कि f के साथ, इसे निष्क्रिय कर रहे हैं। "नहीं" के माध्यम से regexps की सूची अपरिवर्तित और व्युत्क्रम के बिना गुजरती हैं।

इस प्रकार, Sha256 के लिए हम एक ग्राफ बना सकते हैं, हमारे संदेश को बिट्स में डाइजेस्ट कर सकते हैं, इन बिट्स को आउटपुट में खिला सकते हैं और हम उलटे वेरिएबल्स के संभावित मानों की एक सूची वापस करेंगे।

अनुकूलन

एल्गोरिथ्म को यथासंभव अनुकूलित करने के लिए कोई लक्ष्य नहीं थे। यह स्पष्ट है कि पात्रों के माध्यम से बिट्स के साथ काम करना व्यर्थ है, और यदि आप इसे बिटवाइस ऑपरेशन के साथ एस और असेंबलर में स्थानांतरित करते हैं, तो आप एल्गोरिथ्म की गति बढ़ा सकते हैं। हालाँकि, अनुकूलन का एक और तरीका है - उन सूचियों के आकार को कम करना जो हम संचालित करते हैं। सूचियों के संयोजन के दौरान, डुप्लिकेट और गैर-विरोधाभासी regexps अक्सर उत्पन्न होते हैं जिन्हें मोड़ने की आवश्यकता होती है। इसके अलावा, कभी-कभी, दो रेगेक्स को एक नए में जोड़ा जा सकता है, जो आगे अनुकूलन के अधीन हो सकता है। उदाहरण के लिए, 000100 और 001100 को 00 * 100 में जोड़ा जा सकता है, इस तरह के संयोजन का नियम अपेक्षाकृत आसान है - केवल एक बिट परिवर्तन अनुमेय है, यह केवल महत्वपूर्ण है कि नव निर्मित regexp अपने अनावश्यक चर मानों का प्रतिनिधित्व नहीं करता है। इसलिए, * 0 को 0 * के साथ नहीं जोड़ा जा सकता है, इस प्रकार ** प्राप्त होता है, क्योंकि ** 11 का प्रतिनिधित्व करता है, जिसे न तो पहले और न ही दूसरे regexp की अनुमति है।
इसके अलावा, सूचियों के नोड्स में हम कैश करेंगे - हम उन्हें नीचे से आने वाले प्रत्येक एफ के लिए एक बार गिनते हैं।

प्रयोग

मैंने निम्नलिखित धारणाएँ बनाईं
- मूल संदेश 56 बाइट्स (बिटकॉइन के लिए) से कम है, हम यह मान सकते हैं कि ऐसा है, वास्तव में, इस सरलीकरण को मना करना मुश्किल नहीं है);
- हम सभी मूल संदेश को जानते हैं, पहले 8 बिट्स को छोड़कर।

बेशक, यह एक फव्वारा नहीं है, मैं समझता हूं कि 8 अज्ञात बिट्स प्रत्यक्ष संपूर्ण खोज द्वारा उन्हें चुनने के लिए पर्याप्त छोटे हैं, लेकिन विधि को सत्यापित करने के लिए प्रयोग का उद्देश्य ठीक था। मैं इस तरह से अक्षर T को खोजने में कामयाब रहा, वाक्यांश से sha-256 "आलसी कुत्ते पर त्वरित भूरे लोमड़ी कूदता है", और अक्षर T को छोड़कर इस वाक्यांश के सभी अक्षरों को जानना। कार्यक्रम को बड़े अज्ञात के लिए काम करना चाहिए, यह सिर्फ काम करेगा। अब और अधिक स्मृति की आवश्यकता होगी। इस कारण से, सभी पत्रों को अज्ञात मानना ​​असंभव है - पर्याप्त कंप्यूटिंग संसाधन नहीं होंगे, जिसका अर्थ है कि कोई व्यावहारिक अनुप्रयोग नहीं है। T T अक्षर की गणना 3Hz Phenom पर 82 सेकंड है। बेशक, सभी अज्ञात बिट्स (256 मान) की एक प्रत्यक्ष गणना एक सेकंड के अंश लेती है, इसलिए इस अर्थ में कार्यक्रम से कोई व्यावहारिक लाभ भी नहीं है।

यह मुझे लगता है कि अनुकूलन का एक संभावित तरीका है, जो सेट के लिए एक कॉम्पैक्ट अंकन के साथ आना है, लेकिन फिर भी विधि प्रत्यक्ष गणना से तेजी से काम नहीं करेगी।

एक परियोजना का लिंक जो अक्षर को पाता है: https://github.com/chabapok/sha256unroll