Key space vs Cardinality of 1024-bit RSA 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 ?
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&lt;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 Carmichael 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


$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$.
$\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.
Bounds on individual primes $r_i$, such as $2^{(k-1)/m}&lt;r_i&lt;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.
$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.

$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.

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 $&gt;2^{101}$; when $k=2048$ (resp. $k=3072$) this becomes an optional requirement, and large becomes $&gt;2^{141}$ (resp. $&gt;2^{171}$).
For $m=2$, it is common to require that $|p-q|&gt;\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}$.
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.
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.
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&lt;p&lt;b$ and $a&lt;q&lt;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&lt;x&lt;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).