Google Answers Logo
View Question
 
Q: RSA Public Key Encryption ( No Answer,   2 Comments )
Question  
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.
Answer  
There is no answer at this time.

Comments  
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.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

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 Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy