![]() |
|
![]() | ||
|
Subject:
RSA Public Key Encryption
Category: Reference, Education and News > Homework Help Asked by: siball-ga List Price: $10.00 |
Posted:
23 Oct 2005 14:00 PDT
Expires: 24 Oct 2005 13:44 PDT Question ID: 583922 |
In an RSA system, the public key of a given user is e = 31, n = 3599. What is the private key of this user? I have the answer: 3031. I am just not sure how it is calculated. |
![]() | ||
|
There is no answer at this time. |
![]() | ||
|
Subject:
Re: RSA Public Key Encryption
From: manuka-ga on 24 Oct 2005 00:44 PDT |
The first step is to factor 3599 into its component primes. Since we're dealing with a small number this is not too hard (and indeed note that 3599 = 60^2 - 1, so the factors are 60 - 1 and 60 + 1, i.e. 59 and 61). Then compute (p-1)(q-1) = 58.60 = 3480. Now the decryption key d satisfies d.e = 1 (mod 3480), i.e. 31 d = 1 (mod 3480). Now we use Euler's algorithm to express 1 as an integer combination of 31 and 3480: 3480 = 112(31) + 8 31 = 3(8) + 7 8 = 1(7) + 1 therefore 1 = 8 - 7 = 8 - (31 - 3(8)) = 4(8) - 31 = 4(3480 - 112(31)) - 31 = 4(3480) - 449(31) This gives us: 31 d = 4(3480) - 449(31) (mod 3480) = 31 (-449) (mod 3480) Since 31 is prime we can divide to get d = -449 (mod 3480) and adding 3480 to bring it into the canonical range gives us d = 3031. |
Subject:
Re: RSA Public Key Encryption
From: siball-ga on 24 Oct 2005 13:43 PDT |
Thank you very much manuka. Your help is greatly appreciated. |
If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you. |
Search Google Answers for |
Google Home - Answers FAQ - Terms of Service - Privacy Policy |