हिल सिफर

हिल की सिफर मशीन, पेटेंट के चित्र 4 से

शास्त्रीय क्रिप्टोग्राफी में, हिल सिफर रैखिक बीजगणित पर आधारित एक पॉलीग्राफिक प्रतिस्थापन है। 1929 में लेस्टर एस. हिल द्वारा आविष्कार किया गया, यह पहला पॉलीग्राफिक सिफर था जिसमें एक साथ तीन से अधिक प्रतीकों पर काम करना व्यावहारिक (हालांकि मुश्किल से) था।

निम्नलिखित चर्चा मैट्रिक्स (गणित) का प्रारंभिक ज्ञान मानती है।

एन्क्रिप्शन

प्रत्येक अक्षर को एक संख्या मॉड्यूलर अंकगणित 26 द्वारा दर्शाया जाता है। हालांकि यह सिफर की एक अनिवार्य विशेषता नहीं है, इस सरल योजना का अक्सर उपयोग किया जाता है:

Letter	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Number	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

एक संदेश को एन्क्रिप्ट करने के लिए, एन अक्षरों के प्रत्येक ब्लॉक (एन-घटक सदिश स्थल के रूप में माना जाता है) को मॉड्यूलर अंकगणित 26 के मुकाबले एक उलटा एन × एन मैट्रिक्स (गणित) से गुणा किया जाता है। संदेश को डिक्रिप्ट करने के लिए, प्रत्येक ब्लॉक को व्युत्क्रम से गुणा किया जाता है एन्क्रिप्शन के लिए प्रयुक्त मैट्रिक्स का।

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

संदेश 'ACT' और नीचे दी गई कुंजी (या GYB) पर विचार करें{{silver (color)|/}एन.के/अक्षरों में यूआरपी):

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}$

चूँकि 'ए' 0 है, 'सी' 2 है और 'टी' 19 है, संदेश वेक्टर है:

${\begin{pmatrix}0\\2\\19\end{pmatrix}}$

इस प्रकार एन्क्रिप्टेड वेक्टर इस प्रकार दिया गया है:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}0\\2\\19\end{pmatrix}}={\begin{pmatrix}67\\222\\319\end{pmatrix}}\equiv {\begin{pmatrix}15\\14\\7\end{pmatrix}}{\pmod {26}}$

जो 'पीओएच' के सिफरटेक्स्ट से मेल खाता है। अब, मान लीजिए कि हमारा संदेश इसके बजाय 'CAT' है, या:

${\begin{pmatrix}2\\0\\19\end{pmatrix}}$

इस बार, एन्क्रिप्टेड वेक्टर इस प्रकार दिया गया है:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}={\begin{pmatrix}31\\216\\325\end{pmatrix}}\equiv {\begin{pmatrix}5\\8\\13\end{pmatrix}}{\pmod {26}}$

जो 'FIN' के सिफरटेक्स्ट से मेल खाता है। हर अक्षर बदल गया है. हिल सिफर ने क्लाउड एलवुड शैनन के भ्रम और प्रसार को हासिल कर लिया है, और एक एन-आयामी हिल सिफर एक ही बार में एन प्रतीकों में पूरी तरह से फैल सकता है।

डिक्रिप्शन

डिक्रिप्ट करने के लिए, हम सिफरटेक्स्ट को वापस एक वेक्टर में बदल देते हैं, फिर कुंजी मैट्रिक्स के मैट्रिक्स व्युत्क्रम से गुणा करते हैं (आईएफके)/ रहना/वीएमआई अक्षरों में)। हम पाते हैं कि, मॉड्यूलर अंकगणित 26, पिछले उदाहरण में प्रयुक्त मैट्रिक्स का व्युत्क्रम है:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}^{-1}{\pmod {26}}\equiv {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}$

'पीओएच' का पिछला उदाहरण सिफरटेक्स्ट लेते हुए, हमें मिलता है:

${\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\begin{pmatrix}15\\14\\7\end{pmatrix}}={\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix}0\\2\\19\end{pmatrix}}{\pmod {26}}$

जो हमें उम्मीद के मुताबिक 'ACT' पर वापस ले जाता है।

उलटा मैट्रिक्स को चुनने में दो जटिलताएँ मौजूद हैं:

1. सभी आव्यूहों में व्युत्क्रमणीय आव्यूह नहीं होता। मैट्रिक्स का व्युत्क्रम तभी होगा जब इसका सारणिक शून्य न हो।
2. एन्क्रिप्टिंग मैट्रिक्स के निर्धारक में मॉड्यूलर आधार के साथ कोई सामान्य कारक नहीं होना चाहिए।

इस प्रकार, यदि हम ऊपर बताए अनुसार मॉड्यूल 26 पर काम करते हैं, तो सारणिक गैर-शून्य होना चाहिए, और 2 या 13 से विभाज्य नहीं होना चाहिए। यदि सारणिक 0 है, या मॉड्यूलर आधार के साथ सामान्य कारक हैं, तो मैट्रिक्स का उपयोग हिल में नहीं किया जा सकता है सिफर, और दूसरा मैट्रिक्स चुना जाना चाहिए (अन्यथा इसे डिक्रिप्ट करना संभव नहीं होगा)। सौभाग्य से, हिल सिफर में उपयोग की जाने वाली शर्तों को पूरा करने वाले मैट्रिक्स काफी सामान्य हैं।

हमारे उदाहरण कुंजी मैट्रिक्स के लिए:

${\begin{vmatrix}6&24&1\\13&16&10\\20&17&15\end{vmatrix}}=6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)=441\equiv 25{\pmod {26}}$

तो, मॉड्यूल 26, सारणिक 25 है। चूँकि $25=5^{2}$ और $26=2\times 13$, 25 में 26 के साथ कोई सामान्य गुणनखंड नहीं है, और इस मैट्रिक्स का उपयोग हिल सिफर के लिए किया जा सकता है।

मापांक के साथ निर्धारक के सामान्य कारक होने के जोखिम को मापांक को अभाज्य संख्या बनाकर समाप्त किया जा सकता है। नतीजतन, हिल सिफर का एक उपयोगी संस्करण मापांक को 29 तक बढ़ाने के लिए 3 अतिरिक्त प्रतीक (जैसे एक स्थान, एक अवधि और एक प्रश्न चिह्न) जोड़ता है।

उदाहरण

होने देना

$K={\begin{pmatrix}3&3\\2&5\end{pmatrix}}$

कुंजी बनें और मान लें कि सादा पाठ संदेश 'सहायता' है। फिर इस प्लेनटेक्स्ट को दो जोड़ियों द्वारा दर्शाया जाता है

$HELP\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to {\begin{pmatrix}7\\4\end{pmatrix}},{\begin{pmatrix}11\\15\end{pmatrix}}$

फिर हम गणना करते हैं

${\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}7\\4\end{pmatrix}}\equiv {\begin{pmatrix}7\\8\end{pmatrix}}{\pmod {26}},$ और

${\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}11\\15\end{pmatrix}}\equiv {\begin{pmatrix}0\\19\end{pmatrix}}{\pmod {26}}$

और निम्नानुसार एन्क्रिप्शन जारी रखें:

${\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end{pmatrix}}\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}$

इसलिए, मैट्रिक्स K उलटा है $K^{-1}$ ऐसा मौजूद है $KK^{-1}=K^{-1}K=I_{2}$. K के व्युत्क्रम की गणना व्युत्क्रमणीय मैट्रिक्स#2×2 मैट्रिक्स के व्युत्क्रम का उपयोग करके की जा सकती है ${\begin{pmatrix}a&b\\c&d\end{pmatrix}}^{-1}=(ad-bc)^{-1}{\begin{pmatrix}d&-b\\-c&a\end{pmatrix}}$ यदि गणना करने के लिए मॉड्यूलर गुणक व्युत्क्रम का उपयोग किया जाता है तो यह सूत्र मॉड्यूलर कमी के बाद भी लागू रहता है $(ad-bc)^{-1}$. इसलिए इस मामले में, हम गणना करते हैं

$K^{-1}\equiv 9^{-1}{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv 3{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv {\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\pmod {26}}$

$HIAT\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}\to {\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end{pmatrix}}$

फिर हम गणना करते हैं

${\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix}7\\8\end{pmatrix}}={\begin{pmatrix}241\\212\end{pmatrix}}\equiv {\begin{pmatrix}7\\4\end{pmatrix}}{\pmod {26}},$ और

${\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix}0\\19\end{pmatrix}}={\begin{pmatrix}323\\171\end{pmatrix}}\equiv {\begin{pmatrix}11\\15\end{pmatrix}}{\pmod {26}}$

इसलिए,

${\begin{pmatrix}7\\4\end{pmatrix}},{\begin{pmatrix}11\\15\end{pmatrix}}\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to HELP$.

सुरक्षा

मूल हिल सिफर ज्ञात-प्लेनटेक्स्ट हमले के प्रति संवेदनशील है क्योंकि यह पूरी तरह से रैखिक है। एक प्रतिद्वंद्वी जो अवरोधन करता है $n^{2}$ प्लेनटेक्स्ट/सिफरटेक्स्ट कैरेक्टर जोड़े एक रैखिक प्रणाली स्थापित कर सकते हैं जिसे (आमतौर पर) आसानी से हल किया जा सकता है; यदि ऐसा होता है कि यह प्रणाली अनिश्चित है, तो केवल कुछ और प्लेनटेक्स्ट/सिफरटेक्स्ट जोड़े जोड़ना आवश्यक है। मानक रैखिक बीजगणित एल्गोरिदम द्वारा इस समाधान की गणना करने में बहुत कम समय लगता है।

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

कुंजी स्थान आकार

key_space_(क्रिप्टोग्राफी) सभी संभावित कुंजियों का समूह है। कुंजी स्थान का आकार संभावित कुंजियों की संख्या है। प्रभावी कुंजी आकार, बिट्स की संख्या में, कुंजी स्थान आकार का बाइनरी लघुगणक है।

वहाँ हैं $26^{n^{2}}$ आयाम n × n के आव्यूह। इस प्रकार $\log _{2}(26^{n^{2}})$ या के बारे में $4.7n^{2}$ n × n मैट्रिक्स का उपयोग करके हिल सिफर के कुंजी आकार पर एक ऊपरी सीमा है। यह केवल एक ऊपरी सीमा है क्योंकि प्रत्येक मैट्रिक्स उलटा नहीं होता है और इसलिए कुंजी के रूप में प्रयोग करने योग्य नहीं होता है। व्युत्क्रमणीय आव्यूहों की संख्या की गणना चीनी शेष प्रमेय के माध्यम से की जा सकती है। यानी, एक मैट्रिक्स व्युत्क्रमणीय मॉड्यूलो 26 है यदि और केवल यदि यह मॉड्यूलो 2 और मॉड्यूलो 13 दोनों व्युत्क्रमणीय है। व्युत्क्रमणीय n × n आव्यूह मॉड्यूलो 2 की संख्या सामान्य रैखिक समूह GL(n,'Z' के क्रम के बराबर है₂). यह है

$2^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n}).$

समान रूप से, व्युत्क्रमणीय आव्यूहों की संख्या मापांक 13 (अर्थात् GL(n,Z) का क्रम₁₃)) है

$13^{n^{2}}(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).$

व्युत्क्रमणीय आव्यूह मॉड्यूलो 26 की संख्या उन दो संख्याओं का गुणनफल है। इसलिए यह है

$26^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).$

इसके अतिरिक्त, कुंजी मैट्रिक्स में बहुत अधिक शून्य से बचना समझदारी है, क्योंकि वे प्रसार को कम करते हैं। कुल प्रभाव यह है कि एक मूल हिल सिफर का प्रभावी कीस्पेस लगभग है $4.64n^{2}-1.7$. 5 × 5 हिल सिफर के लिए, यह लगभग 114 बिट्स है। बेशक, कुंजी खोज सबसे कुशल ज्ञात हमला नहीं है।

यांत्रिक कार्यान्वयन

एक साथ 2 प्रतीकों पर काम करते समय, एक हिल सिफर प्लेफेयर सिफर या द्विभाजित सिफर पर कोई विशेष लाभ प्रदान नहीं करता है, और वास्तव में दोनों की तुलना में कमजोर है, और पेंसिल और कागज द्वारा संचालित करने के लिए थोड़ा अधिक श्रमसाध्य है। जैसे-जैसे आयाम बढ़ता है, सिफर तेजी से मनुष्य के लिए हाथ से संचालित करना असंभव हो जाता है।

आयाम 6 का एक हिल सिफर यंत्रवत् लागू किया गया था। हिल और एक साथी को एक पेटेंट से सम्मानित किया गया (U.S. Patent 1,845,947) इस उपकरण के लिए, जिसने गियर और चेन की एक प्रणाली का उपयोग करके 6 × 6 मैट्रिक्स गुणन मोडुलो 26 का प्रदर्शन किया।

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

यह भी देखें

अन्य व्यावहारिक पेंसिल-और-पेपर पॉलीग्राफिक सिफर में शामिल हैं:

• प्लेफेयर सिफर
• द्विभाजित सिफर
• त्रिफिड सिफर

संदर्भ

• Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly Vol.36, June–July 1929, pp. 306–312. (PDF)
• Lester S. Hill, Concerning Certain Linear Transformation Apparatus of Cryptography, The American Mathematical Monthly Vol.38, 1931, pp. 135–154.
• Jeffrey Overbey, William Traves, and Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, Vol.29, No.1, January 2005, pp59–72. (CiteSeerX) (PDF)

बाहरी संबंध

• "Hill Cipher Web App" implements the Hill cipher and shows the matrices involved
• "Hill Cipher Explained" illustrates the linear algebra behind the Hill Cipher
• "Hill's Cipher Calculator" outlines the Hill Cipher with a Web page