1
  1. Construct a pair of private/public key RSA, where the prime numbers that we use are $p=11, q=13$.
  2. Describe how we can calculate a RSA signature at the message $m=2$ without using a hash function.
  3. Show that, given the above signature, we can calculate a valid signature at the message $m'=8$ without using the private key.

I have done the following:

  1. $n=p \cdot q=11 \cdot 13$

    $\phi(n)=(p-1)(q-1)=10 \cdot 12=120$

    We choose a $e$ such that $(e,\phi(n))=1$. We take for example, $e=7$.

    Then we calculate $d$ such that $ed \equiv 1 \pmod {\phi(n)}$. So, $d=13$.

    The private key is $d=13$ and the public key is $(e, n)=(7, n)$.

  2. The signature is $c=m^d \pmod {\phi(n)}$.

  3. There is a $m_1$ such that $m=m'm_1$.

    $c=m^d \pmod {\phi(n)} \Rightarrow c=m'^dm_1^d \pmod {\phi(n)} \\ \Rightarrow c(m_1^d)^{-1}=m'^d \pmod {\phi(n)} \Rightarrow cm_1^{-d}=m'^d \pmod {\phi(n)} \\ \Rightarrow ((cm_1^{-d})^{-e})^{-\frac{1}{e}}=m'^d \pmod {\phi(n)} \Rightarrow (c^{-e}m_1^{ed})^{-\frac{1}{e}}=m'^d \pmod {\phi(n)} \\ \Rightarrow (c^{-e}m_1)^{-\frac{1}{e}}=m'^d \pmod {\phi(n)}$

    That means that the signature of the message $m'$ is $(c^{-e}m_1)^{-\frac{1}{e}}$.

Could you tell me if it is correct what I have done??

Mary Star
  • 13,956

1 Answers1

2

For (2) and (3), I think you should be computing mod $n$, not mod $\phi(n)$. (Requiring verifiers to know $\phi(n)$ leaks too much information.) Otherwise (2) could work.

For (3) you've also got some complication. Instead, make the observation that, if the signing scheme is simply raising to the $d$ power, then

$$8^d = (2^3)^d = 2^{3d} = 2^{d3} = (2^d)^3 = c^3\textrm{.}$$

That is, just take your signature for $2$ and cube it.

Ken
  • 3,751
  • Ok... Thank you very much!! :-)

    $$$$

    Could you also take a look at my other question: http://math.stackexchange.com/questions/1324224/electronic-voting-system ?

     – Mary Star Jun 13 '15 at 20:54
  • for the second question why using $m^d mod n$ and not $m^e mod n$ – Paris Lamp Jul 23 '15 at 21:30
  • @paris Since people have to verify the signature, all they have is $e$. Hence, if the signer uses $d$, verifiers can verify. – Ken Jul 23 '15 at 21:32
  • in theory we know that $m^d mod n$ is encryption function and the seond one is descryption.when they say to calculate an RSA signature we have to calculate the decryption function only? – Paris Lamp Jul 23 '15 at 21:35
  • @paris Well, $m^e\mod n$ is encryption, but you get the idea. Remember that, at their heart, these are just math calculations. Just because we perform an operation to perform a certain task, it doesn't mean that's all that calculation is good for. :) – Ken Jul 23 '15 at 21:38
  • sorry i meant the other way arround.thank for the correction. i am right for that i asked about when they ask about signature? – Paris Lamp Jul 23 '15 at 21:42
  • @paris Yes; in this scheme, to sign means to simply perform the decryption operation. – Ken Jul 23 '15 at 21:43
  • for the $(3)$ observation continous in $mod(n)$? such that $8^d mod n=.....=c^3 mod n$ ? – Paris Lamp Jul 23 '15 at 21:59
  • @paris Yes, it all occurs in $\mod n$. – Ken Jul 23 '15 at 22:01
  • we have to observe only this for a complete answer? i saw what the OP wrote and its complicated for the $3$ – Paris Lamp Jul 23 '15 at 22:03
  • @paris Yes, just cube the signature for $2$. – Ken Jul 23 '15 at 22:05
  • @Ken I am wondering that if the second problem was :Describe how we can sign the message $m$ with $h(m)=3$ its indepedent from $m \neq 2$ of the regular question how we can attach it? – Paris Lamp Jul 24 '15 at 18:20