3
$\begingroup$

I'm not quite sure how to phrase this question mathematically, so I am going to express it in words first:

Let us suppose I have a secret $m_1$ and a plausible innocent secret $m_2$. Is there an encryption algorithm which takes $m_1$ and $m_2$ and combines them with 2 public keys $e_1$ and $e_2$ into a ciphertext $c$ such that when a publicly known decryption algorithm is used on $c$ with private key $d_1$, $m_1$ is returned, but if $d_2$ is used instead, $m_2$ is returned, but without knowing the encryption algorithm used it must be plausible that there is only 1 hidden message?

ie: $$D(E(m_1,m_2,e_1,e_2),d_k)=m_k \qquad k\in\lbrace 1,2\rbrace$$

I am thinking it would require a pair of one-way trapdoor functions mingled together somehow so that it would be difficult to compute $d_k$ from $e_k$. But I also have no idea how to make it plausible that there is only 1 possible $d$ (assuming the ENcryption algorithm is unknown to the enemy).

For example, one naive attempt I had was to append two RSA messages together using the same $n$ value but differing $e$, and then decryption involves splitting $c$ into two parts and discarding the irrelevant half depending which private key is used (can be simply indexed as part of each key). The obvious downside to this method is that if you examine the decryption algorithm it is blatantly discarding half the ciphertext, and the enemy will know straight away that he has not recovered the whole message.

Improve this question
$\endgroup$
5
  • $\begingroup$ Are you just interested in the existence or do you need an efficient way to find $e_i, d_i$ given $m_i$ ($i = 1, 2$)? $\endgroup$
    – Someone
    Commented Jul 14, 2011 at 12:44
  • $\begingroup$ Well, ideally I'd like to know an algorithm that actually works this way, although I don't "need" it. $\endgroup$
    – Damien Zammit
    Commented Jul 14, 2011 at 12:53
  • $\begingroup$ For the existence you could just take the RSA with modulus $m = p\cdot q$ where $\mathrm{gcd}(p, q) = 2$. Then "solve" the discrete logarithm problems $m_i^{f_i} = c \bmod p$ and $m_i^{g_i} = c \bmod q$. If $f_i = g_i \bmod 2$ then you should be able to assemble $f_i$ and $g_i$ to get the public exponent $e_i$, and the chance of both equations to hold should be $\frac{1}{4}$ (if not, take another $m$). $\endgroup$
    – Someone
    Commented Jul 14, 2011 at 13:03
  • 1
    $\begingroup$ If m_1 and m_2 are of comparable length, how are you going to trick the eavesdropper about the quantity of information contained in the message? However you do it, if they only recover a short plaintext from a long ciphertext, they are bound to be suspicious about the apparent inefficiency. $\endgroup$
    – Colin Reid
    Commented Jul 14, 2011 at 16:10
  • 1
    $\begingroup$ To put a positive spin on Colin's comment, one could use steganographic techniques to hide a small $m_1$ inside a relatively large $m_2$. $\endgroup$
    – Gerry Myerson
    Commented Jul 15, 2011 at 1:05

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .