4
$\begingroup$

RFC 5639 brainpoolP160r1 has

p = E95E4A5F737059DC60DFC7AD95B3D8139515620F (Wolfram Alpha says prime)

A = 340E7BE2A280EB74E2BE61BADA745D97E8F7C300

B = 1E589A8595423412134FAA2DBDEC95C8D8675E58

x = BED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3

y = 1667CB477A1A8EC338F94741669C976316DA6321

q = E95E4A5F737059DC60DF5991D45029409E60FC09 (Wolfram Alpha says prime)

h = 1

I do not understand why h = 1 yet q < p. I thought that if you had a prime field size then there is only one cyclic subgroup in size equal to the field size (c.f. Lagrange). This doesn't seem to be the case for brainpoolP160r1

$\endgroup$

migrated from security.stackexchange.com Nov 22 '18 at 9:26

This question came from our site for information security professionals.

2
$\begingroup$

The order of the curve $\#E(\mathbb{F}_p)$ is different from $p$. In fact, according to Hasse's theorem, $\#E(\mathbb{F}_p)=p+1-t$ where $t$ the Frobenius trace satisfies $|t|<2\sqrt{p}$. So the gap between $\#E(\mathbb{F}_p)$ and $p$ is at most $2\sqrt{p}$. Note that, if $\#E(\mathbb{F}_p)=p+1$, $\textit{i.e.}$ $t=0$, the curve is supersingular. For brainpoolP160r1, the order is 1332297598440044874827085038830181364212942568457 (160-bit). You can play with sage code:

p = 0xE95E4A5F737059DC60DFC7AD95B3D8139515620F 
A = 0x340E7BE2A280EB74E2BE61BADA745D97E8F7C300
B = 0x1E589A8595423412134FAA2DBDEC95C8D8675E58
x = 0xBED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3
y = 0x1667CB477A1A8EC338F94741669C976316DA6321
E = EllipticCurve(GF(p),[A,B])
G = E(x,y)
G.order()
E.order()
$\endgroup$
1
$\begingroup$

This would be more appropriate on crypto.SX where it has been addressed several times:
https://crypto.stackexchange.com/questions/27904/how-to-determine-the-order-of-an-elliptic-curve-group-from-its-parameters
https://crypto.stackexchange.com/questions/8888/elliptic-curve-parameter-generation
https://crypto.stackexchange.com/questions/28947/how-to-calculate-elliptic-curve-parameters

Briefly, the order of the curve #E(GF(p)) (sometimes abbreviated n) is NOT p, although it is fairly close in magnitude. The curve group is the relevant finite group and is subject to Lagrange; any point on the curve has order (of the subgroup it generates) dividing n, and if n is prime, as is chosen to be the case for the Brainpool prime curves and also the X9/SECG prime curves, every point has order q=n and cofactor h=1.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy