2
$\begingroup$

Possible Duplicate:
Why are very large prime numbers important in cryptography?

I'm interested in how the algorithms for creating key pairs to be used in dual key encryption work. I have looked them up and they are a little too much for me to parse at my level but I could really use a conceptual explanation of how prime numbers fit into the picture (they seem to the the key to it all).

Another way of saying this is I know what dual key encryption is and I know what prime numbers are. I would like to understand what properties of the one connects it to the other.

A related curiosity is this: if prime numbers are spread out and hard to find, how is there a seemingly unlimited number of key pairs and how can programs generate them so quickly?

  • 2
    For your "curiosity", the primes of practical length (say 256 to 1024 bits) are indeed sparse, but not so sparse that you can't generate one by picking a random bit pattern an testing whether it is prime. (Rinse and repeat.) Luckily for us, we have efficient algorithms to test primality (with a few provisos that we won't deal with in a comment).2012-07-06

0 Answers 0