The Pure Crypto Project's Hash Function

[Bill Stewart]

Back when we were having fun doing minimum-length crypto implementations
http://www.cypherspace.org/~adam/rsa/  like RSA-in-minus-3-lines-of-perl,
suitable for T-shirts and tattoos and coke cans and email signatures,
it was probably possible to put together a one-page cryptosystem
implementing PGP-like functionality (but not compatibility, of course),
capable of being faxed to anybody.
The most likely function to be difficult was the prime number generation 
routine;
everything else is known small (except of course for perl itself :-)

Extreme Smallness is mainly a hack, though it was politically important in 
its day.

         (By the way, there's a typo in 
http://www.cypherspace.org/~adam/rsa/rc4.html )

At 07:42 PM 05/02/2003 +0200, Ralf Senderek wrote:
>        http://senderek.de/pcp/pcp-security.html#pure-hash

The version on the web page is slightly different than this one.

Comment 1 - YOW!  BLAZINGLY SLOW!  One modexp per character?

Comment 2 - I've read your explanation of why this should be a keyed hash,
and I'm not convinced that's generally applicable or useful.
There are times it's nice to have a pure hash function,
though I suppose you can somewhat achieve that by using H0==constant.
(It's not very pretty if the constant is 0 or 1, though,
and your "19s" may not percolate fast if the first few input characters are 
small.)

It's also not clear whether the Public Key Modulus you're using
is the modulus of the sender or recipient of a message,
or what to do if you're signing something and encrypting it.

Comment 3 - Is the Modexp implementation you're using dependent on the
first parameter being less than the prime?
If so, you've got a high probability of overflow and need to do
(mod(Hi+Ho), Prime) instead of (Hi+H0).

Comment 4 - The output isn't evenly distributed.  It's always < Prime.
I don't have a handy bignum calculator, and while I assume your prime is
close to 256 bits long, I don't see where you got it, so unless it's
very close to 2**256-1, it'll have artifacts.

>The Pure Crypto Hash Function :
>
>     Prime = 106603488380168454820927220360012878679207958575989291522270608
>     237193062808643
>
>     Ho = PublicKeyModulus mod Prime
>
>     for every character in the message text
>     do
>          Hi+1 = (Hi + 19) XOR ModExp((Hi + Ho), (character i + 19), Prime)
>     done
>
>The hash function produces 256 bit output values.






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