Re: Determine size of keyspace for RSA keys

From: Mike Amling (nospam_at_nospam.com)
Date: 05/20/05

  • Next message: Jean-Luc Cooke: "Re: Determine size of keyspace for RSA keys" 
    Date: Fri, 20 May 2005 16:21:30 GMT

    Roger Schlafly wrote:
    > "Mike Amling" <nospam@nospam.com> wrote:
    >
    >> 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

  • Next message: Jean-Luc Cooke: "Re: Determine size of keyspace for RSA keys"

    Relevant Pages

    • Re: A possible argument for no more Fermat primes.
      ... there has to be a much deeper reason why there can't be more. ... The reason why there are finitely many Fermat primes is simple. ... We are looking at the intersection of two sets: One is somewhat thin ...
      (sci.math)
    • Re: Simple way to show number is a power?
      ... The reason I asked the question was that the methods I have seen ... and had determined the primes in this ring, ... I said it was easy to show there is an infinity ... by using more general quadratic fields? ...
      (sci.math)
    • Re: Rabin vs. RSA/ElGamal
      ... RSA with exponent n = p*q requires that e has no common divisors ... of primes of some order of magnitude, ... is actually a compelling reason, but it might explain why the choice ...
      (sci.crypt)
    • Re: Determine size of keyspace for RSA keys
      ... >> 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? ... > could pick for p times the number of primes that you could pick for q. ... > not increase the private keyspace. ...
      (sci.crypt)
    • Re: A possible argument for no more Fermat primes.
      ... The reason why there are finitely many Fermat primes is simple. ... measure since the number of such sequences is uncountable) ... they are a very very very thin sequence and there is no a priori ...
      (sci.math)