4
$\begingroup$

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?

Edit. We do not consider equivalent keys. For example, private keys differing by $\lambda(n)$ in RSA. Because they give identical decryption results for all ciphertexts. In other words, they give identical mappings between plaintext and ciphertext. But still using RSA as an example, there are some other interesting numbers:

$$(p_0,q_0,e_0,d_0)=(17,41,7,23)$$ $$(p_1,q_1,e_1,d_1)=(29,23,5,185)$$ $$m=6$$ $$c_0 = m^{e_0} (\text{mod} \; n_0) = 439$$ $$c_1 = m^{e_1} (\text{mod} \; n_1) = 439$$

In this example, the person with key pair 1 can decrypt a message encrypted using key pair 0. How do we know if there are other messages that are encrypted into the same ciphertext using either key pair? How do we know, in general, how close are two given key pairs? Informally, "close" is defined by the number of messages encrypted into the same ciphertext using either key pair.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 24, 2016 at 13:04

2 Answers 2

Reset to default
7
$\begingroup$

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$.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ 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)}$. $\endgroup$
    – Ilmari Karonen
    Commented Dec 24, 2016 at 16:02
  • $\begingroup$ 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 $\endgroup$
    – Jerre
    Commented Dec 25, 2016 at 11:30
  • $\begingroup$ 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$. $\endgroup$
    – Ilmari Karonen
    Commented Dec 25, 2016 at 13:00
  • $\begingroup$ 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? $\endgroup$
    – Jerre
    Commented Dec 25, 2016 at 19:25
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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). $\endgroup$
    – Ilmari Karonen
    Commented Dec 24, 2016 at 15:57
  • $\begingroup$ 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. $\endgroup$
    – CGG
    Commented Dec 25, 2016 at 11:10
  • 2
    $\begingroup$ "Secret key" is an acceptable term for the private key in an asymmetric cryptosystem. For example, NaCL uses it consistently throughout its documentation. $\endgroup$
    – user40185
    Commented Dec 25, 2016 at 14:23
  • $\begingroup$ Thank you so much for your detail an0dos, I did not know that. I have corrected that part. $\endgroup$
    – CGG
    Commented Dec 25, 2016 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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