Is the role of public key/private key determined arbitrarily or mathematically?

Cryptography Asked by 北美38fule on January 29, 2021

I have read about conflicting information about the roles of public/private keys.

In one article(Asymmetrical-key algorithms), it says:

Simply put each party, say Alice, picks a private random value, inputs
this into a key generation program, and receives two keys. It is
arbitrary which of these is made public and which is kept private, but
the privacy of the private key is paramount.

While in many other articles, they suggest that private keys is always for decryption and public keys encryption. Or private keys are for the party being authenticated while public keys are authenticating ones.

So my question is, are private keys called ‘private’ only because you keep them private, or because they have some mathematical merits that fundamentally differentiate them from their public counterpart?

3 Answers

Mathematically. It is only true that the public and private sides are arbitrary in the very specific case where you're using textbook RSA with keys that were generated starting with a large, random exponent as in the original RSA paper. This is absolutely not the case for other asymmetric cryptosystems, or even for most implementations of RSA where the exponent is chosen as a small value like 3 or 65537. These small values are obviously not acceptable as private exponents due to their small size and predictability.

Answered by forest on January 29, 2021

The web article states

..a key generation program (produces) two keys. It is arbitrary which of these is made public and which is kept private.

This second sentence is wrong, especially since it appears in a general discussion about "Asymmetrical-key algorithms" (sic: the closer usual adjective in the cryptographic literature is asymmetric, and the concept is better known as public-key).

In most common forms of public-key cryptography, the public and private keys are very different beasts, and we can't exchange them. Examples:

  • Public-key cryptography based on the Discrete Logarithm Problem (DSA, ECDSA, EdDSA, Schnorr signature, ElGamal encryption, ECIES..), where there is a direct method to find the public key from the private key: $text{Pub}=g^text{Priv}$ (or $text{Pub}=text{Priv}times G$ depending on notation), when that's not possible in the other direction (security relies on that).
  • Hash-based public key cryptography, for a similar reason.
  • RSA encryption and signature as practiced, where the public key is $(N,e)$ and the private key is $(N,e,d,p,q,d_p,d_q,q_text{inv})$ (see RSAPrivateKey in PKCS#1 v2.2). And even if we reduce the later to $(N,d)$ so that the two keys become substitutable, doing such substitution would ordinarily ruin security, because ordinarily $e$ is small, thus guessable. Better methods allow to recover $e$ from $(N,d)$ for size of $e$ up to $29.2%$ the size of $N$ (see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999), which covers all values of $e<2^{256}$, often considered as a practical upper limit.

In fact, I can only see that the quoted statement applies to a particular cryptosystem: a form of RSA where $e$ in the public key $(N,e)$ is random and large, and the private key is stored as $(N,d)$. That is barely used because it makes the use of either key several times more costly than in regular RSA with small $e$ (in the hundreds for the public key, like 3 to 4 times for the private key), and almost double the storage requirement of the public key.

Are private keys called 'private' only because you keep them private, or (do) they have some mathematical merits that fundamentally differentiate them from their public counterpart?

The later!

Is public key always for encryption, and private (for) decryption?

No, because there are other uses of public/private keys than encryption and decryption.

When doing encryption and decryption, the public key is always the one used for for encryption, and the private key is always the one used for encryption.

When signing (or demonstrating one's identity), the private key is always the one used. When verifying a signature (or someone's identity), the public key is always the one used.

In the context of an RSA cryptosystem, the expression "encrypt with private key" is sometime used where there should be "sign" or "apply the private-key transformation $xto x^dbmod N$". Same for "decipher with public key" where there should be "verify" or "apply the public-key transformation $xto x^ebmod N$". The web article does that without emphasis on the impropriety, and worse for an unspecified asymmetric cryptosystem. That's a sign of lack of rigor in the material, and sadly is very common. It seems some authors believe that all signatures are based on a trapdoor permutation, like RSA signatures are. I've recently seen that in a standard for train tickets under review, where a drawing explains that the prescribed DSA signature verification compares the hash of the message to be authenticated against the result of decryption with the public key (which is plain wrong). That same misconception is there (which mentions DSA two paragraphs after the drawing).

Answered by fgrieu on January 29, 2021

No this is not generally true, it must be a misunderstanding. The private key could entirely contain the public key and the scheme still be secure, but clearly reversing the roles of the public and private keys in such a scheme would be trivially broken (as now the public key would reveal the private key).

Apart from that it would often not even be clear what encryption/decryption would mean with reversed roles.

The misunderstanding could arise from RSA where there are public and private exponents (not keys) that to some degree are interchangeable.

Answered by Guut Boy on January 29, 2021

Add your own answers!

Related Questions

Would Triple DES-X with 7 keys be much slower than standard Triple DES?

1  Asked on October 24, 2021 by abercrombie-dorfen


Can someone help me understand this?

1  Asked on October 24, 2021 by user80873


Modulo hashing scheme

0  Asked on October 24, 2021


AES/ECB vs AES/CBC for <16 bytes

1  Asked on October 24, 2021 by andriy-gerasika


Pollard Rho Optimization

0  Asked on October 24, 2021


Proof of the Diffie-Hellman Key Exchange

1  Asked on March 7, 2021 by mppub


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir