What determines the number of possible RSA key pairs for a given $n$?
Is it because $\varphi(n)$ produces the number of values that are less than $n$ and coprime with $n$?
Is it as simple as $\varphi(n)$?
$\begingroup$
$\endgroup$
7
-
3$\begingroup$ Is the question asking for the number of possible RSA key pairs for a given $n$, or for $n$ of a given bit size? When do we count two key pairs are distinct: when using them leads to different encryption, or when their value are distinct ? In the later case, what exactly do we count as valid: any restriction on the range of $e$ ? Of $d$? What's the relation between them in a valid key pair (even that varies)? $\endgroup$– fgrieu ♦Commented Feb 5, 2021 at 18:19
-
$\begingroup$ im looking for "number of possible RSA key pairs for a given n" $\endgroup$– kinglyCommented Feb 5, 2021 at 18:52
-
3$\begingroup$ "number of possible RSA key pairs for a given n" is infinite; if $(e, d)$ is a valid key pair, so is $(e + a \lambda(n), d + b \lambda(n))$ for any pair of integers $a, b$ $\endgroup$– ponchoCommented Feb 5, 2021 at 19:17
-
$\begingroup$ Doesn't e and d have to be <n? $\endgroup$– kinglyCommented Feb 5, 2021 at 19:27
-
1$\begingroup$ @kingly: no, there is no mathematical reason why they have an upper bound. Now, some RSA standards or implementations may have such a bound, but if you're talking about it in abstract terms, no, there's no bound $\endgroup$– ponchoCommented Feb 5, 2021 at 22:12
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
How to calculate number of possible key pairs in RSA
Well, if we bound the acceptable $e, d$ values to, say, $(0, \phi(n))$ (as I pointed out in the comments, if we don't have such a bound, then the number of such pairs is infinite), then the number of such pairs is:
$$(\gcd( p-1, q-1))^2 \cdot \phi( \lambda( n))$$
Or possibly one less, if you arbitrarily disqualify the $e=d=1$ pair.
It's fairly straight-forward to see that this is true; if we limit the bounds to $(0, \lambda(n))$, then for every $e$ relatively prime to $\lambda(n)$, there is precisely 1 value of $d$ in that range that is a valid pair; and because there are $\phi( \lambda(n))$ such values $e$ which are in that range, that means that there are that many valid pairs in that range.
However, we specified a larger range $(0, \phi(n))$; it turns out that for all valid pairs $(e, d)$ in the original range, all pairs of the form $(e + a\lambda(n), d + b\lambda(n))$ (for integer $a, b$) are also valid (and for any valid pair, there is a unique representation $(e, d, a, b)$ tuple (with $e, d$ being a valid pair in the $(0, \lambda(n))$ range)).
With that in mind, we can see that, for any $e$, there are exactly $\gcd(p-1,q-1)$ values $a$ for which $e + a \lambda(n)$ is in the range $(0, \phi(n))$, and similarly there are $\gcd(p-1,q-1)$ values $b$ for which $d + b \lambda(n)$ is in the range $(0, \phi(n))$; hence for any $(e, d)$ pair in the smaller range, there are $(\gcd(p-1,q-1))^2$ such pairs; because we have already seen there are $\phi(\lambda(n))$ such pairs in the smaller range, this gives us the formula for the bigger range.
