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 an 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.
Proof: We will prove that, if is an algorithm of complexity at most that breaks existential unforgeability under chosen message attack with probability , then there is an algorithm that breaks RSA (finds given mod ) with probability and complexity .
Without the loss of generality we assume that:
- never makes the same random oracle query twice.
- queries before it requests a signature on a message .
- If outputs then it had previously queried
We construct an algorithm which on input where mod , finds .
Algorithm is defined as:
- Pick randomly.
- Initialise datastructure that stores triples, initially empty.
- Simulate :
- When makes its th random oracle query
- If , answer the oracle query with .
- Otherwise, randomly pick , compute mod , store mod in the datastructure and answer the oracle query with mod
- When requests
- If abort.
- If look for mod in the datastructure and answer the oracle query with .
(Note that we had made the assumption that queries before it requests a signature on a message .)
- When makes its th random oracle query
- After finishes, it outputs . If and mod , then output as the required output .
For each random oracle query, we are doing a RSA exponentiation operation of complexity . So the complexity of would be at most complexity of multiplied by i.e. .
The index chosen by in the first step represents a guess as to which oracle query of will correspond to the eventual forgery output by . When the guess is correct, view of as part of is distributed identically to the view of alone. When guesses correctly and outputs a forgery, then solves the given instance of RSA problem (because mod and thus is of ). Since guesses correctly with probability and outputs a forgery with probability . So, Probability with which breaks RSA , which is what we intended to prove.