On Thu, Aug 04, 2005 at 12:55:51PM +1000, Arash Partow wrote:

> Hi all,
> 
> My question relates to hash functions in general and not specifically
> cryptographic hashes. I was wondering if there exists a group of hash
> function(s) that will return an identical result for sequentially
> similar yet rotate/shift wise dissimilar input:
> 
> ie: input1 : abcdefg -> h(abcdefg) = 123
>     input2 : gabcdef -> h(gabcdef) = 123
>     input3 : fgabcde -> h(fgabcde) = 123
> 

Sure, just pick the lexicographically first cycle and hash
that. This is an invariant of all cyclic permutations of the
string.

        epermut -> h(epermut) 
        ermutep -> h(epermut)
        muteper -> h(epermut)
        permute -> h(epermut)
        rmutepe -> h(epermut)
        tepermu -> h(epermut)
        uteperm -> h(epermut)

More generally given any automorphism group on the input strings, hashing
the lexicographically smallest member of the orbit of an input string
under the group gives a hash that is invariant under the group operation.

-- 

 /"\ ASCII RIBBON                  NOTICE: If received in error,
 \ / CAMPAIGN     Victor Duchovni  please destroy and notify
  X AGAINST       IT Security,     sender. Sender does not waive
 / \ HTML MAIL    Morgan Stanley   confidentiality or privilege,
                                   and use is prohibited.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to