A list of his publications, articles and interests can also be found on his web site, http://bibd.unl.edu/~stinson.

Doug, welcome to the show.

DS: Hello.

TNC: I'm looking at your web site here and I see this pretty interesting painting. Is this supposed to be a representation of yourself?

DS: No, that's just a painting that I found browsing around the Internet one day and I just kind of liked it. So I put it on my web site.

TNC: Okay. Any clue as to who the author of the painting is?

DS: It's somebody named Sobie.

TNC: One thing that attracts my attention is that your subject field is cryptography. Looking at the papers, a lot of mathematics are involved, obviously. Your background is that of a mathematician. And yet you teach in the department of computer science.

What is the relationship between cryptography and computer science today?

DS: Well, cryptography's kind of a multi-disciplinary subject. It's of great interest in computer science, I think, mainly because of the applications to the Internet are so important these days. But the actual tools that are used to do cryptography are basically mathematical in nature. So you find a lot of interest in cryptography in computer science departments as well as mathematics departments and also electrical engineering departments.

TNC: Do computer science departments look the cryptography from a different angle, with an emphasis on implementation rather than on the theory of some of the functions and algorithms involved?

DS: Oh, that probably depends on the individual. I come at it from a mathematical standpoint, myself, because that's what my background is. But many other people might come at it from a more applied viewpoint, where they're looking more at implementations rather than developing the mathematical theories.

You can approach the subject from a lot of different viewpoints.

TNC: Now, you're taking a position, you're leaving the University of Nebraska and you're taking a position in a mathematics department.

Do you find the same type of courses in mathematics departments as you would in the computer science departments?

DS: Well, I'm moving to the University of Waterloo in Canada. And I will be in a different department, so I will be teaching some different courses there than I teach here. I won't be teaching courses on programming or algorithms anymore. I imagine I'll still continue to teach courses on cryptography and other areas such as error correcting codes and things like that. But it certainly will mean a change in terms of the types of courses that I teach.

TNC: What are some of the mathematical fields or topics that are required to study cryptography?

DS: Well, there are a lot of different mathematical areas that are used. Number theory is probably the most important area, particularly for public-key cryptography. But you need basic ideas from other areas like probability theory, information theory, complexity theory, combinatorial mathematics.

So cryptography is a pretty broad subject and it draws on a lot of different areas of mathematics in different ways.

TNC: When people think about cryptography, one thing that comes to mind is really simple ciphers where people exchange letters, which they code by substituting characters or shifting characters around.

DS: Yes, that's right.

TNC: And actually, in your book, you describe such ciphers. Now, one obvious characteristic of such ciphers like that is that the key is shared. If I shift letters around, I have to tell the receiver about the code I used.

DS: That's correct. The sender and receiver in this type of a cipher both have to share the same key and the key that's used to encrypt the message at one end is essentially the same key that's used to decrypt it at the other end.

TNC: This concept is also used in the most commonly used cipher today, DES.

DS: That's right. DES is also an example of a shared key or private key crypto system.

TNC: Can you tell us more about DES?

DS: Well, DES is a federal standard that has been in use now for over 20 years. And it's what's called a block cipher where the data is split into blocks, which are of a binary for. 64 bits comprise a block. And then each block is encrypted using a 56-bit key. And the result is a 64-bit cipher text.

TNC: You're saying it's a standard. What does that mean, exactly?

DS: It means that it was developed and approved by the U.S. government. It's what is called a FIP standard, Federal Information Processing standard, and it's certainly the most widely used crypto system in the world today. It's used just millions of times a day by banking institutions and applications all over the world.

TNC: Now, I believe the government recommends DES for unclassified documents only. Why is that?

DS: Well, it was -- well, I guess the answer to that may be that the government may have different systems that it uses for classified documents.

TNC: Well, I guess my point is, is it not good enough for classified documents?

DS: I guess that's a difficult question to answer. I don't really have the information to say about that.

TNC: Okay. What are some of the performance issues related to DES? It's common knowledge that DES is much faster than public key crypto systems.

DS: Yes, that's one of the strengths of DES is that it is extremely fast. Particularly in hardware, it can achieve encryption rates of something like a gigabit per second. So it's very, very fast and that's important when large amounts of data have to be encrypted. So that's one of the big advantages of DES.

TNC: How about some of its weaknesses? Recently it's been under attack. I guess there's a history to this.

There was a challenge published in "Scientific American" in 1977.

DS: Actually, the "Scientific American" challenge was relating to RSA. That was a different challenge. But there have been DES challenges. There is one that took place last year. Some data encrypted using DES and was broken after a period of about three months by a large number of people cooperating on different computers all over the world.

And the technique that was used was really just to try every possible key. And this points to the main weakness of DES, is that since the key is a 56-bit key, there are only two to the 56 possible keys that can be used. And two to the 56 is a big number, but it's not that big. And it's reached the point now that with very fast computers and with many computers being available to try all the possible values, you can just take a message and try every possible key until the correct one is found.

That's, in fact, how the challenge was broken.

TNC: How about lengthening the key? What would that do, achieve?

DS: If you use a longer key?

TNC: Would it be possible?

DS: Then it means that there are many more possible keys to test and it increases the security.

Now, DES is built in with a fixed key length of 56. There are some variants of DES. One of them is called Triple DES, where in fact you really run the DES algorithm three times in a row with three different keys. And that has the effect of increasing the key length from 56 to three times 56, or 168.

TNC: Now, because of this vulnerability, the government has decided to phase out DES, correct? And it is actually soliciting a new standard?

DS: Yes, that's right. This problem of key length has long been recognized as a weakness and there's a proposal to adopt what will be called an advanced encryption standard. The solicitation for this was put forward last September, I believe, and various people are putting together proposals for what would be a new block cipher to replace DES. And this is something that should happen within the next couple of years.

TNC: And what are the prospects of the solicitation meeting with an acceptable proposal?

DS: Well, all the proposals that are made will be evaluated and one of the -- there are several criteria that any new system has to satisfy. In particular, it will use much longer keys and longer block length. So I think the proposed block length is being changed to 128 bits and the key lengths would be 128, 192 or 256 bits. So these are certainly long enough key lengths that it would make an exhaustive search, as can be done now with DES, it would make an exhaustive search basically impossible.

TNC: One thing that surprises me is just the process. Aren't there any technologies today that meet the requirements of AES?

DS: Well, there are several popular block ciphers around which use longer block and key lengths than DES. So it's completely conceivable that one of these existing systems or a variation of it might be put forward as a potential system to be adopted as the AES.

TNC: In your book you describe the steps that are involved in the computation of DES encrypted message. There's actually quite a lot. It's about ten steps.

One of them involves S boxes. And from what I understand, all the other computations are linear, but the S box computations are not linear, and that makes them vital to the security of the system.

DS: Yes, that's exactly correct. All of the operations in DES are what are called linear operations. And if you have a crypto system that's based entirely on linear operations, it's going to be completely insecure. So the S-boxes form a really vital component of DES, because they introduce the non-linearity, which really provides the security that is necessary.

TNC: Now, there's been a lot of talk about these S boxes and some people actually believe that they may contain trap doors.

In your book you comment on that and say that it is impossible to disprove such an assertion.

Why is that the case if all the calculations involved in generating S boxes are public?

DS: Well, the S boxes are these, are basically random looking functions. And you can, the actual description of the S boxes is public knowledge. Anybody can analyze them. For all intents and purposes they appear to be random looking functions, and there's no evidence that they're not random looking functions.

I think the only point that I was trying to make in the book was that you can't really, you can't prove that something isn't there. So if some people believe that there's a trap door, there's nothing that I or anybody else can do to convince them that there isn't one there. There's no mathematical way to prove the absence of a trap door.

TNC: So the point is that the cryptography community has not studied S-Boxes thoroughly enough to be able to say that there is no trap door. But the National Security Agency may have studied them enough to actually know that there are trap doors in these S boxes.

DS: Well, people have studied the S-boxes quite carefully, and no one has found anything that would point to any kind of a trap door or anything insecure about them. They've been around for 20 years now, so I think that's pretty compelling evidence that there is no trap door there.

TNC: Maybe we should just define what a trap door is. Because this is going to come back during our discussion of public key systems.

DS: Well, a trap door would be a method by which someone could decrypt the cipher text, other than by using the key that was used to encrypt it. So some kind of a secret, alternative method of decryption, where you don't need to know the key.

TNC: And obviously, we'll come back to that with public keys, but that's a vital and desirable feature of public-key ciphers.

What are some of the weaknesses of DES and how can it be attacked?

DS: Well, really, the main weakness is just the key length. Other than that, DES has proved to be a very well designed and very strong cipher that's still in use actually far longer than it was ever intended to be used initially.

So I think the only real criticism that can be made about DES is that the key length isn't long enough.

TNC: So why actually go through this process of soliciting a new cipher if, maybe just by increasing the key length, the required result could be reached?

DS: Well, as I said before, DES really has a fixed, built-in key length. It is box possible to modify DES along the lines of iterating the algorithm more times. By doing so, you introduce a time penalty.

So I think that people would like to see a cipher that has a larger block size and a larger key length that is also faster than what you would be able to get by just iterating or running DES several times in a row. And another point that is probably relevant here is that DES was designed at a time when chips were much smaller than they are now. So there's a lot of, there's better technology in producing chips. Computers have larger word sizes and things like that that maybe could be taken advantage of in designing a new cipher from scratch, rather than just trying to modify the old one.

TNC: Public key systems are the type of crypto-systems that have attracted the most attention recently. In public key systems, part of the key is made available to everybody.

DS: That's correct. That's the main difference between a shared key or a private key system and a public key system.

In a public key system, there are two different keys. One key is used to encrypt and the other key is used to decrypt. And there's no obvious way to figure out what the encryption key is from the decryption key, or vice versa. And what this means is that the encryption key can be made public. And that means that anybody can encrypt a message, but only one person, only the person who possesses the secret decryption key, can then decrypt the message.

TNC: As an example, I can send you a message encrypted using your public key. You receive the message and you use your private key to decrypt it.

DS: That's right, yes.

TNC: Now, what is achieved by the system that shared key does not achieve?

DS: Well, if you use a shared key system, the question is how does the key get shared in the first place. So by some means, the two people who want to communicate have to somehow agree on a secret, on what key they've going to use, and they have to do this ahead of time, either when they're in the same place, or they have to use some kind of a secure channel to do that.

If you're using a public key system, in contrast, the key doesn't have to be agreed upon by the two people. I can set up my own system. I can choose a public key and a private key. I can put the public key on my Web page so that anyone who wants to can use that public key to send me an encrypted message.

TNC: Now, you state in the book that public key systems do not provide unconditional security.

DS: Yes. That's right, because unconditional security is, means that, essentially that a message can't be decrypted, no matter how much computing time you use to do it, without the key. And public key systems, being based on computational problems, don't have this property.

The type of security is just a way of categorizing the crypto system. And most of the systems that are in practical use today are what are called computationally secure. And that includes the systems like DES, as well.

TNC: Because it's also possible to break DES using massive computing power. So DES is not unconditionally secure, either.

DS: That's right. The only system really that is unconditionally secure is something called the one-time pad, where the secret key is a random bit string of a certain length, and then the message to be encrypted is a bit string of the same length. And what you do is you take the exclusive OR of the two bit strings to form the cipher text.

And that's an example of unconditionally, of unconditional security, because it's provably impossible to decrypt the message unless you know what the key is.

TNC: Now, what are the drawbacks of using the one-time pad system in real life applications?

DS: Well, the very big drawback is that the key has to be just as long as the message is. And you can only use it once.

It's attractive from a theoretical standpoint. But it has very serious drawbacks in trying to use it in practice.

TNC: Now, before we describe any specific public key systems, let's discuss some of the mathematics that actually make this possible.

Obviously, such cipher must possess properties that make it possible not only to make public part of the information, but also to hide another part of the information. How is that achieved mathematically?

DS: Well, the public key systems in use are based on different mathematical problems. The RSA system, which was the first public key system to be proposed, is the security of that system is based on the old mathematical problem of factoring. And the encryption and decryption operations are such that in order that the encryption operation is a public operation, being a public key system. In order to figure out what the decryption operation would be, you would basically have to factor a large number in order to be able to do that.

So as long as someone is unable to factor that number, then they're not going to be able to break RSA.

TNC: And actually there's been developments recently where because of computational power and increased computational power and better algorithms, it's possible to factor larger and larger integers.

DS: Yes, that's right. It's kind of a race that never ends, really, because computers keep getting faster and algorithms get improved and now it's possible to factor much larger numbers than could be done even a few years ago. And this means that in order for RSA to be secure, you have to use larger numbers, numbers that are large enough that they can't be factored by the algorithms that are in use today.

TNC: You actually describe some of the new algorithms in your book.

Is it conceivable that by simply, that progress in that field will actually come up with an algorithm that will be powerful enough to break any cipher based on factoring?

DS: Well, that's difficult to predict. One can never know what kind of algorithms might be discovered in the future. Just by virtue of computers getting faster, the numbers that can be factored will continue to increase at a fairly steady rate.

It would require some kind of a breakthrough, though, a completely new algorithm for factoring, really, to make the system obsolete. And, you know, maybe such an algorithm will be found. It's hard to say.

The other possibility is that some of these new, different types of computer technologies might turn out to be realistic, like quantum computing, for an example. That's highly speculative right now, but if that ever turned out to be a reality, it would pose big problems for factoring problems and for other problems that are the basis of other public key systems.

TNC: We mentioned trap doors. Trap doors are an intricate part of public key systems and they're necessary in order to to expose part of the key.

How is that done mathematically?

DS: Well, in the case of the RSA system, the encryption operation involves taking a number and raising it to a power and then reducing the results modulo another number, so this is a congruence. So the encryption operation is a function of that form. And the decryption operation is another function of the same form. But the power to which you raise the number is different.

And it's the relationship between the encryption exponent and the decryption exponent. That relationship is given by knowing the factorization of a large number.

So the factorization provides a trap door, that if somebody knows that factorization then they can figure out how to compute an encryption exponent from the corresponding decryption exponent, or vice versa. But if someone doesn't know that factorization, they don't have the trap door, then there's no obvious way for them to figure out the decryption exponent from the encryption exponent, or vice versa.

TNC: Factorization is based on two large prime integers. What's interesting here is that we cannot know for certainly that a large integer is prime or not. And actually you describe in the book several algorithms that will simply determine the probability of an integer being prime.

DS: Yes, that's right. In order to set up the RSA system, you need to begin with two large prime numbers and then multiply them together. So the two numbers that you start with have to be prime, and the efficient algorithms that have been developed for primality testing are what are known as Monte Carlo probabalistic algorithms. And it means that you have a test that you can run, and if the algorithm, if the number passes the test, then it may or may not be prime. If the number fails the test, then you know it is not prime.

And what you do in practice is run the test many times with different random numbers. And if a number passes the test 100 times, say, then you're pretty well convinced that it is prime. But you don't have absolute proof of it.

TNC: So this really introduces another element of uncertainty, but one that is negligible and can, for practical reasons, be discarded.

DS: That's right.

TNC: The basic approach to attacking an RSA cipher would be factoring. Massive computational power.

Is there more refined ways of trying to break RSA?

DS: Really, factoring is the only approach that people have found to break RSA. There's no rigorous mathematical proof that RSA cannot be attacked by some other method, but no one has discovered any. So all attempts to break RSA are basically, basically involve trying to factor the modules that's used in the system.

TNC: Now let's talk about available implementations of RSA.

RSA is actually patented technology, is that correct?

DS: Yes, that's correct.

TNC: So somebody owns it.

DS: Mm-hmm.

TNC: And in order to include RSA technology in my software, I would need to license it.

DS: Yes, that's right.

TNC: The company that owns RSA?

DS: That's Security Dynamics.

TNC: Are there several -- is there one holder of the patent or are there several holders?

DS: Well, there are different patents around and some of the patents are going to be expiring fairly soon. So I would -- I don't have the information right at hand. I'd have to look it up.

TNC: How does the process work? I work in my laboratory or office. I come up with this technique for encryption. Then I submit it to the patent office? Is that how -- is it as simple as that? Then nobody else can use it.

DS: Well, if you want to patent something, you have to go through a pretty long, involved process of getting a legal description of the method and then eventually you can submit a patent application.

TNC: It just seems that encryption techniques are really based on known theories and mathematical properties and that it would be difficult to actually determine who is the owner of the technology. But obviously that's not true.

DS: Well, I think it's fairly involved process. But certainly there have been several different cryptographic technologies that have been patented over the years.

TNC: Now, let's talk about implementation on a computer. You describe in your book the square and multiply algorithm that's essential to RSA encryption. Now, this underscores that these techniques, these encryption techniques are only as good as the implementation.

For example, a technique would be useless if it were not possible to compute the formulae it uses in a reasonable amount of time.

DS: That's right. In RSA, the only reason that encryption and decryption is a practical technique is because of this idea of the square multiply algorithm. Because what you're doing is you're raising a number, X, to some power, A. And this number, A, is going to be a huge number, maybe 100 digits long. And you certainly can't multiply X by itself that many times. So there's a mathematical way of being able to compute X to the power A that doesn't involving multiplying X by itself that many times.

So without that mathematical theory, RSA really wouldn't exist because you couldn't do the encryption or decryption in a reasonable amount of time.

TNC: Another feature of public key systems as they're implemented today are digital signatures.

What can you tell us about -- what is a digital signature?

DS: Well, a digital signature is really a way of proving the integrity of data, in other words, that it hasn't been changed or tampered with. So the basic property of encryption is that it provides privacy, that someone can't read it.

On the other hand, a signature doesn't necessarily keep the message secret, but it means that somebody can't change it.

TNC: How does that work in practice? I include a signature with the message I send you?

DS: Yes, that's right. A signature scheme will have two facets to it. It will be one algorithm that will be used to sign a message, and that's going to be a secret signing key. And then there will be another algorithm which will be a verification algorithm, which will use a public verification key. So only one person can sign the message, but anybody at all can verify verify the signature on the message using the public verification key.

So it's almost the opposite situation to a public key crypto system.

TNC: Can you use RSA for digital signing?

DS: Actually, RSA can be used for both encryption and signing because the encryption function and decryption function are basically the same function. Just you're using different exponents.

So, in fact, RSA can be used for signing and for encryption, whereas other public key systems maybe can be used for encryption but not for signing, or vice versa.

TNC: Now, I know for a fact that RSA is not used, is not the preferred method, the preferred algorithm for these digital signatures. Why is that?

DS: Well, I guess it depends who you talk to. The federal standard for signature schemes is not based on RSA. It's based on another signature scheme called ElGamal, and it's been modified a little bit and made into what is called the digital signature standard.

TNC: Now, did the government prefer ElGamal to RSA because of patent issues?

DS: Well, ElGamal is a system that's based on a different mathematical problem than factoring, so it's a completely different system than RSA. Perhaps the -- I don't know if the patent issue was important in terms of setting a federal standard. But the digital signature standard has some nice features, especially in the way that the initial ElGamal scheme is modified. And it actually allows the signature to be made a little bit smaller. So that's an important thing in a lot of applications.

TNC: I guess another requirement is that verification be fast because one message may go out to many, many receivers.

DS: Yes, it's certainly true that a message is signed once and it could in general be verified many times. So sometimes that can be an important consideration, the relative speed of signing and verifying.

TNC: How does a digital signature get included with the message? How is it packaged with the message? I encrypt the signature. I encrypt my message. How do I package them together?

DS: Well, the most common way to do it is to first of all sign the message, sign the plain text message and then encrypt the whole thing, if you want to do signing and encryption.

But, actually, that may be a little bit of an oversimplification. Because the way a signature scheme is used in practice is that you don't sign the whole message. You first of all apply a hash function to the message, which compresses it down to a small, very small piece of data called a message digest. And then the message digest is actually signed. And this is done for reasons of efficiency, mainly.

TNC: Hash functions. These are hash functions similar to the ones programmers use every day in their applications?

DS: Well, they're similar in that they take a very large piece of data and make it into a very small piece of data. So it's a kind of data compression technique, except that the type of hash functions that are used in cryptography have to satisfy different properties than hash functions that are used in applications in databases or other areas of computer science.

TNC: What are some of those properties?

DS: Well, they have to have a one-way property so that you can't take the small message digest and reverse it back --

TNC: To the original message.

DS: -- to the original message. And it's also desirable that they satisfy what's called a collision-free property, that it should be difficult, computationally difficult for someone to find two different messages that have the same message digest. Because the message is the part that actually gets signed.

So if you could find two messages that hashed down to the same message digest, then a signature that works for one message would also work for the other message. And that would obviously be a bad thing to have.

TNC: After I decrypt your signature, I know that you actually sent me the message. I authenticate it. And then the digest actually matches it to the document.

DS: The hash function actually provides some redundancy. And it also enables the signature function to work more efficiently, because you're just signing a small piece of data, namely the message digest, rather than the whole message.

TNC: In your book you also describe some techniques for time stamping messages using the signature.

DS: There are several different schemes that have been put forward to time stamp documents. And the, what you want to accomplish here is you want to say that the certain document was signed at a particular time. And there are time stamping services actually that exist that will do that. And they're quite ingenious, because what they do is link together a whole sequence of messages so that you can make sure that a given message was signed before the next message in the sequence and then after the previous message in the sequence, so you can pin down the time at which it was actually signed.

TNC: How do I go about obtaining a key if I want to start encrypting messages. An RSA key, for example?

DS: Well, you can use an algorithm just to construct your own key. You could do it yourself or you can get a key from a key-serving mechanism or --

TNC: You call them trusted authorities.

DS: Any kind of a trusted authority that might issue keys. Another alternative is for two people to take part in what is called a key agreement protocol, where they send, they follow a certain algorithm where they send messages back and forth, and at the end of the protocol they both possess the same shared secret key. So there are many ways the keys can be created and transported. That's a very important, probably the most important and most difficult area of cryptography.

TNC: It's also common to encrypt a message using a shared key algorithm. That's called digital envelopes?

DS: Yes. This is done for reasons of efficiency again. The public key systems such as RSA are typically 1,000 times slower than a shared key system, such as DES, for example.

So the most efficient way to encrypt your data is to encrypt it using DES.

TNC: How is the DES key shared?

DS: Well, then, the DES key itself is encrypted using a public key system. And then it would be transmitted to someone else.

TNC: Very quickly, Doug, we only have a few minutes left, I would like to talk about elliptic curves, because ECC is really a hot technology right now.

What can you tell us about it, very quickly?

DS: Well, elliptic curve systems are modifications of discrete log-based systems. And the discrete log rhythm problem is the basis of systems such as ElGamal, the digital signature standard, DSS. The discrete log problem is generally defined as a mathematical problem in a finite field.

And the elliptic curve systems use the discrete log problem as it's defined on a mathematical object called an elliptic curve.

TNC: What are some of its applications in real life? Why are people so excited about it?

DS: It's important because you can obtain a similar level of security with a much smaller key. So it has a lot of potential applications to things like smart cards, where the memory is very limited, where you want to use a small key. With elliptic curves, you can use a small key and get the same level of security that you would with RSA with a much larger key, for example.

TNC: Okay, Doug, I'm sorry. We're running out of time. We have to end it here.

Thanks a lot for your time.

Doug Stinson's book is "Cryptography: Theory and Practice.", published by CRC Press. Unfortunately, we were not able to talk about visual cryptography, but you have an article in April's "Dr. Dobb’s Journal" about visual cryptography.

DS: That's right.

TNC: Thanks, Doug.

DS: Thank you.