Kenneth

2005-05-19 21:41:54 UTC

I am trying to find out if there is a smart way of expressing the size

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))'.

Example:

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.

Thanks,

Kenneth

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))'.

Example:

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.

Thanks,

Kenneth