Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question

closed as off-topic by Maarten Bodewes, e-sushi Jun 17 at 22:02

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

1  
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
1  
this is not about cryptography, CRC is a general purpose, non-cryptographic function – Maarten Bodewes Jun 17 at 21:43
up vote 2 down vote accepted

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)$.

share|improve this answer
1  
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
1  
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.

share|improve this answer
1  
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

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