3
$\begingroup$

First of all, excuse me if this question is too noobish.

I'm trying to understand how these things are relate: Curve type, its 'number of bits of security', size of the key and the maximum ciphertext size.

Comparing to RSA, I know, that size of the key directly affects the maximum size of ciphertext: it can never exceed the key size and in practice is even smaller than that.

Is this still holds for ECC?

If so, what's the limitations on the size of the key in terms of a specific Curve? Is it even possible to allocate keys of different sizes? Or, given that math is discrete, does each curve has a hard ceiling for a key size?

If on the other hand, the key size is unlimited, is it true that no matter how large it is, the effective hardness of encryption will never exceed the 'number of bits of security' of specific Curve? If so, does increase the key size only gives you a larger limit on the ciphertext size?

$\endgroup$
6
  • 2
    $\begingroup$ While RSA actually does encryption, ECC (assuming you mean ECDH) is used for pure key agreement where a shared secret is mutually generated upon as a result of the operation. ECDH doesn't actually encrypt anything. With that in mind, are you asking about the size of the shared secret derived from key agreement with ECDH? $\endgroup$
    – forest
    Feb 23, 2019 at 10:30
  • $\begingroup$ @forest, See, I thought the question was noobish. Yes, let's assume the shared secret is a ciphertext. Because, if I understand it correctly, technically shared secret is kind of encrypted (hidden from the thing party). $\endgroup$
    – GreenScape
    Feb 23, 2019 at 10:44
  • 1
    $\begingroup$ It's a fine question. Better than the ones asking how to decode some homemade cipher! Technically though, the shared secret agreement is not encryption, although it is a cryptographic operation. I believe the shared secret is the same size as the curve, so P-256 results in a 256-bit shared secret. Public key cryptography is not my forte, so I'm still looking it up. That doesn't mean that the secret has 256 bits of entropy, though! $\endgroup$
    – forest
    Feb 23, 2019 at 10:49
  • 2
    $\begingroup$ @GreenScape with minor exceptions, an ECC curve designed for an N bits field will have a key of N bits, and usually has a security equivalent to an N/2 bit symmetric key, and in ECDH (key exchange) it produces N bits of session key, and depending on signature scheme it might produce N*2 signature bits (two-part) $\endgroup$
    – Natanael
    Feb 23, 2019 at 10:54
  • 1
    $\begingroup$ Note that the shared secret, in the form of output coordinates on the curve, is rarely used directly. It is typically fed through a KDF (e.g. HKDF) to derive symmetric keys of the desired size. $\endgroup$
    – forest
    Feb 23, 2019 at 10:56

2 Answers 2

2
$\begingroup$

The standard way to do public-key encryption with elliptic curves has no limit on ciphertexts. It works roughly as follows, with many details omitted for practical instances:

Parameters.

  • Fix an elliptic curve $E/\mathbb F_p$ over a finite field $\mathbb F_p$, e.g. $p = 2^{255} - 19$ and $E\colon y^2 = x^3 + 486662 x^2 + x$ (Curve25519).
  • Fix a standard base point $G \in E(\mathbb F_p)$ of large prime order $\ell$, e.g. $G = (9, \dots)$.
  • Fix a hash function $H\colon \mathbb E(\mathbb F_p) \to \mathbb \{0,1\}^{256}$, e.g. SHA-256 on the little-endian encoding of the coordinates.
  • Fix an authenticated (symmetric) cipher $E_k$, e.g. NaCl crypto_secretbox_xsalsa20poly1305.

Public keys. A public key is the encoding of a point $P$ on the curve with coordinates in $\mathbb F_p$.

Encryption. To encrypt a message $m$: Pick an integer $b$ with $0 \leq b < \ell$ uniformly at random. Compute $k = H([b]P)$, the encapsulated symmetric key. Compute $c = E_k(m)$, the authenticated ciphertext. Compute $Q = [b]G$, the encapsulation of the symmetric key. Transmit $Q$ and $c$.

Private keys. A private key is an integer $a$ with $0 \leq a < \ell$ chosen uniformly at random. The corresponding public key is $P = [a]G$.

Decryption. To decrypt a message given $Q$ and $c$, knowing the private key $a$: Compute $k = H([a]Q)$. Compute $m = E_k^{-1}(c)$, or drop it on the floor if authentication fails.

This structure is sometimes called ECIES, or sealed box. It works because $$H([a]Q) = H([a][b]G) = H([b][a]G) = H([b]P),$$ so the sender and receiver are guaranteed to use the same key $k$. The size of the message is limited only by the authenticated cipher $E_k$, and most authenticated ciphers have very large limits on message size, measured either in gigabytes or so big I don't even remember the word for it (what's more than a zettabyte?).

The field size $p$ and the group order $\ell$ are related by Hasse's theorem—they can't differ by more than approximately $\sqrt p$, so they are of the same order of magnitude. The security offered by the curve is at most about $\log_2 \sqrt \ell$ bits, e.g. for Curve25519 you get at most the gold standard ~128-bit security, because a generic attack costs approximately $\sqrt \ell$ curve operations. Of course, if you use AES-128, you won't get 128-bit security because it is much cheaper to attack multiple AES targets than to attack multiple Curve25519 targets.

The ciphertext expansion is only the constant overhead of the encoding of a curve point, and whatever ciphertext expansion $E_k$ has (typically a 128-bit authentication tag).

Some people call it ‘hybrid encryption’ when you combine a public-key operation like this with a symmetric-key cipher. This is a poor choice of terminology, because it suggests that the public-key operation without the symmetric-key is itself a form of public-key encryption. That is not the case here, or in any scheme similarly based on ephemeral/static key agreement, and that is generally a poor design with bad security and usage limitations even when it can technically be done with RSA.

The only way RSA is used in practice for encryption has the same separation, whether with RSA-KEM or with essentially any use of RSAES-PKCS1-v1_5 or RSAES-OAEP: encapsulate a uniform random symmetric key $k$ in an $e^{\mathit{th}}$ root modulo $n$, and encrypt the message with $E_k$. Unlike attempting to shoehorn the message $m$ into $m^e \bmod n$, this has no limits on the message size or on the structure or distribution of messages that can be concealed.

$\endgroup$
2
$\begingroup$

While RSA defines both a way to encrypt and to sign, ECC is a more general concept, and one can come up with multiple encryption and signature schemes. So if you want to talk about the maximum size of a ciphertext, your answer will depend on two things: (a) the curve used; (b) the encryption system used.

Let's have a look at (a). Your elliptic curve system crudely defines two mathematical sets: the scalar field (an integer field $\mathbb{F}_q$, typically $q$ is prime) and the group (the actual curve). Private keys are usually a single field element (so, of length $\log_2{q}$), while public keys are usually a single group element.

There are two well-known ways to "encrypt using ECC": ElGamal encryption and hybrid encryption.

Using ElGamal, your message needs to fit a scalar. This means that the curve defines the maximum plain text size, namely $\log_2{q}$, typically a bit below (almost literally) 256 bits.

Using hybrid encryption, you will not directly use ECC to encrypt. Rather, you use ECC to generate a key for a symmetric cryptosystem. There, the message can be (almost) arbitrary length. There's another advantage that makes (EC)IES the most popular way to use ECC for encryption: you don't take the penalty of slow asymmetric cryptography!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.