Combinatoric.h

/*
 * 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: Combinatoric.h,v 1.4 2005/01/21 19:44:18 mmarsh Exp $
//
// $Log: Combinatoric.h,v $
// Revision 1.4  2005/01/21 19:44:18  mmarsh
// Updated for compatibility with Doxygen 1.4.1
//
// Revision 1.3  2004/05/19 15:57:00  mmarsh
// *** empty log message ***
//
// Revision 1.2  2003/11/04 22:31:52  mmarsh
// *** empty log message ***
//
//

#ifndef __CODEX_VSS_COMBINATORIC_H__
#define __CODEX_VSS_COMBINATORIC_H__

#include <fstream>

#include "CODEX_ASN1/SecureBigNumber.h"
#include "CODEX_ASN1/Integer.h"
#include "CODEX_Exceptions/BignumExceptions.h"
#include "CODEX_Exceptions/FileExceptions.h"
#include "ShareFunctional.h"
#include "ShareSet.h"
#include "CombinatoricScenario.h"
#include "Range.h"

namespace CODEX_VSS
{
   template< int N , int T >
   struct choose
   {
         static const unsigned int value = N*choose<N-1,T-1>::value/T;
   };

   template< int N >
   struct choose<N,0>
   {
         static const unsigned int value = 1;
   };

   template< int N >
   struct choose<N,1>
   {
         static const unsigned int value = N;
   };

   template< unsigned int NumT , unsigned int ThreshT >
   class Combinatoric : public CODEX_ASN1::Base
   {
      public :
         typedef CODEX_ASN1::SecureBigNumber  ValueType;

         static const unsigned int NumShares = choose<NumT,ThreshT-1>::value+1;

         Combinatoric();

         Combinatoric( const Combinatoric<NumT,ThreshT>& aOther );

         Combinatoric( const ShareSet< Combinatoric<NumT,ThreshT> >& shareSet,
                       unsigned int partNum );

         virtual ~Combinatoric();

         void operator=( const Combinatoric<NumT,ThreshT>& aOther );

         void operator+=( const Combinatoric<NumT,ThreshT>& aOther );

         void setShare( unsigned int i,
                        const CODEX_ASN1::SecureBigNumber& share );

         const CODEX_ASN1::SecureBigNumber& share( unsigned int i ) const;

         unsigned int count() const;

         void apply( const ShareFunctional& func,
                     Combinatoric<NumT,ThreshT>& result ) const;

         void recover( CODEX_ASN1::SecureBigNumber& result ) const;

         int marshal( unsigned char ** pp ) const;

         void* unmarshal( void* bogus, unsigned char ** pp, long length );

         void toFile( const char* fname ) const;

         void* fromFile( const char* fname );

      private :
         CODEX_ASN1::SecureBigNumber  m_shares[ NumShares ];
   };

   template< unsigned int NumT , unsigned int ThreshT >
   Combinatoric<NumT,ThreshT>::Combinatoric() :
      CODEX_ASN1::Base( false )
   {
   }

   template< unsigned int NumT , unsigned int ThreshT >
   Combinatoric<NumT,ThreshT>::Combinatoric(
      const Combinatoric<NumT,ThreshT>& aOther ) :
      CODEX_ASN1::Base( aOther.m_initialized )
   {
      for ( unsigned int i = 0 ; i < NumShares ; ++i )
      {
         m_shares[i] = aOther.m_shares[i];
      }
   }

   template< unsigned int NumT , unsigned int ThreshT >
   Combinatoric<NumT,ThreshT>::Combinatoric(
      const ShareSet< Combinatoric<NumT,ThreshT> >& shareSet,
      unsigned int partNum ) :
      CODEX_ASN1::Base( true )
   {
      typedef CombinatoricScenario<NumT,ThreshT-1>  CSType;
      CSType* cs = CSType::instance();
      for ( unsigned int i = 0 ; i < NumShares ; ++i )
      {
         // Every participant gets the last share.
         if ( ( NumShares == (i+1) ) ||
              ( ! cs->inScenario( partNum, i ) ) )
         {
            m_shares[i] = shareSet(i);
         }
      }
   }

   template< unsigned int NumT , unsigned int ThreshT >
   Combinatoric<NumT,ThreshT>::~Combinatoric()
   {
   }

   template< unsigned int NumT , unsigned int ThreshT >
   void
   Combinatoric<NumT,ThreshT>::operator=(
      const Combinatoric<NumT,ThreshT>& aOther )
   {
      m_initialized = aOther.m_initialized;
      for ( unsigned int i = 0 ; i < NumShares ; ++i )
      {
         m_shares[i] = aOther.m_shares[i];
      }
   }

   template< unsigned int NumT , unsigned int ThreshT >
   void
   Combinatoric<NumT,ThreshT>::operator+=(
      const Combinatoric<NumT,ThreshT>& aOther )
   {
      if ( ! aOther.m_initialized )
      {
         return;
      }
      m_initialized = true;
      for ( unsigned int i = 0 ; i < NumShares ; ++i )
      {
         if ( ! m_shares[i].initialized() )
         {
            m_shares[i] = aOther.m_shares[i];
         }
      }
   }

   template< unsigned int NumT , unsigned int ThreshT >
   void
   Combinatoric<NumT,ThreshT>::setShare(
      unsigned int i,
      const CODEX_ASN1::SecureBigNumber& share )
   {
      if ( i >= NumShares )
      {
         throw CODEX_Exceptions::IllegalIndexException( __FILE__ , __LINE__ );
      }
      m_shares[i] = share;
      m_initialized = true;
   }

   template< unsigned int NumT , unsigned int ThreshT >
   const CODEX_ASN1::SecureBigNumber&
   Combinatoric<NumT,ThreshT>::share( unsigned int i ) const
   {
      if ( i >= NumShares )
      {
         throw CODEX_Exceptions::IllegalIndexException( __FILE__ , __LINE__ );
      }
      return m_shares[i];
   }

   template< unsigned int NumT , unsigned int ThreshT >
   unsigned int
   Combinatoric<NumT,ThreshT>::count() const
   {
      unsigned int retVal = 0;
      for ( unsigned int i = 0 ; i < NumShares ; ++i )
      {
         if ( m_shares[i].initialized() )
         {
            ++retVal;
         }
      }
      return retVal;
   }

   template< unsigned int NumT , unsigned int ThreshT >
   void
   Combinatoric<NumT,ThreshT>::apply( const ShareFunctional& func,
                                      Combinatoric<NumT,ThreshT>& result )
      const
   {
      result.m_initialized = true;
      for ( unsigned int i = 0 ; i < NumShares ; ++i )
      {
         if ( m_shares[i].initialized() )
         {
            func( m_shares[i] , result.m_shares[i] );
         }
      }
   }

   template< unsigned int NumT , unsigned int ThreshT >
   void
   Combinatoric<NumT,ThreshT>::recover( CODEX_ASN1::SecureBigNumber& result )
      const
   {
      if ( result.initialized() )
      {
         result = CODEX_ASN1::SecureBigNumber(); // reset
      }
      if ( ! m_initialized )
      {
         return;
      }
      for ( unsigned int i = 0 ; i < NumShares ; ++i )
      {
         if ( ! m_shares[i].initialized() )
         {
            return;
         }
      }
      BIGNUM * r = 0;
      try
      {
         r = BN_new();
         if ( 0 == r )
         {
            throw CODEX_Exceptions::BignumNullException( __FILE__ , __LINE__ );
         }
         if ( ! BN_zero(r) )
         {
            throw CODEX_Exceptions::BignumSetWordException( __FILE__ ,
                                                            __LINE__ );
         }
         for ( unsigned int i = 0 ; i < NumShares ; ++i )
         {
            if ( ! BN_add( r, r, m_shares[i].value() ) )
            {
               throw CODEX_Exceptions::BignumAddException( __FILE__ ,
                                                           __LINE__ );
            }
         }
         result = CODEX_ASN1::SecureBigNumber( r );
      }
      catch ( ... )
      {
         if ( 0 != r ) BN_clear_free(r);
         throw;
      }
   }

   template< unsigned int NumT , unsigned int ThreshT >
   int
   Combinatoric<NumT,ThreshT>::marshal( unsigned char ** pp ) const
   {
      int r=0;
      int ret=0;
      unsigned char * p;

      CODEX_ASN1::Integer isSet[NumShares];
      for ( unsigned int counter = 0 ; counter < NumShares ; ++counter )
      {
         isSet[counter] =
            CODEX_ASN1::Integer( m_shares[counter].initialized() ? 1 : 0 );
      }
      for ( unsigned int counter = 0 ; counter < NumShares ; ++counter )
      {
         ret += isSet[counter].marshal(0);
         if ( isSet[counter].value() )
         {
            ret += m_shares[counter].marshal(0);
         }
      }
      M_ASN1_I2D_seq_total();
      for ( unsigned int counter = 0 ; counter < NumShares ; ++counter )
      {
         isSet[counter].marshal(&p);
         if ( isSet[counter].value() )
         {
            m_shares[counter].marshal(&p);
         }
      }
      M_ASN1_I2D_finish();
   }

   template< unsigned int NumT , unsigned int ThreshT >
   void*
   Combinatoric<NumT,ThreshT>::unmarshal( void* bogus,
                                          unsigned char ** pp,
                                          long length )
   {
      if ( m_initialized )
      {
         return 0;
      }
      if ( (0 == pp) || (0 == *pp) )
      {
         return 0;
      }
      ASN1_CTX c;
      c.pp = pp;
      c.q = *pp;
      c.error = ERR_R_NESTED_ASN1_ERROR;
      int i;

      M_ASN1_D2I_Init();
      M_ASN1_D2I_start_sequence();
      for ( unsigned int counter = 0 ; counter < NumShares ; ++counter )
      {
         CODEX_ASN1::Integer isSet;
         M_ASN1_D2I_get(i, isSet.unmarshal);
         if ( isSet.value() )
         {
            M_ASN1_D2I_get(i, m_shares[counter].unmarshal);
         }
      }
      if ( !asn1_Finish(&c) )
      {
         return 0;
      }
      *pp=c.p;
      m_initialized = true;
      return this;
     err: // needed by ASN.1 macros
      return 0;
   }

   template< unsigned int NumT , unsigned int ThreshT >
   void
   Combinatoric<NumT,ThreshT>::toFile( const char* fname ) const
   {
      int length = marshal(0);
      if ( 0 == length ) return;
      unsigned char* buff = new unsigned char[length];
      unsigned char* p = buff;
      marshal(&p);
      ofstream os(fname);
      if ( ! os.is_open() )
      {
         delete [] buff;
         throw CODEX_Exceptions::FileCannotCreateException( __FILE__ ,
                                                            __LINE__ ,
                                                            fname );
      }
      for ( int i = 0 ; i < length ; ++i )
      {
         os << buff[i];
      }
      os.close();
      delete [] buff;
   }

   template< unsigned int NumT , unsigned int ThreshT >
   void*
   Combinatoric<NumT,ThreshT>::fromFile( const char* fname )
   {
      ifstream is(fname);
      if ( ! is.is_open() )
      {
         throw CODEX_Exceptions::FileCannotOpenException( __FILE__ ,
                                                          __LINE__ ,
                                                          fname );
      }
      string s;
      char ch;
      while ( is.get(ch) )
      {
         s.push_back(ch);
      }
      //basic_string<unsigned char> s;
      //is >> s;
      unsigned int length = s.length();
      unsigned char* p = new unsigned char[length];
      unsigned char* pOrig = p;
      //unsigned char* p = (unsigned char*)s.data();
      for ( unsigned int i = 0 ; i < length ; ++i )
      {
         p[i] = s.data()[i];
      }
      return unmarshal(0,&p,length);
      delete [] pOrig;
   }


   template< unsigned int NumT , unsigned int ThreshT >
   class ShareSet< Combinatoric<NumT,ThreshT> >
   {
      public :
         typedef Combinatoric<NumT,ThreshT>  ShareType;

         ShareSet() {}

         ShareSet( const ShareSet< ShareType >& aOther ) :
            m_shares( aOther.m_shares )
         {}

         void operator=( const ShareSet< ShareType >& aOther )
         {
            m_shares = aOther.m_shares;
         }

         const typename ShareType::ValueType& operator()( unsigned int i )
            const
         {
            return m_shares.share(i);
         }

         void setShare( unsigned int i,
                        const typename ShareType::ValueType& share )
         {
            m_shares.setShare(i,share);
         }

         void addShare( const ShareType& share )
         {
            m_shares += share;
         }

         void recover( CODEX_ASN1::SecureBigNumber& result ) const
         {
            return m_shares.recover( result );
         }

         bool shouldHave( unsigned int shareNum, unsigned int partNum ) const
         {
            typedef CombinatoricScenario<NumT,ThreshT-1>  CSType;
            CSType* cs = CSType::instance();
            if ( shareNum + 1 == ShareType::NumShares )
            {
               return true;
            }
            return ( ! cs->inScenario( partNum, shareNum ) );
         }

      private :
         ShareType  m_shares;
   };

   template< unsigned int NumT , unsigned int ThreshT >
   class ShareSplitting< Combinatoric<NumT,ThreshT> >
   {
      public :
         typedef Combinatoric<NumT,ThreshT>  ShareType;

         const static unsigned int           NumShares = ShareType::NumShares;

         static void split( const BIGNUM* secret,
                            ShareSet< ShareType >& shareSet,
                            const Range& range )
         {
            const BIGNUM * minVal = range.min();
            const BIGNUM * maxVal = range.max();
            BIGNUM * m = 0;
            BIGNUM * temp = 0;
            BIGNUM * total = 0;
            BIGNUM * remainder = 0;
            try
            {
               m = BN_new();
               if ( 0 == m )
               {
                  throw CODEX_Exceptions::BignumNullException( __FILE__ ,
                                                               __LINE__ );
               }
               total = BN_new();
               if ( 0 == total )
               {
                  throw CODEX_Exceptions::BignumNullException( __FILE__ ,
                                                               __LINE__ );
               }
               remainder = BN_new();
               if ( 0 == remainder )
               {
                  throw CODEX_Exceptions::BignumNullException( __FILE__ ,
                                                               __LINE__ );
               } 

               if ( ! BN_sub( m, maxVal, minVal ) )
               {
                  throw CODEX_Exceptions::BignumSubException( __FILE__ ,
                                                              __LINE__ );
               }
               if ( ! BN_add( m, m, BN_value_one() ) )
               {
                  throw CODEX_Exceptions::BignumAddException( __FILE__ ,
                                                              __LINE__ );
               }

               for ( unsigned int i = 0 ; i < NumShares - 1 ; ++i )
               {
                  temp = BN_new();
                  if ( 0 == temp )
                  {
                     throw CODEX_Exceptions::BignumNullException( __FILE__ ,
                                                                  __LINE__ );
                  }
                  if ( ! BN_rand_range( temp, m ) )
                  {
                     throw
                        CODEX_Exceptions::BignumRandRangeException( __FILE__ ,
                                                                    __LINE__ );
                  }
                  if ( ! BN_add( temp, temp, minVal ) )
                  {
                     throw CODEX_Exceptions::BignumAddException( __FILE__ ,
                                                                 __LINE__ );
                  }

                  if ( ! BN_add( total, total, temp ) )
                  {
                     throw CODEX_Exceptions::BignumAddException( __FILE__ ,
                                                                 __LINE__ );
                  }
                  shareSet.setShare(i,ShareType::ValueType(temp));
                  temp = 0;  // temp's memory is taken over above
               }

               if ( ! BN_sub( remainder, secret, total ) )
               {
                  throw CODEX_Exceptions::BignumSubException( __FILE__ ,
                                                              __LINE__ );
               }
               shareSet.setShare(NumShares-1,ShareType::ValueType(remainder));
               remainder = 0; // remainder's memory is taken over above
               BN_clear_free(total);
               BN_free(m);
            }
            catch ( ... )
            {
               if ( 0 != m ) BN_free(m);
               if ( 0 != temp ) BN_clear_free(temp);
               if ( 0 != total ) BN_clear_free(total);
               if ( 0 != remainder ) BN_clear_free(remainder);
               throw;
            }
         }
   };

}

#endif /* __CODEX_VSS_COMBINATORIC_H__*/

---