0
$\begingroup$

The question is pretty self-explanatory but basically I just want to ask if, when choosing the p and q primes that, when multiplied, become the modulus for an RSA public key, is there a risk that attackers can exploit if p and q are equal to each other?

The only requirement that I've seen up until now is that both p and q need to be primes but I never read anywhere about what happens if they are the same number. Basically, p = q and, as such, the square root of the N modulus is p. Is there an efficient algorithm that can detect this efficiently and, as such, factor the numbers and compute the private key? And, if such an algorithm exists, doesn't this mean that this can compromise existing RSA keys with such setups?

Is this even a realistic risk at all or is it just too unlikely to happen in practice?

$\endgroup$
2
  • 4
    $\begingroup$ Hint: the adversary knows $n$ from the public key, and that's $p\,q$ $\endgroup$ – fgrieu Mar 11 at 13:12
  • 1
    $\begingroup$ From wikipedia under RSA_(cryptosystem): "Key generation ... 1. Choose two distinct prime numbers p and q." 'distinct' is a super secret word known only to highly advanced mathematicians that means "not the same". $\endgroup$ – dave_thompson_085 Mar 12 at 3:37
3
$\begingroup$

There is a simple way to detect if a number is square because there is an efficient way to compute square roots.

This should not be a realistic threat as the chance of picking two $b$-bit primes uniformly at random and getting a match will be about $b(\log 2)/2^b$. Given that a broken random number generator that always returns the same value would cause this to happen, it should not be discounted as a threat. However many standards specify a minimum difference between $p$ and $q$ to block Fermat's difference of squares attack (e.g. ANSI X9.31) which should stop such moduli being generated. Moreover, if such moduli were generated, they would not function properly as RSA moduli as the decryption process would not work.

$\endgroup$
2
$\begingroup$

In addition to squares being trivial to factor, if you get $p=q$ then the usual RSA formulas just don't work. RSA exponents $e,d$ are chosen such that $ed \equiv 1 \pmod{(p-1)(q-1)}$. But if $p=q$ then $(p-1)(q-1)$ is not the correct totient of $pq$. Raising to the $e$th power is not the inverse of raising to the $d$th power.

Concrete example:

\begin{align*} p = q &= 7 \\ N &= 49\\ (p-1)(q-1) &= 36 \\ [\mbox{ correct value of } \phi(N) &= 42\,] \end{align*} Choose exponents $e,d$ such that $ed \equiv 1 \pmod{36}$, for example: \begin{align*} e &= 5 \\ d &= 29 \end{align*} Now $x \mapsto x^e \bmod N$ and $x \mapsto x^d \bmod N$ are not inverses:

\begin{align*} 2^e \bmod N &= 32 \\ 32^d \bmod N &= 37 \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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