फ्रीक्वेंसी क्रिप्टैनालिसिस का उपयोग करके एक वीगन साइफर को हैक करना

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



Habré पर कई बार लेख चार्ल्स वेदरली की पुस्तक "प्रोग्रामर्स के लिए दृष्टिकोण" पर टिमटिमाया। यहां सबसे दिलचस्प में से एक का एक टुकड़ा है, मेरी राय में, रेखाचित्र - "कंपनी का रहस्य", जिसका मुख्य कार्य विगेनियर सिफर को दरार करना है । बहुत पहले नहीं, मुझे इस स्केच का एहसास हुआ, और अपने लेख में मैं इस बारे में बात करूंगा कि मैंने यह कैसे किया और आखिर में क्या हुआ।

कार्य

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







फिर एक कीवर्ड का चयन किया जाता है और स्रोत पाठ के तहत बार-बार लिखा जाता है। अंत में, प्रत्येक जोड़ी (स्रोत पाठ का प्रतीक, इसके नीचे कीवर्ड का प्रतीक) इस जोड़ी के अनुरूप प्रतीक के साथ तालिका का उपयोग करके एन्क्रिप्ट किया गया है। उदाहरण के लिए, "रेस स्टार" वाक्यांश को "सामान" कुंजी और इस तरह की उपरोक्त तालिका का उपयोग करके एन्क्रिप्ट किया जाएगा:

समाधान का विचार

रिवर्स विगेनयर वर्ग पर विचार करें, जो कि एक टेबल है जो एक जोड़ी (सिफरटेक्च सिंबल; कीवर्ड सिंबल) के स्रोत टेक्स्ट सिंबल पर मैप करता है।







हम दो वर्णों के बीच की दूरी को वर्णमाला में उनकी स्थिति के अंतर को कॉल करने के लिए सहमत हैं: उदाहरण के लिए, 'a' और 'b' के बीच की दूरी 2. है। फिर आप देख सकते हैं कि यदि कीवर्ड के ith और jth वर्णों के बीच की दूरी d है, तो दूरी स्रोत पाठ के संगत वर्णों के बीच -d है। इसलिए, यदि हम एक कीवर्ड खोजने का प्रबंधन करते हैं, तो हम विगेनियर सिफर को एक साधारण प्रतिस्थापन सिफर में कम कर सकते हैं: स्रोत पाठ के प्रत्येक अक्षर को दूसरे से बदल दिया जाएगा, और अक्षरों का पत्राचार एक-से-एक होगा। ऐसे सिफर को हैक करना मुश्किल नहीं है।



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



इस प्रकार, कार्यक्रम में तीन भाग शामिल होंगे:

1) कीवर्ड की लंबाई का निर्धारण

2) कीवर्ड सर्च

3) पाठ की वर्णमाला और डिकोडिंग के क्रमांकन के लिए खोजें

कीवर्ड लंबाई

कीवर्ड की लंबाई मैच इंडेक्स विधि का उपयोग करने के लिए आसान है। विलियम फ्राइडमैन द्वारा इस विधि को 1922 में मूल विगेनियर सिफर को क्रैक करने के लिए प्रस्तावित किया गया था, लेकिन यह हमारे मामले में काम करेगा। विधि इस तथ्य पर आधारित है कि कुछ काफी लंबे पाठ (संयोग सूचकांक) में दो यादृच्छिक अक्षरों के संयोग की संभावना एक निरंतर मूल्य है। इस प्रकार, यदि हम पाठ को वर्णों के L समूहों में विभाजित करते हैं, जिनमें से प्रत्येक को एक साधारण प्रतिस्थापन कोड (याद रखें, इसका अर्थ है कि L कीवर्ड की लंबाई है), तो प्रत्येक समूह के लिए मैच सूचक इस मान के सैद्धांतिक मूल्य के काफी करीब होंगे; अन्य सभी विभाजनों के लिए, मैच सूचक बहुत कम होंगे। संयोग सूचकांक की गणना सूत्र का उपयोग करके की जा सकती है





(पाठ में वर्णमाला के i-अक्षरों की संख्या f है, और n इसकी लंबाई है)



नीचे, उदाहरण के लिए, "प्रोजेक्ट" कुंजी (6 वर्ण) का उपयोग करके एन्क्रिप्ट किए गए पाठ के लिए मैच सूचकांकों हैं।







इस प्रकार, एक कीवर्ड की लंबाई निर्धारित करने के लिए, एल = 1, 2, ... समूहों में पाठ को तोड़ने के लिए संयोग सूचकांकों की गणना करना आवश्यक है, और फिर प्राप्त मानों में से, दूसरों से अधिकांश के लिए सबसे पहले श्रेष्ठ, चुनें। लेकिन ... थोड़ी चाल है। क्या होगा यदि पाठ एक कुंजी का उपयोग करके एन्क्रिप्ट किया गया है जिसे कई समान भागों में विभाजित किया जा सकता है? नीचे पहले उदाहरण के समान पाठ के लिए संयोग सूचकांकों की एक तालिका है, लेकिन "स्पेस" कुंजी (समान 6 वर्ण) का उपयोग करके एन्क्रिप्ट किया गया है। इस मामले में महत्वपूर्ण लंबाई कैसे निर्धारित करें?







मैंने विभिन्न विधियों के साथ खेला और पाया कि इस तरह के आवश्यक सूचकांक को चुनना सबसे आसान है: आपको पहला सूचकांक लेने की आवश्यकता है, जिसके लिए यह सही है: 1.06 * आईपी> आईसीआई, i = 1, 2, ... 1.06 से गुणा करना एक वास्तविक आईपी बनाने के लिए पर्याप्त है। “कई” आईपी से अधिक (हमारे उदाहरण में, ये एल = 12 और 18 पर सूचक हैं), लेकिन यह वास्तविक लोगों को पार करने के लिए झूठे सूचक (एल = 3, 9 और 15 पर) के लिए पर्याप्त नहीं है।



बेशक, मेरी विधि 100% परिणाम नहीं देती है। इसके अलावा, यदि पाठ समान भागों (उदाहरण के लिए, "टैटार") से युक्त किसी शब्द का उपयोग करके एन्क्रिप्ट किया गया है, तो किसी भी मामले में कीवर्ड की लंबाई गलत तरीके से निर्धारित की जाएगी (जब तक, निश्चित रूप से, हम एक सार्थक कीवर्ड खोजना चाहते हैं): एन्क्रिप्शन के बीच कोई अंतर नहीं है कुंजी टैटार और टार है। इसलिए, कार्यक्रम के दौरान उपयोगकर्ता को कुंजी की लंबाई बदलने की क्षमता देना महत्वपूर्ण है: उदाहरण के लिए, 6 फिट नहीं था, जिसका मतलब है कि यह 3 या 12 की कोशिश करने के लायक है।

सौभाग्य से, एक किताब से एन्क्रिप्टेड नोट के लिए, सब कुछ बहुत सरल है। संयोग सूचकांक की तालिका को देखने के बाद, हम विश्वास के साथ कह सकते हैं कि कीवर्ड की लंबाई 7 वर्ण है।

कीवर्ड

अब जब कुंजी की लंबाई मिल गई है, तो आप कीवर्ड की खोज स्वयं करना शुरू कर सकते हैं। सबसे पहले, हमें उन समूहों के बीच विभिन्न पारियों की संभावनाओं को निर्धारित करना होगा जिसमें हमने सिफर को विभाजित किया था (मुझे याद है कि प्रत्येक समूह वर्णमाला के कुछ क्रमचय का उपयोग करके एन्क्रिप्ट किया गया है, जबकि क्रमपरिवर्तन वर्णमाला के कई पदों द्वारा प्रत्येक अक्षर को शिफ्ट करने से भिन्न होता है)। पारियों की संभावनाओं को खोजने के लिए, मैंने Etudes के अनुवादकों द्वारा प्रस्तावित विचार का उपयोग किया। यदि हम सभी गणितीय गणनाओं को छोड़ देते हैं, तो यह इस प्रकार है। प्रत्येक समूह के लिए, हम वर्णों की संख्या x (x = 'a', 'b', ..., 'i') पर विचार करते हैं और रूसी भाषा में अक्षरों की आवृत्ति के बारे में जानकारी के आधार पर, हम इस संभावना का अनुमान लगाते हैं कि सिफर का वर्ण y वर्ण y से मेल खाता है स्रोत पाठ का (y = 'a', 'b', ..., 'i')। विभिन्न समूहों के लिए प्राप्त संभाव्यता तालिकाओं की तुलना करते हुए, हम इन समूहों के बीच पारियों r (r = 1, 2, ..., 32) की संभावनाओं की गणना कर सकते हैं। नतीजतन, हमें एक तालिका मिलती है जो दिखाती है कि किसी भी दो समूहों और किसी भी बदलाव के लिए समूहों i और j के बीच बदलाव r की संभावना क्या है



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



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



कुंजी खोजने का दूसरा तरीका सरल और निर्बाध है, लेकिन प्रभावी है। हम एक शब्दकोश लेते हैं और प्रत्येक उपयुक्त शब्द की विशेषताओं की गणना करते हैं (कार्यक्रम की गति बढ़ाने के लिए, मैंने शब्दों को उनकी लंबाई से विभाजित किया है)। हम एक महत्वपूर्ण शब्द के रूप में सर्वश्रेष्ठ शब्द लेते हैं। यह विधि संक्षिप्त (400-500 अक्षर) पाठों के लिए भी सही ढंग से काम करती है, लेकिन इसमें एक स्पष्ट दोष है: यदि कीवर्ड शब्दकोश में नहीं है, तो प्रोग्राम किसी भी परिस्थिति में सही ढंग से काम नहीं करेगा।



हालांकि, अगर शब्दकोश में एक कुंजी है, तो दूसरी विधि पहले की तुलना में बहुत अधिक प्रभावी है। इसलिए, मैंने इसे अपने कार्यक्रम में इस्तेमाल किया। इस पद्धति ने तुरंत सही (जैसा कि बाद में पता चला) कीवर्ड - "मूली" दिया।

वर्णमाला क्रमपरिवर्तन

एक खोजशब्द होने पर, हम पाठ को संशोधित कर सकते हैं ताकि यह एक साधारण प्रतिस्थापन सिफर के साथ एन्क्रिप्ट किया गया हो। ऐसा करने के लिए, वर्णमाला क्रम में बाईं ओर के कीवर्ड के पहले और Lth अक्षरों के बीच की दूरी से Lth समूह (L = 2, 3, ..., की लंबाई) के प्रतीकों को cyclically शिफ्ट करना आवश्यक है। इन परिवर्तनों को करने के बाद, यह हमारे लिए यह जानने के लिए बना रहता है कि स्रोत पाठ के कौन से अक्षर सिफरटेक्ट के वर्णों के अनुरूप हैं।

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





(b_ij "डिक्रिप्टेड" टेक्स्ट में बिगग्रामों की संख्या है, और p_ij रूसी में एक विशेष आश्रम बैठक की संभावना है)



फिर हम पत्राचार तालिका में यादृच्छिक परिवर्तन करेंगे और प्रत्येक चरण में एक नई विशेषता की गणना करेंगे। यदि नई विशेषता पुराने वाले की तुलना में बेहतर (अधिक) हो जाती है, तो हम परिवर्तनों को याद करते हैं, अन्यथा हम उन्हें वापस रोल करते हैं। नतीजतन, हमें पत्रों का सही पत्राचार तालिका मिलती है, और हम मूल पाठ को पुनर्स्थापित कर सकते हैं!



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







क्रमपरिवर्तन तालिका (बाएं) के सफल परिवर्तन की संख्या और तालिका के परिवर्तन संख्या (दाएं) पर पाठ की विशेषताओं पर पुनरावृत्ति संख्या के निर्भरता के ग्राफ को देखना भी दिलचस्प है।



हम देखते हैं कि पाठ का लक्षण वर्णन क्रमबद्धता तालिका के प्रत्येक परिवर्तन के साथ कम या अधिक रैखिक रूप से बदलता है, और तालिका में एक नया सफल परिवर्तन खोजने के लिए आवश्यक प्रयासों की संख्या तेजी से बढ़ती है। पुनरावृत्तियों की संख्या पर पाठ की विशेषताओं की निर्भरता लॉगरिदमिक के समान है। दरअसल, निम्न रेखांकन दिखाते हैं कि यदि x पुनरावृत्तियों की संख्या है, y विशेषता है और t सफल तालिका परिवर्तनों की संख्या है, तो x changese ^ t, y∼t, इसलिए, y∼ln (x)। लघुगणक बल्कि धीरे-धीरे बढ़ता है, लेकिन इसकी वृद्धि केवल स्पर्शोन्मुखता तक सीमित नहीं है, इसलिए एक सही पत्राचार तालिका खोजने के बजाय एक बड़ी मात्रा में लेती है, लेकिन काम की अनंत राशि नहीं। हालांकि, परीक्षण बताते हैं कि 10-12 हजार पुनरावृत्तियां हमेशा पर्याप्त होती हैं।

निष्कर्ष

वर्णित एल्गोरिदम को लागू करने और एक ग्राफिकल इंटरफ़ेस को जोड़ने के बाद, हमें ऐसा कार्यक्रम मिला:











कार्यक्रम सफलतापूर्वक 400-500 वर्णों की लंबाई के साथ ग्रंथों को कम कर देता है और अधिक, ऑपरेटिंग समय 10 सेकंड से अधिक नहीं होता है। मुझे लगता है कि यह एक अच्छा परिणाम है।



UPD यहाँ मेरे कार्यक्रम की एक कड़ी है। मैंने इसे विजुअल स्टूडियो 2012 में किया था और विंडोज फॉर्म का इस्तेमाल किया था, इसलिए शुरू करने से पहले, सुनिश्चित करें कि आपके पास उपयुक्त पुनर्वितरण पैकेज और .net फ्रेमवर्क 4 स्थापित है। आप प्रोग्राम में पाठ को एन्क्रिप्ट कर सकते हैं (इसके लिए, फ़ॉर्म और कीवर्ड के शीर्ष पर पाठ दर्ज करें; यदि कीवर्ड दर्ज नहीं किया जाएगा, इसे बेतरतीब ढंग से चुना जाएगा) या सिफर को क्रैक करने के लिए (इसके लिए सिफरटेक्स्ट दर्ज करें और "हैक" दबाएं; यदि यह कीवर्ड या कीवर्ड की लंबाई को इंगित करता है, तो यह डेटा डिक्रिप्ट करने के लिए उपयोग किया जाएगा, अन्यथा) कार्यक्रम उन्हें खुद उठाता है)।