Re: Which checksums/hashes do not have any 'internal cycles'?


"Claudio Grondi" <claudio.grondi@xxxxxxxxxx> wrote in message
news:ecps0p$rmv$1@xxxxxxxxxxxxxxxxxxxxxxxxxxxx

Let's consider the 32-bit CRC as a mapping of all four byte long strings
onto another four byte long strings representing the CRC values of the
first mentioned ones.

The 32-bit CRC has at least one 'internal cycle' because the CRC-32 of
chr(0xFF)+chr(0xFF)+chr(0xFF)+chr(0xFF)
is the integer
0xFFFFFFFF
which expressed as a four byte string is
chr(0xFF)+chr(0xFF)+chr(0xFF)+chr(0xFF)

Which of the known checksums/hashes does not have any 'internal cycles',
i.e.
- starting at any checksum value and taking it as input for
- calculating a checksum in order to take this value as input for
- calculating a checksum value ... (i.e. continuing with above ^)
'visits' all of the possible checksum values?


I don't know of any, or how any (useful ones) could be efficiently
constructed. the easiest would likely be some kind of internal permutation
(a piece of data, when processed, results in a particular permutation). each
permutation, when processed, results in another permutation (the next in a
'chain').

the cycle depends on the nature of the permutation and the algo used for
generating it.

(intuitively, I can imagine the general process, but it is difficult to
imaging a worthwhile demonstation that would follow the whole chain). one
possibility (working directly on the permutatoion itself) would involve
attempting to increment the first item (effectively swapping or rotating
parts of the permutation to fulfil this goal).

many other simple direct-computation approaches I can imaging would,
intuitively, seem to generate a "transpose", which if run through the same
algo would produce the first again.

any individual permutation would exhibit this property in itself.

however, none have been commited to paper or tested, so really, I don't
know.

example:
1 2 3 4 5
2 1 3 4 5
3 1 2 4 5
4 1 2 3 5
5 1 2 3 4
1 5 2 3 4
2 5 1 3 4
3 5 1 2 4
4 5 1 2 3
....
1 3 4 5 2
2 3 4 5 1
3 2 4 5 1
4 2 3 5 1
5 2 3 4 1


As I am after gaining some deeper understanding of what checksums/hashes
are, can someone please explain it to me or point me to appropriate
resources helping me to get enlightened on this subject?


don't have anything particularly good here myself.
my experience has been based mostly been trial and error, and also on my own
intuition.


Claudio Grondi


.

Relevant Pages

  • Which checksums/hashes do not have any internal cycles?
    ... Let's consider the 32-bit CRC as a mapping of all four byte long strings onto another four byte long strings representing the CRC values of the first mentioned ones. ... The 32-bit CRC has at least one 'internal cycle' because the CRC-32 of ... calculating a checksum in order to take this value as input for ...
    (comp.compression)
  • Re: Slowing down string changers
    ... If you are only interested in protecting the strings, ... CRC or checksum somewhere else in the file. ... To make life easier on yourself, you could encode a pointer ...
    (comp.lang.asm.x86)
  • Re: Compare permutations
    ... \ FORTH> permtest (short strings, ... permutation comparisons returns false. ... During the pass through the second string if any count goes negative ... This also means that summing of the characters is ...
    (comp.lang.forth)
  • Re: Sabermetrics goes mainstream, part 2384
    ... many strings are unique. ... K 'L', handing off each string to the Canonical Permutation Generator, ... put in the extra work on the random distribution to keep it from ... Possibly the worst sorting algorithm around. ...
    (rec.sport.baseball)
  • Re: Microsoft Interview Questions
    ... Are the two strings the same length? ... why is the first case not a permutation? ... Zero might have implied "false". ... Just obtaining the answer for a non-permutation would not have proved ...
    (comp.theory)