521 bit ECC uses key sizes 7.5 times smaller than the RSA standard while offering encryption that is magnitudes more secure. An RSA 2048-bit key's secure enough for banking, but a 521-bit ECC key is the equivalent of a 15,360-bit RSA key.

I read it on SKYECC - Explaining 521-bit ECC Encryption From the Ground Up. Can anyone give me an independent answer and opinion on the claims made here This messaging apps claims to be the most secure

Is there a really much difference between 128bits 256bit and 512bits as it comes to security implemented in messaging apps or is t more important the way it has been implemented?

  • 1
    $\begingroup$ Does this answer your question? Key sizes for discrete logarithm based methods Although the algorithms are different, the attacks're pretty much the same. $\endgroup$
    – DannyNiu
    Apr 14 '20 at 1:01
  • 1
    $\begingroup$ @DannyNiu actually that Q&A seems to be about Finite-Field discrete-log which scales the same as RSA. $\endgroup$
    – SEJPM
    Apr 14 '20 at 9:39
  • $\begingroup$ "Can anyone give me an independent answer and opinion" my opinion is that 521-bit ECC implies use of the P-521 NIST curve, and therefore cannot be the most secure. Also their security description does not inspire confidence $\endgroup$ Apr 14 '20 at 11:39

When it comes to asymmetric cryptosystems like RSA and ECC, security in bits is not the figure quoted in bits for key size (which itself has no universal relationship with the number of bits in the actual form taken by either the public or private key, which I won't further discuss in this answer).

Oversimplifying, and sticking to attacks using classical computers (because quantum computers usable for cryptanalysis are only an uncertain possibility for a remote future)

  • $n$-bit security means that $2^n$ operations of some kind are believed needed on a classical computer to attack the system from ciphertext or other intercepted data. 96-bit security seems practically secure today (even 80-bit was never broken in a public attack), and each additional bit doubles the difficulty, making 128-bit safe for perhaps one or more decades, depending on one's wilderness of imagination. Anything above is for long-term security, or as a margin for attacks not envisioned in evaluation of the security level.
  • With ECC, $n$-bit security requires a curve on a finite field which elements need at least about $2n$ bits for their representation, and that $2n$-bit field size is usually what's quoted as size or key size. Thus 256-bit ECC gives at most about 128-bit security, 521-bit ECC gives at most about 260-bit security, rounded to 256-bit because that's a common symmetric key size.
  • With RSA, the public modulus size as found in (or derivable from) the public key is what's quoted as size, or key size (like, 2048-bit or 15360-bit). Its relationship to security level is more complex than in ECC. NIST SP 800-57 Pt 1 gives these very rough figures, which indeed tell (bottom line, leftmost and two rightmost columns) that 256-bit security is roughly obtained for 15360-bit RSA or 521-bit ECC.

    NIST comparable strengths table

Is there a really much difference between 128bits 256bit and 512bits as it comes to security implemented in messaging apps or is t more important the way it has been implemented?

For data becoming of no value after less than a decade, there is not really much difference between 128-bit security and higher grades (but in the unlikely case that in the above "128bit" was an ECC field size, or if any of "128bits 256bit and 512bits" was an RSA modulus size, these numbers would be too low for decent security).

For key sizes giving decent security level (with the limit perhaps somewhere between 72 to 112-bit security these days depending on a variety of factors), what matters most to security of a messaging apps is who can get at the keys and ancillary data (like, most importantly, who communicates with who), what's done with the crypto, and the quality of the implementation.

  • $\begingroup$ I would like to add that, with the proof of the generic group's models, if there is no special property of the group then we don't have better algorithms other than the generic discrete log algorithm. $\endgroup$
    – kelalaka
    Apr 14 '20 at 14:43

521-bit ECC keys are the same strength as RSA 15,360-bit keys

Yes, this is the common wisdom. If you look through the tables at keylength.com you will find that a rough 256-bit security level is usually equated to 512-bit or longer ECC keys and 15360-bit RSA keys.

If you are more interested in the why of this I recommend you read the original work by Lenstra and Verheul on estimating key lengths (PDF) or Lenstra's simplified follow-up (PDF).

However the basic idea is that we know a sub-exponential runtime algorithm for RSA (the GNFS) and for ECC we only know exponential runtime algorithms (the best being Pollard-Rho). That is we need $2^{n/2}$ operations to break an ECC key but much less to factor an RSA key.

You may want to note though (as pointed out by fgrieu in the comments), that if a major breakthrough would happen and we would get a non-generic algorithm for elliptic curves chances are RSA would survive that. There's even some calculations that say that small-size ECC keys are (a bit) easier to break than large-size RSA keys using quantum computers.

  • 1
    $\begingroup$ Maybe it should be pointed that as long as Pollard's rho on classical computers remains about the best attack against ECC as used today, then 521-bit ECC is terribly overkill. But if it stops to be (e.g. because of a math break-thru, or quantum computers usable for cryptoanalysis materialize, which in the very long run is not pipedream), that might change. Assuming that, it is arguable that 15360-bit RSA stands a chance to remain safe at a time when 521-bit ECC would no longer be. $\endgroup$
    – fgrieu
    Apr 14 '20 at 10:15
  • 1
    $\begingroup$ That's true assuming no new progress in integer factorization. But there's been a lot more recent progress there than in solving discrete log or even arguably on quantum computing. $\endgroup$ Apr 14 '20 at 12:47

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.