Suppose that Alice and Bob communicate using the RSA PKC$.$ This means

that Alice has a public modulus NA $=$ pAqA, a public encryption exponent eA$,$ and a

private decryption exponent dA$,$ where pA and qA are primes and eA and dA satisfy

eAdA $1$ mod $($pA$1)($qA$1).$

Similarly, Bob has a public modulus NB $=$ pBqB$,$ a public encryption exponent eB$,$

and a private decryption exponent dB$.$

In this situation, Alice can simultaneously encrypt and sign a message in the

following way. Alice chooses her plaintext m and computes the usual RSA ciphertext

c $$ m

eB $($mod NB$).$

She next applies a hash function to her plaintext and uses her private decryption

key to compute

s $$ Hash$($m$)$dA $($mod NA$).$

She sends the pair $($c$,$s$)$ to Bob.

Bob first decrypts the ciphertext using his private decryption exponent dB$,$

m $$ c

dB $($mod NB$).$

He then uses Alice$$s public encryption exponent eA to verify that

Hash$($m$)$ s

eA $($mod NA$).$

Explain why verification works, and why it would be di$$cult for anyone other

than Alice to send Bob a validly signed message.