In data conversion processing such as encryption processing, a hash function that executes hash processing for input data is often used. The hash function is a function for calculating a compressed value (digest) having a fixed length, for a given message. As the hash function already known, there are: MD5 having an output value of 128 bits; SHA-1 having an output value of 160 bits; further, SHA-256 having an output value of 256 bits; and the like.
For example, based on an analysis-resistance enhancement request and the like, the hash function is desired to have the following resistances.                Preimage Resistance        Second Preimage Resistance        Collision Resistance        
These resistances will be briefly described.                In a hash function that outputs y=h(x) where an input is x and the hush function is h, the Preimage Resistance is equivalent to difficulty in calculating the input x that results in h(x)=y for the output y.        The Second Preimage Resistance is equivalent to difficulty in finding a different input value x′ that satisfies h(x′)=h(x) when one input value x is known.        The Collision Resistance is equivalent to difficulty in finding two different input values x and x′ that satisfy h(x′)=h(x).        It can be said that the higher these resistances are, the safer the hash function is.        
Up to now, due to progress of analytical methods in recent years, vulnerability of the hash functions that have been used, in terms of the above-described resistances, has been revealed. For example, it has become evident that the Collision Resistances of MD5, SHA-1 and the like that have been often used as the hash functions do not meet many system requirement levels. Further, there is SHA-256 or the like having a comparatively long output length as an existing hash function, but this SHA-256 follows the design policy of SHA-1 and thus, anxiety about safety remains as well and therefore, a safer hash function based on other design policy is desired to emerge.