आरएसए की गणना डी

Question

यह सुनिश्चित नहीं है कि क्रिप्टोग्राफी प्रश्न पूछने के लिए यह सही जगह है, लेकिन यहां जाता है।

मैं आरएसए में "डी" काम करने की कोशिश कर रहा हूं, मैंने पी, क्यू, ई, एन और ओएनएन का काम किया है; होगा एक उदाहरण:

p = 79, q = 113, e = 2621 

n = pq     øn = (p-1)(q-1) 
n = 79 x 113 = 8927  øn = 78 x 112 = 8736 

e = 2621 
d = 

मैं नहीं कर सकते घ खोजने के लिए लगता है, मुझे पता है कि घ कि एक मूल्य करने के लिए है .. एड आधुनिक ø (एन) = 1. किसी भी मदद की सराहना की होगी

संपादित करें ई = 17, डी = 2753, पर = 3120

17 * 2753 आधुनिक 3120 = 1

Answer 1

आप की ई (आधुनिक n) मॉड्यूलर उलटा है, जो बढ़ाया इयूक्लिडियन कलन विधि का उपयोग की जा सकती है के लिए देख रहे हैं:

function inverse(x, m) 
    a, b, u := 0, m, 1 
    while x > 0 
     q := b // x # integer division 
     x, a, b, u := b % x, u, x, a - q * u 
    if b == 1 return a % m 
    error "must be coprime" 

इस प्रकार, अपने उदाहरण में, inverse(17, 3120) = 2753 और inverse(2621, 8736) = 4373. यदि आप एल्गोरिदम लागू नहीं करना चाहते हैं, तो आप उत्तर के लिए Wolfram|Alpha से पूछ सकते हैं।

Answer 2

एल्गोरिथ्म आप की जरूरत Extended Euclidean Algorithm है। यह आपको Bézout की पहचान का गुणांक जिसमें कहा गया है कि किसी भी दो गैर शून्य पूर्णांकों a और b के लिए, वहाँ पूर्णांकों x और y ऐसे हैं जो अस्तित्व में गणना करने के लिए अनुमति देता है:

ax + by = gcd(a,b) 

यह तुरंत उपयोगी नहीं लग सकता है, लेकिन हम जानते हैं कि e और φ(n) coprime हैं, gcd(e,φ(n)) = 1। तो एल्गोरिथ्म हमें देता है x और y ऐसी है कि:

ex + φ(n)y = gcd(e,φ(n)) 
      = 1 
Re-arrange: 
ex = -φ(n)y + 1 

यह ex mod φ(n) = 1 कहा, तो x = d के बराबर है।

Answer 3

उदाहरण के लिए आप अगले में घ प्राप्त करने की आवश्यकता:
3 * घ = 1 (आधुनिक 9167368)

इस समान रूप से है:
3 * घ = 1 + K * 9,167,368, जहां कश्मीर = 1, 2, 3, ...

यह रीराइट:
घ = (1 + K * 9167368)/3

आपका डी सबसे कम के साथ पूर्णांक होना चाहिए।
के सूत्र लिखते हैं:
घ = (1 + K * फाई)/ई

public static int MultiplicativeInverse(int e, int fi) 
     { 
      double result; 
      int k = 1; 
      while (true) 
      { 
       result = (1 + (k * fi))/(double) e; 
       if ((Math.Round(result, 5) % 1) == 0) //integer 
       { 
        return (int)result; 
       } 
       else 
       { 
        k++; 
       } 
      } 
     } 

आइए परीक्षण इस कोड:

Assert.AreEqual(Helper.MultiplicativeInverse(3, 9167368), 6111579); // passed