From 1e6d868791ef0c22b86c620a6d38c0a7fe964c61 Mon Sep 17 00:00:00 2001 From: erdgeist Date: Wed, 22 Oct 2014 16:32:32 +0200 Subject: Sync state of development with the other repository I've been working in --- powm.c | 773 +++++++++++++++-------------------------------------------------- powm.h | 44 ++++ 2 files changed, 218 insertions(+), 599 deletions(-) create mode 100644 powm.h diff --git a/powm.c b/powm.c index 5c281a6..1f0b0c7 100644 --- a/powm.c +++ b/powm.c @@ -1,249 +1,89 @@ +#include "powm.h" #include #include +#include #include #include #include /* -This code implements base ^ exp mod p with base being a small integer, -g given in g_prime and the r number of bits (4096) being used to pre-calculate -g_r_square = r^2 mod p in order to speed up montgomery reduction +This code implements result = base ^ exp (mod m) -Because our primes conveniently end in 0xf..f for word sizes up to 64, the -multiplicative inverse is ("pre-calculated") g_r_inverse = 1. +Internally bignums are represented by limbs of type limb_t ordered in little +endian (LLF). -Todo: check if little endian internal representation is more efficient, also -write an import/export function for the exponent/result from big endian uint8_t -representation which is the default transport representation. - -Currently, with gcc -O3, we measure at around 2,75x the time libgmp needs for -it's powm which is not so bad, considering we don't use any assembler optimization. +Currently, with gcc -O3, we measure at around 2,3x the time libgmp needs for +it's powm which is not so bad, considering we don't use any assembler +optimization. Hot spot function is mp_mul_uint_add. -When we're done measuring, we should set PREVENT_TIMING_ATTACKS so that powm() -does not leak information about the number of bits set, but on average doubling the -time needed. Discuss ;) +We should set PREVENT_TIMING_ATTACKS so that powm() does not leak information +about the number of bits set, but on average doubling the time needed. */ -#if 0 -typedef uint32_t leg_t; -typedef uint64_t dleg_t; -#else -typedef uint64_t leg_t; -typedef unsigned int uint128_t __attribute__((mode(TI))); -typedef uint128_t dleg_t; -#endif - -//#define WITH_MEASURE_GMP -//#define WITH_PREVENT_TIMING_ATTACKS -//#define WITH_TESTS +#define WITH_PREVENT_TIMING_ATTACKS //#define WITHOUT_UNROLLING #define WITH_ROUNDS 128 - -#ifdef WITH_TESTS -static int run_tests( ); -#define KARATSUBA_THRESHOLD 4 -#else #define KARATSUBA_THRESHOLD 16 -#endif - -#ifdef WITH_MEASURE_GMP -#include -#endif - -#ifdef DEBUG_FUNCTIONS -static void dump_int( int level, char * prefix, leg_t const * p, int l, int nl ) -{ - printf( "L%d %s: ", level, prefix ); - while( l-- ) - printf( "%08llX", p[l] ); - if( nl ) - putchar( 10 ); -} -#endif - -/* Test values for smaller legs sizes */ -#if 0 -static leg_t g_prime[] = { 4293918689 }; -static leg_t g_r_square[] = { 333456065 }; -static leg_t g_r_inverse = 4192173023; -#endif - -#if 0 -static leg_t g_prime[] = { 0xFFFFFFFF, 0xFFFFFFA1 }; -/* g_prime == 18446744073709551521 */ -/* g_r == 18446744073709551616 */ -/* g_r^2 == 340282366920938463463374607431768211456 */ -static leg_t g_r_square[] = { 0, 9025 }; -/* g_prime^-1 mod g_r = 12815632724892951649 */ -static leg_t g_r_inverse = 3571604383; -#endif - -#if 0 -static leg_t g_prime[] = { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffff61 }; -/* g_prime == 340282366920938463463374607431768211297 */ -/* g_r == 340282366920938463463374607431768211456 */ -/* g_r^2 == 115792089237316195423570985008687907853269984665640564039457584007913129639936 */ -static leg_t g_r_square[] = { 0, 0, 0, 25281 }; -/* g_prime^-1 mod g_r = 104866892950477891256008526818595234977 */ -static leg_t g_r_inverse = 783358815; -#endif - -#if 0 -static leg_t g_prime[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x61 }; -/* g_prime == 340282366920938463463374607431768211297 */ -/* g_r == 340282366920938463463374607431768211456 */ -/* g_r^2 == 115792089237316195423570985008687907853269984665640564039457584007913129639936 */ -static leg_t g_r_square[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x62, 0xc1 }; -/* g_prime^-1 mod g_r = 104866892950477891256008526818595234977 */ -static leg_t g_r_inverse = 0x5f; -#endif - -#if 0 -/* Standard prime for leg_t defined as uint32_t */ -static const leg_t g_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, 0x8AAAC42D, 0xAD33170D, 0x04507A33, - 0xA85521AB, 0xDF1CBA64, 0xECFB8504, 0x58DBEF0A, 0x8AEA7157, 0x5D060C7D, 0xB3970F85, 0xA6E1E4C7, - 0xABF5AE8C, 0xDB0933D7, 0x1E8C94E0, 0x4A25619D, 0xCEE3D226, 0x1AD2EE6B, 0xF12FFA06, 0xD98A0864, - 0xD8760273, 0x3EC86A64, 0x521F2B18, 0x177B200C, 0xBBE11757, 0x7A615D6C, 0x770988C0, 0xBAD946E2, - 0x08E24FA0, 0x74E5AB31, 0x43DB5BFC, 0xE0FD108E, 0x4B82D120, 0xA9210801, 0x1A723C12, 0xA787E6D7, - 0x88719A10, 0xBDBA5B26, 0x99C32718, 0x6AF4E23C, 0x1A946834, 0xB6150BDA, 0x2583E9CA, 0x2AD44CE8, - 0xDBBBC2DB, 0x04DE8EF9, 0x2E8EFC14, 0x1FBECAA6, 0x287C5947, 0x4E6BC05D, 0x99B2964F, 0xA090C3A2, - 0x233BA186, 0x515BE7ED, 0x1F612970, 0xCEE2D7AF, 0xB81BDD76, 0x2170481C, 0xD0069127, 0xD5B05AA9, - 0x93B4EA98, 0x8D8FDDC1, 0x86FFB7DC, 0x90A6C08F, 0x4DF435C9, 0x34063199, 0xFFFFFFFF, 0xFFFFFFFF -}; - -static const leg_t g_r_square[] = { - 0x3DA97659, 0xE280DB0B, 0xE65BCC3A, 0xB78FDAA9, 0xB7B768C8, 0x9931D78D, 0xF8B11725, 0x339EBC93, - 0xAA7FBD95, 0x62059F1F, 0x4C2DE67D, 0xAD47527E, 0x526A653A, 0x7A674BD5, 0x5401EA4F, 0x3ED73A2F, - 0x70B56F52, 0x7F6F604F, 0xF3E56CC2, 0xBD9F048C, 0xFEA80D9A, 0x6EC9FCD3, 0x3AD36FD8, 0x22C39F34, - 0x91F30C52, 0xF798DA6A, 0x18C3DCE2, 0x0188D84C, 0xCB225176, 0x259E080F, 0xA89D1DCD, 0x9D381CC5, - 0xBEACD46F, 0x3CDD1196, 0x91A4F557, 0x2929B90C, 0x67DE8FA0, 0x23864714, 0xC28A61D4, 0x7411402D, - 0x6C09060D, 0x41058639, 0xE4FCCF1D, 0x638F4566, 0x9E10FDE2, 0x8E54806B, 0xF1D27D0B, 0x5C7DC9C2, - 0xB616D6FA, 0x8BE2C91D, 0xE8105464, 0xE9F80A5F, 0x34720869, 0x90DACF1A, 0x7E2C75A5, 0x8E25F142, - 0x8FB4832E, 0xF827DE84, 0xCA06DA91, 0xC2B3E7E2, 0x4F024193, 0x787A8278, 0x8BD70562, 0xDA60E392, - 0x46BDB733, 0x6E8452D9, 0x1D7D37A2, 0x3FB8CF61, 0xB18A9EF1, 0x50C8953A, 0xC93919D1, 0x2A4B1A67, - 0xFDC65A26, 0x9B51C1EF, 0x09954843, 0x20E739F4, 0x6C7951A5, 0x23CEF785, 0xE60C6EFD, 0xFFB7A9A9, - 0x5F666146, 0xCB441F59, 0xAE01E0F3, 0x63A9315D, 0x04BA044A, 0xEB4EEFD4, 0x8563215F, 0x72C8D989, - 0x62D21877, 0x1296EF6A, 0x20BD72B9, 0xB21E6B3D, 0x53C44FAB, 0x734810F7, 0xD203A9E0, 0xD7CE25D0, - 0x2E52989E, 0xCCF85F34, 0x912A0491, 0x3E9EBD87, 0x8267537D, 0x4A612A18, 0x51E75D99, 0x98F001DB, - 0xC9C77F0C, 0x352D408C, 0xA796D182, 0x04A636F7, 0xE4404092, 0x1C1E467C, 0x524E7C7A, 0x7ED36C41, - 0x2A434CEB, 0x230B2DFE, 0x3549C577, 0x7A17FB04, 0xB850DE95, 0xD97AC40A, 0x55EA6F75, 0x41C4F82B, - 0x37BF90FE, 0x52074F19, 0xFA8F75F0, 0x067E82B1, 0x8A1AC024, 0xB30E9B12, 0xC14AB0DD, 0xCC03AA20 -}; - -static const leg_t g_r_inverse = 1; -*/ -#endif - -#if 1 -/* Standard prime for leg_t defined as uint64_t */ -static const leg_t g_prime[] = { - 0xFFFFFFFFFFFFFFFF, 0x4DF435C934063199, 0x86FFB7DC90A6C08F, 0x93B4EA988D8FDDC1, - 0xD0069127D5B05AA9, 0xB81BDD762170481C, 0x1F612970CEE2D7AF, 0x233BA186515BE7ED, - 0x99B2964FA090C3A2, 0x287C59474E6BC05D, 0x2E8EFC141FBECAA6, 0xDBBBC2DB04DE8EF9, - 0x2583E9CA2AD44CE8, 0x1A946834B6150BDA, 0x99C327186AF4E23C, 0x88719A10BDBA5B26, - 0x1A723C12A787E6D7, 0x4B82D120A9210801, 0x43DB5BFCE0FD108E, 0x08E24FA074E5AB31, - 0x770988C0BAD946E2, 0xBBE117577A615D6C, 0x521F2B18177B200C, 0xD87602733EC86A64, - 0xF12FFA06D98A0864, 0xCEE3D2261AD2EE6B, 0x1E8C94E04A25619D, 0xABF5AE8CDB0933D7, - 0xB3970F85A6E1E4C7, 0x8AEA71575D060C7D, 0xECFB850458DBEF0A, 0xA85521ABDF1CBA64, - 0xAD33170D04507A33, 0x15728E5A8AAAC42D, 0x15D2261898FA0510, 0x3995497CEA956AE5, - 0xDE2BCBF695581718, 0xB5C55DF06F4C52C9, 0x9B2783A2EC07A28F, 0xE39E772C180E8603, - 0x32905E462E36CE3B, 0xF1746C08CA18217C, 0x670C354E4ABC9804, 0x9ED529077096966D, - 0x1C62F356208552BB, 0x83655D23DCA3AD96, 0x69163FA8FD24CF5F, 0x98DA48361C55D39A, - 0xC2007CB8A163BF05, 0x49286651ECE45B3D, 0xAE9F24117C4B1FE6, 0xEE386BFB5A899FA5, - 0x0BFF5CB6F406B7ED, 0xF44C42E9A637ED6B, 0xE485B576625E7EC6, 0x4FE1356D6D51C245, - 0x302B0A6DF25F1437, 0xEF9519B3CD3A431B, 0x514A08798E3404DD, 0x020BBEA63B139B22, - 0x29024E088A67CC74, 0xC4C6628B80DC1CD1, 0xC90FDAA22168C234, 0xFFFFFFFFFFFFFFFF - }; - -static const leg_t g_r_square[] = { - 0xC14AB0DDCC03AA20, 0x8A1AC024B30E9B12, 0xFA8F75F0067E82B1, 0x37BF90FE52074F19, - 0x55EA6F7541C4F82B, 0xB850DE95D97AC40A, 0x3549C5777A17FB04, 0x2A434CEB230B2DFE, - 0x524E7C7A7ED36C41, 0xE44040921C1E467C, 0xA796D18204A636F7, 0xC9C77F0C352D408C, - 0x51E75D9998F001DB, 0x8267537D4A612A18, 0x912A04913E9EBD87, 0x2E52989ECCF85F34, - 0xD203A9E0D7CE25D0, 0x53C44FAB734810F7, 0x20BD72B9B21E6B3D, 0x62D218771296EF6A, - 0x8563215F72C8D989, 0x04BA044AEB4EEFD4, 0xAE01E0F363A9315D, 0x5F666146CB441F59, - 0xE60C6EFDFFB7A9A9, 0x6C7951A523CEF785, 0x0995484320E739F4, 0xFDC65A269B51C1EF, - 0xC93919D12A4B1A67, 0xB18A9EF150C8953A, 0x1D7D37A23FB8CF61, 0x46BDB7336E8452D9, - 0x8BD70562DA60E392, 0x4F024193787A8278, 0xCA06DA91C2B3E7E2, 0x8FB4832EF827DE84, - 0x7E2C75A58E25F142, 0x3472086990DACF1A, 0xE8105464E9F80A5F, 0xB616D6FA8BE2C91D, - 0xF1D27D0B5C7DC9C2, 0x9E10FDE28E54806B, 0xE4FCCF1D638F4566, 0x6C09060D41058639, - 0xC28A61D47411402D, 0x67DE8FA023864714, 0x91A4F5572929B90C, 0xBEACD46F3CDD1196, - 0xA89D1DCD9D381CC5, 0xCB225176259E080F, 0x18C3DCE20188D84C, 0x91F30C52F798DA6A, - 0x3AD36FD822C39F34, 0xFEA80D9A6EC9FCD3, 0xF3E56CC2BD9F048C, 0x70B56F527F6F604F, - 0x5401EA4F3ED73A2F, 0x526A653A7A674BD5, 0x4C2DE67DAD47527E, 0xAA7FBD9562059F1F, - 0xF8B11725339EBC93, 0xB7B768C89931D78D, 0xE65BCC3AB78FDAA9, 0x3DA97659E280DB0B -}; - -static const leg_t g_r_inverse = 1; -#endif /* Returns 0 if a and b are equal, -1 if a < b, 1 if a > b */ -static int mp_cmp( leg_t const *a, leg_t const *b, int legs ) +static int mp_cmp( limb_t const *a, limb_t const *b, int limbs ) { - while( legs-- ) + while( limbs-- ) { - if( a[legs] < b[legs] ) return -1; - if( a[legs] > b[legs] ) return 1; + if( a[limbs] < b[limbs] ) return -1; + if( a[limbs] > b[limbs] ) return 1; } return 0; } /* Subtract b from a, store in a. Expects enough words prepended to borrow from */ -static void mp_sub( leg_t *a, leg_t const *b, int legs ) +static void mp_sub( limb_t *a, limb_t const *b, int limbs ) { int borrow = 0, borrow_temp; - while( legs-- ) + while( limbs-- ) { - leg_t temp = *a - *(b++); + limb_t temp = *a - *(b++); borrow_temp = temp > *a; *a = temp - borrow; borrow = borrow_temp | ( *(a++) > temp ); } while( borrow ) { - leg_t temp = *a - borrow; + limb_t temp = *a - borrow; borrow = temp > *a; *(a++) = temp; } } -/* Add b to a, store in a. Operates on legs + flegs words, with - flegs the amount of legs to propagate the carry to */ -static void mp_add( leg_t *a, leg_t const *b, int legs, int flegs ) +/* Add b to a, store in a. Operates on limbs + flimbs words, with + flimbs the amount of limbs to propagate the carry to */ +static void mp_add( limb_t *a, limb_t const *b, int limbs, int flimbs ) { - dleg_t acc = 0; - while( legs-- ) + dlimb_t acc = 0; + while( limbs-- ) { - acc += (dleg_t)*a + (dleg_t)*(b++); - *(a++) = (leg_t)acc; - acc >>= 8*sizeof(leg_t); + acc += (dlimb_t)*a + (dlimb_t)*(b++); + *(a++) = (limb_t)acc; + acc >>= 8*sizeof(limb_t); } - while( acc && flegs-- ) + while( acc && flimbs-- ) { - acc += (dleg_t)*a; - *(a++) = (leg_t)acc; - acc >>= 8*sizeof(leg_t); + acc += (dlimb_t)*a; + *(a++) = (limb_t)acc; + acc >>= 8*sizeof(limb_t); } } /* Subtract b from a and store in result. Expects nothing to borrow.*/ -static void mp_sub_mod( leg_t * result, leg_t const *a, leg_t const * b, int legs ) +static void mp_sub_mod( limb_t * result, limb_t const *a, limb_t const * b, int limbs ) { int borrow = 0, borrow_temp; - while( legs-- ) + while( limbs-- ) { - leg_t temp = *a - *(b++); + limb_t temp = *a - *(b++); borrow_temp = temp > *(a++); *result = temp - borrow; borrow = borrow_temp | (*(result++) > temp ); @@ -251,119 +91,120 @@ static void mp_sub_mod( leg_t * result, leg_t const *a, leg_t const * b, int leg } /* Fast negate */ -static void mp_negate( leg_t * p, int legs ) +static void mp_negate( limb_t * p, int limbs ) { /* Only as long as we find 0 along the way, we need to propagate the carry of -x == !x+1 */ int carry = 1; - while( legs-- ) + while( limbs-- ) { - leg_t v = carry + ( *p ^ (leg_t)-1 ); + limb_t v = carry + ( *p ^ (limb_t)-1 ); if(v) carry = 0; *(p++)=v; } } /* Multiplies a with fac, adds to result. - result is guaranteed to be initialized with enough legs prepended to take the carry */ -static void mp_mul_uint_add( leg_t *result, leg_t const *a, leg_t fac, int legs ) + result is guaranteed to be initialized with enough limbs prepended to take the carry */ +static void mp_mul_uint_add( limb_t *result, limb_t const *a, limb_t fac, int limbs ) { - dleg_t acc8 = 0; + dlimb_t acc15 = 0; #ifndef WITHOUT_UNROLLING - dleg_t acc1 = 0, acc2 = 0, acc3 = 0, acc4 = 0; - dleg_t acc5 = 0, acc6 = 0, acc7 = 0; + dlimb_t acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0; + dlimb_t acc4 = 0, acc5 = 0, acc6 = 0, acc7 = 0; + dlimb_t acc8 = 0, acc9 = 0, acc10= 0, acc11= 0; + dlimb_t acc12= 0, acc13= 0, acc14= 0; - while( legs >= 8 ) + while( limbs >= 16 ) { - acc1 = ( acc8 >> 8*sizeof(leg_t) ) + (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc1; - - acc2 = ( acc1 >> 8*sizeof(leg_t) ) + (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc2; - - acc3 = ( acc2 >> 8*sizeof(leg_t) ) + (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc3; - - acc4 = ( acc3 >> 8*sizeof(leg_t) ) + (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc4; - - acc5 = ( acc4 >> 8*sizeof(leg_t) ) + (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc5; - - acc6 = ( acc5 >> 8*sizeof(leg_t) ) + (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc6; - - acc7 = ( acc6 >> 8*sizeof(leg_t) ) + (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc7; - - acc8 = ( acc7 >> 8*sizeof(leg_t) ) + (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc8; - - legs -= 8; +#define MUL_UINT_ADD_ROUND(ACC,CARRY) \ + acc##ACC = ( acc##CARRY >> 8*sizeof(limb_t) ) + (dlimb_t)result[ACC] + (dlimb_t)a[ACC] * (dlimb_t)fac; \ + result[ACC] = (limb_t)acc##ACC; + + MUL_UINT_ADD_ROUND(0,15) + MUL_UINT_ADD_ROUND(1,0) + MUL_UINT_ADD_ROUND(2,1) + MUL_UINT_ADD_ROUND(3,2) + MUL_UINT_ADD_ROUND(4,3) + MUL_UINT_ADD_ROUND(5,4) + MUL_UINT_ADD_ROUND(6,5) + MUL_UINT_ADD_ROUND(7,6) + MUL_UINT_ADD_ROUND(8,7) + MUL_UINT_ADD_ROUND(9,8) + MUL_UINT_ADD_ROUND(10,9) + MUL_UINT_ADD_ROUND(11,10) + MUL_UINT_ADD_ROUND(12,11) + MUL_UINT_ADD_ROUND(13,12) + MUL_UINT_ADD_ROUND(14,13) + MUL_UINT_ADD_ROUND(15,14) + + result += 16; + a += 16; + limbs -= 16; } - acc8 >>= 8*sizeof(leg_t); + acc15 >>= 8*sizeof(limb_t); #endif - while( legs-- ) + while( limbs-- ) { - acc8 += (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac; - *(result++) = (leg_t)acc8; - acc8 >>= 8*sizeof(leg_t); + acc15 += (dlimb_t)*result + (dlimb_t)*(a++) * (dlimb_t)fac; + *(result++) = (limb_t)acc15; + acc15 >>= 8*sizeof(limb_t); } - while( acc8 ) + while( acc15 ) { - acc8 += (dleg_t)*result; - *(result++) = (leg_t)acc8; - acc8 >>= 8*sizeof(leg_t); + acc15 += (dlimb_t)*result; + *(result++) = (limb_t)acc15; + acc15 >>= 8*sizeof(limb_t); } } /* Multiplies a and b, adds to result, base case version. */ -static void mp_mul_oper_add( leg_t * result, leg_t const *a, leg_t const *b, int legs ) +static void mp_mul_oper_add( limb_t * result, limb_t const *a, limb_t const *b, int limbs ) { - int leg = legs; - while( leg-- ) - mp_mul_uint_add( result++, a, *(b++), legs ); + int limb = limbs; + while( limb-- ) + mp_mul_uint_add( result++, a, *(b++), limbs ); } /* Optimized mp_mul_oper_add for a == b, i.e. squaring */ -static void mp_sqr( leg_t *result, leg_t const * a, int legs ) +static void mp_sqr( limb_t *result, limb_t const * a, int limbs ) { - while( legs-- ) { - leg_t fac = *(a++), *dest = result; - leg_t const *src = a; - int leg = legs; + while( limbs-- ) { + limb_t fac = *(a++), *dest = result; + limb_t const *src = a; + int limb = limbs; - dleg_t acc = (dleg_t)*dest + (dleg_t)fac * (dleg_t)fac; + dlimb_t acc = (dlimb_t)*dest + (dlimb_t)fac * (dlimb_t)fac; - *(dest++) = (leg_t)acc; - acc >>= 8*sizeof(leg_t); + *(dest++) = (limb_t)acc; + acc >>= 8*sizeof(limb_t); - while( leg-- ) + while( limb-- ) { - dleg_t subresult = (dleg_t)fac * (dleg_t)*(src++); - int carry = !!( subresult >> (16*sizeof(leg_t)-1)); + dlimb_t subresult = (dlimb_t)fac * (dlimb_t)*(src++); + int carry = !!( subresult >> (16*sizeof(limb_t)-1)); - acc += 2 * subresult + (dleg_t)*dest; - *(dest++) = (leg_t)acc; + acc += 2 * subresult + (dlimb_t)*dest; + *(dest++) = (limb_t)acc; - acc >>= 8*sizeof(leg_t); - acc += (dleg_t)carry << 8*sizeof(leg_t); + acc >>= 8*sizeof(limb_t); + acc += (dlimb_t)carry << 8*sizeof(limb_t); } while( acc ) { - acc += (dleg_t)*dest; - *(dest++) = (leg_t)acc; - acc >>= 8*sizeof(leg_t); + acc += (dlimb_t)*dest; + *(dest++) = (limb_t)acc; + acc >>= 8*sizeof(limb_t); } result += 2; } } /* Optimized karatsuba (toom2.2) for a == b, i.e. squaring */ -static void mp_mul_kara_square( leg_t* p, leg_t const *a, int len, leg_t *scratch ) +static void mp_mul_kara_square( limb_t* p, limb_t const *a, int len, limb_t *scratch ) { - memset( p, 0, 2 * len * sizeof( leg_t )); + memset( p, 0, 2 * len * sizeof( limb_t )); if( len <= KARATSUBA_THRESHOLD ) mp_sqr( p, a, len ); else @@ -389,9 +230,9 @@ static void mp_mul_kara_square( leg_t* p, leg_t const *a, int len, leg_t *scratc } /* karatsuba (toom2.2), generic */ -static void mp_mul_kara( leg_t* p, leg_t const *a, leg_t const *b, int len, leg_t *scratch ) +static void mp_mul_kara( limb_t* p, limb_t const *a, limb_t const *b, int len, limb_t *scratch ) { - memset( p, 0, 2 * len * sizeof( leg_t )); + memset( p, 0, 2 * len * sizeof( limb_t )); if( len <= KARATSUBA_THRESHOLD ) mp_mul_oper_add( p, a, b, len ); else @@ -428,398 +269,132 @@ static void mp_mul_kara( leg_t* p, leg_t const *a, leg_t const *b, int len, leg_ } } -/* Multiply a and b, store in a, work in montgomery domain - to achieve multiply, a needs to be reduced by k * g_prime - until all lower legs are 0, allowing exact division by 2^r +/* Multiply a and b, store in a, work in montgomery domain to achieve multiply, + a needs to be reduced by k * modulus (with k being the unknown integer) + until all lower limbs are 0, allowing exact division (via implicit shift) + by 2^r - if !do_mul, we convert from montgomery domain back to - g_prime domain and thus only multiply by 1 before reducing + if !do_mul, we convert from montgomery domain back to modulus domain and + thus only multiply by 1 before reducing */ -static void redc( leg_t *a, leg_t const *b, int legs, int do_mul ) +static void redc( limb_t * a, + const limb_t * b, int limbs, + const limb_t * modulus, limb_t r_inverse, int do_mul ) { - leg_t scratch[ 2 * ( legs - KARATSUBA_THRESHOLD ) ]; - leg_t temp[1 + 2 * legs]; - leg_t leg; + limb_t scratch[ 2 * ( limbs - KARATSUBA_THRESHOLD ) ]; + limb_t temp[ 1 + 2 * limbs ]; + int limb; /* Not necessary for transforming back */ if( do_mul ) { - temp[2*legs] = 0; + temp[2*limbs] = 0; if( a == b ) - mp_mul_kara_square( temp, a, legs, scratch ); + mp_mul_kara_square( temp, a, limbs, scratch ); else - mp_mul_kara( temp, a, b, legs, scratch ); + mp_mul_kara( temp, a, b, limbs, scratch ); } else { - memset( temp + legs, 0, (legs + 1 ) * sizeof(leg_t)); - memcpy( temp, a, legs * sizeof(leg_t)); + memset( temp + limbs, 0, (limbs + 1) * sizeof(limb_t)); + memcpy( temp, a, limbs * sizeof(limb_t)); } /* m = p * ( m * R_1 ) % R */ - for( leg = 0; leg < legs; ++leg ) + for( limb = 0; limb < limbs; ++limb ) { - leg_t k = temp[leg] * g_r_inverse; - mp_mul_uint_add( temp+leg, g_prime, k, legs ); + limb_t k = temp[limb] * r_inverse; + mp_mul_uint_add( temp+limb, modulus, k, limbs ); } - /* the lower legs of temp are now zero - if necessary, reduce temp to fit in legs */ - if( temp[2*legs] || mp_cmp( temp + legs, g_prime, legs ) > 0 ) - mp_sub( temp + legs, g_prime, legs ); + /* the lower limbs of temp are now zero + if necessary, reduce temp to fit in limbs */ + if( temp[2*limbs] || mp_cmp( temp + limbs, modulus, limbs ) > 0 ) + mp_sub( temp + limbs, modulus, limbs ); - memcpy( a, temp + legs, legs * sizeof(leg_t) ); - memset( scratch, 0, sizeof( scratch ) ); - memset( temp, 0, sizeof( temp ) ); + memcpy( a, temp + limbs, limbs * sizeof(limb_t) ); + memset( scratch, 0, sizeof(scratch)); + memset( temp, 0, sizeof(temp)); } -/* calculate base ^ exponent modulo g_prime */ -static void powm( leg_t * result, leg_t const *exponent, leg_t base, int legs ) +/* calculate base ^ exponent modulo modulus */ +void powm_internal( limb_t * result, + const limb_t * base, uint32_t base_limbs, + const limb_t * exponent, uint32_t exp_limbs, + const limb_t * modulus, uint32_t mod_limbs, + const limb_t * r_square, const limb_t r_inverse ) { - leg_t acc[legs]; + limb_t acc[mod_limbs]; #ifdef WITH_PREVENT_TIMING_ATTACKS - leg_t dummy[legs]; + limb_t dummy[mod_limbs]; #endif int first = 0, bit; + int expbits = 8 * sizeof(limb_t) * exp_limbs; + + memset( result, 0, sizeof(limb_t) * mod_limbs ); + memset( acc, 0, sizeof(limb_t) * mod_limbs ); - memset( acc, 0, sizeof(acc) ); - *acc = base; + memcpy( acc, base, sizeof(limb_t) * base_limbs ); + //*acc = base; /* Transform base into montgomery domain */ - redc( acc, g_r_square, legs, 1 ); + redc( acc, r_square, mod_limbs, modulus, r_inverse, 1 ); /* mul in temp and if bit set in exponent, multiply into accumulator */ - for( bit = 0; bit < legs * 8 * sizeof(leg_t); bit++ ) + for( bit = 0; bit < expbits ; bit++ ) { - int this_bit = bit % ( sizeof(leg_t) * 8 ); - if( ( exponent[ bit / ( sizeof(leg_t) * 8 ) ] >> this_bit ) & 1 ) { + int this_bit = bit % ( sizeof(limb_t) * 8 ); + if( ( exponent[ bit / ( sizeof(limb_t) * 8 ) ] >> this_bit ) & 1 ) { if( first++ ) - redc( result, acc, legs, 1 ); + redc( result, acc, mod_limbs, modulus, r_inverse, 1 ); else - memcpy( result, acc, sizeof(leg_t) * legs ); + memcpy( result, acc, sizeof(limb_t) * mod_limbs ); } #ifdef WITH_PREVENT_TIMING_ATTACKS else - redc( dummy, acc, legs, 1 ); + redc( dummy, acc, mod_limbs, modulus, r_inverse, 1 ); #endif - redc( acc, acc, legs, 1 ); + redc( acc, acc, mod_limbs, modulus, r_inverse, 1 ); } - /* Transform result in acc back into mod p domain */ + /* Transform result in acc back into mod m domain */ if( first ) - redc( result, 0, legs, 0 ); - else /* base ^ 0 mod p = 1 */ + redc( result, 0, mod_limbs, modulus, r_inverse, 0 ); + else /* base ^ 0 mod m = 1 */ { - memset( result+1, 0, legs * sizeof(leg_t) ); + memset( result+1, 0, mod_limbs * sizeof(limb_t) ); *result = 1; } } -static void mp_import( leg_t *dest, uint8_t const * src, size_t len ) +uint32_t mp_import( limb_t *dest, uint8_t const * src, uint32_t len ) { int byte = 0; - leg_t acc = 0; + limb_t *d = dest; + limb_t acc = 0; + while( len-- ) { - acc |= ((leg_t)src[len]) << ( 8 * byte ); - if( ++byte == sizeof(leg_t)) + acc |= ((limb_t)src[len]) << ( 8 * byte ); + if( ++byte == sizeof(limb_t)) { - *(dest++) = acc; + *(d++) = acc; acc = 0; byte = 0; } } if( byte ) - *dest = acc; + *(d++) = acc; + return ( d - dest ); } -int main() +void mp_export( uint8_t * dest, const limb_t * src, uint32_t limb_size ) { - int i, legs = 64; - leg_t input[ /*legs*/ ] = { - 0x281b04b30bb62984, 0xe0cc506399225574, 0xb08ad95f8040183f, 0x56eee1ba0dc1936c, - 0x5ec1d62932d6937a, 0xfa8718685a5b8359, 0xfb4e8dadb3111df4, 0x87e90f5b6397727e, - 0x6b984d2e7b9cc244, 0x9ae478fd69254dc9, 0x21da1ef76099ed94, 0xe407bde8519bc534, - 0x051a88159adc842b, 0x547fd48d3b471c7c, 0xd6b85c29e8e8a528, 0x74fc0b5dcdfaa679, - 0xe0c022a74c073360, 0xc0dc8c759af7492b, 0xa86946df6abbea0f, 0xfcc2a7f6d4b0d4f7, - 0xd2111f6ce69c2bc6, 0x4ab8b5e0adaad6a0, 0xf8df973a9842e7b2, 0x2d44f438b889673c, - 0x82b4e75bf0e60d06, 0x4c3b1333a07fee24, 0x353eb64e067f86cc, 0x518781609b447bf8, - 0xe9228ae741da24cd, 0xd8aec44d430026aa, 0x196bcb0cc0e353f8, 0x942fad7b2cc3dcc5, - 0xa77b229138f2d5d1, 0x5479eaeb9b64ba87, 0x70cc7ff6ea8f1b51, 0x1785bbfb88755c99, - 0xd7ac4896d4e08b35, 0x0e2aab629710919b, 0xa3612061c92319ce, 0xb5444312b3b43541, - 0xa13b801d1ac631d5, 0x87e0db1397d9f2fd, 0x0e84ab94e744b8ba, 0x1f61b1ea0e5aafb4, - 0x70f0c055dde43121, 0x094d72c301b8f25d, 0xd151e2770baec00b, 0x31052a6fc332563d, - 0x2bca50f311573101, 0xb420bd7e538ef88b, 0xac5ecd1fe4997513, 0x3ca892560247ca32, - 0x950e895d7777d182, 0xcb650843a43a4a00, 0xd07dc909e7070b0e, 0x72d720399b4ad2d4, - 0x52292d56ea2960a9, 0x6060e2cd96000219, 0x118727b5eb17dfbd, 0xa6d78571af8d3688, - 0xb563a9cf79c6eaec, 0xe5d85f8fb8fced5c, 0x9ac2961fe160f837, 0x1de7eae6c0d6a0b0, - }; - - leg_t res[legs]; /* -= { 569D056BC5485C6F3C026935CFC1FC36CFC5A6B770B442323750EE08A32C63F64743A4902E32A41F7C5A9097509EB9AAA5C5B425D9BDAEDC3B98EE3A9F99AE6FB8723EBE01154937ECC1E4AE38CBC12B767FD17264A4AAEB310EA5B0E72D12FE3969532C5A0718B45F251BFB2A126EFB87F819BDCD434EAEE3B9108C387F4DFFEFA0E9532A0532192034DB0EF5C5BB2A77BCA5B4A08DFFD22F6B1D4F17F5123935CAB4F40EC7E77F4FEEEC6A8CD20CDB2D37DD1BB44544C50B01E98F8B3F5E1ABF91817D40B7E526D6ED80CDE416C6CD32218D3ECCA753D15BBB007661754E44A937C5A68957C3C2D3F39A220930567E9F720B3AAE9D34FEBA6E5A047C131F32271A3BC1E85BC1BC210F49B09F3938226399991BC90299B4E0E684B2DE6BDA684693F40CF728FD24A4B1D1A2B8F4CD3316A02DBC44069A40C1AC64F862091A888DD284AB180918B379A3BD173EDDEA5E08DF4BE51B441AEA7EDA4E439CF57914F68E0FB3E756AB7286616C3736CA72DD40A88FC37B598BF561300AFD1F80F7D44E53C4C1D85FF215250A0C56222A177299C61C2E654B040176F4A8D44BE2612B36E066E7AA6E58D84D4C4CB9A5952E1668CDF04EE55C38ABA59614CB7F43D12921551DD82062AFC3F340B33F43C643BC9D5DB6D6BAB2C94F100D139443B20BCB80384C3231261C5ABFFF3D971CB878116F4EBB7D4D24A2B6F5869 } -*/ - -#ifdef WITH_TESTS - run_tests(); -#endif - -#ifdef WITH_MEASURE_GMP - mpz_t m, base, exp, result; - - mpz_init( m ); mpz_init( base ); mpz_init( exp ); mpz_init( result ); - mpz_import( m, sizeof(g_prime) / sizeof(uint64_t), -1, sizeof(uint64_t), 0, 0, g_prime ); - mpz_set_ui( base, 2 ); - mpz_import( exp, sizeof(input) / sizeof(uint64_t), -1, sizeof(uint64_t), 0, 0, input ); - - for( i=0; i< WITH_ROUNDS; ++i ) - mpz_powm( result, base, exp, m ); - - gmp_printf("%ZX\n", result); -#else - - for( i=0; i=0; --i ) - printf( "%016llX", res[i] ); - putchar(10); putchar(10); -#endif - - return 0; -} - -#ifdef WITH_TESTS -#define TEST_MAX 1024 -static void REPORT( char * fail ) { fprintf( stderr, "\nFailed in %s\n", fail ); exit(-1); } -static leg_t test_001[] = { (leg_t)-1, 1 }; -static leg_t test_002[] = { (leg_t)-1, 2 }; -static leg_t test_003[] = { 0, 1 }; -static leg_t test_004[] = { (leg_t)-1, 1, 1 }; -static leg_t test_005[] = { 0, (leg_t)-1, 0 }; -static leg_t test_006[] = { (leg_t)-2, 4, 0 }; -static leg_t test_007[] = { (leg_t)-1, (leg_t)-2 }; -static leg_t test_008[] = { (leg_t)-1, (leg_t)-3 }; -static leg_t test_009[] = { (leg_t)-2, (leg_t)-4, 0 }; -static leg_t test_010[] = { (leg_t)-2, (leg_t)-4, 1 }; - -static uint8_t test_011[] = { - 0xf2, 0xda, 0xe5, 0x35, 0xa0, 0xbd, 0xb8, 0x4c, 0x88, 0x65, 0x50, 0xca, 0xe8, 0x17, 0xa8, 0xab, 0x34, 0xd6, 0x86, 0xc4, 0x29, 0xa0, 0xc8, 0x51, 0x84, 0x05, 0x3e, 0x9d, 0x4d, 0x23, 0xce, 0x75, - 0x1f, 0xa6, 0xc1, 0x36, 0x86, 0x35, 0xf5, 0x6f, 0xcc, 0x0b, 0x13, 0x40, 0x89, 0xc2, 0x41, 0xb0, 0x0e, 0xa7, 0x68, 0xd4, 0x68, 0x6a, 0xd2, 0x08, 0xf7, 0xf5, 0x2c, 0x05, 0x11, 0x43, 0x00, 0x9b, - 0xf4, 0x92, 0xe1, 0x17, 0xae, 0xcc, 0x05, 0x98, 0x95, 0xc4, 0x33, 0xfd, 0x54, 0x42, 0x06, 0x98, 0x90, 0x62, 0x61, 0x15, 0x34, 0xe8, 0xbd, 0x37, 0xe0, 0x57, 0x27, 0x90, 0x75, 0x08, 0x33, 0x15, - 0xe5, 0x48, 0x19, 0xbb, 0x2c, 0xc1, 0xda, 0xeb, 0x95, 0x72, 0x97, 0x05, 0x60, 0xbf, 0xbf, 0x80, 0xfe, 0x04, 0x7a, 0x4a, 0xff, 0x0e, 0xa0, 0x47, 0x82, 0x0d, 0x90, 0xf0, 0x5b, 0xfc, 0x21, 0x82 -}; -static uint8_t test_012[] = { - 0x0c, 0xc4, 0xc0, 0xb7, 0x13, 0xee, 0xf6, 0xf3, 0xcd, 0xf7, 0x02, 0x0b, 0x97, 0x70, 0xc0, 0x59, 0x27, 0xd2, 0x74, 0xbf, 0x54, 0xbf, 0x9d, 0x77, 0x59, 0xe0, 0x86, 0x06, 0x18, 0x7a, 0x3c, 0x3e, - 0x12, 0x52, 0xed, 0x77, 0x10, 0xf9, 0x4b, 0xb8, 0xb7, 0x2b, 0xdc, 0x23, 0xe0, 0x45, 0x79, 0xe2, 0xe9, 0xef, 0x12, 0x97, 0x22, 0xf8, 0x72, 0xa2, 0x05, 0x1f, 0x5f, 0x36, 0xae, 0xfb, 0x7a, 0xb2, - 0x7d, 0xd7, 0xa2, 0x15, 0xa4, 0x9f, 0x27, 0x55, 0x65, 0x2a, 0x49, 0x0f, 0xca, 0x9f, 0xf3, 0xf6, 0x26, 0xcb, 0x57, 0x07, 0x82, 0xb7, 0x04, 0x1a, 0x7b, 0x65, 0x40, 0xb8, 0x55, 0x93, 0xee, 0xd4, - 0x09, 0x3e, 0x30, 0xa1, 0x6c, 0x00, 0x90, 0x54, 0x9b, 0x05, 0xb4, 0x08, 0xc4, 0xcc, 0xcd, 0xa2, 0xf6, 0xe6, 0x34, 0xf3, 0x5f, 0xe0, 0xe4, 0xb3, 0xcd, 0xd3, 0x8f, 0x83, 0xb2, 0xe8, 0x08, 0xb6 -}; -static uint8_t test_013[] = { - 0x0C, 0x1C, 0xE9, 0x27, 0xD9, 0xE2, 0xF8, 0x92, 0x97, 0x0B, 0x8E, 0x79, 0x91, 0x07, 0xE7, 0xAA, 0xF8, 0x5C, 0x11, 0xAB, 0x84, 0xFA, 0x0C, 0x6F, 0xED, 0xA5, 0x0C, 0x1F, 0x4C, 0x55, 0x5F, 0x5B, - 0x70, 0x63, 0x22, 0x85, 0x72, 0x6B, 0x3D, 0x9A, 0x78, 0x6E, 0xBF, 0x2E, 0x29, 0xB8, 0x2E, 0xE4, 0x4C, 0x09, 0x35, 0x45, 0x92, 0x26, 0xCC, 0x29, 0x15, 0xFC, 0x9A, 0x2F, 0x58, 0x4E, 0x70, 0xDD, - 0x00, 0xA9, 0xC7, 0xDE, 0xF5, 0x26, 0x85, 0x23, 0xDF, 0xBF, 0x00, 0x61, 0xC7, 0x47, 0x0E, 0x23, 0x9D, 0xC3, 0xB6, 0x17, 0x8C, 0x36, 0x19, 0x03, 0x70, 0xD1, 0xE1, 0xE7, 0x58, 0xDD, 0x10, 0xD5, - 0x76, 0x3B, 0xA7, 0xAE, 0x73, 0xAC, 0x4E, 0xBF, 0x4B, 0x79, 0xE5, 0xDE, 0x19, 0x68, 0x1D, 0x19, 0xD4, 0xF1, 0xF9, 0x90, 0x0B, 0x55, 0x9A, 0x8A, 0xAE, 0x5C, 0x85, 0x0C, 0x84, 0xB1, 0x33, 0x2F, - 0x0E, 0x99, 0xFC, 0xC6, 0x57, 0xE8, 0x81, 0x53, 0x23, 0x87, 0x5D, 0x41, 0xDF, 0xC9, 0xE0, 0xE5, 0xE1, 0x8C, 0x2C, 0x4E, 0x69, 0xAE, 0x99, 0x54, 0x19, 0x85, 0x7F, 0x7F, 0x19, 0x1E, 0x28, 0xC2, - 0x04, 0xAB, 0x16, 0x1D, 0xE9, 0x22, 0x55, 0xD2, 0x2D, 0x45, 0x44, 0xD2, 0x16, 0x3C, 0x2B, 0xD3, 0xE5, 0x88, 0xF2, 0x5E, 0x97, 0x92, 0x51, 0xF0, 0x64, 0x7D, 0x27, 0x5E, 0x0F, 0x5C, 0x99, 0xD8, - 0x02, 0xA8, 0xD3, 0x87, 0x90, 0x02, 0x9E, 0x4E, 0x9A, 0x9D, 0x72, 0xF3, 0xA8, 0xBC, 0x28, 0x74, 0xBD, 0x60, 0x92, 0xE1, 0x4A, 0x7E, 0x3E, 0xC2, 0xB3, 0x88, 0xBA, 0xAD, 0x8F, 0xFF, 0xCD, 0x57, - 0xE2, 0x7E, 0x43, 0x68, 0x91, 0xC3, 0xBE, 0x50, 0x9E, 0xB8, 0xFA, 0x53, 0x3C, 0xEE, 0x1F, 0x4C, 0x59, 0x5D, 0x4B, 0xE8, 0x42, 0x32, 0xD5, 0xE4, 0xFC, 0xD7, 0xFD, 0x12, 0x08, 0x1B, 0xE2, 0x6C -}; - -static uint8_t test_014[] = { - 0xE6, 0x62, 0x94, 0x84, 0x90, 0x75, 0x70, 0x5D, 0xF3, 0x6C, 0xC7, 0xFC, 0x45, 0x0C, 0x9F, 0xF7, 0x37, 0xB9, 0x71, 0x65, 0x62, 0x47, 0xC6, 0xD8, 0xFE, 0x93, 0xB0, 0xF1, 0xE2, 0x34, 0x78, 0x99, - 0xE1, 0xED, 0x3C, 0xA7, 0xF0, 0xD3, 0x00, 0x26, 0xA0, 0x18, 0xAA, 0x43, 0xDB, 0xFA, 0xD1, 0xFE, 0x2A, 0x71, 0xC5, 0xD1, 0xA1, 0x1D, 0xC0, 0xD3, 0x26, 0x15, 0x43, 0x6F, 0x06, 0x35, 0x5D, 0x02, - 0x3A, 0xFD, 0x58, 0xAA, 0x91, 0x4A, 0x27, 0xFC, 0xD5, 0x78, 0xBC, 0x65, 0xE6, 0xE6, 0xEC, 0x4E, 0x25, 0xBE, 0xEC, 0xDD, 0x82, 0xDB, 0x6D, 0xDE, 0x42, 0x4D, 0xE6, 0x39, 0x71, 0x80, 0x4B, 0xDA, - 0x2E, 0xD2, 0x25, 0x70, 0x96, 0x9D, 0x7B, 0x1B, 0x61, 0x85, 0xE6, 0x3C, 0x31, 0x4B, 0x60, 0x07, 0xCA, 0x66, 0xEF, 0x98, 0xEA, 0xAE, 0xED, 0xB8, 0x91, 0xC2, 0x8A, 0x70, 0x3B, 0xAC, 0x0B, 0x0A, - 0x3D, 0x80, 0xC9, 0x55, 0x96, 0x2F, 0xF3, 0xED, 0x55, 0xBC, 0x8B, 0x06, 0x62, 0xD9, 0x3F, 0x18, 0x4D, 0x87, 0x51, 0xD2, 0x11, 0x97, 0x7D, 0x16, 0xC5, 0xF0, 0xAB, 0x25, 0xCA, 0xB4, 0xF2, 0x66, - 0xCE, 0xCE, 0x58, 0xBB, 0x23, 0x10, 0x53, 0x6E, 0xA8, 0x96, 0xAD, 0x67, 0x9A, 0xEE, 0x53, 0xF0, 0x37, 0xCF, 0x51, 0x88, 0x51, 0xB8, 0x45, 0x15, 0x19, 0xCD, 0x84, 0xAD, 0xEB, 0xC5, 0xAA, 0x9C, - 0xCC, 0x03, 0x47, 0x2B, 0xDC, 0xCF, 0x86, 0x67, 0x04, 0xA0, 0xBA, 0xF5, 0x1D, 0x6B, 0xB2, 0xAB, 0x2E, 0xAA, 0x83, 0x5F, 0x56, 0x3F, 0x33, 0xB7, 0xA6, 0xA9, 0xF1, 0x0D, 0x95, 0x7B, 0x2F, 0x21, - 0xB6, 0xC0, 0x0E, 0xF2, 0x03, 0x91, 0x56, 0x3C, 0x56, 0x4C, 0x91, 0x87, 0xB3, 0x68, 0x49, 0xC5, 0x8E, 0x12, 0x41, 0xB6, 0xFD, 0xD9, 0xC8, 0xE7, 0xAE, 0xB2, 0x4B, 0xE4, 0x68, 0x52, 0xC6, 0x04 -}; - -static uint8_t test_015[] = { - 0x00, 0xA3, 0x09, 0x48, 0xD3, 0x48, 0x0D, 0xE4, 0xF4, 0x42, 0xA7, 0xA7, 0x7E, 0x47, 0xE0, 0x07, 0x6E, 0x93, 0x73, 0x43, 0xE9, 0x42, 0x6D, 0xCC, 0x87, 0xAE, 0x3B, 0x87, 0x33, 0xAE, 0xDF, 0x4E, - 0x32, 0xE5, 0x78, 0x0C, 0x93, 0xD9, 0x84, 0xCC, 0x31, 0x8B, 0xB4, 0x83, 0xC7, 0x45, 0x71, 0xA9, 0x3C, 0x9F, 0x60, 0x8E, 0xA0, 0xED, 0x80, 0xF5, 0xBD, 0xC1, 0x75, 0x70, 0xB5, 0xFE, 0x39, 0x2A, - 0x90, 0xB9, 0x00, 0xF7, 0x7D, 0x78, 0x91, 0x43, 0xB4, 0xC2, 0x9F, 0xC9, 0x77, 0x8A, 0x26, 0xC9, 0x17, 0xF4, 0x08, 0x0F, 0x5A, 0x5A, 0x64, 0x99, 0x47, 0xF6, 0x6E, 0x41, 0x77, 0x35, 0x20, 0x03, - 0xB6, 0xCC, 0x3C, 0x21, 0x4C, 0x87, 0x18, 0x7E, 0x8A, 0x13, 0xCA, 0x2D, 0x51, 0x53, 0x76, 0xAE, 0x94, 0x37, 0xA4, 0x32, 0x5F, 0x0E, 0x47, 0x50, 0x9A, 0xD6, 0xDB, 0x30, 0xED, 0x43, 0xAC, 0xC3, - 0xD4, 0x1E, 0x53, 0xD2, 0x9C, 0x29, 0x69, 0x98, 0xF6, 0x82, 0xF2, 0x12, 0x50, 0x04, 0x72, 0xC9, 0x57, 0x17, 0xA8, 0xF9, 0x80, 0xED, 0xDF, 0x96, 0x54, 0x5E, 0x1D, 0x21, 0x51, 0xCB, 0xC9, 0xAF, - 0xC5, 0xC2, 0x71, 0xE1, 0xB4, 0xF1, 0xDF, 0xCA, 0xC9, 0xF3, 0x71, 0x4C, 0x91, 0x03, 0xA9, 0x71, 0x3B, 0x08, 0xCA, 0x67, 0x2D, 0x65, 0x35, 0x38, 0x16, 0x02, 0xE5, 0xF9, 0x1C, 0x58, 0x23, 0xE6, - 0x7E, 0x14, 0x97, 0x51, 0x6B, 0xDE, 0xEB, 0x14, 0xB0, 0xE7, 0xB8, 0x59, 0xAD, 0xC4, 0x98, 0xA2, 0xEC, 0x1F, 0x32, 0x35, 0x31, 0x96, 0x64, 0x82, 0x7B, 0x2A, 0x48, 0x59, 0x1B, 0xC8, 0x9C, 0xBB, - 0x55, 0x6D, 0xE7, 0xAD, 0xBC, 0x14, 0x48, 0xF8, 0xF5, 0xBB, 0xD1, 0xF6, 0xC5, 0xD5, 0xDC, 0x62, 0x8F, 0x4D, 0x91, 0x92, 0xA2, 0x95, 0x4C, 0x95, 0xA8, 0x3F, 0xBC, 0xB0, 0xE2, 0x2B, 0xE1, 0x64 -}; - -static int run_tests( ) -{ - leg_t val1[TEST_MAX], val2[TEST_MAX], val3[TEST_MAX], scratch[TEST_MAX]; - int i; - - /***********************************************************************/ - printf( "Testing mp_cmp... " ); - - printf( "1 " ); - if( mp_cmp( test_001, test_001, sizeof(test_001) / sizeof(leg_t ) )) - REPORT( "MP_CMP test 1" ); - - printf( "2 " ); - if( mp_cmp( test_001, test_002, sizeof(test_001) / sizeof(leg_t ) ) != -1 ) - REPORT( "MP_CMP test 2" ); - - printf( "3 " ); - if( mp_cmp( test_002, test_001, sizeof(test_001) / sizeof(leg_t ) ) != 1 ) - REPORT( "MP_CMP test 3" ); - - printf( "success.\n" ); - - /***********************************************************************/ - printf( "Testing mp_sub... " ); - printf( "1 " ); - memcpy( val1, test_002, sizeof(test_002) ); - mp_sub( val1, test_001, sizeof(test_001) / sizeof(leg_t ) ); - if( memcmp( val1, test_003, sizeof(test_003)) ) - REPORT( "MP_SUB test 1" ); - - printf( "2 " ); - memset( val1, 0, sizeof(val1) ); - memcpy( val1, test_004, sizeof(test_004) ); - mp_sub( val1, test_002, sizeof(test_002) / sizeof(leg_t ) ); - if( memcmp( val1, test_005, sizeof(test_005))) - REPORT( "MP_SUB test 2" ); - - printf( "success.\n" ); - - /***********************************************************************/ - printf( "Testing mp_add... " ); - printf( "1 " ); - memset( val1, 0, sizeof(val1) ); - memcpy( val1, test_002, sizeof(test_002) ); - mp_add( val1, test_001, sizeof(test_001) / sizeof(leg_t ), 0 ); - if( memcmp( val1, test_006, sizeof(test_006)) ) - REPORT( "MP_ADD test 1" ); - - printf( "2 " ); - memset( val1, 0, sizeof(val1) ); - memcpy( val1, test_007, sizeof(test_007) ); - mp_add( val1, test_008, sizeof(test_008) / sizeof(leg_t ), 0 ); - if( memcmp( val1, test_009, sizeof(test_009)) ) - REPORT( "MP_ADD test 2" ); - - printf( "3 " ); - memset( val1, 0, sizeof(val1) ); - memcpy( val1, test_007, sizeof(test_007) ); - mp_add( val1, test_008, sizeof(test_008) / sizeof(leg_t ), 1 ); - if( memcmp( val1, test_010, sizeof(test_010)) ) - REPORT( "MP_ADD test 3" ); - - printf( "success.\n" ); - /***********************************************************************/ - - printf( "Testing mp_mul_oper_add... " ); - printf( "1 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_011, sizeof(test_011) ); - mp_import( val3, test_012, sizeof(test_012) ); - mp_mul_oper_add( val1, val2, val3, sizeof(test_011) / sizeof(leg_t ) ); - mp_import( val3, test_013, sizeof(test_013) ); - - if( memcmp( val1, val3, sizeof(test_013)) ) - REPORT( "MP_MUL_OPER_ADD test 1" ); - - printf( "2 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_011, sizeof(test_011) ); - mp_mul_oper_add( val1, val2, val2, sizeof(test_011) / sizeof(leg_t ) ); - mp_import( val3, test_014, sizeof(test_014) ); - - if( memcmp( val1, val3, sizeof(test_014)) ) - REPORT( "MP_MUL_OPER_ADD test 2" ); - - printf( "success.\n" ); - /***********************************************************************/ - - printf( "Testing mp_sqr... " ); - printf( "1 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_011, sizeof(test_011) ); - mp_sqr( val1, val2, sizeof(test_011) / sizeof(leg_t ) ); - mp_import( val3, test_014, sizeof(test_014) ); - - if( memcmp( val1, val3, sizeof(test_014)) ) - REPORT( "MP_SQR test 1" ); - - printf( "2 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_012, sizeof(test_012) ); - mp_sqr( val1, val2, sizeof(test_012) / sizeof(leg_t ) ); - mp_import( val3, test_015, sizeof(test_015) ); - - if( memcmp( val1, val3, sizeof(test_015)) ) - REPORT( "MP_SQR test 2" ); - - printf( "success.\n" ); - /***********************************************************************/ - - printf( "Testing mp_mul_kara_square... " ); - printf( "1 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_011, sizeof(test_011) ); - mp_mul_kara_square( val1, val2, sizeof(test_011) / sizeof(leg_t ), scratch ); - mp_import( val3, test_014, sizeof(test_014) ); - - if( memcmp( val1, val3, sizeof(test_014)) ) - REPORT( "MP_MUL_KARA_SQUARE test 1" ); - - printf( "2 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_012, sizeof(test_012) ); - mp_mul_kara_square( val1, val2, sizeof(test_012) / sizeof(leg_t ), scratch ); - mp_import( val3, test_015, sizeof(test_015) ); - - if( memcmp( val1, val3, sizeof(test_015)) ) - REPORT( "MP_MUL_KARA_SQUARE test 2" ); - - printf( "success.\n" ); - /***********************************************************************/ - - printf( "Testing mp_mul_kara... " ); - printf( "1 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_011, sizeof(test_011) ); - mp_import( val3, test_012, sizeof(test_012) ); - mp_mul_kara( val1, val2, val3, sizeof(test_011) / sizeof(leg_t ), scratch ); - mp_import( val3, test_013, sizeof(test_013) ); - - if( memcmp( val1, val3, sizeof(test_013)) ) - REPORT( "MP_MUL_KARA test 1" ); - - printf( "2 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_011, sizeof(test_011) ); - mp_import( val2, test_011, sizeof(test_011) ); - mp_mul_kara( val1, val2, val2, sizeof(test_011) / sizeof(leg_t ), scratch ); - mp_import( val3, test_014, sizeof(test_014) ); - - if( memcmp( val1, val3, sizeof(test_014)) ) - REPORT( "MP_MUL_KARA test 2" ); - - printf( "3 " ); - memset( val1, 0, sizeof(val1) ); - mp_import( val2, test_012, sizeof(test_012) ); - mp_import( val2, test_012, sizeof(test_012) ); - mp_mul_kara( val1, val2, val2, sizeof(test_012) / sizeof(leg_t ), scratch ); - mp_import( val3, test_015, sizeof(test_015) ); - - if( memcmp( val1, val3, sizeof(test_015)) ) - REPORT( "MP_MUL_KARA test 3" ); - - printf( "success.\n" ); - /***********************************************************************/ - - -// putchar(10); -// for( i = sizeof(test_013)/sizeof(leg_t )-1; i>=0; --i) printf( "%016llX", val1[i] ); -// putchar(10); -// for( i = sizeof(test_013)/sizeof(leg_t )-1; i>=0; --i) printf( "%016llX", val3[i] ); -// putchar(10); - + while( limb_size ) + { + limb_t outlimb = src[--limb_size]; + int cnt = sizeof( limb_t ); + while( cnt ) + *(dest++) = (uint8_t)( outlimb >> ( 8 * --cnt ) ); + } } - -#endif diff --git a/powm.h b/powm.h new file mode 100644 index 0000000..7290165 --- /dev/null +++ b/powm.h @@ -0,0 +1,44 @@ +#ifndef __LIBGSMKBIGNUM_POWM_H__ +#define __LIBGSMKBIGNUM_POWM_H__ + +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif + +#ifdef USE32BITLIMB +typedef uint32_t limb_t; +typedef uint64_t dlimb_t; +#else +typedef uint64_t limb_t; +typedef unsigned int uint128_t __attribute__((mode(TI))); +typedef uint128_t dlimb_t; +#endif + + +/* import from serialized format, big endian byte representation + return amount of limbs */ +uint32_t mp_import( limb_t *dest, uint8_t const * src, uint32_t byte_size ); +void mp_export( uint8_t *dest, const limb_t *scr, uint32_t limb_size ); + +/* This function works with precalculated parameters passed in r_square + and r_inverse. The latter being 1, if the bottom limb_t is -1. */ +void powm_internal( limb_t * result, + const limb_t * base, uint32_t base_limbs, + const limb_t * exponent, uint32_t exp_limbs, + const limb_t * modulus, uint32_t mod_limbs, + const limb_t * r_square, const limb_t r_inverse ); + +/* Not yet implemented */ +void powm( limb_t * result, + const limb_t * base, uint32_t base_limbs, + const limb_t * exponent, int expbits, + const limb_t * modulus, uint32_t mod_limbs ); + +#ifdef __cplusplus +} +#endif + +#endif -- cgit v1.2.3