Updates from December, 2009 Toggle Comment Threads | Keyboard Shortcuts

  • CG 11:12 pm on December 30, 2009 Permalink | Reply
    Tags: torsion subgroups   

    List of torsion subgroups 

    A list of elliptic curves with each possible torsion subgroup can be found here:

    And PARI code that lists infinitely many elliptic curve with each torsion subgroup is here.

    Advertisements
     
  • CG 11:01 pm on December 30, 2009 Permalink | Reply
    Tags: torsion points   

    Torsion points of elliptic curves 

    From Torsion Points of Elliptic Curves Over Number Fields by Christine Croll :

    so ours is finite order. Then

    hah!

    And this is an example:

    More about torsion points:

    1. ON THE TORSION POINTS OF ELLIPTIC CURVES  & MODULAR ABELIAN VARIETIES by SETH KLEINERMAN
    2. ELLIPTIC CURVES WITH A TORSION POINT by TOSHIHIRO HADANO

    [head ready to explode]

     
  • CG 12:40 am on December 30, 2009 Permalink | Reply
    Tags: ,   

    Comparing elltors 

    for y^2 + xy = x^3 + x^2 + 1 :

    (00:37) gp > a = 1
    %1 = 1
    (00:37) gp > b = 1
    %2 = 1
    (00:37) gp > E = ellinit([0,0,0,a,b])
    %3 = [0, 0, 0, 1, 1, 0, 2, 4, -1, -48, -864, -496, 6912/31, [-0.6823278038280193273694837397, 0.3411639019140096636847418698 - 1.161541399997251936087917687*I, 0.3411639019140096636847418698 + 1.161541399997251936087917687*I]~, 3.749942978094342855851406868, -1.874971489047171427925703434 + 1.321720533565204538833995727*I, -1.256789871861911570289134735 + 0.E-29*I, 0.6283949359309557851445673678 - 1.280744177088026904445230577*I, 4.956376633845946955308257251]
    (00:38) gp > elltors(E)
    %4 = [1, [], []]

    for y^2 + xy = x^3 + z^3x^2 + (z^3+1)

    (00:38) gp > a = 8
    %5 = 8
    (00:39) gp > b = 9
    %6 = 9
    (00:39) gp > E=ellinit([0,0,0,a,b])
    %7 = [0, 0, 0, 8, 9, 0, 16, 36, -64, -384, -7776, -67760, 3538944/4235, [-1.000000000000000000000000000, 0.5000000000000000000000000000 - 2.958039891549808021283664145*I, 0.5000000000000000000000000000 + 2.958039891549808021283664145*I]~, 2.323573124298217095517745754, -1.161786562149108547758872877 + 0.9328742056162391756323628615*I, -1.773647591593647783280373514 + 0.E-28*I, 0.8868237957968238916401867572 - 2.064141081460241175088749935*I, 2.167601432520942242537573241]
    (00:39) gp > elltors(E)
    %8 = [2, [2], [[-1, 0]]]

     
    • Budi Rahardjo 7:03 am on December 30, 2009 Permalink | Reply

      hmm… still trying to digest this

      • CG 3:20 pm on December 30, 2009 Permalink | Reply

        me too. still don’t understand what is the torsion and the generators 😦

  • CG 12:04 am on December 30, 2009 Permalink | Reply
    Tags: ,   

    elltors 

     
  • CG 11:24 am on December 27, 2009 Permalink | Reply
    Tags: , ,   

    Embedding data to a curve 

    To embed data to a curve, these are things to be the guidelines:

    1. The “data” to embedded to the curve is in the form of big integer. In the example by Rosing, the data is processed in hexadecimal representation.
    2. Put the data into a variable and add more bits for some “garbage” bits that will help the data to be a point that fits into the curve equation.
    3. The more garbage, the more difficult for the attacker to get the data.
    4. The garbage keep incremented (with the size of increment we choose) until we find an x that fits the equation, and then there will be two values of  y to make it P(x,y) on curve.

    Here’s a simple code for checking that a data can be embedded to a curve (modified Rosing):

    //This program is to experiment with small curves
    //CG - Dec 2009
    
    #include <stdio.h>
    #include "field2n.h"
    #include "poly.h"
    #include "eliptic.h"
    
    extern FIELD2N poly_prime;
    
    int main()
    {
            FIELD2N t1, t2, test;
            FIELD2N q, r, y, x, y2, xy, g[3];
            INDEX   i, error, j, order, k, m, n;
            ELEMENT index, check;
            FILE *del;
            CURVE  crv;
            POINT   p2, p3, p4, p5, p6, p7;
            char curve_string[80];
    
            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);
            }
    
            crv.form = 0;
            null(&crv.a2);
            null(&crv.a6);
    //      crv.a2.e[NUMWORD] = 1;
    //      crv.a2.e[NUMWORD] = 1;
            crv.a6.e[NUMWORD] = 0x8;
            crv.a6.e[NUMWORD] = 0x9;
            null(&test);
            test.e[NUMWORD] = 0xa;
            print_field("data = ", &test);
            poly_embed( &test, &crv, NUMWORD, 0, &p2);
    
    /*  check that point is in fact on curve  */
    
            copy(&p2.y, &y);
            copy(&p2.x, &x);
            print_point("for point", &p2);
     poly_mul( &p2.y, &y, &y2);
            poly_mul( &y, &x, &xy);
            SUMLOOP(i) r.e[i] = y2.e[i] ^ xy.e[i];
            poly_fofx( &x, &crv, &q);
            SUMLOOP(i) test.e[i] = r.e[i] ^ q.e[i];
            print_field("rhs + lhs =",&test); //if the rhs+lhs = 0 means that th
    e point is on curve
            print_field("left = ", &r);
            print_field("right = ", &q);
    return 0;
    }
    

    The result is


    poly_prime =
    13
    data =
    a
    for point
    x: a
    y: f
    rhs + lhs =
    0
    left =
    6
    right =
    6

    Notes:

    1. This means that for a 4-bit length curve, 13 (1101 = x^3 + x^2 + 1 ), the data is $0xa, the point is P(0xa, 0xf) . if rhs + lhs = 0 means that the data is already on curve.
    2. There are several ways to convert a message into a “data” (large integer).
     
    • Budi Rahardjo 6:09 am on December 28, 2009 Permalink | Reply

      Wow, you have progressed. Let me digest this first. (Still thinking how to find y, given x.)

      • CG 11:52 am on December 28, 2009 Permalink | Reply

        next i have to explore pari for elltor. and finish the decrypting part. oh and also convert the message into a big integer. and praying for finishing it before 11th jan!

    • Soni 6:17 am on December 28, 2009 Permalink | Reply

      i have several questions and comments for this posting:
      1. what do you mean by ‘data’? is it a message to be encrypted?
      2. what is ‘garbage’? is it some kind of adjustment bit which has purpose to fit the point into the curve, or else?
      3. what is a point exactly? is it the message or the key?
      4. what do you mean by increment garbage? is it just adding the representation, or add more bits?
      5. after you give the example, now i understand how to represent prime number into equation :D.
      6. i don’t understand the code. maybe i have to see the header file first before i understand how the functions work. can i?

      • CG 11:41 am on December 28, 2009 Permalink | Reply

        @soni: 1. data is message to be encrypted but have converted from array of characters into a form of integer (usually big integers).
        2. garbage is additional bits added to the data in integer representation (so when the data is viewed in binary representation, adding garbage is simply add more bits to it).
        3. a point is a pair of (x, y) that solve the curve equation. the message is the data, and the key is how many times the point is moved inside the curve.
        4. adding more bits.
        5. by converting the prime numbers into binary representation?
        6. yes. the code use many header files. and contained a lot of tricks and maths too 😀

  • CG 3:52 am on December 17, 2009 Permalink | Reply
    Tags: 4 bit, , , test bed   

    4-bit curve 

    Now experimenting on a very small curve, taken from Guide to Elliptic Curve Cryptography #27, F_2^4 with reduction polynomial f(z) = z^4+z+1 , E: y^2 + xy = x^3 + z^3x^2 + (z^3+1) (a = z^3, b = z^3+1).

    Have checked that the points on #81 are on curve.

    Next to do is to perform curve operation Q= k.P

    Notes:

    This curve is not a Koblitz curve. Going compare this one with Koblitz (by changing a =1 or a = 0 and b = 1). To generate points on curve look at P1363.

     
    • Budi Rahardjo 8:00 am on December 17, 2009 Permalink | Reply

      Still thinking how to make a flexible ecc system to calculate all of these.

    • CG 12:44 pm on December 17, 2009 Permalink | Reply

      and what it’s gonna be called? a simulator? platform?

    • soni 9:22 am on December 18, 2009 Permalink | Reply

      what do you mean by ‘small curve’? if we only have 4 bit, it means that we only have a little bit combinations. then we have a rough curve, rather than a smooth curve if we have more bit. is it right?

    • CG 4:55 pm on December 18, 2009 Permalink | Reply

      @soni: i’m afraid it’s not that simple. yes that small curves will have only a small number of points but higher bits doesn’t not determine the smoothness of the curve. the curve is called “smooth” only if it is defined in real numbers, not in finite fields.

  • CG 6:03 am on December 13, 2009 Permalink | Reply  

    Polynomial scribbles cartoon 

     
    • Budi Rahardjo 6:43 pm on December 13, 2009 Permalink | Reply

      ha ha ha … koblitz guy?

    • CG 6:47 pm on December 13, 2009 Permalink | Reply

      @BR: good guess 🙂 how do you know it’s not the koblitz girl? :))

    • Budi Rahardjo 6:53 pm on December 13, 2009 Permalink | Reply

      because he’s not wearing skirt, lipstick, eye lashes, or those girly stuff 🙂

    • CG 6:54 pm on December 13, 2009 Permalink | Reply

      @BR: smart answer 😀 hei but how do you know koblitz is not wearing eyelashes? :))

  • CG 10:15 pm on December 11, 2009 Permalink | Reply
    Tags: equation, latex   

    Writing latex equation in WordPress 

    I keep forget how to paste latex equation in WordPress, so I post it here (I might have been but don’t remember).

    1. Type the equation here. Then copy and paste it to WordPress editor.
    2. Add put the equation inside “$latex” <equation here> “$”.
    3. Done. Great and convincing equation appear on your WordPress blog.
     
  • CG 9:23 pm on December 11, 2009 Permalink | Reply
    Tags: ,   

    Koblitz-163bit, the point is on curve! On curve! Yay! 

    Oh, finally. The code proves that the point (x, y) from the sample parameter is on the Koblitz-163.

    There are several mistakes:

    1. I took the wrong sample parameters set. It’s not supposed to be the parameters at the previous posting, but these:
    2. I used the wrong equation. It was y^{2}+xy=x^{3}+ax+b ! After spending the whole day debugging every operations and bits and parameters, I checked the equation, and I picked the wrong one all this time. It should have been y^{2}+xy=x^{3}+x^{2}+1 .

    The coding is:

    #include <stdio.h>
    #include "field2n.h"
    #include "poly.h"
    
    extern FIELD2N poly_prime;
    
    int main(){
       INDEX i;
    
       FIELD2N a = {0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001};
       FIELD2N b = {0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001};
       /*FIELD2N b = {0x00000002, 0x0a601907, 0xb8c953ca, 0x1481eb10, 0x512f7874, 0x4a3205fd};   */
       FIELD2N x = {0x00000002, 0xFE13C053, 0x7BBC11AC, 0xAA07D793, 0xDE4E6D5E, 0x5C94EEE8};
       FIELD2N y = {0x00000002, 0x89070FB0, 0x5D38FF58, 0x321F2E80, 0x0536D538, 0xCCDAA3D9};
    
       FIELD2N yy, xy;
       FIELD2N left, right;
       FIELD2N c;
       FIELD2N x_2, x_3, ax;
    
       null(&yy);
       null(&xy);
       null(&c);
       null(&left);
       null(&right);
       null(&x_2);
       null(&x_3);
       null(&ax);
    
       if (!irreducible(&poly_prime)) return(0);
          print_field("poly_prime = ", &poly_prime);
    
       printf("\nNUMBITS = %d", NUMBITS);
       printf("\nNUMWORD = %d", NUMWORD);
       printf("\nMAXLONG = %d\n", MAXLONG);
    
       print_field("a = ", &a);
       print_field("b = ", &b);
    
       print_field("x = ", &x);
       print_field("y = ", &y);
       poly_mul(&y, &y, &yy);
       print_field("yy = ", &yy);
       poly_mul(&x, &y, &xy);
       print_field("xy = ", &xy);
       SUMLOOP(i) left.e[i] = yy.e[i] ^ xy.e[i];
       print_field("left = ", &left);
    
       poly_mul(&x, &x, &x_2);
       print_field("x_2 = ", &x_2);
       poly_mul(&x, &x_2, &x_3);
       print_field("x_3 = ", &x_3);
       poly_mul(&a, &x, &ax);
       print_field("ax = ", &ax);
       print_field("b = ", &b);
       SUMLOOP(i) right.e[i] = x_3.e[i] ^ x_2.e[i];
       SUMLOOP(i) right.e[i] = right.e[i] ^ b.e[i];
       print_field("right = ", &right);
    
       return 0;
    }
    

    this header file is also have to be updated for the NUMBITS:

    /*** field2n.h ***/
    
    #define WORDSIZE        (sizeof(int)*8)
    #define NUMBITS         163
    
    #define NUMWORD         (NUMBITS/WORDSIZE)
    #define UPRSHIFT        (NUMBITS%WORDSIZE)
    
    #define MAXLONG         (NUMWORD+1)
    
    #define MAXBITS         (MAXLONG*WORDSIZE)
    #define MAXSHIFT        (WORDSIZE-1)
    #define MSB                     (1L<<MAXSHIFT)
    
    #define UPRBIT          (1L<<(UPRSHIFT-1))
    #define UPRMASK         (~(-1L<<UPRSHIFT))
    #define SUMLOOP(i)      for(i=0; i<MAXLONG; i++)
    
    typedef short int INDEX;
    
    typedef unsigned long ELEMENT;
    
    typedef struct {
            ELEMENT         e[MAXLONG];
    }  FIELD2N;
    

    and also this line from polymain.c:

    FIELD2N poly_prime = {0x00000008, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x000000c9}; /*163*/
    

    and the result is:


    poly_prime =
    8 0 0 0 0 c9

    NUMBITS = 163
    NUMWORD = 5
    MAXLONG = 6
    a =
    0 0 0 0 0 1
    b =
    0 0 0 0 0 1

    2 fe13c053 7bbc11ac aa07d793 de4e6d5e 5c94eee8
    y =
    2 89070fb0 5d38ff58 321f2e80 536d538 ccdaa3d9
    yy =
    7 ca0561ef a7b090b5 ddf25eaf f0567c2c 39c1cad7
    xy =
    4 d7418721 62b253d5 a381f1f6 80b47e5c ad3aa2a
    left =
    3 1d44e6ce c502c360 7e73af59 70e20270 331260fd
    x_2 =
    6 710bd85f 2b559b08 5dc2832e 86f4a4c 7ef8d0be
    x_3 =
    5 6c4f3e91 ee575868 23b12c77 788d483c 4deab042
    right =
    3 1d44e6ce c502c360 7e73af59 70e20270 331260fd

    Now left and right is equal! YAY!!!

     
  • CG 11:33 pm on December 10, 2009 Permalink | Reply
    Tags: ,   

    Not on curve! 

    Modifying Rosing’s codes to do this checking if a point is on curve using Pari,
    with the sample parameters:

    the result is like this (on binary fields):


    poly_prime =
    8 0 0 0 0 c9

    NUMBITS = 163
    NUMWORD = 5
    MAXLONG = 6
    a =
    0 0 0 0 0 1
    b =
    2 a601907 b8c953ca 1481eb10 512f7874 4a3205fd

    3 f0eba162 86a2d57e a0991168 d4994637 e8343e36
    y =
    0 d51fbc6c 71a0094f a2cdd545 b11c5c0c 797324f1
    left =
    1 393a5074 f973003b 4ab508ce 55cc184a 928293df
    right =
    1 cf775de5 a25942e6 33c8b050 97bf9375 d364fba2

    left and right, is not equal!

    The idea is to compare if the left side and the right side of y^2 + xy = x^3 + ax + b is equal, then the point (x, y) is on the curve.

    Something is still very wrong. Now will do debugging…

     
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