cs387 ยป

Contents

- 1 CS387 Unit 4
- 1.1 01 l Asymmetric Cryptosystems
- 1.2 02 q Private Messages
- 1.3 02 s Private Messages
- 1.4 03 q Signatures
- 1.5 03 s Signatures
- 1.6 04 l One Way Function
- 1.7 05 l RSA Cryptosystem
- 1.8 06 q Small M
- 1.9 06 s Small M
- 1.10 07 q Correctness of RSA
- 1.11 07 s Correctness of RSA
- 1.12 08 q Eulers Theorem
- 1.13 08 s Eulers Theorem
- 1.14 09 s Totient Function
- 1.15 10 q Proving Eulers Theorem pt1
- 1.16 10 s Proving Eulers Theorem pt1
- 1.17 11 q Proving Eulers Theorem pt2
- 1.18 11 s Proving Eulers Theorem pt2
- 1.19 12 q Invertibility of RSA
- 1.20 12 s Invertibility of RSA
- 1.21 13 q Picking e and d
- 1.22 13 s Picking e and d
- 1.23 14 q Compute e
- 1.24 14 s Compute e
- 1.25 15 q Compute d
- 1.26 15 s Compute d
- 1.27 16 q Security of RSA
- 1.28 16 s Security of RSA
- 1.29 18 l Computing d still hard
- 1.30 19 q 40 Quadrillion Years
- 1.31 19 s 40 Quadrillion Years
- 1.32 20 l Factoring is still hard
- 1.33 21 q Optional: Complexity
- 1.34 21 s Optional: Complexity
- 1.35 23 q Small messages
- 1.36 23 s Small messages
- 1.37 24 l Thwarting Guessing
- 1.38 25 q Back to signatures
- 1.39 25 s Back to signatures
- 1.40 26 l Summary

Welcome to unit 4. Unit 4 is all about asymmetric cryptosystems. We started talking in unit 3 about the paper that Diffie and Hellman wrote in 1976 that introduced the idea of an asymmetric cryptosystem. They didn't figure out how to build one quite yet. They did figure out that key exchange protocol that we focused on in unit 3. What we'll do in unit 4 is talk about the first successful asymmetric cryptosystem, which is called "RSA," which is named for its inventors-- Ron Rivest, Adi Shamir, and Leonard Adleman. We'll look at how asymmetric cryptosystems can be used that we'll see how RSA is constructed, and we'll go in a fair bit of detail of why RSA works and why people believe it is secure. Then we'll look at some of the problems that happen when people use RSA in practice. Finally, we'll start talking about applications of asymmetric cryptosystems. We won't get too far in applications in this unit, but that'll be the main focus of unit 5. All the cryptosystems we've talked about so far have been symmetrical. What that means is that the key used for encryption, and the key used for decryption are the same. This lead to the problem that we talked about in the previous unit about how do you distribute this key between two parties, but even if you can solve that problem using the same key for encryption as you do for decryption limits what you can do with a cryptosystem. With an asymmetric cryptosystem we have different keys for encrypting and decrypting. We'll call one of those keys ku--the u stands for public-- and the other key kr--the r stands for private. Unfortunately, both public and private start with the same letter p. That's why we use u and r to distinguish the two keys. Public is a bit of a misnomer here. What we really mean is this key does not need to be kept secret. It's still very important that it's generated in a particular way and it's associated with the right identity. Before we get into the scheme for actually building a cryptosystem like this, and until one is actually built, it seems like this should be impossible. If we reveal the way we do encryption, that seems like we also reveal the inverse. The way to do decryption. For the cipher to be correct, decryption must be the inverse of encryption. For most functions when you reveal how you compute the function in one direction, that also reveals how to compute the inverse.

Now let's look at a couple applications, if we could build a cryptosystem like this. First we'll look at a standard use of it to send private messages. This is what our goal was initially for the symmetric cryptosystems. That assumed that we had a shared key to begin with. Now let's assume that we don't. Let's assume Alice wants to send a private message to Bob. She doesn't have a secure channel, and she doesn't have a key shared with Bob, but she does know Bob's public key. We'll call that KUB. Bob knows his private key that corresponds to the public key that Alice as well as anyone else who wants to know knows is associated with Bob. Now Alice can send a message to Bob, encrypting it with Bob's public key knowing that the only one who can decrypt it is someone who knows Bob's private key, which should be only known to Bob. Bob decrypts the message using his private key. Now we'll have a quiz to see that everyone is understanding asymmetric cryptosystems. What correctness property does this rely on? Here are the three choices. Pick the one that this private messaging system is relying about the E and the D functions.

The answer is it's relying on the third property that decrypting with the private key is the inverse of encrypting with the public key. The second property turns out to be one that's also very useful It's not necessary for this use of asymmetric cryptosystems, but it is necessary for other uses. Many asymmetric cryptosystems, including RSA also provide this property.

An important application of that is to do digital signatures. We think of physical signatures as authenticating documents. When something is signed, that means that the signer is responsible for the message in the document. Physical signatures don't actually work very well for this purpose. Someone can cut and paste a physical signature or maybe they can modify the document after it's signed. There's nothing that really guarantees that the signature and the document are matched. What we want with digital signatures is something much stronger than that. We want something that shows that the person who signed it agreed to the message, and the message can't be changed without also breaking the signature. How can we do that with asymmetric cryptography? Here is our goal: we want Alice to be able to sign a message, transmit that message to Bob, Bob should be able to read the message. and know that it could only have come from Alice. The question is what should we use for the respective keys k1 and k2 in order to provide that digital signature where the message that Bob receives proves that it was signed by Alice? Here are the choices. We've used for k1 Alice's public key and k2 Alice's private key. For the second choice we'll use Bob's public key for k1 and Bob's private key for k2. For the third choice we'll use Alice private key for k1 and Alice's public key for k2.

The answer is the third choice. The first choice doesn't work, because it assumes Bob knows Alice's private key. If Bob knows Alice's private key, then it's not Alice's private key anymore. The second choice doesn't work because the message is being assigned using Bob's public key. There's nothing that proves that it came from Alice. In the third choice, the message is being encrypted using Alice's private key, which only Alice should have. Anyone who has Alice's public key, which includes Bob, can then decrypt the message. Then if it decrypts to a reasonable message, they know that it came from Alice. The correctness of this depends on the inverse property that we saw on the previous quiz. That in order for signatures to work, we need to be able to do encryption and decryption in the reverse order and have them still be inverses using the appropriate private key private key for decryption and public key for encryption.

There are lots and lots of other interesting applications of asymmetric cryptography. We'll see some of those later in unit 5, but for now I want to focus on how to actually build an asymmetric cryptosystem. What we want to build is what's known as a "trap door" one-way function. A one-way function would be a function that is easy to compute in one direction and hard to compute in another direction. With asymmetric crypto we need to reveal this function. We want the reverse to still be hard, but we want some way to be able to do the reverse easily if we know some secret. That's our trap door. We want to be able to--if you have some secret key, you can do the inverse. If you don't, you can't. That's what makes an asymmetric cryptosystem. It's hard to do in the reverse direction unless you have this extra key. But revealing the easy way to do the forward direction does not reveal the easy way to do the reverse direction. Diffe and Hellman envisioned such a cryptosystem in the 1976 paper that we talked about last unit, but they didn't devise a function that had this property. The first cryptosystem to successfully have this property, is the RSA cryptosystem. That'll be the focus for the rest of this unit.

The RSA comes from the initials of its three inventors-- Ronald Rivest, Adi Shamir, and Len Adleman. One thing you'll notice in cryptography is many of the most important ideas are named after groups of people. We have Diffie-Hellman. We have RSA. We have Needham-Schroeder. We'll see lots of other examples. This is different from what we tend to see in mathematics where most of the big ideas have just one name. Cryptography is a very collaborative process. The way Rivest, Shamir, and Adleman worked together-- Rivest and Shamir came up with lots of ideas, trying to come up with ways to provide this public-key property, and Adleman would find the flaws in them. They kept trying this and eventually came up with the one idea that Adleman couldn't find any flaws in, and that's the one that we know of today as RSA. RSA was the first successful public-key encryption system. It's also one of the most widely used crypto systems and continues to be the most widely used public-key system today. The way it works is actually quite simple. We have the public key as a pair of two numbers, e and n, where n is the product of two primes. The secret key is a pair of two numbers. The n is the modulus, which is the same in both the public and the private keys. The difference is in the public key we have e. In the secret key we have a secret number d. To perform encryption of some message m, we raise m to the e power mod n. To perform decryption using the secret key, we have some ciphertext, which we raise to the d power mod n. That means encryption and decryption are the same functions, just with different powers that we're using, depending on whether we're using the public key or the secret key. RSA is a very important cryptosystem, but it's simple enough that we can fit the whole thing on one screen or even on a license plate. Unfortunately, in the state of Virginia, the license plates don't allow you to have exponents in them. If you live somewhere where you're DMV allows you to have exponents in license plates, that's great. You can get a much better version of this than I have. Actually understanding why it works and the argument that it's secure, require understanding some more things, and in particular, the we choose the values of e, d, n. In fact, we have to be careful how we choose the message as well.

To check that you understand how the crypto system works, we have a quiz. Suppose n has chosen to be 6371. That's 277 times 23, the two prime numbers. And I should emphasize that this is not a secure choice. For RSA to have any security, p and q have to be very large prime numbers, large meaning several hundred digits long, but to keep things simple, suppose we pick our n value as 6371. What is the maximum value of our message?

The answer is 6370. In order for this to work, well, we need a mapping. We need encryption to be invertible. Given that the output is mod n, we have output values that the possible values here would be from 0 to n - 1. We need to know that this mapping maps each message to a unique cipher text, otherwise they wouldn't be invertible. If 2 messages map to the same value, then we wouldn't know which to decrypt to. That would definitely be the case if we have more than the modulus number of values. That would mean that we've wrapped around and we've definitely used one at least twice. But as long as m and n are relatively prime, we should generate all the different values, so we can use each of these as different messages, but we should be very careful. What if the value m is 0? If m is 0 no matter what the exponent is, we still get 0 as our result. That's not a very good encryption function if the result doesn't depend on the key. The same thing if m is 1. We still get 1 as the output, and in fact, it's dangerous for any small value to use this encryption. And one reason you can see that--and we'll talk more about this later-- is the key is public. We're assuming that the adversary knows e, so if there's only a small possible set of m values, the adversary can just try them all and see which one maps, so it's very dangerous to use a small m as the input message for RSA. We'll talk more about that later, but first I want to talk about why RSA is correct and then why we think it's secure, at least when it's used in a very careful way.

First we're going to talk about correctness. The question is what property do we need in order for RSA to be invertible? And let me remind you the encryption and decryption functions. Here are the possible choices. Which one of these do we need in order for the RSA encryption system to provide the correctness property that we can invert messages encrypted with a public key by using the private key?

The answer is the second choice. What we want to know is that we can get the message back, so to get the message back. We started by encrypting the message. Then to decrypt it, now this is what goes in as the cipher text, so we're going to raise this to the d power mod n. And then if you remember when we looked at Diffie-Hellman, we have this rule for combining powers of powers, that this is equivalent to m to the ed mod n, and we want that to be equivalent to the message. If we divide both sides by m, this becomes 1. This becomes m to the ed - 1. We've reduced the power by 1 because dividing by m. This is the property we want. If we had this property, all messages would decrypt as one. That wouldn't be very useful. This property is always true but not useful, and this property is unlikely to be true. That means our goal is to select values for e, d, and n that satisfy for all m values, that m to the ed - 1 is congruent to 1 mod n. That's our goal. If we have that, we have the correctness property we need for RSA.

The main theorem that we're going to use to get that was devised by Euler, and the theorem is that if a and n are relatively prime, then a raised to the totient of n power is 1 mod n. I'll talk soon about what the totient means. If we can obtain this, then what we want to do is set ed - 1 is equal to the totient of n. Then we would have exactly the correctness property we need with the assumption that m and n are relatively prime. This is the totient function, and what the totient function means is the number of positive integers that are less than n and are relatively prime to n. We'll have a quick quiz to see that you understand what the totient means, and the question is what is the value of the totient of 277? And I'll point out that 277 is my favorite prime number.

The answer is 276, and I hope you didn't work this out by counting them all. There's an easy way to solve the value of the totient when n is prime, and that is if n is prime, that means that all of the positive integers less than n are relatively prime to n, so the totient of n is n-1 for prime number n.

The answer is 8. The easy way to see that is to observe that 15 is 3 * 5. That's a composite number that can be broken down into two primes. Then if we look at the numbers from 1 to 14-- these are all the positive integers less than n-- we want to figure out how many of these are relatively prime. The multiples of 3 are not. You can cross all those out. true for the multiples of 5 as well. The multiples of 5 are not. That leaves us with eight numbers. This works in general. If we know that n is the product of two primes. Then we could compute ph(n). It's the number of integers less than n, which is also pq - 1. That would be all the integers. Then we subtract out all the multiples of p that are less than n. Since n is pq, there are q - 1 of those. Then we want to subtract all the multiples of q less than n, which is again pq, so there are p - 1 of those. If we do the algebra, we get pq - (p + q) +1, which we could also write as (p -1)(q - 1). Since p and q are prime--and this property depended on q being prime. Otherwise, some of these multiples might have collided. Since they are prime, we know they didn't. That means that we know that ph(n) is equal ph(p)ph(q). This is going to turn out very useful for RSA. The reason for that is if we know the factors of n, we have an easy way to compute the value of ph(n). But if we don't know the values of p and q, it appears to be hard to compute the value of ph(pq). That's the crux of what the security of RSA relies on, and we'll talk more about that later. For now we're still focused on correctness.

Remember what we wanted to prove was that a\^ph(n) is congruent to 1 mod n. Now you should understand what the totient function means here. First we're going to look at a different theorem, which we've already used, that's very similar. This is Fermat's Little Theorem, which is a\^(n - 1) is congruent to 1 mod n as long as n is prime and a is not divisible by n. We used this in the previous lecture when we talked about finding large primes. This was the basis of the primality test. We didn't prove it, though, and it's actually fairly straightforward to prove. So let's see if we can prove that Fermat was correct. The question is what is the value of this set where we're taking a mod n, You have four choices.

The answer is the first choice. We know that this is the case because this set has n - 1 elements. We also know that there are no duplicates in this set, because we know that n is prime and a is not divisible by n. That means that this will generate the numbers 1 through n - 1 in some order, some permutation of those, but since it's a set, it's the same as the set 1 through n -1. This turns out to be a useful property for proving Fermat's Little Theorem, because we can set these two things as equal and multiply all the elements in those sets. Since we know they're the same set, we know that their products are also equal. This product is (n - 1)!. Since the sets contain the same elements, we know their products also must be equal. So this is the product of the first set. This is the product of the second set. It's (n - 1)!, because it's multiplying all those numbers up to n - 1, and mod n--those must be equal. We took the mod n out of each of these terms, but that's fine. Then we can simplify this, taking out the a's. If we take out all the a's what we have is (1 * 2 * 3 * ... * n - 1)a still equal to (n - 1)! mod n. Now we can separate those, taking out all the numbers at all the a's, so we'll have n - 1 terms. We have n\^(n - 1) here times all the numbers is still equal to (n - 1)! This is the same as (n - 1)!. Now we can remove these terms, and we're left with exactly what we wanted-- that a\^(n - 1)! is congruent to 1 mod n. This is pretty close to what we want, but we needed for Euler's theorem and what we'll need for the RSA correctness proof is this property with ph(n). That's different from what we have here.

Let's look at the two cases. The first case is where n is prime. When n is prime, ph(n) is equal to n - 1, so we're done. We have exactly what we need for that from Fermat's Little Theorem. Case two is where n is not prime, but we know that a and n are relatively prime. In this case, we know since n is not prime, there are some numbers that are not relatively prime to n. Let's put those in a set. We'll call it R. We're going to multiply that set by a mod n to get a new set we'll call S. Now I have a quiz about R and S. Here are the choices. Check all of the statements that are true.

The answer is the first and the third are true. For the first one we know that the size of r is equal to ph(n). That's the way the totient is defined. It's the number of positive integers less than n that are relatively prime to n. That's exactly how we define r. The second one is not true. In order for this not to be true, it would mean that there is some element where a xi mod n is equal to axj mod n, but that's not the case, because a and n are relatively prime. We know that these values must all be different. The only way these could be equal is if xi is equal to xj. That means that the sets are the same size, and this set contains numbers only up to n - 1. This set also contains numbers from 1 to n - 1. That's why we know that s actually contains the same elements as r. It must be a permutation of r. Now we can use a similar idea to what we used in the proof for Fermat's little theorem. We can take the product of these two sets. Since we know the contain the same elements, we know their products are also equal. Here is what we get: the P(R) is equal to the xi's all multiplied together, which is equal to the P(S), which is equal to these values all multiplied together. We also know from this property that the number of terms is ph(n). That's true on both sides. That means we can separate out the a's from the x's. We're going to have a\^ph(n) times all the x's--still equal to this product. Now we can do the division. Removing the x's from both sides, we end up with exactly what we need, which is that 1 is congruent to a\^ph(n) mod n for any a and n where a and n are relatively prime.

Now let's recap RSA and see how things fit together. We have our modulus n, which is the product of 2 primes. We have our encryption function, which raises m to the e power, and we have our decryption function, which raise the cipher-text to the d power. For the invertibility property, we need to know that m\^(ed - 1) = 1 mod n. What we know from Euler is that that's true for a and n relatively prime. That means: If we can pick e and d such that ed - 1 is equal to a multiple of ph(n), then we're real close to having the correctness property we need. To see how close we are, let's ask a quiz whether we can determine if m and n are relatively prime. That's the property we need to be able to use Euler's theorem.

The answer is not necessarily. We can't guarantee that m and n are relatively prime. What we know is that n is pq, which are prime, and we know that m is less than n. But it's possible that m is some multiple of p or some multiple of q. Those could still be less than n if c1 is less than q or c2 is less than p, but that would mean that m and n are not relatively prime. That means that we can't use Euler's theorem directly. We'd have to deal with these special cases. That's a little kink in our correctness proof. I'm not going to go through those details. They're not too interesting, but we're real close, and we're going to assume that we can deal with this detail, and now we have the invertibility property that we need for RSA to be correct. One useful thing to notice here is that this works in both directions. What we wanted for signatures was invertibility where we do decryption first and then encryption.. That's equal to c\^de mod n, which is also congruent to c mod n. We'll have correctness in both directions.

We have one big issue left to resolve, which is how do we pick e and d to make this property true? For correctness what we need to know is that ed - 1 is equal to a multiple of ph(n), and we know since n is the product of the primes p and q that this is equal to (p-1)(q-1). The quiz is which one of these should be selected randomly-- either e, d, or it doesn't matter which one?

The answer is that it'd better be d. The reason for that a selected d determines e uniquely and vice versa. Hence, if one of these two parameters is selected, we have no choice about the selection of the other one. Since we must make sure that d represents a value hard to guess or to find, we have no other choice to select firstly the private key d (the private key includes the secret d). The public key includes e. If we want the private key to be secret and hard for an adversary to guess, it's got to include something that is unpredictable. That will be the value of d. N, again, is part of the public key, so that doesn't provide any security for the private key. Notice from this that since e is public, it's okay if e is computed in a predictable way. In fact, e is often chosen to be a small value.

We're going to start by picking a random d that has to be relatively prime to ph(n). We can pick random numbers and test that this property holds and pick again if it doesn't. Since d is relatively prime to the totient of n, that means it has a multiplicative inverse in that group. So we can find some value e such that d is equal to 1 mod ph(n). There exists some value e such that de is congruent to 1 mod ph(n). Now the question is given d and the totient of n is it hard to compute e? The choices are, yes, it'd better be hard. Otherwise RSA would be insecure. No, it's easy. We can use the extended Euclidean algorithm to do this. Or three--no, it's easy. We can just divide the ph(n) by d.

The answer is the second choice. The extended Euclidean algorithm does exactly this. It will give us that multiplicative inverse. We won't go through that in detail now. Maybe it'll be a good question for a homework problem.

I'm going to ask a slight variation on this question. This time you're given e and n and the question is is it hard to compute d. The answers are yes, otherwise it would mean RSA is insecure or no we can just compute the totient of n on the multiplicative inverse using using the extended Euclidean algorithm.

The answer is "yes." At least we hope it's hard to compute d. Otherwise, RSA would be insecure. This, of course, is only true if n is big enough and n is a product of two primes. The reason the no answer doesn't work is because actually doing the computation of the totient is difficult. If we don't know how to turn n into a factor of primes, then it's hard to compute this. We finished showing the correctness property for RSA. Now we're getting to the question of how can we claim RSA is secure. This claim that it is secure because otherwise it would be insecure is not a very convincing proof. That's what we're going to look at next.

Now we're going to look at whether RSA has the security properties we need. We've seen that it has the correctness property, that encryption with a public key and decryption with a private key are indeed inverses. But we want to know also the most important property-- that it's difficult for an attacker who doesn't have access to the private key to perform the decryption. This is the property that we need that given e and n, which is the public key, it's hard for an attacker to find d. We actually need stronger properties than just this. We want to also know that the attacker can't learn anything about the message. This is not strong enough by itself to know that an attacker can't learn anything about the message. In fact, we'll see there are cases where an attacker could learn something about the message without learning d soon. The first thing we know is that this would be easy for someone who knows the factors p and q--the two large primes that we multiplied to get n. We know that because such an attacker could compute the multiplicative inverse of e mod the totient of n. If you know the factors of n, you know the totient, because that would be the totient of p times the totient of q, which are both primes. So easily solved. Our security argument relies on two things. The first is that showing that all ways of breaking RSA would allow some easy way to factor n. If we could use that way of breaking RSA to factor n, the we could always use that to factor large numbers. That would contradict our second claim that factoring large numbers constructed by multiplying two large primes is hard. We're going to show the first thing first--that other ways of breaking RSA, other ways of finding d, would allow us to factor n. Then we're going to argue from experience and historical effort that factoring seems to be hard. The first question is whether it's easier to compute the totient of n than it is to factor n. Our goal is to show that that's not the case. What should we do to show that? Here are the choices. Give p and q, show that it's hard to compute the totient of n. Given the totient of n, show that there is no easy way to compute p and q. Or given the totient of n, show that there is an easy way to compute p and q.

The answer is we want to do the third thing. We want to show some way that if we had the totient of n we could also factor n. That would show that finding the totient is not easier than finding the factors. Of the other choices, the first one is actually not true. If we have p and q, it's actually easy to compute the totient of n, and it's easy because we know the totient of n is (p - 1)(q - 1). The second answer is not true, but if it were, it wouldn't help us prove that RSA is hard. It would just show that there might be an easier way to compute the totient of n than there is to factor. This would be damaging for our security proof. Fortunately, at least for the security of RSA, the third one is true, and next we'll show why.

The last thing that we need to show is there isn't an easier way to compute d than finding the factors of n. This follows from what we just showed-- that if we know the totient, we could easily find the factors, because the correctness of RSA depends on this property. That means that there is some integer k such that k * ph(n) is equal to ed - 1, which means that we already know the value of e. We're assuming now that we figure out a way to compute d. If we can solve this, then we know a multiple of the totient. Once we know a multiple of the totient, it's easy to find the factors p and q. If there were some easier way to find d than factoring the modulus, that would provide an easy way to factor. We finished showing that at least all the obvious mathematical ways of breaking RSA would easily allow us to factor n. This certainly doesn't cover issues in implementation or issues in weak choices of messages or keys, but assuming all of those things are good then we've shown that all the obvious mathematical ways to break RSA are equivalent to factoring n. That means if factoring is hard, breaking RSA would be hard. That's the second part of this claim--that factoring is, indeed, hard.

One way to convince people something is hard is to post a challenge, provide some motivation, and see if anyone can solve it. This particular challenge was posted in Martin Gardner's Scientific American column in an article that he wrote in August 1977 that was introducing RSA to a wide audience. The technical paper on RSA was published shortly after that in 1978. As part of this article, he asked for Ron Rivest to come up with a challenge. This was the challenge that was published in this article. Given a public key and an e--and here we have n as a 129-digit number-- and the intercepted cipher text, figure out what the message was. That can be done by factoring n. Ron Rivest estimated that factoring n would take about 40 quadrillion years. It turns out this was a little bit off. The actual time was 17--without the quadrillion--years. It was shown by a team lead by Derek Atkins in 1994 that these two numbers multiplied together to produce the n in the challenge. For the quiz, the question is what does this mean-- the fact that Derek Atkins and his team were able to break n into these two factors. This is kind of a silly quiz, but I hope you'll think about it anyway. Some of the answers are more serious than others. It could mean that RSA is fundamentally broken. It could mean that the magic words are "squeamish ossifrage." It could mean that RSA keys need to be longer than 129 for good security. Or it could mean that time flies when you're factoring,

The best answer is the third one. It definitely raises some concern that the time to factor is much less than what was estimated here but maybe that just wasn't a very good estimate to begin with. It doesn't mean that RSA is fundamentally broken. If we make our keys large enough, unless we understand more about the cost effector, maybe that's still good enough. So we'll talk about that next. It is the case that the message could be decrypted. Once you have these factors, it's easy to compute d. The actual message was "The magic words are squeamish ossifrage."

This gets back to the fundamental question we have of how hard is factoring. We saw that it was possible to factor 129 decimal digits in 1994. The computing resources to do this were about 1600 machines collaborating on the internet. Certainly that's much less than many people have access to today. There are larger numbers that have been broken since. The largest challenge that's been broken so far was RSA-768, which was a challenge. Those are bits instead of decimal digits. That's equivalent to 232 decimal digits. That was done in 2009 using about 2000 years of computational power. If we want to know that RSA is secure, we need to understand how the cost of factoring depends on the size of the numbers that we need to factor. We'd like to know that if we pick a large enough key, even an adversary with a large amount of computational power-- and as the years go on adversaries will have more and more power-- still won't be able to factor the number and break the RSA. We don't know any way to actually prove a problem like this is fundamentally hard. The best we can do is look at the best-known algorithms and have some confidence because people worked very hard to find better algorithms-- and progress has been slow--that, barring some very unexpected breakthrough, it won't bet much faster. This is quite unsatisfying, but it's the best we can do. To talk about this, I want to measure the size of the input. That's the number of bits--we'll use "b" for that--in the modulus. We could try a brute force approach, which would go through all the numbers from 2 up to the square root of n, checking whether each one is a factor. If it finds a factor, then it returns that. Let's be optimistic and assume, unrealistically, that we could do this factoring test which could be done by finding the greatest common divisor of the two numbers in constant time. Then we're going to need to go through this loop square root of n times, which means our running time will be linear in the square root of n, but b is the log of n. Our running time will be exponential in b/2. This clearly is not going to work for large b. But this is not the best-known factoring algorithm. The fastest known factoring algorithm as of 2012 when I'm recording this is what's known as the General Number Field Sieve. This is a bit faster than the brute force, but it's still essentially requires trying all possibilities. Its running time is exponential in b^1/3\ log\ b^2/3, which is still much worse than being polynomial. One important caveat--this is the best known factoring algorithm assuming a classical computer. If you have a large quantum computer, which no one does yet, there's a faster algorithm, which is known as Shor's algorithm, which was created by Peter Shor in 1994. That actually has a running time that's polynomial in the number of bits. This development, which we won't go into more depth in this class, is both why there's a tremendous amount of practical interest as well as theoretical interest in quantum computing. It seems to allow for some problems that seem to be hard a way to compute them more efficiently. This means that factoring is in a complexity class called "bounded error quantum polynomial time"--known as BQP. What's unknown is whether factoring is in the class NP-Hard, which are the hardest problems that can be solved by a non-deterministic Turing machine in polynomial time.

If you haven't had a theory of computation class, I'm not going to explain this now, but I hope some of you have had it and will be able to answer the next quiz, which is if it's proven that factoring is NP-hard, what would it mean?

The answer is it would mean that NP is a subset of BQP. It wouldn't mean that RSA is secure. In fact, we know because of Shor's algorithm, if someone can build a sufficiently large quantum computer, they would be able to break RSA. But it would increase our confidence, because it would put factoring in the class of problems that are believed to be hard to solve in polynomial time as long as P is not equal to NP. If it's also showing that P is not equal to NP, then this would mean that there is not any polynomial time solution for factoring with a classical computer. That would greatly increase our confidence that RSA is secure. To see why this is the case, we can think about how complexity classes as sets of problems. That makes the green circle the class NP. We have the class BQP, which is not known whether it's a subset of NP. We have the problem factoring, and we know factoring is somewhere in this circle. The reason we know factoring is NP is we have solutions that solve it in non-deterministic polynomial time. Even the brute force solution, if we could execute all those passed at once, would solve it in polynomial time. The other way to see that it's an NP is there's an easy way to check if the answer is correct. That's just multiplication. That's enough to know that factoring is definitely within the NP circle. We also know that it's within BQP. If it's known to be NP hard, that would mean it's as hard as the hardest problem in NP. It's also known to be in BQP, so that would mean that we'd have to squish-- everything in the circle would now be inside BQP, because there is no problem that would be harder than factoring in NP. I hope those of you who haven't yet studied the theory of computation will forgive the full excursion, but this is a really important point to understand what the security of RSA relies on--these assumptions about problems being hard.

Suppose we want to send a small number-- say it's the day of the year for some very secret event like the next Udacity party-- using RSA. Can we do it? Which of these solutions would work? We could pick a large value x, and then send a pair where x is in the clear text, and we're sending the encryption of n + x encrypted with Alice's public key. We could pick a large enough value of e so that m\^e is always much greater than n. We could pick a large random value x and send m + x encrypted with Alice's public key. Or none of these.

The answer is that none of these solve our problem. The third one would be secure, but would be useless, because there was no way from this to learn the value of M unless you know x, and there's no way to know x. The second one doesn't solve our problem, and it's not even possible. M could be 1. There is no value of e we could pick that would make m\^e when m is 1 exceed n. So that doesn't work. The first one is the most plausible, but it also doesn't work. Let me show you why the first one doesn't work. Even though the previous attack of just taking the eth root would not work on this. There's another attack that does, which is just to try all the messages. We can try for each message, and in this case the messages were the numbers from 1-365 whatever the set of messages is. As long as that's small, we can try them all, and we can try for each of those messages we're going to try encrypting using the public key. That message--see if it matches the cipher text. In this case it's not that message that we would try encrypting. We would try encrypting x + m, since we know the value of x. We find the one that matches. Then we know what the message was. Without randomizing the encryption system, this is very dangerous. If the set of message is small in a public key system, that's always dangerous because the public key is known. We can always try encryption in the forward direction and see which one matches the intercepted cipher text. If we're going to use RSA in practice, we need a solution to that, because we can't assume the messages are large and random and from some large set.

Our goal is to avoid the message guessing attack. The key idea is just to add some random padding to make the message large and unpredictable. There are lots of different ways to do this. One is the public key cryptography standard number 1, which is to replace the original message with 0 padding followed by a 10, followed by some random bits, followed by a bite of 0s, followed by the original message. This uses at least 64 random bits. Depending on the length of the message and the size of n, it may use more. This prevents the small message-space attack, since even if the set of possible messages is fairly small, an attacker needs to try all possible choices for the random bits, which is at last 2\^64 of them in order to test those messages. There's a better way to do this, which is known as optimal asymmetric encryption padding--OAEP. I won't go into the details of that, but the main idea is to XOR the message with the output of a cryptographic hash function that takes in a random value. But the recipient can still decrypt the message, because they can obtain the random value and XOR out the result of the cryptographic hash.

The last thing we'll do in this unit is talk about how to use RSA to solve the problem of signing a document. This is what we started with as one of the key motivations for asymmetric cryptography. This would be the straightforward way to do this, that Alice would take the document, encrypt it using her private key. That produces a cipher-text, which is really the sign document,. Anyone who has her public key, including Bob, can now use the encryption using her public key on that signed document and obtain the document and verify--because this document was decrypted using Alice's public key-- that only Alice could have created it. The problem with this approach is RSA is very expensive. We don't want to use it on large documents. It costs about 1000 times more as much computing power to do one RSA encryption as it does to do symmetric encryption. That means we don't want to encrypt the whole document like this. We need to do something else. The question is how should Alice sign a large document m? We'll assume that Alice has a public key known to anyone who wants to read the document, a private key known only to Alice, an implementation of RSA, and H-- a secure cryptographic hash function. Which one of these options makes the most sense?

The answer is the third choice. We're only looking for signatures here, so we don't need to encrypt the document. We don't care about confidentiality. We can send the document in clear, but what we want to send along with it is something that proves that it's the document that Alice intended. To do that we need to do something that uses Alice's private key. That's these two options. If we use the public key--well, anyone can do that. The public key could be known to anyone else. We're assuming that the private key is only known to Alice. The only one who could compute these two things would be Alice Then we have a choice of which one of these two things is better. If we believe we can have one-way hash functions that have the collision resistance properties that we talked about. Then this is much better, because the output of the hash function is small fixed-size value. It's only for a given security level. It might be 256 bits. We can encrypt that much more cheaply than if we had to encrypt the whole document using RSA. That's why this is the best choice, and lot's of protocols are based on this kind of solution where we use RSA to encrypt something small, which could be a hash value or it could be an encryption key. Then we use that with symmetric crypto for the rest of the message.

I hope you've enjoyed our introduction to RSA and asymmetric cryptography. It's really a very powerful idea. In this unit, we introduced the idea of using asymmetric cryptography both for privacy and for signatures. There are lots more that we can do with asymmetric cryptography. We'll talk about some of that in the next unit. We talked about the RSA cryptosystem, which is probably still the most widely used public key cryptosystem. There are billions of transactions going on every day using RSA. Nearly every time you use secure website, it's very likely that RSA is being used. We'll talk about the protocol for that next unit. We argue that RSA was correct, that it was invertible and had all the properties that we needed to be able to encrypt and decrypt messages. Its correctness depended on theorems that go back thousands of years from Euclid--there are more recent ones, but still many hundreds of years old from Euler and Fermat. It's putting those things together in the right way that lead to this solution that enables most of modern e-commerce. We also argued that RSA is probably secure--at least for the time being. That depends on the hardness of factoring. Then we talked about some issues in using RSA in practice, the dangers of encrypting small messages or messages from a small set of known messages, and solutions to that based on using random padding. There's one issue that we haven't covered yet. That's how does Bob actually know Alice's public key. If they can get together in a room, maybe she could give it to him. That's not usually possible, so this is a hard problem. Until we have a solution for that, we're going to have to take away Bob's smiley face. He's still a little bit frowny. Until we have a solution to this problem, we don't have a good way to use asymmetric cryptography in practice, because it relies on being able to get all these public keys. That's one of the things we'll talk about next unit-- how to build a public key infrastructure so Bob can learn Alice's public key as well as lots more interesting applications of asymmetric cryptography. Hope to see you back for unit 5.