Hello Everybody,
IS there anyone in this forum who have worked on Elliptic curve cryptosystem/cryptograpgy?
I want to discuss something regarding ECDSA, i have perfectly implemented ECDH and have a problem in implementing ECDSA.
Regards!
khanalone1 -4 Newbie Poster
kolosick.m188 2 Junior Poster in Training
I have experience with ECC. What exactly is the problem with ECDSA?
Edited by kolosick.m188 because: n/a
khanalone1 -4 Newbie Poster
I am posting my program with attachement.
as ECDH is working and i want to use ECDSA in this program
Kindly download these attachements and rename FiniteFieldElement1.txt to FiniteFieldElement1.hpp
Hope this might help you understand our probelm
Regards!
namespace CryptographyOnSensor
{
// helper functions
namespace detail
{
//From Knuth; Extended GCD gives g = a*u + b*v
int EGCD(int a, int b, int& u, int &v)
{
u = 1;
v = 0;
int g = a;
int u1 = 0;
int v1 = 1;
int g1 = b;
while (g1 != 0)
{
int q = g/g1; // Integer divide
int t1 = u - q*u1;
int t2 = v - q*v1;
int t3 = g - q*g1;
u = u1; v = v1; g = g1;
u1 = t1; v1 = t2; g1 = t3;
}
return g;
}
int InvMod(int x, int n) // Solve linear congruence equation x * z == 1 (mod n) for z
{
//n = Abs(n);
x = x % n; // % is the remainder function, 0 <= x % n < |n|
int u,v,g,z;
g = EGCD(x, n, u,v);
if (g != 1)
{
// x and n have to be relative prime for there to exist an x^-1 mod n
z = 0;
}
else
{
z = u % n;
}
// cout << endl << "z= " <<z;
// system("pause");
return z;
}
}
/*
An element in a Galois field FP
Adapted for the specific behaviour of the "mod" function where (-n) mod m returns a negative number
Allows basic arithmetic operations between elements:
+,-,/,scalar multiply
The template argument P is the order of the field
*/
template<int P>
class FiniteFieldElement
{
int i_;
void assign(int i)
{
i_ = i;
if ( i<0 )
{
// ensure (-i) mod p correct behaviour
// the (i%P) term is to ensure that i is in the correct range before normalizing
i_ = (i%P) + 2*P;
}
i_ %= P;
}
public:
// ctor
FiniteFieldElement()
: i_(0)
{}
// ctor
explicit FiniteFieldElement(int i)
{
assign(i);
}
// copy ctor
FiniteFieldElement(const FiniteFieldElement<P>& rhs)
: i_(rhs.i_)
{
}
// access "raw" integer
int i() const { return i_; }
// negate
FiniteFieldElement operator-() const
{
return FiniteFieldElement(-i_);
}
// assign from integer
FiniteFieldElement& operator=(int i)
{
assign(i);
return *this;
}
// assign from field element
FiniteFieldElement<P>& operator=(const FiniteFieldElement<P>& rhs)
{
i_ = rhs.i_;
return *this;
}
// *=
FiniteFieldElement<P>& operator*=(const FiniteFieldElement<P>& rhs)
{
i_ = (i_*rhs.i_) % P;
return *this;
}
// ==
friend bool operator==(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
{
return (lhs.i_ == rhs.i_);
}
// == int
friend bool operator==(const FiniteFieldElement<P>& lhs, int rhs)
{
return (lhs.i_ == rhs);
}
// !=
friend bool operator!=(const FiniteFieldElement<P>& lhs, int rhs)
{
return (lhs.i_ != rhs);
}
// a / b
friend FiniteFieldElement<P> operator/(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
{
// cout<<lhs.i_ * detail::InvMod(rhs.i_,P);
// system("pause");
return FiniteFieldElement<P>( lhs.i_ * detail::InvMod(rhs.i_,P));
}
// a + b
friend FiniteFieldElement<P> operator+(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
{
return FiniteFieldElement<P>( lhs.i_ + rhs.i_);
}
// a - b
friend FiniteFieldElement<P> operator-(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
{
return FiniteFieldElement<P>( lhs.i_ - rhs.i_);
}
// a + int
friend FiniteFieldElement<P> operator+(const FiniteFieldElement<P>& lhs, int i)
{
return FiniteFieldElement<P>( lhs.i_+i);
}
// int + a
friend FiniteFieldElement<P> operator+(int i, const FiniteFieldElement<P>& rhs)
{
// cout<<rhs.i_+i;
// system("pause");
return FiniteFieldElement<P>( rhs.i_+i);
}
// int * a
friend FiniteFieldElement<P> operator*(int n, const FiniteFieldElement<P>& rhs)
{
// cout << n*rhs.i_;
// system("pause");
return FiniteFieldElement<P>( n*rhs.i_);
}
// a * b
friend FiniteFieldElement<P> operator*(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
{
return FiniteFieldElement<P>( lhs.i_ * rhs.i_);
}
// ostream handler
template<int T>
friend ostream& operator<<(ostream& os, const FiniteFieldElement<T>& g)
{
return os << g.i_;
}
};
}The attachment preview is chopped off after the first 10 KB. Please download the entire file.
/*
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 <iomanip>
#include <vector>
#include <ctime>
#include <time.h>
#include <conio.h>
//#include <time>
using namespace std;
using std::ios;
const int SIZEOFELLIPTICCURVE=163;
#include <math.h>
#include "FiniteFieldElement1.hpp"
namespace CryptographyOnSensor
{
/*
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
*/
// class SensorNode
// {
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
// cout <<"\nValues of points: (x1, y1) (" << x1 << " ," << y1 << ") (x2, y2) (" << x2 << ", " << y2 <<")";
// cout <<(3*(x1.i()*x1.i())+ec_->a());
//// system("pause");
s = (3*(x1.i()*x1.i()) + ec_->a()) / (2*y1);
// cout <<"s: " << s<<endl;
// system("pause");
xR = ((s*s) - 2*x1);
// cout <<"xR: "<< xR <<endl;
// system("pause");
}
else
{
//P+Q
s = (y1 - y2) / (x1 - x2);
xR = ((s*s) - x1 - x2);
}
if ( s != 0 )
{
yR = (-y1 + s*(x1 - xR));
// cout << "yR: " <<yR <<endl;
// system("pause");
}
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
Point() {}
static Point Convert (ffe_t c1, ffe_t c2)
{
Point p;
p.x_=c1;
p.y_=c2;
return(p);
}
Point(const Point& rhs)
{
x_ = rhs.x_;
y_ = rhs.y_;
ec_ = rhs.ec_;
}
// assignment
Point& operator=(const Point& rhs)
{
x_ = rhs.x_;
y_ = rhs.y_;
ec_ = rhs.ec_;
return *this;
}
void output(void)
{
cout << "\nx= " <<x_ << "\ty= " << y_ <<endl;
system("pause");
}
// access x component as element of Fp
ffe_t x() const { return x_; }
// access y component as element of Fp
ffe_t y() const { return y_; }
// calculate the order of this point by brute-force additions
// WARNING: this can be VERY slow if the period is long and might not even converge
// so maxPeriod should probab Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.