# Reversing N CRC steps

Starting from a known CRC result(let's call it CRC1), could I undo the CRC operations for last N bits, so I could obtain the CRC (let's call it CRC2) of the message sequence without the last N bits. $$M(x) - message \\ M = \{M1,LastBits\} \\CRC_1=CRC\{M\}\\CRC_2=CRC\{M_1\}$$ Does a function F() exist for which: $$F(CRC_1,LastBits) = CRC_2$$

My hunch would be that such a function which would unrewind the last N CRC steps, would have 2N possible solutions.

-
Welcome to Crypto.SE! In the future do not cross-post questions to multiple Stack Exchange sites like you did in this case by posting the same questions to Math.SE. If (after a period) you feel that a different Stack Exchange site is better suited to your question, flag it for moderator attention, stating which other SE site you feel it would be more suitable for. A moderator will then look into migrating the question for you. Having the same question asked on multiple SE sites only increases the chances of duplicated (and redundant) effort. –  e-sushi Oct 7 '13 at 9:57

This is easiest to understand if we use polynomial arithmetic.

The CRC of a message $m(x)$ is the remainder $r(x)$ of $m(x) x^k$ when divided by the CRC polynomial $f(x)$. Or more conveniently, the CRC is congruent to the message multiplied by $x^k$ modulo the CRC polynomial, $r(x) \equiv m(x) x^k \pmod{f(x)}$.

If the message consists of a prefix $m_1$ and a suffix $m_2$ of length $n$, we can express that as $m(x) = m_1(x) x^n + m_2(x)$. If the CRC of $m_1$ is $r_1(x)$ and the CRC of $m_2(x)$ is $r_2(x)$, then the CRC of $m(x)$ is $$r(x) \equiv (m_1(x) x^n + m_2(x)) x^k \equiv r_1(x) x^n + r_2(x) \pmod{f(x)}.$$

If $f(x)$ is not a multiple of $x$ (which it won't be), there is a polynomial $g(x)$ such that $x g(x) \equiv 1 \pmod{f(x)}$, and then $$r_1(x) \equiv r_1(x) (x g(x))^n \equiv (r(x) - r_2(x)) g(x)^n \equiv (r(x) - m_2(x) x^k) g(x)^n \pmod{f(x)}.$$

In other words, you find what you ask for by first finding $g(x)$, then computing a difference, multiplying by a suitable power of $g(x)$, then taking the remainder when dividing by $f(x)$.

-
Thank you for your answer. Unfortunately my algebra is a very rusty. Do you know by what means I could find g(x)? If f(x) = 1 + x^t1 + x^t2 + .. +x^tk, then g(x) = x^(t1-1) + x^(t2-1) + .... + x^(tk-1). Is my reasoning correct? –  TwoSan Oct 6 '13 at 16:15
Correct. In general, you use the extended Euclidian algorithm. –  K.G. Oct 6 '13 at 19:59

For common CRC functions your function F exists as its inverse is essentially the way that CRCs of long streams of data are calculated without having to store significantly more than the value of the CRC. The existence of a unique inverse is a side-effect of some of the desirable guarantees provided by common CRC functions.

In your terminology, given a plausible CRC function for nearly every CRC1 and LastBits there will be a unique CRC2 which is the CRC of a string of bits which, when LastBits is appended yields a CRC of CRC1.

For some CRC functions there may be some edge cases involving CRCs of zero and LastBits of zero.

-
Thank you for your explanation. I have chosen @k-g 's answer as a solution as it is more thorough, but I also appreciate your answer. –  TwoSan Oct 6 '13 at 15:04
I understand. Thanks. K.G can be justifiably proud of his answer. I would caution that I have encountered functions used as CRCs in some applications which do not behave exactly K.G describes. –  Barack Obama Oct 6 '13 at 22:02