In public key cryptosystem, there are often two keys (pub and pri) and two functions (Enc and Dec) such that:

Enc(pub, m) = c
Dec(pri, c) = m

Usually pub and pri are generated as a matching key pair and used together. However, given a ciphertext c, without knowing pri, is it possible to successfully decrypt it into the original plaintext m with a different private key pri' other than pri?

  • 3
    I suppose that there may be equivalent keys in an asymmetric crypto system. Finding one without knowing one of the other keys would however break the system. Can we assume that equivalent keys are ruled out and that the cryptosystem adheres to the common rules for e.g. (padded) RSA? – Maarten Bodewes Dec 24 '16 at 13:04

No, it's not possible. If it was possible it would have a devastating impact on asymmetric cryptography in general.

Most asymmetric cryptosystems rely on mathematically problems that cannot be solved in polynomial time (such as integer factorization, or discrete logarithm).

Let's look at RSA: you choose your $K_{pub} = (n,e)$ and $k_{priv} = (d)$ with $e \in \{1,2,\dotsc , \Phi(n) - 1\}$ to fulfill the following equations:

$$\Phi(n) = (p - 1) \cdot (q - 1)$$ $$\operatorname{gcd}(e, \Phi(n)) = 1$$ $$d \cdot e \equiv 1 \bmod \Phi(n)$$

Every element in a group can have one inverse element at maximum, you can not find a $d'$ for which:

$$d' \cdot e \not\equiv 1 \bmod \Phi(n)$$

So instead of:

$$d_{k_{priv}}(y) = d_{k_{priv}}(e_{k_{pub}}(x)) = (x^e)^d \equiv x^{de} \equiv x \bmod n$$

you will compute:

$$d_{k'_{priv}}(y) = d_{k'_{priv}}(e_{k_{pub}(x)}) = (x^e)^{d'} = x^{d'e} \equiv m' \not\equiv m \bmod n$$

So you will be able to compute the decryption with a different $d'$, but your result $m'$ will have nothing in common with the original $m$.

  • 4
    Actually, what you write above isn't quite correct, because the exponent of the RSA group is not $\phi(n) = (p-1)(q-1)$, but $\lambda(n) = \operatorname{lcm}(p-1, q-1)$, which is a proper divisor of $\phi(n)$. Thus, $d$ and $d'$ are equivalent RSA exponents if and only if $d \equiv d' \pmod{\lambda(n)}$. – Ilmari Karonen Dec 24 '16 at 16:02
  • You are right with your correction of $\phi(n)$ to $\lambda(n)$. Thanks for your addition. But since the private exponent $d$ has to be also computed $\bmod \lambda(n)$ there will still be none other $d' \not\equiv d \bmod n$, which is an inverse of the public exponent $e$, because inverse elements are unique in groups – Jerre Dec 25 '16 at 11:30
  • The inverse $d \equiv e^{-1} \pmod{\lambda(n)}$ is indeed unique modulo $\lambda(n)$, but, as with any modular congruence class, it has multiple integer representatives of the form $d \pm k\lambda(n)$. In particular, if you calculate $d' \equiv e^{-1} \pmod{\phi(n))}$, you will usually find that $d' \ne d$ (and, since $\lambda(n)$ is not generally a divisor of $n$, also $d' \not\equiv d \pmod{n}$), but both still satisfy $x^{ed} \equiv x^{ed'} \equiv x \pmod n$. – Ilmari Karonen Dec 25 '16 at 13:00
  • Can you explain, why Euler's theorem also holds for $d \equiv e^{-1} \pmod{\lambda(n))}$, although the equation $d \equiv e^{-1} \pmod{\phi(n))}$ and therefore $x^{\phi(n)}\equiv 1 \pmod n$ is not full filled? – Jerre Dec 25 '16 at 19:25

Theoretically, decrypt a text with a different secret key (also known as symmetric cryptography) should be impossible. This is why you use the secret key to encrypt using an algorithm and after, you use the same secret key to decrypt the text applying the reverse algorithm.

If you talk about the public key system, also known as asymmetric cryptography, it is impossible too because when you encrypt a text using the public key, you can only decrypt the text using its public key pair. The same occurs if you encrypt a text using the public key, the only key that can decrypt that text is the related private key.

A detail about your question, the secret key is a part of the symmetric cryptography or private cryptography. Normally, the exact key names in public cryptography are 'public key' and 'private key'. However, sometimes the 'private key' is called 'secret key' too.

  • 1
    You seem to have your terminology a bit mixed up. In public key encryption, the messages are encrypted using the public key and decrypted using the corresponding private key. You never "encrypt with the private key" or "decrypt with the public key", but you can sign a message with a private key and verify the signature with the corresponding public key (and it turns out that for some asymmetric cryptosystems -- specifically, RSA -- signing is mathematically similar to encryption, and signature verification to decryption). – Ilmari Karonen Dec 24 '16 at 15:57
  • It was a fail, thank you for your comment. I wanted to say 'using the public key'. Yeah, I know that you can encrypt with your private key and decrypt with the public key to obtain a digital signature because is the way to say that you were who signed that message. – CGG Dec 25 '16 at 11:10
  • 2
    "Secret key" is an acceptable term for the private key in an asymmetric cryptosystem. For example, NaCL uses it consistently throughout its documentation. – jsfierro Dec 25 '16 at 14:23
  • Thank you so much for your detail an0dos, I did not know that. I have corrected that part. – CGG Dec 25 '16 at 21:49

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.