home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14783 < prev    next >
Encoding:
Text File  |  1992-11-11  |  2.8 KB  |  66 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!pipex!pavo.csi.cam.ac.uk!gjm11
  3. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  4. Subject: Re: HELP on RSA scheme for Encryption/Decryption
  5. Message-ID: <1992Nov11.170156.307@infodev.cam.ac.uk>
  6. Sender: news@infodev.cam.ac.uk (USENET news)
  7. Nntp-Posting-Host: bootes.cus.cam.ac.uk
  8. Organization: U of Cambridge, England
  9. References: <6605@dciem.dciem.dnd.ca>
  10. Distribution: na
  11. Date: Wed, 11 Nov 1992 17:01:56 GMT
  12. Lines: 52
  13.  
  14. In article <6605@dciem.dciem.dnd.ca> jorchard@dretor.dciem.dnd.ca writes:
  15.  
  16. > I would like to know the algorithm for encrypting/decrypting codes
  17. > with the RSA scheme.  I took it in first year algebra, but I sold my
  18. > textbook and can't remember for the life of me how it went.
  19. >
  20. > Could someone out there with better resources (or better memory)
  21. > help me?
  22.  
  23. Surely.
  24.  
  25. Everyone who wants to be sent messages using the RSA scheme picks two
  26. large prime numbers, say p and q, and multiplies them together to give
  27. a number n=pq.
  28. He also picks a number d coprime to phi(n)=(p-1)(q-1).
  29. He computes another number e, which has the property: de congruent 1 mod phi(n)
  30. He makes public the numbers n and e.
  31. He keeps private the numbers p and q; also phi(n) [as given pq and (p-1)(q-1)
  32. one can find p and q by solving a quadratic equation]; also d [for reasons
  33. which will become clear].
  34.  
  35. Now, the first important fact you need to know is that any number coprime to n
  36. has a^phi(n) congruent to 1 mod n.
  37.  
  38. So, if someone wants to send this guy a message, she does this: encode the
  39. message in some standard way as a sequence of numbers less than n and coprime
  40. to n. Then for each such number a, compute a^e mod n; the resulting sequence
  41. is the encrypted message.
  42.  
  43. To decrypt this, suppose b is one of the numbers produced; then compute b^d
  44. mod n; this is a^(de), which is a^(something times phi(n) plus 1), which is
  45. a^(something times phi(n)) times a, which is a. [All this is done modulo n.]
  46.  
  47. This is why we can't make d public, of course: it would enable everyone to
  48. decrypt messages.
  49.  
  50. Now, how secure is this? Well, basically the only way to crack it is to factor
  51. n; that is, to find p and q. It is thought (though not proved) that it is hard
  52. to factorise numbers; that is, that provided some precautions are taken in
  53. choosing p and q there is no quick way to find what the factors of pq are.
  54.  
  55. Precautions include: not having p,q too close together; making sure p-1 and q-1
  56. don't have any really small factors; probably lots of other things I can't
  57. think of offhand.
  58.  
  59. I hope this is of some use. If I've assumed you know more mathematics than you
  60. actually do, send me some e-mail or something and I can explain what the words
  61. mean...
  62.  
  63. -- 
  64. Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
  65. gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
  66.