[SOUND]. In this lecture we'll explore constructions of signature scans based on the RSA assumption. Let's first recall the RSA assumption. If we have a party who chooses two random equal length primes, P and Q. And then multiplies them to compute a modulus N. That party can also then choose two integers e and d such that e times d is equal to one modulo phi of n. And they can do that of course because they can compute phi of n given their knowledge of the prime factors p and q. They can then compute the eth root of any value m modulo N by simply computing m to the d mod N. And as we've seen previously, this works because if we take the value m to the d, and then raise it to the eth power, we get m to the de. Which is equal to M to the ED mod phi of N. Which is then equal to N to the one, or N itself. So the value M to the D is indeed, the Eth root of M modulo N. On the other hand, the RSA assumption says that if we're given only N and E. And not the factors of N, and not D itself, then it's hard to compute the Eth root of a uniform value M in ZN star. And this naturally suggests a signature scheme based on RSA assumption that I'll call plain RSA, and the way this works is as follows. One party will generate a public private key pair by running an RSA generation algorithm to generate a modulus n along with integers e and d having the relationship on the previous slide. The public key will then be the modulus n and the public exponent e, and the private key will be d. And they can then send that to any other entity, any other party who wants to verify their signatures. To sign a message m, what that party will do is simply compute the dth root of m, and that will give a signature, sigma. A recipient, obtaining m and sigma can easily verify that sigma is the eth root of m, by simply computing sigma to the e and verifying whether that does indeed give the value m. Why should this be secure? Well we just said two slides ago that computing eth roots. Modulo n is hard. Right? Given only the public key which contains exactly the modulus n and the exponent e, the rsa assumption says that it's hard to compute eth routes of random m, modulo sorry, random m And since the signature on m is the eth root of m, well it should be difficult then for anybody only having the public key, to compute signatures on messages. Is this a proof of security? Well of course it's not, but it goes beyond that in fact this intuition is really completely wrong in several respects. First of all, it's very easy to sign specific messages. For example it's very easy to compute the eth root, of the message M equals 1. Right? The eth root of 1 is simply 1 and so a valid signature on the message 1 is simply the signature 1. And fundamentally, the issue is that the RSA assumption tells us that computing eth roots of random messages, of random M, is hard but it says nothing about the difficulty of computing eth roots. Of nine random messages. Of small messages for example, or of n equals 1 in this case. Another attack results from the fact that an attacker, is able to generate signatures on random messages as often as he likes. And the way this works is as follows. So we described the scheme as having the signer take a message m that they wanted to sign and then compute the eth root. But an attacker can work backward. What an attacker can do is start with an arbitrary value sigma, and then let the message be determined from sigma as sigma to the e, mod N. So that is the attacker starts with the signature that he's going to for which he doesn't know the corresponding message. And only later computes the message m equals sigma to the e. Now of course sigma is a valid signature on m. Because sigma is of course an eeth root of m. So, you might think this is not much of an attack, because here the attacker doesn't have any control over what message, m, is being signed. Never the less, this would violate our definition of existential unforageablility, because the attacker is able to come up with a signature on some message. An even more damaging attack, it to combine two signatures to obtain a third. And here the attacker can in fact manipulate things so as to obtain a signature on any message of his choice. The way the attack works is as follows. Let's say, that the attacker was able to obtain valid signatures, sigma one and sigma two, on m1 and m2 respectively. What the attacker can then do, is take the product of those two signatures. Call it sigma prime. And that will be a valid signature on the message m prime equal to the product of the two messages. And you can check this yourself to see that it works out. If we take the signature, sigma prime, and raise it to the eth power, well, that's exactly equal to sigma one to the e times sigma 2two to the e. And because sigma one and sigma two are valid signatures on m one and m two respectively. We know that sigma one to the e is going to be equal to m one. And sigma two to the e is going to be equal to m two. And therefore the product is equal to m one times m two as claimed. So again the attacker has been able to piece together two signatures on two other messages. And combine them to attain, obtain a signature on a third message. If the attacker can really obtain signatures on any messages m1 and m2 of his choice, then the attacker can set things up exactly in such a way as to pick two messages m1 and m2 who's product is equal to some message m prime, whose signature the attacker wishes to forge. So this is a really damaging attack that allows the attacker to potentially generate a signature on a message of his choice. As long as he can fool the signer into signing arbitrary messages of the attackers choice. Now the RSA FDH signature scheme was constructed exactly to prevent these kinds of attacks. FDH here stands for Full Domain Hash, and you'll see why it has that name in a moment. The basic idea of this scheme, and the intuition for it's security, is that what we're going to do is apply some cryptographic transformation to a message before signing it like we did in the planar ASIC signature scheme. And in particular, we'll have the same public key and private key as before. But now, when we find a message M, rather than computing the Eth root of M itself, what we'll do instead is to compute H of M for some cryptographic function H. And then compute an eth root of that. Right, so we take H of m, we view it as an element of Z n star, and then we raise that to the d. Thereby obtaining an, the, thereby obtaining the eth root of H of m. We can verify that very easily. Given a claimed signature on a message m, we simply compute H of m ourselves. And then check whether sigma is an eth root of that. That is, we simply check whether sigma to the e is equal to H of m. It's interesting to observe that this scheme actually naturally handles long messages, so we don't have to use hash and sign here. In effect, we're using hash and sign already with the underlying [INAUDIBLE] signature scheme. But I want to make clear that this is not an extenuation of the hash and sign approach because the [INAUDIBLE] signature scheme is insecure. So, we're actually trying to bootstrap a secure scheme out of an insecure one by using a cryptographic transformation and it happens to have the side benefit of allowing, of naturally handling arbitrarily length messages. Now, for intuition as to the security, I think the best thing to do is to look at the three previous attacks and why they failed here. The first attack was generating a signature on a message like m equals 1, for which it's easy to compute the eth root, and the issue here is that it's not clear. Why it would ever be easy to compute the eth root of some output of H and, in particular, if we try looking at what a signature on the message M = 1 might be, well, that would correspond to the eth root of H(1), but H(1) is going to be some arbitrary value in ZN Star. Not likely to be easy to compute the eth root of that. Moreover if the attacker tries the second attack where they first choose sigma and then try to work backward and find a corresponding message. They can try to do that. But if they choose sigma and compute sigma to the e, how will they then find a message m whose hash is equal to sigma to the e. They would have to find a message m such that H of m is equal to sigma to the e. Now this tells you in particular in we want the scheme, the RSAFDH scheme to be secure, then in particular it had better be difficult to compute inverses under H. Because otherwise this attack would work, the attacker compute sigma to the e, and then compute and inverse of H. That is an input such that H of m is equal to sigma of the e. But as H is a cryptographic hash function say, then it will be hard to invert. And that attack simply won't work. The last attack we saw was one where the attacker combined signatures on two messages to obtain a signature on a third. And if you just try doing the natural sort of thing here, you'll see quickly that it doesn't work. So, for example, if the attacker gets a signature sigma 1 on a message m1. And a signature sigma 2 on a message m2, well, the product of those two signatures is not going to be a signature on m1m2. And the reason for that is that sigma 1 to the e times sigma 2 to the e is going to be equal to H of m1 times H of m2. But that's not going to be equal to H applied to m1 and two. If H is a good cryptographic pass function, a good cryptographic transformation, then it won't have any such homomorphic properties like what I've shown here. And there's no reason to expect that it will in general. And not only that, but it'll even be hard for an attacker to find any two messages, an m1 and m2. Such that H of m1 times H of m2 is equal to H of m1 times m2. So the three previous attacks simply don't apply here. Now that doesn't mean that it's secure. We still have to prove that there are no other attacks that can work on this scheme. And in fact, this can be proved under suitable assumptions. And in particular, what it's possible to show. Is that if the RSA assumption holds, and if we model H as a random function mapping messages informally onto Z N star, then the RSA-FDH of function is secure. Now we've talked very briefly about this idea of modeling cryptographic hash functions as random functions before. We haven't discussed that formally, we're not going to do that here, it's a little bit more advanced than something that I want to get into in this course, however if you're interested you can see my book for example for a proof of this theorem, as well as a full discussion of this random oracle model. Now in practice, what we do is we instantiate this function H. With a modified cryptographic hash function. And then we simply are treating in our security analysis, that half function as a random function, mapping onto z n star. Now one thing I do want to point out about this, from an implementation point of view, is that it's not enough to simply take a cryptographic hash function off the shelf and use it here. And the reason for that is that the range of typical cryptographic hash functions is simply going to be too small. For example a, a hash function now a days might have an output length of 256 bits. But the modulus N might be 1,000 or 2,000 bits long. And so hashing on to even a uniform 256 bit string, is not going to give you anything close to a uniform element in a range n. Where n is a thousand bit or 2000 bit integer. So instead what you need to do is take your function. And modify it in some way to give you longer output. Such that the range of H is mapping roughly uniformly onto ZN star, as required by the theorem. We're not going to go into this again in very much detail. However, you are welcome to look at the standards for RSA-FDH and related schemes, and see how it's done there. An in practice the scheme is used in the sense that the RSA PCKS number 1 v2.1 standard included a signature scheme that can be viewed as being inspired by RSA-FDH. In fact what it really gives you is a scheme that can be paramaterized. And it allows the signer to use randomness, but if the signer chooses to use no randomness, then essentially you'll get a scheme that's very close to RSA-FDH. So the point is that RSA-FDH and things built on RSA-FDH and inspired by it really are used in practice. In the next lecture, we'll begin talking about identification schemes. This is going to be a little bit of a detour from the signature schemes, but it does give a very important mechanism for constructing signature schemes. And in fact, one that we're going to use in the lecture after that to construct signature schemes based on the discreet logarithm assumptions.