2
$\begingroup$

I have a simple question.

Is it more weak to encrypt with the private key against the public key with RSA ?

Like is it easier to "crack", "brake", "solve", "decrypt" when I encrypt with the private key against the public key. Is it really the same process of encryption?

(In both cases we assume that the "breaker" doesn't know any of the keys)

Edit:

To be more precise, is there something that differs in the process of encryption with any of these two keys.

Is the only difference between the public and private is that the private can generate public keys but the public key can not generate private? If I want to encrypt with the private or the public key the result is the same, the encryption is passing by the same steps and then results in a difficult breakable encrypted output?

  • RSA key generated with puttygen
  • PGP encryption / decryption
| improve this question | | | | |
$\endgroup$
  • $\begingroup$ Yes, I know that, but that is not my question. To be more precise: Case 1. I encrypt "hello" with my public key, giving me "crypt1" and send it on the internet Case 2. I encrypt "hello" with my private key, giving me "crypt2" and send it on the internet In both cases, I keep the two keys for me. Is "crypt1" more weak than "crypt2" ? If yes/no why? Thank you a lot. $\endgroup$ – Mathias Osterhagen Dec 13 '19 at 11:12
9
$\begingroup$

the "breaker" doesn't know any of the keys

That goes against the very name of the public key, and rationale for using RSA or any asymmetric cryptography. Let's assume it nevertheless in the first section of this answer.

Is the only difference between the public and private (keys) that the private can generate public keys but the public key can not generate private?

No.

  • The two keys typically are not in the same format.
  • Further, in RSA
    • The exponent in the public key is customarily small.
    • The most common formats for private key include the factorization of the modulus, when the public key never does.
    • Depending on format of the private key and method of generation of the key pair, the private key allows to generate a matching public key, or not. Neither constitute a weakness of RSA.
  • The public key of any secure asymmetric cryptosystem never allows to generate a matching private key.

(assume):

  • RSA key generated with puttygen
  • PGP encryption / decryption

PGP does not give any way to encrypt with a private key, nor decrypt with a public key. Neither does GPG, nor any reasonable OpenPGP implementation. The closest it allows is producing a signature, which leaves the message in clear or removes it. That's totally unsafe or dysfunctional from the perspective of confidential transmission of a message.
Note: When creating or importing a private key, PGP/GPG also generates or import the public key, and that what it uses to encrypt. Correspondingly, the passphrase normally required for private key use is not asked for encryption.

The closest feasible thing matching the question's description would be to swap the public and private key generated by puttygen, before somewhat feeding them to the encryption program. That's not quite trivial, because the two keys are not in the same format. But that's feasible: we change $e$ of the formerly public key to $d$ from the formerly private key, and change $d$, $d_p$ and $d_q$ of the formerly private key to the former $e$, that is $37$ as explained here.

If we do this, the newly made public key will look about normal, except for a large exponent instead of a customary short one ($37$ and $65537$ are common). Encryption will be possible (and measurably slower than usual). Decryption with the newly made private key will be possible (and measurably faster than usual). The question asks if that's less safe than normal encryption is.

Yes, that's less safe in the sense that now an adversary knows the normally secret $d$ in the private key (that's $37$). Thus if somewhat the normally public modulus $N$ gets public, it becomes trivial to decipher. Normally $N$ is in both keys, thus public; and further, encryption programs make no effort to keep $N$ secret: we can't rule out that with some encryption option, $N$ is sent in clear along the plaintext. Or that some attack allows the attacker to know $N$. For a start, PGP and GPG store $N$ in clear in the pubring file, not protected by a passphrase.

If we hypothesize that an attacker only has one ciphertext without $N$, I see no way to obtain $N$ or otherwise decipher or get any useful information about the plaintext.

This perhaps remains true if the attacker has multiple ciphertexts and knows some corresponding plaintexts, assuming hybrid encryption is used (as in OpenPGP). However, with textbook RSA encryption, $N$ can be recovered and security is lost.


[From this point onwards, we again assume the public key is public]

Is it more weak to encrypt with the private key against the public key with RSA ?

Often that's impractical or/and unsafe (see above); but not necessarily. In fact, RSA as taught and practiced today reverses the public and private key compared to the key generation procedure of original RSA (Ronald L. Rivest, Adi Shamir, and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in Communications of the ACM, Feb. 1978). That reversal was originally made for performance reasons, and it turns out that it improves security compared to that in original RSA!

Original RSA has an almost unique characteristic among asymmetric cryptosystems: we indeed can exchange public and private key, and that does not compromise security (including when we reveal the key used for encryption, as designed, see final section). That's because original RSA

  • first selects the decryption exponent $d$ mostly randomly in a large set, then computes the encryption exponent $e$ from that, per the symmetric equation $e\,d\equiv1\pmod{\phi(N)}$
  • public and private keys are in the same format: the public modulus $N$ and an exponent.

It quickly became standard practice to first choose the encryption exponent $e$ (that is, reverse public and private key compared to key generation of original RSA): in Martin Gardner's A new kind of cipher that would take millions of years to break (in the Mathematical Games column of Scientific American, Aug. 1977), Rivest's MIT group used $e=9007$ in a then difficult challenge, implying that $e$ was chosen before $d$. Such small $e$ speeds computations involving that exponent (encryption and signature verification) by a large factor, broadening the practical uses of RSA; but it becomes unsafe to exchange public and private exponents.

It took some time to fully realize that original RSA's prescription "It is important that $d$ should be chosen from a large enough set so that a cryptanalyst cannot find it by direct search" is necessary, but insufficient for security. Selecting a random $d$ in $[2^{135},2^{136}]$ with $\gcd(d,p-1)=1=\gcd(d,q-1)$ blocks direct search of $d$, but would be unsafe for $p$ and $q$ 512-bit or larger primes (see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999).

In original RSA, decrypting is the same as signing, and both are encrypting with public key replaced by private key. However:

  • Original RSA's enciphering is insecure (among reasons: correct guess of the message can be verified with the public key, thus it is insecure to encipher a name on the class roll, a password, or a credit card number).
  • Original RSA's signing is insecure (for different reasons, including: an adversary can find signature of a message showing as any short desired text when printed as a C string; a few rightful signatures of some selected meaningful and sizable messages can be turned into forged signatures of other meaningful and sizable messages).

Weaknesses of original RSA have been fixed, but with modern RSA as practiced (or PGP/GPG and RSA keys), signing is markedly different from encrypting with public key replaced by private key. And many other common signature schemes have no encryption counterpart.

While modern RSA practice distinguish signing from encrypting with public key replaced by private key, it's possible to have the two use essentially the same padding. See Jean-Sébastien Coron, Marc Joye, David Naccache, Pascal Paillier, Universal Padding Schemes for RSA, in proceedings of Crypto 2002 (also there). Note: AFAIK it is not used in practice.


Glossary of things properly named:

  • In public-key cryptography, the public key is made public (the private key is kept secret).
  • In public-key encryption, encryption is with the public key (decryption is with the private key).
  • In public-key signature, signature verification is with the public key (signing was with the private key).
| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ We can also remove the $d , d_p$ and $d_q$ from private key. $\endgroup$ – kelalaka Dec 13 '19 at 12:53
  • $\begingroup$ Exactly what I wanted to know, thank you a lot for this amazing answer. $\endgroup$ – Mathias Osterhagen Jan 2 at 14:59
5
$\begingroup$

In RSA we start with choosing a security parameter $\lambda$ where today we need $\lambda>2048$ i.e. we need at least 2048-bit modulus, key-size recommendations.

We can start with finding two distinct large primes $p \text{ and }q$ such that $n= p\cdot q$

For the public modulus $e$ and private modulus $d$ we start to choose $e$ small so that, at least the one side can use faster calculations. The other parameter, $d$ will be big number and we need it to be a big number due to the Wiener's attack.

We need to choose an $e$ so that $\gcd(e,\phi(n)) = 1$ where $\phi(n)=(p-1)(q-1)$. The usual choices are small prime $e$ like $\{3,5,17,257,\text{ or }65537 = 2^{(2^4)}+1 = F_4\}$ that guarantees small number of modular exponentiation and squarings. (Carmichael lambda $\lambda$ is a better choice instead of $\phi$)

Another approach is first choosing $e$ than the primes $p \text{ and }q$, this can guarantee to choose a specific $e$.

Once we choose $n=pq,e$ we are ready to calculate the private exponent $d$ which can be found using ext-gcd algorithm where $e\cdot d \equiv 1 \bmod \phi(n)$

This was the usual approach and one can see that there is a great difference between $e$ and $d$.

is there something that differs in the process of encryption with any of these two keys.

Yes, there is. The $e$ has chosen small with intentionally. We don't use the public key as the private key and private key as the public key. The name already suggests that; public and private!

An attacker who knows the public modulus can decrypt easily. However, you can start choosing an arbitrary large random $e$ than calculating the private exponent $d$.

the "breaker" doesn't know any of the keys

In this case, the attacker must be able to find the public modulus. If he sees more than one ciphertext, he can figure about it. If a small modulus is not used, this is an extra problem. However, this is not the usual RSA or more generally, public-key cryptosystem. Maybe you need symmetric encryption?

Is the only difference between the public and private is that the private can generate public keys but the public key can not generate private?

We assume the usual definitions; public key $(n,e)$ and private key $(n,d)$. From the public key, we cannot find the private key without factoring or breaking the RSA problem. Of course in practice, the private key contains more than $(n,d)$. It contains $n,e,d, p, q, d_p,d_q,d_{inv}$. The values $d_p,d_q,d_{inv}$ are used for CRT based calculation that can speed up modular exponentiation up to 4-times. Note that, a decryption can still run if we only $(n,d)$.

If I want to encrypt with the private or the public key the result is the same, the encryption is passing by the same steps and then results in a difficult breakable encrypted output?

Well, there is a big conceptual problem here, you don't get someone private key to send the message to them, you get their public key. Assume they swapped them before release, then the result, of course, will not be the same since $e\neq d$. Now, you can try the common public keys.

Also, if we assume that you have given the public modulus and public-key than it is the usual textbook RSA problem and that has many problems. To mitigate this we use padding schemes like se PKCS#1 v1.5 padding or Optimal Asymmetric Encryption Padding (OAEP), Prefer OAEP, PKCS#1 v1.5 has many attacks and hard to implement correctly.

Final note: we don't use RSA for encryption, we prefer to use Hybrid Encryption and for which RSA-KEM is used as a Key Encapsulation Mechanism. The other usage of RSA is the digital signature and this time RSA is used with RSA-PSS

And remember that RSA Signing is Not RSA Decryption!

| improve this answer | | | | |
$\endgroup$
4
$\begingroup$

I didn't know to which answer to attach the following remarks, so I'll just create a separate answer to prove that practically speaking, the use of the private key for encryption is insecure.

Quite often the padding method for signing is used if any "encryption" operation is performed with the private key. The reason for this is that some implementations expect that it is used for signing, e.g. using the weird signature format used within old versions of SSL. In that case the protocol is clearly broken as the PKCS#1 v1.5 method for signing is deterministic, so reusing the key and plaintext would result in the same ciphertext (and if PSS is used, the result would not be reversible, so decryption would not even be possible).

The other problem is that commonly, public key operations are not protected against (side channel) attacks. It is not said that the public key value is not leaked if a non-secure operation is used. Maybe the plaintext value is protected, but there is simply no reason to protect the public key.

Quite often it is simply not possible to swap keys. Private keys have a different encoding format than public keys, so parsing the keys will likely already result in an error. Private keys may also just rely on CRT parameters, and public key operations do not accept those parameters. Finally, public key operations in modern libraries often have limitations when it comes to the size of the public exponent. And if the public key is limited in size then the operation is clearly insecure, as fgrieu has already mentioned in his answer. Many libraries do now even allow a large public exponent to be generated in the first place, and quite often the public exponent is just set to the F4 value of 65537, the fifth prime of Fermat.

One argument in favor of switching the public and private key is that signing is secure. However, that completely ignores how these operations are used, and it ignores the fact that signature generation is not encryption with the private key as explained here. That Q/A also goes a bit deeper into some of the notions of padding schemes briefly mentioned in this answer. And, of course - if considered correct - the answer invalidates this other answer.

| improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ From the first hand, I've noticed that OpenSSL RSA public key encryption was not resistant to side-channel attack. The picture was so clear to distinguish multiplication and squaring. $\endgroup$ – kelalaka Dec 14 '19 at 20:24
-1
$\begingroup$

The strength of the cipher (against cryptanalysis) does not depend on which key of the pair is being used to encrypt your text.

In Public Key Encryption, we encrypt with private key for proving authenticity and we encrypt with public key for confidentiality. In the security domain, authenticity and confidentiality are equally important although they're used in different context. If encrypting with a the private key rendered a weaker cipher, then people wouldn't use their private key for signing (generating digital signature) to prove authenticity.

By the way, the followitn claim made by @fgrieu is entirely wrong: "PGP does not give any way to encrypt with a private key, nor decrypt with a public key. Neither does GPG, nor any reasonable OpenPGP implementation."

All functional crypto-system including PGP and GPG allow us to digitally sign a document or text. Signing an email is merely encrypting the hash of the text with the sender's private key. The receiver, on the other hand, proves the authenticity of the message by decrypting the ciphertext (i.e. the digital signature) with the public key of the sender. For reference, you can take a look at: https://users.ece.cmu.edu/~adrian/630-f04/PGP-intro.html

Note: I couldn't make a comment on @fgrieu's post as I'm new in this community and do not have enough reputation score.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Welcome to CSE! You state: "Signing an email is merely encrypting the hash of the text with the sender's private key". Some of the article you link to supports that error: "The basic manner in which digital signatures are created is illustrated in Figure 1-6. Instead of encrypting information using someone else's public key, you encrypt it with your private key. If the information can be decrypted with your public key, then it must have originated with you". Figure 1-6, and AFAICT the rest of the article, correctly uses "signing" and "verifying". So do PGP and GPG commands and messages. $\endgroup$ – fgrieu Dec 14 '19 at 14:18
  • $\begingroup$ Hi fgrieu, Thanks for welcoming me. Could you elaborate your point please? By the way, you can check any reputable reference material (e.g. the book Network Security Essentials by William Stallings) and you will find that you signing essentially means encrypting with your private key and verification is done by decrypting the cipher with your public key. $\endgroup$ – Newbie Dec 15 '19 at 8:58
  • $\begingroup$ To those who down voted: I would be grateful if you could explain the reasons first and then down-vote. Otherwise, there's no transparency and we don't call it a discussion forum which is here to help us learn. If you cannot show the reason for your action, then please don't take an action. $\endgroup$ – Newbie Dec 15 '19 at 9:18
  • $\begingroup$ After yet another revision, my answer now acknowledges that in original RSA, and also in a variation proposed in 2002 fixing shortcomings of the original, signing is encrypting with public key replaced by private key. I maintain that's not the case in RSA as practiced since the 1980's, nor when using PGP/GPG as a tool, even with RSA keys; nor in many other common signature schemes. I give much attention to such details, which in cryptography sometime are the difference between secure and not. I hope I never was harsh. $\endgroup$ – fgrieu Dec 16 '19 at 7:57

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.