椭圆曲线加密解密模拟演示程序

/* 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