Modulo based hash functions [was: The Pure Crypto Project's Hash Function]

[tom st denis]

--- Ralf Senderek <ralf at senderek.de> wrote:

> 
> But for the sake of clarity (and truth) let us use this hash to
> create signatures using secrets p=43 and q=79 assuming that the
> factorization of n=3397 is "unknown". We can go into 2048 bit space
> the other day.
> 
> Let x=1234 and y=2345 be two inputs.
> 
> I choose g = lcm(42, 78) = 546 as the hash's generator.
> (Please correct me if I am doing wrong here)
> 
> The SRH now is :    hash(x) = 546 ^ x mod 3397
> 
> We get:    hash(x)    = 2949
>            hash(y)    = 1284
>            hash(x+y)  = 2258
> 
> Now we use the same modulus to create signatures using d = 113 as the
> secret signingkey and e = 29 for signature verification.
> 
>            sig(hash(x))   =  1029
>            sig(hash(y))   =  1125
> 	   sig(hash(x+y)) =  2645
> 
> So if you happen to be Alice and you have created the signatures on x
> and y
> someone can compute
> 
> 	  sig(hash(x)) * sig(hash(y)) mod n = 1029 * 1125 mod 3397
>                                             = 2645
> and pretend to have Alice's signature on z = x+y, which verifies
> correctly.

Wow you single-handly rediscovered why we pad hashes before signing
with RSA...

See, this is the ====>EXACT<==== reason why you shouldn't be inventing
new crypto algorithms without at least doing some research first.

Tom

__________________________________
Do you Yahoo!?
The New Yahoo! Search - Faster. Easier. Bingo.
http://search.yahoo.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com