In This Corner
Much More Than Salsa
From norteño to reggaeton, Latino music opens a window on the cultural experiences of immigrants to America
Ask The Professor
How do my credit card numbers get transmitted safely on the Internet?
This month’s expert, Ben Hescott, a research assistant professor of computer science, responds:
It used to be, when you wanted to transmit secret information, people who trusted each other would meet in person, exchange a secret key and communicate a message later using that key. One party would write a message, encrypt it using an algorithm defined by the secret key, and the ciphertext, as the encrypted message is known, would be decrypted using an algorithm employing the same secret key.
An example would be something called a Caesar cipher. This cipher is a simple shift in the alphabet. In this protocol, each letter in the message is shifted by a fixed amount—our secret key—to create a ciphertext. If the word to encrypt was “crypto” and the secret key was 7, the ciphertext would be “wlsni.”
That method is called symmetric key encryption, since the encryption and decryption use the same key. The ciphertext is secure as long as the key is hard to find. In the Caesar cipher, the secret key 7 is used to encrypt, meaning that we shift forward 7 letters. To decrypt, the user shifts back 7 letters. This is obviously not a secure scheme, since there are only 26 possible secret keys, and even without a computer, we can easily check all 26.
With online purchases, though, trust is a big problem. While the symmetric key encryption assumes the two parties trust each other, this is not the case with online purchases. Amazon.com, for example, does not trust us—and it shouldn’t. After all, if everyone used the same key for encryption and decryption, I could use my encryption key to decrypt your messages.
Instead of generating a secret key for every customer, Amazon uses two keys: a public key for encryption and a secret key for decryption. Since the two keys needed are not equal, this method is called asymmetric key encryption, or public-key cryptography. The most popular method used for public key cryptography is called RSA, named for the last names of its inventors, Ron Rivest, Adi Shamir and Leonard Adleman.
To understand how an asymmetric scheme works, consider this analogy: Suppose no one but Amazon employees could speak Finnish. Amazon publishes an English-to-Finnish dictionary. Everyone who wishes to do business has one of these dictionaries. This dictionary is Amazon’s public key. But Amazon keeps the Finnish-to-English dictionary private.
To encrypt the word “three,” we look up in the “T” section for the word three. We see that it is “kolme” in Finnish. We send the word “kolme” as our ciphertext. Since no one else speaks Finnish or has a Finnish-to-English dictionary, the only way to decrypt is using the English-to-Finnish dictionary. But this would take too long. Because it is organized alphabetically using the English words, you would have to start reading through all English words looking for a match with “kolme.” Since Amazon has a Finnish-to-English dictionary, decryption is easy; they look under “k” and decrypt back to the word “three.”
On the Internet, mathematical functions are used to encrypt and decrypt. These mathematical functions attempt to create a situation like the one with the dictionary. One such function is the multiplication of large prime numbers. If I asked you to multiply 4,621 by 6,269, you could, with a little work, come up with the answer: 28,969,049. Going in the opposite direction is not as easy. If I gave you 25,534,001 and asked for the two prime numbers that multiply together to give this number, it would take a very long time for you to find out. In fact, as the numbers get larger, about 1,000 digits long, computers cannot compute the prime factors in any reasonable amount of time—think years, not minutes.
So how do we encrypt our credit card? We represent it as a binary number, made up of 0’s and 1’s. We have Amazon’s public key, an exponent and another number, called a modulus, which is the result of two very large prime numbers multiplied together. You multiply your message by itself, exponent number of times. You then divide the modulus into the result. This division is done like long division in grade school, and the remainder is your ciphertext.
To decrypt the code, Amazon uses the two prime numbers that multiply together to make the modulus. This enables the company to quickly decipher your message.
This process is believed to be secure, based on several key assumptions, the major one being that undoing the multiplication of two large primes is not feasible. It is widely believed that this is a reasonable assumption, and our credit card numbers are indeed safe.
