Exetools  

Go Back   Exetools > General > General Discussion

Notices

Reply
 
Thread Tools Display Modes
  #1  
Old 03-24-2016, 05:00
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
CRC Polynomial

I understand that the CRC is calculated by dividing the message by the CRC polynomial, and the checksum is the remainder of this division.

My question is, if the polynomial is, for example:

x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

Then why would my checksum ever have the top 5 bits set, because surely the remainder must be strictly less than the modulus?
Reply With Quote
  #2  
Old 03-24-2016, 17:55
Kerlingen Kerlingen is offline
VIP
 
Join Date: Feb 2011
Posts: 324
Rept. Given: 0
Rept. Rcvd 276 Times in 98 Posts
Thanks Given: 0
Thanks Rcvd at 308 Times in 95 Posts
Kerlingen Reputation: 200-299 Kerlingen Reputation: 200-299 Kerlingen Reputation: 200-299
CRC polynominals have always the highest degree (bit) set.

The full CRC32 polynominal you've posted is x^32 + x^26 + x^23 + x^22 + ...

The x^32 part sometimes gets ommited, since you would need 33 bits to represent that number.

Since you don't do an integer division but rather a polynominal division this is no problem.
Reply With Quote
The Following 2 Users Say Thank You to Kerlingen For This Useful Post:
dila (03-25-2016), tonyweb (03-26-2016)
  #3  
Old 03-27-2016, 06:56
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
Thanks for explaining that, it makes sense now.

I'm puzzled by another property of CRC. According to Wikipedia, the function is supposed to be linear:

u = crc32(a ^ b);
v = crc32(a) ^ crc32(b);

Meaning that u==v for bytes a and b. But I'm finding that letting a=0x55 and b=0xAA gives me the checksums:

u=0xFF000000 and v=0x2D02EF8D

So in what sense is CRC linear?
Reply With Quote
  #4  
Old 03-28-2016, 03:08
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
For anyone who is interested, it turns out that CRC satisfies this identity:

crc32(a) ^ crc32(b) ^ crc32(c) = crc32(a ^ b ^ c)
Reply With Quote
The Following User Says Thank You to dila For This Useful Post:
Hypnz (03-28-2016)
  #5  
Old 03-28-2016, 04:40
evlncrn8 evlncrn8 is offline
VIP
 
Join Date: Sep 2005
Posts: 179
Rept. Given: 36
Rept. Rcvd 54 Times in 24 Posts
Thanks Given: 49
Thanks Rcvd at 117 Times in 69 Posts
evlncrn8 Reputation: 54
that i did kinda know...

safedisc used it lots... in the end all you had to do was find the master key and skip a lot of their functions
Reply With Quote
Reply

Tags
checksum, crc

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to compute the inverse of a polynomial under GF(2^8) ? BlackWhite General Discussion 0 10-10-2015 21:24


All times are GMT +8. The time now is 20:27.


Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX, chessgod101
( 1998 - 2024 )