Sunday, March 31, 2013

How big is RSA keyspace?

The probability that a randomly chosen 30 digit number will be prime, is 1 / (30 * ln(30))

If you multiply that number by 10^30, you have an approximation of the raw bulk of prime numbers exactly 30 digits long.

RSA 1024 is near 310 digits, so the largest prime factor would be 155 digits long. The number of 155 digit keys alone would be 1 / (155 ln(155)) * 10^155. To estimate all possible keys, it would be necessary to repeat that calculation for 154, 153 etc, and add the all in an accumulator.

Key selection algorithms vary, and each implementation may have its own method of ensuring well chosen keys.

No comments:

Post a Comment