Re: Hash function

bobic <fbloveu@xxxxxxxxxxx> wrote:
Hi, everyone. Here, I have a problem about hash function. That is, can
we construct a hash function, such that, H(x)=y, where x is a random
string, and y=p_1*...*p_k mod p, p_1,...,p_k are small primes, p is a
large prime.

Yep! Let p_1, ..., p_k be the 256 first primes, let p be a prime that is
larger than p_1*...*p_k (that is about 2100 bits). Let y_1,...,y_k be the
bits output by SHA-256 on input of x, and define

H(x) = p_1^y_1 * ... * p_k^y_k .

Voila!

It seems to me that this hash function should inherit all of SHA-256's
collision properties, yet it is a brilliantly bad hash to use in
combination with RSA-FDH signatures. It may be good for an example
of why you really need a random oracle, and not just a collision
resistant hash function.

But perhaps you had something more sensible in mind?

--
Kristian Gjøsteen
.

Relevant Pages

  • Re: Hash function
    ... Kristian Gjøsteen wrote: ... Let p_1, ..., p_k be the 256 first primes, let p be a prime that is ... It seems to me that this hash function should inherit all of SHA-256's ...
    (sci.crypt)
  • Re: Hash function
    ... Mike Amling wrote: ... If p is smaller than the product, the collision properties of SHA-256 ... may be lost in reduction. ... It seems to me that this hash function should inherit all of SHA-256's ...
    (sci.crypt)
  • Re: Fast 1 -> 1 non md5 hash algorithm
    ... > I'm looking for a fast and simple one to one hash function, ... The first thing that comes to mind is that you've found ... hash function can be extremely simple and extremely fast: ... just use the hashed object as its own hash code. ...
    (comp.lang.c)
  • Re: Re-secured Algorithm?
    ... > The other thing is there is no reason to propose SHA-1 anymore. ... > come to mind]. ... But sha2 is quite slow, ... Maybe they will call for YA new hash function. ...
    (sci.crypt)
  • Re: strncmp performance
    ... > I've just been reading thread and two things pop to mind. ... the hash function you have chosen looks a little bit questionable ... if your program still boils down to string comparison no ...
    (comp.lang.c)