CRC32 operations question

[nesrocks]

So, what I'm trying to do, is to edit a ROM while keeping its CRC32 hash. There is a known sequence of 4 bytes of value "zero" at one section in the ROM that can be reserved for this.
What I want to do is edit the ROM using a level editor (that I'm making), and then the level editor will manipulate these zeroes in such a manner that the ROM's CRC32 hash will be unchanged.

I have found some resources online that tell me how to achieve this, in certain detail, and I've managed to reproduce it mostly in my development environment, but there's one step that I'm having trouble with understanding the math. The user describes the step as follows:

"Step four, and this is a bit funky so see below, perform an inverse CRC32 calculation:"

Code: Select all

0xD046655F * inverse(x32) mod crc_poly

It all boils down to what is "inverse(x32)". If I figure this out, my problem is solved.

He goes on further to explain this:
"P * x32 mod crc_poly is the remainder of (P shifted 32 bits to the right) after dividing by the CRC polynomial, which is how CRCs are computed).
inverse(x32) is the multiplicative inverse of x32 mod crc_poly. Multiplicative inverse means x32 * inverse(x32) mod crc_poly = 1."

The way I understand it, after going through steps 1-3, I will have to bitshift the manipulated hash 32 bits to the right, but that means it will always result in a value of zero since it is always 32 bits long? I am missing something here and I'd really appreciate some help.

Maybe he meant bit shift 32x to the left?

First link to his explanations: https://stackoverflow.com/questions/482 ... 0#48248530
Further info: https://www.reddit.com/r/crypto/comment ... ollisions/

[pubby]

My best guess is that inverse(x32) is a constant value that is determined by the CRC polynomial. You can precompute it outside of your code and copy/paste it in.

The multiplication is finite field multiplication, not standard arithmetic.

This is only a guess though.

[nesrocks]

This issue has been solved. Inverse(x32) for the CRC32 with default polynomial is just a constant $cbf1acda. (thanks zzdd from RHDN!) http://www.romhacking.net/forum/index.p ... 382134#new