Assume Alice wants to communicate with Bob. Bob provides his public parameters $(g,n,y)$ with $y=g^x$ where $x$ is his secret key

Now Alice wants to send $m$ to Bob. She generates a random $r$ and computes $u = g^r$ and $c=my^r$ and sends back to Bob $(u,c)$.

You intercept $(g,n,y)$ and $(u,c)$ and you also know what $m$ is.

As far as I know, it is still not possible to recover $r$ from this.

But what happens if Alice sends a second message $(u',c')$ with $u' = g^{r'} = g^{f(r)}$, in other words $r'$ can be easily computed from $r$.

Can you recover $m'$ and/or even $r$ ?


The answer obviously depends on what $f$ is. However, we can say a few general things.

If $f$ is a "simple" linear function (e.g. $f(r) = kr$ for most constant $k$), you can recover $m'$ easily. You cannot recover $r$ or $r'$.

If $f$ is a more complex function that is bijective or nearly bijective (say SHA-256), then you probably cannot recover $m'$. You cannot recover $r$ or $r'$.

If $f$ is a sufficiently many-to-one function and its inverse image is sufficiently simple (say $f(r) = r \bmod{2^i}$ for a suitable $i$), you may be able to recover $r$ and $r'$.


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.