Brainpool

In 2005, Manfred Lochter and Johannes Merkle proposed a new set of elliptic curves as part of the new standard ECC Brainpool Standard Curves and Curve Generation [1]. The authors claimed that existing elliptic curve standards have issues that have not been up to that point addressed, such as:

Seeds for verifiably pseudorandom parameters have been chosen ad hoc.
The base-field primes have special forms which contradict the approach of pseudorandom parameters and are at risk of violating patents on special prime arithmetic.

Hence the Brainpool group proposed a new method for the generation of so-called verifiably pseudorandom Weierstrass curves, including the generation of base-field primes of bit-lengths 160, 192, 224, 256, 320, 384, and 512. The document then recommends seven curves for each bit-length with the names brainpoolPXXXr1 where XXX stands for the bit-length (seven other curves are also specified with the names brainpoolPXXXt1, which are isomorphic curves satisfying $a=-3$).

Security

The security conditions for the elliptic curves were specified as follows:

The cofactor shall be 1, i.e. the group order $n$ shall be prime.
The embedding degree shall be greater than $(n-1)/100$.
The trace can't be 1. Technical requirements then state that $t>1$.
The class number should be larger than $10^7$.

Further technical requirements then state, apart from $t>1$, that the curve should be isomorphic over $\mathbb{F}_p$ to a curve with $a=-3$, the parameter $b$ can't be a square, and the base-field prime $p$ should be $3 \pmod 4$. See Algorithm 3 for the used generation method.

To be precise, in the original 2005 document, a slightly different algorithm was given. Step 4 of Algorithm 3 looped back to step 1 instead of step 4. This mistake had the consequence that the presented curves were not generated using this specified procedure. The complete description of this discovery is in [2]. The mistake was corrected in 2010 in the second version of the standard [3]. The first version, however, still contains useful information which is not included in the second one, including certain seed values and class number computation recommendations.

Algorithm 1 looks very similar to Algorithm 1 from the standard X9.62. Indeed, they differ only in the first step. Brainpool goes a bit further and uses this algorithm to generate both the parameter $a$, $b$, and the base-point. Between each of these, the seed is incremented, which ,together with the incremental character of Algorithm 1, has very strange consequences. For example, if we consider the brainpoolP256r1, we can see the identical segments in the parameters $a,b$.

p = 0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377

a =0x7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9

b = 0x26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6

Similar overlaps can be found in brainpoolP192r1, brainpoolP256r1, brainpoolP384r1 and brainpoolP512r1. This unusual behavior is not bound to happen for every elliptic curve generation, but it happens roughly half of the time. This corresponds with the fact that we can't find such overlaps in brainpoolP160r1, brainpoolP224r1, and brainpoolP320r1. To be more specific, after we generate parameter $a$, the seed is incremented, and the parameter $b$ is produced from this seed. If $b$ is square, which happens roughly half of the time, assuming uniformity of the outputs, then the seed is incremented, and we repeat the step. The visible overlaps are the cases when $b$ wasn't a square on the first try. If we assume that, for example, in the case of brainpoolP320r1, the parameter $b$ was generated on the second incrementation of the seed (with 75% probability), then we can actually reconstruct the discarded $b'$ without the original seed (the first byte of the corresponding segments are different because of step 4 in Algorithm 1):

a =0x3ee30b568fbab0f883ccebd46d3f3bb8a2a73513f5eb79da66190eb085ffa9f492f375a97d860eb4

b' = 0x75eb79da66190eb085ffa9f492f375a97d860eb4d20883949dfdbc42d3ad198640688a6fe13f4134

b = 0x520883949dfdbc42d3ad198640688a6fe13f41349554b49acc31dccd884539816f5eb4ac8fb1f1a6

This is partially supported by the fact that $b'$ is a square. Regarding the security conditions, all of the requirements correspond to the standard choices except for the class number bound. Computation of the class number is famously difficult and is therefore not feasible for curve generation. The 2005 version proposed an algorithm to verify the condition, which was only based on picking random elements of the class group (represented as quadratic forms) and computing their order. This can, of course, only be used to prove that the conditions are satisfied and not the contrary. Any comments for the class number computations were removed in the 2010 version. The class number can be bounded by the CM discriminant, which can be quickly derived from the trace, and so it seems that the condition actually talks about the discriminant. The seeds for the seven standardized primes (resp. curves) were chosen as 7 substrings of 160-bit-length of $\pi2^{1120}$ (resp. $\lfloor e2^{1120} \rfloor$). These choices seem to follow from the email by M. Scott [4].