Determine size of keyspace for RSA keys

[Kenneth]

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

[Mike Amling]

Post by Kenneth
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?
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)?

I think it would be reasonable to take the number of primes that you
could pick for p times the number of primes that you could pick for q.
That may be the square of the number of primes whose bit length is
half that of n, or may be something else if, for instance, the process
of choosing tries to prevent p and q from being nearly equal.
While you do have a choice for e, e is public, hence not part of the
private keyspace. d is a function of p, q, and e, hence choosing d does
not increase the private keyspace.

--Mike Amling

[Roger Schlafly]

Post by Mike Amling
I think it would be reasonable to take the number of primes that you
could pick for p times the number of primes that you could pick for q.

I wouldn't multiply. Just take the number of primes that you could
pick for p.

My reason is that the RSA modulus N=pq is public, so q can be
recovered from p. Furthermore, it is insecure to use different values
of q with the same value of p.

So while it is true that once you choose p, you have a lot of freedom
in choosing q, you can only choose one value of q. Once you pick a
q, you can never use another q with the same p.

[Mike Amling]

Post by Roger Schlafly

Post by Mike Amling
I think it would be reasonable to take the number of primes that you
could pick for p times the number of primes that you could pick for q.

I wouldn't multiply. Just take the number of primes that you could
pick for p.
My reason is that the RSA modulus N=pq is public, so q can be
recovered from p. Furthermore, it is insecure to use different values
of q with the same value of p.

I agree. For the same reason that d does not contribute to the
keyspace size, q is a function of p and the public n.
But apparently the group has more than one definition in mind for
"keyspace" applied to RSA. I'm thinking that if there are 2**x possible
keys, and users always reveal y bits of information about the key
they've chosen, then the effective keyspace is x-y bits. E.g., if SSL
uses a 128-bit key and reveals 88 bits of the key, I'd say the keyspace
is 40 bits.

--Mike Amling

[Jean-Luc Cooke]

Post by Mike Amling
I agree. For the same reason that d does not contribute to the
keyspace size, q is a function of p and the public n.
But apparently the group has more than one definition in mind for
"keyspace" applied to RSA. I'm thinking that if there are 2**x possible
keys, and users always reveal y bits of information about the key
they've chosen, then the effective keyspace is x-y bits. E.g., if SSL
uses a 128-bit key and reveals 88 bits of the key, I'd say the keyspace
is 40 bits.

The key space is 40 bits? Or the search space?

--

[Joe Peschel]

Post by Jean-Luc Cooke

Post by Mike Amling
I agree. For the same reason that d does not contribute to the
keyspace size, q is a function of p and the public n.
But apparently the group has more than one definition in mind for
"keyspace" applied to RSA. I'm thinking that if there are 2**x possible
keys, and users always reveal y bits of information about the key
they've chosen, then the effective keyspace is x-y bits. E.g., if SSL
uses a 128-bit key and reveals 88 bits of the key, I'd say the keyspace
is 40 bits.

The key space is 40 bits? Or the search space?

The keyspace is the "search space."

J

[Jean-Luc Cooke]

Post by Joe Peschel

Post by Jean-Luc Cooke
The key space is 40 bits? Or the search space?

The keyspace is the "search space."

I guess what I'm trying to point out here is that the key space you
search doesn't have to be the complete key space. Hence the whole p not
p*q argument kinda of silly.

The key space is p joint q. But if you want to search it. search of p
and you'll find q by virtue of know p*q.

Anyhow, we're all in agreement.

JLC

--

[Roger Schlafly]

Post by Mike Amling
I think it would be reasonable to take the number of primes that you
could pick for p times the number of primes that you could pick for q.

I wouldn't multiply. Just take the number of primes that you could
pick for p.

My reason is that the RSA modulus N=pq is public, so q can be
recovered from p. Furthermore, it is insecure to use different values
of q with the same value of p.

So while it is true that once you choose p, you have a lot of freedom
in choosing q, you can only choose one value of q. Once you pick a
q, you can never use another q with the same p.

[Kenneth]

Post by Mike Amling

Post by Kenneth
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?

<snip>

Post by Mike Amling
I think it would be reasonable to take the number of primes that you
could pick for p times the number of primes that you could pick for q.
That may be the square of the number of primes whose bit length is
half that of n, or may be something else if, for instance, the process
of choosing tries to prevent p and q from being nearly equal.

So is my understanding about where the bitlength applies correct in your
opinion? (And why the heck doesn't it explain that in either of W.
Stallings crypto book and the "Handbook of applied cryptography"?)

I understand your argument that some combinations of p and q should
perhaps be avoided, and also both p and q should be of a certain size (7
and 13 prolly won't do :-), so naturally the number of valid values is
much smaller than just the total number of primes below a given size.

Any idea of what is a reasonable lower limit? For instance one could use
the "next lower bitsize", so that when generating a 2048 bit key, the
primes should be larger than the largest ones used for a 1024 bit key?
That will reduce the n-space marginally.

Post by Mike Amling
While you do have a choice for e, e is public, hence not part of the
private keyspace. d is a function of p, q, and e, hence choosing d does
not increase the private keyspace.

Yes, I understand that.

Hmmm, I still can't figure out if the keyspace can be expressed
mathematically. :-)

Thanks for your comments though, to both of you.

Cheers
Kenneth

[Pubkeybreaker]

"Hmmm, I still can't figure out if the keyspace can be expressed
mathematically. :-) "

Huh? Of course it can. The size of the keyspace equals the number of
n-bit
primes squared. This can be well approximated by the prime number
theorem.

And I disagree with Roger's viewpoint. When selecting a key, we
randomly
select TWO primes p, and q. if each is n-bits there are (2^n)/(n log
2) choices for
each. We choose in pairs, thus there are [ 2^n/(n log 2)]^2 / 2
possible keys.
(approximately) [the final divide by 2 comes from avoiding duplicate
pairs: (p,q)
is the same as (q,p)]

The size of the keyspace is the number of possible different keys we
can generate
from 2 n-bit primes. The part about not choosing the same p for two
different keys
is a red-herring.

[Jean-Luc Cooke]

Post by Pubkeybreaker
The size of the keyspace is the number of possible different keys we
can generate
from 2 n-bit primes. The part about not choosing the same p for two
different keys
is a red-herring.

Agreed. The key-space is as Rob explained. Though perhaps you could
twist yourself into saying "the effective key space is the number of
possible p's". But that's going 1/2 way to saying "the effective key
space is related to the factoring problem".

So you can see how Rob doesn't like taking that approach.

JLC

--

[Roger Schlafly]

Post by Pubkeybreaker
The size of the keyspace is the number of possible different keys we
can generate
from 2 n-bit primes. The part about not choosing the same p for two
different keys
is a red-herring.

If you really want to enumerate all possible keys, then you should
count all choices for the exponent as well.

But you don't. You don't because the user does not want
different keys that use the same p*q and are only different
because they use different exponents.

Likewise, the user doesn't want different keys that share a
value of p, and differ only in q. So I still say to just count
the number of p values.