I needed some RSA public key encrypt / decrypt functionality recently. To do this, you need integer mathematics of longer-than-usual precision. This comes for free in a lot of languages, but not in C.

So, I searched around on the web, and I found a simple C "bignum" library, and it worked okay, once I added a shift and a modulo function. I still had a problem, though - the native format of that library's bignums was decimal, and all my data (RSA keys and cipher-text) was in hexadecimal - and conversion of huge numbers between decimal and hex, although straightforward, takes a lot of time.

So, I hacked at it a fair bit, and now I have a working hexadecimal "bignum" library. I'm posting it here as a way of placing what I've done into the public domain. I hope someone finds it useful. Sometime soon I'll probably post the RSA encrypt / decrypt functions that use this library also (but that stuff is really pretty simple, once you have the big integer maths).

Enough talk - shut up and show them the code, already... Copy and paste the stuff between the lines of plus signs. There's a .h file and a .c file.

Enjoy!

The header file : ++++++++++++++++++++++++++++++ #ifndef _HEX_BIGNUM_H_ #define _HEX_BIGNUM_H_

  ////////////////////////////////////////////////////////////////////
  //
  // Hexadecimal "bignum" functions. Deals solely with unsigned hexadecimal numbers.
  // Hacked together by Brian Myers (brian.d.myers@gmail.com)
  // Free for any use - no warranty.
  //
  // I started with the decimal "bignum" library by Skiena (see link below) below, but
  // I have modified it heavily :
  // 1. To convert it from signed-decimal to unsigned-hexadecimal.
  // 2. To allow source and destination arguments to be the same (at a small RAM cost).
  // 3. To add functions like modulo and rshift, for use in RSA public-key cryptography.
  //
  // Original source found here : http://www.brilliantsheep.com/handling-big-numbers-in-c/
  //
  /////////////////////////////////////////////////////////////////////
  /**
   * Copyright 2003 by Steven S. Skiena; all rights reserved. 
   *
   * Permission is granted for use in non-commerical applications provided this 
   * copyright notice remains intact and unchanged.
   * 
   * This file contains the structure for representing big numbers. In addition, 
   * this file contains functions for adding, subtracting, multiplying, and
   * dividing very large numbers.
   */
  ////////////////////////////////////////////////////////////////////
  // NOTE!
  // 1. Overflow errors will not be reported. YOU must ensure that your
  //    calculations don't overflow. This library will not corrupt anything
  //    on overflow (unless a bug), but your results will not be correct.
  // 2. These hex bignums DO NOT WRAP OR ROLL OVER. No 2's complement, no
  //    concept of negative values.
  // 3. If a subtraction would result in a negative result, you get zero.
  // 4. Truncating integer division is used.
  // 5. Division (or modulo) by zero gives a result of zero. GIGO.
  // 6. MAX_HEX_DIGITS can be set quite low if you like, but values of 0
  //    or 1 will most likely not work very well (or be very useful).
  ////////////////////////////////////////////////////////////////////

  #include <stdio.h>
  #include <stdlib.h>

  ///////////////////////////////////////////////////////////////////

  // Maximum length of a hex_bignum (number of hex digits). 
  #define MAX_HEX_DIGITS   2000

  // Set this to 1 for HB_test_main() unit test function.
  #define INCLUDE_UNIT_TESTS    0

  ///////////////////////////////////////////////////////////////////

  typedef unsigned char uint8_t;

  typedef struct
  {
     uint8_t digits[MAX_HEX_DIGITS];  // Valid values are zero to fifteen only.
     int lastdigit;                   // Index of highest-order non-zero digit.
  } hex_bignum_t;

  /////////////////////////////////////////////////////////////////////
  // Public functions.
  /////////////////////////////////////////////////////////////////////

  //////////////////////////////////////////////////////////////////////
  // Returns 1 if supplied number is odd, 0 if even.
  int HB_is_low_bit_set( hex_bignum_t *n_ptr );

  //////////////////////////////////////////////////////////////////////
  // Converts an integer to a hex_bignum.
  // Does nothing if the supplied integer is negative, or if the hex_bignum pointer is NULL.
  void HB_int_to_hex_bignum( int i, hex_bignum_t *n_ptr );

  /////////////////////////////////////////////////////////////////////
  // Adds hex big numbers; i.e. c = a + b */
  void HB_add( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr );

  //////////////////////////////////////////////////////////////////////
  // Subtracts hex big numbers; i.e. c = a - b.
  // If b is >= a, the result is zero! No negatives.
  void HB_subtract( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr );

  //////////////////////////////////////////////////////////////////////
  // Multiplies big numbers; i.e. c = a * b.
  void HB_multiply( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr );

  //////////////////////////////////////////////////////////////////////
  // Divides big numbers; i.e. c = a / b.
  // Truncating integer division.
  void HB_divide( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr );

  //////////////////////////////////////////////////////////////////////
  // Compares hex big numbers.
  // Returns 1 if (b > a); -1 if (a > b); 0 if equal.
  int HB_compare( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr );

  //////////////////////////////////////////////////////////////////////
  // Modulo of hex big numbers; i.e. c = a % b.
  // Calculated using : ( a % b ) == ( a - ( b * c ) ),
  // where c is ( a / b ).
  void HB_modulo( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr );

  //////////////////////////////////////////////////////////////////////
  // Right-shift a hex bignum by one bit.
  // n = n >> 1
  void HB_rshift( hex_bignum_t *n_ptr );

  //////////////////////////////////////////////////////////////////////
  // Converts a hexadecimal ASCII string to a hex big number.
  void HB_hex_string_to_hex_bignum( char *s, hex_bignum_t *n_ptr );

  //////////////////////////////////////////////////////////////////////
  // This function creates a hex-ASCII string in the supplied buffer, giving
  // the hex value of the passed hex bignum. Zero is returned on success;
  // otherwise the supplied buffer length was insufficient to hold the number,
  // or the supplied buffer-pointer was NULL.
  int HB_hex_bignum_to_hex_string( hex_bignum_t *n_ptr, uint8_t *buffer, int buffer_len, int *string_len );

  #if INCLUDE_UNIT_TESTS
  //////////////////////////////////////////////////////////////////////
  // Test Function
  //
  // Try setting MAX_HEX_DIGITS to (say) 10, and then run this, to see what
  // happens on overflow. In general, values are silently truncated.
  //
  void HB_test_main( void );
  #endif
  ///////////////////////////////////////////////////////////////////
  #endif
  

++++++++++++++++++++++++++++++ The C file :

  //
  // Hexadecimal "bignum" functions. Deals solely with unsigned hexadecimal numbers.
  // Hacked together by Brian Myers (brian.d.myers@gmail.com)
  // See the .h file for more details.
  //

  #include "hex_bignum.h"

  // Local prototypes.
  static void init_hex_bignum( hex_bignum_t *n_ptr );
  static void zero_justify( hex_bignum_t *n_ptr );
  static int my_max( int a, int b );
  static void digit_shift( hex_bignum_t *n_ptr );
  static uint8_t a_to_h( char c );
  static uint8_t h_to_a( uint8_t h );

  #if INCLUDE_UNIT_TESTS
  static void test_helper( char *s, hex_bignum_t *n_ptr );
  #endif

  //////////////////////////////////////////////////////////////////////
  // Returns 1 if supplied number is odd, 0 if even.
  int HB_is_low_bit_set( hex_bignum_t *n_ptr )
  {
     if ( n_ptr->digits[0] & 0x01 )
     {
        return 1;
     }
  
     return 0;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Initialises a hex bignum to zero.
  static void init_hex_bignum( hex_bignum_t *n_ptr )
  {
     memset( &(n_ptr->digits[0]), 0, MAX_HEX_DIGITS  );
     n_ptr->lastdigit = 0;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Converts an integer to a hex_bignum.
  // Does nothing if the supplied integer is negative, or if the hex_bignum pointer is NULL.
  void HB_int_to_hex_bignum( int i, hex_bignum_t *n_ptr )
  {
     int index;
  
     if ( ( i < 0 ) || ( n_ptr == NULL ) )
     {
        return;
     }
  
     init_hex_bignum( n_ptr );

     if ( i == 0 )
     {
        return;
     }
  
     index = 0;
     while ( i && ( index < MAX_HEX_DIGITS ) )
     {
        n_ptr->digits[index++] = (uint8_t)( i & 0x0F );
        i >>= 4;
     }
  
     // Note - we know that the while loop above executed at least once,
     // so it is safe to subtract one from 'index' without it going negative.
     n_ptr->lastdigit = index - 1;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Adds hex big numbers; i.e. c = a + b */
  void HB_add( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr )
  {
     static hex_bignum_t result;
     int carry;            /* carry digit */
     int i;                /* counter */
  
     init_hex_bignum( &result );
  
     result.lastdigit = my_max( a_ptr->lastdigit, b_ptr->lastdigit ) + 1;
     carry = 0;
  
     for ( i = 0; i <= result.lastdigit; i++ )
     {
        result.digits[ i ] = ( carry + a_ptr->digits[ i ] + b_ptr->digits[ i ] ) % 16;
        carry = ( carry + a_ptr->digits[ i ] + b_ptr->digits[ i ] ) / 16;
     }
  
     zero_justify( &result );
     *c_ptr = result;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Subtracts hex big numbers; i.e. c = a - b.
  // If b is >= a, the result is zero! No negatives.
  void HB_subtract( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr )
  {
     static hex_bignum_t result;
     int borrow;
     int v;
     int i;
  
     // result = 0;
     init_hex_bignum( &result );
  
     // If (b >= a), return (result is zero).
     if ( HB_compare( a_ptr, b_ptr ) != -1 )
     {
        *c_ptr = result;
        return;
     }
  
     result.lastdigit = my_max( a_ptr->lastdigit, b_ptr->lastdigit );
     borrow = 0;
  
     for ( i = 0; i <= result.lastdigit; i++ )
     {
        v = ( a_ptr->digits[ i ] - borrow - b_ptr->digits[ i ] );
  
        if ( a_ptr->digits[ i ] > 0 )
        {
           borrow = 0;
        }
  
        if ( v < 0 )
        {
           v = v + 16;
           borrow = 1;
        }
  
        result.digits[ i ] = (uint8_t) v % 16;
     }
  
     zero_justify( &result );
     *c_ptr = result;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Removes any leading zeros from a hex bignum.
  static void zero_justify( hex_bignum_t *n_ptr )
  {
      while ( ( n_ptr->lastdigit > 0 ) && ( n_ptr->digits[ n_ptr->lastdigit ] == 0 ) )
      {
          n_ptr->lastdigit--;
      }
  }
  
  //////////////////////////////////////////////////////////////////////
  // Returns the greatest of two integers.
  static int my_max( int a, int b )
  {
     return ( a > b ) ? a : b;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Multiplies big numbers; i.e. c = a * b.
  void HB_multiply( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr )
  {
     static hex_bignum_t result;
     static hex_bignum_t row;
     int i, j;
  
     init_hex_bignum( &result );
     row = *a_ptr;
  
     for ( i = 0; i <= b_ptr->lastdigit; i++ )
     {
        for ( j = 1; j <= b_ptr->digits[ i ]; j++ )
        {
           HB_add( &result, &row, &result );
        }
        digit_shift( &row );
     }
  
     zero_justify( &result );
     *c_ptr = result;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Multiplies a hex big number by 16 - effectively 1 hex-digit
  // shift to the left, zero-filling.
  static void digit_shift( hex_bignum_t *n_ptr )
  {
     int i;
  
     if ( ( n_ptr->lastdigit == 0 ) && ( n_ptr->digits[ 0 ] == 0 ) )
     {
        return;
     }
  
     for ( i = n_ptr->lastdigit; i >= 0; i-- )
     {
        n_ptr->digits[ i + 1 ] = n_ptr->digits[ i ];
     }
  
     n_ptr->digits[ 0 ] = 0;
  
     (n_ptr->lastdigit)++;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Divides big numbers; i.e. c = a / b.
  // Truncating integer division.
  void HB_divide( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr )
  {
     static hex_bignum_t result;
     static hex_bignum_t row;
     static hex_bignum_t tmp;
     int i;
  
     init_hex_bignum( &result );
  
     // Divide-by-zero is a special case, return 0.
     if ( ( b_ptr->lastdigit == 0 ) &&
          ( b_ptr->digits[ 0 ] == 0 ) )
     {
        *c_ptr = result;
        return;
     }
  
     init_hex_bignum( &row );
     init_hex_bignum( &tmp );
  
     result.lastdigit = a_ptr->lastdigit;
  
     for ( i = a_ptr->lastdigit; i >= 0; i-- )
     {
        digit_shift( &row );
        row.digits[ 0 ] = a_ptr->digits[ i ];
        result.digits[ i ] = 0;
  
        while ( HB_compare( &row, b_ptr ) != 1 )
        {
           result.digits[ i ]++;
           HB_subtract( &row, b_ptr, &tmp );
           row = tmp;
        }
     }
  
     zero_justify( &result );
     *c_ptr = result;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Compares hex big numbers.
  // Returns 1 if (b > a); -1 if (a > b); 0 if equal.
  int HB_compare( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr )
  {
     int i;
  
     if ( b_ptr->lastdigit > a_ptr->lastdigit )
     {
        return 1;
     }
  
     if ( a_ptr->lastdigit > b_ptr->lastdigit )
     {
        return -1;
     }
  
     for ( i = a_ptr->lastdigit; i >= 0; i-- )
     {
        if ( a_ptr->digits[ i ] > b_ptr->digits[ i ] )
        {
           return -1;
        }
  
        if ( b_ptr->digits[ i ] > a_ptr->digits[ i ] )
        {
           return 1;
        }
     }
  
     return 0;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Modulo of hex big numbers; i.e. c = a % b.
  // Calculated using : ( a % b ) == ( a - ( b * c ) ),
  // where c is ( a / b ).
  void HB_modulo( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *c_ptr )
  {
     static hex_bignum_t temp;
  
     // temp = a / b;
     HB_divide( a_ptr, b_ptr, &temp );
  
     // temp = temp * b;
     HB_multiply( &temp, b_ptr, &temp );
  
     // c = a - temp
     HB_subtract( a_ptr, &temp, c_ptr );
  }
  
  //////////////////////////////////////////////////////////////////////
  // Right-shift a hex bignum by one bit.
  // n = n >> 1
  void HB_rshift( hex_bignum_t *n_ptr )
  {
     int i;
     uint8_t temp;
     uint8_t carry;
  
     carry = 0;
  
     for ( i = n_ptr->lastdigit; i >= 0; i-- )
     {
        // Get the current value in temp.
        temp = n_ptr->digits[ i ];
  
        if ( carry )
        {
           // Get the next carry-value.
           carry = temp & 0x01;
           // Shift, and OR in the previous carry.
           // Remember that only the low nibble is valid.
           n_ptr->digits[ i ] = ( temp >> 1 ) | 0x08;
        }
        else
        {
           // Get the next carry-value.
           carry = temp & 0x01;
           // Shift, no previous carry.
           n_ptr->digits[ i ] = temp >> 1;
        }
     }
  
     zero_justify( n_ptr );
     // The final carry value is lost (shifted out).
  }
  
  //////////////////////////////////////////////////////////////////////
  // Converts a hexadecimal ASCII string to a hex big number.
  void HB_hex_string_to_hex_bignum( char *s, hex_bignum_t *n_ptr )
  {
     int i;
     int length;
  
     init_hex_bignum( n_ptr );
  
     length = strlen( s ) - 1;
     if ( length > MAX_HEX_DIGITS )
     {
        length = MAX_HEX_DIGITS;
     }
  
     for ( i = length; i >= 0; i-- )
     {
        n_ptr->digits[ length - i ] = a_to_h( s[ i ] );
     }
  
     n_ptr->lastdigit = length;
  
     zero_justify( n_ptr );
  }
  
  //////////////////////////////////////////////////////////////////////
  // Returns the hex value of an ASCII char.
  static uint8_t a_to_h( char c )
  {
     if ( ( c >= '0' ) && ( c <= '9' ) )
     {
        return ( c - '0' );
     }
  
     if ( ( c >= 'A' ) && ( c <= 'F' ) )
     {
        return ( c - 'A' + 0x0A );
     }
   
     if ( ( c >= 'a' ) && ( c <= 'f' ) )
     {
        return ( c - 'a' + 0x0A );
     }
  
     // Shouldn't get here - not ASCII hex.
     return 0;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Returns the ASCII value of a hex digit (or '!', if invalid hex value).
  static uint8_t h_to_a( uint8_t h )
  {
     if ( h <= 9 )
     {
        return '0' + h;
     }
     else if ( h <= 15 )
     {
        return 'A' + ( h - 10 );
     }
     else
     {
        // Error.
        return '!';
     }
  }
  
  //////////////////////////////////////////////////////////////////////
  // This function creates a hex-ASCII string in the supplied buffer, giving
  // the hex value of the passed hex bignum. Zero is returned on success;
  // otherwise the supplied buffer length was insufficient to hold the number,
  // or the supplied buffer-pointer was NULL.
  int HB_hex_bignum_to_hex_string( hex_bignum_t *n_ptr, uint8_t *buffer, int buffer_len, int *string_len )
  {
     int i;
  
     // We need one more character than we have digits, for the null-terminator.
     if ( ( buffer == NULL ) ||
          ( n_ptr->lastdigit > ( buffer_len - 1 ) ) )
     {
        return 1;
     }
  
     for ( i = n_ptr->lastdigit; i >= 0; i-- )
     {
        *buffer++ = h_to_a( n_ptr->digits[ i ] );
     }
   
     *buffer++ = 0;
  
     *string_len = n_ptr->lastdigit + 1;
  
     return 0;
  }
  
  #if INCLUDE_UNIT_TESTS
  //////////////////////////////////////////////////////////////////////
  // Test Function
  //
  // Try setting MAX_HEX_DIGITS to (say) 10, and then run this, to see what
  // happens on overflow. In general, values are silently truncated.
  //
  void HB_test_main( void )
  {
     char *a = "0123456789ABCDEFfedcba9876543210";
     hex_bignum_t n1, n2, n3;
  
     // Create big numbers, from a string variable and from a string.
     HB_hex_string_to_hex_bignum( a, &n1 );
     HB_hex_string_to_hex_bignum( "000DeadBeefCafe", &n2 );
  
     // Convert back to strings and print. Note a-f ==> A-F
     test_helper( "Digits", &n1 );
     test_helper( "Steak joint", &n2 );
  
     // Test of the operations.
     HB_hex_string_to_hex_bignum( "1111111111111111111111111111111111111111111111", &n1 );
     HB_hex_string_to_hex_bignum( "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD", &n2 );
  
     // Addition.
     HB_add( &n1, &n2, &n3 );
     test_helper( "All E's", &n3 );
  
     // Subtraction.
     HB_subtract( &n2, &n1, &n3 );
     HB_subtract( &n3, &n1, &n3 );    // Note - n3 is source & destination.
     test_helper( "All B's", &n3 );
  
     // Subtraction that would result in a negative will yield zero.
     // This is by design! Not wrapping or doing 2's complement here.
     HB_subtract( &n3, &n2, &n3 );
     test_helper( "Zero", &n3 );
  
     // Multiplication.
     HB_int_to_hex_bignum( 2, &n3 );
     HB_multiply( &n3, &n1, &n2 );
     test_helper( "All 2's", &n2 );
  
     HB_divide( &n2, &n3, &n2 );
     test_helper( "All 1's", &n2 );
  
     // Multiply by zero.
     HB_int_to_hex_bignum( 0, &n3 );
     HB_multiply( &n1, &n3, &n2 );
     test_helper( "Zero", &n2 );
  
     // Divide by zero (defined to return zero).
     HB_divide( &n1, &n3, &n2 );
     test_helper( "Zero", &n2 );
  
     // Hex 10000 in n2
     HB_int_to_hex_bignum( 65536, &n2 );
  
     // All 1's mod 10000 should yield 0x1111.
     HB_modulo( &n1, &n2, &n3 );
     test_helper( "Four 1's", &n3 );
  
     HB_rshift( &n3 );
     test_helper( "Three 8's", &n3 );
  
     HB_rshift( &n3 );
     test_helper( "Three 4's", &n3 );
  }
  
  //////////////////////////////////////////////////////////////////////
  //
  static void test_helper( char *s, hex_bignum_t *n_ptr )
  {
     static char big_buffer[1000];
     int length;
  
     if ( HB_hex_bignum_to_hex_string( n_ptr, &big_buffer[0], 1000, &length ) == 0 )
     {
        printf( "%s:\n%s\n", s, big_buffer );
     }
     else
     {
        printf( "Error!\n" );
     }
  
  }
  //////////////////////////////////////////////////////////////////////
  #endif
  

++++++++++++++++++++++++++++++