Deciphering: The Thrill of a Lifetime

3

When I went to graduate school to pursue my master’s degree 35 years ago, I couldn’t have predicted where my study of mathematics would end up taking me. I simply thought I was going to become a math professor.

Before digital communications, the internet, and personal computers became part of our daily lives, cryptography—the area I have devoted my career to—was really only used by the military, diplomats, and spies. So far as the general public was concerned, it wasn’t anything other than a theoretical research area. For me, it was the mathematics—the abstract algebra, Boolean functions, and number theory—that made cryptography interesting.

Beautiful Mathematics

For a long time, the only way you could encrypt radio signals was by using something called “stream cipher,” so named because it encrypts each bit of information as it passes through. My graduate school research mainly focused on generating good keystreams—pseudorandom bit strings that are used to encrypt messages bit by bit. The test of a good keystream is whether it remains secure even if part of the keystream is revealed.

Mathematicians like me love to use Boolean functions and abstract algebra to analyze the security properties of a stream cipher.

Of course, I was exposed to other ideas as well. I learned about the Data Encryption Algorithm (DES), which was the first cryptographic algorithm to become a Federal Information Processing Standard (FIPS). It was through DES that I first heard about an organization called NIST, which published the DES. DES is a block cipher that has a key size of 56 bits, which means if you do an exhaustive search, finding a key will take about 2^56 operations, or 2 multiplied by itself 56 times, a huge number. This was the early 1980s, and at that time, performing 2^56 operations in anything resembling a reasonable amount of time was an impossible task even for the most advanced computers.

That wasn’t to last though. Advances in computing and cryptanalytical techniques eventually made DES susceptible to attack. DES was eventually replaced in 2000 by a much stronger block cipher called Rijndael, which NIST published as the Advanced Encryption Standard (AES) in 2001.

Of course, this happened after I graduated.

Stream and block ciphers both face the same barrier to their widespread application: The communicating parties must share a secret key to encipher and decipher a message. But getting that key into the right hands, and only the right hands, has been a great challenge because either a carrier or a secret channel is needed, both of which can be compromised. Public-key cryptography, which was invented in the 1970s, solves the key distribution problem by using a pair of keys: a public key and a private key. The public key is available to everyone, but the private key is secret. The sender uses the recipient’s public key to encipher the message, and the recipient uses his private key to decipher the message. No secret channel required.

While all this was happening, however, I was teaching mathematics courses at a university. I enjoyed studying these cryptography systems, but I wasn’t thinking much about their application in people’s lives … yet.

Real-World Cryptography

Lily Chen at the Eurocrypt'94 cryptography conference

Here’s me at the “Eurocrypt’94” cryptography conference in Perugia, Italy, while I was in graduate school. I had two papers accepted at the conference, an unusual feat for a grad student. I was pretty happy about it.

For me, the opportunity to pursue my Ph.D. degree at Aarhus University in Denmark opened a magic door. Working with this well-known cryptography research group broadened my view and inspired me to look into many new research areas.  One of these was the “zero-knowledge proof,” a way to prove the truth of a statement without actually revealing any information to a verifier. The zero-knowledge proof turned out to be important for many modern cryptographic schemes.

This was around the same time that some of the first cryptography software toolkits were being made available for banks to use. In fact, my Ph.D. supervisor founded a company to develop cryptography software for applications like this. I wasn’t able to take part because I was a foreign student, but I knew that the cryptographic methods for maintaining privacy for things like electronic cash and voting I was researching would give me similar opportunities down the road.

After I received my Ph.D., my first industry job was with a company in Silicon Valley developing hardware encryption devices using public-key cryptography. As a corporate cryptographer, I was involved in many important decisions and participated in developing the first few cryptographic standards, including X9, standards for the American Bank Association and IEEE P1363.

Encryption Unleashed

In the 1990s, the internet was beginning to connect the whole world. But how do you secure something so huge and so complicated? Because it’s impossible to distribute keys with secret channels on the internet, its architects implemented public-key cryptography to protect the information flowing over it. Public-key cryptography may have been the most fascinating invention of the 20th century, to the cryptographic community anyway, but it was the internet that led to its widespread application.

My skills as a mathematician were stretched even further when I joined a telecom company and began developing security solutions for the third-generation (3G) cellular system. The 3G cellular system marked a dramatic transition from analog to digital, making security extremely challenging. Fortunately, my previous research into the zero-knowledge proof helped me analyze 3G network protocols and develop countermeasures against potential attacks. The research motivated me to co-author a book titled “Communications System Security,” which was published in 2012 by Chapman & Hall/CRC.

Today, everything from automobiles to embedded medical devices to coffeemakers is connected to the internet. People are updating and installing new applications every minute of every day, and every one of these devices and programs is secured by some kind of cryptographic protocol. As a cryptographer, it’s really interesting to see such a broad deployment of cryptographic techniques. On the other hand, for the sake of security, interoperability, and usability, it is extremely important to tailor cryptographic techniques for the implementation environment and also provide proper security strength.

And this is what the Cryptographic Technology Group at NIST is doing: developing cryptographic standards and recommendations for applications’ proper security levels. As the leader of the group, I have been approached by vendors, users, practitioners with all kinds of inquiries about our cryptographic standards. Dealing with new applications and issues has become a part of my daily life. Making decisions is challenging but forces me to understand the application environment and to follow the progress being made in cryptographic research closely.

Every day is a learning experience.

Deciphering the Future

Remember we mentioned that for public-key cryptography, we use a public key and a private key? The public key can be accessed by anyone while the private key is (supposedly) only known by the person receiving the message. But what if someone could figure out what your private key is by looking at your public key?

For example, a public-key cryptosystem called RSA draws its strength from the fact that it is easy to multiply two large prime numbers, but computationally very difficult to do that operation in reverse, i.e., to discover what the two prime numbers are just by looking at their product. With a desktop computer, it would take a quadrillion (10^15) years—more than the age of the universe—to factor a 2048-bit integer used as an RSA public-key.

If factorization becomes easy, then RSA will no longer be secure. But how could something as difficult as factorization become easy?

If one were ever built, a quantum computer could factor the product of two large primes in weeks, if not days. To counter this threat, the cryptographic community is looking for new, hard-to-solve problems that will be able to resist the awesome code-breaking power of these machines, and possibly even use them to create unbreakable codes.

Several years ago, I felt that maybe we would just put what we’ve already created to use for the rest of my career. I did not expect a wonderful cryptography scheme like RSA would need to be retired before I did myself! But we live in interesting times, and technology never stands still. Cryptographers, it seems, will never run out of puzzles to make—and to solve.

*Edited 13 June 2017 to correct a misspelled word

Share.

About Author

Lily Chen

Lily Lidong Chen is a mathematician and leader of NIST's Cryptographic Technology Group. Her research areas include cryptographic protocols, zero-knowledge proof, special featured digital signatures, security protocol design, network security, and security for wireless and mobility applications. Besides authoring research papers, Lily has edited and actively contributed to various standards in cryptography and security.

3 Comments

  1. Very interesting story, Nothing like that back in the late 1950’s when I graduated from college. But I did get a job at Bell Labs and that in itself was considered a major accomplishment for someone who came from a poorly rated high school. but did fine in college.

    • Stephen Villano on

      Rod, that gets complicated. First, there are symmetric and asymmetric encryption systems.
      So, it comes down to what you are trying to encrypt, what infrastructure you are using and even the end point to consider.
      PKI is good, OTP is better. But, a One Time Pad uses a shared decryption key and is one time only. Unbreakable, in theory, but easily broken in practice by losing the key.
      Hence, trade-offs in structure and function, to account for failures, errors, platforms and well, reality.

Leave A Reply