# 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$ ? Aug 19, 2011 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.