In this lesson we will learn about Asymmetric Encryption
(also called Public-Key Encryption).
Asymmetric / Public-Key Encryption allows us to establish
secure communications even when we have no opportunity to agree
on a secret key ahead of time or via another communication channel. This is crucial for secure transactions over the
Internet. Additionally, asymmetric/public-key encryption will
provide us with a mechanism to digitally "sign" files, which
allows us to provide Non-Repudiation.
Limitations of Symmetric (Secret Key) Encryption
- The Problem. The fundamental limitation of symmetric (secret key) encryption is ... how do two parties, who haven't previously communicated, agree on and share an encryption key? Let's call the two parties 'Alice' and 'Bob'. There is a third party, an eavesdropper, who we'll call 'Eve' (generally representing anyone who can intercept traffic). In order for Alice and Bob to communicate securely they need to agree on a secret key. In order to agree on a secret key, they need to be able to communicate securely. In terms of the Pillars of Cyber Security, To provide Confidentiality, a secret key must first be shared. But to initially share the key, you must already have Confidentiality. It's a chicken-and-egg problem.
- This problem is especially common in the digital age. We constantly end up at websites with whom we decide we want to communicate securely (like online auction sites) but with whom we there is not really an option to communicate "offline" to agree on some kind of secret key. In fact, it's usually all done automatically browser-to-server, and for the browser and server there's not
even a concept of "offline" — they only exist online. We need to be able to establish secure communications over an insecure channel. Symmetric (secret key) encryption can't do this for us.
Asymmetric Encryption (Public-Key Cryptography)
Asymmetric encryption is a big topic. It gets used in lots of
interesting ways — often in combination with hashing
secret key encryption, as we'll see.
You might like to check out this
overview of asymmetric encryption/public-key cryptography and how it's
- In asymmetric encryption, both communicating parties (i.e. both Alice and Bob) have two keys of their own — just to be clear, that's four keys total. Each party has their own public key, which they share with the world, and their own private key which they ... well, which they keep private, of course, but more than that, which they keep as a closely guarded secret.
- The magic of public key cryptography derives from three important points:
- A message may be encrypted with a private key and then decrypted with the corresponding (paired) public key, OR it can be encrypted with a public key and then decrypted with the corresponding private key. Either key may be used for encryption or decryption (Some public-key cryptography algorithms, including the RSA algorithm that we'll cover in some depth, have the special property of being commutative, which means that the roles of private key and public key are interchangeable), but they only work in pairs:
- A message encrypted with a certain public key can ONLY be correctly decrypted with the corresponding private key, and vice versa.
- Because only the private key needs to be protected, public keys can be shared openly (even to Eve), and therefore the limitation of symmetric encryption is alleviated.
- Encrypted Communications. In this scenario, Alice encrypts her message with Bob's public key, and Bob decrypts the message with his private key. Alice can rest assured that only Bob can decrypt the message she sends, because she has encrypted it with his public key. Only Bob's private key can correctly decrypt the message.
Note, however, that while this provides a solution to Alice's confidentiality problem (she knows only Bob can read the message), Bob has an authentication problem on his hands. Yes, he's received a message only he could read, and the message claims to have been sent by Alice, but he has no guarantees that it really did come from Alice. Anyone can send a message to Bob using Bob's public key, since it's freely available.
- Authenticated Communications. In this scenario, Alice encrypts her message with her private key. Bob decrypts the message with Alice's public key. If the message correctly decrypts with Alice's public key, Bob knows that the message could only have been encrypted by someone possessing Alice's private key. This establishes that the message must have been sent by Alice (assuming no one has stolen Alice's private key).
Bob's authentication problem is solved. However, Eve, or anyone else seeing the encrypted message, could decrypt it using Alice's public key, which is freely available, so the message's confidentiality is not guaranteed. Can we combine the first two techniques, and achieve both authentication and confidentiality? Sure!
- Confidential and Authenticated Communications. In this scenario, the previous methods are combined. Alice encrypts the message first with her private key, then Bob's public key. Bob decrypts the message, first with his private key, then with Alice's public key. Now, both authentication and confidentiality are achieved!
RSA (Rivest, Shamir & Adleman) Encryption
- General. The RSA encryption scheme provides commutative, asymmetric encryption.
- Math Description. The public key consists of two large integers (e,n) and the private key consists of two large integers (d,n). Note that the second number, n, is the same in both! The three numbers e,d,n are related in a special way, which requires a bit more mathematics to go into. The crucial point is that n is guaranteed to be the product of two prime numbers, i.e. n = pq for two primes p and q. If you know e and n, and you've found the factorization of n into pq, you can compute d easily. So the security of RSA requires that factoring a large integer is difficult. And when we say large, we're not kidding! Today, RSA implementations might use a 4096-bit number for n. Nobody currently knows how to factor numbers of that size quickly, which is to say before we and our planet are long dead, so RSA seems pretty secure. However, nobody has formally, mathematically proved that it's impossible to factor numbers quickly either, so RSA may be broken some day.
- Check out the SY110 RSA Demo Page, which is also linked off of SY110 Resources. Try to encrypt a message as if you were Alice and decrypt the message as if you were Bob. Note that this tool generates just a 128-bit key, which is nowhere near a length that is currently considered to be secure.
The Security of RSA
- Finding the Prime Factors of the Modulus. We won't go into too much detail about how RSA works: block size, padding schemes, key-generation etc., even though getting these kinds of details right when implementing RSA is actually tricky. However, it is important to understand one fundamental fact: it is always possible to crack RSA by computing someone's private key from their public key. All it it takes is being able to factor the modulus (the number n that's common to both the public and private key) into its two prime factors. However, if the modulus is big enough, even though it will be possible to do the factorization, it will not be feasible — meaning that the time/computing-power required to do it is simply too great. After all, if Eve dies of old age before her computer factors the modulus from Bob's public key, it doesn't do her a lot of good.
Your CAC knows crypto.
Your CAC supports a number of different cryptographic
Symmetric encryption: AES-256
Asymmetric Encryption: RSA-2048
... and others.
Included on your CAC are public/private key pairs that you
can use to decrypt e-mails intended only for you, and to
digitally sign documents.
- Just Increase the Key Size. The power of RSA, and the reason that even though it has been in use since the 1970's, stems from the fact that as computers and algorithms get faster, it becomes feasible to factor bigger and bigger numbers, we can simply use bigger (and therefore harder to factor) numbers for the moduli in our RSA keys. Moreover, increasing the size of the modulus even a relatively small amount vastly increases the difficulty of factorization.
- "N-bit" RSA means n bits in the modulus size. Generally, when you read n-bit RSA it means that the modulus (the number n that's shared by the public and private keys) is N-bits long. In 1990, 512-bit RSA keys were deemed pretty secure. In the intervening years, the computing power of a typical desktop computer has increased several thousandfold. Still, today 2048-bit RSA is deemed pretty secure. That means that we've only had to increase our RSA key size by a factor of four to make up for the more than 1,000-fold increase in the computing power of a typical desktop PC. If you are really worried about security, simply increase the bit-size of your RSA keys!
Digital Signatures Intro
- Suppose Alice sends a contract agreement to Bob. To avoid legal troubles, we'd like this communication of contracts to have the property of non-repudiation — Bob should be assured that Alice can't back out of the deal by claiming she never sent the contract. Likewise, we want the property of integrity — Alice should be assured that Bob can't modify the contract and claim that the modified version is what Alice sent him. There's a nice technique called a digital signature that provides these guarantees.
- The Signature. Alice does the following:
- Computes the hash of the contract agreement
- Encrypts that hash with her private key
- Sends the result (which is the "digital signature"), along with the contract (which itself need not be encrypted), to Bob.
- The Check. Anyone can take the contract, hash it, and compare the result with what you get when you decrypt the digital signature with Alice's public key. If it matches then the contract must be exactly the same as what Alice sent, because:
- Alice must've sent it, because only Alice can encrypt something that decrypts properly with Alice's public key.
- The contract can't have been modified, because the hash value would've changed.
Man-in-the-Middle Attack Intro
- The Problem. Asymmetric encryption is almost magical — you create security out of insecurity. However, there is still one weakness in the system that's fundamental: certifying the connection between a public key and its associated identity.
- Example. Suppose you see on a website something like
Hi, I'm Bob and my public key is
How do you know that public key really belongs to the guy you know as "Bob"? While you can be assured that, if you encrypt a message with this key, only the key's owner will be able to decrypt it, how can you be sure that the key's owner is really "Bob"? If you trust the website on which the public key is posted, you might be comfortable. But at the end of the day, you have to trust whoever is presenting this key as belonging to "Bob", and that trust is a security weakness. It's an inescapable weakness, but one that we'll try to control and minimize in the Digital Certificates lab.
- Foreshadowing: the Man-in-the-Middle Attack. Eve, our nefarious eavesdropper, might listen in on an encrypted conversation between Alice and Bob by misrepresenting which keys belong to which people. Later in the course, we will go through this process in detail. It's called a man-in-the-middle attack.