 |
Prime Pursuits
|
Ivars Peterson
UNPACKING A KNAPSACK
Secret messages are central figures in a sophisticated, mathematical game
of hide and seek. The players are a small group of mathematicians and computer
scientists adept at inventing and solving puzzles.
They gleefully root out the fatal flaws that may lie hidden within rival
encryption schemes while conjuring up new methods that they hope will resist
such determined attacks. Their digital games continually stretch the limits
of number theory.
To these puzzlers, deciphering a cryptogram such as JXUCQJX UCQJYSQBJEKHYIJ
is a trivial pursuit. In this case, each letter of the original message happens
to be replaced by another letter that is a fixed number of places away; for
example, an A by a C, a B by a D, and so on. Julius Caesar used this kind
of simple cipher more than 2,000 years ago to hide
military information. Modern encryption schemes are much more elaborate and
mathematically complex than Caesar's simple cipher. But are they unbreakable?
The answer to that question is a major concern for the people entrusted with
protecting sensitive data from eavesdroppers, thieves, and spies.
Many cryptographic schemes used today seem to be so secure that the only
obvious way to break them is by trying every possible cryptographic key until
the solution surfaces. An exhaustive search that requires a computer to work
out these trial keys for deciphering the message could easily take years,
even with the fastest computers available. Alternatively, a computer could
consult a ready-made table listing every possible key for a given cipher,
but such a table would probably take up an enormous amount of computer memory.
It's no simple matter to discover techniques for breaking these schemes.
However, conventional cryptography has a serious flaw that opens a potential
window of vulnerability. The sender of secret information must have a key
for encrypting messages and the receiver a key for decrypting those messages.
The sender must have a secure way of transmitting not only the secret message
but also the key needed to unlock it. In other words, any participants in
a clandestine operation must all safely exchange decryption keys before they
can send and receive messages.
In 1976, Martin Hellman and Whitfield Diffie proposed the notion of
public-key cryptography to circumvent the key-exchange problem. In
this system, the encryption key is public and available to all senders, while
the decryption key is kept secret. The security of this system rests on finding
a mathematical way of generating two related keys such that knowing just
one of the keys and the encryption method is not enough to recover the second
key.
Any mathematical operation that enables such a scheme to work must act like
a trap that's much easier to fall into than to escape. Modular arithmetic,
in which only leftovers count, provides such a one-way trapdoor. For example,
it's easy to compute that 23(mod 5) gives the same remainder as 3(mod 5).
However, if the remainder, after division of some unknown number by 5, is
given as 3, there's no way of guessing the original value of that mysterious
figure. It could be 3, 8, 23, or even 63.
Several public-key cryptosystems have been proposed. One is the
RSA scheme, named for its inventors Ron Rivest,
Adi Shamir, and Len Adleman. Their method is based on the observation that
multiplying together two prime numbers is simple, whereas figuring out the
prime factors of a composite number is very difficult.
Using the RSA technique, an individual keen to receive messages would announce
a public key consisting of a large number N
and an integer r. Anyone wishing to send a message to this individual
would transform the message into an integer of length N, dividing
the message into blocks if necessary. The remainder after each block is raised
to the power r and divided by N would be sent as the secret
message.
The recipient's key is another integer, s, to which no one else is
privy. Raising the encrypted message to the power s automatically
unscrambles the message. The recipient is safe from illicit eavesdropping
because the only possible way to compute s requires knowing not just
N but the prime factors of N as well. Therefore, the recipient
has a way of decrypting a message, but everyone else must first factor
N before they can get a crack at breaking any transmissions. If
N is large enough, that task is practically hopeless. In contrast,
because primality testing is quick, the recipient can readily come up with
a suitable 200-digit number N by finding two 100-digit primes and
multiplying them together.
An example illustrates the RSA scheme's fine points. An official at the Central
Security Agency picks any two prime numbers, say, 3 and 11, and multiplies
them together to get 33, the value of N. Next, the official goes through
a special procedure to come up with the two powers, r and s.
The procedure's first step is to subtract 1 from each prime to get the numbers
2 and 10, which are multiplied together. The public number, r, is
any number between 1 and 20 that is not a factor of 20, which eliminates
2, 4, 5, and 10 from consideration. The number 7 is a suitable choice. A
headquarters computer finds a number that when multiplied by 7 then divided
by 20 leaves a remainder of 1. Modular arithmetic guarantees that there will
always be such a number. The number 3 does the job because 7 x 3 = 21, and
21 (mod 20) equals 1. Hence, s can be 3.
Headquarters is now ready to send out its spies, all equipped with the public
numbers 33 and 7. Agent Alice sends a secret message by converting each letter
in the alphabet into a number. The number 2, for example, could represent
the letter B. To send B, Alice writes down 2, raises it to the seventh power
to get 128, then computes 128(mod 33), probably with the help of a handy
pocket computer. The secret message is transmitted as 29. A headquarters
computer decrypts the message by raising 29 to the third power, then calculating
293(mod 33). The unscrambled message is 2.
The RSA scheme is somewhat cumbersome, and building an efficient integrated-
circuit chip to perform the necessary calculations efficiently is tricky.
The slow speed at which the RSA cryptosystem operates means a significant
bottleneck in transmitting large volumes of confidential data. As a result,
mathematicians have also proposed alternative public-key cryptosystems. One
that offers faster encryption and decryption is the knapsack scheme, first
suggested by Hellman and Ralph Merkle.
Knapsack cryptosystems are based on a puzzle known as the knapsack
problem: given the total weight of a knapsack and its contents and the
weights of the individual items that may be in the knapsack, determine which
items are likely to be packed inside so that the total weight adds up to
the given amount. Mathematically, the more general problem involves deciding
whether some members of a particular collection of positive integers add
up to another given integer. If the collection of numbers contains 1, 2,
4, 8, 16, and 32 and the given total is 37, the answer is yes because 1 +
4 + 32 = 37.
In a knapsack public-key cryptosystem, the public key is an ordered set of
n "knapsack weights." To encrypt a message consisting of a sequence
of 0s and 1s (for example, data stored in a computer), the message is broken
into blocks of n bits. Each bit in a block is multiplied by each
corresponding number in the public key, and then all these products are added
together. The answer is the encrypted message. The method's success or failure
depends on the proper selection of these weights in the knapsack.
Merkle and Heliman's idea was to take an "easy" knapsack problem for which
a fast method of solution was known and to disguise it by running it through
a trapdoor to produce a knapsack that masquerades as a "hard" knapsack, one
that takes an incredibly long time to solve. One simple example of an easy
knapsack is the special set of numbers 1, 2, 4, 8.16, and 32. Each number
is 1 larger than the sum of all the previous numbers. If the encrypted message
is 37, it isn't difficult to discover that the actual message is 101001,
because the first, third, and sixth numbers in the knapsack, or public key,
add up to 37.
Merkle and Hellman used a generalization of this example, called a
superincreasing knapsack, as their set of weights. As a trapdoor, they used
a modular multiplication pair. For the pair (28, 71), for instance, each
original weight is multiplied by 28 and then divided by 71. Only the remainders
are written down. This turns the key into the numbers 11, 41, 22, 56, 28,
and 44. To disguise the knapsack further, the order of the items can also
be rearranged. Decryption involves finding a second modular multiplication
pair (in this case, 33 and 71) that converts the public key back into its
original form; the message is again easy to solve. There happens to be a
fast way of finding this reverse modular multiplication pair. More complicated
schemes - iterated knapsacks - require performing several modular
multiplications.
Once the knapsack scheme was proposed, it became the subject of intense scrutiny,
and the game began. At that stage, searching for an effective attack on the
knapsack cryptosystem was like wandering around in a small piece of a maze.
A godlike figure looking down from above can see whether an exit exists,
but the lost soul randomly searching within has no idea whether an escape
route can be found. Nevertheless, early on, some cryptosystem experts suspected
that there might be a way to rip open the knapsack. Nobody knew of one, but
they believed that somewhere in the patterns of digits in the encrypted messages
and public keys were subtle clues that would make it possible to decrypt
any message.
In 1982, Shamir made the first successful attack on the simplest form of
the knapsack cryptosystem. He found that certain information about
superincreasing sequences is not well disguised by a modular multiplication
trapdoor. In addition, this information could be recovered rapidly by solving
a special kind of mathematics problem. Soon after, using a similar approach,
Adleman broke another form of the knapsack cryptosystem known as the
Graham-Shamir knapsack.
Meanwhile, Shamir collected $1000 from Merkle, who had offered that sum as
a prize for anyone who could break his basic scheme. But Merkle, reacting
to the publicity surrounding Shamir's feat and the as-yet incorrect assertion
that all knapsack cryptosystems were no longer secure, offered a new $1,000
prize for breaking the iterated knapsack. That was finally done in 1984 by
Ernie Brickell, then at the Sandia National Laboratories. Brickell's technique
depends on the fact that modular multiplication is the only method being
used to hide the knapsack.
This result doesn't rule out the possibility that a secure knapsack cryptosystem
can be found. However, it means that a method other than modular multiplication
must be used to hide the message. Of course, cryptologists can't resist the
challenge of coming up with a cryptosystem that circumvents the flaws pinpointed
by Brickell's detection technique. Within months of Brickell's discovery,
other schemes appeared, including one based on arithmetic in mathematical
structures called finite fields. But the history of cryptography is
essentially a history of failures. Lots of cryptosystems have been invented
and used only to be proved insecure, sometimes with disastrous results.
Only two serious public-key cryptosystems have been proposed. The knapsack
scheme has already been broken, and the RSA method depends on the complexity
of factoring, which remains an open question. Surprisingly, no other
fundamentally different techniques have been put forward. Left with only
the worrisome RSA scheme, cryptologists and security analysts are frantically
seeking new mathematical bases for secure
cryptosystems.
One central difficulty in all this activity is that no one can yet prove
mathematically that a cryptosystem is secure. All that anyone can say is
that a lot of people have poked and prodded a given scheme for several years
and that nobody has figured out a way to attack it. Current mathematical
techniques are good enough to put a fence around a problem to show where
security lies. They can show that the only way in is through a particular
gate. But how strong is the lock on the gate? Mathematicians still don't
have good techniques for answering that question.
