0:06

So first of all, if you want to speed up RSA encryption,

Â it's perfectly fine to use a small encryption exponent e.

Â So rather than using a random e one can use a small value of e

Â and in fact the minimum value that's possible is e=3.

Â So it's not difficult to see that the smallest possible value for e

Â is in fact e=3. And let's see why.

Â Well e=1 is a bad idea because that's not particularly hard to invert with e=1.

Â e=2 is not a valid RSA exponent because remember in the definition of RSA,

Â e had to be relatively prime to phi(N). phi(N), if you remember, is (p-1) times (q-1),

Â which is an even number. If p and q are odd primes,

Â (p-1) times (q-1) is an even number, but if e is even, if e is equal to two,

Â it's not going to be relatively prime to phi(N). So e=2 is not valid either.

Â And then e=3 is the first minimum value that can be used,

Â and then we just have to make sure that in fact, p is equal to two mod three,

Â and q is equal to 2 mod 3 so that (p-1) times (q-1) is not divisible by 3.

Â 1:13

So in fact this is a fine public exponent to use,

Â however the recommended value is 2 to the 16 plus 1. So 65537.

Â It's a good idea to use this recommended value of e.

Â To compute x^3 mod N, you would basically need three multiplications.

Â To compute x^65537 mod N using repeated squaring, you would need 17 multiplications.

Â Basically what you would do is you would repeatedly square 16 times

Â and then you would multiply by x one more time.

Â Ok? So just with 17 multiplications you can do this exponentiation,

Â so this is still much, much faster than using a random e,

Â which would require something like 2000 multiplications.

Â So this leads us into what's called the asymmetry of RSA,

Â where in fact encryption is quite fast: encryption only requires 17 multiplications.

Â However decryption is much, much, much slower;

Â it requires something on the order of 2,000 multiplications.

Â 3:17

Now, I wanted to mention a number of implementation attacks on RSA.

Â These are attacks that have been demonstrated against particular,

Â mathematically correct implementations of RSA. However, these implementations were vulnerable

Â to certain side channel attacks that make the implementation completely insecure.

Â So the first example of this is due to Paul Kocher back in '97.

Â He showed a timing attack where all you do is you measure the time for an RSA decryption.

Â And simply by measuring the time, you can actually expose the secret exponent d.

Â And so, this says that if you are going to implement an RSA decryption,

Â you had better make sure that the decryption time is independent of the arguments.

Â 3:57

Another attack also by Paul Kocher two years later showed that

Â if you have a smart card that's implementing RSA decryption

Â you can actually measure the power consumption of the card while it's doing RSA decryption

Â and then simply by looking at the peaks and troughs you can literally read off the bits of d

Â one bit at a time as the smart card is running through the repeated squaring algorithm.

Â So using a power analysis attack it's actually fairly easy to get the secret bits

Â of the secret key unless the smart card defends against power analysis attacks.

Â And finally another attack called a fault attack shows that the RSA is very vulnerable to

Â decryption errors and in particular, if for some reason an error occurs during an RSA decryption,

Â one error is actually completely enough to reveal the secret key.

Â So this attack is actually fairly significant. It's just, one error completely reveals your secret key.

Â And as a result, many cryptolibraries will actually check the result of the RSA decryption

Â before returning it to the caller. And the way you would check it is,

Â you would take the output of this exponentiation, and simply raise it to the power of e,

Â and check that you actually get back c modulo N.

Â 5:04

And if so, you know that your decryption was done correctly.

Â Now the reason you can do this is because again, e is much smaller than d,

Â therefore checking takes much less time than actually raising something to the power of d.

Â Nevertheless, you know, even though checking is ten times faster than the actual decryption,

Â this still introduces a 10% slowdown. And so sometimes this is actually turned off.

Â But nevertheless, it's actually a good idea to check that your RSA output is correctly computed.

Â And so all these attacks kind of again make the point that if you just implement RSA naively

Â it would be mathematically correct, it would work,

Â however there would be all these potential attacks on the implementation

Â and as a result you should never implement RSA yourself.

Â Always, always use standard libraries and just use the implementation available there.

Â 5:51

So to be concrete, I wanted to show you an example of one of these attacks.

Â And in particular I'll show you the fault attacks on RSA.

Â And again, this will be a fault attack on what's called RSA with Chinese remaindering.

Â So in fact, as I said at the beginning of the segment, RSA decryption is often implemented as follows:

Â What you do is, you decrypt the cipher text c modulo p, then you decrypt the cipher text c modulo q.

Â And then you combine the two to actually get the decryption modulo N.

Â And this combination is done using what's called a Chinese remainder theorem.

Â Which I'm not going to explain here but it's not too difficult to see how that works.

Â Basically, once you have the result of the decryption mod p and the decryption mod q

Â you can combine it to get the decryption mod N.

Â And it turns out this gives about a factor of four speed up

Â over the naive implementation of directly doing the exponential modulo N.

Â 6:39

Okay. So, let's see why this is vulnerable to faults.

Â Suppose it so happens that when your decryption library is computing the decryption modulo q,

Â for some reason the processor makes an error.

Â And, actually, what it gets is not the correct xq. It gets an incorrect xq,

Â so let's call this xq hat. However when it computed the decryption modulo p,

Â you know, no error occurred. So these errors are fairly infrequent.

Â And so let's just assume that an error occurred modulo one prime

Â but it did not occur modulo the other prime.

Â Well, if that's the case our computation is correct modulo p and incorrect modulo q.

Â That says when we combine the two results we're actually going to get an output,

Â I'll call it x prime, such that the output is correct modulo p.

Â So, x prime is really equal c to the d mod p but is incorrect modulo q.

Â If we raised both these equations to the power of e, what we obtain is the following two relations.

Â Well, let's see. This guy we raise it to power of e.

Â What happens is the left hand side becomes x prime to the e.

Â The right hand side, here, it's c to the d.

Â If I raise c to the d to the power of e--e and d, remember are inverses of one another--

Â And as a result, if I raise c to the d to the power of e, both exponents cancel out and I simply get c back.

Â So I know that x prime to the e is equal to c. But modulo q, there was a mistake.

Â So x prime to the e is not equal to c modulo q.

Â So therefore, if I look at this difference, x prime to the e minus c.

Â We know that it's zero modulo p, and it's not zero modulo q.

Â So now if we compute the GCD of this value with N, what do we get?

Â 9:10

The last attack I want to talk about is a very recent observation

Â that was observed by Heninger et al and Lenstra et al

Â that shows that RSA key generation can be problematic when it's done with bad entropy.

Â So here's how things go wrong. So the way open SSL generates RSA keys is as follows.

Â Well, it starts by basically seeding the pseudo random number generator.

Â And then it uses random bits from a pseudo random number generator to generate the first prime p.

Â Then it will go ahead and seed the random number generator some more,

Â and will generate bits from the pseudo random number generator to generate q.

Â And finally, it will output the product of p and q.

Â Okay so the two steps, where we see the seed the pseudo random number generator.

Â Now suppose that this is implemented on a router or a firewall of some sort,

Â and suppose that the key generation happens right after the firewall starts up.

Â So the firewall boots up. At the time of the boot, there's not a lot of entropy

Â in the pseudo random number generator, and as a result

Â the firewall is likely to generate a prime p that comes from a very low entropy pool.

Â Which means that this p is gonna be one of a small number of possibilities.

Â However, after we've generated p, generating the prime actually takes a little bit of time,

Â a few microseconds. And so, by then the firewall will have generated more entropy

Â and so after we add more entropy to the entropy pool,

Â the prime q say is generated from a much larger entropy pool and is therefore unique to this firewall.

Â Now the problem is that many different firewalls if they generate an RSA key

Â in this way many of them will actually end up using the same prime p but a different prime q.

Â So what this says is that if we look at two RSA moduli from two different firewalls, N1 and N2.

Â If we compute the GCD of N1 and N2, well both of them had different q's but the same p.

Â So if we compute the GCD, actually we will end up with a factorization of N,

Â of both N1 and N2 and then we can actually figure out the private key both for N1 and for N2.

Â So this has actually been observed in practice.

Â Both of these groups, what they did is they scanned the web

Â and recovered all of the public keys out there that are used on various web servers.

Â They then ran a massive GCD, using some arithmetic tricks

Â they were able to compute this massive GCD of all pairs of public keys N1 and N2.

Â And lo and behold, they actually realized that a fair number of these keys have a common factor.

Â So they were actually able to factor these moduli.

Â So in the experiment, they were actually able to factor about .4% of all public SSL keys.

Â This is an amazing fact, that, in fact, so many web server public keys out there

Â are vulnerable just because they happened to generate the RSA key using low entropy.

Â So they have a common factor with somebody else's factor

Â and GCDing the two together gives you the factorization.

Â So, the lesson from all this is when you generate keys,

Â no matter whether they are RSA keys or ElGamal keys or symmetric keys,

Â it's crucial that the number--, that your generator is properly seeded.

Â So don't generate keys immediately after start up. You have to kind of make sure

Â the seeding of the generator has had enough time to actually generate enough entropy.

Â And only then you can start generating keys. So this is a really nice example

Â of how a, a bad random number generator can mess up your RSA public keys.

Â 12:36

Okay so this is the end of our discussion of public encryption from RSA.

Â I wanted to mention a few further readings if you want to read more about this.

Â So there's a nice paper by Victor Shoup that talks about why

Â chosen cipher text security is so important in the public key settings.

Â So if the Bleichenbacher attack wasn't convincing enough, there are many other attacks like this

Â that are possible if you don't use a chosen cipher-text secure system.

Â So if you want to learn more about chosen cipher-text security,

Â please look at Victor Shoup's paper.

Â There's a survey that I guess I wrote a couple years ago, that looks at many different attacks

Â on the RSA system. I guess I wrote this when RSA was twenty,

Â I actually need to update this to 30 years of attack on the RSA cryptosystem.

Â There've been some developments in the last decade, but for now this is actually a decent survey

Â to look at and read about more attacks on RSA.

Â The OAEP results that I mentioned are referenced here, OAEP reconsidered.

Â And finally, if you're interested in key length analysis of RSA and other public key systems,

Â there's a nice paper by Arjen Lenstra that discusses how you should choose

Â key lengths for your public key systems, and even for your symmetric key systems.

Â Okay, so those are the four references. I hope you have time to look through them.

Â And I will stop here. And, in the next module we're going to look at

Â another family of public key encryption systems, this time based on discrete log.

Â