Campus News

"Public Key Cryptography": How Is Your Credit Card Number Encrypted Online?

Story posted November 30, 2000

You want to buy the latest best-selling book or hit CD. So like millions of others, you go online. Typing name, address and credit card number into a computer in order to purchase something is becoming second nature to most everyone. In fact online ordering is up 15% in recent months. But there is always that nagging question: when I type in my personal information, is it secure? Really secure?

Professor Joel Roberts, mathematics, offered insight into this issue at the latest Faculty Seminar Series event with a lecture on encryption and "Public Key Cryptography" (November 29).

The problem is simply stated. You want to send secure information over the internet. You want to send the information to someone you’ve never had contact with before, and ensure that it cannot be used or read by others. At the other end, the recipient needs to be sure the person sending the information is actually who they say they are.

This is accomplished with a cryptosystem, a method of encrypting information so that all the above conditions are met.

Back in the Dark Ages of cryptography (namely, prior to 1975), encryption employed a "symmetric" or "private key" system. A shift cipher encryption, for example, entailed shifting letters of the alphabet forward, so that A would be encrypted as B, etc. So if you bought a bag of apples ("bqqmft"), you might be planning to make a "qjf."

Obviously such an encryption system is not secure, because if you know the rule to encrypt, you also know the rule to decrypt. That apple pie wouldn’t be much of a secret.

Cryptography then advanced to a "public key" system, whereby knowing the method of encryption did not also mean knowing the method of decryption. This method employs "one-way functions," those which are easy to do, but difficult to undo without extra information. In an ideal world, this would be a perfect cryptosystem.

Does the perfect cryptosystem exist? One candidate, the k-RSA cryptosystem, involves taking the remainders after division. If the result is a remainder of 2, for example, it is not immediately apparent that the original two numbers in the equation were 10 and 8. Because there are so many other possibilities, one would assume that only the person actually sending the message (10 and 8) knows the original two numbers. The encrypted message (2) is secure.

Is the k-RSA system completely secure? Unfortunately, while recovering the original information would be difficult if not nearly impossible, a method of decryption does exist. It entails breaking down the numbers in the equation, then rebuilding by working backwards to the original numbers (though one would have to have extensive mathematical training to do so, or a super computer to run millions of combinations). So while the k-RSA system remains a very useful method of encryption, it is not perfect.

The next step up in encryption is a one-way operation that employs multiplication. It is much easier to do a multiplication problem than it is to recover the numbers from the product. It might be known that the final number is 119, but great difficulty lies in finding the two numbers that resulted in that product. (They are 7 and 17.)

This RSA cryptosystem is a commercially viable method employed online, including by some versions of Netscape. The success of such a cryptosystem comes from its use of large numbers. If the decryption key employs two large numbers, and the product is a very large number, breaking the code is a complex task. While the encryption is fast (2342 x 4684), breaking down 10,969,928 to come up with those two numbers is not.

Budding cryptographers can try the k-RSA below:

1. Choose four numbers x, y, z and w.

2. Compute the following:
m = x * y – 1
d = w * m + y
e = z * m + x
n = (e * d – 1)/m

3. If you want a message sent to you, publish e and n and keep d and m secret.

4. To send a message M (which needs to be a number between 0 and n - 1), multiply M by e and take the remainder when you divide by n. Send the answer C.

5. To read a sent message, take C, multiply it by d, and take the remainder when you divide by n.

« Back | Campus News | Academic Spotlight | | Subscribe to Bowdoin News by Email