0
$\begingroup$

I'm stuck on this, may be due to the fact I'm missing something.
If I'm right, in order to reduce a Message to a point on an elliptic curve the operation is:
$\text{MsgPoint} = \text{msg}\cdot P$ with
- $P$ being the Base point of the curve,
- $\text{msg}$ being the message converted to an integer
- and the operation $\cdot$ being the scalar multiplication

My question is: How do you perform the inverse operation?
formulated differently:
I know $\text{MsgPoint}$ and the Base Point $P$ and I want to find the $\text{msg}$?

In fact, I'm searching a way to retreive the Message from its elliptic point value:
$$P_m + kP_B - n_B(kG) = P_m + k(n_B)G - n_B(kG) = P_m $$ I'm able to get back $P_m$ (decode), but $P_m$ is a Point on the elliptic curve, which is obtained by computing in the encode:
$P_m$ = scalar_mult(message_converted_to_integer, curve.G)
How to get the message_converted_to_integer value?

$\endgroup$
2
$\begingroup$

How to you perform the invert operation ?

Actually, we hope that is a hard problem. After all, if someone has an efficient way, given $G$ and $xG$, to recover $x$, almost all crypto based on elliptic curves is broken (exception: isogeny-based crypto).

So, what do we do? Well, we arrange things so that we don't need to solve this hard problem to decrypt.

One way is the change how we do things. Instead of trying to encode the message as a point, we can use ECIES:

  • We have a private key $k$ and a public key $kG$

  • To encrypt with the public key, we pick a random value $r$, and compute both $rG$ and $r(kG)$. Then, we transform $r(kG)$ into a symmetric key, and use that to symmetrically encrypt the message. Then, the ciphertext consists of both $rG$ and the encrypted message.

  • To decrypt with the private key, we compute $k(rG) = r(kG)$, and use the exact same transforming to turn that into the same symmetric key, and then use that to decrypt the message, revealing the original plaintext.

This works quite well, and avoids any awkwardness about converting a message into a elliptic curve point in a reversible fashion...

$\endgroup$
  • $\begingroup$ Your answer is fine but it is not clear for me that he is actually asking for this. Maybe he asking just encoding a number into a point. $\endgroup$ – kelalaka Dec 1 '18 at 17:44
  • $\begingroup$ In fact, I'm searching the way to retreive the Message from its elliptic point value: Pm + kPB - nB(kG) = Pm + k(nB)G - nB(kG) = Pm I'm able to get back Pm (decode), but Pm is a Point on the elliptic curve, which is obtain by computing in the encode: Pm = self.scalar_mult(message_reduced_to_integer, curve.G) How to get the "message_reduced_to_integer" value ? $\endgroup$ – Gilles06 Dec 1 '18 at 18:15
  • $\begingroup$ Thks kelaka, may be I'm wrong in my code. How do you encode a number into a point ? $\endgroup$ – Gilles06 Dec 3 '18 at 16:13

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.