Article View: sci.crypt
Article #1461Re: Polynomial Deduction
From: Bennet Yee
Date: Mon, 09 Nov 1992 22:14
Date: Mon, 09 Nov 1992 22:14
24 lines
1510 bytes
1510 bytes
In article <69133@cup.portal.com>, lordSnooty@cup.portal.com (Andrew - Palfreyman) writes:
>On reading a couple of texts on error-correcting codes, the
>following question occurred to me:
>
>What is an efficient method for deducing the checksum generating
>polynomial, given many examples of a block code with an appended checksum?
Let file_n considered as q_n(x), with checksum the residual r_n(x),
where for all n: q_n(x) mod p(x) = r_n(x), p the checksum generating
polynomial used.
Then for all n: p divides q_n - r_n. So p divides GCD_{i=1}^{n} q_i - r_i.
In particular, with high probability p = GCD_{i=1}^{n} q_i - r_i
(assuming random q's).
This shows that Karp-Rabin fingerprints can not be used to check
integrity when the privacy of the fingerprints (as well as the
irreducible[s] used) can not be guaranteed.
-bsy
--
Bennet S. Yee Phone: +1 412 268-7571 Email: bsy+@cs.cmu.edu
School of Computer Science, Carnegie Mellon, Pittsburgh, PA 15213-3890
Technical Details
Message-ID:
<BxGz3w.Jy6.2@cs.cmu.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!PLAY.TRUST.CS.CMU.EDU!bsyReferences:
<69133@cup.portal.com>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!PLAY.TRUST.CS.CMU.EDU!bsy From: bsy+@CS.CMU.EDU (Bennet Yee) Newsgroups: sci.crypt Subject: Re: Polynomial Deduction Message-ID: <BxGz3w.Jy6.2@cs.cmu.edu> Date: 9 Nov 92 22:14:13 GMT Article-I.D.: cs.BxGz3w.Jy6.2 References: <69133@cup.portal.com> Sender: news@cs.cmu.edu (Usenet News System) Reply-To: bsy+@cs.cmu.edu Organization: Cranberry Melon, School of Cucumber Science Lines: 24 Nntp-Posting-Host: play.trust.cs.cmu.edu