home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / crypt / 4513 < prev    next >
Encoding:
Internet Message Format  |  1992-11-09  |  1.4 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!PLAY.TRUST.CS.CMU.EDU!bsy
  2. From: bsy+@CS.CMU.EDU (Bennet Yee)
  3. Newsgroups: sci.crypt
  4. Subject: Re: Polynomial Deduction
  5. Message-ID: <BxGz3w.Jy6.2@cs.cmu.edu>
  6. Date: 9 Nov 92 22:14:13 GMT
  7. Article-I.D.: cs.BxGz3w.Jy6.2
  8. References: <69133@cup.portal.com>
  9. Sender: news@cs.cmu.edu (Usenet News System)
  10. Reply-To: bsy+@cs.cmu.edu
  11. Organization: Cranberry Melon, School of Cucumber Science
  12. Lines: 24
  13. Nntp-Posting-Host: play.trust.cs.cmu.edu
  14.  
  15. In article <69133@cup.portal.com>, lordSnooty@cup.portal.com (Andrew - Palfreyman) writes:
  16. >On reading a couple of texts on error-correcting codes, the
  17. >following question occurred to me:
  18. >
  19. >What is an efficient method for deducing the checksum generating
  20. >polynomial, given many examples of a block code with an appended checksum?
  21.  
  22. Let file_n considered as q_n(x), with checksum the residual r_n(x),
  23. where for all n: q_n(x) mod p(x) = r_n(x), p the checksum generating
  24. polynomial used.
  25.  
  26. Then for all n: p divides q_n - r_n.  So p divides GCD_{i=1}^{n} q_i - r_i.
  27.  In particular, with high probability p = GCD_{i=1}^{n} q_i - r_i
  28. (assuming random q's).
  29.  
  30. This shows that Karp-Rabin fingerprints can not be used to check
  31. integrity when the privacy of the fingerprints (as well as the
  32. irreducible[s] used) can not be guaranteed.
  33.  
  34. -bsy
  35.  
  36. -- 
  37. Bennet S. Yee        Phone: +1 412 268-7571        Email: bsy+@cs.cmu.edu
  38. School of Computer Science, Carnegie Mellon, Pittsburgh, PA 15213-3890
  39.