रैखिक प्रतिक्रिया शिफ्ट रजिस्टर। रैखिक आवर्तक रजिस्टर

फीडबैक शिफ्ट रजिस्टर ( एफएसआर ) दो भाग होते हैं: शिफ्ट का रजिस्टरऔर प्रतिक्रिया कार्य .

शिफ्ट रजिस्टर (त्रुटि: संदर्भ स्रोत नहीं मिला) बिट्स का अनुक्रम है। जब बिट को निकालने की आवश्यकता होती है, तो शिफ्ट रजिस्टर के सभी बिट्स को 1 स्थान से दाईं ओर स्थानांतरित कर दिया जाता है। सबसे नया सबसे नया बिट रजिस्टर में शेष बिट्स से फीडबैक फ़ंक्शन का मान है। अवधि शिफ्ट रजिस्टर दोहराना शुरू करने से पहले परिणामी अनुक्रम की लंबाई है।

फीडबैक शिफ्ट रजिस्टर का सबसे सरल प्रकार है प्रतिक्रिया के साथ रेखीय पारी रजिस्टर (एलएफएसआर – बाएं प्रतिक्रिया बदलाव पंजीकरण करवाना) (त्रुटि: संदर्भ स्रोत नहीं मिला)। फीडबैक केवल कुछ पी बिट्स का एक्सओआर है। रजिस्टर, इन बिट्स की सूची कहा जाता है बायपास अनुक्रम.

एन-bit LFSR इनमें से एक में हो सकता है 2 एन -1 आंतरिक राज्य। इसका मतलब यह है कि, सैद्धांतिक रूप से, ऐसा रजिस्टर एक अवधि के साथ छद्म-यादृच्छिक अनुक्रम उत्पन्न कर सकता है 2 एन -1 बिट्स। आंतरिक अवस्थाओं की संख्या और अवधि समान हैं, क्योंकि रजिस्टर को शून्य से भरने से यह शून्य के अनंत अनुक्रम का उत्पादन करेगा, जो बिल्कुल बेकार है। केवल कुछ टैप सीक्वेंस के साथ, एलएफएसआर सभी के माध्यम से साइकिल चलाएगा 2 एन -1 आंतरिक राज्य। ऐसे एलएफएसआर कहलाते हैं एलएफएसआरअधिकतम अवधि के साथ.

किसी विशेष एलएफएसआर के लिए अधिकतम अवधि, टैप अनुक्रम और स्थिरांक से गठित बहुपद 1 आदिम मॉड्यूलो होना चाहिए 2 .

एक बहुपद की आदिमता की गणना करना एक काफी जटिल गणितीय समस्या है। इसलिए, तैयार किए गए टेबल हैं जो जेनरेटर की अधिकतम अवधि प्रदान करने वाले टैप अनुक्रमों की संख्या सूचीबद्ध करते हैं। उदाहरण के लिए, 32-बिट शिफ्ट रजिस्टर के लिए, आप निम्नलिखित प्रविष्टि पा सकते हैं: (32,7,5,3,2,1,0) . इसका मतलब है कि एक नया बिट उत्पन्न करने के लिए, आपको XOR फ़ंक्शन का उपयोग करके बत्तीसवें, सातवें, पांचवें, तीसरे, दूसरे और पहले बिट्स का योग करना होगा।

सी ++ में ऐसे एलएफएसआर के लिए कोड होगा:

// शून्य के अलावा कोई भी मूल्य

ShiftRegister = (((((ShiftRegister >> 31)

^(ShiftRegister>>6)

^(ShiftRegister>>4)

^(ShiftRegister>>2)

^(ShiftRegister>>1)

^शिफ्टरजिस्टर)

और 0x00000001)<<31)

| (शिफ्टरजिस्टर >> 1);

वापसी शिफ्ट रजिस्टर और 0x00000001;

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

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

यह संशोधन कहा जाता है गैलोज़ विन्यास. सी भाषा में ऐसा दिखता है:

स्थिर अहस्ताक्षरित लंबा ShiftRegister = 1;

शून्य बीज_एलएफएसआर (अहस्ताक्षरित लंबा बीज)

शिफ्टरजिस्टर = बीज;

int Galua_LFSR(शून्य)

अगर (शिफ्टरजिस्टर और 0x00000001) (

ShiftRegister = (ShiftRegister ^ मास्क >> 1) | 0x8000000;

शिफ्ट रजिस्टर >>= 1;

भुगतान यह है कि सभी एक्सओआर एक ऑपरेशन में किए जाते हैं। इस सर्किट को समानांतर भी किया जा सकता है।

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

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

विवरण

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

संचालन का सिद्धांत

रैखिक जटिलता

सहसंबंध स्वतंत्रता

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

सॉफ्टवेयर कार्यान्वयन

RSLOS का सॉफ्टवेयर कार्यान्वयन काफी धीमा है और अगर वे असेंबलर में लिखे गए हैं तो तेजी से काम करते हैं। समाधानों में से एक 16 आरएलएलएस (या 32, कंप्यूटर आर्किटेक्चर में एक शब्द की लंबाई के आधार पर) का समानांतर उपयोग है। ऐसी योजना में, शब्दों की एक सरणी का उपयोग किया जाता है, जिसका आकार शिफ्ट रजिस्टर की लंबाई के बराबर होता है, और शब्द का प्रत्येक बिट अपने स्वयं के LFSR को संदर्भित करता है। चूंकि समान संख्या में नल अनुक्रमों का उपयोग किया जाता है, यह जनरेटर के प्रदर्शन में उल्लेखनीय लाभ दे सकता है।

फाइबोनैचि विन्यास

32-बिट शिफ्ट रजिस्टर पर विचार करें। इसमें भागने का क्रम है (32 , 31 , 30 , 28 , 26 , 1) (\displaystyle \बाएं(32,\;31,\;30,\;28,\;26,\;1\दाएं)). इसका मतलब है कि एक नया बिट उत्पन्न करने के लिए, XOR ऑपरेशन का उपयोग करके 31वें, 30वें, 29वें, 27वें, 25वें और 0वें बिट का योग करना आवश्यक है। परिणामी LFSR की अधिकतम अवधि होती है 2 32 − 1 (\displaystyle 2^(32)-1). C में ऐसे रजिस्टर का कोड इस प्रकार है:

int LFSR_Fibonacci (शून्य) ( स्थिर अहस्ताक्षरित लंबा S = 0x00000001 ; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >>) 25) ^ एस) और 0x00000001)<< 31 ) | (S >> 1); वापसी एस एंड 0x00000001; )

गैलोज़ विन्यास

इस जनरेटर में अधिक क्रिप्टोग्राफ़िक शक्ति नहीं है, लेकिन यह एक प्रदर्शन लाभ देता है: समांतरता के माध्यम से सभी एक्सओआर संचालन एक ऑपरेशन में किया जा सकता है, और क्रमिक रूप से एक के बाद एक नहीं, जैसा कि फिबोनैचि कॉन्फ़िगरेशन में होता है। यह योजना हार्डवेयर कार्यान्वयन में भी लाभ देगी।

C में 32-बिट शिफ्ट रजिस्टर का कोड इस प्रकार है:

int LFSR_Galois (शून्य) (स्थैतिक अहस्ताक्षरित लंबा S = 0x00000001; अगर (S & 0x00000001) (S = (S ^ 0x80000057 >> 1) | 0x80000000; वापसी 1;) और (S >>= 1; वापसी 0;))

यह ध्यान देने योग्य है कि Galois कॉन्फ़िगरेशन में LFSR_Galois फ़ंक्शन के लिए निश्चित संख्या में कॉल का चक्र फिबोनैचि कॉन्फ़िगरेशन में LFSR_Fibonacci फ़ंक्शन (Intel Core i5 पर MS VS 2010 कंपाइलर) की तुलना में लगभग 2 गुना तेज़ है।

उत्पन्न अनुक्रम उदाहरण

फाइबोनैचि विन्यास

एलएफएसआर को विशेषता बहुपद द्वारा दिया जाना चाहिए x 3 + x + 1 (\displaystyle x^(3)+x+1). इसका मतलब है कि टैप बिट्स 2 और 0 होंगे, और बहुपद सूत्र में इकाई का मतलब है कि 0 बिट इनपुट है। फीडबैक फ़ंक्शन का रूप है S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). मान लीजिए कि शिफ्ट रजिस्टर की प्रारंभिक स्थिति अनुक्रम थी। रजिस्टर के आगे के राज्य नीचे दी गई तालिका में दिखाए गए हैं:

चूंकि सातवें चरण में आंतरिक स्थिति अपनी मूल स्थिति में लौट आई है, इसलिए, अगले चरण से शुरू होकर, बिट्स को दोहराया जाएगा। तो उत्पन्न क्रम है: [1, 0, 0, 1, 1, 1, 0, 1। . . ] (\डिस्प्लेस्टाइल\बाएं)(अनुक्रम में बिट्स का क्रम उस क्रम से मेल खाता है जिसमें वे एलएफएसआर द्वारा उत्पन्न किए गए थे)। इस प्रकार, अनुक्रम की अवधि 7 है, अर्थात अधिकतम संभव मान, जो दिए गए बहुपद की प्रधानता के कारण हुआ।

गैलोज़ विन्यास

आइए हम समान अभिलाक्षणिक बहुपद लें, अर्थात्, सी 3 = सी 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). आउटपुट बिट में केवल पहला बिट जोड़ा जाता है। प्रारंभिक अवस्था वही है। रजिस्टर के आगे राज्यों:

सातवें चरण में रजिस्टर की आंतरिक स्थिति अपनी मूल स्थिति में लौट आई, इसलिए, इसकी अवधि भी 7 के बराबर है। फिबोनैचि कॉन्फ़िगरेशन के विपरीत, रजिस्टर की आंतरिक स्थिति अलग हो गई, लेकिन उत्पन्न अनुक्रम समान है , केवल 4 चक्रों द्वारा स्थानांतरित किया गया: [0, 1, 1, 1, 0, 0, 0, 0, 1, 1,। . . ] (\डिस्प्लेस्टाइल\बाएं)(अनुक्रम में बिट्स का क्रम उस क्रम से मेल खाता है जिसमें वे एलएफएसआर द्वारा उत्पन्न किए गए थे)।

आदिम बहुपद उत्पन्न करना

फायदे और नुकसान

लाभ

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

कमियां

उत्पन्न अनुक्रमों की क्रिप्टोग्राफ़िक शक्ति में सुधार करने के तरीके

मल्टीपल शिफ्ट रजिस्टर वाले जेनरेटर

इस प्रकार के जनरेटर में कई रैखिक फीडबैक शिफ्ट रजिस्टर होते हैं जो बिट्स उत्पन्न करते हैं x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\dots ,\;x_(M,i))क्रमश। इसके अलावा, उत्पन्न बिट्स को कुछ बूलियन फंक्शन द्वारा रूपांतरित किया जाता है f (x 1 , i , x 2 , i , … , x M , i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\dots ,\;x_(M) ,मैं))). यह ध्यान दिया जाना चाहिए कि इस प्रकार के जनरेटर की लंबाई रजिस्टर होती है एल आई (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\dots ,\;M), एक दूसरे के साथ कोप्राइम हैं।

इस जनरेटर की अवधि है T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^( L_(2))-1)\cdots (2^(L_(M))-1)\lessim 2^(L)), कहाँ L = ∑ i = 1 ML i (\displaystyle L=\sum \limits _(i=1)^(M)L_(i))- कोशिकाओं की कुल संख्या। इसलिए, एकल रजिस्टर की तुलना में कई एलएफएसआर का उपयोग उत्पन्न अनुक्रम की अवधि को बढ़ाता है, जिससे जनरेटर की क्रिप्टोग्राफ़िक शक्ति बढ़ जाती है। यह किसी दिए गए जनरेटर के अनुरूप रैखिक जटिलता या सबसे छोटे रजिस्टर की लंबाई भी बढ़ाता है। ऐसा रजिस्टर बर्लेकैंप-मैसी एल्गोरिथम का उपयोग करके उत्पन्न अनुक्रम का उपयोग करके पाया जाता है। सर्वोत्तम रूप से, इसकी लंबाई उत्पन्न अनुक्रम की अवधि के अनुरूप है।

गैर-रैखिक परिवर्तन वाले जनरेटर

ऐसे जनरेटर का ब्लॉक आरेख पिछले जनरेटर के आरेख से अलग नहीं है। मुख्य अंतर यह है कि ट्रांसफॉर्म डिवाइस एक गैर-रैखिक बूलियन फ़ंक्शन द्वारा दिया जाता है f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\dots ,x_(M))). उदाहरण के लिए, Zhegalkin बहुपद को इस तरह के एक फ़ंक्शन के रूप में लिया जाता है (Zhegalkin प्रमेय के अनुसार, किसी भी बूलियन फ़ंक्शन को Zhegalkin बहुपद द्वारा विशिष्ट रूप से दर्शाया जा सकता है)।

एक गैर-रैखिक जनरेटर भी लागू किया जा सकता है गैर रेखीय फीडबैक शिफ्ट रजिस्टर. वह दे सकता है 2 2 एल − 1 − एल (\displaystyle 2^(2^(L-1)-L))अनुक्रम अधिकतम अवधि के प्रकार, जो LFSR से अधिक है।

उपयोग किए गए फ़ंक्शन की गैर-रैखिकता के कारण इस जनरेटर की क्रिप्टोग्राफ़िक शक्ति बढ़ जाती है। उत्पन्न बिट अनुक्रम से रजिस्टरों की स्थिति का निर्धारण एक जटिल गणितीय समस्या है, क्योंकि कोई एल्गोरिदम ज्ञात नहीं है जो मूल राज्यों को पुनर्स्थापित करता है।

इस पद्धति का उपयोग किया जाता है, उदाहरण के लिए, में जनरेटर Geffऔर सामान्यीकृत Geff जनरेटर, हालांकि, ऐसे जनरेटर को एक सहसंबंध हमले से तोड़ा जा सकता है।

अलग-अलग शिफ्ट रजिस्टर टाइमिंग वाले जेनरेटर

स्टॉप-गो जनरेटर

स्टॉप-गो जनरेटर(इंग्लिश स्टॉप-एंड-गो, बोथ-पाइपर) LFOS-1 के आउटपुट का उपयोग LFOS-2 की क्लॉक फ्रीक्वेंसी को नियंत्रित करने के लिए करता है, ताकि LFSR-2 किसी समय में केवल तभी अपनी स्थिति बदलता है जब LFOS-1 का आउटपुट उस समय इकाई के बराबर था। इस योजना ने सहसंबंध-उद्घाटन का विरोध नहीं किया।

क्रिप्टोग्राफ़िक ताकत बढ़ाने के लिए, यह प्रस्तावित किया गया था स्टॉप-एंड-गो अल्टरनेटर. यह विभिन्न लंबाई के तीन शिफ्ट रजिस्टरों का उपयोग करता है। यहां LFOS-1 दूसरे और तीसरे रजिस्टरों की घड़ी की आवृत्ति को नियंत्रित करता है, यानी LFSR-2 अपनी स्थिति तब बदलता है जब LFSR-1 आउटपुट एक के बराबर होता है, और LFSR-3 - जब LFSR-1 आउटपुट शून्य के बराबर होता है। जनरेटर का आउटपुट RSLOS-2 और RSLOS-3 के  modulo दो आउटपुट को जोड़ने का ऑपरेशन है। इस जनरेटर की एक बड़ी अवधि और एक बड़ी रैखिक जटिलता है। आरएलओएस-1 के सहसंबंध खोलने की एक विधि है, लेकिन यह जनरेटर के क्रिप्टोग्राफ़िक गुणों को बहुत कमजोर नहीं करता है।

एक परिष्कृत क्लॉकिंग योजना का उपयोग किया जाता है टू-वे स्टॉप-एंड-गो जनरेटर, जो समान लंबाई के 2 शिफ्ट रजिस्टरों का उपयोग करता है। यदि किसी समय RLOS-1 का आउटपुट t i − 1 (\displaystyle t_(i-1))- एक, तो उस समय RLOS-2 को क्लॉक नहीं किया जाता है टी आई (\displaystyle t_(i)). यदि समय के समय RLOS-2 का आउटपुट t i − 1 (\displaystyle t_(i-1))शून्य के बराबर है, और समय पर t i − 2 (\displaystyle t_(i-2))- एक, और अगर इस रजिस्टर को उस समय क्लॉक किया जाता है टी आई (\displaystyle t_(i)), तो उसी समय RLOS-1 को क्लॉक नहीं किया जाता है। इस सर्किट की रैखिक जटिलता उत्पन्न अनुक्रम की अवधि के लगभग बराबर है।

स्व-डिकिमेटिंग जनरेटर

आंतरिक उत्पाद के साथ मल्टीरेट ऑसिलेटर

यह जनरेटर दो शिफ्ट रजिस्टर RSLOS-1 और RSLOS-2 का उपयोग करता है। में RSLOS-2 की घड़ी की आवृत्ति डी (\डिस्प्लेस्टाइल डी) RSLOS-1 से कई गुना अधिक। इन रजिस्टरों के कुछ बिट्स को AND ऑपरेशन का उपयोग करके एक दूसरे से गुणा किया जाता है। गुणन के परिणाम XOR ऑपरेशन द्वारा जोड़े जाते हैं, और आउटपुट अनुक्रम प्राप्त किया जाता है। इस जनरेटर में एक उच्च रैखिक जटिलता है और इसमें अच्छे सांख्यिकीय गुण हैं। हालाँकि, इसकी स्थिति को लंबाई के आउटपुट अनुक्रम से निर्धारित किया जा सकता है L 1 + L 2 + log 2 ⁡ d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), कहाँ एल 1 (\डिस्प्लेस्टाइल L_(1))और एल 2 (\डिस्प्लेस्टाइल L_(2))क्रमशः LFOS-1 और LFOS-2 की लंबाई हैं, और डी (\डिस्प्लेस्टाइल डी)- उनकी घड़ी की आवृत्तियों का अनुपात।

गोलमैन कैस्केड

यह सर्किट स्टॉप-गो जनरेटर का एक उन्नत संस्करण है। इसमें एलएफएसआर का एक क्रम होता है, जिनमें से प्रत्येक का समय पिछले एलएफएसआर द्वारा नियंत्रित होता है। यदि उस समय RLOS-1 का आउटपुट टी आई (\displaystyle t_(i)) 1 है, तो RLOS-2 क्लॉक किया जाता है। यदि समय के समय RLOS-2 का आउटपुट टी आई (\displaystyle t_(i)) 1 है, तो RLOS-3 क्लॉक किया जाता है, इत्यादि। अंतिम एलएफएसआर का आउटपुट जनरेटर का आउटपुट है। यदि सभी एलएफएसआर की लंबाई समान और बराबर है एल (\डिस्प्लेस्टाइल एल), तब से सिस्टम की अवधि एम (\डिस्प्लेस्टाइल एम)एलएफएसआर के बराबर है (2 एल − 1) एम (\displaystyle (2^(एल)-1)^(एम)), और रैखिक जटिलता है एल (एस) = एल (2 एल − 1) एम − 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .

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

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

चावल। 1. फीडबैक के साथ लीनियर शिफ्ट रजिस्टर

अधिकतम सिफर गामा अवधि प्राप्त करने के लिए, अंकों की संख्या एमशिफ्ट रजिस्टर को Mersenne primes (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), और आंतरिक लिंक में से एक चुना गया है। रजिस्टर के उच्चतम डिग्री के साथ अलघुकरणीय आदिम बहुपदों के अनुसार चुना जाना चाहिए एम. इस मामले में, सिफर गामा अवधि (2 एम-1).

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

रजिस्टरों का कैस्केड एलएफएसआर का एक सेट है जो इस तरह से जुड़ा हुआ है कि एक एलएफएसआर का व्यवहार कैस्केड में पिछले एलएफएसआर के व्यवहार पर निर्भर करता है। यह "आश्रित" व्यवहार आमतौर पर पहले एलएफएसआर द्वारा अगले एलएफएसआर के शिफ्ट काउंटर को नियंत्रित करने के लिए स्थापित किया जाता है।

उदाहरण के लिए, यदि पिछले रजिस्टर का मान 1 है, तो रजिस्टर को एक चरण से स्थानांतरित किया जाता है, और यदि मान 0 है, तो रजिस्टर को दो चरणों में या अन्यथा स्थानांतरित किया जाता है। बड़ी संख्या में ऐसे संयोजन बहुत उच्च सुरक्षा की अनुमति देते हैं।

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

देरी के साथ फाइबोनैचि विधिव्यापक रूप से उपयोग किए जाने वाले फाइबोनैचि जनरेटर में से एक निम्नलिखित पुनरावृत्त सूत्र पर आधारित है:

कहाँ वाई के- सीमा से वास्तविक संख्या

चावल। 2. राउंड-रॉबिन एन्क्रिप्शन

डीईएस आउटपुट फीडबैक मोड का उपयोग छद्म-यादृच्छिक संख्या उत्पन्न करने के लिए किया जा सकता है, जैसा कि स्ट्रीम एन्क्रिप्शन के लिए इसका उपयोग किया जाता है। प्रत्येक एन्क्रिप्शन चरण का आउटपुट 64-बिट मान है, जिसमें से केवल ऊपरी j बिट्स को एन्क्रिप्शन के लिए फीड किया जाता है। 64-बिट आउटपुट अच्छे सांख्यिकीय गुणों के साथ छद्म-यादृच्छिक संख्याओं का एक क्रम बनाते हैं।

ANSI X9.17 मानक में वर्णित छद्म-यादृच्छिक संख्या जनरेटर, क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म-यादृच्छिक संख्या जनरेटर में से एक है। इस तकनीक का उपयोग करने वाले अनुप्रयोगों में वित्तीय सुरक्षा और PGP अनुप्रयोग शामिल हैं।

ANSI X9.17 जनरेटर में निम्नलिखित भाग होते हैं (चित्र 3):

1. इनपुट: जनरेटर को दो छद्म-यादृच्छिक इनपुट द्वारा नियंत्रित किया जाता है। पहला इनपुट वर्तमान दिनांक और समय का 64-बिट प्रतिनिधित्व है ( डीटी आई) जो हर बार नंबर बनने पर बदल जाता है। दूसरा इनपुट एक 64-बिट प्रारंभिक मान है, जिसे कुछ मनमाना मूल्य के लिए आरंभीकृत किया जाता है और छद्म-यादृच्छिक संख्याओं के अनुक्रम की पीढ़ी के दौरान बदल दिया जाता है ( छठी).

2. कुंजियाँ: जनरेटर दो कुंजियाँ K 1, K 2 के साथ तीन ट्रिपल DES मॉड्यूल का उपयोग करता है। तीनों एक ही 56-बिट कुंजी जोड़ी का उपयोग करते हैं, जिसे गुप्त रखा जाना चाहिए और केवल छद्म-यादृच्छिक संख्या उत्पन्न करने के लिए उपयोग किया जाना चाहिए।

चावल। 3. एएनएसआई X9.17 छद्म-यादृच्छिक संख्या जनरेटर

फीडबैक शिफ्ट रजिस्टरदो भाग होते हैं: शिफ्ट रजिस्टर और प्रतिक्रिया कार्य.

चित्र 19. फीडबैक शिफ्ट रजिस्टर।

सामान्य तौर पर, शिफ्ट रजिस्टर रिंग या फील्ड के कुछ तत्वों का एक क्रम होता है। अधिकतर प्रयोग होने वाला अंशशिफ्ट रजिस्टर। ऐसे रजिस्टर की लंबाई को कई बिट्स के रूप में व्यक्त किया जाता है। हर बार एक बिट को पुनः प्राप्त किया जाता है, रजिस्टर में सभी बिट्स को एक स्थान से दाईं ओर स्थानांतरित कर दिया जाता है। नए सबसे महत्वपूर्ण बिट की गणना रजिस्टर में अन्य सभी बिट्स के एक समारोह के रूप में की जाती है। आउटपुट आमतौर पर सबसे कम महत्वपूर्ण बिट होता है। शिफ्ट रजिस्टर की अवधि पुनरावृत्ति शुरू होने से पहले आउटपुट अनुक्रम की लंबाई है।

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

चित्र 20। फाइबोनैचि विन्यास का एलएफओएस।

एलएफएसआर के सॉफ्टवेयर कार्यान्वयन में, एक संशोधित योजना का उपयोग किया जाता है: एक नया महत्वपूर्ण बिट उत्पन्न करने के लिए, टैप अनुक्रम के बिट्स का उपयोग करने के बजाय, जनरेटर के आउटपुट के साथ इसके प्रत्येक बिट पर एक एक्सओआर ऑपरेशन किया जाता है, पुराने की जगह टैप सीक्वेंस का थोड़ा सा। इस संशोधन को कभी-कभी कहा जाता है गैलोज़ विन्यास.

चित्र 21। Galois कॉन्फ़िगरेशन का RLOS।

एन-bit LFSR 2 में से एक में हो सकता है एन- 1 आंतरिक स्थिति। इसका मतलब है कि, सैद्धांतिक रूप से, ऐसा रजिस्टर 2 की अवधि के साथ छद्म-यादृच्छिक अनुक्रम उत्पन्न कर सकता है एन- 1 बिट (शून्य के साथ पैडिंग पूरी तरह बेकार है)। सभी का मार्ग 2 एन- 1 आंतरिक स्थिति केवल कुछ टैप अनुक्रमों के साथ ही संभव है। ऐसे रजिस्टरों को अधिकतम अवधि के साथ एलएफएसआर कहा जाता है। LFSR की अधिकतम अवधि सुनिश्चित करने के लिए यह आवश्यक है कि इसकी विशेषता बहुपद हो प्राचीनमोडुलो 2। बहुपद की डिग्री शिफ्ट रजिस्टर की लंबाई है। आदिम डिग्री बहुपद एन- यह इस तरह है अलघुकरणीयएक बहुपद जो एक भाजक है लेकिन भाजक नहीं है एक्स डी+ 1 सभी के लिए डी, जो 2 के विभाजक हैं एन- 1. (बहुपद पर चर्चा करते समय, शब्द अभाज्य संख्यापद से प्रतिस्थापित अलघुकरणीय बहुपद). एलएफएसआर की विशेषता बहुपद आंकड़ों में दिखाया गया है:

एक्स 32 + एक्स 7 + एक्स 5 + एक्स 3 + एक्स 2 + एक्स + 1

आदिम मोडुलो 2 है। इस तरह के एक रजिस्टर की अवधि अधिकतम होगी, सभी 2 32 - 1 मूल्यों के माध्यम से साइकिल चलाना जब तक वे दोहराते नहीं हैं। सबसे अधिक उपयोग किए जाने वाले पतले बहुपद हैं, अर्थात। जिनमें केवल कुछ गुणांक होते हैं। सबसे लोकप्रिय ट्रिनोमियल।

एलएफएसआर पर आधारित जनरेटर का एक महत्वपूर्ण पैरामीटर है रैखिक जटिलता. इसे लंबाई के रूप में परिभाषित किया गया है एनसबसे छोटा एलएफएसआर जो जनरेटर आउटपुट का अनुकरण कर सकता है। रैखिक जटिलता महत्वपूर्ण है क्योंकि एक सरल के साथ बर्लेनकैंप-मैसी एल्गोरिथमकेवल 2 की जाँच करके इस तरह के LFSR को फिर से बनाना संभव है एनगामा बिट्स। वांछित एलएफएसआर की परिभाषा के साथ, स्ट्रीम सिफर वास्तव में टूटा हुआ है।

LFSR के अलावा, नॉन-लीनियर फीडबैक, ट्रांसफर फीडबैक आदि के साथ शिफ्ट रजिस्टर का भी उपयोग किया जाता है।

संख्या-सैद्धांतिक दृष्टिकोण (ब्लम-माइकली जनरेटर, आरएसए, बीबीएस, संपीड़न, योजक जनरेटर, आदि) के आधार पर कई जनरेटर विकसित किए गए हैं।

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

सबसे सरल प्रकार का फीडबैक फ़ंक्शन एक रैखिक फ़ंक्शन है, जैसे कि मॉड्यूल 2 कुछ बिट्स की सामग्री का योग। इस तरह के एक रजिस्टर को लीनियर फीडबैक शिफ्ट रजिस्टर (लघु के लिए एलएफएसआर) कहा जाता है। सामान्य स्थिति में, रैखिक प्रतिक्रिया फ़ंक्शन सूत्र द्वारा दिया जाता है। यहाँ सी के= 1 अगर कवें बिट का उपयोग फीडबैक फ़ंक्शन में किया जाता है, और सी के= 0 अन्यथा। प्रतीक Å मॉड्यूलो 2 जोड़ (अनन्य OR) के लिए है।

उदाहरण के लिए, फीडबैक फ़ंक्शन के साथ एलएफएसआर पर विचार करें (आंकड़ा देखें)।

यदि रजिस्टर की प्रारंभिक स्थिति 1111 है, तो बाद के चरणों में यह राज्यों की निम्नलिखित श्रृंखला को स्वीकार करेगा: 1111, 011, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100 , 1110, 1111, 1111, 1111 …

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

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

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