सरल ग्राफिकल परीक्षणों के साथ यादृच्छिक अनुक्रम विश्लेषण

अमूर्त

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

टेस्ट "अनुमानित एन्ट्रॉपी"

"अनुमानित एंट्रोपी" की गणना एनआईएसटी परीक्षण सूट में शामिल परीक्षणों में से एक है।

इस परीक्षण में बिट्स के प्रारंभिक अनुक्रम में लंबाई एम बिट्स के सभी संभावित अतिव्यापी पैटर्न की आवृत्ति की गिनती होती है। परीक्षण का उद्देश्य पूरी तरह से यादृच्छिक अनुक्रम में समान ब्लॉकों की ओवरलैप आवृत्तियों के साथ लंबाई एम और एम + 1 के साथ मूल अनुक्रम के दो लगातार ब्लॉकों के ओवरलैप आवृत्तियों की तुलना करना है। परीक्षण के दौरान गणना की जाने वाली संभावना कम से कम 0.01 होनी चाहिए। अन्यथा (पी <0.01), बाइनरी अनुक्रम पूरी तरह से मनमाना नहीं है।

एपन (एम), जहां एन आने वाले अनुक्रम की थोड़ी लंबाई है; मी परीक्षण के लिए प्रारंभिक ब्लॉक की लंबाई में लंबाई है; sequence थोड़ा अनुक्रम है

चरण 1

N-बिट अनुक्रम को m-bit अनुक्रम के साथ ठीक से ओवरले प्राप्त करने के लिए पूरा करें। ऐसा करने के लिए, अनुक्रम की शुरुआत से इसके अंत तक m-1 बिट जोड़ें।

उदाहरण के लिए: example = 0100110101 और एम = 3, फिर n = 10. अनुक्रम की शुरुआत और अनुक्रम के अंत में 0 और 1 जोड़ें। (यह m के प्रत्येक मान के लिए किया जाता है)।
यह एक परीक्षण अनुक्रम में परिणाम देगा: 010011010101।

चरण 2

आवृत्ति की गणना एन ओवरलैपिंग ब्लॉकों के लिए की जाती है (उदाहरण के लिए: यदि _{is j} और calculated _{j + m-1} वाले ब्लॉक की गणना स्थिति j पर _की जाती है, तो block _{j + 1} और _{+ j + m} वाले ब्लॉक _की गणना स्थिति j + 1 से की जाती है)।

संभावित m-bit ((m + 1) -बिट) मानों की संख्या C _m ^{i के} रूप में दर्शाई जाती है, जहाँ मैं m-bit मान हूँ।

चरण 1 में प्राप्त परीक्षण अनुक्रम के लिए, ओवरलैपिंग एम-बिट ब्लॉक (एम = 3 के साथ) 010, 100, 001, 011, 110, 101, 010, 101, 010, और 101 होंगे। घटनाओं की संख्या 2 ^{मीटर -} 2 ³ = 8 एम-बिट अनुक्रम:
# 000 = 0, # 001 = 1, # 010 = 3, # 011 = 1, # 100 = 1, # 101 = 3, # 110 = 1, # 111 = 0

चरण 3

हम ⁱ के प्रत्येक मान के लिए C _m ^{i की} गणना करते हैं।
C ³ ₀₀₀ = 0, C ³ ₀₀₁ = 0.1, C ³ ₀₁₀ = 0.3, C ³ ₀₁₁ = 0.1, C ³ ₁₀₀ = 0.1, C ³ ₁₀₁ = 0.3, C ³ ₁₁₀ = 0.1, C ³ ₁₁₁ = 0।

चरण 4

हम एक गणना करते हैं
जहाँ
π _i = C ³ _j , और j = log ₂ i
वर्तमान उदाहरण के लिए: ϕ ⁽³⁾ = 0 (लॉग 0) + 0.1 (लॉग 0.1) + 0.3 (लॉग 0.3) + 0.1 (लॉग 0.1) +
0.1 (लॉग 0.1) + 0.3 (लॉग 0.3) + 0.1 (लॉग 0.1) + 0 (लॉग 0) = -1.64341772।

चरण 5

M = m + 1 के लिए चरण 1-4 दोहराएं

चरण 6

हमें ApEn (m) = ^{m (m)} -φ ^{(m + 1)} का मान मिलता है

वर्तमान उदाहरण के लिए, ApEn (3) = -1.643418 - (-1.834372) = 0.190954

आवक मान

N और m का मान चुनना आवश्यक है जैसे: m <log ₂ n-5

प्लॉटिंग

रेखांकन प्राप्त करने के लिए, M = 2 पर ApEn की गणना करने के लिए परीक्षणों की एक श्रृंखला की गई। N का मान 0 से 1,000,000 तक 100 की वेतन वृद्धि में था। परीक्षणों की एक श्रृंखला भी 1 के चरणों में निभाई गई थी। 1 के चरणों में प्राप्त परिणामों और 100 के वेतन वृद्धि में कोई महत्वपूर्ण अंतर नहीं है, इसलिए परीक्षण को 100 चरणों में ठीक से अंजाम दिया गया था। एक अनुक्रम के लिए अनुमानित गणना समय 1,000,000 बिट्स एक थ्रेड में Intel Core i3 U380 1.33 GHz पर लगभग 7 मिनट और 16 थ्रेड्स में लगभग 6:30 मिनट लगते हैं। लॉगरिदमिक स्केल Y का उपयोग रेखांकन प्रदर्शित करने के लिए किया जाता है, और परिणाम सामान्य वितरण से विचलन के रूप में प्रस्तुत किए जाते हैं। गणना सिद्धांत आलेख में वर्णित है स्टीवन एम। पिनस्कस अनुमानित एन्ट्रापी सिस्टम जटिलता का एक उपाय के रूप में

परिणामों की चित्रमय प्रस्तुति।

1. अतुल्यकालिक टाइमर पर एन्ट्रापी का स्रोत

टाइमर 1 - वॉचडॉग, आरसी-जनरेटर से घड़ी, टी 1 = 15 एमएस।
टाइमर 2 - 8 बिट, एक क्रिस्टल थरथरानवाला से घड़ी, घड़ी की आवृत्ति F = 16.0 MHz।

rand_async_1_1M - काउंटर 2 का सबसे कम महत्वपूर्ण बिट परिणाम के रूप में उपयोग किया जाता है। जनरेशन दर 120 बिट है
rand_async_4_1M - काउंटर 2 के निचले 4 बिट्स परिणाम के रूप में उपयोग किए जाते हैं। जनरेशन रेट 280 बिट / एस
rand_async_8_1M - काउंटर 2 के सभी 8 बिट्स परिणाम के रूप में उपयोग किए जाते हैं। जनरेशन स्पीड 450 बिट्स / एस

2. आरसी सर्किट के साथ एन्ट्रॉपी का स्रोत

समय निरंतर आरसी = 5 एमएस। घड़ी काउंटर फ्रीक्वेंसी F = 16.0 MHz।
rand_rc_1_1M - 1 कम से कम महत्वपूर्ण बिट का उपयोग परिणाम के रूप में किया जाता है। जनरेशन रेट 370 बीपीएस
rand_rc_4_1M - परिणाम के रूप में काउंटर के निचले 4 बिट्स का उपयोग किया जाता है। 1500 बिट / पीढ़ी दर
rand_rc_8_1M - काउंटर के सभी 8 बिट्स परिणाम के रूप में उपयोग किए जाते हैं। 2870 बिट / एस पीढ़ी दर

3. एडीसी पर एन्ट्रापी का स्रोत

मापा वोल्टेज VDD = 3.3 V (अस्थिर) है, संदर्भ वोल्टेज VCC = 5.0 V है। ADC संकल्प 10 बिट्स है, और रूपांतरण घड़ी की आवृत्ति 125 kHz है।
rand_adc_1_1M - ADC परिणाम का कम से कम महत्वपूर्ण बिट परिणाम के रूप में उपयोग किया जाता है। 8.93 केबीपीएस पीढ़ी की गति
rand_adc_2_1M - ADC परिणाम के निचले 2 बिट्स परिणाम के रूप में उपयोग किए जाते हैं। जनरेशन रेट 17.9 kbps
rand_adc_4_1M - ADC परिणाम के निचले 4 बिट्स परिणाम के रूप में उपयोग किए जाते हैं। जनरेशन रेट 29.5 केबीपीएस

निष्कर्ष

परिणामों के चित्रमय प्रतिनिधित्व को देखते हुए, हम यह निष्कर्ष निकाल सकते हैं कि माइक्रोकंट्रोलर्स का उपयोग करके प्राप्त यादृच्छिक अनुक्रमों की गुणवत्ता DIEHARD सेट से यादृच्छिक अनुक्रमों से कम परिमाण के कई आदेश हैं और "2" से वर्गमूल निकालकर प्राप्त अनुक्रम से।

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