Posted by: tejat | October 19, 2008

## Modular Math and Crypto

Studying congruence groups these past weeks has reminded me of something cool I learned with the high school students I worked with this summer. While we realize that we see an example of mods every day with a clock (mod 12), we also interact with modular math on a regular basis in a way that is much less obvious. In the realm of crypto, there have been many attempts to come up with a foolproof method of encryption, with varying success. The key to a successful encryption is that the person who sends it is able to encode it, and that the person who receives the message is able to decode it, but no one else. One of the most successful codes to date is RSA, which is used, for example, by online companies (like amazon.com). The way it works is somewhat confusing, but basically, when you send the data, it is encrypted via a public key. (In fact, you can look at the public key used by most secure webpages!) This key uses prime numbers and modular math. The general idea is that in order to decrypt the message, you need to know which prime numbers were used to encrypt the data, and that is something that only the recipients of the message know. Here is a website that has more info on the specifics of the algorithm:

http://www.di-mgt.com.au/rsa_alg.html

It’s pretty cool to actually learn how this stuff works! The kids I worked with this summer ultimately each came up with their own keys, and then sent each other encrypted messages and practiced decrypting them.

## Responses

1. Yeah, RSA is a particularly fun application of modular arithmetic! I actually do some cryptography (based on elliptic curves, not RSA) as part of my research. The nice thing about RSA is that you can demonstrate it with paper! You can actually code and decode things by hand and see how it works.

I have my public RSA key on my website, if anyone wants to send me encrypted email. (I generated one for bank transactions with Japan, whose government is a little more careful than ours with financial info.)

2. Hi,

I currently learn cryptography and our teacher explained us RSA recently.

RSA, like many ciphers uses one way functions; functions that are easily calculated in one way, but hardly in the other direction, except if you have some additional information.

For example in the case of RSA, we choose two big primes p and q (1024 bits each is recommanded) and we multiply them to obtain n.

n is our public key (available to anyone willing to send messages to us). On the other end, we will keep p and q to ourselves, it is our secret key.

Anyone who wants to send us a message using RSA will encrypt his message using our public key n. Once encrypted, we are the only ones able to decrypt it because p and q are only known by us.

Thus, RSA is based on the prime number factorisation problem (easy to multiply two primes p, q; but hard to find p,q while only knowing the result of the multiplication).

Stupidly, I asked my teacher if it wouldn’t be possible to just create some kind of database by choosing p and q values, multiplying them to obtain n (easy by definition), then store the (p,q,n) tuple in the database.

Actually my idea was really really bad since if p and q are 1024 bit numbers, then the biggest number that we can consider for p or q is 2^1024-1, which is “close” to 10^309. To know how many prime numbers are < 2^1024-1, we would need to calculate pi(10^309). Just as indication, pi(10^23) = 1 925 320 391 606 818 006 727, and we have to calculate 10^309, not 10^23.

Finally, if we calculate pi(2^1024-1) – pi(2^1023-1), to count how many prime numbers are written with 1024 bits and no less, we still have values bigger than 10^250.

And apparently, people suppose that there would be around 10^80 atoms in the universe, thus all the matter of the universe wouldn’t be enough to store my database.

On another note, thanks for the blog, I enjoy reading it.