everything looks perfect from far away

I’ve been using cryptography recently for one of my graduate school projects. I’m rusty. Hell, I’ve always been rusty, but I was able to track down my Applied Cryptography book. I begged my mom to buy this for me when I was in high school and she finally caved. I think it’s a great bathroom reader (so much so that the binding has broke). I also used it at Rose in a few classes.

So while I’m reviewing the process of how to authenticate a signature, I spun myself on a tangent and started reading the section on number theory which then lead into prime number generation. Below is an excerpt which caused me to giddily laugh uncontrollably during class. I’m a nerd.

Public-key algorithms need prime numbers. Any reasonably sized network needs lots of them. Before discussing the mathematics of prime number generation, I will answer a few obvious questions.

1. If everyone needs a different prime number, won’t we run out? No. In fact, there are approximately 10¹⁵¹ primes 512 bits in length or less. For numbers near n, the probability that a random number is prime is approximately one in ln n. So the total number of primes less than n is n/(ln n). There are only 10⁷⁷ atoms in the universe. If every atom in the universe needed a billion new primes every microsecond from the beginning of time until now, you would only need 10¹⁰⁹ primes; there would still be approximately 10¹⁵¹ 512-bit primes left.
2. What if two people accidentally pick the same prime number? It won’t happen. With over 10¹⁵¹ prime numbers to choose from, the odds of that happening are significantly less than the odds of your computer spontaneously combusting at the exact moment you win the lottery.
3. If someone creates a database of all primes, won’t he be able to use that database to break public-key algorithms? Yes, but he can’t do it. If you could store one gigabyte of information on a drive weighing one gram, then a list of just the 512-bit primes would weigh so much that it would exceed the Chandrasekhar limit and collapse into a black hole… so you couldn’t retrieve the data anyway.

Now if I could only solve the discrete logarithm problem.