Re: [TLS] Twist security for brainpoolp256r1

[Johannes Merkle <[e-mail]>]

> As Manuel has explained its the security level of the non-quadratic twist. It is NOT the security of the quadratic
> twists, which is the same as of the original brainpoolP256r1.
> 
> Background: All quadratic twists are isomorphic (equivalent) to each other. And each quadratic twist (i.e.
> brainpoolP256t1 and brainpoolP256r1) has the same set of non-quadratic twists, which are also all equivalent to each
> other (they are quadratic twists of each other). So we have two sets of curves: The quadratic twists of brainpoolP256r1
> (which contains brainpoolP256t1) and the set of non-quadratic twists of brainpoolP256r1. Any curve from the former set
> (including brainpoolP256t1) is as secure as brainpoolP256r1. And any curve from the second set (the non-quadratic
> twists) have a group order that factors to moderately sized primes and are, thus, insecure.  But nobody would use the
> non-quadratic twists, except potentially in an invalid-curve attack.
> 


As Watson Ladd just pointed out to me, the terms "quadratic twists" and "non-quadratic twists" are not common in math
textbooks. For a curve in Weierstrass form E: y^2 = x^3 + a*x  + b mod p, the term twist denotes a curve  E': y^2 = x^3
+ v^2*a*x + v^3* b mod p.
 - If v is a quadratic residue, i.e., if there is a w with w^2 = v mod p, then E and E' are isomorphic mod p and thus
have equivalent security.
 - If v is a quadratic non-residue, E' is not isomorphic to E and the curve orders satisfy |E| + |E'| = p+2.
Text books often discuss only the case of quadratic non-residues (e.g. Blake, Seroussi, Smart).

In the case of the Brainpool curves, the twists mentioned in RFC 5639 are twists via a quadratic residue and have the
same security as the respective random curves.
-- 
Johannes