हिल सिफर

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

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

निम्नलिखित चर्चा आव्यूहों के प्रारंभिक ज्ञान पर आधारित है।

एन्क्रिप्शन

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

लेटर	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
नंबर	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

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

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

संदेश 'एसीटी' और नीचे दी गई कुंजी (या अक्षरों में जीवाईबी/एनक्यूके/यूआरपी) पर विचार करें:

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

चूँकि 'A' 0 है, 'C' 2 है और 'T' 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}}$

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

${\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}}$

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

डिक्रिप्शन

डिक्रिप्ट करने के लिए, हम सिफरटेक्स्ट को वापस एक सदिश में बदल देते हैं, फिर कुंजी आव्यूह के व्युत्क्रम आव्यूह (अक्षरों में आईएफके/वीआईवी/वीएमआई) से गुणा करते हैं। हम पाते हैं कि, मॉड्यूलो 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}}$

जो हमें उम्मीद के के अनुसार 'एसीटी' पर वापस ले जाता है।

व्युत्क्रम आव्यूह को चुनने में दो समष्टि उपस्थित हैं:

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 के व्युत्क्रम की गणना सूत्र का उपयोग करके की जा सकती है${\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}$ प्लेनटेक्स्ट/सिफरटेक्स्ट वर्ण जोड़े को रोकता है, वह एक रैखिक प्रणाली स्थापित कर सकता है जिसे (समान्यत: पर) सरलता से हल किया जा सकता है; यदि ऐसा होता है कि यह प्रणाली अनिश्चित है, तो केवल कुछ और प्लेनटेक्स्ट/सिफरटेक्स्ट जोड़े जोड़ना आवश्यक है। मानक रैखिक बीजगणित एल्गोरिदम द्वारा इस समाधान की गणना करने में बहुत कम समय लगता है।

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

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

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

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

$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