Public key system confusion

Question

I read the following about PKI:

Using a public key system, a user may encrypt a portion of a document using his or her private key. This message will later be decrypted by the recipient using the sender’s public key. Assuming that the sender’s private key is secure, the recipient can assume basic authenticity of the encrypted portion of the document in that only the sender holds the private key used to encrypt the message. Thus, the encrypted portion of the message is said to have been “digitally signed” by the sender.

I have a few questions about the following line:

This message will later be decrypted by the recipient using the sender’s public key

Let's say I have the sender's public key. And let's say I have "satan's" public key also (which does not belong to the original sender).

1. I thought that the private key is used for signing and deciphering/decrypting, so why does it say that "a user may encrypt a portion of a document using his or her private key"?

2. If I try to decrypt with the sender's public key (as written above), how do I know that the message hasn't been altered? And how do I know that the decryption has succeeded?

3. What will be the result if I try to decrypt the message using "satan's" public key?

   • No data ?

   • Error indicating incorrect key?

   • Gibberish data?

Answer 1

Your text is just very badly written. No wonder you got confused.

1)

a user may encrypt a portion of a document using his or her private key.

Sounds like a badly written description of RSA signing. With RSA signing you essentially encrypt a hash of the message with your private key.

2) You use the senders public key to verify the signature. And since the signature contains a hash of the whole document, you know it hasn't been tampered with.

3) Is a bit unclear. If you decrypt with plain, unpadded RSA, it will succeed for most blocks, and give gibberish. When using padding you'll get a padding failure. But since this is a nonsensical operation, you don't need to think about that.

---

The way messages are encrypted in a public key system is:

1. Sign the hash of the message with your private key
2. Generate a random symmetric key, and encrypt the message(and potentially the signature) with it.
3. Encrypt the symmetric key with the receivers public key and combine it with the ciphertext.

Encrypting the key with the receiver's public key, means that only the owner of the associated private key can decrypt the symmetric key, and thus the message.

Signing the whole message with your private key, means that the receiver verifies that the signature matches the sender's public key, and that the hash embedded in the signature matches the document. Thus he can be sure that the whole message is unaltered, and was sent by the owner of the sender's private key.

Answer 2

Your block of text appears to be aimed at a novice. The last line states the actual result:

Thus, the encrypted portion of the message is said to have been “digitally signed” by the sender.

So question 1. Yes, you sign with a private key and verify the signature with the public key. The actual operation involved is the same. You are "encrypting" the text using a large number. Whether the number is a private key or a public key makes no difference, though there are security gotchas associated with using the wrong key for an operation.

For question 2, you know the message hasn't been altered because only the private key can sign the message. This is the basis of all asymmetric cryptography: one key is held dear, and the other is made public. Through this, you create the characteristic of non-repudiation of sending -- the inability to claim the message was not sent by the holder of the private key. If the private key has been compromised, then all bets are off.

For question 3, the results are implementation-dependent though I suspect you would get gibberish in many cases.

Answer 3

Previous answers are very good, but there's so much confusion in this question that I believe more explanation is always better.

• I thought that the private key is used for signing and deciphering/decrypting, so why does it say that "a user may encrypt a portion of a document using his or her private key"?

It's used to decrypt data that was encrypted by your public key. Also it can sign anything and people with your public key will be able to verify your identity.

• If I try to decrypt with the sender's public key (as written above), how do I know that the message hasn't been altered? And how do I know that the decryption has succeeded?

You decrypt with your own private key, they encrypt with your public key. The decryption cannot fail silently, if an output file is here, then it's all good. Implementations may be broken though.

• What will be the result if I try to decrypt the message using "satan's" public key? No data ? Error indicating incorrect key? Gibberish data?

You cannot decrypt with other public keys. If you try with all but the right private key, it will not work. Error indicating incorrect key is the most likely outcome. You could expect weird implementations to still produce an output file with gibberish data though.