1
$\begingroup$

I'm wondering if a binary elliptic curve (such as sect571r1 aka B-571) supports pairs of asymmetric operations (for example, either sign/verify or encrypt/decrypt) on a fixed bit or byte input size in a way that this operation becomes fully bijective on those bytes/bits (where the inverse operation requires the opposite key).

If the alignment of such an operation doesn't fall on a byte (8-bit) boundary (but instead falls on just a bit boundary) then this is an alternate route to finding something similar in spirit, since it would then be possible to perform two, four, or eight similar operations until the extra bits are consolidated in a series of aggregate operations. This is workable, but something like a prime field I believe cannot support bijective operation on bits.

This question is also asking for some clarification on the operations of elliptic curves for these pairs of operations (like sign/verify or encrypt/decrypt) that's not the typical Diffie-Hellman key agreement (though maybe there's a simple way to relate that to encrypt/decrypt). Basically, suppose I have an input of "n" bytes, and some key pair (public, private). I'm wondering if it's possible to encrypt that arbitrary input with a public key, and then subsequently decrypt with the private key to fully recover the original "n" bytes - without any additional encoding or exceptional cases/constraints needed on the input/output.

The relative cryptographic strength of binary curves versus prime curves isn't part of the question. Although the other aspect I'm wondering about is the most straightforward, succinct, and self-contained example in code that performs these primitive operations without unnecessary elements like padding, wrapping, hashing, and so on. It can be assumed I can find an appropriate fixed size input to match the binary elliptic curve. And then, I presume if the encrypt-then-decrypt with the respective public-then-private key is doable, then so would sign-then-verify with the private-then-public key (similar to RSA).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Mapping from a scalar (a positive integer less than the order of the group generated by the curve base point) to a group element (EC point) is a bijection. However, it's also computationally one-way.

The RSA mapping is a trapdoor function where secret knowledge can invert the mapping. In EC, there is no trap door that allows secret knowledge to invert the mapping to get back from a group element to a scalar.

You therefore need to use a scheme such as ECIES or El Gamal for asymmetric encryption/decryption, and a scheme such as ECDSA or Schnorr for asymmetric signatures.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes. Subtitle for the OP: when it comes to cryptography relying on the hardness of the Discrete Logarithm Problem in some group and related problems, it's not built a bijective asymmetric operation (aka trapdoor permutation) as done in RSA. But we can still make asymmetric encryption, and signature. That holds all the same when said group is an Elliptic Curve on a binary field as in the question, an Elliptic Curve on a prime field as is more common practice, a Schnorr group as used in e.g. DSA, or some other (sub)group modulo a prime. $\endgroup$
    – fgrieu ♦
    Commented Sep 29, 2022 at 4:39
  • $\begingroup$ Thanks for the explanations. I'd wonder, then, if there is any known asymmetric cryptosystem that has the property of being able to biject its encrypt/decrypt operations on bytes (that is, no additional padding needed given the input is of the right size). I don't know if finding field inverse elements or square root is a potential foundation. I'm wondering what the encoding of an EC point (group element) looks like that can't be easily turned into a series of bits. Suppose some transformation from scalar to group is computationally hard to invert. Is it possible to assume it's been done? $\endgroup$
    – user3325588
    Commented Sep 29, 2022 at 16:20
  • $\begingroup$ @user3325588 "I'm wondering what the encoding of an EC point looks like" <- it looks like a coordinate pair in a finite field, which can be represented in 'compressed' form as a single coordinate encoded as a little-endian integer with a sign encoded into an unused high-order bit in the byte sequence. I don't know what you mean by "Is it possible to assume it's been done?". EC would be broken if the one-way function was invertible, and no one would use it any more. Try reading about the why padding was introduced into RSA, and you might find that your use case works with textbook RSA. $\endgroup$
    – knaccc
    Commented Sep 29, 2022 at 17:06
  • $\begingroup$ Thanks. The description of the encoding clarifies; I wanted to get an intuitive sense for why it may not be easily invertible. While it's a small footnote here (and could be its own question) I'm wondering if any other (non-EC) asymmetric scheme might meet this "fully bijective on bits" property. I don't see how RSA could exactly fit the bitwise part. But maybe a non-mainstream approach based upon a trapdoor function / lattice based / functional encryption / multilinear map. Just brainstorming there, though anything that expanded the size would be ineligible due to the bijective constraint. $\endgroup$
    – user3325588
    Commented Oct 3, 2022 at 2:38
  • $\begingroup$ @user3325588 With textbook RSA, you start with a byte sequence $m$, and treat it as an integer and raise it to the power $e$, and then you can decrypt by raising that to the power $d$. This will return you back to your original byte sequence. $\endgroup$
    – knaccc
    Commented Oct 3, 2022 at 3:46

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.