Question

How to generate a key pair for Alice and Bob Respectively Suppose Alice sends plaintext P= 113, how does she encrypt and whats the ciphertext C? After Bob receives C, how does he decrypts it to get the plaintext P? Suppose Alice sends plaintext P= 113, how does she sign it and what are sent to Bob. How does Bob verify the signature? Suppose Bob sends plaintext P=113, how does he sign it and what are sent Alice. How does Alice verify the signature?

Answer 1

If you're using RSA, the signature verification process is (effectively) checking whether:

Se=Pad(Hash(M))(modN)Se=Pad⁡(Hash⁡(M))(modN)

Definitions: SS is the signature; MM is the message; ee and NN are the public exponent and modulus from the public key; (modN)(modN) means that equality is checked modulo NN; PadPad is the padding function; and HashHash is the hashing function. Note I say "effectively" because sometimes the padding method is nondetermanistic; that makes this check slightly different, but not in a way that matters for this discussion.

Now, if we were trying to forge a signature for a message M′M′(with only the public key), we could certainly compute P′=Pad(Hash(M′))P′=Pad⁡(Hash⁡(M′)); however, then we'd need to find a value S′S′ with:

S′e=P′(modN)S′e=P′(modN)

and, if NN is an RSA modulus, we don't know how to do that.

The holder of the private key can do this, because he has a value dd with the property that:

(xe)d=x(modN)(xe)d=x(modN)

for all xx. That means that:

(P′)d=(S′e)d=S′(modN)(P′)d=(S′e)d=S′(modN)

is the signature.

Now, if we have only the public key, we don't know dd; getting that value is equivalent to factoring NN, and we can't do that. The holder of the private key knows dd, because he knows the factorization of NN.