जब मैंने प्रोग्राम करना सीखा, तो यह मुझे हमेशा अभ्यास में समस्या रहित समस्याओं को हल करने के लिए परेशान करता था। अब मैं पढ़ाता हूं, और मैं नहीं चाहता कि छात्र मेरी कक्षाओं में बोर हों।

इस लेख में, मैं MIT योजना भाषा में एन्क्रिप्शन और डिक्रिप्शन विधि RSA [1] को हल करता हूं। कई कारणों से जिन्हें लेख में माना जाता है, कार्यान्वयन का उपयोग सूचना के क्रिप्टोग्राफ़िक संरक्षण के लिए नहीं किया जा सकता है।

मुख्य पीढ़ी - खोज प्राइम्स

RSA असममित एन्क्रिप्शन एल्गोरिदम को संदर्भित करता है: यदि एन्क्रिप्शन के लिए एक सार्वजनिक कुंजी का उपयोग किया जाता है, तो डिक्रिप्शन के लिए एक निजी कुंजी का उपयोग किया जाता है, और इसके विपरीत। पहली संपत्ति किसी को भी निजी कुंजी के मालिक के पते के लिए एक सार्वजनिक कुंजी के साथ एक संदेश एन्क्रिप्ट करने की अनुमति देती है और इस तरह इसकी गोपनीयता सुनिश्चित करती है। दूसरी संपत्ति कुंजी मालिक को निजी हैश के साथ संदेश हैश को एन्क्रिप्ट करने की अनुमति देती है ताकि कोई भी एन्क्रिप्ट किए गए हैश को डिक्रिप्ट कर सके, संदेश हैश के साथ तुलना करें और निर्धारित करें कि क्या संदेश संशोधित किया गया है।

चाबियाँ बनाने में पहला कदम बेतरतीब ढंग से दो बड़े पर्याप्त primes p और q का चयन करना है। एक सकारात्मक पूर्णांक x को अभाज्य कहा जाता है यदि इसके दो अलग-अलग विभाजक हैं: 1 और x। संख्या के अन्य सभी भाजक खंड पर 2 से x के वर्गमूल पर स्थित हैं, हालांकि, यह इस खंड से संबंधित केवल सरल विभाजक गुणन के लिए जाँच करने के लिए पर्याप्त है।

  (परिभाषित) (प्राइम्स एन)
   (परिभाषित)
     (परिभाषित)
       (या अशक्त? विभाजक)
           (चलो ([भाजक (कार भाजक)))
                (या (> (* भाजक भाजक) n)
                    (और (<0 (शेष n (कार भाजक))) (iter (cdr भाजक)))))
       )
     (iter primes)
     )
   (परिभाषित करें)
     (cond 
       ((= में) primes)
       ((प्राइम? कैंडिडेट (रिवर्स प्राइम्स)) (iter (कंस कैंडिडेट प्राइम)) (+ i 1) (+ कैंडिडेट 1))
       (अन्य (पुनरावृत्त iimes (+ उम्मीदवार 1)))
       )
     )
   (iter ') (0 2)
   )
 (परिभाषित प्राइम्स (प्रिम्स 100))
 (परिभाषित पी (कार primes))
 (परिभाषित क्यू (कार 10 ड्रॉप)) 

पाए गए प्राइम का उत्पाद सार्वजनिक और निजी कुंजी का पहला तत्व है। उपरोक्त एल्गोरिथ्म आपको उचित समय में केवल पहले मिलियन प्राइम नंबर खोजने की अनुमति देता है। सूचना की सुरक्षा के लिए उपयोग किए जाने वाले आरएसए कार्यान्वयन में, अधिक अंक वाले अपराधों को खोजने के लिए प्रिम्स खोज एल्गोरिदम का उपयोग किया जाता है; इस तथ्य के कारण कि संख्याओं को प्रमुख कारकों में समाप्‍त करने के लिए सबसे अच्छा ज्ञात एल्गोरिदम अंकों की संख्या के घातांक के लिए आनुपातिक समय के लिए काम करता है, यह माना जाता है कि माना जाने वाला सार्वजनिक कुंजी तत्व [2] से कुछ युग्मों को पुनर्स्थापित करना असंभव है।

  (परिभाषित n (* pq)) 

प्रमुख पीढ़ी - म्युचुअल प्राइम सर्च

सार्वजनिक और निजी कुंजी के दूसरे तत्वों की गणना करने के लिए, फाई मूल्य का उपयोग किया जाता है, जो कि n पर गणना किए गए यूलर फ़ंक्शन [3] के बराबर है। एक्स का यूलर फ़ंक्शन प्राकृतिक संख्याओं की संख्या के बराबर है जो बड़े एक्स नहीं हैं और इसके साथ पारस्परिक रूप से सरल हैं। एन के लिए, यह मात्रा पी -1 और क्यू -1 के उत्पाद के बराबर होगी।

  (परिभाषित फाई (* - (पी १)) (- क्यू १))) 

सार्वजनिक कुंजी का दूसरा तत्व 1 से लेकर फाई तक की एक यादृच्छिक संख्या ई है, जो कि कोप्राइम फ़ाइम है। यह है, जैसे कि संख्याओं का सबसे बड़ा सामान्य भाजक 1 है।

  (परिभाषित करें (CoprimesLess n)
   (परिभाषित करें (पुन: संचयकर्ता उम्मीदवार)
     (cond
       ((= 1 उम्मीदवार) संचायक)
       ((= 1 (gcd n उम्मीदवार)) (iter (विपक्ष उम्मीदवार संचायक) - (उम्मीदवार 1))
       (और (पुनरावृत्ति संचयक - (उम्मीदवार 1)))
       )
     )
   (iter ') (- (एन 1))
   )
 (परिभाषित ई (कार 5 ड्रॉप (CoprimesLess फाई)))) 

सबसे बड़ा सामान्य कारक खोजने के लिए, आप यूक्लिडियन एल्गोरिथ्म का उपयोग कर सकते हैं [4]।

मुख्य पीढ़ी - कटौती की अंगूठी में संचालन

संख्या सिद्धांत द्वारा अध्ययन की गई वस्तुओं में से एक अवशेष अंगूठी है [5]। अवशिष्ट वलय modulo k, 0 से k-1 तक पूर्णांक और उस पर जोड़ और गुणा के संचालन हैं। अवशेषों की अंगूठी में जोड़ (a + b mod k) पूर्णांकों के समूह में जोड़ से भिन्न होता है यदि जोड़ परिणाम k से अधिक हो जाता है, तो k इसे से घटा दिया जाता है, जिसके परिणामस्वरूप यह परिणाम फिर से रिंग में होता है। सहज रूप से, एक रिंग को इसके सिरों को जोड़कर एक खंड से प्राप्त किया जाता है।

पूर्णांक के समूह के रूप में, अवशेषों की अंगूठी में गुणा जोड़कर और गुणन द्वारा घातांक निर्दिष्ट किया जा सकता है। पूर्णांकों के समूह में, परिणामी जोड़ और गुणन क्रियाओं में समरूपता होगी, अर्थात:
a + (b + c mod k) mod k = (a + b mod k) + c mod k
a * (b * c mod k) mod k = (a * b mod k) * c mod k

सार्वजनिक कुंजी का दूसरा तत्व एक संख्या d होना चाहिए जैसे कि अवशिष्ट वलय modulo n में e के साथ उसका उत्पाद 1 है, यानी गुणात्मक व्युत्क्रम तत्व। मैं विस्तारित यूक्लिडियन एल्गोरिथ्म [6] का उपयोग करके ऐसे तत्व के लिए खोज एल्गोरिथ्म लाता हूं।

  (परिभाषित करें (MultInverseModN)
   (परिभाषित करें (iter-a-prev a r-prev r)
     (अगर (> = 1 r) a (let * ([r-next (शेष r-prev r))
                           [क्ष (भागफल r-prev r)]
                           [a-next-(a-prev (* qa))]
                          (iter a-next r r-next)))
     )
   (दो ([परिणाम 0 1 na)]) (यदि (<0 परिणाम) परिणाम (+ n परिणाम))
 )
 (डी को परिभाषित करें (MultInverseModN e Fi)) 

एन्क्रिप्शन और डिक्रिप्शन

RSA एल्गोरिथ्म का उपयोग करके, आप 0 से n-1 तक की संख्या में M की श्रृंखला द्वारा दर्शाये गए संदेशों को एन्क्रिप्ट कर सकते हैं। एन्क्रिप्शन में M को पावर ई में रेजिंग रिंग मोडुलो n में बढ़ाने के लिए, डिक्रिप्शन टू पावर d है। इस तथ्य के कारण कि गुणन साहचर्य है, हम लॉग (x) संचालन [7] के लिए पावर x तक बढ़ा सकते हैं।

  (परिभाषित करें (PowerModN असामान्य)
   (परिभाषित करें (पुनरावृत्ति संचायक गुणक शक्ति)
     (यदि
       (= शक्ति ०)
       बिजली संचयक यंत्र
       (जाने
           ((new_accumulator (यदि (भी? शक्ति) संचायक) (शेष (* संचायक गुणक) n)))
           (iter new_accumulator (* गुणक गुणक) (भागफल शक्ति 2))
         )
       )
     )
   (iter 1 ab)
   ) 

टेस्ट केस

मेरे उदाहरण में, सार्वजनिक कुंजी एक जोड़ी (250483 31) है, निजी कुंजी एक जोड़ी है (250483 32191)। एन्क्रिप्टेड संदेश 123456 133240 है।

संदर्भ

1. en.wikipedia.org/wiki/RSA
2. en.wikipedia.org/wiki/Integer_factorization
3. en.wikipedia.org/wiki/Euler%27s_totient_function
4. en.wikipedia.org/wiki/Euclidean_algorithm
5. en.wikipedia.org/wiki/Modular_arithmetic
6. en.wikipedia.org/wiki/Extended_Euclidean_algorithm
7. en.wikipedia.org/wiki/Exponentiation_by_squaring