1
$\begingroup$

Is there an algorithmic, mathematical, technical or implementation "hack" to recover the private key or is it definitively encrypted without any particular mathematical property, like any message M?

$\endgroup$
  • $\begingroup$ This depends heavily on what method of encryption you used. An IES scheme (typical with ECC) relies on a randomized symmetric key. It will probably weaken the problem of "find my private key" to the weakest of the two though. I imagine the same happens to RSA, but I'm not too much into RSA to comment on it. $\endgroup$ – Ruben De Smet Jul 22 at 17:16
  • $\begingroup$ What is the point of this question? $\endgroup$ – kelalaka Jul 22 at 17:28
  • 2
    $\begingroup$ BTW: the standard terminology for this type of operation being safe is "circular security" $\endgroup$ – poncho Jul 22 at 17:35
  • $\begingroup$ @kelalaka 1. It happened to me once (shoot himself in the foot). 2. This is a question I ask my students in a quiz. $\endgroup$ – Benoit LEGER-DERVILLE Jul 22 at 19:08
3
$\begingroup$

With RSA or ECC, if I encrypt my private key with my public key, is there a way to recover my private key?

No, at least for usual or safe definitions of encrypt: anything involving hybrid encryption (ECIES…) or random padding (RSAES-OAEP in ECB mode¹, likely RSAES-PKCS1-v1_5…). Argument (not a formal proof, but still strong): without the private key, we can't decipher a ciphertext for random unknown plaintext. That condition applies for hybrid encryption and OAEP padding, and is approached for PKCS#1 random padding.

That argument does not apply for an arbitrary scheme (as rightly pointed in that answer). And it does not apply for direct textbook RSA encryption of the private exponent $d$, which sometime is assimilated to the private key. The problem then boils down to: given an RSA public key $(N,e)$, and $c=d^e\bmod N$ with $d$ a valid RSA private exponent, can we factor $N$? I find no way, but that's far from a valid argument. I asked there.


¹ As discussed in comments, size restrictions make it hard to RSA-encipher the private key with proper padding. That requires splitting it into multiple blocks, which is unusual and inneficient. I retract my statement that it is commonly supported by crypto APIs.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Actually, with proper padding, one cannot encrypt their private key with RSA since the padding reduces message space. $\endgroup$ – kelalaka Jul 22 at 19:12
  • $\begingroup$ @kelalaka: some APIs, including Java I believe [retracted], nevertheless do it, by splitting the plaintext into maximum chunks. That's poor practice (time and space overhead) but at least it allows decryption and gives confidentiality. $\endgroup$ – fgrieu Jul 22 at 19:15
  • $\begingroup$ I did not found any evidence for Java, rather the opposite ( on SO). If a library goes in this way, the proper action is to move away from that library. $\endgroup$ – kelalaka Jul 22 at 19:21
  • $\begingroup$ "RSA/ECB" is a misnomer in Java, it should be "RSA/None" really (and accepted as such by the Bouncy Castle provider). It certainly does not split the plaintext or anything like that. It's a bit like "AES/.../PKCS5Padding" which also doesn't make sense. $\endgroup$ – Maarten Bodewes Jul 23 at 13:46
  • 1
    $\begingroup$ @kelalaka: you are right, the standard Java crypto API Cipher.doFinal throws an error on the tune of "javax.crypto.IllegalBlockSizeException: Data must not be longer than 190 bytes" when the capacity of RSA/ECB/OAEPWithSHA-256AndMGF1Padding is exceeded. It's up one notch in my mental scale for doing so. BouncyCastle(151) says "java.lang.ArrayIndexOutOfBoundsException: too much data for RSA block", also OK. Hum, where did I get that idea that some Java thing actually does RSA/ECB when asked to do so? $\endgroup$ – fgrieu Jul 23 at 13:58
4
$\begingroup$

Although there is an answer here saying "no" for usual definitions, I want to strongly warn that there is no rigorous basis for that. Specifically, it is true that there is no known way of recovering a private key from an encryption of it with its associated public key. However, there is also no proof whatsoever that it isn't possible. Security of this kind is called "circular security" and there has been researching understanding it. In general, it is possible to achieve this in the random oracle model (quite easily - since the random oracle breaks the mathematical connection between the keys). Specifically, the encryption ${\sf enc}'_{pk}(m) = ({\sf enc}_{pk}(r), H(r) \oplus m)$ is circular secure when $H$ is modelled as a random oracle (meaning that it's secure when taking $m=sk$ or the like), as shown by Camenisch-Lysyanskaya in their EUROCRYPT 2001 paper titled An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. However, in general, there are no reductions from the security of the encryption scheme in general to the case of encrypting the private key, and one should be careful.

| improve this answer | |
$\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.