बूलियन कार्यों से क्रमपरिवर्तन के निर्माण पर कुछ प्रश्न
मैंने बूलियन फ़ंक्शंस के कई उदाहरणों को एक क्रमपरिवर्तन के रूप में इस्तेमाल किया है।
उदाहरण के लिए केकेक ची: 2.3.1 फ़ंक्शन:
से https://keccak.team/figures.html
या एक सूत्र के रूप में: के लिए $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ अनुक्रमित modulo 5 की गणना के साथ
पहला सवाल यह होगा कि औचित्य क्या है (या प्रमाण) यह एक क्रमपरिवर्तन क्यों है?
दूसरा, संबंधित एक: गुण क्या हैं, बूलियन फ़ंक्शन को संतुष्ट करना पड़ता है कि यह एक क्रमपरिवर्तन का परिणाम है?
और अब इस तरह के क्रमपरिवर्तन के व्युत्क्रम के बारे में।
क्या इस तरह के निर्माण के व्युत्क्रम को खोजने के लिए कोई सामान्य तरीके / एल्गोरिदम हैं?
इसके अलावा, व्युत्क्रम (चर की संख्या, बीजगणितीय डिग्री आदि) की जटिलता के लिए प्रमुख योगदान कारक क्या हैं?
और अगर इस तरह की विधि एक बड़े इनपुट पर लागू होती है - तो कहो $i=\{0..127\}$, क्या व्युत्क्रम की गणना करना अधिक कठिन है, यदि फ़ंक्शन में केवल कुछ है (जैसे कि ची के लिए 3) या कई, 128 कहते हैं, इनपुट चर?
किसी भी उत्तर / संकेत की सराहना की जाती है।
जवाब
सामान्य बीजीय प्रश्न बहुविकल्पीय है और काफी जटिल हो सकता है। कुछ वेक्टर स्पेस पर निर्भर हैं, कुछ एक्सटेंशन फील्ड गुणों पर।
जैसा कि टिप्पणियों में उल्लेख किया गया है कि संपत्ति की जांच सरल हो सकती है।
मैंने एक संबंधित प्रश्न का उत्तर दिया बहु आउटपुट बिट संतुलित बूलियन फ़ंक्शन के उदाहरण
न्यबर्ग के लेखों का उल्लेख है
के। न्यूर्ब, क्रिप्टोग्राफी के लिए विभेदित रूप से समान मैपिंग , 1993 और
के न्यबर्ग, परफेक्ट नाइलिनियर एस-बॉक्स , 1992
दोनों आसानी से Google विद्वान पर खोजा जा सकता है।
संपादित करें : केककेक$\chi$ नक्शे $\{0,1\}^5$ खुद को।
मैं इस्तेमाल करूँगा $a_i$ इनपुट के रूप में और $A_i$ संपादित प्रश्न में आउटपुट चर के रूप में।
यदि कोई नहीं है, तो सूचकांकों के मोडुलो 5 की गिनती करना $i$ ऐसा है कि $(a_i,a_{i+2})=(0,1)$ तब फिर $\chi$उस इनपुट के लिए एक निश्चित बिंदु है। चलो$W=\{i: (a_i,a_{i+2})=(0,1)\},$ फिर सामान्य मैपिंग से संबंधित बिट्स को निष्क्रिय कर देता है $i.$
ध्यान दें कि सेट $J_i,J_j$ कहां है $J_i=\{i,i+2\}$ सिवाय कब तक असंतुष्ट हैं $j=i+2$ या $i=j+2.$इसलिए व्युत्क्रम का निर्धारण करने के लिए कोई अस्पष्टता नहीं है जब तक कि हम इस विशेष मामले में नहीं हैं, इस प्रकार इस विशेष मामले को छोड़कर उलटा मौजूद है। लेकिन इस मामले में भी पैटर्न$(a_i,a_{i+2},a_{i+4})$ जिसके परिणामस्वरूप बिटफ़्लिप असंदिग्ध हैं।
अगर $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ तब फिर $a_{i+1}$ फ़्लिप किया जाएगा लेकिन नहीं $a_{i+3}$। इसलिए$A_{i+1}=1\oplus a_{i+1},$ तथा $A_{i+3}=a_{i+3}.$
अगर $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ तब फिर $a_{i+1}$ फ़्लिप किया जाएगा लेकिन जरूरी नहीं $a_{i+3}$, कि के मूल्य पर निर्भर करेगा $a_{i+6}=a_{i+1}$। लेकिन वह बिट पिछले तर्क से प्रभावित नहीं है$J_i$ तथा $J_j$ निराश हैं अगर $i=j+1\pmod 2.$
तो एक अद्वितीय उलटा मानचित्रण मौजूद है।
टिप्पणी : सामान्य तौर पर "आधार स्वतंत्र" विस्तार क्षेत्र निर्माणों के बीच क्रमपरिवर्तन बनाम "आधार आश्रित" बिट वेक्टर क्रमांकन मुश्किल से सीधा है। मैं इस क्रमपरिवर्तन के लिए एक तत्काल आधार स्वतंत्र विस्तार क्षेत्र निर्माण नहीं देखता, और जैसा कि टिप्पणियों में कहा गया है कि इस तरह के योगों (लेग्रेग इंटरपोलेशन द्वारा प्राप्त किए गए प्रश्न), काफी जटिल और उच्च डिग्री हो सकते हैं।
द $\chi$समारोह को परिभाषित किया गया है और Joan Daemen Ph.D में विश्लेषण किया गया है। थीसिस
- सिफर और हैश फंक्शन डिजाइन रणनीतियाँ रैखिक और अंतर क्रिप्टोनालिसिस, 1995 पर आधारित हैं
अध्याय 6: Shift-Invariant Transformations (SIT) वह जगह है जहां सिद्धांत का उल्लेख किया गया है। मैं इसकी एक झलक (बहुत सारी परिभाषाएँ और परिणाम) प्रदान करूँगा।
एसआईटी के गुण जो उन्हें उपयोगी बनाते हैं;
- हार्डवेयर में, इन परिवर्तनों को समान 1-बिट आउटपुट "प्रोसेसर" के एक परस्पर सरणी के रूप में लागू किया जा सकता है।
- शिफ्ट-इनवेरियन यह सुनिश्चित करता है कि कम्प्यूटेशनल लोड को बेहतर तरीके से वितरित किया जाए।
- सॉफ्टवेयर में, उनकी नियमितता बिटवाइज़ लॉजिकल ऑपरेशंस को नियोजित करके कुशल कार्यान्वयन की अनुमति देती है।
- इसके अलावा, बाइनरी शिफ्ट-इनवेरिएंट ट्रांसफॉर्मेशन को एकल बूलियन फ़ंक्शन द्वारा निर्दिष्ट किया जा सकता है।
एसआईटी बहुत ही बारीक सेलुलर ऑटोमेटा से संबंधित हैं जो समय के साथ दीर्घकालिक संरचना और पैटर्न पर ध्यान केंद्रित करते हैं, यह काम इनवर्टरिटी और स्थानीय प्रसार और सहसंबंध गुणों के अल्पकालिक पहलुओं पर ध्यान केंद्रित करता है।
परिभाषा 6.1: एक परिवर्तन$\phi: \mathcal{A} \to \mathcal{A}$है पाली-अपरिवर्तनीय अगर
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ कहां है $\mathcal{A}$ सभी संभव अवस्थाएँ हैं।
फिर इसने स्थानीय मानचित्रों को परिभाषित किया जहां छवि केवल कुछ इनपुट पर निर्भर करती है।
प्रमेय 6.1 (डी। रिचर्डसन) यदि एक परिवर्तन$\phi$ परिमित के साथ $\nu$ उलटा है, फिर उसका उलटा $\phi^{−1}$ परिमित के साथ एक पारी-अपरिवर्तनीय परिवर्तन है $\nu$।
कहा पे $\nu$पड़ोस को परिभाषित करता है, 6.3 स्थानीय मानचित्र देखें । यह प्रमेय स्पष्ट रूप से प्रतिलोम का निर्माण प्रदान नहीं करता है।
धारा 6.6 परिमित के साथ गैर-रेखीय परिवर्तन $\nu$ वह जगह है जहाँ कार्रवाई शुरू की गई है।
यहां स्थानीय मानचित्र को पैटर्न के एक सेट द्वारा निर्दिष्ट किया गया है, जिसे पूरक परिदृश्य (सीएल) कहा जाता है। किसी घटक का मान पूरक होता है यदि उसका पड़ोस इनमें से किसी एक पैटर्न पर होता है। एक परिदृश्य प्रतीकों से मिलकर एक पैटर्न है$1, 0$, तथा $\textbf{-}$ एक मूल के सापेक्ष तैनात "परवाह न करें", जिसे दर्शाया गया है $∗$। इस संदर्भ में, सर्व-शून्य स्थिति को निरूपित किया जाएगा$0^*$ और सभी एक राज्य द्वारा $1^*$।
का विलोम $\chi$स्थानीय और वैश्विक अक्षमता वर्गों में बात की जाती है जिन्हें सिद्धांत में गहराई की आवश्यकता होती है। एक अच्छा पढ़ने के लिए अगर आप चाहते हैं जानने के लिए।
इसलिए, जैसा कि मैंने टिप्पणियों में कहा है, या तो सभी वांछित संपत्ति को देखने के लिए सभी संभावित क्रमों की तलाश कर सकते हैं, या सिद्धांत में Daemen के रूप में देख सकते हैं, किया। उन्होंने इस सिद्धांत का उपयोग वर्षों बाद स्पंज निर्माण में किया था$\chi$ SHA-3 का एकमात्र गैर-रेखीय हिस्सा है।
चूँकि मेरे पहले प्रश्न का उत्तर क्लोडलू और केलकाका के उत्तर में विस्तार से दिया गया है, मैं पोस्टिंग के बाद से अपने दूसरे प्रश्न पर एकत्रित किए गए परिणामों को साझा करना चाहता था:
गुण क्या हैं, बूलियन फ़ंक्शन को संतुष्ट करना पड़ता है कि यह क्रमचय में परिणत होता है?
बहुत सारे अतिरिक्त पढ़ने के दौरान मैंने पाया कि यह एक अच्छी तरह से (लेकिन व्यापक रूप से नहीं) ज्ञात संपत्ति है। क्रिप्टोग्राफी अध्याय 2.3.1 के प्रस्ताव 2 के रूप में वेक्टर बुलियन फ़ंक्शंस में कहा और सिद्ध किया गया उदाहरण :
ए (एन, एम) -फंक्शन संतुलित है अगर और केवल अगर इसके घटक कार्य संतुलित हैं, अर्थात, यदि और केवल यदि, तो प्रत्येक नॉनजरो v) के लिए $F^2_m$, बूलियन फ़ंक्शन v · F संतुलित है।
अध्याय 2.3 के अतिरिक्त तथ्य के साथ:
संतुलित (n, n) -functions पर क्रमपरिवर्तन हैं $F^2_n$
तो, एक (एन, एन) -फंक्शन एक क्रमचय है, यदि और केवल अगर यह उपरोक्त परिभाषा के अनुसार संतुलित है।
दूसरे शब्दों में, प्रत्येक घटक फ़ंक्शन को संतुलित करना पड़ता है, साथ ही घटक कार्यों के किसी भी संभावित संयोजन, झुकाव। एक बार में सभी कार्यों को संतुलित करना होगा।
वैसे, यह संपत्ति भी कम स्पष्ट रूप से, सिफर और हैश फंक्शन डिजाइन रणनीतियों में रैखिक और अंतर क्रिप्टोनालिसिस पर आधारित है, 1995 प्रमेय 5.1
इसका अर्थ यह भी है कि बड़े कार्यों के लिए सामान्य स्थिति के लिए इस संपत्ति की जाँच करना, उदाहरण के लिए 64 बिट चौड़ा (n = 64), संभव नहीं है क्योंकि इसके लिए 2 ^ 64 - 1 विभिन्न संयोजनों (2 ^ 64 संभावित इनपुटों के लिए) की आवश्यकता होगी। । तो कुछ ट्रिक्स या शॉर्टकट्स की आवश्यकता होगी।