RSA signature system

Question

Alice wants to construct a RSA signature system to sign messages. The system is secure if the measure $n$ is a product of two primes, each of them has two digits.

1. Describe the construction of the keys.
2. Describe how Alice signs the message $m$, with $h(m)=3$.
3. Describe how Bill, who gets the message and the signature, verifies the signature at the message.

$$$$

I have done the following:

1. Alice choose two primes $p$, $q$ and calculates $n=p \cdot q$. She calculates $\phi(n)=(p-1)(q-1)$ and she chooses an integer $e$ coprime with $\phi(n)$. The she finds the inverse $d$, $ed \equiv 1 \pmod {\phi(n)}$.

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

   Is this correct??

2. $s=h(m)^d \pmod n$

   Do we have to find the private key $d$??

Answer 1

You've got all the high points. Your description of (1) is fine.

You've also got the high points for the signature. Alice sends $(h(m))^d$ as the signature. Since $d$ is possessed only by Alice, this is fine. Bill will then take the message $m$ and hash it using the same hash function $h$ to obtain $h(m)$.

He then also takes the received $(h(m))^d$, raises it to the power $e$ (mod $n$), and if all is well, it will be the same as his calculation of $h(m)$. At no point will Bill need to obtain $d$.

Answer 2

Secret Key Generation:

• Find odd primes $p$ and $q$
• Choose a number $d\in{Z}^*_{\phi(pq)}$

Public Key Generation:

• Compute $n=pq$
• Find a number $e$, such that, $ed\equiv1\pmod{\phi(n)}$

Message Space:

• $[0,\dots,n-1]$

Message Signature:

• Compute $T=H(M)$
• Compute $S=T^d\bmod{n}$

Message Verification:

• Compute $T=H(M)$
• Assert $S^e\bmod{n}=T$