CS276 Lecture 22 (draft)

Summary

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 ${H : \{ 0,1 \}^n \rightarrow \{ 0,1 \}^m}$ . 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 ${M}$ is signed as ${M^d \bmod N}$ and an alleged signature ${S}$ for a message ${M}$ is verified by checking that ${S^e \bmod N = M}$ .

We discussed various ways in which this scheme is insecure, including the fact that

It is easy to generate random message/ signature pairs ${M,S}$ by first picking a random ${S}$ and then setting ${M:= S^e \bmod N}$ ;
If ${S_1}$ is the signature of message ${M_1}$ and ${S_2}$ is the signature of ${M_2}$ , then ${S_1\cdot S_2 \bmod N}$ is the signature of ${M_1 \cdot M_2 \bmod N}$ .

Suppose now that all parties have access to a good cryptographic hash function, which we will model as a completely random function ${H : \{ 0,1 \}^m \rightarrow {\mathbb Z}_N}$ , mapping every possible message ${M}$ to a random integer ${H(M) \in {\mathbb Z}_N}$ , and define a signature scheme ${(Gen,Sign,Verify)}$ as follows:

Key generation: as in RSA
Signature: the signature of a message ${M}$ with secret key ${N,d}$ is ${H(M)^d \bmod N}$
Verification: given an alleged signature ${S}$ , a message ${M}$ , and a public key ${N,e}$ , check that ${S^e \bmod N = H(M)}$ .

That is, we use the textbook RSA method to sign ${H(M)}$ .

Now it is not clear any more how to employ the previously mentioned attacks. If we first select a random ${S}$ , for example, then to find a message of which ${S}$ is a signature we need to compute ${h := S^e \bmod N}$ and then find a message ${M}$ such that ${H(M)=h}$ . This, however, requires exponential time if ${H}$ is a random functions. Similarly, if we have two messages ${M_1,M_2}$ and know their signatures ${S_1,S_2}$ , the number ${S_1 \cdot S_2 \bmod N}$ is a signature for any document ${M}$ such that ${H(M) = H(M_1) \cdot H(M_2) \bmod N}$ . Finding such an ${M}$ is, however, again very hard.

2. Analysis

We provide a formal analysis of the signature scheme defined in the previous section, in the random oracle model.

Theorem 1 Suppose that ${(Gen,Sign,Verify)}$ , as defined in the previous section, is not ${(t,\epsilon)}$ 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 ${(t\cdot O(r), \epsilon\cdot t)}$ -secure family of trapdoor permutations, where ${r}$ is the time taken by RSA computation with the selected key size.

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

CS276 Lecture 22 (draft)

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply