|
Title: Why does 256-bit ECC offers equivalent security of 128-bit symmetric encryption? Post by: BusyBeaverHP on March 31, 2015, 01:33:00 AM I've been studying ECDSA from Royal Fork (http://www.royalforkblog.com/2014/09/04/ecc/) for a few weeks now, and I think I'm starting to get it. Some question remains.
Why is it that 256-bits of ECC only offers equivalent security of say, 128-bit AES? Is it because of the birthday paradox? Or is it something else? Title: Re: Why does 256-bit ECC offers equivalent security of 128-bit symmetric encryption? Post by: hhanh00 on March 31, 2015, 01:53:04 AM It's because the best algo that solves the EC discrete log problem is in O(sqrt(N)).
Title: Re: Why does 256-bit ECC offers equivalent security of 128-bit symmetric encryption? Post by: DeathAndTaxes on March 31, 2015, 02:08:31 AM Everything is compared to symmetric encryption because baring a flaw in the algorithm there is no method to find a symmetric encryption key faster than O(n) steps. All other algorithms have solutions than can be found in less steps.
ECC is "secure" because the Elliptic Curve Discrete Logarithm Problem is infeasible for large sets however there are solutions to the ECDLP which are faster than O(n) but the fastest (such as pollard's rho (http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms)) is still O(n1/2). Since the solution can be found in faster than O(n) steps it requires a larger key for an equivalent level of security. Keep in mind that the ratio of relationship of O(n1/2) between key size and bit strength only applies to ECC and only because there no faster solution is currently known. This can change over time. The strength of a given RSA key has declined over time as faster solutions to the integer factorization problem have been found. Today to achieve '128 bit security' requires a 3,072 bit RSA key. |