kokke / tiny-bignum-c Goto Github PK

Hi, I've been doing my own implementation, largely based on your code, thanks! 👍

Take a look at this bit from bignumdiv:

while (bignum_cmp(&denom, a) != LARGER) // while (denom <= a) {
{
_lshift_one_bit(&current); // current <<= 1;
_lshift_one_bit(&denom); // denom <<= 1;
}

What happens when denom <= a, and denom's most significant bit is 1? The left shift fails.

My code (big numbers using 32bit arrays) looks something like this:

uint32_t const half_max = 1 + (uint32_t)INT32_MAX;
bool overflow = false;
//
while (_bignum_cmp(denom, a) != LARGER) // while (denom <= a) {
{
if ( denom[array_size-1] >= half_max )
{
overflow = true;
break;
}
_lshift_one_bit(current); // current <<= 1;
_lshift_one_bit(denom); // denom <<= 1;
}
if ( ! overflow )
{
_rshift_one_bit(denom); // denom >>= 1;
_rshift_one_bit(current); // current >>= 1;
}

The current division algorithm uses a BIGNUM structure for 'current' while its task can be completed with natural integer arithmetics. In my local fork (sorry, it's still a hot mess), I have changed the algorithm as follows, where several names and small things have been altered, but should still be recognizable fine:

  //
  // Use an integer of natural size to store the current Bit index as 'current'
  // is always a 2's potency. While a BIGNUM can theoretically hold a
  // 2's potency eight times larger than what can represent as Bit index with a
  // natural integer (Bytes vs Bits), this cannot happen within this function
  // as 'a' aligned to the next 2's potency would need to be just as big for
  // this to be the case. This cannot happen due to the address space
  // limitation.
  //
  size_t currentBitIndex = 0;                         // int current = 1;         
  bignum_u_assign_const(denom, b);                    // denom = b
  bignum_u_assign_const(tmp, a);                      // tmp   = a

  const DTYPE half_max = 1 + (DTYPE)(((1ULL << (8 * WORD_SIZE)) - 1U) / 2);
  bool overflow = false;
  while (bignum_u_cmp(denom, a) != LARGER)            // while (denom <= a) {
  {
    if (denom->d[BN_U_DLEN(denom) - 1] >= half_max)
    {
      overflow = true;
      break;
    }
    ++currentBitIndex;                                //   current <<= 1;                 
    _lshift_bit_const(denom, 1);                      //   denom <<= 1;
  }
  if (!overflow)
  {
    _rshift_bit_const(denom, 1);                      // denom >>= 1;
    --currentBitIndex;                                // current >>= 1;                 
  }
  bignum_u_init_const(c);                             // int answer = 0;
  //
  // currentBitIndex cannot add-wraparound to reach this value as reasoned in
  // the comment before.
  //
  while(currentBitIndex != (size_t)0U - 1U)           // while (current != 0)
  {
    if (bignum_u_cmp(tmp, denom) != SMALLER)          //   if (dividend >= denom)
    {
      bignum_u_sub(tmp, denom, tmp);                  //     dividend -= denom;            
      bignum_u_or_int (c, 1, currentBitIndex);        //     answer |= current;
    }
    --currentBitIndex;                                //   current >>= 1;
    _rshift_bit_const(denom, 1);                      //   denom >>= 1;
  } 

Along with this newly introduced function:

void bignum_u_or_int(ubn* a, DTYPE v, size_t nbits)
{
  require(a, "a is null");

  const uint8_t nbits_pr_word = (WORD_SIZE * 8);
  size_t nwords   = nbits / nbits_pr_word;
  uint8_t  nwordbits = nbits % nbits_pr_word;

  if (nwords >= BN_U_DLEN (a)) {
    return;
  }

  a->d[nwords] |= (v << nwordbits);
}

BN_U_DLEN returns the array size of the current sturcture instance, which I added because I cannot affort having every BIGNUM at the maximum required size among all.

This new function is also a really important one performance-wise for different tasks as it allows super-fast construction of 2's potencies. For example, I also used it for the calculation of R², used for Montgomery arithmetics, where R is a 2's potency. The BoringSSL algorithm utilizes BIGNUM shift, pow and mul algorithms for its construction, when with this function, it can be achieved easily with just a preceeding BIGNUM init.

The problem lies with this piece of code:

which appears as:

`
int i = nbytes - (2 * WORD_SIZE); /* index into string /
int j = 0; / index into array */

/* reading last hex-byte "MSB" from string first -> big endian /
/ MSB ~= most significant byte / block ? :) /
while (i >= 0)
{
tmp = 0;
sscanf(&str[i], SSCANF_FORMAT_STR, &tmp);
n->array[j] = tmp;
i -= (2 * WORD_SIZE); / step WORD_SIZE hex-byte(s) back in the string. /
j += 1; / step one element forward in the array. */
}
`

If 'i' (the length of the inbound string, in characters) is not a multiple of '2 * WORD_SIZE' then it will skip over the MSB hexadecimal characters at the beginning of the string when 'i < 0' and miss the characters at the beginning of the inbound string, incorrectly setting 'n'.

I think the use of sprintf/sscanf is not ideal. Custom to/from string routines would be better.

Have been working with your neat library today but struggling with simplest of things. Want to work with larger 64 byte hex ecdsa but not even having luck with simple conversions to/from small strings and back. I see a note in one test script to force even number strings

file ec.c excerpt
struct bn bn1,bn2,gX;
bignum_init(&bn1);
bignum_init(&bn2);
bignum_init(&gX);

    char s1[8];
bignum_from_string(&bn1,"01",2);
bignum_from_int(&bn2, 2);
bignum_to_string(&bn1,s1,8);
printf("tostr  %s",s1);

   I have set my WORD size in bn.h to 1,2,and 4 hoping to figure it out
  building as  gcc ec.c bn.c  -g -o  ec

 on small size strings as above I'm not getting any output. On larger strings such as below the conversion back
 to string is much shorter and all wrong
 bignum_from_string(&gX, "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",64);

Any help much appreciated. C is very problematic for me, so hoping am missing something easy

I was running a program in which I observed that the argument b in
void bignum_pow(struct bn* a, struct bn* b, struct bn* c);

had its original value changed to zero after executing this function. Looking at the function code, it seems that the b pointer is directly being decremented within (see lines 524, 533 in bn.c). I guess this is not expected behavior, as b is an input argument.

Since bignum_mod already does the division, it might be handy to have a function that gives both a/b and a%b in one call instead of calling both bignum_div and bignum_mod.

Current implementation of the header will throw a compile-time error, if word size would be defined to be 8. On x86_64 platforms, which are a very common target this word size might be the fastest type and thus it is desireable that WORD_SIZE=8 could also be specified

`
char buffer[500];
struct bn a, b, c;

bignum_from_string(&a, "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe", 64);
bignum_to_string(&a, buffer, 500);
printf("%s\n", buffer);

bignum_from_int(&b, 3);

bignum_add(&a, &b, &c);
bignum_to_string(&c, buffer, 500);
printf("%s\n", buffer);

`

length of "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe" is 63
if I change 64 to 63 and comment out
// require((nbytes & 1) == 0, "string format must be in hex -> equal number of bytes"); // require((nbytes % (sizeof(DTYPE) * 2)) == 0, "string length must be a multiple of (sizeof(DTYPE) * 2) characters");

that code works correct

PR created: #26

bignum_to_string appears to render a struct bn as hex rather than decimal; can we get a decimal option?

I think its good to export pow_mod_faster in the tests/rsa.c to the public API in the form bignum_pow_mod function.
Its complement bignum_pow but with fast modulo exponentiation functionality at the hand

Hi,
When I run the RSA test case, it output empty decrypt result.

int bignum_r_degree(struct bn* n)
{
int i = BN_ARRAY_SIZE;
while ((n->array[--i] == 0) && i);
int out = i * WORD_SIZE * 8;
out += 32 - __builtin_clz(n->array[i]);
return out;
}
Returns the number of bits used to write the number (!!!not the buffer size).

  File "./scripts/test_rand.py", line 123
    expected = int(math.sqrt(oper1));
                                    ^
TabError: inconsistent use of tabs and spaces in indentation
*** Error code 1

Python-3.8

Otherwise the user of bignum_to_string() should guess how many characters might be needed?

Sorry for not submitting a pull request, I'm working on a bignum library and I saw your implementation of multiplication so I just want to point out that you can simplify it by doing the multiply and the add in one loop into the result bn as follow:

typedef unsigned int           u32;
typedef unsigned long long int u64;
void _bn_add_mul_u32(u32 *out, u32 *a, size_t a_len, u32 b)
{
  u64 c = 0;
  size_t i;
  for(i=0; i<a_len; i++)
  {
    u64 a_w = a[i];
    u64 out_w = out[i];
    u64 o = out_w + a_w * b + c;
    c = o >> 32;
    out[i] = o & 0xffffffff;
  }
  for(; c; i++)
  {
    u64 o = out[i] + c;
    c = o >> 32;
    out[i] = o & 0xffffffff;
  }
}
void _bn_mul(u32 *out, u32 *a, size_t a_len, u32 *b, size_t b_len)
{
  for(size_t i=0; i<b_len; i++)
  {
    u32 b_w = b[i];
    _bn_add_mul_u32(out+i, a, a_len, b_w);
  }
}

1. Can you please clarify the maximum size of a bignum in bits?

bn.h states that

a A 1024 bit integer takes up 128 bytes RAM, implying that the library supports at least that.

b.But for a WORD_SIZE of 4 (which appears to the the maximum) bn.h also states that
the size of big numbers in bytes BN_ARRAY_SIZE is 128/WORD_SIZE which = 32 bytes or 32 *8 bits/byte = 256 bits

c.The data holding structure (Array of DTYPES) is DTYPE array[BN_ARRAY_SIZE]
For WORD_SIZE == 4 DTYPE is a uint32_t (32 bits) and * (per b.) BN_ARRAY_SIZE = 256 bits
which gives 32 * 256 = 8192 bits

I attach below the output from a test tool (kblt) and the 'c' source for it.

Using the bignum_pow function
2^607 appears to be evaluated correctly but
2^1279 which is comfortably over 1024 bits is evaluated to 0
which inclines me to the conclusion that tiny-bignum-c supports up to 1024 bit integers.

2. A second question which I am uncertain about, is whether DTYPE_TMP,
   which for WORD_SIZE == 4 is a uint64_t 64-bit value
   may in fact constrain results to only 64-bits

   in the functions where it is used directly.
   bignum_from_int()
   bignum_inc()
   bignum_add()
   bignum_sub()
   bignum_mul()
   bignum_div()

   and functions that depend on the above
   bignum_divmod()
   bignum_pow()
   bignum_isqrt()

   I have seen no evidence of this in bignum code I have written using bignum_from_int(),
   divmod, pow, and isqrtbut i would appreciate clarification on this.

I appreciate the clarity and cleanness of the code and thank you for it.

dave

==== kblt output =========================================================================================

kblt Version 1.0 Build 02 (c) ZDS LLC 2020 started

bignum WORD_SIZE = 4
bignum BN_ARRAY_SIZE (size of big-numbers) : 32 (bytes) 256 (bits)
bignum MAX_VAL (of DTYPE_TMP) : 4294967295 (bits) 4,294,967,296 -1 16^8 or 2^32 (bits)

2^7 Result Hex = 80
Expected Hex=[0x80]
Expected Dec=[128]

2^19 Result Hex = 80000
Expected Hex=[0x80000]
Expected Dec=[524288]

2^31 Result Hex = 80000000
Expected Hex=[0x80000000]
Expected Dec=[2147483648]

2^61 Result Hex = 2000000000000000
Expected Hex=[0x2000000000000000]
Expected Dec=[2305843009213693952]

2^63 Result Hex = 8000000000000000
Expected Hex=[0x8000000000000000]
Expected Dec=[9223372036854775808]

2^64 Result Hex = 10000000000000000
Expected Hex=[0x10000000000000000]
Expected Dec=[18446744073709551616]

2^65 Result Hex = 20000000000000000
Expected Hex=[0x20000000000000000]
Expected Dec=[36893488147419103232]

2^89 Result Hex = 20000000000000000000000
Expected Hex=[0x20000000000000000000000]
Expected Dec=[618970019642690137449562112]

2^127 Result Hex = 80000000000000000000000000000000
Expected Hex=[0x80000000000000000000000000000000]
Expected Dec=[170141183460469231731687303715884105728]

2^521 Result Hex = 20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Expected Hex=[0x20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]
Expected Dec=[6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057152]

2^607 Result Hex = 80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Expected Hex=[0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]
Expected Dec=[531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728128]

2^1279 Result Hex =
Expected Hex=[0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]
Expected Dec=[10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729088]

kblt Version 1.0 Build 02 (c) ZDS LLC 2020 completed

==== kblt.c source =======================================================================================

//
// Program : kblt : kokke_bignum_limit_test
// Author : Dave Goodall, ZDS LLC [email protected]
// Syntax : kblt
// Function : Test 2^n limit of bignum package

// Suppress Microsoft Visual Studio 2019 pestilential ERRORS
// "C4996: 'ctime': This function or variable may be unsafe. Consider using ctime_s instead."
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <time.h> // time_t
#include <stdlib.h> // malloc free
#include "bn.h"
#include <inttypes.h> // sprintf specifier uint64_t
#include <string.h>

// ----------------------------------------------------------------------

#define PROGRAM_NAME "kblt"

#define VERSION "1.0 Build 02" // 10/20/2090
// 1. Add powTest()
// 2. Extend tests past the 1024 bit limit(?)
// "1.0 Build 01" // 10/19/2090
// 1. First clean compile
// Discrete test c cases

typedef enum
{
false = 0,
true = 1,
} bool;

// Files ------------------------------------------------------------------
#define STRING_SIZE_DEC 262144 // Hex 0x40000
#define STRING_SIZE_HEX 0x40000
char szString[STRING_SIZE_HEX];

// ------------------------------------------------------------------------
// Log File

#define MSG_LEN 524288 // Hex 0x80000
#define LOG_FILE_EXT "log"

FILE *fdLogFile; // File descriptor
char szLogFileName[128];
char szLogFileBuf[MSG_LEN]; // File buffer
bool bLogFile; // File available

// ------------------------------------------------------------------------

DTYPE_TMP dt_base = 2;

DTYPE_TMP dt_exponent_31 = 31;
DTYPE_TMP dt_exponent_61 = 61;
DTYPE_TMP dt_exponent_63 = 63;
DTYPE_TMP dt_exponent_64 = 64;
DTYPE_TMP dt_exponent_65 = 65;
DTYPE_TMP dt_exponent_89 = 89;
DTYPE_TMP dt_exponent_127 = 127;
DTYPE_TMP dt_exponent_521 = 521;

// Global to simplify parameter passing
struct bn bn_base;
struct bn bn_exponent;
struct bn bn_result;

// ------------------------------------------------------------------------
// Prototypes
void powTest(DTYPE_TMP dt_exponent, char* cpExpectedHex, char* cpExpectedDec);
extern void logPrint( char * cpBuf, bool bCloseFile);
void syntax();

int main(int argc, char** argv) {

//------------------------------------------------------------------------
// Open the log file for appending
sprintf(szLogFileName, "%s.%s", PROGRAM_NAME, LOG_FILE_EXT);
fdLogFile = fopen(szLogFileName, "a+");
if (fdLogFile != NULL) {
bLogFile = true;
}

//------------------------------------------------------------------------
// Now logging can start...
sprintf(szLogFileBuf, "%s Version %s (c) ZDS LLC 2020 started\n", PROGRAM_NAME, VERSION);
logPrint(szLogFileBuf, false);

// Display bignum configuration parameters
sprintf(szLogFileBuf, "bignum WORD_SIZE = %d", WORD_SIZE);
logPrint(szLogFileBuf, false);

sprintf(szLogFileBuf, "bignum BN_ARRAY_SIZE (size of big-numbers) :  %d (bytes)  %d (bits)", BN_ARRAY_SIZE, BN_ARRAY_SIZE*8);
logPrint(szLogFileBuf, false);

sprintf(szLogFileBuf, "bignum MAX_VAL (of DTYPE_TMP) :  %I64u (bits)  %s (bits)\n\n", MAX_VAL, "4,294,967,296 -1  16^8 or 2^32");
logPrint(szLogFileBuf, false);

bignum_from_int(&bn_base, dt_base);  // ( bignum_int does an internal bignum_init(n) )

// Power computations:                 https://www.mathsisfun.com/calculator-precision.html
//                                     http://lcn2.github.io/mersenne-english-name/m1279/prime-c-e.html
// Decimal to Hexadecimal converter:   https://www.rapidtables.com/convert/number/decimal-to-hex.html 

// Evaluate  2^n     {Expected Hex}  {Expected Dec}
// Note: String size STRING_SIZE_HEX must be manually adjusted to exceed the maximum needed by the largest power
// For example : // 31-11 61-19 63-19 64-20 65-20 89-26 127-35 521-134 607-184 1279-385

powTest((DTYPE_TMP)7, "0x80", "128");
powTest((DTYPE_TMP)19, "0x80000", "524288");
powTest((DTYPE_TMP)31, "0x80000000",          "2147483648" );
powTest((DTYPE_TMP)61, "0x2000000000000000",  "2305843009213693952");
powTest((DTYPE_TMP)63, "0x8000000000000000",  "9223372036854775808");
powTest((DTYPE_TMP)64, "0x10000000000000000", "18446744073709551616");
powTest((DTYPE_TMP)65, "0x20000000000000000", "36893488147419103232");
powTest((DTYPE_TMP)89, "0x20000000000000000000000", "618970019642690137449562112");
powTest((DTYPE_TMP)127, "0x80000000000000000000000000000000", "170141183460469231731687303715884105728");
powTest((DTYPE_TMP)521, "0x20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", 
"6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057152");

powTest((DTYPE_TMP)607, "0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000","531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728128");

// 1279 (Past the 1024 bit integer specified in bn.h)
// 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729088
powTest((DTYPE_TMP)1279, "0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729088");


sprintf(szLogFileBuf,"%s Version %s (c) ZDS LLC 2020 completed\n\n", PROGRAM_NAME, VERSION );
logPrint(szLogFileBuf, true);

// Cleanup

if (bLogFile)
fclose (fdLogFile);

return 0;

}

void powTest(DTYPE_TMP dt_exponent, char* cpExpectedHex, char* cpExpectedDec) {

bignum_from_int(&bn_exponent, dt_exponent);  // ( bignum_int does an internal bignum_init(n) )
bignum_pow(&bn_base, &bn_exponent, &bn_result); // ( bignum_pow does an internal bignum_init(c) )
memset(szString, '\0', sizeof(szString));
bignum_to_string(&bn_result, szString, sizeof(szString));
printf(" 2^%I64u Result Hex =     %-170.170s\n       Expected Hex=[%s]\n       Expected Dec=[%s]\n\n", dt_exponent, szString, cpExpectedHex, cpExpectedDec);

}

// Log and Display message
void logPrint( char * cpBuf, bool bCloseFile) {

if (bLogFile) {
   fprintf(fdLogFile, " %s\n", cpBuf);
   fflush(fdLogFile);
   if (bCloseFile) {
       fclose(fdLogFile);
    }
}
printf("\n %s", cpBuf);

}

//---------------------------------------------------------------------------
// Required [r]
// {Optional} {o}

void syntax() {
printf("\n\n Syntax: [required] {optional}\n\n");
printf(" %s \n", PROGRAM_NAME);
}

// --- End Program --------------------------------------------------------

I am trying to implement the deffie-hellman-group14 but unfortunately bignum_pow_mod_faster gives me 0 back...
I got a & b for testing from this site: http://acme.com/dhtest/dhtest.html

#include <string.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "bn.h"

uint32_t P[64] = { // Prime
     0xFFFFFFFF,0xFFFFFFFF,0xC90FDAA2,0x2168C234,0xC4C6628B,0x80DC1CD1
    ,0x29024E08,0x8A67CC74,0x020BBEA6,0x3B139B22,0x514A0879,0x8E3404DD
    ,0xEF9519B3,0xCD3A431B,0x302B0A6D,0xF25F1437,0x4FE1356D,0x6D51C245
    ,0xE485B576,0x625E7EC6,0xF44C42E9,0xA637ED6B,0x0BFF5CB6,0xF406B7ED
    ,0xEE386BFB,0x5A899FA5,0xAE9F2411,0x7C4B1FE6,0x49286651,0xECE45B3D
    ,0xC2007CB8,0xA163BF05,0x98DA4836,0x1C55D39A,0x69163FA8,0xFD24CF5F
    ,0x83655D23,0xDCA3AD96,0x1C62F356,0x208552BB,0x9ED52907,0x7096966D
    ,0x670C354E,0x4ABC9804,0xF1746C08,0xCA18217C,0x32905E46,0x2E36CE3B
    ,0xE39E772C,0x180E8603,0x9B2783A2,0xEC07A28F,0xB5C55DF0,0x6F4C52C9
    ,0xDE2BCBF6,0x95581718,0x3995497C,0xEA956AE5,0x15D22618,0x98FA0510
    ,0x15728E5A,0x8AACAA68,0xFFFFFFFF,0xFFFFFFFF,
};

void bignum_from_uint32(struct bn* n, uint32_t* ar, int length){
    int i;
    bignum_init(n);

    for(i=0; i < length; i++){
        n->array[i] = ar[i];
    }
}

/* O(log n) */
void bignum_pow_mod_faster(struct bn* a, struct bn* b, struct bn* n, struct bn* res){
  bignum_from_int(res, 1); /* r = 1 */

  struct bn tmpa;
  struct bn tmpb;
  struct bn tmp;
  bignum_assign(&tmpa, a);
  bignum_assign(&tmpb, b);
  bignum_init(&tmp);

  while (1)
  {

    if (tmpb.array[0] & 1)     /* if (b % 2) */
    {
      bignum_mul(res, &tmpa, &tmp);  /*   r = r * a % m */
      bignum_mod(&tmp, n, res);
    }
    bignum_rshift(&tmpb, &tmp, 1); /* b /= 2 */
    bignum_assign(&tmpb, &tmp);

    if (bignum_is_zero(&tmpb))
      break;

    bignum_mul(&tmpa, &tmpa, &tmp);
    bignum_mod(&tmp, n, &tmpa);
  }
}

void bignum_rand(struct bn* n){
    int i;
    for(i=0; i < BN_ARRAY_SIZE; i++){
        n->array[i] = rand();
    }
}

void main(void){
    int i;
    struct bn prime, 
    a,b,
    A,B,
    g,      //generator
    K_a,    //B^a mod prime
    K_b;    //A^b mod prime

    bignum_init(&a);
    bignum_init(&b);
    bignum_init(&A);
    bignum_init(&B);
    bignum_init(&K_a);
    bignum_init(&K_b);

    bignum_from_uint32(&prime, P, 64);
    print(&prime, "P");
    bignum_from_int(&g, 2);
    print(&g, "G");

    uint32_t ta[] = {
        0xfcc9a5d7,0x391df8fd,0x5e772975,0x8936c474,0xaa30b981,0xd17b1c92,0x194b11a9,0xa76ef75b,0xdf8b50dd,0xe5969ce,0x8068c602,0x13935eaf,0x82fc4d8d,0xb3bfb2c5,0x6f8f84cb,0x8e1966b2,0x1c45cd44,0x74c71ddc,0x428cf7d,0xa9e20c48,0xe2f178cb,0xe61b2e06,0x782373b6,0xe7ca18b4,0xeb60289a,0x5b76374d,0x72d301f5,0x196cbb6d,0x2b4e42d1,0x6575a616,0x2612a4f3,0x59cf2c7,0xdcf78046,0x51f0019,0x2d95f717,0x18542fc3,0x26788c6a,0x5ad9fb26,0xec644d3a,0x63824f53,0x73bf6e57,0x7e9adc44,0xadbd4f78,0x964e3add,0xed2ae2df,0xcf427594,0x4f2c52a7,0xde4f9a45,0xf3603134,0x857a7ef9,0x970d0a41,0xe2926f5e,0x5777022a,0x1c53f04,0xac36066a,0xf74a100,0x2d11b509,0xb6ef5cc0,0xe45e3744,0xc75a23e,0x8c4665ed,0x7382d0f5,0x87089069,0x4c580147
    };
    uint32_t tb[] = {
        0x43de3fb1,0x372a4b9f,0xab988c39,0xec229c26,0xc61e0a5b,0x923b467e,0x77b292a,0x329005a1,0xeb82f955,0xc08bf84d,0x19a57ab9,0xe2c3253b,0x4f933610,0xfd6b699f,0x62123379,0xf91fbf9a,0x63eafcab,0xa52d6e2e,0x4caa7ba7,0xf5024552,0x572becf3,0x528120af,0xd97ef711,0xa1cca982,0xc4ec3c59,0x8b9f2736,0xb6892085,0xc28a5366,0x64a594d,0xf8ac64a6,0x38d8e027,0x82937858,0x895bfb6e,0x787e51c6,0xda608660,0x359700d1,0xe23c56d2,0x5330b327,0xceafc4d3,0x76154cb3,0xf23c135a,0xe0e84f21,0x8a5caa5,0x929bccb9,0x23721701,0xa3d8a39a,0xf907e59d,0xc1880e42,0xaa6867b8,0x99ebd1ad,0x8403defc,0x40aa57f,0xe96830e,0x15cfbd39,0x66494f76,0x85a3c463,0xbd2143dd,0xeab6c439,0xde7987c9,0x94e2ce83,0x8e7802c5,0x44ad04a6,0x14f89058,0xe7c5f096
    };
    
    bignum_from_uint32(&a, ta, 64);
    print(&a, "a");
    
    bignum_from_uint32(&b, tb, 64);
    print(&b, "b");

    bignum_pow_mod_faster(&g, &a, &prime, &A); // g^a mod prime = A
    print(&A, "A");
    
    bignum_pow_mod_faster(&g, &b, &prime, &B); // g^b mod prime = B         
    print(&B, "B");

    bignum_pow_mod_faster(&B, &a, &prime, &K_a); // B^a mod prime = K
    print(&K_a, "K_a");
    bignum_pow_mod_faster(&A, &b, &prime, &K_b); // B^b mod prime = K
    print(&K_b, "K_b");

    printf("COMP K_a == K_b = %s\n", (bignum_cmp(&K_a,&K_b)==0?"EQUAL":"NOT EQUAL"));
    printf("K_a is %s\n", (bignum_is_zero(&K_a)==1?"ZERO":"NOT ZERO"));
    printf("K_b is %s\n", (bignum_is_zero(&K_b)==1?"ZERO":"NOT ZERO"));
}

void print(struct bn* n, char* c){
    int i;
    printf("%s: ",c);
    for(i=0; i < BN_ARRAY_SIZE; i++)
        printf("%02x ",n->array[i]);
    printf("\n");
    printf("\n");
}

./test_random 3 0100 80 02

test_random: bn.c:104: bignum_from_string: Assertion `(nbytes % (sizeof(uint32_t) * 2)) == 0 && "string length must be a multiple of (sizeof(DTYPE) * 2) characters"' failed.
Aborted (core dumped)

are there any links to performance comparisons against GMP?

is there any planned work to support negative integers?

links

see also ilia3101/Big-Integer-C#1

in function bignum_add at line 215

DTYPE_TMP tmp;
int carry = 0;
for (i = 0; i < BN_ARRAY_SIZE; ++i)
{
  tmp = a->array[i] + b->array[i] + carry;
  carry = (tmp > MAX_VAL);  // will always be false
  c->array[i] = (tmp & MAX_VAL);
}

tmp > MAX_VAL will always be false because the result of a->array[i] + b->array[i] + carry will always be truncated to DTYPE.
To verify that you can try bignum_add between -1 and 3
To fix it, convert the type of a->array[i] to DTYPE_TMP.