home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5689 < prev    next >
Encoding:
Text File  |  1992-12-14  |  1.3 KB  |  34 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!telebit!phr
  3. From: phr@telebit.com (Paul Rubin)
  4. Subject: Re: RSA questions
  5. In-Reply-To: tsa@cellar.org's message of 15 Dec 92 00:47:07 GMT
  6. Message-ID: <PHR.92Dec14202839@napa.telebit.com>
  7. Sender: news@telebit.com
  8. Nntp-Posting-Host: napa.telebit.com
  9. Organization: Telebit Corporation; Sunnyvale, CA, USA
  10. References: <9cTsVB4w164w@cellar.org>
  11. Date: 14 Dec 92 20:28:39
  12. Lines: 20
  13.  
  14.     I read the article in popular mechanics and have a few questions
  15.     about how RSA works.  You take the ASCII value of the number,
  16.     raise it to an arbitrary high power, and mod it by the public key,
  17.     correct?  But how do you decrypt it?
  18.  
  19. The message "x" is just a number, not an ascii value.
  20.  
  21. RSA works like this:
  22. 1. Pick two large primes p and q (with certain extra properties). Let N=pq.
  23. 2. Pick random exponent s.  The pair (N, s) will be the public key.
  24. 3. Compute secret key t, so that st = 1 mod (p-1)(q-1).  You can do
  25.    this efficiently if you know p and q, but it is intractable otherwise.
  26. 4. To encrypt: E(x) = x^s mod N.
  27. 5. To decrypt: D(y) = y^t mod N.
  28.  
  29. From number theory, it turns out that x^st mod N is just x.
  30. (This is because st = 1 mod phi(N), where phi(N) is the Euler
  31. totient function, equal to (p-1)(q-1) when N=pq.)
  32.  
  33. Thus, D(E(x)) = x.
  34.