Question

RSA and digital signatures. Recall that in the RSA public-key cryptosystem, each user has a public key P=(N,e) and a secret key d. In a digital signature scheme, there are two algorithms, sign and verify. The sign procedure takes a message and a secret key, then outputs a signature $\mathit{\sigma }$. The verify procedure takes a public key $\left(N,e\right)$, a signature $\mathit{\sigma }$, and a message M, then returns “true” if $\mathit{\sigma }$could have been created by sign (when called with message M and the secret key (N, e) corresponding to the public key ); “false” otherwise.

(a)Why would we want digital signatures?

(b) An RSA signature consists of sign, $\left(M,d\right)\mathbf{=}{\mathit{M}}^{\mathbf{d}}\left(modN\right)$where d is a secret key and N is part of the public key . Show that anyone who knows the public key $\mathbf{(}\mathbf{N}\mathbf{,}\mathbf{}\mathbf{e}\mathbf{)}$can perform verify $\mathbf{\left(}\mathbf{\right(}\mathbf{N}\mathbf{,}\mathbf{}\mathbf{e}\mathbf{)}\mathbf{,}{\mathit{M}}^{\mathbf{d}}\mathbf{}\mathbf{,}\mathbf{}\mathit{M}\mathbf{)}$, i.e., they can check that a signature really was created by the private key. Give an implementation and prove its correctness.

(c) Generate your own RSA modulus, N=pq public key e, and private key d (you don’t need to use a computer). Pick p and q so you have a 4-digit modulus and work by hand. Now sign your name using the private exponent of this RSA modulus. To do this you will need to specify some one-to-one mapping from strings to integers in $\left[0,N-1\right]$. Specify any mapping you like. Give the mapping from your name to numbers ${\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{m}}_{\mathbf{k}}\mathbf{,}$then sign the first number by giving the value ${{\mathit{m}}^{\mathbf{d}}}_{\mathbf{1}}\left(modN\right)$, and finally show that .

${\left({m^d}_1\right)}^{\mathbf{e}}\mathbf{=}{\mathit{m}}_{\mathbf{1}}\left(modN\right)$

(d) Alice wants to write a message that looks like it was digitally signed by Bob. She notices that Bob’s public RSA key is $\left(17,391\right)$. To what exponent should she raise her message?

Short answer

(a) Digital Signature ensures safety of data.

(b) It is proved that digital signature make data more secure along with RSA algorithm.

(c) The implementation of RSA module is correct.

(d) The exponent must be raised by the factor of 145

Step-by-step solution

Solution (a)

We are using Digital Signature here because these might be chances of leakage of secret message. Hence, digital signature is used for authentication of the person who sends the message and this also ensures that no other person then sender and target receiver can change the original message.

Solution (b)

We can implement the algorithm verify $\left(\left(\mathrm{N},\mathrm{e}\right),{\mathrm{M}}^{\mathrm{d}},\mathrm{M}\right)$by making a check if.

${\left({\mathrm{M}}^{\mathrm{d}}\right)}^{\mathrm{e}}\mathrm{mod}\mathrm{N}=\mathrm{M}.$

Now if the signature was created by the private key ‘d’, then

${\left({\mathrm{M}}^{\mathrm{d}}\right)}^{\mathrm{e}}\mathrm{mod}\mathrm{N}={\left({\mathrm{M}}^{\mathrm{e}}\right)}^{\mathrm{d}}\mathrm{mod}\mathrm{N}=\mathrm{M}\mathrm{mod}\mathrm{N}=\mathrm{M}$

This is done by correctness of RSA protocol. Now, if someone (opponent) was able to sign, then the opponent will be able to exponentiate by d mod N.

This will allow the opponent(intruder) to decrypt the message which becomes a loophole of RSA algorithm.

Thus along with RSA algorithm, Digital Signature must be used to ensure more security.

Solution (c)

Let us take value of p and q as: p=137and q=71.

So,

N=pq

=137x71

=9727

And

Phi (N)= (p-1) (q-1)

=136x70

=9520

Let. = 99We use such value of because ‘99’ is co-prime of Phi( N).

So,d must have to be inverse of (e mod Phi (N)) which would be d=6539. We use found by using Extended Euclid.

Suppose my name is ‘Laurance’, then first letter of my name is ‘L’ and I would like to map it with binary using ASCII code, for which L=76.

So the signature of my first letter ‘L’ is:${76}^{99}\mathrm{mod}$9727 =4814

Now if we want to revert it:${4814}^{99}\mathrm{mod}$9727 = 76

Hence prove that we get back ASCII code of my name’s first character.

Solution (d)

Given Bob’s public key (17,391).

On factorize 391=17x23.

If we consider N=391according to Alice, then Phi (391) = 16x22 = 352

Then, we know that if ‘d’ is private key,

ed =1mod (p-1) (q-1)

Hence,

$$\begin{gathered} d=e^{-1}\mathrm{mod}\left(\mathrm{p}-1\right)\left(\mathrm{q}-1\right) \\ \mathrm{d}={\mathrm{e}}^{-1}\mathrm{mod}352=145 \end{gathered}$$

So 145is the required factor.