/*
Example implementation of an Elliptic Curve over a Finite Field
By Jarl Ostensen, December 2007
jarl.ostensen@gmail.com
I wrote this because I wanted to understand more about Elliptic Curves and how they are
used in cryoptography. There's plenty of sources and articles out there but I didn't find anything that
condenced it all down to a "one pager" of code...
And as I completed this I thought others might want find it useful to help understand how ECC "works".
So, if you scroll all the way down to the bottom you'll find a symmmetric encryption example using
ECC that motivates pretty much all the code above it...
DISCLAIMERS:
* I obviously take no responsibility for any state secrets you might loose should
you actually *use* the code herein...
* I have written this as a fun little intellectual excercise - there might be mistakes, there might be bugs...
Main sources:
* Certicom: http://www.certicom.com/index.php?action=ecc,home
* Wikipedia
* Harry J. Smith's inverse-modulo implementation
http://www.geocities.com/hjsmithh/Numbers/InvMod.html
* Raju and Akbani: http://www.cs.utsa.edu/~rakbani/publications/Akbani-ECC-IEEESMC03.pdf
* Allardyce and Goyal: http://www.ece.tamu.edu/~reddy/ee689_04/pres_joel_nitesh.pdf
* Klaus Reinhard's ECC test page: http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.4.en.html
Developed using Dev-C++ version 4.9.9.2
http://www.bloodshed.net
*/
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
#include <math.h>
#include "FiniteFieldElement.hpp"
namespace Cryptography
{
/*
Elliptic Curve over a finite field of order P:
y^2 mod P = x^3 + ax + b mod P
NOTE: this implementation is simple and uses normal machine integers for its calculations.
No special "big integer" manipulation is supported so anything _big_ won't work.
However, it is a complete finite field EC implementation in that it can be used
to learn and understand the behaviour of these curves and in particular to experiment with them
for their use in cryptography
Template parameter P is the order of the finite field Fp over which this curve is defined
*/
template<int P>
class EllipticCurve
{
public:
// this curve is defined over the finite field (Galois field) Fp, this is the
// typedef of elements in it
typedef FiniteFieldElement<P> ffe_t;
/*
A point, or group element, on the EC, consisting of two elements of the field FP
Points can only created by the EC instance itself as they have to be
elements of the group generated by the EC
*/
class Point
{
friend class EllipticCurve<P>;
typedef FiniteFieldElement<P> ffe_t;
ffe_t x_;
ffe_t y_;
EllipticCurve *ec_;
// core of the doubling multiplier algorithm (see below)
// multiplies acc by m as a series of "2*acc's"
void addDouble(int m, Point& acc)
{
if ( m > 0 )
{
Point r = acc;
for ( int n=0; n < m; ++n )
{
r += r; // doubling step
}
acc = r;
}
}
// doubling multiplier algorithm
// multiplies a by k by expanding in multiplies by 2
// a is also an accumulator that stores the intermediate results
// between the "1s" of the binary form of the input scalar k
Point scalarMultiply(int k, const Point& a)
{
Point acc = a;
Point res = Point(0,0,*ec_);
int i = 0, j = 0;
int b = k;
while( b )
{
if ( b & 1 )
{
// bit is set; acc = 2^(i-j)*acc
addDouble(i-j,acc);
res += acc;
j = i; // last bit set
}
b >>= 1;
++i;
}
return res;
}
// adding two points on the curve
void add(ffe_t x1, ffe_t y1, ffe_t x2, ffe_t y2, ffe_t & xR, ffe_t & yR) const
{
// special cases involving the additive identity
if ( x1 == 0 && y1 == 0 )
{
xR = x2;
yR = y2;
return;
}
if ( x2 == 0 && y2 == 0 )
{
xR = x1;
yR = y1;
return;
}
if ( y1 == -y2 )
{
xR = yR = 0;
return;
}
// the additions
ffe_t s;
if ( x1 == x2 && y1 == y2 )
{
//2P
s = (3*(x1.i()*x1.i()) + ec_->a()) / (2*y1);
xR = ((s*s) - 2*x1);
}
else
{
//P+Q
s = (y1 - y2) / (x1 - x2);
xR = ((s*s) - x1 - x2);
}
if ( s != 0 )
{
yR = (-y1 + s*(x1 - xR));
}
else
{
xR = yR = 0;
}
}
Point(int x, int y)
: x_(x),
y_(y),
ec_(0)
{}
Point(int x, int y, EllipticCurve<P> & EllipticCurve)
: x_(x),
y_(y),
ec_(&EllipticCurve)
{}
Point(const ffe_t& x, const ffe_t& y, EllipticCurve<P> & EllipticCurve)
: x_(x),
y_(y),
ec_(&EllipticCurve)
{}
public:
static Point ONE;
// copy ctor