फास्ट 128-बिट LFSR (MMX आवश्यक)

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

इसके अलावा, परिणामी अनुक्रम की गुणवत्ता छद्म यादृच्छिक संख्या जनरेटर के कार्यान्वयन की गुणवत्ता पर ही निर्भर करती है। जैसा कि कहा जाता है: "यादृच्छिक संख्या पीढ़ी को मौका देने के लिए छोड़ना बहुत महत्वपूर्ण है।"



एक छद्म आयामी संख्या जनरेटर को लागू करने के लिए बहुत सारे विकल्प हैं: यारो, पारंपरिक क्रिप्टो प्राइमेटिव का उपयोग करके, जैसे एईएस -256, एसएचए -1, एमडी 5; Microsoft क्रिप्टोकरंसी विदेशी अराजकता और PRAND और अन्य।

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

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

LFSR के बारे में थोड़ा सा

वस्तुतः, LFSR एक रैखिक प्रतिक्रिया पारी रजिस्टर है, जिसमें दो भाग होते हैं - एक पाली रजिस्टर और एक प्रतिक्रिया फ़ंक्शन। एक रजिस्टर में बिट्स होते हैं; इसकी लंबाई इन बिट्स की संख्या होती है।



जब एक बिट पुनर्प्राप्त किया जाता है, तो रजिस्टर के सभी बिट्स को एक स्थिति से दाईं ओर स्थानांतरित कर दिया जाता है। इस मामले में, नई सबसे बाईं बिट निष्कर्षण से पहले शेष बिट्स के कार्य द्वारा निर्धारित की जाती है। रजिस्टर के आउटपुट में सबसे कम महत्वपूर्ण बिट दिखाई देता है।



जैसा कि यह निर्धारित करना मुश्किल नहीं है, उत्पादित अनुक्रम के गुण संबंधित बहुपद के गुणों से निकटता से संबंधित हैं

इसके अलावा, इसके नॉनज़ेरो गुणांक को टैप कहा जाता है, जिसके आधार पर फीडबैक फ़ंक्शन के लिए इनपुट मान निर्धारित किए जाते हैं।

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

व्यावहारिक कार्यान्वयन

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

ईमानदारी से, मैं इससे सहमत नहीं हूं। जैसा कि मैंने देखा, अक्सर समस्या एल्गोरिथ्म में ही नहीं होती है, बल्कि इसके कार्यान्वयन में होती है। आमतौर पर हम निम्न प्रकार का निर्माण देखते हैं:

int LFSR (void) { static unsigned long S = 0xFFFFFFFF; /* taps: 32 31 30 28 26 1; charact. polynomial: x^32 + x^31 + x^30 + x^28 + x^26 + x^1 + 1 */ S = ((( (S>>0)^(S>>1)^(S>>2)^(S>>4)^(S>>6)^(S>>31) ) & 1 ) << 31 ) | (S>>1); return S & 1; } 

क्रूर। यहां, कम से कम, हम ध्वज रजिस्टर के समता ध्वज PF (समता ध्वज) के मूल्य का उपयोग करके कुछ XORs और पारियों से छुटकारा पा सकते हैं। वास्तव में, मोडुलो 2 (XOR) जोड़ बिट्स सेट की संख्या की समता निर्धारित करते हैं। यदि परिणाम का कम से कम महत्वपूर्ण बाइट इकाई (गैर-शून्य) बिट्स की एक समान संख्या है, अर्थात, केवल एकमात्र समता ध्वज PF सेट है, अर्थात हमें कम से कम एक अंकगणितीय बदलाव करना होगा:

 xor ecx,ecx mov ebx,0FFFFFFFFh ; S mov eax,080000057h ; taps (32,31,30,28,26,1) and ebx,eax mov cl,ah sar ebx,018h lahf xor cl,ah sar cl,02h and cl,01h 

घने बहुपद का उपयोग करने के मामले में, जब नल को 32-बिट रजिस्टर के पूरे क्षेत्र में वितरित किया जाता है, तो हम पहले से ही 4 बदलाव और 3 XOR ऑपरेशन प्राप्त करेंगे:

 xor ecx,ecx mov ebx,0FFFFFFFFh ; S mov eax,095324C57h ; taps (32,31,30,28,26,22,21,18,15,12,11,8,6,4,1) and ebx,eax lahf mov cl,ah ; [0-7] bits sar ebx,08h lahf xor cl,ah ; [8-15] bits sar ebx,08h lahf xor cl,ah ; [16-23] bits sar ebx,08h lahf xor cl,ah ; [24-31] bits sar cl,02h and cl,01h 

विचलन: मामले में जब सर ईबेक्स की संख्या, 08h पाली शून्य के बराबर या बराबर होती है, तो XOR को निष्पादित करने से पहले रजिस्टर एएच के मूल्य को पलटना आवश्यक है, क्योंकि पीएफ सेट किया जाता है जब नॉनजेरो बिट्स की संख्या भी होती है। और हमें इसके विपरीत चाहिए।

जो अब भी कुछ हद तक कोषेर है:

 int LFSR (void) { static unsigned long S = 0xFFFFFFFF; S = ((( (S>>0)^(S>>1)^(S>>2)^(S>>4)^(S>>6)^(S>>10)^(S>>11)^ (S>>14)^(S>>17)^(S>>20)^(S>>21)^(S>>24)^(S>>26)^ (S>>28)^(S>>31) ) & 1 ) << 31 ) | (S>>1); return S & 1; } 

अगला कदम प्रत्येक एलएफएसआर राज्य पर मेमोरी को सीधे फ्लश करने के बजाय परिणामों को जमा करने के लिए रजिस्टर का उपयोग करना है:

 sal edx,01h or dl,cl 

और 32 राज्यों (edx DWORD) तक, जिसके बाद ही हम मेमोरी में लिखते हैं।

और अंत में, अगर हमें वास्तव में तेजी से 128-बिट LFSR (अचानक) लागू करने की आवश्यकता है, तो हम MMX रजिस्टरों का उपयोग कर सकते हैं, जो हमें मेमोरी एक्सेस (केवल रजिस्टरों के साधन) की आवश्यकता के बिना पेंटियम परिवार के 32-बिट प्रोसेसर पर एक बदलाव को लागू करने की अनुमति देगा।

स्रोत कोड
विधानसभा भाषा में स्रोत कोड (x86): pastebin.com/rwKfsYsN
संकलित निष्पादन योग्य कोड: www.sendspace.com/file/atg0cf

अपडेट:
अनुकूलित कोड संस्करण: pastebin.com/B3kPEaew
संकलित निष्पादन योग्य कोड: www.sendspace.com/file/9bl5di

• 128-बिट एलएफएसआर
• MMX रजिस्टर का इस्तेमाल किया
• x86 आर्किटेक्चर
• 2097120 (0FFFFh x 32) रजिस्टर LFSR की स्थिति बदलें

अंत में

अंत में, काम की गति के बारे में - 2 097 120 (0FFFFh x 32) को बदलकर 128-बिट LFSR "वार्मिंग" एमएमएक्स और कॉफी रजिस्टर फ्लैग (कॉफी डिस्प्ले) का उपयोग करते हुए मेरे पीसी पर लगभग 5 सेकंड लगे। इसी समय, उपरोक्त के साथ सादृश्य द्वारा लिखित C ++ प्रोग्राम का निष्पादन, लेकिन 128-बिट संस्करण के लिए और स्क्रीन के आउटपुट के साथ भी, इसमें लगभग 2-3 मिनट लगे।

इसी समय, मुख्य क्रिमिस यह है कि पैरिटी फ्लैग उपयोग मामले में, बहुपद घनत्व का नए एलएफएसआर रजिस्टर राज्य के लिए उलटा फ़ंक्शन की गणना की दर पर एक मजबूत प्रभाव नहीं है। और तदनुसार, शैली में कथन: “RSLOS की मुख्य समस्याओं में से एक यह है कि उनका सॉफ्टवेयर कार्यान्वयन बेहद अक्षम है। आपको विरल प्रतिक्रिया पॉलीओनियम्स से बचना होगा क्योंकि वे सहसंबंध को तोड़कर आसानी से टूटेंगे। और घने बहुपद की गणना बहुत धीरे-धीरे की जाती है ”(यहाँ से: ru.wikipedia.org/wiki/LFSR ) कुछ हद तक… अस्थिर हैं और स्पष्टीकरण की आवश्यकता है :)

ps और क्या दिलचस्प है, क्या एक उच्च-स्तरीय भाषा में एक प्रोग्राम कार्यान्वयन करना संभव है, कोडांतरक आवेषण के बिना, जिसका रनटाइम जब 2 097 120 (0FFFFh x 32) की गणना करता है, तो 128-बिट एफएफएसआर के लिए राज्यों ... उदाहरण के लिए, 0.5 सेकंड से कम होगा?