Proof of security for RSA signatures 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 &amp; \text{if }m=\sigma^e \mod N \\ 0 &amp; \text{otherwise}.\end{cases}$$

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


A no-message attack: if the adversary has access to a signing oracle and a public key, he can sign an arbitrary message.
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.
For (a), what if you query the signing oracle on $m&#39; \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.