- Construct a pair of private/public key RSA, where the prime numbers that we use are $p=11, q=13$.
- Describe how we can calculate a RSA signature at the message $m=2$ without using a hash function.
- 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:
$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)$.
The signature is $c=m^d \pmod {\phi(n)}$.
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??
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.