Updates from February, 2010 Toggle Comment Threads | Keyboard Shortcuts

  • CG 10:21 am on February 28, 2010 Permalink | Reply
    Tags: , ,   

    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!

     
  • CG 11:31 am on February 24, 2010 Permalink | Reply
    Tags: , irreducible polynomials   

    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

  • CG 12:15 pm on February 23, 2010 Permalink | Reply
    Tags: curve set up, , ,   

    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)
      ada teoremanya sih:
      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 😀

  • CG 4:47 pm on February 21, 2010 Permalink | Reply
    Tags: , manning forum,   

    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: , ,   

    Reading list 

    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. Efficient 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 Efficient Modified 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

     
  • CG 3:03 pm on February 15, 2010 Permalink | Reply
    Tags: , , morales, reconfigurable   

    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.
      i like your article specially about
      Adding and doubling in hardware

      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.
      i will come back to read more of your posts.
      specially about Adding and doubling in hardware

      Cheers

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

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

  • CG 10:14 pm on February 12, 2010 Permalink | Reply
    Tags: ,   

    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

     
  • CG 9:19 pm on February 12, 2010 Permalink | Reply
    Tags: , ,   

    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!

     
  • CG 10:51 am on February 10, 2010 Permalink | Reply
    Tags: , , non-adjacent form   

    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.
     
  • CG 9:54 am on February 10, 2010 Permalink | Reply
    Tags: , , point multiplication   

    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
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel