Question:
In the RSA public-key cryptosystem, if primes \(p = 7\) and \(q = 11\) are chosen with public encryption exponent \(e = 13\), what is the private decryption key \(d\)?
RSA पब्लिक-की क्रिप्टोसिस्टम में, यदि अभाज्य संख्याएं \(p = 7\) और \(q = 11\) तथा पब्लिक एक्सपोनेंट \(e = 13\) चुनी जाती हैं, तो प्राइवेट की \(d\) क्या होगी?
Options:
- 37
- 43
- 17
- 29
- 37
- 43
- 17
- 29
Correct Answer: a)
Explanation:
1. Modulus \(n = p \times q = 7 \times 11 = 77\).
2. Euler’s totient \(\phi(n) = (p-1)(q-1) = 6 \times 10 = 60\).
3. Compute \(d \equiv e^{-1} \pmod{\phi(n)} \implies 13d \equiv 1 \pmod{60}\).
Using Extended Euclidean Algorithm:
\(60 = 13 \times 4 + 8\)
\(13 = 8 \times 1 + 5\)
\(8 = 5 \times 1 + 3\)
\(5 = 3 \times 1 + 2\)
\(3 = 2 \times 1 + 1\).
Testing \(13 \times 37 = 481 = 60 \times 8 + 1 \equiv 1 \pmod{60}\).
Therefore, \(d = 37\).
2. Euler’s totient \(\phi(n) = (p-1)(q-1) = 6 \times 10 = 60\).
3. Compute \(d \equiv e^{-1} \pmod{\phi(n)} \implies 13d \equiv 1 \pmod{60}\).
Using Extended Euclidean Algorithm:
\(60 = 13 \times 4 + 8\)
\(13 = 8 \times 1 + 5\)
\(8 = 5 \times 1 + 3\)
\(5 = 3 \times 1 + 2\)
\(3 = 2 \times 1 + 1\).
Testing \(13 \times 37 = 481 = 60 \times 8 + 1 \equiv 1 \pmod{60}\).
Therefore, \(d = 37\).
\(\phi(n) = (7-1)(11-1) = 60\)। \(13d \equiv 1 \pmod{60}\) को हल करने पर: \(13 \times 37 = 481 = 8 \times 60 + 1\), अतः \(d = 37\)।