## gcc now works on snow leopard

After upgrading to Snow Leopard, I encountered some incompability problems. One of them is the wifi problem that has been resolved. And gcc problem has just also been resolved 🙂

Like has been said here, here and here, the gcc problems can be solved easily by installing xcode from the Snow Leopard media installation.
(luckily I don’t have to do this, this and this 😉 )

Now I can get back to coding. Yay!

## Table of Low-Weight Binary Irreducible Polynomials

A very useful list of irreducible trinomial and pentanomial of degree n 2 <= n <= 10000.

• #### Rn Colvard 2:26 am on July 17, 2010 Permalink | Reply

Need GF(2^64) & GF(2^32) irreducible polynomials

## modifying curve setting up

```/* CG - February 2010
the program is supposed to find y for any given x
[in progress]
the representation is in polynomial
*/

#include <stdio.h>
#include <stdlib.h>
#include "field2n.h"
#include "poly.h"
#include "eliptic.h"

unsigned long random_seed;
extern FIELD2N poly_prime;

void set_field(value, n)
FIELD2N *value;
INDEX n;
{
value->e[0] = n;
}

void set_curve(curv)
CURVE *curv;
{
curv->form = 1;
set_field(&curv->a6, 1L);
null(&curv->a2);
//   set_field(&curv->a2, 0L);
}

int main()
{
FIELD2N	*data, *data_juga;
CURVE *curve;
POINT *point;
INDEX error;
FIELD2N f;
POINT *pnt;

curve = malloc(sizeof(CURVE));
if (curve == NULL) {exit(-1);}

point = malloc(sizeof(POINT));
if (point == NULL) {exit(-1);}

if (!irreducible(&poly_prime)) return(0);
print_field("poly_prime = ", &poly_prime);

if (error = init_poly_math())
{
printf("Can't initialize S matrix, row = %d\n", error);
return(-1);
}

printf("setting up curves \n\n");

set_curve(curve);
print_curve("the curve after setting up: ", curve);

return 0;
}

```

``` poly_prime = 8 0 0 0 0 c9 setting up curves ```

``` ```

```the curve after setting up: form: 1 a2: 0 0 0 0 0 0 a6: 1 0 0 0 0 0 ```

• #### zakimath 7:28 am on February 24, 2010 Permalink | Reply

how to find an elliptic curve E with #E (the order of group) is prime…? 🙂

• #### CG 9:21 am on February 24, 2010 Permalink | Reply

hadoh! susah, harus tanya sama dukun math dulu nih 😀

• #### zakimath 11:10 am on February 24, 2010 Permalink | Reply

hehehe, emang susah bgt! masih belum terbayang… 🙂
Kalo gitu dibalik: Jika diberikan bilangan prima p, apakah terdapat suatu kurva elliptik E sedemikian hingga #E = p ?

• #### CG 11:27 am on February 24, 2010 Permalink | Reply

[berpikir keras] #E itu order kurva ya? berarti jumlah titik dalam kurva? bisa gitu jumlah titiknya ganjil (prima) kan titik2xnya sepasang? y^2?

• #### zakimath 12:59 pm on February 24, 2010 Permalink | Reply

Iya bu, #E itu banyaknya titik dalam suatu kurva E… bener gk sih simbolnya? koq jd lupa, he2… Contohnya kurva elliptik E: y^2 = x^3 + 12x + 20 atas field F_23 itu mempunyai jumlah titik 17, yaitu #E = 17 yg merupakan bilangan prima, akibatnya setiap titiknya merupakan generator dari E. CMIIW…

• #### zakimath 1:03 pm on February 24, 2010 Permalink | Reply

Hmmm, tp rasanya ada yg salah dg komentarku… #E = 17 itu sudah termasuk titik infinity blom ya? aduh, koq jadi lupa… 😦

• #### CG 9:23 pm on February 24, 2010 Permalink | Reply

eh baru aja saya mau bales, iya bner ganjil kan ditambah point of infinity 🙂

• #### HongKong 10:09 pm on February 27, 2010 Permalink | Reply

jawabannya sih.. bisa bilangan ganjil dan bisa juga bilangan genap ((x,0) kan gak punya pasangan)
untuk setiap bilangan prima p selalu dapat dicari kurva eliptik atas Fp dengan orde (banyaknya titik) p

• #### CG 6:26 am on February 28, 2010 Permalink | Reply

thank you, HongKong 🙂

• #### CG 5:33 pm on February 28, 2010 Permalink | Reply

baru inget kalau si HongKong = the geometer 😀

## Is composite field secure?

The discussion about composite field implementation and its security can be read here.

Paper comparing about finite field for using in elliptic curve cryptography is here.

Important paper about how secure is elliptic curve over extension field is here.

Paper about efficient arithmetic in finite field extensions with application in elliptic curve cryptography is here.

• #### CG 5:48 pm on February 17, 2010 Permalink | Reply Tags: composite fields ( 2 ), ECC ( 14 ), finite fields ( 9 )

1. Comparison of Galois Fields Multipliers in Standard and Composite Fields Architectures, Petrus Mursanto, Proceedings of National Conference on Computer Science and Information Technology 2007, January 29-30, 2007, Faculty of Computer Science, University of Indonesia.
2. A Scalable Dual-Field Elliptic Curve Cryptographic Processor, Akashi Satoh and Kohji Takano, IEEE TRANSACTIONS ON COMPUTERS, VOL. 52, NO. 4, APRIL 2003.
3. Eﬃcient Methods for Composite Field Arithmetic, E. Savas and C.  K. Koc, Technical Report, December 1999.
4. Implementation Options for Finite Field Arithmetic for Elliptic Curve Cryptosystems, Christof Paar, 1999.
5. Hardware Implementation of Eﬃcient Modiﬁed Karatsuba Multiplier Used in Elliptic Curves, Sameh M. Shohdy, Ashraf B. El-Sisi, and Nabil Ismail (Corresponding author: Sameh M. Shohdy), International Journal of Network Security, Vol.11, No.3, PP.138–145, Nov. 2010.
6. http://www.computer.org/portal/web/csdl/abs/html/trans/tc/2003/11/t1391.htm

## Adding and doubling in hardware

The above is the hardware implementation for point addition and double addition in Guide to Elliptic Curve Cryptography – Hankerson,Menezes,Vanstone page 81.

• #### Soni 8:03 pm on February 15, 2010 Permalink | Reply

kalau dilihat dari istilahnya: ‘reconfigurable hardware architecture’, berarti rekonfigurasi dilakukan secara software. benar begitu?

• #### Samantha 11:14 pm on February 19, 2010 Permalink | Reply

Nice blog, i like it, its informative,
i will visit his blog more often.

Cheers

• #### CG 4:42 pm on February 21, 2010 Permalink | Reply

you’re welcome, samantha.

thank you for visiting.

• #### Lana 9:15 am on February 24, 2010 Permalink | Reply

Nice post! I really like your posting.

Cheers

• #### CG 11:25 am on February 24, 2010 Permalink | Reply

oh no. i think samantha and lana is automatically generated comments 😀

## More on ONB1 identity element

“Application of Finite Fields”  page 98:

For a type I optimal normal basis, its minimal polynomial is obviously x $x^n + ... + x + 1$, which is irreducible over $F_q$ if and only if $n + 1$ is a prime and $q$ is primitive in $Z_{n+1}$

For n = 4,
$x^4+x^3+x^2+x = 1$
$x^5 = 1$
$x^6 = x$
$x^7 = x^2$
$x^8 = x^3$
$x^9 = x^4$

Ex :
Let’s prove that 1111 is the identity element of ONB1 n = 4.

1010 x 1111 = ($x^8+x^2$) x ($x^8+x^4+x^2+x$)
= $x^{16}+x^{12}+x^{10}+x^9+x^{10}+x^6+x^4+x^3$
= $x^{16}+x^{12}+x^9+x^6+x^4+x^3$
= $x + x^2 + x^4 + x + x^4 + x^3$
= $x^2 + x^3$
= $x^2 + x^8$
= $x^8 + x^2$
= 1010

## ONB1 identity element

Rosing wrote on page 144:

In an optimal normal basis, adding 1 is the same as taking a complement

And finally figuring this out after finding out that the identity element of ONB1 is $x^{2^{n-1}}+...+x^{2^{1}}+x^{2^{0}}$. If we have n = 4, the identity element or “1” is 1111 ($x^{8}+x^{4}+x^{2}+x$).

That’s why if we have 0011 in normal basis ($x^2+x$), adding it with “1” so it becomes 0011 + 1111 = ($(x^2+x) + (x^8+x^4+x^2+x)$ = $x^8+x^4$ = 1100.

Hoooraaaay!

## NAF Representation

Using algorithm here (this algorithm is equal with Algorithm 3.30 in Guide to Elliptic Curve Cryptography, Hankerson-Menezes-Vanstone, #98), the result is:

Notes:

1. The length of NAF representation is at most one more than the length of the binary representation of k.
2. In NAF representation, non-zero values cannot be adjacent.

## Doubling & Addition Table (4 bits)

Notes:

1. The calculation starts from LSB
2. Every bit shift means doubling, bit 1 means added by P and bit 0 means not added by P
3. Adding costs more than doubling

• #### Budi Rahardjo 5:19 pm on February 13, 2010 Permalink | Reply

to be frankly, i cannot see the pattern from the table.
i have different notation in my head 🙂 which is basically similar to what you wrote in your notes.

• #### CG 5:42 pm on February 13, 2010 Permalink | Reply

@BR: should there be any pattern anyway? 😛 i’m so lost in multiplication of different bases 😀 show me your notation 🙂

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