2005-05-19 21:41:54 UTC
of the keyspace for a given bitsize RSA key?
Before going postal on me, I know that bruteforcing asym. crypto is not
very bright and that keyspace is therefore generally not very
interesting, and bruteforce attack is not my purpose. And I know about
factorization attacks and such, so please... ;)
In symmetric cryptography it is easy to determine the keyspace, since
almost all keys are valid, so 128 bit key = 2^128 keys.
But I assume that, for a X bit RSA key, not all 2^X possible values are
valid keys, given the constraints for generating the key?
One of my crypto books has this formula for generating an RSA key:
1) Pick two prime numbers p and q.
2) Calculate n = p*q (I assume the bitsize limits the maximum value of
n, but it doesn't say so explicitly? So for a 512 bit key, max(n)=2^512.)
3) Calculate ø(n) = (p-1)*(q-1)
4) Select e, so that e is relative prime to ø(n) and e < ø(n)
5) Determine d, so d*e = 1 mod(ø(n)) and d < ø(n)
I know that the number of primes lower than x is x/ln(x).
Also I think it says somewhere that p != q and both should be as large
as possible. This means that |p| = |q| = sqroot(n) = sqroot(2^x) where x
is the keysize in bits.
So that means that the maximum number of values for p and q for a given
bitsize b is 'sqroot(b)/ln(sqroot(b))'.
16 bit keys => sqroot(2^16)/ln(sqroot(2^16)) keys => 46 possible values
for p and q, giving 2070 combinations of the two.
But now my math-abilities fail on me. :-)
How can the number of possible values for e and d be expressed, given
the constraints in 4) and 5)?
Any help is appreciated.