Proof of security for RSA signatures

Question

I am new to here, I was having some problems with a problem I am working on:

"For each of the following variants of the definition of security for signatures, state whether textbook RSA is secure and prove your answer:

(a) In this first variant, the experiment is as follows: the adversary is given the public key $pk=(N,e)$ and a random message $m$. The adversary is then allowed to query the signing oracle once on a single message that does not equal $m$. Following this, the adversary outputs a signature $\sigma$ and succeeds if $\operatorname{Vrfy}_{pk}(m,\sigma)=1$. As usual, security is said to hold if the adversary can succeed in this experiment with at most negligible probability.

(b) The second variant is as above, except that the adversary is not allowed to query the signing oracle at all."

The construction for $\sigma$ is:

$$\sigma=m^d \mod N,$$ where $(N, d)$ is the secret key.

And the $\operatorname{Vrfy}$ function is as follows: $$\operatorname{Vrfy}_{(N,e)}(m,\sigma)= \begin{cases}1 & \text{if }m=\sigma^e \mod N \\ 0 & \text{otherwise}.\end{cases}$$

Since the known attacks on textbook-RSA signature forgery arise from two things:

1. A no-message attack: if the adversary has access to a signing oracle and a public key, he can sign an arbitrary message.

2. If the adversary has two signatures on two different messages, he can get a third message that is the product of those two messages and sign it with the product of the two signatures and it would be valid.

Would this be a good proof to show how a.) is secure:

The adversary uses the signing oracle to get a signature on $m_1$, so he gets $\sigma=m_1^d \mod N$, where $d$ is the secret key. Now he should be able to take the discrete logarithm of $\sigma$ to find $d$, but that is a hard problem, so the algorithm to forge this signature by finding the secret key is at least as hard as the DL problem, so the probability is negligible.

And my intuition is that b) is also secure, but I don't yet know how to go on about proving it formally.

Answer 1

For (a), what if you query the signing oracle on $m' \equiv -m \mod N$? Can you see how to compute $m^d$ given $(-m)^d$? (Hint: $d$ is odd.)

For (b), try showing that doing this is equivalent to solving the RSA problem.

Answer 2

I believe there is no standard model proof for security of the RSA signature scheme ( Certainly there isn't for textbook RSA. Therefore 1) is insecure. 2 Maybe secure.

The proof of security for a signature scheme is to show that given an adversary that breaks the scheme with non negligible probability, you can construct a solver for the underlying security problem of the system. This is called a reduction proof. You prove the security of a scheme by showing the ability to break the scheme breaks the computationally hard problem.

In this case,the problem you are reducing to the security of the schemeis the rsa problem which is given $m^e mod \ n $, $e$,$n$, recover $m$.

The problem is that in order to compute the signature the adversary requires in 1, you must know the private key d (i.e. $d$ s.t. $ d=e^{-1}mod \ \phi(n)$).Since you don't know this when given an instance of the RSA problem, you can't use a break in the signature scheme to solve the RSA problem because you can't operating the signing oracle.

2) Doesn't have this problem, so it might or might not be secure.