Are there...

Jerrold Leichter jerrold.leichter at
Mon Nov 17 14:56:12 EST 2003

| As David Wagner points out, encryption with a public key (for which the
| private key has been discarded) would seem to work.
There's something seriously wrong here, however.  There are many close, but
not identical, definitions, of a one-way hash.  While none of them explicitly
say so, many *uses* of one-way hashes assume that the output of a hash looks
like the output of a random function.  However, for (say) RSA, this fails
very badly, since RSA is multiplicative.  Suppose, for example, that we used
the well-known technique of generating working keys K1 and K2 from a master
key K by applying a one-way hash function H:  K1 = H(K || "K1"),
K2 = H(K || "K2").  With H=SHA or any reasonable one-way hash revealing K1
provides no useful information about K or K2.  But now suppose instead of
concatenation we, for some reason, used multiplication:

	K1 = H(3 * K)	K2 = H(5 * K)

For H as before, this is just as secure.  But for H = RSA with a known modulus
N and public key, this is completely insecure:  It's easy to compute 3' = the
inverse of 3 mod N (Euclidean algorithm), at which point H(3') * K1 * H(5) =
H(3') * H(K * 3) * H(5) = H(3' * 3 * K * 5) = H(K * 5) = K2.

A useful one-way hash function shouldn't have any simple algebraic properties.
(The existing ones do have a prefix property due to their iterative nature,
and it would be nice to avoid that, though I don't know of any work in that
direction.  Note that this prefix property does mean that the K in "K || "K1")
should probably be significantly less than the block size.  Personally, I favor
XOR'ing the distinguisher - "K1", here - into K, avoiding the whole potential
interaction with the prefix property.  Note of course that this assumes that
H does *not* have some "bad" interaction with XOR - as RSA does with simple
							-- Jerry

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list