Struktur Grup pada Himpunan Titik Rasional Kurva Eliptik

Attended an interesting final project presentation at Math Dept on Jan 15th 2009 8am.

It’s about proving that the rational points on elliptic curve form a group. Once again learning so much from those mathematicians. Thanks!

Software vs Hardware

Have just read this, this and this .

And make this simple table

Now reading this book and trying to figure out what issues in software implementation that worth to be the focus of my research and promising enough to explore [and defendable enough to convince my academic advisors ]

Why prime fields? Why binary fields?

From this document, now I can answer one of the questions from the previous posting:

Why prime fields?

1. Commonly used for software implementations because
   the integer arithmetic is more optimized in today’s
   microprocessors
2. Desktops: favour fast multipliers
3. Embedded: varies based on processor architecture‏
4. Hardware implementations benefit from the full size
   operands but the area impact may be significant
5. Hardware implementations carry chain timing challenges

Why binary fields?

1. Not as efficient in SW implementations compared to
   prime fields where large multipliers are available
   • Integer multipliers can deal with word size data
   • Not true for smaller processors with inefficient integer

   multipliers

2. Even more challenging for custom SW implementations if
   m is a large value
   • Challenging for SW implementations with reduced register

   space

3. Usually use a sliding window dbl/add to speed up
   multiplication

Questions and notes

1. Why prime field? Why binary field?
2. Reconfigurable, interoperable issues, are they important?
3. HW? SW? or HW/SW partitioning?

What and why Koblitz curves?

Answer to this post #1 (from “Software Implementation of Elliptic Curve Cryptography over Binary Fields” – Darrel Hankerson, Julio Lopez Hernandez and Alfred Menezes):

Koblitz curves are elliptic curves defined over . The primary advantage of Koblitz curve is that point multiplication algorithms can be devised that do not use any point doublings.

More discussions, more questions

From the discussion at Math Dept. today:

1. Why and when Koblitz curve?
2. Why cyclic group/subgroup? Does it have to be cyclic? Or does it have to be non-cyclic?
3. When I have with the order of the group where is a prime number then the group will be cyclic. What if the is which is also a prime number not equal to . Will the group be cyclic?

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 , , , and . 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 -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 .

More on fields and polynomial

Have just learned that:

means that the elements are

, , and

means that we’ll have tuple, thus we’ll have a polynomial with degree

(degree is the highest exponent of the polynomial).

Example:

means

Important notes:

is only if is prime.

Polynomial

The phd student had just found out more about representation. For , there are tuples. The tuples turn out to be the degree of a polynomial!

She is so happy to know the basic terms and concepts in math. Interesting!

[will write more about this, the phd student needs to get ready for a morning jog ]

Changing generators

I was going to observe the “behaviour” of an elliptic curve by changing its generator, and looking for an answer what does happen if I change it.

From the discussion yesterday, I understand that each generator will generate different cyclic subgroups. And does it have something to do with security level? Let’s find out.

Still thinking about changing other parameters of elliptic curve, and observe the result.