Cryptography
Cryptography refers to the techniques of making a message understandable only by selected recepients.
There are 2 basic types of cryptography: public key and private key. Each of these is discussed below..
Private Key Cryptography
Private
key cryptography is perhaps the most traditional method of cryptography. One
user would use a key that only s/he knew to encrypt a message using some
function T. Perhaps the earliest cryptosystem was developed by the Greek
historian Polybios. He used a grid of letters where each letter of the message
was replaced by the two letters indicating the row and column in which the
original letter lies. Here is a Polybios square with the English alphabet
excluding the letter J.
S Y D W Z
R I P U L
H C A X F
T N O G E
B K M Q V
Here P would be replaced by RD and G would be replaced by TW.
Another system is the CAESAR system. Although Suetonius claims
that Caesar used this system, Caesar actually replaced his Latin letters with
Greek ones in a way that he did not make fully clear. The system that bears his
name uses a simple technique and a private key. In this system, each letter is
replaced by the kth letter beyond it, where k is the key. For
example, say the message were the word "PRIVATE" and we use the private key k=4.
Under the CAESAR system this would yield TVMZEXI. The user could then send this
message to the recipient who also knew the algorithm and the key. This is a very
simple example of a private key algorithm.
CAESAR is easy to break if an outsider were to know the algorithm, regardless
of whether or not s/he had the key. A person would need only try a maximum of 26
permutations before finding an intelligible word. Most modern private key
algorithms are actually quite more complex and thus difficult to break, but they
all rely on the key remaining private. The problem then becomes the
transportation of the key to the person who will be receiving the message. This
is usually done by a courier, but the cost of frequently changing and
distributing keys becomes quite expensive.
This is where public key cryptography comes into
play. The main idea behind public key cryptography is that not only can one make
his/her algorithm public, one can make his/her key public as well. A person
might publish their public key in a directory, and anyone who wishes to send
that person secure information can encrypt that information using the public key
and send it over insecure channels. Then when the cryptotext gets to the
receiver s/he can decrypt it using their private key. This way, anyone can
encrypt information, but only the person with the private key can decrypt it.
Public key cryptography is very much like looking up someone's phone number in a
large telephone directory. If you know the person's name, like having the
private key, it is easy to find out their information. If, however, you only
have their phone number you would have to search each entry one by one. Thus,
the bigger the possible amount of names, the harder and harder it would become
to find a person.
The idea of public key cryptography was first presented by Martin Hellman,
Ralph Merkle, and Whitfield Diffie at Stanford University in 1976. They used a
method which they referred to as the subset-sum problem, but which has been come
to be known as the knapsack problem. The knapsack problem is based upon the NP
complete problem that, given a container of some specific size and a set of
distinct blocks, one can only find the set of blocks that fits exactly into the
container using an exhaustive search or using special knowledge about the
problem.
S | E | C | R | E | T |
1010011 | 1000101 | 1000011 | 1010010 | 1000101 | 1010100 |
Next we apply that public key to each
letter. Encrypting just the letter S gives us:
B = 1 x (901) + 0 x (568) + 1 x (803) + 0 x (39) + 0 x (450) + 1 x (645) + 1 x
(1173) = 3522
If we then send the number 3522 to the receiver, he can decrypt that using
his private key and the equation B = B * w^(-1) mod m, where w^(-1) is
the multiplicative inverse of w. This gives us: B = 3522 * (901)^(-1) mod
1234 = 3522 * 1171 mod 1234 = 234.
Now we are left to find the combination of A that will yield 234. This is easily done because of the property we mentioned before that each member of A is larger than all of the members to the right of it added together. In this example we get 141+87+5+1 or 1010011 which is the same as the S we originally encrypted. This solution can always be found without the key by trying all of the subsets of A, but if there are hundreds and hundreds of the numbers ai, then the problem quickly becomes unmanageable without the key.
But why does public key cryptography work?
Public key cryptography counts upon the assumption
that there is not a "short-cut" to solving any of these algorithms. According to
complexity theory, if one must try a tremendous amount of possibilities to find
the right one, then the search will not be worthwhile or successful. All public
key algorithms are thought not to be solvable in polynomial time. They are
thought instead to be solvable only in exponential time. There is ongoing debate
as to the question of whether there truly are problems that cannot be solved in
polynomial time. This question is known as the P = NP question, where P is the
set of all equations that can be solved in polynomial time and NP are the
questions that cannot be solved in polynomial time. While most people currently
believe that P does not equal NP, if that assumption were to be proven
incorrect, it would mean that no public key algorithm is entirely safe. Even if
P does not to equal NP, certain algorithms might have a polynomial time
solution, or certain algorithms that are NP complete might have a backdoor, as
was the case with the Hellman, Merkle, Diffie Knapsack algorithm.
While the knapsack problem remains NP complete, Adi Shamir of MIT found a way
for a person without the private key to avoid doing an exhaustive search of the
combinations. Shamir's attack finds the private key that will decrypt something
encrypted with a certain public key, so one can find the key even before a
message has been sent. Shamir's method finds a w and a m (numbers used to make
the public key from the private key - see above) that will work as private keys.
They may not be the same as the original, but they will work the same. The fact
that the private key holder originally used a w and a m guarantee that at least
one of each will exist, and the fact that they need not be prime suggests that
there may be multiple pairs of w and m that will yield the same result. He finds
w& m by graphing aiw(mod m) for all i = 1,...,n. It looks like this