home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5727 < prev    next >
Encoding:
Internet Message Format  |  1992-12-16  |  1.8 KB
  1. Xref: sparky sci.crypt:5727 alt.security.pgp:201
  2. Newsgroups: sci.crypt,alt.security.pgp
  3. Path: sparky!uunet!telebit!phr
  4. From: phr@telebit.com (Paul Rubin)
  5. Subject: Re: RSA Question (was Re: PKP/RSA comments on PGP legality)
  6. In-Reply-To: crespin@nadir.uucp's message of Tue, 15 Dec 92 21:50:21 -0800
  7. Message-ID: <PHR.92Dec16022546@napa.telebit.com>
  8. Sender: news@telebit.com
  9. Nntp-Posting-Host: napa.telebit.com
  10. Organization: Telebit Corporation; Sunnyvale, CA, USA
  11. References: <1992Dec14.190615.13954@macc.wisc.edu> <dOsLrAnGBh107h@nadir.uucp>
  12. Date: 16 Dec 92 02:25:46
  13. Lines: 28
  14.  
  15.     >    For the record I am going to publish a number I
  16.     >    want to keep secret.  I am going to raise it to the power of
  17.     >    three modulo 91 which is the product of two primes.  The
  18.     >    result is 34.  My wife knows the factors of 91 and will be able
  19.     >    to decode this message.  
  20.  
  21.     Please excuse my ignorance, but, how can "your wife" decode the message
  22.     knowing 34, 91, 7, and 13?
  23.  
  24.     i.e. I have a number
  25.       (X^3) moulo 77 (product of two primes) = 48
  26.     what is my number? and how did you get the answer?
  27.  
  28.  
  29. Generally, given x^3 mod N = y, knowing the factors N = pq,
  30. recover x by the following:
  31.   1. Compute phi(N) = (p-1)(q-1).  For number theorists, this is
  32.      the number of elements of Z^*_N, the (multiplicative mod N) group
  33.      of integers relatively prime to N.
  34.   2. Use the Extended Euclidean Algorithm (see Knuth vol. 2, etc.)
  35.      to compute t, so that 3t == 1, mod phi(N).  This means that
  36.      x^(3t) mod N will be equal to x.
  37.      This is because x^(phi(N)) mod N == 1, from Lagrange's theorem.
  38.   3. Now to decrypt y, simply compute x = y^t mod N.
  39.  
  40. In the case of N=77 and N=91, phi(N) is a multiple of 3 so no
  41. suitable t exists.  You have to have picked your original primes
  42. p and q to make this not happen.
  43.