Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have been trying to figure out the encryption key space, and cardinality of 1024-bit RSA. From my understanding, the key generated from 1024-bit will be primes greater than $2^{1023}$ but less than $2^{1024}$. So, there are approximately $8\times10^{307}$ types of keys that can be used.

Is this the key space or the cardinality, and how do you distinguish the two from RSA ?

share|improve this question
4  
Actually, for 1024-bit RSA, the primes generated will typically be 512 bits each... –  poncho Apr 16 at 21:02

2 Answers 2

up vote 8 down vote accepted

Definitions

In RSA, an encryption key is a pair of integers $(N,e)$ with $N$ the product of $m\ge2$ distinct odds secret primes $r_i$ (with $0<i\le m$), and $e$ is such that $\gcd(e,\lambda(N))=1$ where $\lambda(N)=\operatorname{lcm}(r_1-1,\dots,r_m-1)$ is the Charmichael function. It follows that $e$ is odd. Typically, other conditions are added, like $e\ge 3$ (because $e=1$ gives no security), or that each of the $r_i$ is large for some definition of that (because small $r_i$ can be easily found from $N$, and then are no longer secret). Other conditions are commonly added, and discussed later in this answer.

The most natural definition of encryption key space is the set of pairs $(N,e)$ matching the applicable conditions defined in a particular variant of RSA. The cardinality of the encryption key space is the number of elements in that set if it is finite, else the cardinality is $\aleph_0$ (the cardinality of $\mathbb N$ and all countable sets).

Strictly speaking, by the definition above, the cardinality of the encryption key space of 1024-bit RSA is $\aleph_0$, because we put no upper limit on $e$.

Counting classes of equivalent encryption keys

Different encryption keys $(N,e)$ and $(N',e')$ can be equivalent; that is encryption with $(N',e')$ (including with random padding, which is necessary to make RSA encryption secure) can always be reversed by using a decryption key $(N,d)$ corresponding to $(N,e)$. This occurs when one of the following holds:

  • $N=N'$ and $e\equiv e'\pmod{\lambda(N)}$;
  • for degenerate keys $e\equiv1\pmod{\lambda(N)}$, $e'\equiv1\pmod{\lambda(N')}$, and the bitsize of $N$ and $N'$ such that padding remains compatible; with the two common PKCS#1 paddings, that's when $\lceil\log_2(N)/8\rceil=\lceil\log_2(N')/8\rceil$.

We can thus use an alternate definition of encryption key space where we assimilate equivalent encryption keys (technically: by considering an element of the set as being an equivalence class of the equivalence relation among $(N,e)$ pairs that we just defined).

Now, for $k$-bit $N$

  • there are $2^{k-2}$ odd $k$-bit integers, thus no more possible $N$;
  • for each $N$ we have exactly $\varphi(\lambda(N))$ equivalence classes of encryption keys (where $\varphi$ is the Euler totient function), thus less than $N/4$.

There are thus less than $3\cdot2^{2k-6}$ equivalence classes of $k$-bit encryption keys, about $2^{2043.6}$. This bound could be slightly improved with a better estimate of $\varphi(\lambda(N))$, and removing those $N$ that are either prime or not square-free.

Conditions commonly added to RSA keys

  1. $m=2$ (that is $N$ product of two primes, as in the original RSA paper); this is also mandated by FIPS 186-4. In that case, customarily, we note $p=r_1$ and $q=r_2$.
  2. $\lceil\log_2N\rceil=k$ for $k$ in some limited set, that is $N$ has an exactly prescribed bit length (because that's good for interoperability); FIPS 186-4 mandates $k\in\{1024,2048,3072\}$, with $k=1024$ deprecated.
  3. Bounds on individual primes $r_i$, such as $2^{(k-1)/m}<r_i<2^{k/m}$ (this insures condition 2 for any choice of the $r_i$; helps interoperability of private keys in CRT format; and gives protection against some factorization algorithms). FIPS 186-4 mandates that.
  4. $e\ge e_\text{min}$. Typical values are:
    • $e_\text{min}=3$ (because that's the fastest secure value of $e$ for RSA using good padding); that's mandated by PKCS#1.
    • $e_\text{min}=2^{16}+1$ (because that's less insecure than $e=3$ when insecure padding is used, and other debatable reasons); FIPS 186-4 mandates that.
  5. $e\le e_\text{max}$. Typical values are:
    • $e_\text{max}=e_\text{min}$, which fixes $e$, simplifying things.
    • $e_\text{max}=2^{16}+1$ (this is the most common $e$ around, and I know no reason to use a larger one).
    • $e_\text{max}=2^{2^l}-1$ with $l\in\{5,6,7,8\}$, because that puts an end to using ludicrously large $e$ that waste time, energy, and memory. FIPS 186-4 mandates it with $l=8$.
    • $e_\text{max}=N-1$; that's mandated by PKCS#1. Notice that with this definition, there are always equivalent keys.
  6. Each $r_i-1$ and each $r_i+1$ is known to have a large prime factor, for some definition of large. The rationale is to render some simple factorization algorithms hopeless, and for moderate $\max(\log_2r_i)$ without such requirement it could make sense for an adversary to attempt using these algorithms on each one of a great many $N$, rather than using equivalent effort trying to factor a single $N$ using better algorithms. When $k=1024$, FIPS 186-4 mandates this, with large defined as $>2^{101}$; when $k=2048$ (resp. $k=3072$) this becomes an optional requirement, and large becomes $>2^{141}$ (resp. $>2^{171}$).
  7. For $m=2$, it is common to require that $|p-q|>\Delta$. The only benefits are a simple counterargument to someone pretending that Fermat factorization can factor $N$, and catching a few of the many things that can go wrong in an implementation. FIPS 186-4 sets $\Delta=2^{k/2-100}$.
  8. In addition to condition 6, there might be some upper bound on how large the largest (known) prime factors of $r_i-1$ and $r_i+1$ are. Refer to FIPS 186-4 which has several options in this regard.
  9. In addition to the requirement that each $r_i-1$ has a large prime factor $u$, it has been recommended that $u-1$ has a large prime factor; see this question.
  10. One of many particular key generation algorithm might be specified/used, which will put arbitrary constraints on the $r_i$. For example, algorithm B.3.4 of FIPS 186-4 specifies a deterministic algorithm to generate $N$ from a random seed of exactly $security\_strength$ bits, which (by reference to NIST SP 800-57) must be $80$ (resp. $112$, $128$) when $k=1024$ (resp. $2048$, $3072$).

Evaluating cardinality for a common set of requirements

As example I'll use $m=2$ (cond. 1), $k=1024$ (cond. 2), $a<p<b$ and $a<q<b$ with $a=2^{(k-1)/2}=2^{511.5}$ and $b=2^{k/2}=2^{512}$ (cond. 3), $e=3$ (cond. 4 and 5).

The density of primes near a large $x$ is about $1/\log(x)$, it varies little for $a<x<b$, thus the number of primes in range $]a\dots b[$ is about $t=(b-a)/\log({a+b\over2})\approx2^{501.8}$. Of these, a proportion of about $e-1\over e$ can be used given the requirement $\gcd(e,\lambda(N))=1$. Given that $p\cdot q=q\cdot p$, the cardinality is thus about $(t{e-1\over e})^2/2\approx2^{1001.3}$.

Different key generation requirements can yield vastly different cardinality. For example, the cardinality for 1024-bit RSA with fixed $e$ using algorithm B.3.4 of FIPS 186-4 (see req. 10) is at most $2^{80}$ (and close to that if the seed can take all possible values).

share|improve this answer
    
Excellent answer, would upvote twice if I could. –  Aleph Apr 18 at 17:41
    
fgrieu, Thank you for taking the time to write this detailed explanation. I now have a much greater understanding of the key space and cardinality of RSA, along with a better understanding of RSA in general. –  user3547551 Apr 19 at 2:37
    
Mostly excellent, but in #7 I think you meant m=2 (primes) not k=2 (bits) –  dave_thompson_085 May 1 at 11:05
    
@dave_thompson_085; good catch, thanks –  fgrieu May 1 at 11:31

A keyspace is the set of all possible keys; it's a set. The cardinality of the keyspace is an integer, and is the number of elements in the keyspace. There is no possibility of confusion, because one is a set and the other is an integer.

share|improve this answer
    
Thank you for your answer cpast. So correct me if i'm wrong, 1024-bit key RSA uses 2 primes each 512 bits. Then the keyspace is the set of primes from 2^511 to 2^512 and the cardinality would be the total number of elements in this set? –  user3547551 Apr 16 at 21:21
2  
Actually, the keyspace would be the set of prime pairs between $2^{511}$ and $2^{512}$. Actually, it's somewhat less, because we insist that the product be between $2^{1023}$ and $2^{1024}$. The set of prime pairs between $2^{511.5}$ and $2^{512}$ is one way to evaluate it. –  poncho Apr 16 at 21:22
    
To avoid duplicate moduli we want $p<q$, that about halves the cardinality. And then, what about $e$ ? Setting a fixed $e=3$ reduces the cardinality by a factor of about $4/9$. If $e$ is allowed to vary, and we defined an RSA key as $(p\cdot q,e)$, our cardinality increases (and we should account for equivalent $e$ if very large $e$ are allowed). And then, many practical RSA key generation algorithms only generate primes of a certain form (like, such that $p-1$ and $p+1$ each have a known prime factor of a fixed bit size) and that reduces the cardinality of what they could generate. –  fgrieu Apr 17 at 6:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.