• User routines
• System routines
• Group routines
• Examples

Elliptic Curve Cryptography

Pauline Hong

Duke University

pauline.hong@duke.edu

www.duke.edu/~ph6

To see how to use this program, see the example at the end of this worksheet.

To see how this program works, see the accompanying paper.

User routines

>

init_receiver := proc()    local   G,g,h,kappa,n;    global  Privkey,Pubkey;    Privkey := 1309500873854749099831268309457391717722850279;    G := [-3,          2455155546008945908945579827824778998937758030093070285253,          6277101735386680763835789423207666416083908700390324961279];    g := [602046843592854700404561654781648738821600320709046855698,          1580573966983949753944652941399918970627913726427538969730];    h := giop(G,g,Privkey);    kappa := 2^8;    n := floor(evalf((log[2](G[3])-log[2](kappa))/8))-1;    Pubkey := [G,g,h,kappa,n]; end:

>	send_message := proc(T)    local   S,s,C,x,p,c;    S := split(T);    C := [];    for s in S do       x := text_to_num(s);       p := num_to_point(x);       c := encrypt(p);       C := [op(C),c];    od;    return C; end:

>	receive_message := proc(C)    local   T,c,p,x,t;    T := "";    for c in C do       p := decrypt(c);       x := point_to_num(p);       t := num_to_text(x);       T := cat(T,t);    od;    return T; end:

System routines

>

split := proc(T)    local   n,num_parts,pieces,i;    global  Pubkey;    n         := Pubkey[5];    num_parts := floor(length(T)/n);    pieces := [];    for i from 0 to (num_parts-1)*n by n do       pieces := [op(pieces),substring(T,i+1..i+n)];    od;    if (length(T)/n - num_parts) > 0 then       pieces := [op(pieces),substring(T,num_parts*n+1..length(T))];    end;    return pieces; end:

>	text_to_num := proc(t)    local   tb,x,i;    tb := convert(t,'bytes');    x := 0;    for i from length(t) to 1 by -1 do       x := x*2^8 + tb[i];    od;    return x; end:

>	num_to_text := proc(x)    local   n,xb,tb,i,t;    global  Pubkey;    n := Pubkey[5];    xb := x;    tb := [];    for i from 1 to n do       xb := iquo(xb,2^8,'r');       tb := [op(tb),r];    od;    t := convert(tb,'bytes');    return t; end:

>

num_to_point := proc(x)    local   a,b,p,xp,c,yp,G,kappa;    global  Pubkey;    G := Pubkey[1];    a := G[1];    b := G[2];    p := G[3];    kappa := Pubkey[4];    for xp from kappa*x to kappa*(x+1)-1 do       c := xp^3 + a*xp + b mod p;       yp := numtheory[msqrt](c,p);       if yp <> FAIL then          return [xp,yp];       fi;    od;    print("Very unlikely thing happened!!!           You need to increase kappa value.");    return FAIL; end:

>	point_to_num := proc(p)    local   kappa;    global  Pubkey;    kappa := Pubkey[4];    return floor(p[1]/kappa); end:

>	encrypt := proc(p)    local   G,g,h,genrand,s,c1,c2,c;    global  Pubkey;    G := Pubkey[1];    g := Pubkey[2];    h := Pubkey[3];    genrand := rand(2..10);    s  := genrand();    c1 := giop(G,g,s);    c2 := gop(G,giop(G,h,s),p);    c  := [c1,c2];    return c; end:

>	decrypt := proc(c)    local   G;    global  Privkey,Pubkey;    G := Pubkey[1];    return gop(G,giop(G,ginv(G,c[1]),Privkey),c[2]); end:

Group routines

>	giop := proc(G,A,k)    local   kp,Ap,r;    if k = 0 then       return 0;    fi;    kp := iquo(k,2,'r');    Ap := giop(G,A,kp);    if r = 0 then       return gop(G,Ap,Ap);    else       return gop(G,A,gop(G,Ap,Ap));    fi; end:

>	giop_slow := proc(G,A,k)    local   B,i;    B := 0;    for i from 1 to k do       B := gop(G,A,B);    od;    return B; end:

>

gop := proc(G,A,B)    local   a,b,p,xA,yA,xB,yB,xC,yC,C,slope;    a := G[1];    b := G[2];    p := G[3];    if A = 0 then       return B;    fi;    if B = 0 then       return A;    fi;    xA := A[1];    yA := A[2];    xB := B[1];    yB := B[2];    if (xA - xB) mod p = 0 and (yA + yB) mod p = 0 then       return 0;    fi;          if (xA - xB) mod p = 0 and (yA - yB) mod p = 0 then       slope := (3*xA^2 + a) / (2*yA) mod p;    else       slope := (yA - yB) / (xA - xB) mod p;    fi;    xC := slope^2 - xA - xB mod p;    yC := -yA + slope*(xA - xC) mod p;    C := [xC,yC];    return C; end:

>	ginv := proc(G,A)    local   p;    p := G[3];    if A = 0 then       return 0;    fi;    return [A[1],-A[2] mod p]; end:

Examples

>	init_receiver():

>

sent := "The urge to discover secrets is deeply ingrained in human nature; even the least curious mind is roused by the promise of sharing knowledge withheld from others. Some are fortunate enough to find a job which consists of the solution of mysteries, but most of us are driven to sublimate this urge by the solving of artificial puzzles designed for our entertainment. Detective stories or crossword puzzles cater for the majority; the solution of secret codes may be the pursuit of the few. (John Chadwick from The Decipherment of Linear B, as quoted in The Code Book, by Simon Singh)":

>	encrypted := send_message(sent);

>	received := receive_message(encrypted);

>	StringTools[Compare](sent,received);

Disclaimer:  While every effort has been made to validate the solutions in this worksheet, Waterloo Maple Inc. and the contributors are not responsible for any errors contained and are not liable for any damages resulting from the use of this material.