home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5817 < prev    next >
Encoding:
Internet Message Format  |  1992-12-18  |  2.8 KB
  1. Xref: sparky sci.crypt:5817 alt.security.pgp:259
  2. Newsgroups: sci.crypt,alt.security.pgp
  3. Path: sparky!uunet!newsflash.concordia.ca!nstn.ns.ca!newton.ccs.tuns.ca!johnsomr
  4. From: johnsomr@newton.ccs.tuns.ca (Mark R Johnson)
  5. Subject: Re: RSA Question (was Re: PKP/RSA comments on PGP legality)
  6. Summary: answer is 27
  7. Message-ID: <1992Dec18.001213.8000@newton.ccs.tuns.ca>
  8. Date: Fri, 18 Dec 1992 00:12:13 GMT
  9. References: <1992Dec14.190615.13954@macc.wisc.edu> <PHR.92Dec16022546@napa.telebit.com> <r09LrAXKBh107h@nadir.uucp>
  10. Organization: Technical University of Nova Scotia, Halifax, N.S.
  11. Lines: 63
  12.  
  13. In article <r09LrAXKBh107h@nadir.uucp> you write:
  14. >In <PHR.92Dec16022546@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
  15. >>    Please excuse my ignorance, but, how can "your wife" decode the message
  16. >>    knowing 34, 91, 7, and 13?
  17. >
  18. >>    i.e. I have a number
  19. >>      (X^3) moulo 77 (product of two primes) = 48
  20. >>    what is my number? and how did you get the answer?
  21. >
  22. >[Stuff Deleted]
  23. >
  24. >>In the case of N=77 and N=91, phi(N) is a multiple of 3 so no
  25. >>suitable t exists.  You have to have picked your original primes
  26. >>p and q to make this not happen.
  27. >
  28. >O.K., now that you've excused my ignorance, I beg you excuse my stupidity.
  29. >
  30. >Same number  X^3(mod, 391) = 133
  31. >(phi(N) is not divisible by 3) What is my number?
  32. >
  33. 27.
  34.  
  35. >I tried to figure out t, but got stumped.
  36.  
  37. t is 235.  Other larger numbers like 587 will also work.
  38. The method is explained in Rivest et al, "A Method for Obtaining Digital
  39. Signatures and Public-Key Cryptosystems," Communications of the ACM,
  40. vol 21, no 2, Feb 1978, pp120ff.
  41. Section VII d and VIII are the most relevant.
  42.  
  43. Now, that we have gcd(PHI(n), d) = 1, e must be calculated.  This is
  44. done by calculating a series x0, x1, .... with x0 = PHI(n), and x1 = d
  45. (ie 3), and x(i+1) = x(i-1) (mod xi).  For each xi, a pair of numbers ai and
  46. bi must be found that satisfy:
  47. ai*x0 + bi*x1 = xi.
  48. As far as I know the most efficient way to solve this is to try different
  49. values for a until you get a positive integer for b.
  50. My numbers:
  51.     x   a   b
  52. 0  352  1   0
  53. 1    3  0   1
  54. 2    1 -2  235
  55.  
  56. >Thanks again,
  57.  
  58. I hope this helps.
  59.  
  60. >Rudy Crespin
  61. >
  62. >--
  63. >                                                      _           _
  64. >   ---   O       | Rudy Crespin                    | / \ |\ | __ / \ |\ |
  65. >   --   <^-      | crespin@nadir.uucp              | \_/ | \|    \_/ | \|
  66. >  --  -\/\       | crash!nadir!crespin             |
  67. >  ---     \      |                                 |- No-No, it is On-On.
  68.  
  69. --
  70. ;---------------------------------------------------------------------
  71. ; Mark Johnson             ; msdos has 6 types of RAM - dos ram,
  72. ; My views are my own and  ; upper memory, high memory, extended memory,
  73. ; nobody else's.           ; expanded memory, and video ram.
  74. ;                          ; YUCKKK!!!!!!!!!!!
  75. ;---------------------------------------------------------------------
  76.