Wednesday, April 8, 2009

Getting my Nerd On

I spent a hour or two this morning learning about the copyright protection (known as Digital Rights Management or DRM) used by Microsoft for encrypting music files. This is a very complex topic, which reflects the back-and-forth between Microsoft and those that don't believe in copyright. The first effort of the crackers is to remove copy protection from music to which they possess the correct licence. In other words, if you purchase a song and listen to it on your computer, is it possible to then copy it to your iPod, CD player, etc. This turns out to be not so difficult--there are at least two basic methods for doing this.

The much more difficult task is outright cracking a protected file (without having the licence to begin with). This turns out to be very, very hard. Those with an interest in cryptography would enjoy reading about the guts of the Microsoft Encryption scheme here. There are several levels, but the heart of it is what's called Elliptic curve cryptography. This is a version of "Public-Key Cryptography" which is the fundamental method behind most of the encryption we use on a daily basis for protecting our cell-phone conversations, credit card numbers sent through the internet, etc., etc. Essentially, the idea is that I can scatter about a "key" that can be used to encrypt messages for me that only I can read. Even though an enemy may have my public key and a message encoded with it and even the original plain text, they still can't discover what my "private key" is because the mathematical puzzle to be solved is too difficult.
Public-key cryptography is based on the intractability of certain mathematical problems. Early public key systems, such as the RSA algorithm, used the product of two large prime numbers as the puzzle: a user picks two large random primes as his private key, and publishes their product as his public key. While finding large primes and multiplying them together is computationally easy, reversing the process is thought to be hard. It is generally recommended that RSA public keys be 1024 bits in length to render integer factoring algorithms infeasible. (source)

Rather than use the problem of factoring a very large number which is the product of two primes, ECC relies on the problem of finding the discrete Log of an element of an ellipse. The nature of this problem allows for a smaller key size with equivalent strength as the older, large prime number problem.

One of the really cool things about all is that these schemes can be easily broken by a type of computer which has been theorized, but never built. It's called a quantum computer, and it has the ability (theoretically) to easily decode these public-key encryption methods. Of course, no one has yet been able to build such a device, but if (perhaps when) they do, the world is going to shift it a big way. Besides cryptography, quantum computers will make it possible to solve lots of problems that are currently difficult to solve in chemistry, physics, and information technology. So far the quantum computers that have been built have not been able to solve more than trivial questions, but lot of money is funding the research.

I wonder about the implications for quantum computing on the social sciences (including theology). Using game theory, it may be possible to discover and demonstrate the relationships between many kinds of phenomena that are currently intractable. Very cool stuff.


No comments: