Main content
Course: AP®︎/College Computer Science Principles > Unit 7
Lesson 5: Data encryption techniquesPublic key encryption
On the Internet, two computers often want to exchange secure data with each other. When I type my password into the Khan Academy login screen, I want my computer to send that data safely to the Khan Academy servers. I do not want to worry that an attacker might be monitoring my Internet traffic and watching the password go across the wires.
Symmetric encryption techniques rely on both the sender and receiver using the same key to encrypt and decrypt the data. How can my computer and the Khan Academy server exchange the key securely? If an attacker can see my password go across the wires, then they can also see an encryption key!
Public key encryption to the rescue! It's an asymmetric encryption technique which uses different keys for encryption and decryption, allowing computers over the Internet to securely communicate with each other.
Let's step through the high-level process of public key encryption.
Step 1: Key generation
Each person (or their computer) must generate a pair of keys that identifies them: a private key and a public key.
You can generate a pair below, using the same RSA algorithm that's used by your computer:
Did you notice it takes a few seconds to generate the keys? That's due to the math involved. The keys are generated by multiplying together two incredibly large primes. The algorithm repeatedly generates random large numbers and checks if they're prime, until it finally finds two random large primes. All that checking for primes can take a while, and these keys are only 512 bits long. The current nationally recommended key length is 2048, or even 3072 bits.
Step 2: Key exchange
The sending and receiving computers exchange public keys with each other via a reliable channel, like TCP/IP. The private keys are never exchanged.
Step 3: Encryption
The sending computer encrypts the secret data using the receiving computer's public key and a mathematical operation.
The power of public key encryption is in that mathematical operation. It's a "one-way function", which means it's incredibly difficult for a computer to reverse the operation and discover the original data. Even the public key cannot be used to decrypt the data.
You can try it out below, with the public key you generated above:
Step 4: Sending encrypted data
The sender can now safely transmit the encrypted data over the Internet without worry of onlookers.
Step 5: Decryption
Now the receiver can decrypt the message, using their private key. That's the only key that can be used to decrypt the message (in the world!).
Try it out below, with the encrypted message and private key from above:
Once you successfully decrypt the message, try decrypting it with the public key. It won't work; only the private key can decrypt it.
But how is that possible?
It may sound too good to be true; that it's possible to encrypt something with one key that can only then be decrypted by a different key. For a long time, mathematicians weren't sure if it was possible, but fortunately they discovered a way in the 1970s.
The math of the one-way function relies on prime numbers, the difficulty of factoring large primes, and modular arithmetic. If you'd like to dig deeper into the math, check out the Khan Academy tutorials on modern cryptography.
Fortunately, all of us can use and benefit from public key cryptography without needing to understand the complicated math behind it. In fact, we likely use public key cryptography everyday as we use computers and the Internet. Just imagine, what would the world be without it?
🙋🏽🙋🏻♀️🙋🏿♂️Do you have any questions about this topic? We'd love to answer—just ask in the questions area below!
Want to join the conversation?
Is all data sent on the internet due to regulations automatically encrypted?
When getting other's public keys, generating private keys, and decrypting data, when does all this happen, because I now know that my computer does this but I have no idea when it is all this going on. Is it like when I type in someone's email address? Is the address a public key? If so, is the email address like a way humans can remember the public key like domain names instead of typing IP addresses?
Does every computer have its own designated keys, or do they change like IP addresses?
Hope this is not too confusing to answer.(5 votes)
This is a great question!
All data sent over the Internet is not encrypted. Only if you use certain protocols like HTTPS will it be encrypted. There is no regulation requiring all data to be encrypted.
A person's email address is not a public key. Every computer has the ability to create its own keys, but when you get a new computer, it doesn't magically already exist. You have to generate it. Once it's generated, keys don't change. You can always generate a new set of keys though.
One way I find it easy to think about is the following:
Think about your home. If someone sends you mail, do they need a key to your home to put it inside? No, they could just slide it under the door or put into your mailbox. When you reach home, you can unlock your home and read the mail.
This is why as users we don't have to generate keys with our own computers. In some sense, we just send mail to servers by slipping it underneath their doors (via a public key encryption) and they can read it via a private key decryption.
I hope this helps!(7 votes)
When I encrypt something using my public key, eg "Hi" it seems like it can have many different encrypted forms. How is this possible?(1 vote)- This occurs because each encryption takes in some amount of randomness. So encrypt("hi") and encrypt("hi") are different because each encrypt() call uses different randomness.
Imagine a world in which this wasn't the case. In other words, encrypt("hi") and later encrypt("hi") returned the same thing. Then, you could create replay attacks. The different encrypted forms help prevent this.
See here for more. https://www.kaspersky.com/resource-center/definitions/replay-attack
Hope this helps!(7 votes)
I don't get how the private and public key looks like a mess. Shouldn't the private and public key just be a number? Then what is all those symbols doing in the private and public key?
-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgH1gajwsAHgJKHD7QEFpzWRSbqA2SxdwpmC/QEdqGZpn4ueGI_REMOVED_SOMEPF4TzF/VAPlJ4IJ6f39oohZU27If3jqStYYY2ctwsQ==
-----END RSA PRIVATE KEY-----
P.s. I went through the math but at no point is it mentioned how this strange looking key was derived.(2 votes)- For convenience, the RSA private key is represented with text. It makes transferring and comparing the keys easier for people. This large text is indeed a large number as there is a one-to-one well-defined encoding between every letter and number. ASCII is one such encoding.(4 votes)
What I wanna know is: The whole public key process, how it really works in a real life situation.
The receiver shares their public key so the sender can encrypt with it, and then it decrypts it with it’s private key, the only thing that can decrypt it...
But in what way does this process happen?
Do they need eachothers public keys for the entire process until TCP/IP disconnection?
Does every step in the communication require another key?
Do you always have the same public key on your machine or when does it change?(2 votes)
A common scenario is for a party to publish their RSA public key. Then, when someone communicates with that party, they create an AES key and encrypt it with the RSA public key. The encrypted AES key is sent over to the party who then decrypts it with their RSA private key. After that, the remaining messages are encrypted with the AES key for the rest of the session.
AES encryption is used to encrypt the majority of the messages as it is significantly faster than RSA encryption.(2 votes)
- What format is the encrypted output? is it base64?(1 vote)
- In step 1, it is mentioned that the generated keys are only 512 bits long. However, using a character counter, I counted the first key generated and it was 824 characters. How is that 512 bits? am I misunderstanding something?(1 vote)
Great question! The reason for this is the difference between bits and characters. In a computer, a character is represented as a byte (or 8 bits). So, if a key is 512 bits long, that does not mean it is 512 characters long.
The 512 bits refers to the length of the binary representation of the key. When this binary sequence is encoded as text (for example, using Base64 encoding, which is common for keys), it will indeed be longer than 512 characters.(1 vote)
- can someone please make this a bit more understandable because i am not 100% sure i understand all of it(0 votes)
When we transfer data to others, the data may be intercepted by attackers. Therefore, we want to encrypt the data so that the attacker doesn't know what it is, but the person we sent the data to know what it is.
Public key encryption makes use of 2 pairs of keys, each pair for each side. The pair of keys is special. You can think of it like having a lock, but you can use either one to lock, and use the other one to unlock. Note you cannot use the same key to lock & unlock.
Let's use a process of us sending data to others to demonstrate.
First, we have a private key. This key is hidden, and shouldn't be exposed to the public. Now, you can encrypt the data using this key.
Then, you place another key in the public (For simplicity, everyone can access it). This is called the public key.
Following this, find the public key of the target you want to send the data to. Encrypt the data using that public key.
After that, send the encrypted data to the target. Since the data is encrypted using your private key and the target's public key, attackers cannot intercept the data. Even if the attacker has your public key, they still don't have the target's private key.
Last, the encrypted data is sent to the target.
They first verify your identity using your public key. Note public key not only serves as an encryption method, but also an identity verification.
If it matches, then they first decrypt the data using your public key. Last, they use their own private key to decrypt the data.(3 votes)
Are the public and private keys fixed or dynamic for a device connected to internet? Should one of the keys change result in another one change accordingly? Thanks.(1 vote)- A device can have multiple public-private key pairs. When connecting to a device over the Internet, the key pairs are usually fixed, but it's possible for it to be dynamic. The public key for a server can be found in its web certificate (over HTTPS), and the private key is secret.
Also, keys form a pair, changing one of the keys changes the pair and hence the other one should change accordingly.
Hope this helps!(0 votes)
Some descriptions of the public key encryption method also mention a "hash function" being applied to the plain text before it is encrypted with the private key ?
What is the purpose of the hash function ?(0 votes)- A hash function gives an output from a limited range of values when it is given some input. Most hash functions that are used give pseudo-random outputs. (The output is pseudo-random because it is difficult to predict what the output will be when we know the input. However, the hash function will always give the same output when given the same input.) For example, the modulus function is a hash function because x mod n will always give a value between 0 and n.
Hash functions have a variety of uses, such as providing a way to find elements in a hash table data structure. Hash functions can also be used to verify data integrity. Suppose Bob wants to send a message labelled M to Alice. Bob can apply a hash function to M to get hash(M). Now, Bob sends both M and hash(M) to Alice. Alice will then apply the hash function to the message she received and compares it to hash(M). If the result of the hash function Alice used matches hash(M), then she likely received the correct message. If the results are different, then the message was corrupted or changed in some way during transmission.(1 vote)
- Can you relate to the mathematicians that invented this RSA algorithm?
It sounds very interesting(0 votes)