home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / crypt / 4521 < prev    next >
Encoding:
Text File  |  1992-11-09  |  1.6 KB  |  38 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!mnemosyne.cs.du.edu!nyx!cplumb
  3. From: cplumb@nyx.cs.du.edu (Colin Plumb)
  4. Subject: Re: Polynomial Deduction
  5. Message-ID: <1992Nov10.064307.21388@mnemosyne.cs.du.edu>
  6. X-Disclaimer: Nyx's hardware; my words.
  7. Sender: usenet@mnemosyne.cs.du.edu (netnews admin account)
  8. Organization: Nyx, Public Access Unix at U. of Denver Math/CS dept.
  9. References: <69133@cup.portal.com>
  10. Date: Tue, 10 Nov 92 06:43:07 GMT
  11. Lines: 25
  12.  
  13. In article <69133@cup.portal.com> lordSnooty@cup.portal.com (Andrew - Palfreyman) writes:
  14. > On reading a couple of texts on error-correcting codes, the
  15. > following question occurred to me:
  16. > 
  17. > What is an efficient method for deducing the checksum generating
  18. > polynomial, given many examples of a block code with an appended checksum?
  19.  
  20. The simplest application of an error-checking polynomial (mapping other
  21. cases, like preset to all 1's as in FDDI, to this is simple) is that
  22. the valid messages are all multiples of some check polynomial c(x).
  23. Given a number of message polynomials, m_i(x), their GCD will contain
  24. c(x) as a factor, and if there are enough, there will probably be no
  25. other factors.
  26.  
  27. It is not too difficult to extend this to handle a small number of
  28. erroneous messages, by taking various subsets and applying sanity checks
  29. to the GCD's to find the erroneous ones.
  30.  
  31. In summary, it's not a hard problem.  I can also deduce unknown (but
  32. constant) preset strings by subtracting messages to cancel the constant
  33. leading parts and applying this algorithm to the differences.  I can't
  34. think of a difficult variation.  CRC's have *lots* of exploitable
  35. mathematical structure to use in analysis.
  36. -- 
  37.     -Colin
  38.