Public-private key cryptography is based on inverse operations that use separate input. In elliptic curve cryptography, what are those inverse operations?

  • $\begingroup$ Are you looking for examples of where the inverse of a number is required in one of the equations enabling traversing the elliptic curve? $\endgroup$ – JohnGalt Apr 3 '19 at 19:21
  • $\begingroup$ Depends on the specific algorithm. For example key exchange algorithms (ECDH) is really just a singular operation with no clear inverse operation. $\endgroup$ – Natanael Apr 3 '19 at 23:58
  • $\begingroup$ for signatures, in RSA e and d are inverse operations both for signing/verifying and/or encrypting/decrypting, I assume it is similar with ECC $\endgroup$ – phi Apr 4 '19 at 17:27
  • $\begingroup$ Elliptic Curve Crypto is not an algorithm, it is a set of algorithms that are based on the properties of (discrete) Elliptic Curves. And another nitpick: e and d are not operations, they are the exponents used in modular exponentiation (i.e. modular exponentiation with e is the inverse of modular exponentiation with d and vice versa). $\endgroup$ – Maarten Bodewes Apr 6 '19 at 0:03
  • $\begingroup$ if your represent d as how it has been derived, it is the inverse of e, why signature/verification works $\endgroup$ – phi Apr 6 '19 at 10:01

Public-private key cryptography is based on inverse operations that use separate input.

That is not always true, or at least, not a very useful way of thinking of it.

For public key encryption, there is a transform (based on the public key) that converts the message and some randomness into a ciphertext; there is a reverse transform (based on the private key) that converts that ciphertext back into the message. And so, in that sense, public key encryption can be viewed as based on an 'invertable' operation (or at least, a partially invertible one; there's no guarantee that the decryptor can recover the original randomness).

However, that doesn't mean that the 'hard problem' that the public key encryption is based on is a part of that invertibility; the obvious example is EC-El Gamal, where the encrypt a point $M$, you select a random value $r$, and publishes the two values $rG$ and $rH + M$ (where $H$ is the public key). To decrypt, you don't try to invert $rG$ to recover $r$; instead, you go forwards; you multiply the point $rG$ by the private key, which gives the value $rH$ (and then subtract that from $rH + M$ to recover the message $M$).

It turns out that ECC is always like that; it's always a hard problem to recover $r$ from $rG$, and so we never insist on trying; instead, we rely on the group properties to make the cryptosystem work.

When we look at signatures, it's even more obvious; there is no guarantee that we can recover even the hash of the message from the signature. While ECC signatures (such as ECDSA and EdDSA) do not allow such recovery, the most extreme example is hash based signatures, which are based on noninvertible functions, and have nothing that can be described as an 'inverse' operation.

| improve this answer | |
  • $\begingroup$ it is always true since it is how trap door functions are defined $\endgroup$ – phi Apr 7 '19 at 22:38
  • $\begingroup$ @phi: "it is always true"; is that specifically about public key encryption, or about all public key algorithms? If the latter, I would ask what is the inverse function within a hash based signature... $\endgroup$ – poncho Apr 7 '19 at 23:02

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.