david wrote:
> Can someone explain how to compute checksums
It depends entirely upon what sort of checksum you wish to compute.
> and how do they work ?
The idea is that every bit of the data affects the checksum in some
way. If the data changes, then the checksum will (usually) also
change.
There are two main types of checksums: weak checksums and strong
(cryptographic) checksums.
A weak checksum is one where it is fairly straightforward to generate
a block of data which has a particular checksum.
A strong checksum is one where you can't generally generate a block of
data which has a particular checksum, apart from by trying many
different blocks of data until you find one with the correct checksum
(i.e. a `brute force' method).
> This is for a program i'm working on (
> http://www.imaginet.fr/~dramboz/jview) :
> the program can create databases which are composed of blocks with the
> same size. I'd like to add a checksum to each block to see if the block
> is corrupted (or not).
The simplest form of checksum is to use an associative binary
operation (e.g. addition or exclusive-or), e.g.
int checksum(int *data, int size)
{
int sum = 0;
int i;
for (i = 0; i < size / sizeof(int); i++)
sum += data[i];
return sum;
}
This is quick to calculate, but weak. For instance, if you swap any
two words of the data block, you will get the same checksum. The `sum'
program uses this sort of algorithm.
A stronger checksum can be obtained by applying a different `weight'
to each position, e.g.
for (i = 0; i < size / sizeof(int); i++)
sum += (i + 1) * data[i];
This will catch transposition errors (swapping two words), but it
still isn't hard to `forge' (i.e. to create a block of data having a
particular checksum). The `cksum' program uses this sort of algorithm.
The `standard' cryptographic checksum is MD5. This is very strong, but
is slow to calculate. You can get the MD5 algorithm from the source
code for the `md5sum' program, which is part of the GNU textutils
package.
--
Glynn Clements <[EMAIL PROTECTED]>
