# RSA signing message without its disclosal

I am trying to solve this problem from some textbook:

Assume some authoririty $A$ has the public RSA key $(n,e)$ and $(n,d)$ as its private key.

We would like $A$ to sign us a message $m$, but without disclosing it. So we send to $A$ the message $m' = k\cdot m$ and receive back $s' = m'^d \pmod{n}$

How could we determine $k$ so that we can find the signed message for $m$ ($s = m^d \pmod{n}$) without the use of the private key $d$?

Is the problem of determing $k$ any harder if $A$ only signs messages that are even? You can assume $gcd(n,m) = 1.$

Now, an easy thing to do would be to take $k = m$ and then calculate $s = \sqrt{m'}$ but since there could be more solutions to the last equality, I suspect there has to be a smarter choice for $k$?

Anyone happens to see a good choice of $k$ that allows one to compute $s$?

-
Have you tried $\alpha^e$ for some $\alpha$ ? –  user10676 Aug 19 '11 at 19:08

The nice thing for modular exponentation (as used by RSA) is that the power laws are still valid: $a^{b\cdot c} =(a^b)^c = (a^c)^b$, and $(a\cdot b)^c = a^c \cdot b^c$. (Everything written here is to be thought $\mod n$.)

So, $m' = k \cdot m$ implies $s' = (k \cdot m)^d = k^d \cdot m^d = k^d \cdot s$.

Also, we know the $e = d^{-1}$, thus we simply choose any random number $q$, calculate $k := q^e$, which implies $k^d = q$ (with $q$ known to us).

Now we can calculate $q^{-1}$, and from this $s = s' \cdot q^{-1}$. Done.

Of course, this will not as easy work in reality, as RSA is there always used with some padding in a fixed format, which is added to the message (and can't be influenced by us).

-
+1 Excellent point about the padding. –  Peter Taylor Aug 19 '11 at 20:54