summaryrefslogtreecommitdiffstats
path: root/src/securerom/ecverify.C
diff options
context:
space:
mode:
Diffstat (limited to 'src/securerom/ecverify.C')
-rw-r--r--src/securerom/ecverify.C2009
1 files changed, 1009 insertions, 1000 deletions
diff --git a/src/securerom/ecverify.C b/src/securerom/ecverify.C
index 659d7d6fb..a4ba85a65 100644
--- a/src/securerom/ecverify.C
+++ b/src/securerom/ecverify.C
@@ -22,14 +22,6 @@
/* permissions and limitations under the License. */
/* */
/* IBM_PROLOG_END_TAG */
-/*----------------------------------------------------------------------
- * (C) COPYRIGHT INTERNATIONAL BUSINESS MACHINES CORPORATION 2010
- * ALL RIGHTS RESERVED
- * IBM Research, Zurich and IBM Crypto Competency Center, Copenhagen
- *----------------------------------------------------------------------
- * Author: Tamas Visegrady (tvi@zurich.ibm.com)
- * Change: W Eric Hall (wehall@us.ibm.com)
- *----------------------------------------------------------------------*/
/** ECDSA verification on fixed curve/s (currently, on NIST P-521)
* The code below works for a compile-time constant curve, and requires
@@ -48,25 +40,23 @@
#include <stdio.h>
#include <string.h>
#include <stdint.h> /* uint_fast8_t, uintN_t */
-#include <inttypes.h> /* PRIx64 used to format bn_t's */
+#include "inttypes.H" /* PRIx64 used to format bn_t's */
/**
* Define __LITTLE_ENDIAN or __BIG_ENDIAN for target.
*/
#if defined __BIG_ENDIAN__ || defined _BIG_ENDIAN
- #define __BIG_ENDIAN
- #undef __LITTLE_ENDIAN
+ #define __BIG_ENDIAN
+ #undef __LITTLE_ENDIAN
#else
- #undef __BIG_ENDIAN
- #define __LITTLE_ENDIAN
+ #undef __BIG_ENDIAN
+ #define __LITTLE_ENDIAN
#endif
-#include "ecverify.h"
-
+#include <securerom/ecverify.H>
#define EC_PRIMEBITS 521 /* P521 */
-//#define EC_DEBUG 1 /* needs libc (not in Prism version) */
#define EC_STACKTRACE 1 /* debug only; currently, glibc */
#define NO_EC_DOUBLE_XY 1 /* do not implement ec_double_xy */
@@ -76,20 +66,6 @@ typedef uint_fast8_t bnindex_t;
#define BN_FMT "%016" PRIx64 /* PRIx64 from inttypes.h */
-
-// show word boundaries in bignumbers (diagnostics dump only)
-// #define EC_DEBUG_WORDS 1
-
-
-// define this if we construct ec_prime[] on the fly
-// saves code, adds runtime static structs; check your compiler if useful
-// does not make sense if non-exec, read-only constants are cheap
-//
-// #define BN_PRIME_GENERATED 1
-
-
-//--- nothing user-servicable below ---------------------------------------
-
#if !defined(__LITTLE_ENDIAN) && !defined(__BIG_ENDIAN)
#error "Please define target endianness (__LITTLE_ENDIAN or __BIG_ENDIAN)"
#endif
@@ -106,8 +82,7 @@ typedef uint_fast8_t bnindex_t;
#define BN_MAXBIT (((bn_t) 1) << (BN_BITS -1))
-#define BITS2BN(bits) \
- (((bits) +BN_BITS -1) / BN_BITS)
+#define BITS2BN(bits) (((bits) +BN_BITS -1) / BN_BITS)
// we only deal with big numbers of fixed size
#define NWORDS BITS2BN( EC_PRIMEBITS )
@@ -123,21 +98,22 @@ typedef uint_fast8_t bnindex_t;
#else
static void __attribute__((noinline)) BN_COPY (bn_t *dst, const bn_t *src)
{
- size_t i;
- for(i=0;i<NWORDS;i++) {
- *dst++ = *src++;
- }
+ size_t i;
+ for(i=0;i<NWORDS;i++)
+ {
+ *dst++ = *src++;
+ }
}
#endif
#ifdef BN_POWER64_DBG
static void __attribute__((noinline)) BN_DUMP (int i, bn_t *top)
{
- asm volatile ("nop" : : "r" (i), "r" (top));
+ asm volatile ("nop" : : "r" (i), "r" (top));
}
static void BN_EXIT (void)
{
- asm volatile("b .Check_Stop");
+ asm volatile("b .Check_Stop");
}
#else
#define BN_DUMP(_i,_bn) ((void)0)
@@ -161,19 +137,15 @@ static void bn_dprint (const char *msg, const bn_t *m) ;
#define EC_DEVASSERT(cond) ((void) 0) // removed '((void) cond)' which still did the cond test
#endif
-
-
static bn_t bn_sub (bn_t *a, const bn_t *b) ;
static void bn_add (bn_t *a, const bn_t *b) ;
static void bn_mul (bn_t *r, const bn_t *a, const bn_t *b) ;
static void bn_modadd (bn_t *a, const bn_t *b) ;
static void bn_modsub (bn_t *a, const bn_t *b) ;
-// static int bn_cmp (const bn_t *a, const bn_t *b) ;
static int bn_cmp (const bn_t a[NWORDS], const bn_t b[NWORDS]) ;
// P521: a==-3, fixed curve parameter
-//
static int ec_double (bn_t *x, bn_t *y, bn_t *z) ;
@@ -189,105 +161,101 @@ static int ec_double (bn_t *x, bn_t *y, bn_t *z) ;
typedef struct {
- bn_t ec_prime[ NWORDS ];
+ bn_t ec_prime[ NWORDS ];
bn_t ec_order[ NWORDS ];
bn_t prime_px[ NWORDS ];
bn_t prime_py[ NWORDS ];
bn_t ec_order_qn[ NWORDS ];
} consts_t;
-const consts_t consts = {
+extern "C"
+const consts_t consts = {
//const bn_t ec_prime[ NWORDS ] =
- {
- BN_PRIME_MSW,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- },
-
-//-------------------------------------
+ {
+ BN_PRIME_MSW,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ },
//const bn_t ec_order[ NWORDS ] =
{
- 0x00000000000001ffLL,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- 0xffffffffffffffffLL,
- 0xfffffffffffffffaLL,
- 0x51868783bf2f966bLL,
- 0x7fcc0148f709a5d0LL,
- 0x3bb5c9b8899c47aeLL,
- 0xbb6fb71e91386409LL,
+ 0x00000000000001ffLL,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ 0xffffffffffffffffLL,
+ 0xfffffffffffffffaLL,
+ 0x51868783bf2f966bLL,
+ 0x7fcc0148f709a5d0LL,
+ 0x3bb5c9b8899c47aeLL,
+ 0xbb6fb71e91386409LL,
},
//const bn_t prime_px[ NWORDS ] = {
{
- 0x00000000000000c6LL,
- 0x858e06b70404e9cdLL,
- 0x9e3ecb662395b442LL,
- 0x9c648139053fb521LL,
- 0xf828af606b4d3dbaLL,
- 0xa14b5e77efe75928LL,
- 0xfe1dc127a2ffa8deLL,
- 0x3348b3c1856a429bLL,
- 0xf97e7e31c2e5bd66LL,
+ 0x00000000000000c6LL,
+ 0x858e06b70404e9cdLL,
+ 0x9e3ecb662395b442LL,
+ 0x9c648139053fb521LL,
+ 0xf828af606b4d3dbaLL,
+ 0xa14b5e77efe75928LL,
+ 0xfe1dc127a2ffa8deLL,
+ 0x3348b3c1856a429bLL,
+ 0xf97e7e31c2e5bd66LL,
},
//const bn_t prime_py[ NWORDS ] = {
{
- 0x0000000000000118LL,
- 0x39296a789a3bc004LL,
- 0x5c8a5fb42c7d1bd9LL,
- 0x98f54449579b4468LL,
- 0x17afbd17273e662cLL,
- 0x97ee72995ef42640LL,
- 0xc550b9013fad0761LL,
- 0x353c7086a272c240LL,
- 0x88be94769fd16650LL,
- },
-
- //-------------------------- mod mul by order (n) -------
- // MS 521 bits of Q/N, fractional part
- //
-// static const bn_t ec_order_qn[ NWORDS ] =
- {
- 0LL,
- 0LL,
- 0LL,
- 0LL,
- 0x0000000000000005LL,
- 0xae79787c40d06994LL,
- 0x8033feb708f65a2fLL,
- 0xc44a36477663b851LL,
- 0x449048e16ec79bf6LL,
- }
+ 0x0000000000000118LL,
+ 0x39296a789a3bc004LL,
+ 0x5c8a5fb42c7d1bd9LL,
+ 0x98f54449579b4468LL,
+ 0x17afbd17273e662cLL,
+ 0x97ee72995ef42640LL,
+ 0xc550b9013fad0761LL,
+ 0x353c7086a272c240LL,
+ 0x88be94769fd16650LL,
+ },
+
+//-------------------------- mod mul by order (n) -------
+// MS 521 bits of Q/N, fractional part
+//
+// static const bn_t ec_order_qn[ NWORDS ] =
+ {
+ 0LL,
+ 0LL,
+ 0LL,
+ 0LL,
+ 0x0000000000000005LL,
+ 0xae79787c40d06994LL,
+ 0x8033feb708f65a2fLL,
+ 0xc44a36477663b851LL,
+ 0x449048e16ec79bf6LL,
+ }
} ;
-inline const consts_t* __attribute__((pure)) consts_p() {
+inline const consts_t* __attribute__((pure)) consts_p()
+{
+
#ifdef EMULATE_HW
- return &consts;
+ return &consts;
#else
consts_t* result_consts_p;
- asm("li %0,(__toc_start)@l ### %0 := base+0x8000 \n\t" // because li does not work
- "sub %0,r2,%0 \n\t" // because subi does not work
- "addi %0,%0,(consts-0x8000)@l" : "=r" (result_consts_p) );
+ asm volatile("li %0,(__toc_start)@l ### %0 := base+0x8000 \n\t" // because li does not work
+ "sub %0,2,%0 \n\t" // because subi does not work
+ "addi %0,%0,(consts-0x8000)@l" : "=r" (result_consts_p) );
return result_consts_p;
#endif
}
-//-------------------------------------
-
-
#define bn_ge_prime(val) (bn_cmp((val), consts_p()->ec_prime) >= 0)
#define bn_ge_order(val) (bn_cmp((val), consts_p()->ec_order) >= 0)
-
-//-------------------------------------
// P521: MSW has unused bits
#define BN_MSW_UNUSED_BITS (BN_BITS - BN_PRIME_MSW_BITS)
#define BN_MSW_UNUSED_BYTES ((BN_MSW_UNUSED_BITS +7) >>3)
@@ -300,23 +268,23 @@ inline const consts_t* __attribute__((pure)) consts_p() {
//
static bn_t bn_shl (bn_t *a, bn_t acc)
{
- bnindex_t i = NWORDS;
- bn_t cf = 0;
-
- EC_ASSERT(NULL != a);
- EC_ASSERT(0 == a[0]);
+ bnindex_t i = NWORDS;
+ bn_t cf = 0;
- a += NWORDS;
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(0 == a[0]);
- while (0<i--) {
- cf = *(--a);
- *a <<= BN_MSW_UNUSED_BITS;
- *a |= BN_MSW_UNUSED_MASK & (acc >> BN_PRIME_MSW_BITS);
+ a += NWORDS;
- acc = cf;
- }
+ while (0<i--)
+ {
+ cf = *(--a);
+ *a <<= BN_MSW_UNUSED_BITS;
+ *a |= BN_MSW_UNUSED_MASK & (acc >> BN_PRIME_MSW_BITS);
+ acc = cf;
+ }
- return cf;
+ return cf;
}
@@ -325,38 +293,40 @@ static bn_t bn_shl (bn_t *a, bn_t acc)
static void bn_printn (const char *msg, const bn_t *m, bnindex_t i)
{
- EC_ASSERT(NULL != m);
+ EC_ASSERT(NULL != m);
- if (NULL != msg)
- printf("%s", msg);
+ if (NULL != msg)
+ {
+ printf("%s", msg);
+ }
- while (0 < i--) {
+ while (0 < i--)
+ {
#if defined(EC_DEBUG_WORDS)
- if (i<NWORDS-1)
- printf(".");
+ if (i<NWORDS-1)
+ {
+ printf(".");
+ }
#endif
- printf(BN_FMT, *(m++));
- }
+ printf(BN_FMT, *(m++));
+ }
- printf("\n");
+ printf("\n");
}
-
static void bn_print (const char *msg, const bn_t *m)
{
- bn_printn(msg, m, NWORDS);
+ bn_printn(msg, m, NWORDS);
}
-
static void bn_dprint (const char *msg, const bn_t *m)
{
- bn_printn(msg, m, NWORDS+NWORDS);
+ bn_printn(msg, m, NWORDS+NWORDS);
}
#endif /* defined(EC_DEBUG) */
-
//============================================== modular multiplication ====
// this section should be routed to hardware, when it becomes available
@@ -368,11 +338,12 @@ static void bn_dprint (const char *msg, const bn_t *m)
#define bn_dclear(n) bn_clr((n), 2*NWORDS)
static void __attribute__((noinline)) bn_clr (bn_t *dst, size_t s)
{
- size_t i;
- dst--;
- for(i=0;i<s;i++) {
- *(++dst) = 0LL;
- }
+ size_t i;
+ dst--;
+ for(i=0;i<s;i++)
+ {
+ *(++dst) = 0LL;
+ }
}
#endif
@@ -384,40 +355,41 @@ static void __attribute__((noinline)) bn_clr (bn_t *dst, size_t s)
static bn_t bn_dmul (bn_t a, bn_t b)
{
#ifdef EC_POWER64_ASM
- bn_t t;
- asm("mulhdu %0,%1,%2" : "=r" (t) : "r" (a), "r" (b) );
- return t;
+ bn_t t;
+ asm("mulhdu %0,%1,%2" : "=r" (t) : "r" (a), "r" (b) );
+ return t;
#else
- hbn_t ah, al, bh, bl;
- bn_t t;
-
- al = a;
- ah = (hbn_t) (a >> HBN_BITS);
- bl = b;
- bh = (hbn_t) (b >> HBN_BITS);
-
- a = ((bn_t) ah) * bh; // collects high word
- b = ((bn_t) al) * bl; // collects low word
-
- t = ((bn_t) ah) * bl;
- a += t >> HBN_BITS;
- t <<= HBN_BITS;
- if (b+t < t)
- ++a;
- b += t;
-
- t = ((bn_t) al) * bh;
- a += t >> HBN_BITS;
- t <<= HBN_BITS;
- if (b+t < t)
- ++a;
-// b += t; // we don't actually need this, only its carry above
- return a;
+ hbn_t ah, al, bh, bl;
+ bn_t t;
+
+ al = a;
+ ah = (hbn_t) (a >> HBN_BITS);
+ bl = b;
+ bh = (hbn_t) (b >> HBN_BITS);
+
+ a = ((bn_t) ah) * bh; // collects high word
+ b = ((bn_t) al) * bl; // collects low word
+
+ t = ((bn_t) ah) * bl;
+ a += t >> HBN_BITS;
+ t <<= HBN_BITS;
+ if (b+t < t)
+ {
+ ++a;
+ }
+ b += t;
+
+ t = ((bn_t) al) * bh;
+ a += t >> HBN_BITS;
+ t <<= HBN_BITS;
+ if (b+t < t)
+ {
+ ++a;
+ }
+ return a;
#endif
}
-
-//-------------------------------------
/** multiply (a,NWORDS) by (b,NWORDS) into (r,2*NWORDS)
* we collect 2-word multiples, and carries across columns in two
* arrays:
@@ -435,110 +407,121 @@ static bn_t bn_dmul (bn_t a, bn_t b)
//
static void bn_mul (bn_t *r, const bn_t *a, const bn_t *b)
{
- unsigned char cf[ NWORDS+NWORDS ]; /* carry collector */
- bnindex_t i, j;
- bn_t ph, pl; /* product high,low words */
+ unsigned char cf[ NWORDS+NWORDS ]; /* carry collector */
+ bnindex_t i, j;
+ bn_t ph, pl; /* product high,low words */
- EC_ASSERT(NULL != r);
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
+ EC_ASSERT(NULL != r);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
- bn_dclear(r);
- memset(cf, 0, sizeof(cf));
+ bn_dclear(r);
+ memset(cf, 0, sizeof(cf));
- for (j=0; j<NWORDS; ++j) {
- for (i=0; i<NWORDS; ++i) {
- ph = bn_dmul(a[i], b[j]);
- pl = a[i] * b[j];
+ for (j=0; j<NWORDS; ++j)
+ {
+ for (i=0; i<NWORDS; ++i)
+ {
+ ph = bn_dmul(a[i], b[j]);
+ pl = a[i] * b[j];
#ifdef EC_POWER64_ASM
- asm("addc %0,%2,%4\n"
- "addze %1,%3"
- : "=r" (r[i+j]), "=r" (cf[i+j])
- : "0" (r[i+j]), "1" (cf[i+j]), "r" (ph)
- );
- asm("addc %0,%2,%4\n"
- "addze %1,%3"
- : "=r" (r[i+j+1]), "=r" (cf[i+j+1])
- : "0" (r[i+j+1]), "1" (cf[i+j+1]), "r" (pl)
- );
+ asm("addc %0,%2,%4\n"
+ "addze %1,%3"
+ : "=r" (r[i+j]), "=r" (cf[i+j])
+ : "0" (r[i+j]), "1" (cf[i+j]), "r" (ph)
+ );
+ asm("addc %0,%2,%4\n"
+ "addze %1,%3"
+ : "=r" (r[i+j+1]), "=r" (cf[i+j+1])
+ : "0" (r[i+j+1]), "1" (cf[i+j+1]), "r" (pl)
+ );
#else
- r[i+j] += ph;
- if (r[i+j] < ph) {
- EC_ASSERT(i+j>0); // MSW can't carry to left
- (cf[i+j-1])++;
- }
-
- r[i+j+1] += pl;
- if (r[i+j+1] < pl)
- (cf[i+j])++;
+ r[i+j] += ph;
+ if (r[i+j] < ph)
+ {
+ EC_ASSERT(i+j>0); // MSW can't carry to left
+ (cf[i+j-1])++;
+ }
+
+ r[i+j+1] += pl;
+ if (r[i+j+1] < pl)
+ {
+ (cf[i+j])++;
+ }
#endif
- }
- }
+ }
+ }
- // propagate carries (LS to MS)
+ // propagate carries (LS to MS)
#ifdef EC_POWER64_ASM
- i=NWORDS+NWORDS-2;
- asm("addc %0,%1,%2"
- : "=r" (r[i])
- : "0" (r[i]), "r" (cf[i+1])
- );
- for ( ; 0<i; ) {
- --i;
- asm("adde %0,%1,%2"
- : "=r" (r[i])
- : "0" (r[i]), "r" (cf[i+1])
- );
+ i=NWORDS+NWORDS-2;
+ asm("addc %0,%1,%2"
+ : "=r" (r[i])
+ : "0" (r[i]), "r" (cf[i+1])
+ );
+ for ( ; 0<i; )
+ {
+ --i;
+ asm("adde %0,%1,%2"
+ : "=r" (r[i])
+ : "0" (r[i]), "r" (cf[i+1])
+ );
#else
- for (i=NWORDS+NWORDS; 0<i; ) {
- if (cf[--i]) {
- r[i] += cf[i];
- if (r[i] < cf[i]) {
- EC_ASSERT(0 < i);
- cf[i-1]++;
- }
- }
+ for (i=NWORDS+NWORDS; 0<i; )
+ {
+ if (cf[--i])
+ {
+ r[i] += cf[i];
+ if (r[i] < cf[i])
+ {
+ EC_ASSERT(0 < i);
+ cf[i-1]++;
+ }
+ }
#endif
- }
+ }
}
#else
static void bn_mul (bn_t *r, const bn_t *a, const bn_t *b)
{
- bnindex_t i, j;
- bn_t ph, pl, th, tb; /* product high,low words */
+ bnindex_t i, j;
+ bn_t ph, pl, th, tb; /* product high,low words */
- EC_ASSERT(NULL != r);
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
+ EC_ASSERT(NULL != r);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
- bn_dclear(r);
+ bn_dclear(r);
- r += NWORDS;
- b += NWORDS;
- for (j=0; j<NWORDS; j++) {
- th = 0LL;
- tb = *(--b);
r += NWORDS;
- a += NWORDS;
- for (i=0; i<NWORDS; i++) {
- asm("mulld %0,%1,%2" //pl = *(--a) * tb
- : "=r" (pl)
- : "r" (*(--a)), "r" (tb)
- );
- asm("mulhdu %0,%1,%2" //ph = *a * tb
- : "=r" (ph)
- : "r" (*a), "r" (tb)
- );
- asm("addc %1,%5,%4\n" //pl += *(--r)
- "addze %2,%6\n" //ph += ca
- "addc %0,%5,%7\n" //*r = pl + th
- "addze %3,%6" //th = ph + ca
- : "=r" (*r), "=r" (pl), "=r" (ph), "=r" (th)
- : "0" (*(--r)), "1" (pl), "2" (ph), "3" (th)
- );
+ b += NWORDS;
+ for (j=0; j<NWORDS; j++)
+ {
+ th = 0LL;
+ tb = *(--b);
+ r += NWORDS;
+ a += NWORDS;
+ for (i=0; i<NWORDS; i++)
+ {
+ asm("mulld %0,%1,%2" //pl = *(--a) * tb
+ : "=r" (pl)
+ : "r" (*(--a)), "r" (tb)
+ );
+ asm("mulhdu %0,%1,%2" //ph = *a * tb
+ : "=r" (ph)
+ : "r" (*a), "r" (tb)
+ );
+ asm("addc %1,%5,%4\n" //pl += *(--r)
+ "addze %2,%6\n" //ph += ca
+ "addc %0,%5,%7\n" //*r = pl + th
+ "addze %3,%6" //th = ph + ca
+ : "=r" (*r), "=r" (pl), "=r" (ph), "=r" (th)
+ : "0" (*(--r)), "1" (pl), "2" (ph), "3" (th)
+ );
+ }
+ *(--r) = th;
}
- *(--r) = th;
- }
}
#endif
@@ -546,75 +529,77 @@ static void bn_mul (bn_t *r, const bn_t *a, const bn_t *b)
#ifdef BN_POWER64_SQR
static void bn_sqr (bn_t *r, const bn_t *a)
{
- bnindex_t i, j;
- const bn_t *b; /* product high,low words */
- bn_t *c, ph, pl, ta, t0, t1, t2; /* product high,low words */
+ bnindex_t i, j;
+ const bn_t *b; /* product high,low words */
+ bn_t *c, ph, pl, ta, t0, t1, t2; /* product high,low words */
- EC_ASSERT(NULL != r);
- EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != r);
+ EC_ASSERT(NULL != a);
- bn_dclear(r);
+ bn_dclear(r);
- r += 2*NWORDS;
- a += NWORDS;
- for (j=0; j<NWORDS-1; j++) {
+ r += 2*NWORDS;
+ a += NWORDS;
+ for (j=0; j<NWORDS-1; j++)
+ {
+ ta = *(--a);
+ c = r;
+ b = a;
+ asm("mulld %0,%2,%2\n" //pl = ta * ta
+ "mulhdu %1,%2,%2" //ph = ta * ta
+ : "=r" (pl), "=r" (ph)
+ : "r" (ta)
+ );
+ asm("addc %0,%2,%4\n" //*r = *(--r) + pl
+ "addze %1,%3" //t0 = ph + ca
+ : "=r" (*c), "=r" (t0)
+ : "0" (*(--c)), "r" (ph), "r" (pl)
+ );
+ t1 = 0L;
+ for (i=j+1; i<NWORDS; i++)
+ {
+ t2 = 0L;
+ asm("mulld %0,%1,%2" //pl = *(--b) * ta
+ : "=r" (pl)
+ : "r" (*(--b)), "r" (ta)
+ );
+ asm("mulhdu %0,%1,%2" //ph = *b * ta
+ : "=r" (ph)
+ : "r" (*b), "r" (ta)
+ );
+ asm("addc %1,%7,%7\n" //pl += pl
+ "adde %2,%8,%8\n" //ph += ph + ca
+ "addze %5,%11\n" //t2 += ca
+ "addc %1,%7,%9\n" //pl += t0
+ "adde %2,%8,%10\n" //ph += t1 + ca
+ "addze %5,%11\n" //t2 += ca
+ "addc %0,%6,%7\n" //*r = *(--r) + pl
+ "addze %3,%8\n" //t0 = ph + ca
+ "addze %4,%11" //t1 = t2 + ca
+ : "=r" (*c), "=r" (pl), "=r" (ph), "=r" (t0), "=r" (t1), "=r" (t2)
+ : "0" (*(--c)), "1" (pl), "2" (ph), "3" (t0), "4" (t1), "5" (t2)
+ );
+ }
+ asm("addc %0,%2,%4\n" //*r = *(--r) + t0
+ "addze %1,%3" //t1 += ca
+ : "=r" (*c), "=r" (t1)
+ : "0" (*(--c)), "1" (t1), "r" (t0)
+ );
+ *(--c) = t1;
+ r -= 2;
+ }
ta = *(--a);
- c = r;
- b = a;
- asm("mulld %0,%2,%2\n" //pl = ta * ta
- "mulhdu %1,%2,%2" //ph = ta * ta
+ asm("mulld %0,%2,%2\n" //pl = ta * ta
+ "mulhdu %1,%2,%2" //ph = ta * ta
: "=r" (pl), "=r" (ph)
: "r" (ta)
);
- asm("addc %0,%2,%4\n" //*r = *(--r) + pl
- "addze %1,%3" //t0 = ph + ca
- : "=r" (*c), "=r" (t0)
- : "0" (*(--c)), "r" (ph), "r" (pl)
+ asm("addc %0,%2,%4\n" //*r = *(--r) + pl
+ "addze %1,%3" //ph += ca
+ : "=r" (*r), "=r" (ph)
+ : "0" (*(--r)), "1" (ph), "r" (pl)
);
- t1 = 0L;
- for (i=j+1; i<NWORDS; i++) {
- t2 = 0L;
- asm("mulld %0,%1,%2" //pl = *(--b) * ta
- : "=r" (pl)
- : "r" (*(--b)), "r" (ta)
- );
- asm("mulhdu %0,%1,%2" //ph = *b * ta
- : "=r" (ph)
- : "r" (*b), "r" (ta)
- );
- asm("addc %1,%7,%7\n" //pl += pl
- "adde %2,%8,%8\n" //ph += ph + ca
- "addze %5,%11\n" //t2 += ca
- "addc %1,%7,%9\n" //pl += t0
- "adde %2,%8,%10\n" //ph += t1 + ca
- "addze %5,%11\n" //t2 += ca
- "addc %0,%6,%7\n" //*r = *(--r) + pl
- "addze %3,%8\n" //t0 = ph + ca
- "addze %4,%11" //t1 = t2 + ca
- : "=r" (*c), "=r" (pl), "=r" (ph), "=r" (t0), "=r" (t1), "=r" (t2)
- : "0" (*(--c)), "1" (pl), "2" (ph), "3" (t0), "4" (t1), "5" (t2)
- );
- }
- asm("addc %0,%2,%4\n" //*r = *(--r) + t0
- "addze %1,%3" //t1 += ca
- : "=r" (*c), "=r" (t1)
- : "0" (*(--c)), "1" (t1), "r" (t0)
- );
- *(--c) = t1;
- r -= 2;
- }
- ta = *(--a);
- asm("mulld %0,%2,%2\n" //pl = ta * ta
- "mulhdu %1,%2,%2" //ph = ta * ta
- : "=r" (pl), "=r" (ph)
- : "r" (ta)
- );
- asm("addc %0,%2,%4\n" //*r = *(--r) + pl
- "addze %1,%3" //ph += ca
- : "=r" (*r), "=r" (ph)
- : "0" (*(--r)), "1" (ph), "r" (pl)
- );
- *(--r) += ph;
+ *(--r) += ph;
}
#endif
#endif
@@ -636,34 +621,40 @@ static void bn_sqr (bn_t *r, const bn_t *a)
#ifndef EC_POWER64_RED
static void bn_modred_p521 (bn_t *r, bn_t *a)
{
- bn_t *al;
-bn_t *rc = r;
+ bn_t *al;
+ bn_t *rc = r;
- EC_ASSERT(NULL != r);
- EC_ASSERT(NULL != a);
- EC_ASSERT((const bn_t *) r != a);
+ EC_ASSERT(NULL != r);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT((const bn_t *) r != a);
- al = a+NWORDS;
+ al = a+NWORDS;
- // P521: product is 1042 bits, MSW of double-width bignum always 0
- //
- EC_ASSERT(0 == a[0]);
+ // P521: product is 1042 bits, MSW of double-width bignum always 0
+ //
+ EC_ASSERT(0 == a[0]);
- BN_COPY(rc, a);
- bn_shl(rc, *al);
+ BN_COPY(rc, a);
+ bn_shl(rc, *al);
- *al &= BN_PRIME_MSW_MASK;
+ *al &= BN_PRIME_MSW_MASK;
- if (bn_cmp(rc, consts_p()->ec_prime) >= 0)
- bn_sub(rc, consts_p()->ec_prime); // XXX can this happen? (mod-based input)
+ if (bn_cmp(rc, consts_p()->ec_prime) >= 0)
+ {
+ bn_sub(rc, consts_p()->ec_prime); // XXX can this happen? (mod-based input)
+ }
- if (bn_cmp(al, consts_p()->ec_prime) >= 0)
- bn_sub(al, consts_p()->ec_prime);
- EC_ASSERT(!bn_ge_prime(al)); // al must have bitlen <= ec_prime
+ if (bn_cmp(al, consts_p()->ec_prime) >= 0)
+ bn_sub(al, consts_p()->ec_prime);
+ {
+ EC_ASSERT(!bn_ge_prime(al)); // al must have bitlen <= ec_prime
+ }
- bn_add(rc, al);
- if (bn_cmp(rc, consts_p()->ec_prime) >= 0)
- bn_sub(rc, consts_p()->ec_prime);
+ bn_add(rc, al);
+ if (bn_cmp(rc, consts_p()->ec_prime) >= 0)
+ {
+ bn_sub(rc, consts_p()->ec_prime);
+ }
}
#else
#ifdef BN_POWER64_SQR
@@ -672,71 +663,74 @@ static void __attribute__((noinline)) bn_modred_fast (bn_t *r, bn_t *a)
static void bn_modred_fast (bn_t *r, bn_t *a)
#endif
{
- bn_t *ah = a + NWORDS;
- bn_t *al = a + 2*NWORDS;
- bn_t t0 = (*(a+1) >> 18) + (*ah >> 9);
- bn_t t1, t2, t3=0;
- size_t i;
- r += NWORDS;
- for (i=0; i<NWORDS-2; i++) {
+ bn_t *ah = a + NWORDS;
+ bn_t *al = a + 2*NWORDS;
+ bn_t t0 = (*(a+1) >> 18) + (*ah >> 9);
+ bn_t t1, t2, t3=0;
+ size_t i;
+ r += NWORDS;
+ for (i=0; i<NWORDS-2; i++) {
+ t1 = *(--ah) << 55;
+ t2 = *ah >> 9;
+ asm("addc %3,%7,%5\n" //t3 = *(--al) + t0;
+ "addze %2,%6\n" //t2 += ca;
+ "addc %0,%4,%8\n" //*(--r) = t3 + t1;
+ "addze %1,%6" //t0 = t2 + ca;
+ : "=r" (*(--r)), "=r" (t0), "=r" (t2), "=r" (t3)
+ : "3" (t3), "1" (t0), "2" (t2), "r" (*(--al)), "r" (t1)
+ );
+ }
t1 = *(--ah) << 55;
- t2 = *ah >> 9;
- asm("addc %3,%7,%5\n" //t3 = *(--al) + t0;
- "addze %2,%6\n" //t2 += ca;
- "addc %0,%4,%8\n" //*(--r) = t3 + t1;
- "addze %1,%6" //t0 = t2 + ca;
+ t2 = (*ah >> 9)&BN_PRIME_MSW_MASK;
+ asm("addc %3,%7,%5\n" //t3 = *(--al) + t0;
+ "addze %2,%6\n" //t2 += ca;
+ "addc %0,%4,%8\n" //*(--r) = t3 + t1;
+ "addze %1,%6" //t0 = t2 + ca;
: "=r" (*(--r)), "=r" (t0), "=r" (t2), "=r" (t3)
: "3" (t3), "1" (t0), "2" (t2), "r" (*(--al)), "r" (t1)
);
- }
- t1 = *(--ah) << 55;
- t2 = (*ah >> 9)&BN_PRIME_MSW_MASK;
- asm("addc %3,%7,%5\n" //t3 = *(--al) + t0;
- "addze %2,%6\n" //t2 += ca;
- "addc %0,%4,%8\n" //*(--r) = t3 + t1;
- "addze %1,%6" //t0 = t2 + ca;
- : "=r" (*(--r)), "=r" (t0), "=r" (t2), "=r" (t3)
- : "3" (t3), "1" (t0), "2" (t2), "r" (*(--al)), "r" (t1)
- );
- *(--r) = (*(--al)&BN_PRIME_MSW_MASK) + t0;
+ *(--r) = (*(--al)&BN_PRIME_MSW_MASK) + t0;
}
static void __attribute__((noinline)) bn_modred_slow (bn_t *r)
{
- size_t i;
- if (*r > BN_PRIME_MSW_MASK) {
- bn_t t0 = *r >> 9;
- *r &= BN_PRIME_MSW_MASK;
- r += NWORDS;
- asm("addc %0,%1,%2"
- : "=r" (*r)
- : "0" (*(--r)), "r" (t0)
- );
- for (i=0; i<NWORDS-1; i++) {
- asm("addze %0,%1"
- : "=r" (*r)
- : "0" (*(--r))
- );
+ size_t i;
+ if (*r > BN_PRIME_MSW_MASK)
+ {
+ bn_t t0 = *r >> 9;
+ *r &= BN_PRIME_MSW_MASK;
+ r += NWORDS;
+ asm("addc %0,%1,%2"
+ : "=r" (*r)
+ : "0" (*(--r)), "r" (t0)
+ );
+ for (i=0; i<NWORDS-1; i++)
+ {
+ asm("addze %0,%1"
+ : "=r" (*r)
+ : "0" (*(--r))
+ );
+ }
+ }
+ if (bn_ge_prime(r))
+ {
+ bn_sub(r, consts_p()->ec_prime);
}
- }
- if (bn_ge_prime(r))
- bn_sub(r, consts_p()->ec_prime);
}
#endif
-
static void bn_modmul_prime (bn_t *a, const bn_t *b)
{
- bn_t prod[ NWORDS+NWORDS ];
+ bn_t prod[ NWORDS+NWORDS ];
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
- bn_mul(prod, a, b);
+ bn_mul(prod, a, b);
#ifdef EC_POWER64_RED
- bn_modred_fast(a, prod); // accepts upto 46 extra bits => outputs at most 1 extra bit (522)
+ bn_modred_fast(a, prod); // accepts upto 46 extra bits => outputs at most 1 extra bit (522)
#else
- bn_modred_p521(a, prod);
+ bn_modred_p521(a, prod);
#endif
}
@@ -744,24 +738,22 @@ static void bn_modmul_prime (bn_t *a, const bn_t *b)
static void bn_modsqr_prime (bn_t *a)
{
#ifdef BN_POWER64_SQR
- bn_t prod[ NWORDS+NWORDS ];
+ bn_t prod[ NWORDS+NWORDS ];
- EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != a);
- bn_sqr(prod, a);
+ bn_sqr(prod, a);
#ifdef EC_POWER64_RED
- bn_modred_fast(a, prod); // accepts upto 46 extra bits => outputs at most 1 extra bit (522)
+ bn_modred_fast(a, prod); // accepts upto 46 extra bits => outputs at most 1 extra bit (522)
#else
- bn_modred_p521(a, prod);
+ bn_modred_p521(a, prod);
#endif
#else
- bn_modmul_prime(a, a);
+ bn_modmul_prime(a, a);
#endif
}
#endif
-
-
// mod reduce 2*NWORDS to NWORDS through approximate division
//
// input (a,2*NWORDS) <= N^2 -2*N +1
@@ -780,88 +772,91 @@ static void bn_modsqr_prime (bn_t *a)
//
static void bn_modred_p521_order (bn_t *r, const bn_t *a)
{
- bn_t dbl[ NWORDS+NWORDS ];
+ bn_t dbl[ NWORDS+NWORDS ];
- EC_ASSERT(NULL != r);
- EC_ASSERT(NULL != a);
- EC_ASSERT((const bn_t *) r != a);
-// XXX full overlap check
+ EC_ASSERT(NULL != r);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT((const bn_t *) r != a);
+ // XXX full overlap check
- // P521: product is 1042 bits, MSW of double-width bignum always 0
- //
- EC_ASSERT(0 == a[0]);
+ // P521: product is 1042 bits, MSW of double-width bignum always 0
+ //
+ EC_ASSERT(0 == a[0]);
- BN_COPY(r, a);
- bn_shl(r, a[NWORDS]);
+ BN_COPY(r, a);
+ bn_shl(r, a[NWORDS]);
- bn_mul(dbl, r, consts_p()->ec_order_qn);
- bn_shl(dbl, dbl[NWORDS]); // MS 521 bits of product
- bn_add(r, dbl);
+ bn_mul(dbl, r, consts_p()->ec_order_qn);
+ bn_shl(dbl, dbl[NWORDS]); // MS 521 bits of product
+ bn_add(r, dbl);
- bn_mul(dbl, r, consts_p()->ec_order); // N * floor(A / N)
- EC_ASSERT(bn_cmp(dbl, a) <= 0);
- EC_ASSERT(bn_cmp(dbl+NWORDS, a+NWORDS) <= 0);
+ bn_mul(dbl, r, consts_p()->ec_order); // N * floor(A / N)
+ EC_ASSERT(bn_cmp(dbl, a) <= 0);
+ EC_ASSERT(bn_cmp(dbl+NWORDS, a+NWORDS) <= 0);
- BN_COPY(r, a+NWORDS);
- bn_sub(r, dbl+NWORDS); // A - (N * floor(A/N))
+ BN_COPY(r, a+NWORDS);
+ bn_sub(r, dbl+NWORDS); // A - (N * floor(A/N))
- if (bn_cmp(r, consts_p()->ec_order) >= 0)
- bn_sub(r, consts_p()->ec_order);
+ if (bn_cmp(r, consts_p()->ec_order) >= 0)
+ {
+ bn_sub(r, consts_p()->ec_order);
+ }
- if (bn_cmp(r, consts_p()->ec_order) >= 0)
- bn_sub(r, consts_p()->ec_order); // XXX can this still be 2+ over?
+ if (bn_cmp(r, consts_p()->ec_order) >= 0)
+ {
+ bn_sub(r, consts_p()->ec_order); // XXX can this still be 2+ over?
+ }
- EC_ASSERT(bn_cmp(r, consts_p()->ec_order) < 0);
+ EC_ASSERT(bn_cmp(r, consts_p()->ec_order) < 0);
}
static void bn_modmul_order (bn_t *a, const bn_t *b)
{
- bn_t prod[ NWORDS+NWORDS ];
+ bn_t prod[ NWORDS+NWORDS ];
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
- bn_mul(prod, a, b);
- bn_modred_p521_order(a, prod);
+ bn_mul(prod, a, b);
+ bn_modred_p521_order(a, prod);
}
-//-------------------------------------
// negative,0,positive for a<b, a==b, a>b
//
#if defined(__BIG_ENDIAN) && !defined(BN_POWER64_CMP)
static int bn_cmp (const bn_t *a, const bn_t *b)
{
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
- return memcmp(a, b, sizeof(bn_t)*NWORDS);
+ return memcmp(a, b, sizeof(bn_t)*NWORDS);
}
-#else /* defined(__BIG_ENDIAN) */
+#else /* defined(__BIG_ENDIAN) */
static int __attribute__((noinline)) bn_cmp (const bn_t *a, const bn_t *b)
{
- bnindex_t i;
+ bnindex_t i;
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
- for (i=0; i<NWORDS; ++i) {
- if (a[i] != b[i])
- return 1 - ((a[i] < b[i]) <<1);
- }
+ for (i=0; i<NWORDS; ++i)
+ {
+ if (a[i] != b[i])
+ {
+ return 1 - ((a[i] < b[i]) <<1);
+ }
+ }
- return 0;
+ return 0;
}
#endif /* defined(__BIG_ENDIAN) */
-
-
-//-------------------------------------
//removed:
//static const bn_t bn_zero[ NWORDS ];
@@ -869,366 +864,368 @@ static int __attribute__((noinline)) bn_cmp (const bn_t *a, const bn_t *b)
//
static int bn_is_zero (const bn_t *m, unsigned int mn)
{
- EC_ASSERT(NULL != m);
- EC_ASSERT(mn < NWORDS);
+ EC_ASSERT(NULL != m);
+ EC_ASSERT(mn < NWORDS);
- const unsigned char *p2 = (const unsigned char *) m;
- size_t n=sizeof(bn_t)*(NWORDS-mn);
+ const unsigned char *p2 = (const unsigned char *) m;
+ size_t n=sizeof(bn_t)*(NWORDS-mn);
- while (n-- > 0) {
- if (0 != *p2)
- return !(0 - *p2);
- p2 += 1;
- }
-
- return !0;
+ while (n-- > 0)
+ {
+ if (0 != *p2)
+ {
+ return !(0 - *p2);
+ }
+ p2 += 1;
+ }
-// replaces:
-// return !memcmp(bn_zero, m, sizeof(bn_t)*(NWORDS-mn));
+ return !0;
}
-//-------------------------------------
static void __attribute__((noinline)) bn_add (bn_t *a, const bn_t *b)
{
- bn_t aw, cf = 0; /* aw: copy of current word to allow a==b */
- bnindex_t i = NWORDS;
+ bn_t aw, cf = 0; /* aw: copy of current word to allow a==b */
+ bnindex_t i = NWORDS;
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
- a += NWORDS-1;
- b += NWORDS-1;
+ a += NWORDS-1;
+ b += NWORDS-1;
- while (0 < i--) {
- aw = *a;
- if (cf)
- cf = (0 == ++aw);
-
- aw += *b;
- cf |= (aw < *(b--));
- *(a--) = aw;
- }
+ while (0 < i--)
+ {
+ aw = *a;
+ if (cf)
+ {
+ cf = (0 == ++aw);
+ }
+ aw += *b;
+ cf |= (aw < *(b--));
+ *(a--) = aw;
+ }
}
-//-------------------------------------
// a,b < prime
// never with order as base
//
static void bn_modadd (bn_t *a, const bn_t *b)
{
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
- //EC_ASSERT(!bn_ge_prime(a));
- //EC_ASSERT(!bn_ge_prime(b));
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
+ //EC_ASSERT(!bn_ge_prime(a));
+ //EC_ASSERT(!bn_ge_prime(b));
- bn_add(a, b); // P521: can not generate carry (unused MSW bits)
- // other curves need to handle this carry
+ bn_add(a, b); // P521: can not generate carry (unused MSW bits)
+ // other curves need to handle this carry
#ifndef EC_POWER64_RED
- if (bn_ge_prime(a))
- bn_sub(a, consts_p()->ec_prime);
+ if (bn_ge_prime(a))
+ {
+ bn_sub(a, consts_p()->ec_prime);
+ }
#endif
}
-//-------------------------------------
// never with order as base
static bn_t bn_sub (bn_t *a, const bn_t *b)
{
- bnindex_t i = NWORDS;
- bn_t bw, cf = 0;
-
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
-
- a += NWORDS-1;
- b += NWORDS-1;
-
- while (0 < i--) {
- if (cf)
- cf = (0 == (*a)--);
-
- bw = *b;
- cf |= (*a < *(b--));
- *(a--) -= bw;
- }
+ bnindex_t i = NWORDS;
+ bn_t bw, cf = 0;
+
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
+
+ a += NWORDS-1;
+ b += NWORDS-1;
+
+ while (0 < i--) {
+ if (cf)
+ {
+ cf = (0 == (*a)--);
+ }
+ bw = *b;
+ cf |= (*a < *(b--));
+ *(a--) -= bw;
+ }
- return cf;
+ return cf;
}
-
-//-------------------------------------
// never modular-subtracting with ec_order[], only with ec_prime[]
// therefore, implicit modulus
//
static void bn_modsub (bn_t *a, const bn_t *b)
{
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != b);
- //EC_ASSERT(!bn_ge_prime(a));
- EC_ASSERT(!bn_ge_prime(b));
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != b);
+ EC_ASSERT(!bn_ge_prime(b));
- if (bn_sub(a, b))
- bn_add(a, consts_p()->ec_prime);
+ if (bn_sub(a, b))
+ {
+ bn_add(a, consts_p()->ec_prime);
+ }
}
-
-
-//-------------------------------------
// only rn LS words are touched
//
static void bn_shl_n (bn_t r[NWORDS], unsigned int rn, unsigned int bits)
{
- bn_t cf = 0, cfin;
+ bn_t cf = 0, cfin;
- EC_DEVASSERT(NULL != r);
- EC_ASSERT(rn <= NWORDS);
+ EC_DEVASSERT(NULL != r);
+ EC_ASSERT(rn <= NWORDS);
- r += NWORDS-rn;
+ r += NWORDS-rn;
- if (bits >= BN_BITS) { // unlikely, most modinv shift is <5 bits
- cfin = bits / BN_BITS; // whole words
+ if (bits >= BN_BITS) // unlikely, most modinv shift is <5 bits
+ {
+ cfin = bits / BN_BITS; // whole words
- memmove(r, r+cfin, (NWORDS-cfin)*sizeof(bn_t));
+ memmove(r, r+cfin, (NWORDS-cfin)*sizeof(bn_t));
#ifndef BN_POWER64_CLR
- memset(r+NWORDS-cfin, 0, cfin*sizeof(bn_t));
+ memset(r+NWORDS-cfin, 0, cfin*sizeof(bn_t));
#else
- bn_clr(r+NWORDS-cfin, cfin);
+ bn_clr(r+NWORDS-cfin, cfin);
#endif
- bits %= BN_BITS;
- }
+ bits %= BN_BITS;
+ }
- if (bits) {
- r += rn-1;
+ if (bits)
+ {
+ r += rn-1;
+ while (0<rn--)
+ {
+ cfin = cf;
+ cf = (*r >> (BN_BITS - bits));
+ *r <<= bits;
+ *r |= cfin;
+ --r;
+ }
+ }
+}
- while (0<rn--) {
- cfin = cf;
- cf = (*r >> (BN_BITS - bits));
+static unsigned int bn_bits (const bn_t *a)
+{
+ unsigned int full = 8*BNBYTES;
+ bnindex_t i;
+ bn_t an;
- *r <<= bits;
- *r |= cfin;
- --r;
- }
- }
+ for (i=0; i<NWORDS; ++i)
+ {
+ full -= BN_BITS;
+ an = a[i];
+
+ if (!an)
+ {
+ continue;
+ }
+
+ while (an > 0xff)
+ {
+ full += 8;
+ an >>= 8;
+ }
+
+ while (an)
+ {
+ ++full;
+ an >>= 1;
+ }
+ return full;
+ }
+ return 0;
}
+// XXX route to bnt_msbit
+//
+#define bn_is_negative(p) (0x1000 & (*(p)))
-
-static unsigned int bn_bits (const bn_t *a)
+// inv stores S during run
+//
+static int bn_modinv(bn_t *inv, const bn_t *a, const bn_t *n)
{
- unsigned int full = 8*BNBYTES;
- bnindex_t i;
- bn_t an;
+ bn_t r[ NWORDS ], s[ NWORDS ], u[ NWORDS ], v[ NWORDS ],
+ ss[ NWORDS ], vs[ NWORDS ]; // shifted S,V
+ unsigned int shl, ub, vb; // shift amount; bitcount
+ bn_t *pr = r, *ps = s, *pu = u, *pv = v, *pt;
- for (i=0; i<NWORDS; ++i) {
- full -= BN_BITS;
- an = a[i];
+ EC_ASSERT(NULL != inv);
+ EC_ASSERT(NULL != a);
+ EC_ASSERT(NULL != n);
+ EC_ASSERT(bn_cmp(a,n) < 0);
+ EC_ASSERT(!bn_is_zero(a,0));
- if (!an)
- continue;
+ bn_clear(r);
+ bn_clear(s);
+ BN_LSW(s) = 1;
- while (an > 0xff) {
- full += 8;
- an >>= 8;
- }
+ BN_COPY(u, n);
+ BN_COPY(v, a);
- while (an) {
- ++full;
- an >>= 1;
- }
+ // ub = bn_bits(u);
+ ub = EC_PRIMEBITS; // P521: only ec_prime or ec_order possible
+ vb = bn_bits(v);
- return full;
- }
+ while (1 < vb)
+ {
+ EC_ASSERT(ub >= vb);
+ shl = ub-vb;
+
+ BN_COPY(vs, pv);
+ BN_COPY(ss, ps);
+ if (shl)
+ {
+ bn_shl_n(vs, NWORDS, shl);
+ bn_shl_n(ss, NWORDS, shl);
+ }
+
+ if (bn_is_negative(pv) == bn_is_negative(pu))
+ {
+ bn_sub(pu, vs);
+ bn_sub(pr, ss);
+ }
+ else
+ {
+ bn_add(pu, vs);
+ bn_add(pr, ss);
+ }
+
+ if (bn_is_negative(pu))
+ {
+ bn_clear(ss);
+ bn_sub(ss, pu);
+ ub = bn_bits(ss);
+ }
+ else
+ {
+ ub = bn_bits(pu);
+ }
+
+ if (ub < vb)
+ {
+ shl = ub; // shl,ss used as swap-scratch
+ ub = vb;
+ vb = shl;
+
+ pt = pu;
+ pu = pv;
+ pv = pt;
+
+ pt = ps;
+ ps = pr;
+ pr = pt;
+ }
+ }
- return 0;
-}
+ if (bn_is_negative(pv))
+ {
+ BN_COPY(ss, ps);
+ bn_clear(ps);
+ bn_sub(ps, ss);
+ }
+ if (bn_is_negative(ps))
+ {
+ bn_add(ps, n);
+ }
-// XXX route to bnt_msbit
-//
-#define bn_is_negative(p) (0x1000 & (*(p)))
+ if (bn_cmp(ps, n) >= 0)
+ {
+ bn_sub(ps, n);
+ }
+ BN_COPY(inv, ps);
-// inv stores S during run
-//
-static int bn_modinv(bn_t *inv, const bn_t *a, const bn_t *n)
-{
- bn_t r[ NWORDS ], s[ NWORDS ], u[ NWORDS ], v[ NWORDS ],
- ss[ NWORDS ], vs[ NWORDS ]; // shifted S,V
- unsigned int shl, ub, vb; // shift amount; bitcount
- bn_t *pr = r, *ps = s, *pu = u, *pv = v, *pt;
-
- EC_ASSERT(NULL != inv);
- EC_ASSERT(NULL != a);
- EC_ASSERT(NULL != n);
- EC_ASSERT(bn_cmp(a,n) < 0);
- EC_ASSERT(!bn_is_zero(a,0));
-
- // [1, a]
- // [0, n]
-
- bn_clear(r);
- bn_clear(s);
- BN_LSW(s) = 1;
-
- BN_COPY(u, n);
- BN_COPY(v, a);
-
-// bn_print("U ", u);
-// bn_print("V ", v);
- // ub = bn_bits(u);
- ub = EC_PRIMEBITS; // P521: only ec_prime or ec_order possible
- vb = bn_bits(v);
-// printf("%d,%d\n", (int) ub, (int) vb);
-
- while (1 < vb) {
- EC_ASSERT(ub >= vb);
- shl = ub-vb;
-// printf("< %d\n", shl);
-
- BN_COPY(vs, pv);
- BN_COPY(ss, ps);
- if (shl) {
- bn_shl_n(vs, NWORDS, shl);
- bn_shl_n(ss, NWORDS, shl);
- }
-
- if (bn_is_negative(pv) == bn_is_negative(pu)) {
- bn_sub(pu, vs);
- bn_sub(pr, ss);
- } else {
- bn_add(pu, vs);
- bn_add(pr, ss);
- }
-
-// bn_print("u ", pu);
-// bn_print("r ", pr);
- if (bn_is_negative(pu)) {
- bn_clear(ss);
- bn_sub(ss, pu);
- ub = bn_bits(ss);
- } else {
- ub = bn_bits(pu);
- }
-
- if (ub < vb) {
- shl = ub; // shl,ss used as swap-scratch
- ub = vb;
- vb = shl;
-
- pt = pu;
- pu = pv;
- pv = pt;
-
- pt = ps;
- ps = pr;
- pr = pt;
- }
-// printf("\n");
- }
-
- if (bn_is_negative(pv)) {
- BN_COPY(ss, ps);
- bn_clear(ps);
- bn_sub(ps, ss);
- }
-
- if (bn_is_negative(ps))
- bn_add(ps, n);
-
- if (bn_cmp(ps, n) >= 0)
- bn_sub(ps, n);
- BN_COPY(inv, ps);
-
- return 1;
+ return 1;
}
-
-//-------------------------------------
#if defined(__BIG_ENDIAN)
-
static void bn_read_pt(bn_t *r, const unsigned char *data)
{
- EC_ASSERT(NULL != r);
- EC_ASSERT(NULL != data);
+ EC_ASSERT(NULL != r);
+ EC_ASSERT(NULL != data);
- r[0] = 0;
- memmove(((unsigned char *) r) +BNBYTES-EC_PRIMEBYTES,
- data, EC_PRIMEBYTES);
+ r[0] = 0;
+ memmove(((unsigned char *) r) +BNBYTES-EC_PRIMEBYTES,
+ data, EC_PRIMEBYTES);
}
-
// P521: hash does not have unused MS words
//
static void bn_read_hash(bn_t *r, const unsigned char *data)
{
- EC_ASSERT(NULL != r);
- EC_ASSERT(NULL != data);
+ EC_ASSERT(NULL != r);
+ EC_ASSERT(NULL != data);
- r[0] = 0;
- memmove(((unsigned char *) r) +BNBYTES-EC_HASHBYTES,
- data, EC_HASHBYTES);
+ r[0] = 0;
+ memmove(((unsigned char *) r) +BNBYTES-EC_HASHBYTES,
+ data, EC_HASHBYTES);
}
-
#else
static void bn_read(bn_t *r, const unsigned char *data, size_t dlen)
{
- bnindex_t i, whole = dlen / sizeof(bn_t),
- rem = dlen % sizeof(bn_t);
- bn_t acc = 0;
+ bnindex_t i, whole = dlen / sizeof(bn_t),
+ rem = dlen % sizeof(bn_t);
+ bn_t acc = 0;
- EC_ASSERT(NULL != r);
- EC_ASSERT(NULL != data);
- EC_ASSERT(dlen <= EC_PRIMEBYTES);
+ EC_ASSERT(NULL != r);
+ EC_ASSERT(NULL != data);
+ EC_ASSERT(dlen <= EC_PRIMEBYTES);
- acc = whole + (!!rem);
- if (acc < NWORDS) { // unused MS words
- acc = NWORDS - acc;
+ acc = whole + (!!rem);
+ if (acc < NWORDS) // unused MS words
+ {
+ acc = NWORDS - acc;
#ifndef BN_POWER64_CLR
- memset(r, 0, acc*sizeof(bn_t));
+ memset(r, 0, acc*sizeof(bn_t));
#else
- bn_clr(r, acc);
+ bn_clr(r, acc);
#endif
- r += acc;
- }
-
- acc = 0;
- if (rem) {
- ++whole;
- } else {
- rem = sizeof(bn_t);
- }
-
- while (0 < whole--) {
- for (i=0; i<rem; ++i)
- acc = (acc <<8) + *(data++);
- *(r++) = acc;
- acc = 0;
- rem = sizeof(bn_t);
- }
-}
+ r += acc;
+ }
+
+ acc = 0;
+ if (rem)
+ {
+ ++whole;
+ }
+ else
+ {
+ rem = sizeof(bn_t);
+ }
+ while (0 < whole--)
+ {
+ for (i=0; i<rem; ++i)
+ {
+ acc = (acc <<8) + *(data++);
+ }
+ *(r++) = acc;
+ acc = 0;
+ rem = sizeof(bn_t);
+ }
+}
static void bn_read_pt(bn_t *r, const unsigned char *data)
{
- return bn_read(r, data, EC_PRIMEBYTES);
+ return bn_read(r, data, EC_PRIMEBYTES);
}
-
static void bn_read_hash(bn_t *r, const unsigned char *data)
{
- return bn_read(r, data, EC_HASHBYTES);
+ return bn_read(r, data, EC_HASHBYTES);
}
#endif /* defined(__BIG_ENDIAN) */
-
//======================================================= EC primitives ====
/* (0,0) is our infinity, since it's not a curve point */
#define ec_is_infinity(px, py, pz) \
@@ -1236,178 +1233,175 @@ static void bn_read_hash(bn_t *r, const unsigned char *data)
#define ec_set_infinity(p) bn_clear(p)
-
-//-------------------------------------
// (x) is transformed back to affine from projective (X*Z)
//
static void ec_projective2affine (bn_t *x, const bn_t *z)
{
- bn_t zinv[ NWORDS ];
+ bn_t zinv[ NWORDS ];
- EC_ASSERT(NULL != x);
- EC_ASSERT(NULL != z);
+ EC_ASSERT(NULL != x);
+ EC_ASSERT(NULL != z);
- EC_ASSERT(!bn_ge_prime(x));
- EC_ASSERT(!bn_ge_prime(z));
+ EC_ASSERT(!bn_ge_prime(x));
+ EC_ASSERT(!bn_ge_prime(z));
- bn_modinv(zinv, z, consts_p()->ec_prime);
- bn_modmul_prime(x, zinv);
+ bn_modinv(zinv, z, consts_p()->ec_prime);
+ bn_modmul_prime(x, zinv);
#ifdef EC_POWER64_RED
- bn_modred_slow(x);
+ bn_modred_slow(x);
#endif
}
-
// returns 1 if result is at infinity, 0 otherwise
//
static int ec_add (bn_t *x1, bn_t *y1, bn_t *z1,
const bn_t *x2, const bn_t *y2, const bn_t *z2)
{
- bn_t a[ NWORDS ], b[ NWORDS ], c[ NWORDS ],
- bs[ NWORDS ], // B^2
- t1[ NWORDS ], t2[ NWORDS ]; // XXX minimize these
- int inf1, inf2;
-
- EC_ASSERT(NULL != x1);
- EC_ASSERT(NULL != y1);
- EC_ASSERT(NULL != z1);
- EC_ASSERT(NULL != x2);
- EC_ASSERT(NULL != y2);
- EC_ASSERT(NULL != z2);
- EC_ASSERT(!bn_ge_prime(x1));
- EC_ASSERT(!bn_ge_prime(y1));
- EC_ASSERT(!bn_ge_prime(z1));
- EC_ASSERT(!bn_ge_prime(x2));
- EC_ASSERT(!bn_ge_prime(y2));
- EC_ASSERT(!bn_ge_prime(z2));
-
- inf1 = ec_is_infinity(x1, y1, z1);
- inf2 = ec_is_infinity(x2, y2, z2);
-
- if (inf2)
- return inf1;
-
- if (inf1) {
- BN_COPY(x1, x2);
- BN_COPY(y1, y2);
- BN_COPY(z1, z2);
- return 0; // (x1,y1,z1) not infinity (checked above)
- }
-
- if (!bn_cmp(x1, x2) && !bn_cmp(y1, y2))
- return ec_double(x1, y1, z1);
+ bn_t a[ NWORDS ], b[ NWORDS ], c[ NWORDS ],
+ bs[ NWORDS ], // B^2
+ t1[ NWORDS ], t2[ NWORDS ]; // XXX minimize these
+ int inf1, inf2;
+
+ EC_ASSERT(NULL != x1);
+ EC_ASSERT(NULL != y1);
+ EC_ASSERT(NULL != z1);
+ EC_ASSERT(NULL != x2);
+ EC_ASSERT(NULL != y2);
+ EC_ASSERT(NULL != z2);
+ EC_ASSERT(!bn_ge_prime(x1));
+ EC_ASSERT(!bn_ge_prime(y1));
+ EC_ASSERT(!bn_ge_prime(z1));
+ EC_ASSERT(!bn_ge_prime(x2));
+ EC_ASSERT(!bn_ge_prime(y2));
+ EC_ASSERT(!bn_ge_prime(z2));
+
+ inf1 = ec_is_infinity(x1, y1, z1);
+ inf2 = ec_is_infinity(x2, y2, z2);
+
+ if (inf2)
+ {
+ return inf1;
+ }
+
+ if (inf1)
+ {
+ BN_COPY(x1, x2);
+ BN_COPY(y1, y2);
+ BN_COPY(z1, z2);
+ return 0; // (x1,y1,z1) not infinity (checked above)
+ }
+
+ if (!bn_cmp(x1, x2) && !bn_cmp(y1, y2))
+ {
+ return ec_double(x1, y1, z1);
+ }
#ifdef EC_POWER64_ALG
- BN_COPY(t1, y1);
- bn_modmul_prime(t1, z2); // t1 = y1 * z2
- BN_COPY(a, y2);
- bn_modmul_prime(a, z1); // A = y2 * z1 - y1 * z2
+ BN_COPY(t1, y1);
+ bn_modmul_prime(t1, z2); // t1 = y1 * z2
+ BN_COPY(a, y2);
+ bn_modmul_prime(a, z1); // A = y2 * z1 - y1 * z2
#ifdef EC_POWER64_RED
- bn_modred_slow(t1);
+ bn_modred_slow(t1);
#endif
- bn_modsub(a, t1);
-
- bn_modmul_prime(x1, z2); // x1 := x1 * z2 orig x1 no longer used
- BN_COPY(b, x2);
- bn_modmul_prime(b, z1);
+ bn_modsub(a, t1);
+ bn_modmul_prime(x1, z2); // x1 := x1 * z2 orig x1 no longer used
+ BN_COPY(b, x2);
+ bn_modmul_prime(b, z1);
#ifdef EC_POWER64_RED
- bn_modred_slow(x1);
+ bn_modred_slow(x1);
#endif
- bn_modsub(b, x1); // B = x2 * z1 - x1 * z2
+ bn_modsub(b, x1); // B = x2 * z1 - x1 * z2
- BN_COPY(bs, b);
- bn_modsqr_prime(bs); // B^2
+ BN_COPY(bs, b);
+ bn_modsqr_prime(bs); // B^2
- BN_COPY(c, a);
- bn_modsqr_prime(c);
- bn_modmul_prime(z1, z2); // z1 = z1 * z2
- bn_modmul_prime(c, z1); // c = A^2 * z1 * z2
+ BN_COPY(c, a);
+ bn_modsqr_prime(c);
+ bn_modmul_prime(z1, z2); // z1 = z1 * z2
+ bn_modmul_prime(c, z1); // c = A^2 * z1 * z2
- bn_modmul_prime(x1, bs); // x1 = B^2 * x1 * z2
- BN_COPY(t2, b);
- bn_modmul_prime(t2, bs); // t2 = B^3
+ bn_modmul_prime(x1, bs); // x1 = B^2 * x1 * z2
+ BN_COPY(t2, b);
+ bn_modmul_prime(t2, bs); // t2 = B^3
#ifdef EC_POWER64_RED
- bn_modred_slow(t2);
- bn_modred_slow(x1);
+ bn_modred_slow(t2);
+ bn_modred_slow(x1);
#endif
- bn_modsub(c, t2);
- bn_modsub(c, x1); // C = A^2 * z1 * z2 - B^3
- bn_modsub(c, x1); // - 2 B^2 * x1 * z1
+ bn_modsub(c, t2);
+ bn_modsub(c, x1); // C = A^2 * z1 * z2 - B^3
+ bn_modsub(c, x1); // - 2 B^2 * x1 * z1
- bn_modmul_prime(z1, t2); // z1 * z2 * B^3
+ bn_modmul_prime(z1, t2); // z1 * z2 * B^3
#ifdef EC_POWER64_RED
- bn_modred_slow(z1);
- bn_modred_slow(c);
+ bn_modred_slow(z1);
+ bn_modred_slow(c);
#endif
- bn_modmul_prime(t1, t2); // (B^3 * y1 * z2)
- // A(B 2 X1 Z2 ? C)
- bn_modsub(x1, c);
- bn_modmul_prime(x1, a); // A * (B^2 * x1 * z2 - C)
+ bn_modmul_prime(t1, t2); // (B^3 * y1 * z2)
+ // A(B 2 X1 Z2 ? C)
+ bn_modsub(x1, c);
+ bn_modmul_prime(x1, a); // A * (B^2 * x1 * z2 - C)
#ifdef EC_POWER64_RED
- bn_modred_slow(x1);
- bn_modred_slow(t1);
+ bn_modred_slow(x1);
+ bn_modred_slow(t1);
#endif
- bn_modsub(x1, t1); // Y = A * (B^2 * x1 * z2 - C) - (B^3 * y1 * z2)
- BN_COPY(y1, x1);
+ bn_modsub(x1, t1); // Y = A * (B^2 * x1 * z2 - C) - (B^3 * y1 * z2)
+ BN_COPY(y1, x1);
- BN_COPY(x1, b);
- bn_modmul_prime(x1, c); // X = B * C
+ BN_COPY(x1, b);
+ bn_modmul_prime(x1, c); // X = B * C
#ifdef EC_POWER64_RED
- bn_modred_slow(x1);
+ bn_modred_slow(x1);
#endif
#else // !EC_POWER64_ALG
- BN_COPY(t1, y1);
- bn_modmul_prime(t1, z2); // t1 = y1 * z2
- BN_COPY(a, y2);
- bn_modmul_prime(a, z1); // A = y2 * z1 - y1 * z2
- bn_modsub(a, t1);
-
- bn_modmul_prime(x1, z2); // x1 := x1 * z2 orig x1 no longer used
- BN_COPY(b, x2);
- bn_modmul_prime(b, z1);
- bn_modsub(b, x1); // B = x2 * z1 - x1 * z2
-
- BN_COPY(bs, b);
- bn_modmul_prime(bs, bs); // B^2
-
- BN_COPY(c, a);
- bn_modmul_prime(c, c);
- bn_modmul_prime(c, z1);
- bn_modmul_prime(c, z2);
-
- BN_COPY(t2, b);
- bn_modadd(t2, x1);
- bn_modadd(t2, x1);
- bn_modmul_prime(t2, bs);
- bn_modsub(c, t2); // C = A^2 * z1 * z2 - B^3
- // - 2 B^2 * x1 * z1
-
- bn_modmul_prime(z1, z2);
- bn_modmul_prime(z1, b);
- bn_modmul_prime(z1, bs); // z1 * z2 * B^3
-
- bn_modmul_prime(t1, b);
- bn_modmul_prime(t1, bs); // (B^3 * y1 * z2)
- // A(B 2 X1 Z2 ? C)
- bn_modmul_prime(x1, bs); // (B^2 * x1 * z2)
- bn_modsub(x1, c);
- bn_modmul_prime(x1, a); // A * (B^2 * x1 * z2 - C)
- bn_modsub(x1, t1);
- BN_COPY(y1, x1); // Y =
-
- BN_COPY(x1, b);
- bn_modmul_prime(x1, c); // X = B * C
+ BN_COPY(t1, y1);
+ bn_modmul_prime(t1, z2); // t1 = y1 * z2
+ BN_COPY(a, y2);
+ bn_modmul_prime(a, z1); // A = y2 * z1 - y1 * z2
+ bn_modsub(a, t1);
+
+ bn_modmul_prime(x1, z2); // x1 := x1 * z2 orig x1 no longer used
+ BN_COPY(b, x2);
+ bn_modmul_prime(b, z1);
+ bn_modsub(b, x1); // B = x2 * z1 - x1 * z2
+
+ BN_COPY(bs, b);
+ bn_modmul_prime(bs, bs); // B^2
+
+ BN_COPY(c, a);
+ bn_modmul_prime(c, c);
+ bn_modmul_prime(c, z1);
+ bn_modmul_prime(c, z2);
+
+ BN_COPY(t2, b);
+ bn_modadd(t2, x1);
+ bn_modadd(t2, x1);
+ bn_modmul_prime(t2, bs);
+ bn_modsub(c, t2); // C = A^2 * z1 * z2 - B^3
+ // - 2 B^2 * x1 * z1
+
+ bn_modmul_prime(z1, z2);
+ bn_modmul_prime(z1, b);
+ bn_modmul_prime(z1, bs); // z1 * z2 * B^3
+
+ bn_modmul_prime(t1, b);
+ bn_modmul_prime(t1, bs); // (B^3 * y1 * z2)
+ // A(B 2 X1 Z2 ? C)
+ bn_modmul_prime(x1, bs); // (B^2 * x1 * z2)
+ bn_modsub(x1, c);
+ bn_modmul_prime(x1, a); // A * (B^2 * x1 * z2 - C)
+ bn_modsub(x1, t1);
+ BN_COPY(y1, x1); // Y =
+
+ BN_COPY(x1, b);
+ bn_modmul_prime(x1, c); // X = B * C
#endif
- return 0;
+ return 0;
}
-
-
-
-//----------------------------------------------------------------------------
// (x,y,z) in projective coordinates
// P521: curve has a==-3
//
@@ -1415,137 +1409,136 @@ static int ec_add (bn_t *x1, bn_t *y1, bn_t *z1,
//
static int ec_double (bn_t *x, bn_t *y, bn_t *z)
{
- bn_t a[ NWORDS ], b[ NWORDS ], c[ NWORDS ], d[ NWORDS ], t[ NWORDS ];
+ bn_t a[ NWORDS ], b[ NWORDS ], c[ NWORDS ], d[ NWORDS ], t[ NWORDS ];
- EC_ASSERT(NULL != x);
- EC_ASSERT(NULL != y);
- EC_ASSERT(NULL != z);
- EC_ASSERT(!bn_ge_prime(x));
- EC_ASSERT(!bn_ge_prime(y));
- EC_ASSERT(!bn_ge_prime(z));
+ EC_ASSERT(NULL != x);
+ EC_ASSERT(NULL != y);
+ EC_ASSERT(NULL != z);
+ EC_ASSERT(!bn_ge_prime(x));
+ EC_ASSERT(!bn_ge_prime(y));
+ EC_ASSERT(!bn_ge_prime(z));
#ifdef EC_POWER64_ALG
- BN_COPY(a, x);
- BN_COPY(d, x);
-
- bn_modadd(a, z);
- bn_modsub(d, z);
- bn_modmul_prime(a, d); // x^2 - z^2
- BN_COPY(d, a);
- bn_modadd(a, a);
- bn_modadd(a, d); // A = 3 * (x^2 - z^2)
- // P521: generally, A = 3 * x^2 - a * z^2
-
- BN_COPY(b, z);
- bn_modmul_prime(b, y); // B = y * z
-
- BN_COPY(c, x);
- bn_modmul_prime(y, b); // y = y * B
- bn_modmul_prime(c, y); // C = x * y * B
-
- BN_COPY(z, b);
- bn_modsqr_prime(z);
- bn_modmul_prime(z, b);
- bn_modadd(z, z);
- bn_modadd(z, z);
- bn_modadd(z, z); // Z = 8 * B^3
+ BN_COPY(a, x);
+ BN_COPY(d, x);
+
+ bn_modadd(a, z);
+ bn_modsub(d, z);
+ bn_modmul_prime(a, d); // x^2 - z^2
+ BN_COPY(d, a);
+ bn_modadd(a, a);
+ bn_modadd(a, d); // A = 3 * (x^2 - z^2)
+ // P521: generally, A = 3 * x^2 - a * z^2
+
+ BN_COPY(b, z);
+ bn_modmul_prime(b, y); // B = y * z
+
+ BN_COPY(c, x);
+ bn_modmul_prime(y, b); // y = y * B
+ bn_modmul_prime(c, y); // C = x * y * B
+
+ BN_COPY(z, b);
+ bn_modsqr_prime(z);
+ bn_modmul_prime(z, b);
+ bn_modadd(z, z);
+ bn_modadd(z, z);
+ bn_modadd(z, z); // Z = 8 * B^3
#ifdef EC_POWER64_RED
- bn_modred_slow(z);
+ bn_modred_slow(z);
#endif
- BN_COPY(t, c);
- bn_modadd(t, t);
- bn_modadd(t, t);
- bn_modadd(t, t);
- BN_COPY(d, a);
- bn_modsqr_prime(d);
+ BN_COPY(t, c);
+ bn_modadd(t, t);
+ bn_modadd(t, t);
+ bn_modadd(t, t);
+ BN_COPY(d, a);
+ bn_modsqr_prime(d);
#ifdef EC_POWER64_RED
- bn_modred_slow(t);
+ bn_modred_slow(t);
#endif
- bn_modsub(d, t); // D = A^2 - 8*C
+ bn_modsub(d, t); // D = A^2 - 8*C
- BN_COPY(x, b);
- bn_modmul_prime(x, d);
- bn_modadd(x, x); // X = 2 * B * D
+ BN_COPY(x, b);
+ bn_modmul_prime(x, d);
+ bn_modadd(x, x); // X = 2 * B * D
#ifdef EC_POWER64_RED
- bn_modred_slow(x);
- bn_modred_slow(d);
+ bn_modred_slow(x);
+ bn_modred_slow(d);
#endif
- bn_modadd(c, c);
- bn_modadd(c, c);
- bn_modsub(c, d);
- bn_modmul_prime(a, c); // (A * (4*C - D))
+ bn_modadd(c, c);
+ bn_modadd(c, c);
+ bn_modsub(c, d);
+ bn_modmul_prime(a, c); // (A * (4*C - D))
- bn_modsqr_prime(y); // (y * B)^2
- bn_modadd(y, y);
- bn_modadd(y, y);
- bn_modadd(y, y); // (8 * y^2 * B^2)
+ bn_modsqr_prime(y); // (y * B)^2
+ bn_modadd(y, y);
+ bn_modadd(y, y);
+ bn_modadd(y, y); // (8 * y^2 * B^2)
#ifdef EC_POWER64_RED
- bn_modred_slow(a);
- bn_modred_slow(y);
+ bn_modred_slow(a);
+ bn_modred_slow(y);
#endif
- bn_modsub(a, y);
- BN_COPY(y, a); // Y = A * (4*C - D) - 8 * y^2 * B^2
+ bn_modsub(a, y);
+ BN_COPY(y, a); // Y = A * (4*C - D) - 8 * y^2 * B^2
#else // !EC_POWER64_ALG
- BN_COPY(a, x);
- BN_COPY(d, z);
-
- bn_modmul_prime(a, x);
- bn_modmul_prime(d, z);
- bn_modsub(a, d);
- BN_COPY(d, a);
- bn_modadd(a, a);
- bn_modadd(a, d); // A = 3 * (x^2 - z^2)
- // P521: generally, A = 3 * x^2 - a * z^2
-
- BN_COPY(b, z);
- bn_modmul_prime(b, y); // B = y * z
-
- BN_COPY(c, y);
- bn_modmul_prime(c, b);
- bn_modmul_prime(c, x); // C = x * y * B
-
- BN_COPY(z, b);
- bn_modmul_prime(z, b);
- bn_modmul_prime(z, b);
- bn_modadd(z, z);
- bn_modadd(z, z);
- bn_modadd(z, z); // Z = 8 * B^3
-
- BN_COPY(t, c);
- bn_modadd(t, t);
- bn_modadd(t, t);
- bn_modadd(t, t);
- BN_COPY(d, a);
- bn_modmul_prime(d, a);
- bn_modsub(d, t); // D = A^2 - 8*C
-
- BN_COPY(x, b);
- bn_modmul_prime(x, d);
- bn_modadd(x, x); // X = 2 * B * D
-
- bn_modadd(c, c);
- bn_modadd(c, c);
- bn_modsub(c, d);
- bn_modmul_prime(a, c); // (A * (4*C - D))
-
- bn_modmul_prime(y, b);
- bn_modmul_prime(y, y);
- bn_modadd(y, y);
- bn_modadd(y, y);
- bn_modadd(y, y); // (8 * y^2 * B^2)
- bn_modsub(a, y);
- BN_COPY(y, a); // Y = A * (4*C - D) - 8 * y^2 * B^2
+ BN_COPY(a, x);
+ BN_COPY(d, z);
+
+ bn_modmul_prime(a, x);
+ bn_modmul_prime(d, z);
+ bn_modsub(a, d);
+ BN_COPY(d, a);
+ bn_modadd(a, a);
+ bn_modadd(a, d); // A = 3 * (x^2 - z^2)
+ // P521: generally, A = 3 * x^2 - a * z^2
+
+ BN_COPY(b, z);
+ bn_modmul_prime(b, y); // B = y * z
+
+ BN_COPY(c, y);
+ bn_modmul_prime(c, b);
+ bn_modmul_prime(c, x); // C = x * y * B
+
+ BN_COPY(z, b);
+ bn_modmul_prime(z, b);
+ bn_modmul_prime(z, b);
+ bn_modadd(z, z);
+ bn_modadd(z, z);
+ bn_modadd(z, z); // Z = 8 * B^3
+
+ BN_COPY(t, c);
+ bn_modadd(t, t);
+ bn_modadd(t, t);
+ bn_modadd(t, t);
+ BN_COPY(d, a);
+ bn_modmul_prime(d, a);
+ bn_modsub(d, t); // D = A^2 - 8*C
+
+ BN_COPY(x, b);
+ bn_modmul_prime(x, d);
+ bn_modadd(x, x); // X = 2 * B * D
+
+ bn_modadd(c, c);
+ bn_modadd(c, c);
+ bn_modsub(c, d);
+ bn_modmul_prime(a, c); // (A * (4*C - D))
+
+ bn_modmul_prime(y, b);
+ bn_modmul_prime(y, y);
+ bn_modadd(y, y);
+ bn_modadd(y, y);
+ bn_modadd(y, y); // (8 * y^2 * B^2)
+ bn_modsub(a, y);
+ BN_COPY(y, a); // Y = A * (4*C - D) - 8 * y^2 * B^2
#endif
- return 0;
+ return 0;
}
-//-------------------------------------
// (x,y) in affine coordinates; z is output only
// returns (x,y,z) in projective coordinates
//
@@ -1557,40 +1550,45 @@ static int ec_double (bn_t *x, bn_t *y, bn_t *z)
//
static int ec_multiply (bn_t *x, bn_t *y, bn_t *z, const bn_t *k)
{
- bn_t px[ NWORDS ], py[ NWORDS ], pz[ NWORDS ];
- unsigned int i;
- bn_t mask = 1;
-
- EC_ASSERT(NULL != x);
- EC_ASSERT(NULL != y);
- EC_ASSERT(NULL != k);
- EC_ASSERT(!bn_ge_prime(x));
- EC_ASSERT(!bn_ge_prime(y));
-
- i=bn_bits(k);
- k += NWORDS-1;
-
- BN_COPY(px, x);
- BN_COPY(py, y);
- bn_clear(x);
- bn_clear(y);
-
- bn_clear(z);
- BN_LSW(z) = 1; // (x,y) -> (x, y, 1) in projective coordinates
- BN_COPY(pz, z); // (px,py) -> (px,py,1)
-
- BN_DUMP(i,x);
- BN_DUMP(i,y);
- BN_DUMP(i,z);
- BN_DUMP(i,px);
- BN_DUMP(i,py);
- BN_DUMP(i,pz);
- while (0 < i--) {
- if (mask & *k)
- ec_add(x, y, z, px, py, pz);
+ bn_t px[ NWORDS ], py[ NWORDS ], pz[ NWORDS ];
+ unsigned int i;
+ bn_t mask = 1;
+
+ EC_ASSERT(NULL != x);
+ EC_ASSERT(NULL != y);
+ EC_ASSERT(NULL != k);
+ EC_ASSERT(!bn_ge_prime(x));
+ EC_ASSERT(!bn_ge_prime(y));
+
+ i=bn_bits(k);
+ k += NWORDS-1;
+
+ BN_COPY(px, x);
+ BN_COPY(py, y);
+ bn_clear(x);
+ bn_clear(y);
+
+ bn_clear(z);
+ BN_LSW(z) = 1; // (x,y) -> (x, y, 1) in projective coordinates
+ BN_COPY(pz, z); // (px,py) -> (px,py,1)
+
+ BN_DUMP(i,x);
+ BN_DUMP(i,y);
+ BN_DUMP(i,z);
+ BN_DUMP(i,px);
+ BN_DUMP(i,py);
+ BN_DUMP(i,pz);
+ while (0 < i--)
+ {
+ if (mask & *k)
+ {
+ ec_add(x, y, z, px, py, pz);
+ }
- if (0 < i)
- ec_double(px, py, pz);
+ if (0 < i)
+ {
+ ec_double(px, py, pz);
+ }
BN_DUMP(i,x);
BN_DUMP(i,y);
@@ -1598,15 +1596,16 @@ static int ec_multiply (bn_t *x, bn_t *y, bn_t *z, const bn_t *k)
BN_DUMP(i,px);
BN_DUMP(i,py);
BN_DUMP(i,pz);
- mask <<= 1;
- if (!mask) {
- --k;
- mask = 1;
- }
- }
+ mask <<= 1;
+ if (!mask)
+ {
+ --k;
+ mask = 1;
+ }
+ }
BN_EXIT();
- return 0;
+ return 0;
}
@@ -1616,47 +1615,57 @@ int ec_verify (const unsigned char *publicpt, /* 2*EC_COORDBYTES */
const unsigned char *hash, /* EC_HASHBYTES */
const unsigned char *signature) /* 2*EC_COORDBYTES */
{
- bn_t r[ NWORDS ], s[ NWORDS ], e[ NWORDS ],
- px[ NWORDS ], py[ NWORDS ], pz[ NWORDS ],
- u1[ NWORDS ], u2[ NWORDS ];
+ bn_t r[ NWORDS ], s[ NWORDS ], e[ NWORDS ],
+ px[ NWORDS ], py[ NWORDS ], pz[ NWORDS ],
+ u1[ NWORDS ], u2[ NWORDS ];
- if ((NULL == publicpt) || (NULL == signature) || (NULL == hash))
- return -1;
+ if ((NULL == publicpt) || (NULL == signature) || (NULL == hash))
+ {
+ return -1;
+ }
- bn_read_pt (r, signature);
- bn_read_pt (s, signature +EC_COORDBYTES);
- bn_read_hash(e, hash);
- bn_read_pt (px, publicpt);
- bn_read_pt (py, publicpt +EC_COORDBYTES);
+ bn_read_pt (r, signature);
+ bn_read_pt (s, signature +EC_COORDBYTES);
+ bn_read_hash(e, hash);
+ bn_read_pt (px, publicpt);
+ bn_read_pt (py, publicpt +EC_COORDBYTES);
- if (bn_ge_order(r) || bn_ge_order(s) ||
- bn_is_zero(s,0) || bn_is_zero(r,0))
- return 0; // assume user messed with signature
+ if (bn_ge_order(r) || bn_ge_order(s) ||
+ bn_is_zero(s,0) || bn_is_zero(r,0))
+ {
+ return 0; // assume user messed with signature
+ }
- if (bn_ge_prime(px) || bn_ge_prime(py) ||
- bn_is_zero(px,0) || bn_is_zero(py,0))
- return -1; // admin fault; should not happen
+ if (bn_ge_prime(px) || bn_ge_prime(py) ||
+ bn_is_zero(px,0) || bn_is_zero(py,0))
+ {
+ return -1; // admin fault; should not happen
+ }
- bn_modinv(u1, s, consts_p()->ec_order); // s no longer needed (NLN)
- BN_COPY(u2, r);
- bn_modmul_order(u2, u1);
- bn_modmul_order(u1, e); // e NLN
+ bn_modinv(u1, s, consts_p()->ec_order); // s no longer needed (NLN)
+ BN_COPY(u2, r);
+ bn_modmul_order(u2, u1);
+ bn_modmul_order(u1, e); // e NLN
- // reuse (e,s) for base multiplication
- BN_COPY(e, consts_p()->prime_px); // (e,s) <- (base point)
- BN_COPY(s, consts_p()->prime_py);
+ // reuse (e,s) for base multiplication
+ BN_COPY(e, consts_p()->prime_px); // (e,s) <- (base point)
+ BN_COPY(s, consts_p()->prime_py);
- ec_multiply(px, py, pz, u2); // (px,py,pz) = u2 * (px,py); u2 NLN
- ec_multiply(e, s, u2, u1); // (s, e, u2) = u1 * (gx,gy); u1 NLN
+ ec_multiply(px, py, pz, u2); // (px,py,pz) = u2 * (px,py); u2 NLN
+ ec_multiply(e, s, u2, u1); // (s, e, u2) = u1 * (gx,gy); u1 NLN
- if (ec_add(px, py, pz, e, s, u2)) // u1 * base + u2 * public
- return 0; // reached infinity (SNH with sig)
+ if (ec_add(px, py, pz, e, s, u2)) // u1 * base + u2 * public
+ {
+ return 0; // reached infinity (SNH with sig)
+ }
- ec_projective2affine(px, pz);
+ ec_projective2affine(px, pz);
- if (bn_ge_order(px))
- bn_sub(px, consts_p()->ec_order); // px mod order
+ if (bn_ge_order(px))
+ {
+ bn_sub(px, consts_p()->ec_order); // px mod order
+ }
- return (! bn_cmp(r, px));
+ return (! bn_cmp(r, px));
}
OpenPOWER on IntegriCloud