Tagged: rosing Toggle Comment Threads | Keyboard Shortcuts

  • CG 2:01 pm on September 16, 2011 Permalink | Reply
    Tags: , random data, rosing   

    Is this random enough? 

    Advertisements
     
  • CG 3:18 pm on July 13, 2011 Permalink | Reply
    Tags: , , rosing   

    Setting up curves with different numbits for ElGamal 

    This book and the software is very useful for doing experiments of encrypting using elliptic curve cryptography. I’ve been reading some thread with questions on how to change curve parameters, and here’s how:

    To change the number of bits, you have to set it in field2n.h

    Choose the polynomial irreducible in polymain.c

    Set the message to be encrypted in elgamal.c (important note: the length of the message depends on the numbits of the curve)

     
  • CG 9:49 am on November 8, 2010 Permalink | Reply
    Tags: , ecc implementation, rosing   

    How secure is ECC with composite field binary? 

    An interesting discussion about ECC with composite field security with Dr. Michael Rosing here.

     
  • CG 9:55 am on April 30, 2010 Permalink | Reply
    Tags: , , rosing   

    Encryption – Decryption finally works 

    With the help of this debugger and that debugger, changing the data from this:

    into this:

    make the code works. It’s because the data occupied more space than the capacity of the number of words.


    lss-67-39:Rosing Experiments CG chika$ ./test_elgamal_CG
    poly_prime =
    8 0 0 0 0 c9
    setting up curve

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

    counter = 0
    inc = 5
    Base point
    x: 5 63323eab 10fc68f8 254d4d11 d2d518f2 9979dd24
    y: 4 883e6269 de8bf93e f6c224e3 330dbf7f 2dd25ec1

    create side 2's private key

    Side 2 secret:
    5 5d0be8bb a913fcdb 91edee60 4da6d486 295d85ac

    Generate side 2's public key

    Side 2 public key
    x: 0 60838c40 7580aec4 b658d152 729f7f67 51d694bd
    y: 0 1be3f90c c4a81de1 848ff01b d63e97a4 6b46c459
    data =
    0 68616c6c 6f0a0000 0 0 60000000

    Hide data on curve and send from side 1 to side 2

    curve before send_elgamal:
    form: 1
    a2: 0 0 0 0 0 2
    a6: 0 0 0 0 0 1

    Their_public before send_elgamal:
    x: 0 60838c40 7580aec4 b658d152 729f7f67 51d694bd
    y: 0 1be3f90c c4a81de1 848ff01b d63e97a4 6b46c459
    =====IN send_elgamal=====
    data (in send_gamal function) :
    0 68616c6c 6f0a0000 0 0 60000000
    Base point
    x: 5 63323eab 10fc68f8 254d4d11 d2d518f2 9979dd24
    y: 4 883e6269 de8bf93e f6c224e3 330dbf7f 2dd25ec1
    Base curve
    form: 1
    a2: 0 0 0 0 0 2
    a6: 0 0 0 0 0 1

    random value:
    5 3a0f94f6 e0caf9a7 2d189f04 8591c5e5 3935d4dc
    Random point C1
    x: 2 d6670f0 ab08aca3 8818adbe cf36881d 83accc06
    y: 2 cad560f5 72c889b5 226934a2 733455c8 c53a15a6
    counter = 0
    inc = 0
    raw point M (after poly_embed)
    x: 0 68616c6c 6f0a0000 0 0 60000000
    y: 0 7a64a103 a296a42d 4130d375 23ef2cf2 3f1a3ec0
    Their_public:
    x: 0 60838c40 7580aec4 b658d152 729f7f67 51d694bd
    y: 0 1be3f90c c4a81de1 848ff01b d63e97a4 6b46c459
    hidden point (after poly_elptic_mul)
    x: 7 1f5fceb7 8269106c c1708600 cde8821b 38e0c7ee
    y: 2 d752fec4 40840001 be4a3e7f 347e7013 7f36ce97
    Hidden data (C2):
    x: 6 a8a348b9 60a911b7 852a3bb9 8ba949df 5a157ae
    y: 0 239b098 7584aea3 af4431db 2f3fa3f4 312c5ea9
    Random point (C1):
    x: 2 d6670f0 ab08aca3 8818adbe cf36881d 83accc06
    y: 2 cad560f5 72c889b5 226934a2 733455c8 c53a15a6
    =====OUT send_elgamal

    AFTER send_elgamal
    curve after send_elgamal:
    form: 1
    a2: 0 0 0 0 0 2
    a6: 0 0 0 0 0 1

    Hidden data (C2)
    x: 6 a8a348b9 60a911b7 852a3bb9 8ba949df 5a157ae
    y: 0 239b098 7584aea3 af4431db 2f3fa3f4 312c5ea9
    Random point (C1)
    x: 2 d6670f0 ab08aca3 8818adbe cf36881d 83accc06
    y: 2 cad560f5 72c889b5 226934a2 733455c8 c53a15a6

    Recover transmitted message

    IN receive_elgamal
    Base curve in receive_elgamal
    form: 1
    a2: 0 0 0 0 0 2
    a6: 0 0 0 0 0 1

    Hidden_data (in receive_elgamal) :
    x: 6 a8a348b9 60a911b7 852a3bb9 8ba949df 5a157ae
    y: 0 239b098 7584aea3 af4431db 2f3fa3f4 312c5ea9
    Random point
    x: 2 d6670f0 ab08aca3 8818adbe cf36881d 83accc06
    y: 2 cad560f5 72c889b5 226934a2 733455c8 c53a15a6
    hidden_point (d*C1):
    x: 7 1f5fceb7 8269106c c1708600 cde8821b 38e0c7ee
    y: 2 d752fec4 40840001 be4a3e7f 347e7013 7f36ce97
    &raw_point:
    x: 0 68616c6c 6f0a0000 0 0 60000000
    y: 0 7a64a103 a296a42d 4130d375 23ef2cf2 3f1a3ec0
    raw_point.x
    0 68616c6c 6f0a0000 0 0 60000000
    &raw_data (point):
    x: bffff630 bbe72787 d25ef6fb 139332fc 90db35c4 fd129391
    y: 0 2 d6670f0 ab08aca3 8818adbe cf36881d
    raw_data (point):
    x: 0 68616c6c 6f0a0000 0 0 60000000
    y: 0 68616c6c 6f0a0000 0 0 60000000
    &raw_data (field):
    bffff630 bbe72787 d25ef6fb 139332fc 90db35c4 fd129391
    raw_data (field):
    0 68616c6c 6f0a0000 0 0 60000000
    =====OUT receive elgamal

    sent data
    0 68616c6c 6f0a0000 0 0 60000000
    received data (field)
    0 68616c6c 6f0a0000 0 0 60000000

     
  • CG 1:48 pm on April 8, 2010 Permalink | Reply
    Tags: , , rosing   

    Houston, we cannot recover the plaintext 


    poly_prime =
    8 0 0 0 0 c9
    data test =
    68616c6c 6f0a0000 0 0 0 6000000
    setting up curves

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

    counter = 0
    inc = 5
    Base point
    x: 5 63323eab 10fc68f8 254d4d11 d2d518f2 9979dd24
    y: 7 95f678a8 39481c22 2f4c7995 4a571060 6fe263b2

    create side 2's private key

    Side 2 secret:
    5 5d0be8bb a913fcdb 91edee60 4da6d486 295d85ac

    Generate side 2's public key

    Side 2 public key
    x: d107f500 66784cc8 9a0621db 9050de48 31c6e7c5 7d65d83b
    y: 2 1763b098 91e23a1e 2f96df5c 50c63a33 a4b16c75

    Hide data on curve and send from side 1 to side 2

    counter = 0
    inc = 0
    counter = 0
    -- pnt->x =
    x: bffff4d8 1 bffff508 90483f7b a0073a58 905e07e8
    y: 100131 1000 0 bffff7a0 bffff71c 1ed5
    counter = 1
    -- pnt->x =
    x: bffff4d8 1 bffff508 90483f7b a0073a58 905e07e8
    y: 100132 1000 0 bffff7a0 bffff71c 1ed5
    Hidden data
    x: 100135 70f0eb24 c996c3e4 2d120279 e9f3ec30 3370129a
    y: 100132 7a61b198 ccba8673 27995624 c069db6f ab7bdfaa
    Random point
    x: d107f503 81d255cd 358038a7 148e84da a7b39f16 75d320c4
    y: 3 e0053e42 6538a7a0 41dabd3 4cb90701 9a31b3b0

    Recover transmitted message

    sent data
    100130 1000 0 bffff7a0 bffff71c 1ed5
    received data
    d117f431 a8e83258 f59857d7 646d8b77 90191393 f6674925

     
  • CG 11:26 am on March 10, 2010 Permalink | Reply
    Tags: elliptic curve point multiplication, rosing, testing   

    point multiplication testing 

    Point multiplication testing works.

    /* CG - March 2010
       program to check point multiplication
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include "field2n.h"
    #include "poly.h"
    #include "eliptic.h"
    
    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);
       set_field(&curv->a2, 2L);
    }
    
    int main()
    {
            FIELD2N *data;
            FIELD2N *t;
    	FIELD2N y, x, y2, xy;
    	ELEMENT index, check;
            INDEX i, error;
    	FILE *del;
    	CURVE *curve;
            POINT *p, *r;
    	char curve_string[80];
    	
            data = malloc(sizeof(FIELD2N));
            if (data == NULL) {exit(-1);}
    
            t = malloc(sizeof(FIELD2N));
            if (t == NULL) {exit(-1);}
    
            curve = malloc(sizeof(CURVE));
            if (curve == NULL) {exit(-1);}
    
            p = malloc(sizeof(POINT));
            if (p == NULL) {exit(-1);}
    
            r = malloc(sizeof(POINT));
            if (r == 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);
    	}
    
            data->e[0] = 1L;	
            data->e[1] = 1L;
            print_field("data test = ", data);
    
    //        printf("NUMWORD = %ld\n", NUMWORD );
            null(t);
            t->e[NUMWORD] = 2L;
            print_field("t = ", t);
    
            printf("setting up curves\n\n");
            set_curve(curve);
            print_curve("the curve after setting up: ", curve);
    
            poly_embed(data, curve, 1, 0, p);
            printf("data after embedded to the curve: \n");
            print_point("p = ", p);
    
            printf("after point multiplication: \n");
            poly_elptic_mul(t, p, r, curve);
            print_point("r = ", r);	
    }
    

    This is the result of 2P.

    lss-67-23:Rosing Experiments CG chika$ ./test_left_right_eq2
    poly_prime =
    8 0 0 0 0 c9

    NUMBITS = 163
    NUMWORD = 5
    MAXLONG = 6
    a2 =
    2 0 0 0 0 0
    a6 =
    1 0 0 0 0 0

    1 1899fea5 56c420f2 9e4b1f87 5cb6b783 899feb0c
    y =
    1 26a707a1 8daf42c0 dde1d433 6638016d fd2dfcd4
    yy =
    0 1460a86a b5fd89df 6fc41f77 67325e56 91b4cecb
    xy =
    6 ed2088de 820e441 93687252 d3242e3a 62be995e
    x_2 =
    4 3e3b1763 9148e81e efc41b97 24c6e697 82da1543
    x_3 =
    4 ae6b51e0 468d0597 9c179778 e018bf6e 60eb0e54
    ax2 =
    3 572b7154 fb506809 60bbfa5d 540ecf02 93e159c1
    left =
    6 f94020b4 bddd6d9e fcac6d25 b416706c f30a5795
    right =
    6 f94020b4 bddd6d9e fcac6d25 b416706c f30a5795

    And this is for 10P

    lss-67-23:Rosing Experiments CG chika$ ./test_left_right_eq2
    poly_prime =
    8 0 0 0 0 c9

    NUMBITS = 163
    NUMWORD = 5
    MAXLONG = 6
    a2 =
    2 0 0 0 0 0
    a6 =
    1 0 0 0 0 0

    3 91d7e88a 1bb31eaf bdf2e27d bf0271b6 333c29ce
    y =
    3 5d3c582c cbc0a643 fe11bd5a f6e54c0 41df835f
    yy =
    5 69b24b3f 8d3d7709 cd222a06 3d76432f 401b8c42
    xy =
    6 53764521 604fe896 ed4d10b9 660cd6e3 6c398bdd
    x_2 =
    7 a53af799 5d9b4e28 8a12d0c9 bb9dae71 9625d3c3
    x_3 =
    4 6d0ed674 6bfff7dd f5b93ab2 88c98b98 c3079c7f
    ax2 =
    6 57cad86a 868d6842 d5d6000d d3b31e54 ef259be0
    left =
    3 3ac40e1e ed729f9f 206f3abf 5b7a95cc 2c22079f
    right =
    3 3ac40e1e ed729f9f 206f3abf 5b7a95cc 2c22079f

     
  • CG 1:18 pm on March 5, 2010 Permalink | Reply
    Tags: , is on curve, rosing, solving quadratic equation   

    More on testing points on curve 

    Have successfully tested two points:


    FIELD2N x = {0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000};
    FIELD2N y = {0x00000003, 0x477aaa32, 0xb86eae40, 0xa053e2a8, 0x0c4b05c3, 0x073f1c94};

    and


    FIELD2N x = {0x00000001, 0x00000002, 0x00000000, 0x00000000, 0x00000000, 0x00000000};
    FIELD2N y = {0x00000004, 0xc2e04f09, 0x7ec85acb, 0x386fc4f1, 0x526affe9, 0xf6e4d3f5};

    on curve

    poly_prime =
    8 0 0 0 0 c9
    data :
    1 1 0 0 0 0
    setting up curves

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

    point->x :
    1 1 0 0 0 0
    f :
    0 4000141 4000141 4000141 4000000 1f68
    point result
    x: 1 2 0 0 0 0
    y: 4 c2e04f09 7ec85acb 386fc4f1 526affe9 f6e4d3f5

    The result:

    poly_prime =
    8 0 0 0 0 c9

    NUMBITS = 163
    NUMWORD = 5
    MAXLONG = 6
    a2 =
    0 0 0 0 0 0
    a6 =
    1 0 0 0 0 0

    1 2 0 0 0 0
    y =
    4 c2e04f09 7ec85acb 386fc4f1 526affe9 f6e4d3f5
    yy =
    0 8a736b80 84a3b214 9d4c0808 d81f0825 8aecb069
    xy =
    0 8e736902 8ca3b710 8d4c0200 f81f0825 8aecaf01
    x_2 =
    1 20000000 64 80000000 0 15b
    x_3 =
    1 4000282 8000504 10000a08 20000000 1f68
    ax2 =
    0 0 0 0 0 0
    left =
    0 4000282 8000504 10000a08 20000000 1f68
    right =
    0 4000282 8000504 10000a08 20000000 1f68

    the left equation is equal to the right equation. It’s on curve. Yay!

    [what’s next? thinking.]

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

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

    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 9:19 pm on February 12, 2010 Permalink | Reply
    Tags: , , rosing   

    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!

     
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