Packing numbers as weapons, fighting online hackers

ROWAN LOPEZ FORKEY | Evergreen reporter

Imagine a knapsack. Now, imagine that same knapsack, but filled with numbers.

This metaphor is at the heart of the Knapsack Problem, an old dynamic program recently revamped by Nathan Hamlin, WSU Math Learning Center instructor and director, and retired professor William Webb. While this code was a relatively simple and easy solution to public key encryption, it was broken on more than one occasion.

In the history of cryptography, secret communication had to be decided on beforehand, in-person. After that, two people would send letters back and forth, both encoding and decoding their special secret code.

Today, people don’t have to meet in person before a private key is used. In fact, they don’t have to meet at all. This is the purpose of a public key.

“If you want to buy something off of Amazon.com, you don’t want to have to meet with an Amazon agent before you send your credit card over the internet,” Hamlin said. “You want to just go to the website and say ‘I’m going to buy this, here’s my credit card,’ and have it be secure.”

Any trusted website hoping to sell something will have a secure server, with a secure page where the user can enter his or her credit card information. The public key makes this screen available to users who want to buy something. When the user enters his or her information and send it off to the vendor, that is private and can only be seen by that vendor.

While the Knapsack Problem is old, Hamlin and Webb’s code is new.

“Mathematically, you’ve got a big number and then you’ve got a lot of smaller integers,” Webb said.

This is where the Knapsack Problem got its name.

“Can you figure out which subset of those smaller numbers adds up to the bigger number?” Webb said. “And in general, that’s a very hard problem.”

A huge threat to the Knapsack Problem, and similar codes, is the prospect of quantum computers. Hamlin described quantum computers as a “massive step forward in terms of computing power beyond the current super computers.”

The main public key code used today is RSA, which uses two prime numbers that are difficult to factor. Even this might be no match for quantum computers.

Although the original Knapsack Code was broken, Hamlin and Webb said they aren’t worried about the security of their new code.

“We’re using some techniques that people working in cryptography probably were not aware of,” Webb said. “It uses some mathematics that didn’t exist back in the ‘70s and ‘80s. At least, people didn’t know about it.”

The original Knapsack Problem used the shortest vector possible – namely, the least small numbers that could fit into the “knapsack” number. This new code doesn’t use the shortest vector to decode the message.

“This method of finding the shortest vector doesn’t help, because you don’t really need the shortest vector. I think that’s one of the essential features of this code, of why it’s secure,” Webb said. “We make sure there’s something special about our vector.”

Many codes that have been broken at one time have also been considered secure. While this is a possibility with the updated Knapsack, Hamlin and Webb said this code promises to be a tough nut to crack.