home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / crypt / 4600 < prev    next >
Encoding:
Internet Message Format  |  1992-11-11  |  2.3 KB
  1. Path: sparky!uunet!think.com!rpi!bu.edu!transfer.stratus.com!ellisun.sw.stratus.com!cme
  2. From: cme@ellisun.sw.stratus.com (Carl Ellison)
  3. Newsgroups: sci.crypt
  4. Subject: Re: pseudo one time pad...
  5. Message-ID: <1drkb1INNk6f@transfer.stratus.com>
  6. Date: 11 Nov 92 18:44:49 GMT
  7. References: <1992Nov11.173642.29608@ee.eng.ohio-state.edu>
  8. Organization: Stratus Computer, Software Engineering
  9. Lines: 45
  10. NNTP-Posting-Host: ellisun.sw.stratus.com
  11.  
  12. In article <1992Nov11.173642.29608@ee.eng.ohio-state.edu> butzerd@columbia.eng.ohio-state.edu (Dane C. Butzer) writes:
  13. >  "Random number generators" are
  14. >  frequently dreamed up by newcomers as a "pseudo one time pad",
  15. >  but they are notoriously vulnerable to analysis, all
  16. >               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  17. >  independent of whether the pseudo-random stream satisfies
  18. >  randomness tests or not.
  19. >
  20.     [example of DES as a PRNG]
  21.  
  22. >This is pseudo one time pad that I don't think would be "easy" to break.
  23. >Now, how about substituting some other type of PRNG for DES?  If its
  24. >non-predictive (can't determine numbers in the stream from other numbers)
  25. >and statistically random, whouldn't it work?  Is the real problem coming up
  26. >with a "good" enough PRNG?
  27.  
  28. Of course, if you use a cryptographically strong PRNG, it's as good as a
  29. 1-time-pad.  That's the definition of cryptographic strength -- that the
  30. PRNG is indistinguishable by any polynomial time&space test from true
  31. random numbers.
  32.  
  33. The FAQ was warning against use of standard, canned PRNGs (e.g.,
  34.  
  35.     x' = a*x+b mod N
  36.  
  37. ) as the generator.
  38.  
  39. BTW, Ron Rivest published a secure PRNG method in an early Cryptologia.  As
  40. I remember it, he used
  41.  
  42.     x' = x^2 mod N
  43.  
  44. taking one bit from each iteration.  If you know x at any time, you can go
  45. forward trivially -- but because sqrt() is multi-valued, you can't go
  46. backwards.  So, he then used TWO such bit streams -- one forward through
  47. the message and one backward.  He XORed the message text with both streams.
  48.  
  49. [I assume you have to use large numbers N and x0 -- to avoid finally getting
  50. to the value x=1 and having the generator be no good any more.]
  51.  
  52. -- 
  53. -- <<Disclaimer: All opinions expressed are my own, of course.>>
  54. -- Carl Ellison                        cme@sw.stratus.com
  55. -- Stratus Computer Inc.    M3-2-BKW        TEL: (508)460-2783
  56. -- 55 Fairbanks Boulevard ; Marlborough MA 01752-1298    FAX: (508)624-7488
  57.