2
$\begingroup$

openssl speed tests the speed of different protocols on your computer:

$ openssl speed something
Error: bad option or value

Available values:
...
ecdsap160 ecdsap192 ecdsap224 ecdsap256 ecdsap384 ecdsap521
ecdsak163 ecdsak233 ecdsak283 ecdsak409 ecdsak571
ecdsab163 ecdsab233 ecdsab283 ecdsab409 ecdsab571
...

For the ECDSA options, there are the above list of available ciphers (likely this list is different on different PC's).

What is ecdsap vs ecdsak vs ecdsab? What do the letters P, K, and B mean at the end of the ECDSA algorithm?

$\endgroup$
  • 2
    $\begingroup$ immediate guess: prime, koblitz and binary curves. $\endgroup$ – SEJPM Jun 11 '18 at 20:31
  • 1
    $\begingroup$ This list is the same for releases of OpenSSL 1.0.0 through 1.1.0 (and presumably soon 1.1.1). There are only two reasons I know it is likely to vary: RedHat packages (and therefore CentOS and Fedora, and likely other derivatives like Oracle and Scientific) have only P256, P384 and P521; or if you have and use the FIPS option, the FIPS container may have been built to include only prime curves not 'binary' (GF(2^m)) ones. $\endgroup$ – dave_thompson_085 Jun 12 '18 at 6:55
4
$\begingroup$

First: If you're looking for a signature scheme, forget all of those; I recommend Ed25519. It too uses elliptic curves, it's standardized in RFC 8032, and there are implementations widely available. It's safer and faster and simpler than any of the signature schemes you listed: ECDSA is an archaic design, and most or all of the curves mentioned there fail to satisfy modern security criteria for curves.

With that caveat in mind, to answer the question you asked:

  • The nomenclature $\mathrm{ecdsa}tn$, for a type $t \in \{\mathrm p, \mathrm k, \mathrm b\}$ and number $n$, mostly corresponds to ECDSA over the NIST Curve $t{\operatorname-}n$ defined in FIPS 186-4, over a field of about $2^n$ elements. For example, ecdsap256 uses NIST Curve P-256, or just NIST P-256 for short. Prior to FIPS 186-4, the curves also appeared in SECG standards. One of the curves, secp160r1 as used by ecdsap160, does not appear in FIPS 186-4, presumably because it provides too little security.

    (The methods allegedly used to choose the curves are prescribed in ANSI X9.62, and some of the curves also appear in it, and possibly also in IEEE P1363, but what self-respecting anarchist cypherpunk has the cash to shell out for a copy of a bureaucratic standard like that?)

  • The field size $2^n$ means that the highest expected cost for Pollard's $\rho$ to compute discrete logarithms that you, the defender, can hope for is approximately $\sqrt{2^n\pi/4} \approx 2^{n/2}$; for more on prime, field size, curve shape, and curve order, see an answer to an earlier question, and for more on other security criteria, see SafeCurves.

  • The letters p, k, and b represent different types of curves with different properties. I include the full gory details for the sake of curiosity, not because you should be discriminating on these criteria—as before, ideally, you would just use Ed25519, which uses a curve, edwards25519, not in this list at all.

The p curves are curves over prime fields $\mathbb Z/p\mathbb Z$ with allegedly* randomly generated parameters. They all have the short Weierstrass form $y^2 = x^3 - 3x + b$ for a coefficient $b$ chosen from an unexplained seed.

Using a prime field rather than an extension field, particularly a binary extension field, is the most conservative choice for an elliptic curve. The most widely used one is probably NIST P-256, also known as secp256r1.

In addition to being defined on a prime field, all of these curves have prime order, meaning the number of elements on the curve (with coordinates in the field and not an extension) is prime. Thus all of these curves fail SafeCurves because they cannot admit the Montgomery ladder for fast constant-time scalar multiplication, or complete Edwards formulas for fast constant-time arithmetic, which require a cofactor of at least 4; and they are not rigid. Some of them additionally fail SafeCurves for other reasons.

  • ecdsap160: secp160r1, defined in [1], §2.4.2, p. 10, over the prime field of characteristic $p = 2^{160} - 2^{31} - 1$ by $y^2 = x^3 - 3 x + b$, where $b$ is 1C97BEFC 54BD7A8B 65ACF89F 81D4D4AD C565FA45, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 1053CDE4 2C14D696 E6768756 1517533B F3F83345.

    The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{80}$ curve additions, which is a plausible cost today, so it is not endorsed by NIST and it falls far short of the SafeCurves requirement of $2^{100}$ cost for Pollard's $\rho$.

  • ecdsap192: secp192r1, a.k.a. NIST P-192, defined in [2], §2.2.2, p. 6 and [3], §D.1.2.1, p. 90, over the prime field of characteristic $p = 2^{192} - 2^{64} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 64210519 E59C80E7 0FA7E9AB 72243049 FEB8DEEC C146B9B1, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 3045AE6F C8422F64 ED579528 D38120EA E12196D5.

    The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{96}$ curve additions, and while it is endorsed by NIST, it falls short of the slightly higher standard imposed by SafeCurves.

  • ecdsap224: secp224r1, a.k.a. NIST P-224, defined in [2], §2.3.2, p. 8 and [3], §D.1.2.1, p. 90, over the prime field of characteristic $p = 2^{224} - 2^{96} + 1$ by $y^2 = x^2 - 3x + b$ where $b$ is B4050A85 0C04B3AB F5413256 5044B0B7 D7BFD8BA 270B3943 2355FFB4, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5.

    The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{112}$ curve additions. It fails SafeCurves additionally because its twist has composite order with no particularly large prime factors, enabling a variant of Lim–Lee small-subgroup attacks, and therefore requiring the additional complexity of point validation in protocols using it.

  • ecdsap256: secp256r1, a.k.a. NIST P-256, defined in [2], §2.4.2, p. 9 and [3], §D.1.2.3, p. 91, over the prime field of characteristic $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed C49D3608 86E70493 6A6678E1 139D26B7 819F7E90.

    The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{128}$ curve additions.

  • ecdsap384: secp384r1, a.k.a. NIST P-384, defined in [2], §2.5.1, p. 10 and [3], §D.1.2.4, p. 91, over the prime field of characteristic $p = 2^{384} - 2^{128} - 2^{96} - 2^{32} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is B3312FA7 E23EE7E4 988E056B E3F82D19 181D9C6E FE814112 0314088F 5013875A C656398D 8A2ED19D 2A85C8ED D3EC2AEF, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed A335926A A319A27A 1D00896A 6773A482 7ACDAC73.

    The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{192}$ curve additions.

  • ecdsap521: secp521r1, a.k.a. NIST P-521, defined in [2], §2.6.1, p. 11 and [3], §D.1.2.5, p. 92, over the prime field of characteristic $p = 2^{521} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 0051 953EB961 8E1C9A1F 929A21A0 B68540EE A2DA725B 99B315F3 B8B48991 8EF109E1 56193951 EC7E937B 1652C0BD 3BB1BF07 3573DF88 3D2C34F1 EF451FD4 6B503F00, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed D09E8800 291CB853 96CC6717 393284AA A0DA64BA.

    The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{259}$ curve additions. It is not assessed by SafeCurves, presumably because there is a much better curve E-521 over the Mersenne prime $2^{521} - 1$, but it turns out to pass all the same criteria as NIST P-256 and NIST P-384 at a somewhat higher security level: embedding degree $(\ell - 1)/4$; CM discriminant ${>}2^{100}$; not rigid (manipulable but not trivially so); no Montgomery ladder; twist embedding degree $(\ell' - 1)/6$, twist cofactor $5\cdot7\cdot69697531\cdot635884237 = 1551184646225159645$, prime twist subgroup order $\ell' \approx 2^{460.57}$; no Edwards addition law.

The k curves are curves over binary extension fields $\operatorname{GF}(2^m)$ with a special property, called Koblitz curves. Specifically, each exponent $m$ of the field size is prime, and each curve has the Weierstrass form $y^2 + xy = x^3 + ax^2 + b$ where $a, b \in \{0,1\}$, chosen so that the Frobenius map $\varphi\colon (x, y) \mapsto (x^{2^m}, y^{2^m})$ (which can be efficiently computed by bit-shifting) has trace 1, which has the consequence that $[2^m]P = \varphi(P) - \varphi^2(P)$, making the evaluation of scalar multiplication particularly cheap, as noted by Koblitz in 1992 after whom the class of curves is named.

The security of binary elliptic curves against discrete logarithms is not as well-understood (see in particular §10.2, ‘A subexponential algorithm for elliptic curves over $\mathbb F_{2^n}$?’, p. 18), so all of these curves fail SafeCurves.

The class of curves named Koblitz curves is sometimes considered to include any curve with an efficient endomorphism to speed up computations as proposed by Gallant, Lambert, and Vanstone in 2001, not just binary curves. secp256k1, used by Bitcoin, is an example of a prime Koblitz curve. These endomorphisms make some people nervous but are not known to destroy security.

The b curves are curves over binary extension fields $\operatorname{GF}(2^m)$ with allegedly randomly generated parameters. They all have Weierstrass form $y^2 + xy = x^3 + x^2 + b$ for a coefficient $b$ chosen from an unexplained seed.

Unlike the binary Koblitz curves, the allegedly-random binary curves have neither a rigid form, nor special structure admitting efficient implementation. Like the binary Koblitz curves, they are binary, and so their security is poorly understood.

  • ecdsab163: sect163r2, a.k.a. NIST B-163, defined in [2], §3.2.3, p. 18 and [3], §D.1.3.1.2, p. 94, over the binary field $\operatorname{GF}(2^{163})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 02 0A601907 B8C953CA 1481EB10 512F7874 4A3205FD, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 85E25BFE 5C86226C DB12016F 7553F9D0 E693A268.

    There is also a similar curve sect163r1, generated by a variant of the ANSI X9.62 Annex A.3.3 procedure.

  • ecdsab233: sect233r1, a.k.a. NIST B-233, defined in [2], §3.3.2, p. 19 and [3], §D.1.3.2.2, p. 95, over the binary field $\operatorname{GF}(2^{233})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 0066 647EDE6C 332C7F8C 0923BB58 213B333B 20E9CE42 81FE115F 7D8F90AD, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 74D59FF0 7F6B413D 0EA14B34 4B20A2DB 049B50C3.

  • ecdsab283: sect283r1, a.k.a. NIST B-283, defined in [2], §3.5.2, p. 22 and [3], §D.1.3.3.2, p. 97, over the binary field $\operatorname{GF}(2^{283})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 027B680A C8B8596D A5A4AF8A 19A0303F CA97FD76 45309FA2 A581485A F6263E31 3B79A2F5, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 77E2B073 70EB0F83 2A6DD5B6 2DFC88CD 06BB84BE.

  • ecdsab409: sect409r1, a.k.a. NIST B-409, defined in [2], §3.6.2, p. 24 and [3], §D.1.3.4.2, p. 98, over the binary field $\operatorname{GF}(2^{409})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 0021A5C2 C8EE9FEB 5C4B9A75 3B7B476B 7FD6422E F1F3DD67 4761FA99 D6AC27C8 A9A197B2 72822F6C D57A55AA 4F50AE31 7B13545F, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 4099B5A4 57F9D69F 79213D09 4C4BCD4D 4262210B.

  • ecdsab571: sect571r1, a.k.a. NIST B-571, defined in [2], §3.7.2, p. 26 and [3], §D.1.3.5.2, p. 100, over the binary field $\operatorname{GF}(2^{571})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 02F40E7E 2221F295 DE297117 B7F3D62F 5C6A97FF CB8CEFF1 CD6BA8CE 4A9A18AD 84FFABBD 8EFA5933 2BE7AD67 56A66E29 4AFD185A 78FF12AA 520E4DE7 39BACA0C 7FFEFF7F 2955727A, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 2AA058F7 3A0E33AB 486B0F61 0410C53A 7F132310.

References:

  1. Recommended Elliptic Curve Domain Parameters, Standards for Efficient Cryptography: SEC 2, Certicom Research, version 1.0, 2001-09-20.
  2. Recommended Elliptic Curve Domain Parameters, Standards for Efficient Cryptography: SEC 2, Certicom Research, version 2.0, 2010-01-27.
  3. Digital Signature Standard (DSS). Federal Information Processing Standards: FIPS PUB 186-4, United States National Institute of Standards and Technology, July 2013.
  4. Neil Koblitz, ‘CM-Curves with Good Cryptographic Properties’, in Joan Feigenbaum, ed., Proceedings of Advances in Cryptology—CRYPTO 1991, Springer LNCS 576, 1991, pp. 279–287.
  5. C.H. Lim and P.J. Lee, ‘A key recovery attack on discrete log-based schemes using a prime order subgroup’, in Burton S. Kaliski, Jr., ed., Proceedings of Advances in Cryptology—CRYPTO 1997, Springer LNCS 1294, 1997, pp. 249–263.
  6. Stephen D. Galbraith and Pierrick Gaudry, ‘Recent progress on the elliptic curve discrete logarithm problem’, IACR Cryptology ePrint Archive: Report 2015/1022, 2015-10-22.
  7. Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, ‘Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms’, in Joe Kilian, ed., Proceedings of Advances in Cryptology—CRYPTO 2001, Springer LNCS 2139, pp. 190–200.

* I have not verified that they followed the ANSI X9.62 Annex A.3.3 procedure. See also the bada55 curves and the SafeCurves commentary on rigidity.
N.B.: This is not evidence of a back door. (In contrast, Dual_EC_DRBG was clearly designed to have a back door that cryptographers rapidly recognized—the back door was even patented under the not-very-subtle euphemism of ‘key escrow’.) This is only evidence that the authors didn't think hard about inspiring confidence that there is no back door.

For comparison, the Bitcoin network today computes over $2^{80}$ SHA-256 evaluations in a day.

$\endgroup$
  • $\begingroup$ In short, except for p160r1, and in 1.1.0 (and soon 1.1.1?) the addition of an item mislabelled 'ecdsa X25519' which is really Ed25519, these are exactly the curves adopted by FIPS186-2 up with trivially modified names. The output of speed uses a slightly different form that emphasizes this further: $n bit ecdsa ($name) where name is secp160r1 or nist{p,k,b}$n. Also, bitcoin is now roughly 2^89 trials per day where each trial is 1.5 x SHA256 or more exactly the second block of a two-block SHA256 plus (the only block of) a one-block SHA256. $\endgroup$ – dave_thompson_085 Jun 12 '18 at 6:37
  • $\begingroup$ @dave_thompson_085 blockchain.info/charts/hash-rate reports approximately 35e18 H/s. Multiply by 86400 to get H/day, and $\log_2 (86400\cdot35\cdot10^{18}) \approx 81$. How do you get $2^{89}$? $\endgroup$ – Squeamish Ossifrage Jun 12 '18 at 6:53
  • $\begingroup$ Sorry, I was in a rush and used s/year instead of s/day. You're right. $\endgroup$ – dave_thompson_085 Jun 14 '18 at 0:50

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.