In the last lecture we described a very complex signature scheme based on one-time signatures and pseudorandom functions. Unfortunately there is no known simple and efficient signature scheme which is existentially unforgeable under a chosen message attack under general assumptions.
Today we shall see a very simple scheme based on RSA which is secure in the random oracle model. In this model, all parties have oracle access to a random function . In implementations, this random function is replaced by a cryptographic hash function. Unfortunately, the proof of security we shall see today breaks down when the random oracle is replaced by hash function, but at least the security in the random oracle model gives some heuristic confidence in the design soundness of the construction.
1. The Hash-and-Sign Scheme
Our starting point is the “textbook RSA” signature scheme, in which a message is signed as and an alleged signature for a message is verified by checking that .
We discussed various ways in which this scheme is insecure, including the fact that
- It is easy to generate random message/ signature pairs by first picking a random and then setting ;
- If is the signature of message and is the signature of , then is the signature of .
Suppose now that all parties have access to a good cryptographic hash function, which we will model as a completely random function , mapping every possible message to a random integer , and define a signature scheme as follows:
- Key generation: as in RSA
- Signature: the signature of a message with secret key is
- Verification: given an alleged signature , a message , and a public key , check that .
That is, we use the textbook RSA method to sign .
Now it is not clear any more how to employ the previously mentioned attacks. If we first select a random , for example, then to find a message of which is a signature we need to compute and then find a message such that . This, however, requires exponential time if is a random functions. Similarly, if we have two messages and know their signatures , the number is a signature for any document such that . Finding such an is, however, again very hard.
We provide a formal analysis of the signature scheme defined in the previous section, in the random oracle model.
Theorem 1 Suppose that , as defined in the previous section, is not existentially unforgeable under a chosen message attack in the random oracle model.
Then RSA, with the key size used in the construction, is not a -secure family of trapdoor permutations, where is the time taken by RSA computation with the selected key size.