brainpoolP256r1

brainpoolP256r1, from RFC 5639

brainpoolP256r1 handles points and ECDSA verification for OpenPGP keys and certificates. RFC 9580 lists it for ECDSA and ECDH. RFC 7027 brings Brainpool curves to TLS. The twisted brainpoolP256t1 isn't in this package.

RFC 5639 defines the curve in section 3.4. Its equation is y² = x³ + ax + b. The field uses a 256-bit prime. The cofactor is 1.

Brainpool's a is neither 0 nor -3. That makes it different from secp256k1 and P-256. Here's a in hex:

7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9

import { isOnCurve, multiplyGenerator } from "@agntn/curves/brainpoolp256r1";

multiplyGenerator(1n); // "038bd2aeb9cb7e57…9ace3262"
isOnCurve(`02${"0".repeat(64)}`); // false
isOnCurve("036b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"); // true, P-256's compressed G

Coordinates and scalars take 32 bytes, or 64 hex digits. Compressed points take 33 bytes. Uncompressed points take 65. P-256 uses those same lengths. A length check won't tell you which curve a key belongs to.

Verify a brainpoolP256r1 ECDSA signature

Have a signature and its public key? Hash the message first. Then pass the digest, signature and key to verify.

import { verify } from "@agntn/curves/brainpoolp256r1";

const publicKey =
  "04019a2d9637743a63ddaefdbca0ee229a163b809b9b145e5313bbeb8defeab9d6" +
  "548caf89bf5ba49499404145651234336401b9b2843a579ed152e090f11b9e59";
const digest =
  "bb5a52f42f9c9261ed4361f59422a1e30036e7c32b270c8807a419feca605023"; // SHA-256 of 313233343030
const signature =
  "0a5f8c70ba2d0842d5d0f841f160ad15195769a8159bfe692634d73d469d111f" +
  "426e857aad3ff7aa96e4d200c03b45f1846a36d089ee3917768ca1a0d6d4da6e";

verify(signature, { digest, publicKey }); // true
verify(signature, { digest: `00${digest.slice(2)}`, publicKey }); // false

This is Wycheproof's SHA-256 vector tcId 1. The message is six bytes: 313233343030 in hex, or 123400 in ASCII. The second call replaces the digest's first byte. It doesn't prepend a byte.

The signature is r followed by s. It takes 64 bytes, or 128 hex digits. The public key is compressed or uncompressed SEC1 hex.

What about DER and the digest?

X.509 uses DER signatures. OpenPGP uses two MPIs. Extract r and s, then pad each to 64 hex digits. Join them without 0x.

The digest takes 1 to 64 bytes of hex without 0x. The order n has 256 bits. For longer digests, only the leftmost 256 bits count. The library doesn't hash the message for you.

What does it refuse?

verify("00", { digest, publicKey })               // Signature must be 128 hex digits without 0x, r then s
verify(signature, { digest: "0x00", publicKey })  // Digest must be hex without 0x, 1 to 64 bytes
verify(signature, { digest, publicKey: p256G })   // Invalid SEC1 brainpoolP256r1 public key
liftX("0".repeat(64))                             // No point of brainpoolP256r1 has this x

Here p256G is P-256's uncompressed generator. Wrong shapes throw. So do points that don't lie on this curve.

An r or s outside 1 to n - 1 returns false. The lowS option defaults to false. Set it to true to reject s above n / 2.

CLI and agent tool

Want the same check from a terminal? Use curves brainpoolp256r1 <operation>.

curves brainpoolp256r1 verify --point 04019a2d9637743a63ddaefdbca0ee229a163b809b9b145e5313bbeb8defeab9d6548caf89bf5ba49499404145651234336401b9b2843a579ed152e090f11b9e59 --digest bb5a52f42f9c9261ed4361f59422a1e30036e7c32b270c8807a419feca605023 --signature 0a5f8c70ba2d0842d5d0f841f160ad15195769a8159bfe692634d73d469d111f426e857aad3ff7aa96e4d200c03b45f1846a36d089ee3917768ca1a0d6d4da6e

It prints:

{"operation":"verify","valid":true}

The CLI offers add, subtract, negate, multiply, lift, check and verify. The agent tool curves_brainpoolp256r1_compute offers the same operations. Its arguments are point, other, scalar, x, digest, signature, lowS and compressed.

brainpoolP256r1 point math

The @agntn/curves/brainpoolp256r1 entry exports:

• addPoints, subtractPoints and negatePoint
• multiplyPoint and multiplyGenerator
• liftX, isOnCurve and convertPoint
• verify, brainpoolP256r1 and INVALID_POINT

The names match P-256 except for the domain export. brainpoolP256r1 holds the domain parameters. Give liftX an x as 64 hex digits. Scalars run from 1 to n - 1. Use a bigint or hex with at most 64 digits.

Try x = 0 and x = 1. Zero has no point here because b isn't a square modulo p. One does have a point.

Why did P-256's compressed generator pass isOnCurve above? A compressed point contains x and a choice of y. About half of all x values have a point on any curve. That x happens to work here too. Its uncompressed P-256 point fails because its y doesn't match.

Know the key's curve before checking it. A passing point check isn't a curve label.

There's no signing, key recovery or scalar math here. Like P-256, this entry verifies signatures.

Written from the specs

RFC 5639 objected to older curves' seeds being "chosen ad hoc". It also noted primes with special forms that make implementation efficient. Brainpool instead generated its parameters pseudo-randomly, in a systematic and reproducible way. The prime isn't a shortcut. Neither is a.

The curve shares src/core/sec1.ts with six others: secp256k1, P-256, P-384, P-521, brainpoolP384r1 and brainpoolP512r1. Seven curves, one implementation. The odd a was the real work.

The a = 0 and a = -3 formulas refuse this curve. They report These formulas are for another a. Addition and doubling instead use algorithms 1 and 3 from Renes, Costello and Batina (2016). These complete formulas work for any a. They cost a few more multiplications.

On P-256, the general formulas moved point multiplication by a few percent in a local run. Both versions took about 1.1 ms. The special formulas stay where they fit. That's a sensible trade.

Both n and p have 256 bits. Since p is 3 mod 4, a square root takes one power. Multiplication walks 64 hex digits. The secret multiplication comb has four rows, 16 steps apart. The verification table has 64 rows of 15 points.

A secret multiply takes the same steps for every scalar. test/brainpoolp256r1.test.ts times 1 against n - 1. JavaScript bigints don't promise constant timing. The library is unaudited. Keep real money away.

In a local run, G multiplication took about 0.46 ms. Another point took about 1.2 ms. Verification took about 1.3 ms. The generic code for curves you define took about 7.5 ms for one multiplication.

All 261 Wycheproof SHA-256 vectors pass in P1363 form. That's 175 valid and 86 invalid signatures. RFC 7027 appendix A.1 supplies two key pairs and their shared secret. Both match.

@noble/curves has no Brainpool. Multiples of G are frozen from OpenSSL 3.6.5 through node:crypto. In a local run, OpenSSL agreed on 199 keys. The library also verified 20 signatures made by OpenSSL.