Finding collision resistant hash functions
hi, Is there a polynomial time algorithm that will find collision hash functions or how are we supposed to find collision free hash functions?What exactly is the difficulty in finding collision free hash functions? Regards Sarath. __________________________________ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com
On Mon, 7 Jul 2003, Sarad AV wrote:
Is there a polynomial time algorithm that will find collision hash functions or how are we supposed to find collision free hash functions?What exactly is the difficulty in finding collision free hash functions?
It can't be collision free if the number of input bits exceeds the number of output bits. Think about it, it should be obvious! Patience, persistence, truth, Dr. mike
hi, --- Mike Rosing <eresrch@eskimo.com> wrote:
It can't be collision free if the number of input bits exceeds the number of output bits. Think about it, it should be obvious!
Yes,the pigeon hole principle but that was not what i meant. Lets say we are using SHA-1 and i hash 2^80 messages.What I am looking for is a compression function such that the chances of collision in the message digest obtained by hashing these 2^80 messages is collision free or very low probability of collision.How do we make such a compression function? I am not hashing more than 2^160 to get the collisions as you had suggested. Regards Sarath. __________________________________ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com
hi, how do we complete this table Table shown may be completed to define 'associative' binary operation * on S={a,b,c,d}. Assume this is possible and compute the missing entries *|a|b|c|d --------- a|a|b|c|d --------- b|b|a|c|d --------- c|c|d|c|d --------- d| | | | Its clear for commutativity but I am a trifle confused on how we do it for associativity. Thank you. Regards Sarath. __________________________________ Do you Yahoo!? Yahoo! SiteBuilder - Free, easy-to-use web site design software http://sitebuilder.yahoo.com
"For my ally is Perl, and a powerful ally it is." On Tue, Aug 12, 2003 at 02:06:43AM -0700, Sarad AV wrote:
hi,
how do we complete this table
Table shown may be completed to define 'associative' binary operation * on S={a,b,c,d}. Assume this is possible and compute the missing entries
*|a|b|c|d --------- a|a|b|c|d --------- b|b|a|c|d --------- c|c|d|c|d --------- d| | | |
Lucky you! There are only 256 possibilities. There are four solutions: The last row can be any of: d c c a d c c b d c c c d c c d ... #!/usr/bin/perl -w use strict; my $optbl = [ [0,1,2,3], [1,0,2,3], [2,3,2,3], ]; for(my $i=0; $i<0x100; $i++){ $optbl->[3] = [ ($i>>0)&0x3, ($i>>2)&0x3, ($i>>4)&0x3, ($i>>6)&0x3, ]; if(&check_assoc($optbl)){ for(join(',',@{$optbl->[3]})){ tr/0123/abcd/; print "$_\n"; } } } sub check_assoc { my $op = shift; for(my $i=0;$i<3;$i++){ for(my $j=0;$j<3;$j++){ for(my $k=0;$k<3;$k++){ if( $op->[ $op->[$i][$j]] [ $k ] != $op->[ $i ] [ $op->[$j][$k] ] ) { return 0; } } } } return 1; }
Actually, strike that... The last row can only be (d,c,c,d). I had an off-by-one in the check_assoc subroutine. It should be: sub check_assoc { my $op = shift; for(my $i=0;$i<4;$i++){ for(my $j=0;$j<4;$j++){ for(my $k=0;$k<4;$k++){ if( $op->[ $op->[$i][$j]] [ $k ] != $op->[ $i ] [ $op->[$j][$k] ] ) { return 0; } } } } return 1; } On Tue, Aug 12, 2003 at 03:04:41PM -0400, BillyGOTO wrote:
"For my ally is Perl, and a powerful ally it is."
On Tue, Aug 12, 2003 at 02:06:43AM -0700, Sarad AV wrote:
hi,
how do we complete this table
Table shown may be completed to define 'associative' binary operation * on S={a,b,c,d}. Assume this is possible and compute the missing entries
*|a|b|c|d --------- a|a|b|c|d --------- b|b|a|c|d --------- c|c|d|c|d --------- d| | | |
Lucky you! There are only 256 possibilities.
There are four solutions:
The last row can be any of:
d c c a
d c c b
d c c c
d c c d
...
#!/usr/bin/perl -w use strict;
my $optbl = [ [0,1,2,3], [1,0,2,3], [2,3,2,3], ];
for(my $i=0; $i<0x100; $i++){ $optbl->[3] = [ ($i>>0)&0x3, ($i>>2)&0x3, ($i>>4)&0x3, ($i>>6)&0x3, ]; if(&check_assoc($optbl)){ for(join(',',@{$optbl->[3]})){ tr/0123/abcd/; print "$_\n"; } } }
sub check_assoc { my $op = shift; for(my $i=0;$i<3;$i++){ for(my $j=0;$j<3;$j++){ for(my $k=0;$k<3;$k++){ if( $op->[ $op->[$i][$j]] [ $k ] != $op->[ $i ] [ $op->[$j][$k] ] ) { return 0; } } } } return 1; }
participants (3)
-
BillyGOTO -
Mike Rosing -
Sarad AV