4
$\begingroup$

As I understand, we choose the public and private keys to be mutual inverses. However, it is possible that, in a group, there can be numbers which are their own inverses. E.g. Consider p = 7, q = 3. n = 21, phi(n) = 12. For the group G = {s | gcd(s,21) = 1} there are four numbers 1, 8, 13 and 20 which are their own inverses.

In such a case, it is possible to choose these numbers as both private and public keys. Isn't it?

Let me know if I have understood this correctly.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You seem to be specifically discussing RSA, and not looking at how keys are generated. There are other public-key cryptosystems where the dissymmetry between private keys and public keys is more obvious because they're different mathematical objects. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jul 9, 2019 at 11:48
  • $\begingroup$ Recommended reading (not 100% duplicates, but close): crypto.stackexchange.com/questions/43894/… and crypto.stackexchange.com/questions/2541/… $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jul 9, 2019 at 11:53
  • $\begingroup$ Note that, in the case of RSA, if the public exponent is small (specifically, smaller than the squareroot of one of the prime factors), then the private exponent will always be larger (except for the trivial case of $e=d=1$); for example, for 1024 bit RSA modulus (2 prime), if the public exponent is smaller than 256 bits, this will always be true. Hence, this is not something we need to worry about in practice. $\endgroup$
    – poncho
    Commented Jul 9, 2019 at 12:16

1 Answer 1

Reset to default
10
$\begingroup$

That's correct. In some cases, you could, if you really wanted, make a public key equal the private key. It would completely negate the benefit of using a public key cryptosystem, though, because access to the public key would imply access to the private key. It would turn it into a crappy symmetric scheme.

As noted in comments, most common RSA implementations set the public exponent to a fixed value, usually a Fermat prime like 3 or 65537. In that case, for an appropriately-sized modulus, there is no chance for the private exponent to equal the public exponent. The private exponent is always larger.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Yes, I would think as much. Do the popular implementations take care of this duplication while generating the key pairs? $\endgroup$
    – Girisha Shankar
    Commented Jul 9, 2019 at 8:00
  • 2
    $\begingroup$ @GirishaShankar They don't take it into account explicitly because it can't happen. The public key is always a small, fixed number (usually 65537, sometimes 3, hardly ever anything else) and the private key can't be that small. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jul 9, 2019 at 11:49
  • 2
    $\begingroup$ @NicHartley More precisely, I'm talking about the public exponent (usually written $e$), which is part of the public key. The question uses “public key” in that sense, since it talks about the “public key” and “private key” being mutual inverses. There's a way to look at RSA which makes the two exponents the keys, but it requires defining the modulus $n$ as a parameter which must only ever be used once, which is a complicated way to look at it. A more practical way to describe RSA is that the public key is $(n,e)$ and the private key is $(n,d)$. $e$ is usually 65537 but $n$ is unique. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jul 9, 2019 at 18:55
  • 1
    $\begingroup$ @Gilles That's true, but, if you really tried, you could make $e = d$. $\endgroup$
    – forest
    Commented Jul 12, 2019 at 5:16
  • 1
    $\begingroup$ @Gilles You're right, but OP didn't ask about standard implementations of RSA, just whether or not it's possible in theory (which it is). $\endgroup$
    – forest
    Commented Jul 12, 2019 at 8:47

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.