ECC notes

ECC Brief

Q = kP can be expand as several of point doubling + point addition operation

"point doubling + point addition operation" can be expand as several field multiplication + field addition operation

Selection

Selection at the field level:

F2m, Fp, Fpm

poly basis / normal basis

Field arithmetic algorithm

Selection at the elliptic curve level:

affine coordinate / projective coordinate

point addition / double algorithm

protocol level:

appropriate protocol (key exchange / signature)

algorithm for kP

Fp

affine coordinate

projective coordinate - one is called Jacobin. 

Doubling: 2J -> J 4M, 3S

Mixed Coordinate : J+A -> J 8M + 3S

F2m

Field Addition - very simple and fast - just XOR

Field Multiplication - Shift and Add Method / Comb method -> field reduction / LSD (Least significant. digit serial) Multiplier method

Point Multiplication

Binary method: (m/2)PointAdd + (m) PointDouble

NAF method: (m/3) PointAdd + (m) PointDouble

Montgomery Multiplication: (6M+5S+3A)m + (1I+10M)

Message Protocol

Diffie Hellman Key Exchange (man-in-the-middle attack?):

PrC ·PuS =PrS ·PuC =PrS ·PrC ·G

Use same G (base point) and poly.

Server private key: PrS

Client private key: PrC

Server public key: PuS

Client public key: PuC

ECDSA: