http://www.cryptoman.com/elliptic.htm

curve: (x,y) satisfying  y^2=x^3+a*x+b

=======
addition rule for x and y in R

draw a straight line through  P and Q, and find the third intersection with the curve. R.

then P + Q + R = 0   ( the identity element )

algebraicly:
  (x3,y3) = (x1,y1) + (x2,y2)

  x3 = s^2 - x1-x2
  y3 = y1+s*(x3-x1)
  s = (y1-y2)/(x1-x2)

when (x1,y1) == (x2,y2)
  s = (3*x1^2-a)/(2*y1)
  x3 = s^2 - 2*x1
  y3 = y1 + s*(x3-y1)

when (x1,y1) == (x2,-y2)
     -> (x3,y3) = (0,0)

what is the division in the calc of 's' ? ... mod inverse probably.
 
 
=======
addition rule for x and y in GF(p)

(x3,y3) = (x1,y1) + (x2,y2)

when (x1,y1) != (x2,y2)
      x3= L^2 - x1 - x2
      y3= L*(x1-x3) - y1
      L= (y1-y2)/(x2-x1)

when (x1,y1) == (x2,y2)
      x3 = L^2-2*x1
      y3 = L*(x1-x3)-y1
      L=(3*x1^2+a)/(2*y1)

when (x1,y1) == (x2,-y2)
     x3 = y3 = 0

when (x1,y1) = (0,0)  -> (x3,y3)= (x2,y2)

=======
addition rule for x and y in GF(2^m)

when (x1,y1) != (x2,y2)
      x3= L^2 +L + x1 + x2 + a
      y3= L*(x1+x3) + x3 + y1
      L= (y1+y2)/(x2+x1)

when (x1,y1) == (x2,y2)
      x3 = L^2+L+a
      y3 = x1^2+(L+1)*x3
      L=x1+y1/x1

when (x1,y1+x1) == (x2,y2)
     x3 = y3 = 0

when (x1,y1) = (0,0)  -> (x3,y3)= (x2,y2)


=======
closure:
   show that if (x1,y1) and (x2,y2) are in C, than
   (x3,y3) = (x1,y1) ++ (x2,y2)  is also in C.


associativity
   show that  ( (x1,y1) ++ (x2,y2) ) ++ (x3,y3) == (x1,y1) ++ ( (x2,y2) ++ (x3,y3) )

identity
   show that E ++ (x,y) == (x,y) ++ E == (x,y)

inverse
   for each (x,y) and inverse exists (xi,yi) such that
      (x,y) ++ (xi,yi) == (xi,yi) ++ (x,y) == E

commutative
    (x1,y1) ++ (x2,y2) == (x2,y2) ++ (x1,y1)

=======

crypto:  ECC domain params are: p, a, b, G, n, h

prime field
GF(p)   : curve y^2    =x^3+a*x^2+b
    (a,b) such that 4*a^3+27*b^2 !=0
     why this restriction??  : it is the curve discriminant
     when it is 0, the curve has a singularity

binary field: with polynomial f(x)
GF(2^m) : curve y^2+x*y=x^3+a*x^2+b
    b!=0
binary curves are either 'Koblitz' or non-Koblitz

p is the prime modulus for GF(p)
  [ or for the 'binary case' : m and f, instead of p ]
a,b  are the curve parameters in y^2=x^3+a*x+b
G is the generator of the group
n is the order of G ( the smallest number such that n*G = 0 ), n must be prime
h = 'the cofactor'  h = floor((sqrt(p)+1)^2/n)


hasse theorem:  p+1-2*sqrt(p) <= n <= p+1+2*sqrt(p)

algorithms for calculating the curve order:
    - schoofs algorithm
    - wells algorithm
    - complex mult??


wells: order of curve(a,b) over GF(2^(L*K))

2^(L*K) + 1 - lucas( 2^L-(e-1), 2^L, K )

e = order of curve(a,b) over GF(2^L)

lucas(p,Z,K) = V(K), is defined by the recursion V(0) = 2; V(1) = p; V(K) = p·V(K-1) - Z·V(K-2)


todo: document how to solve y given an x for a curve.

-----------
keypair: d, Q
d is the privatekey, in interval [1,n-1]
Q is the publickey,  such that  Q = d * G

alice and bob have keypairs (dA,QA) and (dB,QB)
the shared key = (xk,yk) = dA*QB = dB*QA

unclear:  how do i do scalar multiplication over the curve?

probably  k*P  ( k = integer, P = curve point )
k = sum(b[i]*2^i, i=0 .. log2(k))

then k*P = sum(b[i]*2^i*P, i=0 .. log2(k))



=======
example GF(p) curve   P-112

p=(2^128-3)/76439

curve params:
a = 0x6127C24C05F38A0AAAF65C0EF02C
b = 0x51DEF1815DB5ED74FCC34C85D709

seed S=0x002757A1114D696E6768756151755316C05E0BD4
compressed G =   03:4BA30AB5E892B4E1649DD0928643
uncompressed G = 04:4BA30AB5E892B4E1649DD0928643:ADCD46F5882E3747DEF36E956E97
 -> Gx=0x4BA30AB5E892B4E1649DD0928643
 -> Gy=0xADCD46F5882E3747DEF36E956E97
Group order
n = 0x36DF0AAFD8B8D7597CA10520D04B
h = 0x04

cofactor = 1

=======
example GF(p) curve   P-192

p=2^192 - 2^64 - 1

curve params:
a=p-3
b = 0x64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1

generator:
  gx = 0x188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012
  gy = 0x07192B95FFC8DA78631011ED6B24CDD573F977A11E794811

Group order
n = 0xFFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831

cofactor = 1

======
koblitz curve: y^2+x*y=x^3+a*x^2+1  with a=0 or 1
   cofactor: a=1 -> f=2,    a=0 -> f=4
pseudo-random:  y^2+x*y=x^3+x^2+b
   cofactor: f=2

T=4
p(t)=t^163+t^7+t^6+t^3+1
example GF(2^m) curve  K-163
a=1
r=5846006549323611672814741753598448348329118574063     - what is 'r' ?
Polynomial Basis:
      G x =   2 fe13c053 7bbc11ac aa07d793 de4e6d5e 5c94eee8
      G y =   2 89070fb0 5d38ff58 321f2e80 0536d538 ccdaa3d9
Normal Basis:
      G x =   0 5679b353 caa46825 fea2d371 3ba450da 0c2a4541
      G y =   2 35b7c671 00506899 06bac3d9 dec76a83 5591edb2 

example GF(2^m) curve  B-163
r = 5846006549323611672814742442876390689256843201587 
Polynomial Basis:
b =   2 0a601907 b8c953ca 1481eb10 512f7874 4a3205fd
      G x =   3 f0eba162 86a2d57e a0991168 d4994637 e8343e36
      G y =   0 d51fbc6c 71a0094f a2cdd545 b11c5c0c 797324f1
Normal Basis:
s =   85e25bfe 5c86226c db12016f 7553f9d0 e693a268 
b =   6 645f3cac f1638e13 9c6cd13e f61734fb c9e3d9fb
      G x =   0 311103c1 7167564a ce77ccb0 9c681f88 6ba54ee8
      G y =   3 33ac13c6 447f2e67 613bf700 9daf98c8 7bb50c7f 


for scalar mult on a koblitz curve there is an efficient algorithm
http://74.125.77.132/search?q=cache:zKg3agekxk8J:csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.doc+elliptic+curve+B-163+Koblitz&cd=15&hl=nl&ct=clnk&gl=nl&client=firefox-a


K-113: f(x)=x^113+x^9+1

http://www.secg.org/index.php?action=secg,docs_secg
http://www.secg.org/download/aid-780/sec1-v2.pdf      - ec
http://www.secg.org/download/aid-386/sec2_final.pdf   - recommended EC domain params
http://www.secg.org/collateral/gec2.pdf               - test vectors for sec1


arxiv 0712.2022v1.pdf  - constructing elliptic curves of prime order