The Story Behind RSA: The Invention That Secured the Internet (ft. Turing Award Winner Ron Rivest)

Transcript

People started to realize that standards were essential that cryptography was about communication. Communication required standards. RSA was the natural candidate for standard. But RSA had the defect in in some eyes that it could also be used for encryption. The idea that was proposed was the DSA standard which could only be used for signatures. To me, signatures were probably of more interest. One of the big contributions of the Diffy Helman paper was the idea that you can sign things. You can authenticate messages as well. >> Suppose we wait a thousand years. Are we going to have a quantum computer that can break RSA or do you think it's just not possible period?

>> People think that quantum computing is going to replace your laptop and do everything faster and so on too and it's not. There's the questions whether P equals NP. Look at 100 years we should know the answer to that question. That would help. The cryptographers's nightmare was waking up some morning and finding out that. Hi everyone and welcome to First Principles, a series by the team at A16Z Crypto. I'm Tim Ruffgarden. I'm the head of research at A6Z Crypto and today we're exploring the mechanics of establishing trust between strangers on the internet. Public key cryptography is what makes this possible. Using math to

let strangers communicate securely and verify messages without ever sharing a secret in advance. Our guest today is Ron Revest, a touring award-winning cryptographer and institute professor at MIT. Probably best known as the R in RSA, the public key crypto system he co-invented that underpins secure communication across the internet. Decades later, the core idea still forms the foundation for everything from internet security to blockchains. Joining us is Dan Bonet, professor of computer science at Stanford, also senior research adviser at A6Z crypto, whose pioneering work on pairing based cryptography earned him the Girdle Prize and the ACM Prize in computing and

opened up entirely new categories of cryptographic primitives. Together, we talked with Dr. Revest about the invention of RSA, about the evolution of cryptography, and about how these ideas continue to shape the future, touching on everything from cryptographic hash functions to postquantum security. Here's our conversation. So Dan, we're it's very exciting. We're about to talk to Ron Revest. Um, and you know, so in blockchain protocols, cryptography is used in many ways, but you know, in my mind, there's sort of two cryptographic primitives without which it doesn't even make sense to talk about blockchain protocols. you just literally couldn't do them. One of them being digital signatures, the other being cryptographic hash functions. Uh, and Ron Revest has been, you know, very key

figure in the development of both of those primitives. So, I was hoping you could just talk a little bit about, you know, what role do those primitives play in sort of modern blockchain protocols and then a little bit about Ron's role in their in their evolution. >> Absolutely. Yeah, it's it's so cool that we get to interview Ron Revest. He's one of the gods of cryptography. So, yeah. Yeah. So, Tim, like you said, digital signatures and and cryptographic hash functions, they're kind of uh core to to blockchains. Digital signatures, of course, are used for signing transactions. When I want to pay you, I have to uh sign a transaction that's that's done using a digital signature.

They're also play an important role in consensus. Once enough uh validators sign on the block, the block is finalized. So, many consensus protocols use digital signatures. They're also used quite heavily in decision-m governance and Dows and such, right? All those depend on digital signatures. And guess what? The first digital signature that was ever created uh is actually the RSA digital signature scheme invented by Revest, Shamir, and Edelman RSA. And we're going to be speaking with Ron Revest, who is actually the R in RSA. Of course, there are many other signature schemes that have been invented since, most famously maybe in the blockchain space. ECDSA is a signature scheme that's used widely that uses slightly different technology than what RSA is

using. And then Schnore is another signature scheme that uses this more maybe more similar to ECDSA. And I guess we also have the BLS family of of digital signatures. So those those kind of all together all of those play a pretty critical role in the world of blockchains. Then >> because he's too modest to say it, let me just say my co-host is the B and BLS signatures. >> Well, okay. Thank you. Thank you, Tim. But again, you have to remember the original signature scheme, digital signature scheme is actually RSA. Maybe it's worthwhile saying that kind of RSA there's some moving parts to the scheme itself. But fundamentally, the security is based on the fact that if I give you an integer number, factoring that integer number into its prime factors is difficult. Again, the RSA signature

scheme depends on slightly more intricate complexity assumption. But by and large, you can think that security is derived from the fact that factoring is difficult. And I'm sure we'll get into that with Ron Revest when he discuss with him. The other important primitive in the world of blockchains of course is hash functions. So hash functions are what we call collision resistant hash functions. So it's hard to find two different messages that happen to hash to the same output. So of course they play an important role in the world of digital signatures because before we sign a message, we hash it and then we we sign the short hash that comes out of the hash function. But hash functions also play a critical role in the world of blockchains. For example, they make up Merkel trees. So Merkel trees um it's a way to commit to a large

amount of data and later prove that the you know cells and the data are what was committed to and collision resistant hash functions play an important role in Merkel trees. If you take this one step further, Merkel trees play an important role in what are called hashbased snarks. Um and so hash functions even play an important role in the world of zero knowledge proofs uh and snarks and again Ron played a critical role in designing collision resistant hash functions. It's kind of interesting after they invented RSA uh Ron and his colleagues launched this company called RSA data security. Um and in that company they commercialized RSA for encryption and for signatures. So to do that they needed a collision resistant hash function. And so Ron was tasked

with, can you build a collision resistant hash function? And so he came up with a whole bunch of collision resistant hash functions called MD2, MD4, MD5, MD6. Um, we can ask Ron what was MD3 because that seems to be missing from I was wondering when you when you gave me that overview. Yeah, >> we skipped we skipped over MD3. But these are all very famous hash function. MD4, MD5 were very widely used. MD5 is still used in some places. Now they've been replaced by the NIST standard. These are called the secure hash algorithms. Sha, Shaw 2, Sha 3. But the original collision resistant hash functions were designed by Ron for the purpose of making RSA digital signatures work. So it's really going to be incredible to hear Ron reflect on his experience in designing these

primitives. >> And on the point of cryptographic hash functions, I have to say every every time I teach them, my mind gets blown all over again, right? It's kind of arbitrary compression in practice without any collision. So you can take the entire Bitcoin blockchain, the entire Ethereum blockchain, the entire Salona blockchain, hash it down to 256 bits. The pigeon hole principle tells you there's zillions of other things that would hash down to that exact same set of 256 bits. You will never find nor will anyone else ever find any of them ever like for the life of the universe. It's just it's it's shocking to me that these things could exist.

>> Yeah, it's really quite amazing to a mathematician. A collision resistant hash function makes no sense, right? Because of course there are lots of collisions. You take a huge domain and you map it into a small domain by the pigeon hole principle, there will be lots of collisions. So even though we know that there are gazillions of collisions out there, a a collision resistant hash function makes it so that you can't point to any one explicit collision. It's really really quite a a difficult thing to try and design. So when you build a hash function like SHA 256 to break it, all you have to do is find two different messages that output the same 256-bit output. And not only that, it's like it's like this very short program. It's like a couple dozen lines of code taunting you to try to find those two different those two

different pre-im images. So >> that's right. So it's it's really quite courageous to uh try to build such a thing and um yeah, it's quite amazing that Ron put out the first such constructions. >> All right. Well, let's talk to him all about it. So Ron, thanks so much for joining us. Um really excited that you're here. Really excited about the about the conversation we're about to have. I thought we'd start at the if not the beginning close to the beginning. I was wondering if you could just sort of paint a picture of what things were like back in the early mid70s um when you know after working in other parts of computer science during that time you turned your attention to cryptography uh leading up of course to the famous invention of RSA. So what was you know did cryptography exist at that point?

What did it look like and what drew you in given that you had a lot of other interests at that time as well? Cryptography uh had been an interest of mine I guess for a while. The uh time period we're talking about is se mid70s late 70s something like that. I joined MIT in ' 74 and uh there are some works such as Khan's classic textbook on the codereers which talks about uh the history of cryptography and and the many many centuries of of work that had been done on that before. But modern cryptography was new. The computer revolution was just starting at the time. [snorts] Uh when I got to Stanford as a graduate student, uh people were playing with the internet. The arponet had boxes scattered around. It was it

was uh you know I I programmed in paper tape and then punch cards for a while and then uh eventually I got a time shared computer. So it it was uh early early days of the internet. >> What would you say? What would you say about the status of cryptography? I guess I guess at the time the data encryption standard dees had already come out. So there were some block ciphers. >> Yeah, data encryption standard had had just come out. There was a team at Stanford looking at some of that. I saw some of their papers evaluating dees. >> Sorry, maybe just for context, I'll say the dees is a block cipher. It's a way to encrypt messages if two sides have a shared key. I guess the modern version of it is called AES, which people are familiar with. But back in 1972 or so,

that's kind of where DEES was invented. And would you say that was kind of the cutting edge in cryptography? >> Yeah, I think I think so. I think people started to realize that standards were essential that cryptography was about communication. Communication required standards and that so we need to have standards for cryptography and the organization within the government that took the responsibility for establishing such standards was NIST. So NIST uh was trying to formalize the data encryption standard. They had two calls. The first call didn't yield anything useful at all and the second call they said come on guys you can do better than that. And uh so they they uh got a standard involved.

So eventually the encryption standard was adopted but not without controversy because the key size was short. It was seemed to be a good solid cipher otherwise. So most of the work was classified. This was the first uh inkling that maybe there was a commercial side of things. IBM played a key role in developing the data encryption standard. It was based on statistics and and uh stuff that I I I don't have a security clearance. I never did. And there was no theory. there was there was no theory of cryptography. We didn't know what we were doing. Uh [snorts] pe people were were trying this and that and uh you know I think the data encryption standard was sort of a good exemplar of that. It was it was not provably secure in any any sense of the word. There was no definitions of what

security meant. Uh there was no uh proof of course that went with those definitions. >> But you must have felt that like block ciphers were not the end of the story. I guess everybody was focused on just symmetric encryption at that time. But you must have felt that this is like missing the point that there's more to the storage than just symmetric encryption. >> Well, uh so my own interest at the time was um complexity theory and so on too. I was interested in boolean circuit complexity and and stuff like that. And symmetric ciphers were indeed the story at the time for cryptography. It wasn't until Diffy and Helman published their paper in 1976 uh where they where they uh said, you know, hey guys, there's another way to think about these things. You can have a

a private key and a public key and then [snorts] one undo does what the other does. And their paper new directions in cryptography is is a groundbreaker. It's a fundamental contribution to the field and introduced the idea of public key cryptography. [snorts] It's astonishing to me that you could publish a paper like that because they mostly said, you know, here's an open problem. How do you build a public key crypto system? [snorts] So they uh left left that as a juicy thing for somebody else to to to gather. And uh so we did we got to work on it.

>> And then that's that's how you got into it basically. You kind of got drawn into this open problem. >> Well, I was working on dees at the time, but I I got drawn into that problem certainly. And Audi and Len and I were members of the laboratory for computer science at the time, the precursor to CEL. The lab for computer science was interdep departmental. Audi and Len were both members of the mathematics department. I was a member of the CS department, but we had offices right near each other. And so I engaged them. And this search I said uh hey guys here's an interesting open problem.

Let's work on it together. And so we did uh Audi was more of a cryptographer with me trying to design ciphers and Len was the more the cryp analyst trying to break them. Uh he was very good at breaking them. So Audi and I had lots of stuff we crumpled up and throw the waist waistbin because of uh because of Len. the [snorts] RSA scheme is the one that we didn't know how to attack and so we ended up used pushing that one. >> You know, it's very rare, very few people make get to make a discovery of the magnitude of RSA. So maybe you can just tell us a little bit about how that process worked like how did you guys work on it throughout ideas and maybe even take us through the there's got to be like an aha moment like a day of

discovery. Maybe you can tell us about that day. >> Yeah. Yeah. there there well there was um in some sense I mean the the idea of RSA itself came to me uh after a context of working with Audi and Len a lot uh a after a dinner April 2nd I can remember the day uh you know 1977 and uh this is not long after Diffy Helman published the paper November of 76 we had been working all the time on on ideas for this and that. Uh, AI Shane has this wonderful story where he says, you know, I was skiing at with you guys at Killington and uh, you know, we were working on this problem simultaneously.

We were talking about it all the time and at the top of the hill I had this idea which which would have uh, given us public key and at the bottom of the hill I'd forgotten totally about it. I didn't remember what it was. >> So, we don't know what that was. Uh, there there were many many ideas floating around. >> It's a very firm mat's last theorem type story. >> Really? Yeah. Yeah. So, [laughter] so we uh worked hard on the problem and we we thought at times that maybe it was impossible. Diffening Helman had a set of conditions that they'd like to meet that the public key and this private key were separate. You couldn't tell one from the other and that one undid what the other did. But it was in feasible seeing only the public key to come up with the private key. So that was the

basic idea of public key cryptography at the time. We said, you know, maybe these these conditions are just too stringent. Maybe it's not possible to to satisfy all of them together. We spent a bit of time trying to prove that it was impossible and failed at that. Came up with RSA instead. So, we had a dinner uh one night at Anie Bruce's house, as I said. After the dinner, there was a bit of wine and uh so I was sitting at home afterwards looking at a copy of Dixon's book on number theory. All of a sudden, I said, "No, maybe we should do it this way." And so that that was the idea.

That was the aha moment that you're asking, but I didn't know at the time that that would work. The next day, I explained it to Audi and Len. They started thinking about it. Len couldn't break it. Audi and I said, "Yeah, it looks good. Maybe tweak it this way, tweak it that way, whatever, but it looks looks good." But it wasn't an aha for us in the sense that with with uh any kind of research researching cryptography in particular uh you know that's not the end of the story. Uh may may you have a a proof that comes later. Uh at the time we didn't even have good definitions to to prove things about.

You want to uh try to try to you know get it out there define it carefully but let others poke at it and see if see if it holds water. It's always kind of funny that to me that the first example you guys came up with that Lane Edelman couldn't break, nobody else could break either. >> Yeah. >> Which was which was pretty interesting. >> We were lucky. Well, L's very good. He's he's >> Yes. Yes. [laughter] Yes. I have to tell you, Ron, every time I've ever had an idea that I thought was a good idea at night after a glass of wine, it never survived the harsh [laughter] light of the dawn. So, I'm kind of blown away by this story, too. It's like same experience. Yeah. [laughter] >> Yeah. So, so one of the kind of underlying principles behind RSA, I guess, is the fact that you can easily

multiply two numbers or two prime numbers, but it's difficult to factor them. So, I guess this is something that you were already thinking of exploiting for this kind of system or was this? >> Yes, we we looked at lots of different schemes and uh multiplication and the difficulty of factoring was one of those. Uh, as it stands, computational complexity was new. Uh, we didn't know how hard various problems were. It was the field was still evolving. you know, we're really on quicksand. We're really on soft ground. We didn't know >> what what we were talking about it mostly and factoring was a problem like that. Nowadays, lots of people have looked at factoring and said, "Oh, it's hard." But at the time, it was it was um very sparsely studied. There were few decent algorithms. None of them had been

analyzed carefully except you know, trial division. So the the aha moment that we talked about was an aha that was very cautious because we didn't know we didn't know how hard factoring was and if you could factor numbers quickly you could break the system and so that was the story there. >> So Ron one thing I'm really curious about is sort of the closely intertwined stories of public key encryption and also digital signatures. I was curious both sort of leading into the work and then also sort of afterwards. Were you motivated more by one of those problems than the other? And at the time that it came out, did one of those solutions resonate more with the community than than the other one?

>> Great question. Um the Diffy Helman paper which was our starting point as I said was such that they talked both about digital signatures and uh encryption symmetrically. I mean they they you encrypt with the private key and and sorry encrypt with the public key and then decrypt with the private key or vice versa if you want to turn it around for signatures. So they were entirely symmetric. there was no randomization. So randomization comes in later in the story. Uh these are deterministic algorithms. So to me signatures were probably a more interest because they were new and I thought that was one of the big contributions of the Diffy Helman paper was the idea that you know you can sign things you can authenticate messages as well nicely

this way. Whereas encryption is maybe a more interest to the military community, the intelligence community. They're interested in stealing information and getting listening in on on conversations. But but they were sort of the same in terms of mathematically in terms of the what what you did. >> I guess it was first published in Scientific American, right? I mean Martin Gardner wrote this column and there he seemed to focus mostly on encryption, right? Not so much on signatures. >> I don't remember what he focused on there, but we I went down and met him uh in New York. He he was uh great guy. But the reason for my going was in part uh maybe to prep for this column, but also to find out what he knew about factoring because factoring was was a uh uh a black art at the time. And he's exactly

the kind of person that you want to ask about how hard is factoring, you know, what what do you know about factoring? >> And uh so he wasn't able to to make a dent in it either. And he said, "Let me write a column about this. Maybe my readers will will uh do something." So we helped him write the column. We put a challenge in there and made up a challenge cipher. I think we offered $100 for for anybody who could break the and we put a put a a boke a bad estimate of the time it would take to factor the number. We said it would take 100 40 quadrillion years to factor this uh 129 digit number and that was way off because it was factored in 94 by a bunch of guys uh lenture and and so on.

>> And then and these days you can probably do it on your eyewatch. >> [laughter] >> I haven't tried that yet, but I've got an eyewatch. >> Yeah. But but actually I want to go back to Tim's question in terms of like your sense of the interest in the community between signatures and encryption. Do you have a sense of what were people more excited about? Well, I you know, we're getting getting to the stage where NIST is starting to develop standards and the NSA representing the intelligence agencies, also the FBI, but mostly the NSA at that time was concerned about their ability to eavesdrop on on conversations with foreign adversaries and so on too. So, they were concerned that academic research in cryptography would hurt their business if if encryption became super strong. So we we got some push

back from from them about the encryption side of things and that's a continuing story and I can recommend uh Steven Levy's book crypto to talk about that story. >> Yeah, I guess doing cryptography back then is very different from doing cryptography now. Right now it's a scientific field. It's open. The whole world of cryptographers kind of collaborate with one another. >> Well, I I think I think you've got the blinders on a bit, Dan. I I think I I think that uh you know there there there's still portions within this intelligence community that would like to see academic research and cryptography >> squaltched. Uh and I see some of that. I guess mostly that's within the FBI and the intelligence agency sort of assume that you know what's good for the country is good for the world.

>> Yeah, that's that that that's fair. But it was much more so back then right when you guys got started it was much harder to publish papers in cryptography. >> That's right. That's right. Right. And Len Adelman had a offer from the NSA to uh give him money for a research grant under the condition that he subject all of his papers to their review and stuff like that. So he he declined that. >> You're right though. I mean it was was very different. So there were many consequences of that. I mean, one of which was the founding of the RSA conference series in '91 that was uh set up in part to give people a forum to talk about the tension between [clears throat] academic freedom and and to write the publish and the need for cryptography commercially uh versus the

intelligence needs of the country. >> So I'm also curious just so we've talked about sort of interest from the intelligence community and so on. What about actually within just say you know the ivory tower like computer science academia was it kind of too new? Did it take some number of years before cryptography was sort of really respected as >> I think that's right. I think that's fair. There was there's no immediate ground swell of enthusiasm for this. It was you know oh another application of of complexity theory perhaps or something like that. It was you know we're still feeling our way and and uh people weren't encrypting messages routinely. There was no internet. The examples in the the Dey Helman paper were things like talking to your stock broker and stuff like that which were merely hypothetical.

>> Yeah. Yeah, it's a little hard to imagine uh hard to believe life like that without the internet, without computers, without the phones, without everything being encrypted. >> It's really a different world. But I'm also curious like so like Tim was saying so the the result came out RSA was published >> and then there must I mean there was quite a lot of interest in understanding the security of the scheme. Were there kind of interesting at attempts to break the scheme? Were there interesting attempts at trying to prove that the scheme is secure? >> Yeah, sure. So RSA uh was a stake in the ground and said you know this game might be usable but it's got to be shown to be secure and we didn't know know what secure meant at the time even um I think the golder mccaui work around 80 early

80s um really started off the ball with formal definitions and inclusion of randomness in the encryption operation. Those were two key uh contributions they made. So I I think people tried to uh tune up their analysis of factoring algorithms. Even the existing factoring algorithms were not well analyzed. There was improvements over time to to factoring algorithms. We got better and better at at factoring numbers. The nice thing about RSA is the key size is totally variable. We proposed at first a uh a short key and then then it got longer and it's getting quite long now.

248 bits or something like that. just a recommended length uh for an RSA modulus. Computers can handle that easily these days, but but you know RSA is expandable and so the factoring even the factoring got a bit better, you know, was the kind of thing you could manage and deal with. Yeah, [snorts] I still get um people writing me every week, you know, saying, "Professors, I've got a new factoring algorithm, you know, please consider that. What about this? Can you factor 77 in your [laughter] >> I mean this this was sort of the greatest gift ever to uh you know to the endeavor of coming up with better algorithms for factoring and number theory more generally. I wonder when when you first heard this Ron but many times I've heard people say you know

this ironic quote of George Hardy right the famous the pure mathematician about his love of number theory by virtue of it having no applications. >> No applications. Yeah. Yeah. and and then you kind of completely blew up that vision of it. [laughter] >> Yeah, that's right. >> Yeah. >> Yeah. Yeah. Most of mathematics turns out to be useful somewhere and cryptography is a great consumer of mathematics. So, >> yeah. To me, it's actually amazing that that the things that people pursue for intellectual curiosity mostly, you know, Gaus and Oiler and all these guys and Hardy developed all this mathematics because they were they were curious. >> Yeah.

>> And it always always always turns out to be practical in one way or another. It's really kind of amazing that things that you think have no application eventually turn out to have an application and we just see this over and over again. So actually speaking of the security, I know that people were still kind of interested in how to set the security the size of the modulus as you said like how secure the scheme really is. >> So you guys came up with this really interesting idea to set up a challenge to break up RSA to break ours. There was not only the uh publication in the gardener column about a particular challenge but there was this ladder that we constructed and it was precisely that each number had a series of numbers each one was a product two primes and it went from four digits I forget what the

shortest one was four digits maybe uh up to uh you know thousands of bits long so 248 bits or something like that and the goal was to give people a challenge to find out because in practice the security is is a practical matter uh you can do all the theoretical analys you want, but if if uh you can't [snorts] build a quantum computer or can't implement your factoring algorithm, you know, whatever, uh it's just hard to tell. >> So, the the RSA challenge is basically a sequence of numbers that you need to factor. I think the largest one is like 248 bits. >> Yeah. Yeah. [snorts] >> I think the largest one that's been factored is like 768 bits or maybe slightly bigger. That's around there. Do you know the factoriization of these numbers?

>> I don't know the factoriization of numbers. Like, you know, it keeps my laptop from being hacked. You know, I think that factoring is a nice problem in the sense that, you know, if you're given a solution, if you say these are the factors of that number, you can just multiply them together and see if you get the target number. >> So, so at this point, you're saying nobody knows the solution to the RSA challenge problems. >> Well, the short the short ones they do, that the longer ones they don't. >> The longer ones. Yeah. So, if anybody comes up with a factoriization, then they did something that we think is difficult. Yeah. Well, I did give a talk at my my wife does substitute teaching at a fourth grade class nearby and uh one of the girls in the fourth grade class afterwards, she said, "Professor

Avest, I discovered the factoriization of this number." I said, "My god, what what's going on here? Your fourth grade? You must be a genius." She said, "Oh, it's blah blah blah blah blah blah blah blah blah and a half times two." >> Oh, [laughter] amazing. Yeah, it's true. >> So, I I said, "That's good, but that's not what I meant." [laughter] >> Yes. Right. factoriization into integers >> into integers. >> Integers. Yes. >> But again, our audience should know this. There are these numbers out there. Like like I said, the largest one is called RSA 2048. Ron is on the record. Nobody knows the factoriization of these numbers.

>> Yeah. >> So, you have a challenge. If you can factor any of these numbers, [snorts] uh I don't know that the prize is still still available, but >> it's not available, but people still use the numbers. >> There's a there are headlines every time a new one of these gets solved. For sure. You'll you'll make the news. If you factor any of these numbers, you'll make the news. I mean, it's very it's a very kind of nerdy slice of the news, but the news nonetheless, you will [laughter] make it. So, >> yeah, I'll hear about it for sure. >> Ron, you mentioned um earlier sort of the importance of standards in cryptography. And so, I was wonder if you could spend a little bit of time circling back to signatures and in the 1980s when the NIST made an effort to standardize a signature scheme, right?

DSA and and Dan, I'd love for you to fill in more context to as well, but there are a number of contenders here and there was a winner [laughter] and just would love to hear any stories you have to share about sort of how that process played out. >> Yeah, that that process is part of the bigger picture of uh NIST working as a handmaiden to NSA trying to suppress encryption and adopt signature only standards. RSA was the natural candidate for a standard but RSA had the defect in in some eyes that it could also be used for encryption. The idea that was proposed was the DSA standard which could only be used for signatures.

>> So DSA stands for digital signature algorithm and the goal was to standardize an algorithm that everybody in the US would use and say the government would accept signatures that were issued by DSA. >> Yes. Yes. And so there that was complicated not only for the politics involved and the pushing and shoving that went on about encryption but also because of uh the need to deal with patent coverage. The RSA algorithm itself was patented in um [snorts] 77 I think when we first invented it. So MIT decided to put a patent on on some of this things. uh there was a corresponding Stanford patent for Diffy and Helman and there was a back and forth about that and so that got delayed by six years which was a great six years

to have a patent coverage of 2003 whatever so >> so there there's a whole lot of issues having to come come into play for the adoption of a standard there >> so DSA became later on ECDSA which is very widely used these days but it's not just about the signature algorithm itself it's also about the hash function that goes into the signature algorithm. >> So signatures often they'd rely on collision resistant hashing >> and that also had to be standardized. Yeah. And so maybe just just to set the context, I know you designed a whole bunch of of collision resistant hash functions. MD2, MD4, MD5, MD6. It's a whole family. I'm not sure what happened to MD3.

>> MD3 was canned because it wasn't secure. >> Okay. I see. I see. >> There was there wasn't an MD3. I won't even talk about it now. >> Uhhuh. Yeah. And then and then NIST had their own standards. The SHA the secure hash algorithm >> SHA those came later but the design of MD2 MD4 and so on and too was because exactly as you say there was a need for hash functions to go with digital signature standards and you know we needed good hash functions and so that was my attempt to try to come up with a decent hash function. We I published it tried to let other people evaluate it.

MD2 turned into MD4 because it wasn't long, you know, enough rounds and so on too. Uh MD5 was a later edition. MD6 was was even later. So these things evolved over time as people started poking at it. But uh then the deed was entirely practical. Uh it wasn't theoretical. There were no definitions. There were no [snorts] security proofs or any sort. It was just basically can can you invert this hash function? >> So Ron, how do you h given a just sort of blank page? How do you even start thinking about that problem? Right? Because the point of a cryptographic cash hash function is to sort of be inscrutable to have no structure yet be you know an efficiently computable program like how do you even start thinking about that?

>> That's a great question. I don't know um to start taking a piece of paper and writing a code. I don't know. I mean things >> got [snorts] to start somewhere you know questions. What what should the state be? You know the usual >> you're describing it more as kind of a bit of an ad hoc process. Does is there very very very ad hoc. it was it was not theoretically motivated at all. If it had been, it would have been, you know, some factoring based thing or whatever would have been terribly slow. This is intended to be a fast algorithm. >> Yeah, that's I guess that's one of the things that's changed quite a lot and that's uh I I guess there's a little bit more guidance from the theory today which actually is kind of an interesting question like did any of your work on

public key cryptography inform your constructions for these hash functions or are these completely completely unrelated? >> These are unre unrelated. Well, one was a motivation for the other. The public key work was a motivation for the hash function design but the hash functions uh by themselves were independent could have been done I suppose you know independently without the context. >> Yeah I see and then eventually NIST decided on its own hash functions to standardize >> which I think was a good choice. I mean they they had a community involved and there's a lot of similarities between SHA 2 and Shaw 256 or whatever and MD2 MD4 whatever. So, so there's this they they they took the best of they could find and made it a hash function. So, shot

256 I'm perfectly happy with. >> That's actually good to hear because that's actually used quite a bit these days. So, >> that that's important important to say. >> Um, so actually I I want to change gears just a little bit and talk a little bit more uh about a theoretical concept. So if we go back to look at the schnore signature scheme, if you look at how it was constructed, it was derived from an interactive protocol and then you derive the signature scheme by applying this transformation. It's a very famous transformation these days. It's called the the fiat transformation that takes an interactive protocol and turns it into a non-interactive protocol and in that process we end up with a signature scheme. So that's kind of how how Schnore signatures uh were derived. So this I think that this dates back to like the late 1980s or so. This is kind

of where the idea of random oracles come from and so on. So today the future transformation is very very important in in applied cryptography. It's used a lot um to build to build practical uh protocols. Um random oracle analysis is actually used quite a lot in analyzing real world systems and so on. So um maybe you can just take us back to those times and like when random oracles came out when this idea of fumeir came out what do you think of it? What did the world think of it? At at the time I thought they were great. The theory community was starving for tools and looking for ways to prove things that they couldn't prove. And so you make assumptions and you know the assumptions that random oracles exist is a

reasonable assumption. You know there's no reason that one shouldn't think of shot 256 as a as a random oracle at [snorts] the time anyway. >> So you're saying at the time it seemed reasonable to model things as a random oracle and then instantiate them with shot 256. Yes. and and assume assume the resulting scheme is secure. >> Yeah, that that seemed very reasonable. It still does. I mean, people are getting better at analyzing random oracle protocols and finding places where they they don't work. But, uh, you know, by by and large, I think the random oracle methodology is a is a great one to use and nice to rely on as a theoretician.

>> Yeah, that's actually okay. Good. It's good to hear given how much of the how much of the deployed systems in the world actually depend on on on that methodology. But it's also a re a reasonable assumption though in my opinion. I mean it's not just a crutch. People take a a hash function and instantiate a random oracle with that. And uh Migelo saying that in a paper somewhere they can count on it being secure and and uh in practice it will be. >> Yeah. It's interesting to hear you say this because there was a period in time when this was a very controversial issue like cryptographers could spend entire dinners arguing about whether this makes sense. Is this a good is this a what does it even mean to instantiate a random oracle?

>> So I I think I think that debate is kind of settled uh mostly by now. >> It would be it would be nice if we knew the truths of complexity theory. Uh if we knew you know how to prove that P's different than NP and things like that. Uh but we don't we we still don't. Uh after decades we still don't. Uh and so we do the best we can and the random oracle hypothesis is one of those assumptions we make. Yeah. Jumping off on that, I wonder if you could talk maybe more broadly about the interaction between the more theoretical and the more applied sides of cryptography because you know you meet many many different kinds of computer scientists right some you know it has to just be based on the existence of oneway functions and anything else is cheating and then there's others that are like

you know does it work or does it not work you know implement it and let's you know >> yeah I think theoreticians learn from the practice it's a great question theory and practice at MIT are are both emphasized and uh cryptography is one of the places where theoreticians learn from the practical cryptographers a lot. Uh you'd learn things like timing attacks which are part of what you see in practice but you don't see that in theory. Theoreticians tend just to shoot that under the rug and don't model it at all but they should you know they they should say you know timing attacks are important in practice and and other other aspects of practice. You know being able to get in the middle of a conversation and and so on to the understanding of which protocols are are used in practice matters. So, so I I

think that uh practice informs theory and theory uh also informs practice. I mean you you have systems which are provably secure in theory and they get used in practice. Now machines are fast enough. You can you can find prime numbers, you can do other things uh with with them. You can do exponentiation. I had my 5-year-old grandson ask me, you know, which which is your favorite operation? You know, he's he's just learning mathematics. He loves mathematics, by the way. So I asked you said you know addition, subtraction, multiplication or division. I said exponentiation. Think think of cryptography. So we can do that. We can do exponentiation quickly. Modular expansion.

>> You you heard it here first, Dan. There's some someone to look out for when PhD admissions [laughter] come around in about 17 years. So >> there you go. Ex. Exactly. He's good at math. So send them our way. >> Yeah. Okay. >> 17 years. Yeah. Actually cryptography is one of the one of the amazing areas where there's a very strong interplay between theory and practice. So um I'm I was really happy to hear uh what you just said but actually it's also an interesting area where there's also interaction between kind of the corporate side more of the business side of the world and the academic side of the world. So you kind of lived in both, right? You set up a company, it's called RSA Data Security.

>> Yeah, we set up a company in 82 83 something like that. Early 80s and uh recall that the web did not exist at the time. [snorts] So Tim Berners Lee invented the worldwide web in 90 early 90s something. And uh so RSA as a company did not take off until the web happened really. And so >> it was too early basically. They would said it was created too early. >> It was too early. Yeah. The company was living on fumes for a while. Jim Bidzos joined in ' 86 and kept the company going with some with some uh contracts that he had arranged to get signed by Microsoft and others uh IBM. But uh it was it was very sparse going. We had offices in Redwood City and uh people

would come by and say, "Oh, this is your satellite office." And it turns out that that that was the main office. You know, that was that [laughter] was it. Uh-huh. >> So, uh, >> but then but then the web the book came along and everything took off, right? >> Everything took off. Yeah. Then payment systems happened. People people started paying doing transactions online, stuff like that. All the visions that Diffy and Helman had were realized through the web. >> And I'm curious, was that was that sort of a no-brainer decision in your mind to to form that company? I mean, you were still relatively junior professor at at MIT. I mean, maybe it's post tenure. The folks at MIT said, "Well, there's a commercial application." We said, "Okay, we'll we'll try." I don't know if it was a no, but we certainly didn't know. It

wasn't like doing an AI company these days where where you people throw money at you. >> So MIT encouraged you to do it. >> MIT encouraged us to do it and uh it was an interesting venture. >> So would you like to see, you know, of the current generation of computer scientists in academia, would you like to see more of them try to commercialize their their ideas or do you think the current system is sort of a perfect balance or what are your thoughts there? >> It's hard to tell. I mean MIT has some tradition of entrepreneurship. Maybe a third of the faculty are involved in startups of various sorts. Uh Stanford is you know heavily entrepreneurial and I don't know where it is what it numbers are like where you are Tim but uh >> less than Stanford or MIT at Columbia [laughter] some some they're there

though it's you know for the Ivy League it's it's very good I'd say actually. >> Yeah. Yeah. I I think people need to understand you know what what what the possibilities are and and you know perhaps you know if they lean in a practical direction to set up a startup. May >> maybe another way to ask this question is uh do you think setting up the company made you a better professor? That is did you did you take things back from the company back into your research world? >> Yes and no. I think it made me a better professor in the sense that one of the things I had to to to learn to do was to separate the commercial side of me from the academic side of me. So the academic side of me changed fields. I got tenure in part because of the RSA and things

like that. But I got tenure and I I switched fields to machine learning. So it's time to do something that's a bit more risky. So I I graduated my first uh PhDs in machine learning. uh Rob Shapi got a got a doctoral dissertation award things like that things were happening so the the commercial side of me was pushing the academic side of me to change fields and I did that so I I guess without the commercial side you know who knows what would have happened on the academic side eventually I switched back into doing more cryptography and the academic side of me particularly with the voting work the voting work has a lot of cryptography in it >> and for the younger listeners this era doing machine learning was a highly contrarian thing to do. This was not this. So, um, you back in the 1980s was one of the

more winter types eras in in AI machine. >> It was the practice that made it happen. >> Ron, I think we have like multiple examples where you are like ahead of the way ahead of the curve. So, you have to tell us what you're interested in now. So, we'll know where the world will be in 10 years. >> Uh, I guess the thing I'm thinking about now mostly is AI and AI safety. Nobody knows how these large AI systems work and [snorts] and people talk about safety and having no idea what it means. So I I thinking about some of those issues, but I also spend time on climate change. Both of my sons are involved in climate change. That's a problem we all have to face.

>> So uh we briefly alluded to um the potential of quantum computers and and postquantum cryptography earlier and it's sort of the elephant in in the room, right? The impact that >> um practical quantum computing, you know, would have on public key cryptography. So, you know, what are your thoughts? How much should we be worried about quantum computers? You know, and I guess the much broader version of that question is, you know, where do you think cryptography is going to be 20 years from now, 30 years from now, 50 years from now? >> Yeah, great questions. Quantum computing uh is a hot area for research. Dan knows this and you know this Tim and uh uh this is lots of work happening but you know I tend to be very biased about this and I I I wish the engineers uh the worst of luck actually building building

these things. You know people think that quantum computing is going to replace your laptop and and do everything faster and so on too and it's not. We don't know how to we don't have good algorithms for much except except breaking RSA. >> So yeah. [laughter] So >> it's like it's like the the universe is messing with us. Instead of instead of making quantum computers cure cancer, it makes quantum computers break cryptography. >> Yeah. Yeah. So there's there's that and we don't know that may change. But I think cryptography will will u be resilient and do that. I I love the uh work that's being done by NIST to to be ready for quantum [snorts] computers should they happen. But as I said, I I wish them the worst of luck. Maybe the intelligence agencies will buy buy some, but maybe they won't even. I don't know.

people are switching to slowly switching to uh quantum resistant cryptography. Do you have an opinion on whether this is like uh even in the limits is this possible like suppose we wait a thousand years are we going to have a quantum computer that can break RSA or is it do you think it's just not possible period >> well there's this there's questions whether P equals NP and stuff like that too which will be resolved within a thousand years >> so we'll know one hope yeah [laughter] >> oh I hope so yeah >> me too yeah >> within a 100 years we should know that the answer to that question I would hope I think the cryptographers's nightmare is waking up some morning and finding out that P equals NP all all of your cryptography all of your algorithms run faster but the cryptography is down the

toilet you know people can find out what the secret key is that could be split >> but that that question is likely to be resolved in proving that P is not equal to NP right so I'm not so I'm not so so worried that cryptography is going to break because P is equal to NP >> good knows I think you got to be ready for it I'm a worst case kind of guy you have to be ready for the worst case scenarios >> so what do we what what do you you know P equals NP how do we how do we change over because we you know as cryptographers we've got some responsibility to the world to try to shine a shine a flashlight on the path that's forward and say you know what what do we do here >> maybe it's worthwhile saying for the

audience that if it does turn out that P is equal to NP or you know and the algorithms are fairly practical then cryptography is like impossible or at least public key cryptography is impossible >> any kind of cryptography except except the onetime pad >> except for information theoretic methods like the one time pad Yeah. Yeah. >> But somehow I don't think we're going to be losing too much sleep over P equals to NP given that there's kind of wide fairly wide consensus that they're probably not equal to one another and that's how things might would likely be resolved. Whereas >> with the if they have to not only be equal but equal with a practical algorithm right especially that version of it I don't I think there are people who believe that just because of a mathematical curiosity maybe mathematically those classes are equal

basically because P is too generous a notion of efficient computation I know very I knew very few people who are betting on actually practically efficient algorithms for MP hard problems >> could happen overnight some spark >> it could until it's proved the other way we don't know and the consensus has been wrong before. I mean, we people used to believe in the ether. >> That's true. It's a good It's a good reminder. But but somehow the quantum threat seems a little bit more realistic to worry about in that if you believe in the postulates of quantum mechanics, then shor's algorithm should in principle work and it's just an engineering problem.

>> Quote in quotes. Yeah. >> Yeah. Yeah. Yeah. Just an engineering problem. question is whether they'll ever build a machine [snorts] a quantum machine that's big enough to factor RSA 2048. >> Yeah. Or maybe maybe we'll learn new science. Maybe it turns out the world is more complicated than just quantum mechanics and there's some quadratic terms and shortingers equation that prevents it from working. But but it's it's it's very interesting to hear your hope is that the that endeavor will fail. It's very very very interesting to hear that. Well, it won't help with respect to the standards because I think the standards have moved on to to quantum resistant stuff anyway, which is a wise move. But, you know, I I I must confess to have extreme bias. Yeah. In this regard, I think

>> these these guys are fooling themselves. They think they can build these things. So, >> but maybe maybe I'm wrong. >> No, but at the same time, the world needs to be prepared in the sense that if if it's not true and the and the machine is built in the next 10, 20 years, then we have to be prepared. Yes, >> we can't we can't bet the whole the whole safety of the world on on on our wishes. >> It's a good research problem for some somebody. So, if you got a graduate student who's looking for a research topic Dan [laughter] >> fair enough. For sure. >> Well, Dan is famous for um proposing to his PhD students problems where if they solve it, they are guaranteed a PhD. I think this one would qualify. This one, >> this one in the past. Yes.

>> All right. So, um Ron again, fantastic conversation. >> Good to talk with you folks. Thanks so much for taking the time to speak to us. This has been fantastic. >> Yeah. Yeah. Yeah. Good. Good. Good. >> This has been fantastic, Ron. Thank you so much. >> Wow. Well, so that was amazing getting to spend um an hour or so with Ron Revest, legendary cryptographer, all the stories, all the stuff he's done over the past, you know, half century plus. Just amazing to hear about. So before the interview, we really focused on applications in cryptography, specifically um in blockchain technology. You know, I think it was obvious when, you know, Ron was talking about cryptographic hash functions, signatures, encryption. They're more general cryptographic primitives and he, for example, talked about how, you know, when the web became a thing in the '9s,

you know, how signatures had this and encryption was all of a sudden, you know, used in e-commerce, but they're really much more general technology, right, these cryptographic primitives. So, could you speak a bit about kind of other applications, less obvious applications where they're playing an important role? Yeah, I guess we always think about the all the applications of cryptography to to blockchains which of course there are plenty but cryptography like you say is used in lots of other parts of of you know humanity of human life like for example uh securing the internet is kind of an important application for cryptography. So they're all internet connections. Even though the internet is a public network, we can converse privately over the internet.

For example, for the purpose of e-commerce, for the purpose of banking, uh businessto business applications can talk privately over this public network. And that that's all thanks to to uh the cryptography that Ron and many others have have have built. But another there's other areas where cryptography comes up. For example, uh it comes up a lot in digital elections. So how do we keep our elections safe, secure, sound and uh robust? That is all also based on various aspects of cryptography. And in fact, Ron worked quite a lot on the security of election systems. That is a pretty uh big passion of his. So yeah, cryptography comes up all over the place. It's really really quite an amazing tool and it's an amazing science. Again, it's one of these areas that brings um very powerful

mathematical tools and very heavy tools from the theory of computer science into practice in areas that touch basically all of our lives day in and day out. It's an amazing area. >> Yep. Anytime you're using your smartphone, there's cryptography happening in the background, for example. >> Yeah. >> Any surprises for you, Dan, in the interview? >> Oh, man. Yeah, it was really fun to talk to uh to Ron about his views on quantum computing. >> Yeah. Rooting for it to fail. rooting for it to fail. Yeah. >> I mean, as Ron said, a lot a lot of smart people are working hard on other applications of quantum computing, you know, should it be built, but as you say, the first killer application, no doubt, breaking public key cryptography.

>> That's right. So, it was really interesting to hear him say that he's rooting for it to fail. >> At the same time, hard to blame him. I sort of, you know, I try to put myself in his shoes. I I can see it, you know. >> And I thought I thought his uh point on uh oh, you know, we should be worried about quantum computing, but we should also be worried about what happens if P is equal to NP. That is a pretty unusual uh statement to make. So that was really interesting >> to the point that it makes me wonder if you know so Shor's algorithm was 94 I believe right which is 17 years after RSA. I wonder if in that interim he was worried about P versus MP already as a possible sort of threat to the RSA crypto system, right? And then and then

Shor's algorithm would just be you know yet another kind of you know threat to its enduring sort of uh viability. >> But it's I think you you you brought it up even if P is equal to NP but it turns out that the best factoring algorithm that comes out of P= NP runs in time into the 500 then it's irrelevant. You can't run the algor it's polinomial time but you can't run it. So it's it's it kind of uh not not really uh practically relevant. >> I do know some of the top computer scientists in the world who are worried about P equals NP for kind of weird mathematical reasons. It is very rare that I meet a you know kind of top computer scientist worried about genuinely practical algorithms for MB hard problems. And then you know of

course the flip side is is there's a big optimistic story if you're not a cryptographer right there's a lot of sort of very positive benefits of having you know fast algorithms for all for all problems in NP. >> Some somehow the P equals NP question to me if if P does turn out to be equal to NP it says [snorts] something very strange about the amount of order in our universe. Somehow you can fish out things from a huge fishbowl without looking at uh lots of fishes. It says something about um tremendous amount of order in the world which seems a little a little counterintuitive. Could be but >> perhaps the concern I think would just be it's such a generous notion of efficient computation and perhaps we didn't perfectly mathematically formalize what we meant by efficient

computation. That's the one the one little loophole that I myself do worry about from time to time. I would still bet on pe >> I would bet I would bet on P. Yeah. Yeah. If it's going to be resolved, it's most likely even resolved be resolved that P is not equal to NP. >> Yeah. >> But by the way, I should say that if if like disaster strikes and it does turn out that I don't know SATs has a quadratic time algorithm, then then we're in trouble. Then then all of a sudden uh cryptography like complexity based cryptography is just not possible and then it's not really clear what we do. Kind of the only things we can fall back to would be information theoretic methods like one time pad. And just to clarify that just to clarify that point.

So it's not just that the existing systems fail, right? So what you're saying is fundamentally it cannot exist should P equal NP with a fast algorithm. >> Fundamentally like we do not have good pseudo random generators. We cannot have even symmetric encryption that uh that is secure other than other than things that are information theoretics like the onetime pad. But there's another alternative which is it's kind of interesting that the world of quantum mechanics actually could potentially save us in that scenario too in that um we could actually build key exchange mechanisms based on the laws of quantum mechanics that don't rely on any complexity assumptions. So we could still build using fiber optic channels.

You and I Tim can still exchange a secret key that an easedropper can't uh learn. And then using that secret key, we can use it to then do a onetime pad to encrypt our conversation. So in some sense quantum mechanics could save us in the worst case that in fact SAT has a quadratic time algorithm. >> I see. So quantum giveth and quantum take it away, I guess. Yeah, that's right. That's right. Yeah. Yeah. So, it's a it's a pretty interesting story and I guess cryptography will live on just maybe in a very different different shape different shape and form.

>> It is definitely definitely not a boring area that you work in, Dan. I have to say never a dull day. So, >> never a dull day. >> Well, thanks so much for co-hosting the show. This was super fun as always >> and uh I propose we sign off there. So, >> yeah, this was awesome. Tim, thanks for setting this up.