[SOUND]. In this lecture, we'll see some public key encryption schemes based on the RSA problem. Let's just recall exactly how that problem was formulated. So if we choose two equal-length primes, p and q at random. And then compute their product to obtain a modulus N equal to p times q. And then choose two integers, e and d with the property that e times d is equal to 1 mod fi of N, then we know that we can compute the eth root of any element x modulo n by simply taking x and raising it to the dth modulon. And remember that this works because the solution x to the d, if we raise that to the eth power we get that that's equal to x to the de. Which is, in turn, equal to x to the ed mod fi of N which is equal to x to the 1 which is, of course, x. So the point is that the value x to the d mod n that we computed, is, indeed, the eth of the value x. On the other hand, the RSA assumption is exactly that, given n and e only. And in particular, not given d, and not given the factorization of N. It's hard to compute the eth root of a uniform element fi in Zn star. And we can use this in what's really a very natural way to obtain what I'll cal the plain RSA encryption scheme. And this scheme works as follows. We have the recipient here generate RSA parameters, N, e, and d, just as on the previous slide. The public key will be N, e, and the private key will be the exponent d. When the other party, the defender, obtains the first user's public key, they can then encrypt a message m by simply computing the ciphertext c as m to the e mod N. The recipient can decrypt that by taking the eth root of this ciphertext. And computing the original message m as c to the d mod N. So what we have here is basically the sender setting the ciphertext equal to m to the e, and the receiver recovering the message by computing an eth root. This seems like it should work, because we just said on the previous slide that computing eth roots is difficult without knowledge of the factorization of N. But that does not imply that the scheme is secure. At least not in the sense of CPA security that we've defined. To start with, the scheme we showed on the previous slide, the plain RSA encryption scheme, is deterministic. When you encrypt a message m, you always get the same ciphertext. So therefore, the scheme cannot possibly be CPA secure because we said it in an earlier lecture that any CPA secure encryption scheme must be randomized. It's even slightly worse than that. First of all, the RSA assumption only refers to the hardness of computing the eth route of a uniform element c. But the ciphertext that was computed on the previous slide is not necessarily uniform. In fact, it won't be uniform unless the message m is. And if the message m is not uniform, then c will not be uniform, and the RSA assumption really tells us nothing about whether or not an attacker might be able to recover m. Given the ciphertext c. Moreover, the RSA assumption only refers to the hardness of computing the eth root of some uniform element c in it's entirety. That is the RSA assumption says that it's hard to compute the entire eth root, it's hard to compute the solution that is to compute an eth root of c. But it says nothing about whether it might be possible to compute partial information about the eth root of c, even if c is uniform. That is, it might be hard to compute the eth root of c, but not so hard to compute the first bit of the eth root of c. And in fact, there are particular bits of information that it is possible to learn about the eth root. From the value c without computing the eth root in its entirety. And what this means is that information is being leaked about the message m. Even if the message m is a uniform element of zn star. So for all these reasons, the plain RSA encryption scheme should simply not be used. In an attempt to address the deficiencies in the plain RSA encryption scheme, different proposals have been introduced. PKCS #1 version 5.1, which is a standard issued by RSA labs in 1993, addresses or tries to address some of the issues we mentioned previously by using random padding. That is, to encrypt a message m, which is now going to have bit length much smaller than the bit length of the modulus N. What the sender does is first choose a random bit string r of some appropriate length, prepend r to the message m, and view that now as an integer in the range of 1 to N minus 1. You can then take that integer, r concatenated with m, raise it to the eth power, get a cypher text c, and then send it to the recipient similar to what we had before. In turn the recipient can of course compute the eth root of c, recover r concatenated with M and then simply strip off the high order bits that are the padding and recover the actual message m itself. Now this is good because it addresses the main deficiency of plain RSA, namely that encryption there was not randomized. Here, every time you encrypt m you'll choose a different random value r and so encryption is randomized and so isn't as glaring as a, as a problem as we had in the case of plain RSA. Unfortunately, there's no proof that this scheme with the padding is CPA secure. Unless the message m is very short on the order of a small handful of bits. Even a constant number. In practice in the PKCS #1 version, version 1.5 standard, m is much, much larger and the proof simply no longer works. In fact, there are chosen plaintext attacks known when r is too short. So if you go the other extreme and you try to make m very long, and choose r only on the order of a hundred bits or so, then even though that would resist a brute force search over the randomness being used during encryption, the scheme is still not secure and it's possible to recover the message m. Even worse, chosen ciphertext attacks on this scheme are known. So even if you are willing to use a very large padding value r and therefore a short value for the message m, there would still be chosen ciphertext attacks on this scheme that would make it unsuitable for use in, in practice nowadays. To address some of these issues, the PKCS #1 standard was updated. And in version 2.0, the following scheme was introduced. What they do in this scheme is to use what's called optimal asymmetric encryption padding, often known by the acronym OAEP, to transform the message before raising it to the eth power. This padding that we'll show in the next slide introduces some redundancy in the sense that not every possible element in Zn star is a valid ciphertext. Only some negligible fraction of the elements of Zn star are actually valid. And upon decryption, the receiver actually needs to check for the proper formatting and return an error if indeed the result is not properly formatted. The OAEP encryption scheme looks something like this. So what we do is we take our message M and we append to that message a sufficient number of zero bits. These zero bits are what are going to serve as the redundancy and the receiver will check for the presence of those zero bits upon decryption. We also choose a random value R. And then, as indicated in the diagram, we process these two elements in the following way. We first evaluate some function G on the input r, and take the result and XOR that with our message m, concatenated with the trailing zero bits. We take the resulting value and apply some function H to that. And XOR the result with the initial value r that we started with. This gives two values, s and t, that we can then concatenate together and as before, view those as an integer in the range of one to N minus one. We then take that and raise it to the eth power to get our ciphertext c. The receiver can decrypt by reversing the order of the arrows on the diagram. So given a ciphertext c, the receiver using their private key, can recover the eth route and thereby obtain s and t. It will pass s through the function H and XOR the result with t thereby obtaining r. It can then evaluate G on r, XOR the result with s and then obtain m followed by some number of trailing bits. As mentioned earlier, it will then check those trailing bits and make sure that they're all equal to zero, and if they're not it simply rejects. That is it outputs an error. If they are, it strips them off and then returns the original message, m. And I'll just note for completeness that the number zero bits is fixed and so even if the message m, happens to end in a certain number of zero bits those will not be striped off and thrown away. The receiver knows exactly which bits are supposed to be stripped off and which bits are part of the original message. It turns that out that RSA-OAEP can be proven to be secure against chosen ciphertext attacks under the RSA assumption if we're willing to model our functions G and H as independent random oracles. And this is now again the second time in the class when we're seeing this notion of modeling hash functions as random oracles. We didn't go into this formally but again think about it as viewing some hash functions that are used to construct G and H as making G and H act as if, or behave as it, they're completely random functions. The OAEP, or the RSA-OAEP encryption scheme is used widely in practice. So, PKCS version, for PKCS #1, has been updated several times since 2.0. But the most current version of it still uses a variant of, what we showed on the previous slide. I should warn you, though, that, you shouldn't take what I have on the previous slide as a guide if you're trying to implement this in practice. You should then look at the standard, and implement it exactly as it's described there. This concludes what I wanted to say about public key encryption. We've talked about the public key setting in general. We've talked about public key encryption. We've talked about using hybrid encryption to obtain the asymptotic efficiency of private key encryption while obtaining the functionality of public key encryption. And in this lecture and the previous one we've seen examples of public key encryption schemes based on the discrete logarithm and here are the RSA problems. Next week we'll turn our attention to digital signatures. I hope to see you all there.
