home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15087 < prev    next >
Encoding:
Text File  |  1992-11-17  |  1.6 KB  |  32 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!news.sei.cmu.edu!fs7.ece.cmu.edu!crabapple.srv.cs.cmu.edu!asp
  3. From: asp+@cs.cmu.edu (James Aspnes)
  4. Subject: Re: ok, i'll bite.
  5. Message-ID: <BxtvDG.Jr7.1@cs.cmu.edu>
  6. Sender: news@cs.cmu.edu (Usenet News System)
  7. Nntp-Posting-Host: mixo.soar.cs.cmu.edu
  8. Organization: School of Computer Science, Carnegie Mellon
  9. References: <92320.214859RVESTERM@vma.cc.nd.edu>
  10. Date: Mon, 16 Nov 1992 21:22:23 GMT
  11. Lines: 19
  12.  
  13. In article <92320.214859RVESTERM@vma.cc.nd.edu> RVESTERM@vma.cc.nd.edu writes:
  14. >i understand "cryptography".  i understand "np".  someone please
  15. >explain the connection.
  16.  
  17. If you can solve any problem in NP, and you have a polynomial-time test for
  18. whether a string could be a message, you can decrypt messages encrypted with
  19. any efficient (small keys, small description of algorithm, algorithm is fast)
  20. algorithm as follows:
  21.  
  22.  1. Guess the key and the algorithm (this is where non-determinism comes in).
  23.  2. Decrypt the message according to the key/algorithm you have guessed.
  24.  3. Test to see if the result is a plausible message.
  25.  
  26. The only tricky part is the test for plausibility, since you don't want it to
  27. answer yes too often.  For public-key systems the test is straightforward; you
  28. encrypt the alleged decryption using the public key and see if it matches.
  29. For private-key systems you have to know something about the space of possible
  30. messages (e.g. that they are ASCII English-language text followed by a 64-bit
  31. CRC checksum :-]), but in practice this shouldn't be much of a problem.
  32.