Brainpool

Technical requirements

For each of the bit-lengths $160, 192, 224, 256, 320, 384, 512$ one curve shall be proposed.
The base field size $p$ should be congruent to $3 \mod 4$ .
The curve should be $\mathbb{F}_p$ -isomorphic to a curve with $A \equiv -3 \mod p$ .
The prime $p$ must not be of a special form in order to avoid patented fast arithmetic on the base field.
The order of the curve $\lvert \mathcal{E}(\mathbb{F}_p) \rvert$ should be smaller than the size of the base field $p$ .
The curve coefficient $B$ should be non-square in $\mathbb{F}_p$ .

Security requirements

The embedding degree $l = \min\{t \vert q \text{divides} p^t - 1 \}$ should be large, where $q$ is the order of the basepoint and $p$ the size of the base field. Specifically, $(q - 1) / l < 100$ .
The curves are not trace one curves. Specifically $\lvert \mathcal{E}(\mathbb{F}_p) \rvert \ne p$ .
The class number of the maximal order of the endomorphism ring of the curve is larger than $10000000$ .
The group order $\lvert \mathcal{E}(\mathbb{F}_p) \rvert$ should be a prime number $q$ .

Original method

Brainpool published their method of generating verifiably random curves in the ECC Brainpool Standard Curves and Curve Generation [1] document, along with generated domain parameters claimed to be generated using the presented method and seeds. However, the presented curves were (with the exception of the 512-bit curves) not generated using the presented method, as they have properties that can not result from the presented method of generating curves. See the BADA55 paper [3] for more information.

RFC 5639 method

Brainpool published an RFC with their fixed method of generating verifiably random curves and generated curves in RFC 5639 [2], which matches the generated curves and seeds.

Generating primes

Generating curves

References

Manfred Lochter: ECC Brainpool Standard Curves and Curve Generation v. 1.0, [archive]
Manfred Lochter, Johannes Merkle: Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation (RFC5639)
BADA55 Research Team: BADA55 Crypto - Brainpool curves