## Which curves? What order?

My academic advisor #3 asked those questions yesterday. And I got the answers from “Software Implementation of Elliptic Curve Cryptography over Binary Fields”, Darrel Hankerson, Julio Lopez Hernandez, and Alfred Menezes:

Which curves?

FIPS 186-2 has 10 recommended finite fields: 5 prime fields, and the binary fields $F_{2^{163}}$, $F_{2^{233}}$, $F_{2^{283}}$, $F_{2^{409}}$ and $F_{2^{571}}$. For each of the prime fields, one randomly selected eliptic curve was recommended, while for each of the binary fields one randomly selected elliptic curve and one Koblitz curve was selected.

The order

The fields were selected so that the bitlengths of their orders are at least twice the key lengths of common symmetric-key block ciphers – this is because exhaustive key search of a $k$-bit block sipher is expected to take roughly the same time as the solution of an instance of the elliptic curve discrete logarithm problem using Pollard’s rho algorithm for an appropriately-selected elliptic curve over a finite fied whose order has bitlength $2k$.

• #### CG 12:58 am on October 11, 2008 Permalink | Reply Tags: generator ( 2 ), order

[Hey, my last posting is almost a week ago. What have I been doing? How would I finish the phd in 3 years if the progress is like this???]

Order of an element, order of a group, order of a point. Have read about them but there are several questions in my head:

1. What the order of an element has to do with the security level of a curve, if there’s any relation between them?
2. What’s the use of a generator? It’s been said that a generator has the maximum possible order of $p-1$ elements. So what?

[scratching head, thinking hard, but it’s already late now. the phd student is getting sleepy… zzzzzzzzzzzzzzzz]

## Order of the point

Multiplication over elliptic curve is like this:

$Q = kP$

where $Q$ and $P$ are points on an elliptic curve and $k$ is an integer. The equation above means that $P$ is added to itself $k$ times.

What I don’t understand (yet) is, why the integer $k$ need not be larger than the “order” of the point $P$ ? Understand that reducing $k$ will save a great deal of processing. But what’s the relation between the “order” of the point with this statement:

The points in elliptic curve, forms a cyclic group (a field)

Update:

I guess now I start to grab the ideas about those previous paragraphs 🙂

I’ll check it to mathematician buddy as soon as possible 😉

• #### tetangga sebelah 7:03 pm on October 6, 2008 Permalink | Reply

walah baca postingan ini jadi merasa orang garut……dodol
cing atuh……pake bahasa manusia kalau posting tehhhh

@tetangga sebelah: cing atuh karunya ka sayah. lebaran mudik teh bawain oleh2x atuh, opor kek, dodol kek…

emang bukan bahasa manusia makanya saya juga ga ngarti…

• #### gre 5:51 pm on October 10, 2008 Permalink | Reply

speaking of field, you must be a knowledgeable person in abstract algebra and it is rarely found in LABTEK VIII 🙂
I am just wondering if the k integer might be a Lipshitz constant.

@gre: not yet a knowledgeable person in abstract algebra 😉
what is a Lipshitz constant anyway? [pls don’t give more headaches to me now 😀 ]

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r