jacobi.cc

/*
 * Copyright 2003 Michael A. Marsh, Cornell University. All rights reserved.
 * This software is released under the modified BSD license.
 * See the file LICENSE in the top-level directory for details.
 */
//
// $Id: jacobi.cc,v 1.3 2004/05/19 15:56:48 mmarsh Exp $
//
// $Log: jacobi.cc,v $
// Revision 1.3  2004/05/19 15:56:48  mmarsh
// *** empty log message ***
//
// Revision 1.2  2003/11/04 22:31:48  mmarsh
// *** empty log message ***
//
//

#include "jacobi.h"
#include "CODEX_Exceptions/BignumExceptions.h"

using namespace CODEX_Ciphers;

BIGNUM *
CODEX_Ciphers::jacobi( const BIGNUM * a, const BIGNUM * n )
{
   static BIGNUM * zero     = 0;
   static BIGNUM * one      = 0;
   static BIGNUM * minusOne = 0;
   static BIGNUM * three    = 0;
   static BIGNUM * four     = 0;
   static BIGNUM * five     = 0;
   static BIGNUM * seven    = 0;
   static BIGNUM * eight    = 0;

   // Set up the constants we'll need.
   if ( 0 == zero )
   {
      zero = BN_new();
      if ( 0 == zero )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      if ( ! BN_zero( zero ) )
      {
         BN_free( zero );
         zero = 0;
         throw CODEX_Exceptions::BignumSetWordException( __FILE__ , __LINE__ );
      }
   }

   if ( 0 == one )
   {
      one = BN_new();
      if ( 0 == one )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      if ( ! BN_one( one ) )
      {
         BN_free( one );
         one = 0;
         throw CODEX_Exceptions::BignumSetWordException( __FILE__ , __LINE__ );
      }
   }

   if ( 0 == minusOne )
   {
      minusOne = BN_new();
      if ( 0 == minusOne )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      if ( ! BN_sub( minusOne, zero, one ) )
      {
         BN_free( minusOne );
         minusOne = 0;
         throw CODEX_Exceptions::BignumSubException( __FILE__ , __LINE__ );
      }
   }

   if ( 0 == four )
   {
      four = BN_new();
      if ( 0 == four )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      if ( ! BN_lshift( four, one, 2 ) )
      {
         BN_free( four );
         four = 0;
         throw CODEX_Exceptions::BignumLshiftException( __FILE__ , __LINE__ );
      }
   }

   if ( 0 == three )
   {
      three = BN_new();
      if ( 0 == three )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      if ( ! BN_sub( three, four, one ) )
      {
         BN_free( three );
         three = 0;
         throw CODEX_Exceptions::BignumSubException( __FILE__ , __LINE__ );
      }
   }

   if ( 0 == five )
   {
      five = BN_new();
      if ( 0 == five )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      if ( ! BN_add( five, four, one ) )
      {
         BN_free( five );
         five = 0;
         throw CODEX_Exceptions::BignumAddException( __FILE__ , __LINE__ );
      }
   }

   if ( 0 == seven )
   {
      seven = BN_new();
      if ( 0 == seven )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      if ( ! BN_add( seven, four, three ) )
      {
         BN_free( seven );
         seven = 0;
         throw CODEX_Exceptions::BignumAddException( __FILE__ , __LINE__ );
      }
   }

   if ( 0 == eight )
   {
      eight = BN_new();
      if ( 0 == eight )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      if ( ! BN_lshift( eight, one, 3 ) )
      {
         BN_free( eight );
         eight = 0;
         throw CODEX_Exceptions::BignumLshiftException( __FILE__ , __LINE__ );
      }
   }

   // Now the algorithm
   if ( 0 == BN_cmp( a, zero ) )
   {
      return BN_dup( zero );
   }
   if ( 0 == BN_cmp( a, one ) )
   {
      return BN_dup( one );
   }

   // Simple tests on inputs
   if ( BN_cmp( n, three ) < 0 )
   {
      return 0;
   }
   if ( ! BN_is_odd( n ) )
   {
      return 0;
   }
   if ( BN_cmp( a, zero ) < 0 )
   {
      return 0;
   }
   if ( BN_cmp( a, n ) >= 0 )
   {
      return 0;
   }

   BIGNUM * a1   = 0;
   BIGNUM * n1   = 0;
   BIGNUM * s    = 0;
   BIGNUM * temp = 0;
   BN_CTX * ctx  = 0;
   try
   {
      ctx = BN_CTX_new();
      if ( 0 == ctx )
      {
         throw CODEX_Exceptions::BignumContextException( __FILE__ , __LINE__ );
      }

      temp = BN_new();
      if ( 0 == temp )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }

      unsigned long e = 0;
      a1 = BN_dup( a );
      if ( 0 == a1 )
      {
         throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
      }
      while ( ! BN_is_odd( a1 ) )
      {
         if ( ! BN_rshift( a1, a1, 1 ) )
         {
            throw CODEX_Exceptions::BignumRshiftException( __FILE__ ,
                                                           __LINE__ );
         }
         ++e;
      }

      if ( 0 == (e%2) )
      {
         s = BN_dup( one );
      }
      else
      {
         if ( ! BN_mod( temp, n, eight, ctx ) )
         {
            throw CODEX_Exceptions::BignumModException( __FILE__ , __LINE__ );
         }

         if ( ( 0 == BN_cmp( temp, one ) ) ||
              ( 0 == BN_cmp( temp, seven ) ) )
         {
            s = BN_dup( one );
         }
         else
         {
            s = BN_dup( minusOne );
         }
      }

      if ( ! BN_mod( temp, n, four, ctx ) )
      {
         throw CODEX_Exceptions::BignumModException( __FILE__ , __LINE__ );
      }
      if ( 0 == BN_cmp( temp, three ) )
      {
         if ( ! BN_mod( temp, a1, four, ctx ) )
         {
            throw CODEX_Exceptions::BignumModException( __FILE__ , __LINE__ );
         }
         if ( 0 == BN_cmp( temp, three ) )
         {
            if ( ! BN_sub( s, zero, s ) )
            {
               throw CODEX_Exceptions::BignumSubException( __FILE__ ,
                                                           __LINE__ );
            }
         }
      }
      BN_free(temp);  temp = 0;

      BIGNUM * retVal;
      if ( 0 == BN_cmp( a1, one ) )
      {
         retVal = BN_dup( one );
      }
      else
      {
         n1 = BN_new();
         if ( 0 == n1 )
         {
            throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
         }
         if ( ! BN_mod( n1, n, a1, ctx ) )
         {
            throw CODEX_Exceptions::BignumModException( __FILE__ , __LINE__ );
         }
         temp = jacobi( n1, a1 );
         if ( 0 == temp )
         {
            throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
         }
         if ( ! BN_mul( s, s, temp, ctx ) )
         {
            throw CODEX_Exceptions::BignumMulException( __FILE__ , __LINE__ );
         }
         retVal = BN_dup( s );
      }

      BN_CTX_free( ctx );
      BN_free( temp );
      BN_free( a1 );
      BN_free( n1 );
      BN_free( s );

      return retVal;
   }
   catch ( ... )
   {
      if ( 0 != a1   ) BN_free( a1 );
      if ( 0 != n1   ) BN_free( n1 );
      if ( 0 != s    ) BN_free( s );
      if ( 0 != temp ) BN_free( temp );
      if ( 0 != ctx  ) BN_CTX_free( ctx );
      throw;
   }
}

---