Sunday, April 9, 2006

Mathematics and internet security


April is math awareness month - this year with the theme of internet security. Are you aware that mathematics is used extensively in that?



By now, we are used to shopping online and to "secure sites" where our credit card information is sent via encryption to the merchant.

But do you know what kind of mathematics is behind that? It is based on number theory - the branch of mathematics that looks at whole numbers and the special properties some of them have, such as being a prime.

In 1970s, a group of researchers developed a way to encrypt and decrypt data WITHOUT the need of the parties first sharing the encryption key.

You see, in traditional cryptography, the two parties wishing to exchange secret information first have to somehow let each other know the encryption/decryption 'key'. And that cannot be encrypted.

What if you can't do that? What if the parties haven't had previous contact with each other to share the key?

This exact problem led to the invention of RSA public-key cryptosystem
in 1977 by Ronald Rivest, Adi Shamir and Leonard Adleman.

It was different from the past cryptosystems because in it, the encryption key is different from decryption key, and the former could be made public.

Since the encryption key is public, anyone can encrypt messages (and send them to the online merchant). But only the party with the decryption key can decrypt them.

This is all based on the fact that some mathematical problems (or operations) are easy to do, while some others are very difficult. For example, it is easy to find large primes, and it is easy to multiply them. But it is very difficult to factor a large integer. So even if the large integer is made public, it's not too likely that someone will recover the two primes that were multiplied.

You can read more in this introductory level article The Mathematics of the RSA Public-Key Cryptosystem by Burt Kaliski who works at RSA Laboratories.

The mathematics behind RSA system is kind of fascinating, but requires understanding what modular arithmetic is. (Which is basically "remainder arithmetic" - 23 mod 4 means 'remainder when 23 is divided by 4'.) If you don't want to delve into all that, you can just skim through the mathematics parts and enjoy the rest of the article anyway.

Another article of interest is "Cracking the Code" by Keith Devlin. In it, he discusses messages (such as password) that are sent scrambled via the use of a "hash" function, and how Xiaoyun Wang (one of the good guys) seems to have special intuition to be able to break the code!

Also visit the main site of Mathematics Awareness Month for more articles and info.

Tags: ,

No comments:

Post a Comment