# Help to understand secure connections and encryption using both private/public key in RSA?

I just started teaching myself cryptography, I am reading this http://www.garykessler.net/library/crypto.html to understand the basics.

I am confused by Sections 3.4 and 5.3. Section 3.4 details how to combine hashing, secret key, and public key crypto to get a secure connection over an unsecured network.

To make the digital signature for the message, Alice encrypts the hash value of her message with her private key. Why did Alice do this? I thought private keys were exclusively for decrypting and public keys for encrypting? This means anyone with Alice's public key can decrypt her digital signature and get the hash of her message. How safe is it to use private keys for encryption? Is this the only case where it is acceptable (to send a hash of a message)?

I also have some questions about the digital envelope. A random session key is generated for each session. It is used to encrypt Alice's message, and then it is also encrypted using Bob's public key and both the encrypted message and encrypted session key are sent to Bob. Is this session key the private key in symmetric encryption (i.e. this is how they securely transfer their shared private key to begin using AES for example)? Should Bob respond by only using the session key Alice sent to encrypt his message (no more RSA and hashing). Is it safe to assume Alice is who she really says, and Bob is who he really says at this point? Or does Bob need to first respond and somehow confirm he is in fact Bob? And should the session key change after each message (does this make their correspondence safer)?

Ok, finally one last question! Sorry! In section 5.3 we are given the public key (11,15) and the private key (3,15) as our pair of keys for RSA. The problem is, I can encrypt a string of data using any one of the pairs and decrypt it using any one of the pairs! This means I can use the public key to encrypt something... And then use the very same public key to decrypt that something! Only the private key should be able to do this? My assumption is that this is only the case because the number pair for each key is ridiculously small (3, 11, and 15). If I were using 100 digit prime numbers would this work differently? I think that messages encrypted by the private key can only be decrypted by the public key (the private key can't decrypt its own messages) and messages encrypted by the public key can only be decrypted by the private key (the public key can't decrypt its own messages). Is this correct, or can the private key decrypt its own messages? I'm not at a stage where I can actually use RSA yet..

That's it! For anyone who actually read through this, thanks so much. If you can point me to resources that better explain this topic, that works as well.

I have come to the following conclusions, some not so correct (corrections are addressed in the accepted answer for this question)

Ok I did some more research and I'll answer some of my own questions.

Can you use the private key to encrypt information using RSA?

Yes, actually the keys are interchangeable (the public key can be the private key, and the private key can become the public key). What makes one private and one public is the fact that you keep one private and decide to hand the other one out.

The problem with encrypting using the private key is that ANYONE can decrypt this information if they have the public key! This begs the question of "why even bother encrypting the hash, if anyone can read it? Why not send it as a plaintext hash?"

Turns out this step is important to verify that Alice is who she says. Only the real Alice has the private key, and therefore, only the real Alice can use the private key to encrypt messages that can only be decrypted with the public key. If Bob decrypts the message and the hash of the message and finds that the hash he computes on his own end is different than the one the "alleged Alice" sent, then he can conclude that either the hash or message (or both!) have been tampered with by a 3rd party and that he is not having a secure correspondence.

What is a session key?

If I were to use AES for symmetric encryption, the "session key" would be a 128-bit, 192-bit, or 256-bit secure key I generated (depending on the variant of AES I want to use). This is also known as the private key in symmetric encryption. Since AES is a block cipher, I don't need to worry about changing the key every message (block ciphers use the same key to encrypt different blocks of data). I should change the key every time a new correspondence is established between Alice and Bob, however, for fear that Bob (in my case, Alice is a central server, and "Bob" would be multiple clients) has been compromised and our previously generated secret key has been revealed to a malicious 3rd party.

How should Bob respond now that Alice has initiated correspondence?

Both Alice and Bob have their own pair of public and private keys, and they share an additional private key, the 'session key' used for symmetric encryption. Bob must verify the integrity of Alice's message to confirm Alice's identity and decide his response.

First, Bob needs to decrypt the hash Alice sent (a hash of her message) that was encrypted using Alice's private key. Bob can decrypt it using Alice's public key.

Then, Bob needs to decrypt the session key Alice generated (the private key for their symmetric encryption) that was encrypted using Bob's public key. Only Bob can decrypt this (only he holds Bob's private key!)

Now Bob has a decrypted session key, and a hash of a message Alice wants to send (presumably containing authentication data). The message Alice sent was encrypted using the session key. Bob initializes his symmetric encryption using the session key and then decrypts the encrypted message Alice sent.

To finally verify the integrity of this correspondence, Bob must take a hash of this newly decrypted message. If it is the same as the decrypted hash he got from Alice, a secure connection is established! Alice is really Alice, and Bob is really Bob! Finally. This is the point at which you can assume Alice is who she really says, and Bob is who he really says.

Now that Alice and Bob have established a secure connection, do they only need to use symmetric encryption for communication?

Hell no.

They don't need to use RSA anymore (it's slow), but they still need to send hashes of messages! How can you verify that a malicious 3rd party is not intercepting messages between Alice and Bob, and changing them to gibberish (after all, this 3rd party doesn't know what they're actually saying unless private keys have been compromised)?

The answer is to generate a hash for each message, and then encrypt both the hash and the message and send them.

Since the hash is encrypted, a malicious 3rd party can't just substitute it with their own hash (it will get garbled when Alice or Bob receive the message and attempt to decrypt it). When Alice or Bob receive a message, they can decrypt it to obtain the plaintext hash and plaintext message. They can then compute the hash for the message and compare it with the hash they received. If the hashes aren't the same, it can be concluded a malicious 3rd party tampered with the data. Throw it out!

In RSA can public keys be used to encrypt/decrypt the same info? And private keys?

No, RSA is a one way street (so to speak...) Information encrypted with the public key can only be decrypted with the private key. Information encrypted with the private key can only be decrypted with the public key.

The public key cannot decrypt information encrypted with the public key.

The private key cannot decrypt information encrypted with the private key.

The example keys that webpage gave me to use were too simplistic. Instead, I tried using the pair (3,667) for the public key and (5955,667) for the private key. These worked better.

If I encrypt the number 100 using the public key:

``````100^3 mod 667 = 167

// if I attempt to decrypt this using the public key again, this happens:

167^3 mod 667 = 469 // << WRONG!! the decrypted value should be 100

// if I attempt to decrypt this using the private key, this happens:

167^5955 mod 667 = 100 // Hoorah! I got the right data!
``````

The same outcome occurs when I switch the role of the private and public keys. It is important to choose strong keys for RSA!

Alright I think that's it. If anyone would care to correct any mistakes I made, that would be appreciated.

-

To make the digital signature for the message, Alice encrypts the hash value of her message with her private key. Why did Alice do this?

Think of what we want out of digital signatures:

1. Only Alice should be able to sign a message.
2. Everyone else should be able to verify the signature.

This means that the act of signing a message should require Alice to make use of a secret that only she knows. Her public key doesn't meet this criteria, but her private key does. On the other hand, anyone should be able to verify the signature, and so Alice's public key works for this.

Digital signatures and encryption are very different things. Try not to get distracted by the fact that they can use similar mechanisms under the hood.

How safe is it to use private keys for encryption? Is this the only case where it is acceptable (to send a hash of a message)?

That being said, you are right to be suspicious of the fact that signing a message involves "encrypting" a hash with Alice's private key. For example, we typically want encryption to be secure under chosen plaintext attacks; but if Eve can somehow convince Alice to encrypt a hash using RSA, then Eve can forge Alice's signature on the corresponding message. "Recycling" keys in cryptography is a big no-no because of attacks like this.

But in practice, the only thing Alice will encrypt using her private key are session keys and hashes, and neither type of data will be encrypted directly --- it will be preceded by some bytes that indicate what type of data is being encrypted. This way, Eve can't try to pass off one for the other.

Is this session key the private key in symmetric encryption (i.e. this is how they securely transfer their shared private key to begin using AES for example)?

The short answer is yes. At least, this is the case for, e.g., PGP. (Note that it's not customary to call it a "private key", since it's less confusing if we reserve that term for asymmetric encryption.) There are other protocols that allow Alice and Bob to agree on a session key, such as Diffie-Hellman.

Should Bob respond by only using the session key Alice sent to encrypt his message (no more RSA and hashing). Is it safe to assume Alice is who she really says, and Bob is who he really says at this point? Or does Bob need to first respond and somehow confirm he is in fact Bob?

The answers to these questions are mostly "it depends". You've left the realm of signatures and encryption, and are now asking questions about protocols. For example, when you visit a secure website using SSL, your browser authenticates the web server, but not the other way around. (If you log into an account, the web server is authenticating you, but this is an entirely separate protocol that takes place on the application layer rather than the transport layer.)

You can have a protocol that allows Bob to prove his identity, but you don't always need to. Further, supporting this two-way authentication comes at a price: Bob will have to have his own public/private key pair, and Alice will need some way of getting his public key beforehand (which may need to be signed by a certificate authority, etc.).

And should the session key change after each message (does this make their correspondence safer)?

As the name suggests, a session key is good for a session. In general, it doesn't change after each message. Renegotiating keys would add a high amount of overhead. It can also introduce security problems. In theory, encrypting huge amounts of data (terabytes or more) using the same AES key can result in a gradual loss of security. In practice, this isn't an issue.

The problem is, I can encrypt a string of data using any one of the pairs and decrypt it using any one of the pairs! This means I can use the public key to encrypt something... And then use the very same public key to decrypt that something!

This is false.

I think that messages encrypted by the private key can only be decrypted by the public key (the private key can't decrypt its own messages) and messages encrypted by the public key can only be decrypted by the private key (the public key can't decrypt its own messages). Is this correct[?]

Yes, that is correct.

This is a consequence of the fact that if M is the message, d is the public exponent, and e is the private exponent, then

``````M = (M^e)^d = M^(ed) = (M^d)^e (mod N),
``````

but (M^e)^e is not equal to M, and neither is (M^d)^d.

Edit: It seems you answered your own question while I was writing a response. But I would like to comment on some of your additions.

What makes one private and one public is the fact that you keep one private and decide to hand the other one out.

Also, the public exponent is usually very small. This makes it fast to use, but also means it would be easy to bruteforce. (In fact, it's value is often standardized.)

They don't need to use RSA anymore (it's slow), but they still need to send hashes of messages! How can you verify that a malicious 3rd party is not intercepting messages between Alice and Bob, and changing them to gibberish (after all, this 3rd party doesn't know what they're actually saying unless private keys have been compromised)?

The answer is to generate a hash for each message, and then encrypt both the hash and the message and send them.

Not quite. Just like you can encrypt things using either public key or symmetric key encryption, you can also authenticate messages using public key or symmetric key cryptography. And symmetric key authentication will be faster.

Simply hashing the message won't necessarily be secure. Instead, you use a keyed hash, also called a message authentication code (MAC). You can, however, build MACs out of hash functions using HMAC (giving us HMAC-SHA1, HMAC-SHA2, HMAC-MD5, etc.).

-
Thanks for the answer I'll read through this now, but I have an additional question. I just learned about HMACs and their role in message integrity and authentication.. Would an HMAC be better suited than just a hash in this situation? I don't really see how a hash can be compromised? – user3100783 Jan 6 '14 at 3:17
Ok it appears your edit has addressed this as well! Nice – user3100783 Jan 6 '14 at 3:23
It seems we just keep missing each other. I touched on HMACs in my answer. The reason HMAC (as opposed to a simple hash) is necessary is because most encryption algorithms are, to varying degrees, malleable. That is, they'll stop Eve from learning about the message's contents, but it won't stop her from tampering with the ciphertext in such a way that the decrypted plaintext changes in ways she can control. Your statement that "[the hash] will get garbled when Alice or Bob receive the message and attempt to decrypt it" can actually be false! – Seth Jan 6 '14 at 3:28
Ok I think I understand why using hashes alone aren't secure. I don't really know the ins and outs of HMAC yet though. Are there any gotchas for generating a secret key (what algorithms should I use, supposing I want to use HMAC SHA256)? Also, I just replace the hash in the message with an HMAC (using the hash as input) correct? And should I send the private key for HMAC using RSA (Alice generates, sends to Bob using Bob's public key for encryption)? Lastly, where do salts play into this? Do I salt the hash? Or the plaintext? Or not at all when I use HMAC? Thank you! – user3100783 Jan 6 '14 at 3:40
May I recommend crypto.stackexchange.com. – Seth Jan 6 '14 at 4:11