Dr. Neal Koblitz and Dr. Victor Miller independently co-discovered elliptic-curve cryptography (ECC), part of the mathematics that allows encrypted communication on the internet today. To learn what led these mathematicians to this breakthrough—and understand why these geniuses never patented their ideas—AAC’s Mark Hughes spoke to Dr. Neal Koblitz.
Dr. Neal Koblitz. Image from his faculty page at the University of Washington.
If you're interested in the history of cryptography (especially during the Cold War) and want to hear what we can learn about modern cryptography, you may want to pull up a seat.
A Background in Theoretical Mathematics
AAC: Tell us a little about your background and education.
NK: I have been interested in pure mathematics since I was a young child. When I went to college, I took courses in pure mathematics and a few courses in physics, but no engineering or other courses in practical application. My undergraduate work was at Harvard, and the department courses were very theoretical in nature. I never applied the math I was learning to real-life situations. I even learned calculus in a very abstract way.
"I have been interested in pure mathematics since I was a young child."
I didn’t actually learn about the applications of calculus until several years later when I started teaching it to students who were going into engineering, and the calculus I learned was completely inappropriate to those students. I had to teach the course in a very different way from the way I learned it.
In graduate school, I also studied an abstract area of mathematics: algebraic geometry in relation to number theory. That [area of mathematics] didn’t give me any practical background—but, by happenstance, the subject of elliptic curves was central to my PhD thesis.
The same was true for the other fellow who came up with the ideas at the same time that I did. Victor Miller received his Ph.D. at Harvard at approximately the same time I received my Ph.D. at Princeton in a similar area of mathematics; [we both were] doing a lot of work on elliptic curves.
But my background, and my early work into the 1980s, was in very theoretical mathematics. I had no grounding in applications.
AAC: When did your mathematics background shift from the theoretical realm to security applications?
NK: What changed my feeling about number theory was the invention of RSA cryptography (Rivest-Shamir-Adleman) in about 1977. That was the first important application of number theory to computer security. This really captured the imagination of a lot of people.
"[The invention of RSA cryptography] was the first important application of number theory to the computer age."
Many people who had previously thought of number theory as a purely theoretical area now saw that there might be some interesting work to be done in applications. Yet even in 1985, when I was thinking about using elliptic curves in cryptography, I had no idea that elliptic curve cryptography would ever be of great practical importance. (Author's note: Neither Dr. Koblitz nor Dr. Miller obtained patents for their work.)
AAC: I understand that you also spent some time in Russia. What compelled you to do that?
NK: When I was very young, during the Cold War between the United States and the Soviet Union, both countries were going all out to develop their scientific and technical capacity in a very competitive way. There was the race to the moon and other things like that.
The Soviet Union had at this point, in the 1960s, an extremely high level of theoretical mathematics. They were the only mathematical superpower besides the US. I realized at a young age that it would be really nice to be able to go over there and work with Soviet mathematicians, to learn how they do things. For this, I studied Russian intensively. In fact, as an undergraduate, I double-majored in Mathematics and Slavic Languages and Literature, which included Russian.
I was very serious about my studies and I started applying to study-abroad programs. In those days, it was much less common than now. I first went on a six-week summer language study program. My first trip to the Soviet Union was in 1967. After that, I went again as an independent tourist. Then, after I was married, my wife became very interested in Russian history, so we went again once I completed my PhD. We went several times in the 1970s and 1980s.
[By the 1970s,] at the advanced levels, there were some exchange programs. The National Academy of Sciences and the Soviet Union had an exchange program. So there were reasonable ways to get over there to spend a fair amount of time collaborating with Soviet specialists in theoretical mathematics. In 1985, I took my last long trip to the Soviet Union. That trip coincided with the starting of my work in cryptography.
"The idea of elliptic-curve cryptography came in 1984."
The idea of elliptic-curve cryptography came in 1984. I, along with several other people received a pre-print, a rather preliminary-version, of an algorithm that Hendrik Lenstra developed to factor large integer numbers. If this algorithm was sufficiently fast, it could be a threat to RSA cryptography.
It turned out that this algorithm was not that much more efficient than other algorithms that existed at the time. [The algorithm] did not have a major impact on RSA, although it did have other uses in cryptography.
"Lenstra’s algorithm used elliptic curves in a very fundamental way to attack a problem that, at first glance, didn’t appear to involve elliptic curves—factoring integers."
What fascinated us at the time is that Lenstra’s algorithm used elliptic curves in a very fundamental way to attack a problem that, at first glance, didn’t appear to involve elliptic curves—factoring integers. The fact that he was able to, in a clever way, use the geometry and number theory of elliptic curves to factor integers, was really intriguing. This was the first practical application of that sort of number theory, and I had that fresh in my mind when I went to the Soviet Union in 1984.
While I was in the Soviet Union, I thought that elliptic curves might be a really good basis for constructing a cryptosystem. I wrote about this idea to a mathematician I knew named Andrew Odlyzko, who worked at Bell Labs. Of the mathematicians I knew at the time, he was the person who most bridged the gap between pure and applied mathematics. He was knowledgeable about cryptography and had major work in pure number theory, so I mailed him this idea.
There was no email then, so replies were slow to come in through the mail. When I received his reply he said it was a good idea, and that Victor Miller of IBM had suggested the same thing that I was suggesting. He encouraged me, and I suspect Victor Miller, to pursue it. He saw no fallacies in basing a cryptosystem on what Victor and I suggested.
Soviet-Era Russian Cryptography
AAC: You obviously found your time in the USSR valuable. What were they doing differently and what were you gaining from the experience that you couldn’t find in the United States?
NK: This [last trip to the Soviet Union] was planned before I really started working in cryptography. That trip was my last long visit—six months in 1985. No one in the Soviet Union worked openly on cryptography.
Even in the US in early years, there was a lot of controversy about whether people other than employees of the government working for the NSA should be permitted to study cryptography or permitted to publish their work on it. There were attempts by the NSA to restrict and create a [government] monopoly on cryptography research.
"In the early years in the US, there was a lot of controversy about whether people other than employees of the government working for the NSA should be permitted to study cryptography or permitted to publish their work on it. There were attempts by the NSA to restrict and create a [government] monopoly on cryptography research."
Ultimately, the people in the government that wanted to [restrict cryptography research] lost the battle. But in the Soviet Union, the governments did not want anybody outside government to be working on cryptography, and nobody did so. There was no way I could collaborate with anyone in the Soviet Union on cryptography, and in any case, I was just a beginner at that time.
During the time I was visiting the Soviet Union, I was still working in pure number theory and they had some of the top people in the world. One of them, named Yuri Manin, was one of the top Soviet specialists in number theory. I worked under his guidance for a couple of my trips—but when I came in 1985, he’d changed his interests to mathematical physics which I was not working or interested in.
In addition, since nobody was working in cryptography, my visit in 1985 was not as productive as my previous visits.
"Working in Moscow, was a really a unique experience because it was the biggest concentration of mathematicians anywhere in the world at the time."
I’d gone over for a full year in 1974-1975, and six months in 1978. There, working in Moscow, it was really a unique experience because it was the biggest concentration of mathematicians anywhere in the world at the time.
It’s not that there weren’t a very large number of mathematicians in the US, but they weren’t all in one place. The US is much more decentralized. In the Soviet Union, as in many other countries, a disproportionate amount of scientific work is in the capital or one central location. This brings the top minds in a field all to one place. [In Moscow,] you could have a highly specialized seminar where 30, 40, 50 people attend whereas in the US that wouldn’t be likely except at a large conference, but certainly not on a routine basis. So that was a thrilling experience... and stimulating.
Another thing I found both stimulating and intimidating was that the Soviet students were a lot more advanced than we were at the undergraduate level. In America, even the most serious math students normally wouldn’t publish papers [as undergraduates] but in the Soviet Union the best students started publishing papers when they were juniors and seniors in college—and they were quite good papers.
When I went over there from Harvard and met Soviet students my age, they would ask me what the professors at Harvard were working on right now and I had no idea. I knew what courses they were teaching us students, but I had no idea what their research was. I felt pretty backward compared to [Russian] students and I thought I was pretty advanced for an American student.
Women in Engineering and Mathematics: The Kovalevskaia Fund and the US Committee for Scientific Cooperation with Vietnam
AAC: You chose to get involved with the technical community in Vietnam. What can you tell us about that time period?
NK: My wife and I were very active in the student movement against the war in Vietnam. And a certain number of people who had been involved in the anti-war movement wanted to see if we could do something to support Vietnam because it was so badly destroyed during the war. Not just human suffering, but also economic and environmental destruction.
It was very hard for the people of Vietnam to recover from the war. There were some people in the West who were trying to in some ways help out. Vietnam was isolated because the US refused to have any diplomatic relations with Vietnam for about 20 years. So there were a lot of limitations and scientists in the West were in a position to help out.
A group of us called the US Committee for Scientific Cooperation with Vietnam encouraged their scientists with channels of communication to bring publications, send books, give guest lectures, and other things to help overcome the isolation the scientists were suffering from.
"My wife and I found out that in Vietnam, and other countries, there were big problems with the underrepresentation of women in the science and technical areas... We said 'That’s terrible—we’re going to help.'"
In the 1980s, my wife and I found out that in Vietnam, like other countries, there were big problems with the underrepresentation of women in the science and technical areas. On one visit, we talked to the head of the Hanoi Polytechnic Institute and we asked what proportion of the students are women—and they said 8%. We said, "That’s terrible—we’re going to help."
After consulting with some top Vietnamese scientists and mathematicians, we decided to start an annual prize for women in science, technology, and medicine that was coordinated with the Women’s Union—the Kovalevskaia Fund. This has been going on for the 34 years since 1985 and has been very successful in terms of its visibility in Vietnam. It’s very well publicized for a long period of time.
Until her retirement, the head of the committee that selects the winners in Vietnam was probably the most famous living woman in Vietnam. For that reason, the prize has gotten a lot of publicity and we’ve been encouraged to think that a lot of young women are very much aware of it and that encourages them to go into scientific and technical areas.
AAC: What should everyone know about the Kovalevskaia Prizes?
NK: The award is named after the 19th-century female Russian Mathematician Sofia Kovalevskaya. She was the first woman mathematician from any country to be a full member of the elite academic community of mathematicians. She was a full professor in Sweden and became a very active member of the European mathematical establishment.
While she was certainly not the first important woman mathematician, she was the first one to get full recognition for her accomplishments. That was surprising to a lot of people because Russian in the 19th century was considered somewhat backward country, so this woman was really a pioneer. There was no one in the west with her accomplishments in mathematics and other fields. There were so many restrictions against women in the universities of the world, hers was a unique achievement.
Quite a few of the Vietnamese best scientists studied in the Soviet Union, and there was a lot of exchange between the two countries. My wife wrote her doctoral thesis and a book on Kovalevskaya and we wanted to commemorate her through this prize.
Current Needs in Cryptography
AAC: Tell me about your views on the current field of cryptography. What does modern security need?
NK: The main weaknesses have to do with poor implementation, not using the cryptography that’s available, or using it improperly.
Sometimes shortcuts are taken by companies that provide keys that lead to big problems later on: inadequate security, inadequate key length, outmoded systems, and so on. There is a lot of reluctance to change from the software you know.
"The main weaknesses have to do with poor implementation, not using the cryptography that’s available, or using it improperly... There's a lot of reluctance to change from the software you know."
A long time ago, it was recommended that either people change from RSA to ECC or to greatly increase their RSA key size. But I don’t think everybody has done that yet even to this day. I think there are still a lot of weak keys lying around that could be attacked.
Now, in practice, weak cryptography does not necessarily cause huge amounts of problems because nobody with a lot of resources is really motivated to break into it. Sometimes people can get away with using fairly weak cryptography that if, say, the NSA or the Russian mafia or somebody were really determined they could break it. But if they are not interested, they have no reason to break into your system.
So if you’re using fairly weak cryptography to protect your credit card numbers, you might find that the type of people who steal credit-card numbers don’t have the resources to break it, and the people who do have the resources to break it simply don’t care. So you can get away with weak cryptography if you’re not a tempting target.
"...you can get away with weak cryptography if you’re not a tempting target."
There are all sorts of problems in social engineering that frequently use phishing attacks and things like that. People use weak passwords and use the same passwords in different systems. People can use a password from a weak system to break into a strong system.
"In all the cases I know of, breaches are not the result of weaknesses in the fundamental cryptography that’s available, it’s really because of the failure to use cryptography, failure to set it up correctly, taking shortcuts, social engineering, organizational problems, or system level problems."
In all the cases I know of, breaches are not the result of weaknesses in the fundamental cryptography that’s available, it’s really because of the failure to use cryptography, failure to set it up correctly, taking shortcuts, social engineering, organizational problems, or system level problems.
But the basic types of cryptography that have been used—and that includes RSA, which is now 42 years old—is really sound.
You have to increase to quite large keys in RSA because of all the progress in factoring, but it’s still basically a good system—so is ECC. The basic security of RSA and ECC have really stood the test of time.
There have been many successful breaks in both, for example, the Sony disaster where the DRM was completely broken in 2011 because they used the same random number. They were supposed to choose a different random number for every signature and they just hardwired a single random number for everything and it made it absolutely trivial to break the system and find the secret keys.
"There are a lot of dangers that come from poor implementation and inadequate implementation where you are carefully locking the front door and meanwhile the back door is wide open."
The hack wasn’t because ECC is a bad system, it was because there are certain things that are very important in implementing ECC and they ignored one of the crucial components. There are a lot of dangers that come from poor implementation and inadequate implementation where you are carefully locking the front door and meanwhile the back door is wide open.
The elliptic curve cryptography that Dr. Koblitz and Dr. Miller invented so many decades ago remains one of the best ways to protect data exchanges for embedded microcontrollers. "Hacks" do not break the mathematics of elliptic curve cryptography, at least not yet. But the hackers don't need to defeat the mathematics when it is so much simpler to look for poor implementations by a security engineer.
But it turns out that co-inventing ECC is not the only extraordinary thing about Dr. Neal Koblitz.
When some people see a problem, they say, "Someone should do something about that." When some people organize an award, they name it after themselves as a reminder to others of their magnanimity. When most people are interested in a subject, they go so far as visiting the local library to check out a book.
I hope you realize from this interview that Dr. Koblitz is not like most people.
Koblitz is a man of principle and action. He learned a new language so he could travel to a faraway place during the heights of the Cold War. He saw destruction after war and disrupted his life to help rebuild Vietnam. He created an award attributed to the greatness of another mathematician to raise the hopes and dreams of schoolchildren so that they, too, might one day be great.
Dr. Koblitz Autobiography "Random Curves: Journeys of a Mathematician" is available on Amazon.