18
$\begingroup$

So I think I understand a good amount of the theory behind elliptic curve cryptography, however I am slightly unclear on how exactly a message in encrypted and then how is it decrypted. So my questions are

  • How are messages encrypted and decrypted?
  • How are the public and private keys determined?

Thanks for the help

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Private key: some random integer $a$, Public key: $a\cdot G$ where $G$ is the group generator. Encryption: ElGamal, ECDH or ECIES (all similar) $\endgroup$
    – SEJPM
    Dec 30, 2015 at 22:24
  • $\begingroup$ Use this one to debug 8gwifi.org/ecfunctions.jsp $\endgroup$
    – anish
    Dec 18, 2017 at 4:21

1 Answer 1

Reset to default
29
$\begingroup$

How are messages encrypted and decrypted?

Well, the easiest way to do public key encryption with ECC is to use ECIES. In this system, Alice (the person doing the decryption) has a private key $a$ (which is an integer) and a public key $A = aG$ (which is an EC point); she publishes her public key $A$ to everyone, and keeps her private key secret.

Now, when Bob wants to pass a note to Alice, he first picks a random value $b$, and computes the points $bG$ and $bA$; he then gives the point $bA$ to a key derivation function $h$, which produces a set of symmetric keys; he then uses the symmetric keys to encrypt (and MAC) the message. He then sends the values $bG$ and $\operatorname{Encrypt}_{h(bA)}(\text{note})$ to Alice.

When Alice recieves these two values, she first computes the point $a(bG)$, which is the same as $b(aG) = bA$; she then passes that point to the same key derivation function, which produces the same symmetric keys that Bob had. She then decrypts the value $\operatorname{Encrypt}_{h(bA)}(\text{note})$, recovering the note (and verifying that it wasn't modified in transit by checking the MAC.

If you examine this, you can see what Alice and Bob are effectively doing is performing an Elliptic Curve Diffie-Hellman operation, and then using the shared secret to (symmetrically) encrypt a message. This might seem like we're cheating a bit, however this meets the criteria for public key encryption (anyone with the public key can encrypt, only the holder of the private key can decrypt), and it also sidesteps the issue of translating the message into an elliptic curve point reversibly (which can be done, but it can be kludgy).

How are the public and private keys determined?

That's easy; for just about any ECC method, the private key is a random integer $a$ between 1 and $n$ the order of the generator, and the public key is $aG$, the point multiplication of the private key and the generator (which is just a point on the curve that everyone agrees upon). And, in case you haven't come across this in your studies, the order of the generator $n$ is the minimal value such that $nG$ is the "point at infinity"; when we select the curve, we make sure that this is a large prime.

Improve this answer
$\endgroup$
9
  • $\begingroup$ $nG$ is not neccessarily the point at infinity. $nG$ is always the neutral element. For Edwards curves (which don't have the point at infinity) said neutral element is in fact $(0,1)$. $\endgroup$
    – SEJPM
    Dec 31, 2015 at 10:48
  • $\begingroup$ @poncho Thanks for clarifying that, clears it up for me. On a side note, do you know of any resources which actually explain this process so I can reference them? I know its a bit of an ask, but it would be appreciated! Thanks nonetheless for the help $\endgroup$
    – Ali
    Dec 31, 2015 at 11:55
  • $\begingroup$ It would be helpful to explain the notation. aG does not mean multiplication. $\endgroup$
    – Tuntable
    Apr 11, 2018 at 21:01
  • 1
    $\begingroup$ @HelinWang: actually, you mean 'only Bob can decrypt'. In any case, we insert a MAC to prevent someone from changing the message to a related one without the private key, e.g. change an encrypted "Transfer \$1000 from Alice to Carol: password 8Rjn9f-x" into "Transfer $1000 from Alice to Jacob: password 8Rjn9f-x" $\endgroup$
    – poncho
    May 14, 2018 at 17:47
  • 2
    $\begingroup$ @HelinWang: yes, the middle man would use his partial knowledge of the plaintext structure. Remember, an ECIES ciphertext consists of point and a symmetric encrypted message; we'll leave the point alone and modify the symmetric message. Many encrypting (but not authenticating) modes allow an attacker to modify the ciphertext, and make predictable changes to the resulting plaintext; the standard example is CTR mode, where flipping a bit in the ciphertext will flip the corresponding bit in the plaintext. Because ECIES includes a MAC, any such ciphertext modification is detected $\endgroup$
    – poncho
    May 16, 2018 at 12:40

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.