2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – e-sushi
    Oct 7, 2013 at 9:57
  • 1
    $\begingroup$ this is not about cryptography, CRC is a general purpose, non-cryptographic function $\endgroup$
    – Maarten Bodewes
    Jun 17, 2016 at 21:43

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – TwoSan
    Oct 6, 2013 at 16:15
  • 1
    $\begingroup$ Correct. In general, you use the extended Euclidian algorithm. $\endgroup$
    – K.G.
    Oct 6, 2013 at 19:59
1
$\begingroup$

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.

$\endgroup$
0

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