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

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

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?

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

Related Questions

A modification of the Blum-Micalli construction

1  Asked on October 24, 2021

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

1  Asked on October 24, 2021 by abercrombie-dorfen

Publicly verifiable secret sharing scheme

1  Asked on October 24, 2021 by fiono

DTLS vs direct use of AES. What are the threats unique for direct use of AES instead of DTLS?

1  Asked on October 24, 2021

Can someone help me understand this?

1  Asked on October 24, 2021 by user80873

ZKP for product of two primes

2  Asked on October 24, 2021 by yacovm

How does second pre-image attack on Merkle Signature Scheme work?

1  Asked on October 24, 2021

Modulo hashing scheme

0  Asked on October 24, 2021

How do herding attacks on hash functions work?

1  Asked on October 24, 2021

Has the ECDH protocol been designed just for key exchange or is it widely used for key exchange?

1  Asked on October 24, 2021 by manish-kaul

AES/ECB vs AES/CBC for <16 bytes

1  Asked on October 24, 2021 by andriy-gerasika

How to implement arbitrary s-box in a side-channel-free way in C?

0  Asked on October 24, 2021

Should I use self generated or predefined RFC 7919 DH groups?

1  Asked on October 24, 2021 by wedi

What’s the least computationally expensive way to verify a message is from who they say they are?

1  Asked on October 24, 2021 by alexandhisscripts

AES-256, CBC, plaintext length is multiple of block size: Does PKCS #7 padding weaken the encryption?

1  Asked on October 24, 2021

Pollard Rho Optimization

0  Asked on October 24, 2021

How can a collision attack using MD5 be used to break WOTS

1  Asked on October 24, 2021 by evernal

Is there any examples of information-theoretic secure MPC for dishonest majority against malicious adversary?

1  Asked on October 24, 2021 by shoy700

Are the asymmetric roles of the two keys in the elliptical curves the same (as for RSA)? Can they be interchanged indifferently?

2  Asked on October 24, 2021 by benoit-leger-derville

Proof of the Diffie-Hellman Key Exchange

1  Asked on March 7, 2021 by mppub