0
$\begingroup$

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$?

  • 0
    Have you tried $\alpha^e$ for some $\alpha$ ?2011-08-19

1 Answers 1

2

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).