ncurve.cpp

ecppki-cpp curve

  }
}

void field::sqrt( const poly a, poly b )
{
  // b = a^( 2^(M-1) );
  copy(a,b);
  unsigned i = M-1;
  while (i--)
  {
    field::poly t1;
    square(b,t1);
    reduce(t1);
    copy(t1,b);
  }
}

vlong field::pack( const poly a )
{
  vlong result;
  unsigned i=a[0];
  while (i)
  {
    result = ( result << L ) + a[i];
    i -= 1;
  }
  return result;
}

void field::unpack( const vlong & X, poly a )
{
  vlong x = X;
  unsigned n = 0;
  while ( x != 0 )
  {
    n += 1;
    a[n] = to_unsigned( x & BASE_M1 );
    x >>= L;
  }
  a[0] = n;
}

point::point()
{
  c = 0;
}

point::point( curve * C ) : x(C), y(C)
{
  c = C;
}

point::point( const point & P )
{
  c = P.c;
  x = P.x;
  y = P.y;
}

point operator * ( const vlong & k, const point & P )
{
  point result( P.c );
  P.c->mul( P, k, result );
  return result;
}

point point::operator + ( const point &P ) const
{
  point result(P.c);
  c->add( *this, P, result );
  return result;
}

point point::operator - ( const point & P ) const
{
  point result(P.c);
  c->sub( *this, P, result );
  return result;
}

point & point::operator = ( const point & P )
{
  c = P.c;
  x = P.x;
  y = P.y;
  return *this;
}

vlong curve::to_vlong( const point & P )
{
  return P.c->field::pack( P.x.v );
}

vlong curve::pack( const point & P )
{
  vlong result = 0;
  if ( P.x.v[0] )
  {
    result = to_vlong(P);
    result = result * 2 + ybit( P.y/P.x );
  }
  else if ( P.y.v[0] )
    result = 1;
  else
    result = 0;
  return result;
}

point curve::unpack( const vlong & X )
{
  vlong x = X;
  unsigned yb = to_unsigned( x & 1 ); x >>= 1;
  point R( this );
  field::unpack( x, R.x.v );
  if ( R.x.v[0] || yb )
    calc_y( R, yb ); // will return 1 provided X is valid
  else
    R.y = R.x; // zero
  return R;
}

int curve::MOV( unsigned B, const vlong & q, const vlong & r )
{
  vlong x = 1;
  for (unsigned i=1;i<B;i+=1)
  {
    x = ( x*q ) % r;
    if ( x == 1 )
      return 0; // what a pity ...
  }
  return 1;
}

vlong curve::small_lucas( vlong P, vlong Z, unsigned ik )
{
  vlong V0 = 2;
  vlong V1 = P;
  while ( ik > 1 )
  {
    vlong V2 = P*V1 - Z*V0;
    V0 = V1;
    V1 = V2;
    ik -= 1;
  }
  return V1;
}

#if use_field_op

void curve::sub( const point & P, const point & Q, point & R )
{
  point t1 = Q;
  t1.y = t1.y + t1.x;
  add( P, t1, R );
}

void curve::add( const point & P, const point & Q, point & R )
{
  if ( P.x == 0 && P.y == 0 )
    R = Q;
  else if ( Q.x == 0 && Q.y == 0 )
    R = P;
  else
  {
    if ( P.x == Q.x )
    {
      if ( P.y == Q.y ) // points are equal
      {
        field_element LD = P.x + P.y/P.x;
        R.x = sq(LD) + LD /*+ a*/;
        R.y = sq(P.x) + LD*R.x + R.x;
      }
      else // must be inverse - result is zero
      {
        R.x.v[0] = 0;
        R.y.v[0] = 0;
      }
    }
    else // P,Q are distinct, non-zero, and P != -Q
    {
      field_element LD = ( P.y + Q.y ) / ( P.x + Q.x );
      R.x = sq(LD) + LD + P.x + Q.x /*+ a*/;
      R.y = LD*(P.x+R.x) + R.x + P.y;
    }
  }
}

#else

// optimised version - about 5% faster ?
// could still do better

void curve::sub( const point & P, const point & Q, point & R )
{
  point t1;
  t1.c = this;
  copy( Q.x.v, t1.x.v );
  field::add( Q.x.v, Q.y.v, t1.y.v );
  add( P, t1, R );
}

void curve::add( const point & P, const point & Q, point & R )
{
  if ( P.x.v[0] + P.y.v[0] == 0 )
    R = Q;
  else if ( Q.x.v[0] + Q.y.v[0] == 0 )
    R = P;
  else
  {
    field::poly LD,t1,t2,t3;
    field::add( P.x.v, Q.x.v, t1 );
    if ( t1[0] == 0 )
    {
      if ( equal( P.y.v, Q.y.v ) ) // points are equal
      {
        // field_element LD = P.x + P.y/P.x;
        inverse( P.x.v, t1 );
        field::mul( t1, P.y.v, t2 ); reduce( t2 );
        field::add( t2, P.x.v, LD );
        // R.x = sq(LD) + LD /*+ a*/;
        square( LD, t1 ); reduce( t1 );
        field::add( t1, LD, R.x.v );
        // R.y = sq(P.x) + LD*R.x + R.x;
        square( P.x.v, t1 );
        field::mul( LD, R.x.v, t2 );
        field::add( t1, t2, t3 );
        reduce( t3 );
        field::add( t3, R.x.v, R.y.v );
      }
      else // must be inverse - result is zero
      {
        R.x.v[0] = 0;
        R.y.v[0] = 0;
      }
    }
    else // P,Q are distinct, non-zero, and P != -Q
    {
      //field_element LD = ( P.y + Q.y ) / ( P.x + Q.x );
      inverse( t1, t2 );
      field::add( P.y.v, Q.y.v, t1 );
      field::mul( t1, t2, LD ); reduce(LD);
      //R.x = sq(LD) + LD + P.x + Q.x /*+ a*/;
      square( LD, t1 ); reduce( t1 );
      field::add( t1, LD, t2 );
      field::add( t2, P.x.v, t1 );
      field::add( t1, Q.x.v, R.x.v );
      //R.y = LD*(P.x+R.x) + R.x + P.y;
      field::add( P.x.v, R.x.v, t1 );
      field::mul( LD, t1, t2 ); reduce( t2 );
      field::add( t2, R.x.v, t1 );
      field::add( t1, P.y.v, R.y.v );
    }
  }
}

#endif

point curve::random_point()
{
  point R(this);
  do
    field::set_random(R.x.v);
  while ( calc_y(R) == 0 );
  return R;
}

int curve::calc_y( point & R, unsigned yb )
{
  if ( R.x.v[0] == 0 )
    sqrt( b.v, R.y.v );
  else
  {
    field_element alpha = sq(R.x) * ( R.x /*+ a*/ ) + b;
    R.y.v[0] = 0;
    if ( alpha.v[0] != 0 )
    {
      field_element t1(this);
      field_element beta = alpha/sq(R.x);
      if ( trace(beta.v) != 0 ) return 0;
      quad_solve(beta.v,t1.v);
      assert( t1*t1 + t1 == beta );
      if ( ybit(t1) != yb )
        t1.v[1] ^= 1;
      R.y = R.x * t1;
    }
  }
  assert( sq(R.y) + R.x*R.y == R.x*R.x*R.x + b );
  return 1;
}

void curve::mul( const point & P, const vlong & x, point & Q )
{
  vlong h = x*3;
  Q.x.v[0] = 0;
  Q.y.v[0] = 0;

  point R = P;

  unsigned r = h.bits()-1; // so h.bit(r)==1
  unsigned i=1;
  while (1)
  {
    int hi = h.bit(i);
    int ai = x.bit(i);
    if ( hi == 1 && ai == 0 )
      Q = Q + R;
    if ( hi == 0 && ai == 1 )
      Q = Q - R;
    if ( i == r ) break;
    i += 1;
    R = R+R;
  }
}

curve::curve( full_curve_parameter & a ) : field( a )
{
  b.f = this;
  b.v[0] = 1;
  b.v[1] = a.b;

  unsigned SQRT_BASE = 1u<<((a.L+1)/2); // upper bound
  unsigned so_min = BASE - 2*SQRT_BASE;
  unsigned so = so_min + 2*a.nso;
  vlong sf = so * a.ntf;

  p = a.p0;
  if (p==0)
  {
    vlong Z = pow2(L);
    p = pow2(M) + 1 - small_lucas( Z-(so-1), Z, K );
    p = p / sf;
    a.p0 = p;
  }
  assert( is_probable_prime(p) && MOV( M/8, pow2(M), p ) );

  if (a.P0==0)
  {
    prng = 0; // to make sure P is reproducible
    do PP = sf * random_point();
      while ( PP.x.v[0]+PP.y.v[0] == 0 );
    a.P0 = pack(PP);
  }
  else
    PP = unpack(a.P0);

  #if assert_on
    point t2 = p*PP;
    assert( t2.x.v[0] + t2.y.v[0] == 0 ); // fingers crossed!
  #endif
};

full_curve_parameter::full_curve_parameter( const curve_parameter & bp )
{
  L = bp.L;
  K = bp.K;
  T = bp.T;
  root = bp.root;
  b = bp.b;
  nso = bp.nso;
  ntf = bp.ntf;
  p0 = 0;
  P0 = 0;
  tm = 0;
}

vlong ec_crypt::make_private_key()
{
  vlong x;
  while ( x < p )
    x = (x << 15) + rand(1u<<15);
  x = 2 + x % (p-3);
  return x;
}

vlong ec_crypt::make_public_key( const vlong & private_key )
{
  return pack( private_key * PP );
}

vlong ec_crypt::make_secret( const vlong & public_key, vlong & message )
{
  vlong sr = make_private_key();
  message = pack( sr * PP );
  return to_vlong( sr * unpack(public_key) );
}

vlong ec_crypt::decode_secret( const vlong & private_key, const vlong & message )
{
  point D = private_key * unpack(message);
  return to_vlong(D);
}

pair ec_crypt::nr_sign( const vlong & data, const vlong & private_key )
{
  pair sig;
  vlong k;
  do
  {
    k = make_private_key();
    vlong z = to_vlong( k*PP );
    sig.r = ( z + data ) % p;
  } while ( sig.r==0 );
  sig.s = ( k - private_key * sig.r ) % p; if ( sig.s < 0 ) sig.s += p;
  return sig;
}

vlong ec_crypt::nr_verify( const pair & sig, const vlong & public_key )
{
  vlong bz = to_vlong( sig.s * PP + sig.r * unpack(public_key) );
  vlong data = ( sig.r - bz ) % p; if ( data < 0 ) data += p;
  return data;
}

pair ec_crypt::dsa_sign( const vlong & data, const vlong & private_key )
{
  pair sig;
  vlong k;
  do
  {
    k = make_private_key();
    vlong z = to_vlong( k*PP );
    sig.r = z % p;
  } while ( sig.r==0 );
  sig.s = (modinv(k,p) * ( data + (private_key * sig.r)%p )) % p;
  return sig;
}

int ec_crypt::dsa_verify( const vlong & e, const pair & sig, const vlong & public_key )
{
  if ( sig.r < 1 || sig.r >= p || sig.s < 1 || sig.s >= p )
    return 0;
  vlong c = modinv(sig.s,p);
  vlong u1 = ( e*c ) % p;
  vlong u2 = ( sig.r*c ) % p;
  vlong z = to_vlong( u1 * PP + u2 * unpack(public_key) ) % p;
  return z == sig.r;
}

ec_crypt::ec_crypt( full_curve_parameter & a )
: curve( a ), bits( p.bits() )
{
}