Thursday, September 13, 2007

Identity Problems

New Scientist magazine announced yesterday two independent teams of researchers had developed quantum computers capable of implementing Shor's algorithm. This is a real problem for internet security.

Digital security is built upon various mathematical algorithms. Without going into a whole lot of detail (for the detail-curious, information about the RSA public key encryption algorithm can be read here; RSA is just one of many different algorithmic approaches), many algorithms tend to rely on using prime factorization of very large numbers. To break down a given key, you would need to be able to quickly compute all the prime factors for that number. For very large numbers (several hundred digits), the computation time necessary for this has been such that keys remain essentially secure.

Now that changes.

Shor's algorithm is an approach which allows for non-random determination of the factors of very large numbers (i.e., you don't have to "guess" at factors). It's computationally heavy, but use of quantum computers allows the algorithm to run in polynomial time. I.e., the amount of time to break a given key using a quantum computer would be, at most, the square root of the amount of time it takes now. This speeds things up hugely.

Example: Let's say a given key on Sept. 11 took 1 million seconds to calculate the necessary factors to break. 1 million seconds is roughly equal to 11.5 days. In polynomial time, that takes, at most, 1000 seconds ... or about 16 minutes. Maximum. It could be much faster.

There is a lot of personal data out there being held by banks, businesses, governments which is protected with public key encryption. Names, birth dates, addresses, mothers maiden names, bank account numbers, ssn's, credit cards, etc. Two days ago, that data looked pretty secure.

Today, that data looks pretty vulnerable.

3 comments:

Touchdown said...

my brain hurts.

Sirocco said...

Well, the short version is anything encoded using the standard public key encryption algorithm (RSA) - and that's a _lot_ of commonly held stuff, like bank accounts, for example - will be vulnerable to attack within a couple years (at most), when the ability to create a small quantum computer capable of running Shor's algorithm becomes reasonably doable outside of a research laboratory.

Identity theft is already a problem, but that's largely based on social manipulation (via phishing attacks, for example). Being able to just crack key via brute force calculation will make things much easier, unless a new encryption approach is standardized in rather rapid fashion.

x4mr said...

Very interesting. Humanity has created a real horse race.

Everything is accelerating. Both the dark and light are gaining power.

I have ideas I will articulate later about this, but your post points directly at a key concept. Humanity is facing a collision of biblical proportions.

Horribly oversimplified, but getting at the gist, is that the omnivores, our phenomenally connected children aged 5-20, are about to get really, really, angry with a bunch of rich, fat, white men.

They have cause to be pissed.

Hackers will hack, and defenders will respond. What the hackers get before the response? Unknown.

By the way, Sirocco. I am waiting for your post about Inland Empire.

Cross the border and taste the other side. Lynch is a navigator. Taste Something Else.