1
$\begingroup$

I was reading: Is sharing the modulus for multiple RSA key pairs secure?.

My question is: Given a 1024 bit modulus, how many pairs of 512 bit p's and q's are there that would be able to be combined to create a 1024 bit modulus for use in RSA?

Since a 1024 bit modulus has not been factored, I am guessing we don't know, but I wonder if there is an equation?

I thought it would only be one set honestly: one p and one q multiplied together to get n. (Mainly because they only show 1 set in the wikipedia article: https://en.wikipedia.org/wiki/RSA_numbers#RSA-768)

Maybe I don't understand but the side question would be: Given a 1024-bit modulus, how many pairs of e and d could one come up with?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Given a 1024 bit modulus, how many pairs of 512 bit p's and q's are there that would be able to be combined to create a 1024 bit modulus for use in RSA?

The fundamental property is that any integer is a product of a unique multiset of primes. As such, given an integer $n$ that is a product of two primes, those are the only two primes that, multiplied together, produce that $n$. So, the answer is 1 (if you ignore swapping which prime you call $p$ and which you call $q$). The fact that factorization is difficult means that it's hard to produce $p$ and $q$ given $n$; however that doesn't change the fact that $p$ and $q$ are unique).

Given a 1024-bit modulus, how many pairs of e and d could one come up with?

That is a harder question to answer; given that there is no natural bound on how large $e$ and $d$ can be (as you can find arbitrarily large values that work), one answer might be "infinite".

If we ask for the number of $e, d$ pairs where both are limited to $\textit{lcm}(p-1, q-1)$ (which may sound like an odd limit, but turns out to be reasonable), well, we first note that $e$ can be used as a public exponent iff it is relatively prime to $\textit{lcm}(p-1, q-1)$. In addition, for any $e$ which can be used as a public exponent, there is a unique $d$ within the range that works as the decryption exponent (which is why that odd looking limit is a reasonable one), hence counting potential $e$ values is equivalent to counting $(e, d)$ pairs. And, given that the number of values relatively prime to $\textit{lcm}(p-1, q-1)$ is $\phi(\textit{lcm}(p-1, q-1))$, well that's your answer (or one less, if you don't count the $e=d=1$ pair.

Improve this answer
$\endgroup$
6
  • $\begingroup$ One can have a good approximation by the help of Prime Number Theorem. The function $\pi(x)$ is approximated by $\frac{x}{log(x)}$ gave the number of primes less then x. The number of prime pairs to compose 1024 moduli is then something like $2.(\pi(2^{512})-\pi(2^{511}))$. $\endgroup$
    – Robert NACIRI
    Commented Oct 30, 2016 at 19:24
  • $\begingroup$ @RobertNACIRI: yes, but the question was about the number of factorizations of one specific $n$, not the number of possible 1024 bit $n$ $\endgroup$
    – poncho
    Commented Oct 30, 2016 at 19:29
  • $\begingroup$ One additional remark: If you require that your crypto system is secure then you cannot share n and use different values d and e. In that case, if you know one d you can calculate any other d. $\endgroup$
    – user27950
    Commented Oct 31, 2016 at 6:40
  • $\begingroup$ it then seems like we are saying a 1024 bit RSA certificate can have various different private key values - as compared to 'just one'. $\endgroup$
    – james626
    Commented Jul 14, 2017 at 20:13
  • $\begingroup$ @james626: yes, if $d$ is a valid decryption exponent, then so is $d + k \cdot \text{lcm}(p-1, q-1)$ for any integer $k$; this gives an infinite number of possible private keys... $\endgroup$
    – poncho
    Commented Jul 14, 2017 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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