I asked this on StackOverflow, but, alas, no answers.

I'd like to use CRC or similar codes to check whether certain very large objects are likely to be identical. The trouble is, small parts of these objects are sometimes modified, and it would be very inefficient to re-compute CRC code from the entire object. Think of multiple large images, pre-signed with CRC, and of a software the changes single pixels of some of those images and updating those images' CRCs.

Is it possible to re-compute CRC based on: previous CRC value, location of the changed byte, old value of that byte, and the new value of that byte?

If not, what signature scheme would allow that?


Yes, this is possible. The new CRC value can be computed very efficiently.

To see how, you need to know some math and about how CRCs can be viewed as polynomials. The CRC checksum of the bit-string $c_0,\dots,c_n$ can be viewed as the value of $c(x) \bmod p(x)$, where $p(x)$ is the CRC polynomial and $c(x) = c_n x^n + \dots + c_0$ and all arithmetic is done modulo 2. Let $r(x)$ denote the checksum, i.e., $c(x) \bmod p(x)$. Now if you change the $i$th bit $c_i$ to $c'_i$, then the new checksum will be given by $c'(x) \pmod p(x)$ where we define the polynomial $c'(x) = c(x) - c_i x^i + c'_i x^i$. The checksum will be $c'(x) \bmod p(x)$, which has the form

$$c'(x) \equiv c(x) - c_i x^i + c'_i x^i \equiv r(x) + (c'_i-c_i) x^i \pmod{p(x)}$$

Since we already know $r(x)$ (it's the checksum of the original file), all we need is to compute the value of $(c'_i-c_i) x^i \bmod p(x)$. Naively, you might think this takes $O(i)$ time -- potentially slow. But in fact this can be done very efficiently using fast modular exponentiation, so we compute $x^i \pmod p(x)$, then multiply by $c'_i-c_i$, and we get $(c'_i-c_i) x^i \bmod p(x)$. Then we add that to the original checksum $r(x)$. (All arithmetic is done modulo 2, so here "addition" really means xor.) That gives us the new checksum for the modified file.

If the modification changes multiple bits, there is a natural extension of the move to show how to compute the updated checksum as well.

| cite | improve this answer | |
  • 1
    $\begingroup$ Bit strings for CRC are usually most significant bit first, $$c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + ... + c_{0}$$ Within a group of bits, such as a byte, the CRC may be a left or right shifting CRC. $\endgroup$ – rcgldr May 24 '18 at 19:53
  • $\begingroup$ If n is not too large, then a table of values for x^i mod p for i = 1 to n could be pre-generated reducing time complexity to O(1). $\endgroup$ – rcgldr Apr 4 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.