Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Have you tried $\alpha^e$ for some $\alpha$ ? –  user10676 Aug 19 '11 at 19:08

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
+1 Excellent point about the padding. –  Peter Taylor Aug 19 '11 at 20:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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