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

$\endgroup$
1
  • $\begingroup$ Have you tried $\alpha^e$ for some $\alpha$ ? $\endgroup$
    – user10676
    Aug 19, 2011 at 19:08

1 Answer 1

2
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.