/*
- * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
*
- * Licensed under the OpenSSL license (the "License"). You may not use
+ * Licensed under the Apache License 2.0 (the "License"). You may not use
* this file except in compliance with the License. You can obtain a copy
* in the file LICENSE in the source distribution or at
* https://www.openssl.org/source/license.html
# include "internal/bn_int.h"
-#ifdef __cplusplus
-extern "C" {
-#endif
-
/*
* These preprocessor symbols control various aspects of the bignum headers
* and library code. They're not defined by any "normal" configuration, as
*/
# ifdef BN_DEBUG
-
-/* We only need assert() when debugging */
-# include <assert.h>
-
+/*
+ * The new BN_FLG_FIXED_TOP flag marks vectors that were not treated with
+ * bn_correct_top, in other words such vectors are permitted to have zeros
+ * in most significant limbs. Such vectors are used internally to achieve
+ * execution time invariance for critical operations with private keys.
+ * It's BN_DEBUG-only flag, because user application is not supposed to
+ * observe it anyway. Moreover, optimizing compiler would actually remove
+ * all operations manipulating the bit in question in non-BN_DEBUG build.
+ */
+# define BN_FLG_FIXED_TOP 0x10000
# ifdef BN_DEBUG_RAND
-/* To avoid "make update" cvs wars due to BN_DEBUG, use some tricks */
-# ifndef RAND_pseudo_bytes
-int RAND_pseudo_bytes(unsigned char *buf, int num);
-# define BN_DEBUG_TRIX
-# endif
# define bn_pollute(a) \
do { \
const BIGNUM *_bnum1 = (a); \
sizeof(*_not_const) * (_bnum1->dmax - _bnum1->top)); \
} \
} while(0)
-# ifdef BN_DEBUG_TRIX
-# undef RAND_pseudo_bytes
-# endif
# else
# define bn_pollute(a)
# endif
do { \
const BIGNUM *_bnum2 = (a); \
if (_bnum2 != NULL) { \
- assert((_bnum2->top == 0) || \
- (_bnum2->d[_bnum2->top - 1] != 0)); \
+ int _top = _bnum2->top; \
+ (void)ossl_assert((_top == 0 && !_bnum2->neg) || \
+ (_top && ((_bnum2->flags & BN_FLG_FIXED_TOP) \
+ || _bnum2->d[_top - 1] != 0))); \
bn_pollute(_bnum2); \
} \
} while(0)
# define bn_wcheck_size(bn, words) \
do { \
const BIGNUM *_bnum2 = (bn); \
- assert((words) <= (_bnum2)->dmax && (words) >= (_bnum2)->top); \
+ assert((words) <= (_bnum2)->dmax && \
+ (words) >= (_bnum2)->top); \
/* avoid unused variable warning with NDEBUG */ \
(void)(_bnum2); \
} while(0)
# else /* !BN_DEBUG */
+# define BN_FLG_FIXED_TOP 0
# define bn_pollute(a)
# define bn_check_top(a)
# define bn_fix_top(a) bn_correct_top(a)
/* Used for montgomery multiplication */
struct bn_mont_ctx_st {
int ri; /* number of bits in R */
- BIGNUM RR; /* used to convert to montgomery form */
+ BIGNUM RR; /* used to convert to montgomery form,
+ possibly zero-padded */
BIGNUM N; /* The modulus */
BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1 (Ni is only
* stored for bignum algorithm) */
(b) > 23 ? 3 : 1)
/*
- * BN_mod_exp_mont_conttime is based on the assumption that the L1 data cache
+ * BN_mod_exp_mont_consttime is based on the assumption that the L1 data cache
* line width of the target processor is at least the following value.
*/
# define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH ( 64 )
# if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) && !defined(PEDANTIC)
/*
* BN_UMULT_HIGH section.
- *
- * No, I'm not trying to overwhelm you when stating that the
- * product of N-bit numbers is 2*N bits wide:-) No, I don't expect
- * you to be impressed when I say that if the compiler doesn't
- * support 2*N integer type, then you have to replace every N*N
- * multiplication with 4 (N/2)*(N/2) accompanied by some shifts
- * and additions which unavoidably results in severe performance
- * penalties. Of course provided that the hardware is capable of
- * producing 2*N result... That's when you normally start
- * considering assembler implementation. However! It should be
- * pointed out that some CPUs (most notably Alpha, PowerPC and
- * upcoming IA-64 family:-) provide *separate* instruction
- * calculating the upper half of the product placing the result
- * into a general purpose register. Now *if* the compiler supports
- * inline assembler, then it's not impossible to implement the
- * "bignum" routines (and have the compiler optimize 'em)
- * exhibiting "native" performance in C. That's what BN_UMULT_HIGH
- * macro is about:-)
- *
- * <appro@fy.chalmers.se>
+ * If the compiler doesn't support 2*N integer type, then you have to
+ * replace every N*N multiplication with 4 (N/2)*(N/2) accompanied by some
+ * shifts and additions which unavoidably results in severe performance
+ * penalties. Of course provided that the hardware is capable of producing
+ * 2*N result... That's when you normally start considering assembler
+ * implementation. However! It should be pointed out that some CPUs (e.g.,
+ * PowerPC, Alpha, and IA-64) provide *separate* instruction calculating
+ * the upper half of the product placing the result into a general
+ * purpose register. Now *if* the compiler supports inline assembler,
+ * then it's not impossible to implement the "bignum" routines (and have
+ * the compiler optimize 'em) exhibiting "native" performance in C. That's
+ * what BN_UMULT_HIGH macro is about:-) Note that more recent compilers do
+ * support 2*64 integer type, which is also used here.
*/
-# if defined(__alpha) && (defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT))
+# if defined(__SIZEOF_INT128__) && __SIZEOF_INT128__==16 && \
+ (defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG))
+# define BN_UMULT_HIGH(a,b) (((__uint128_t)(a)*(b))>>64)
+# define BN_UMULT_LOHI(low,high,a,b) ({ \
+ __uint128_t ret=(__uint128_t)(a)*(b); \
+ (high)=ret>>64; (low)=ret; })
+# elif defined(__alpha) && (defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT))
# if defined(__DECC)
# include <c_asm.h>
# define BN_UMULT_HIGH(a,b) (BN_ULONG)asm("umulh %a0,%a1,%v0",(a),(b))
# elif defined(__GNUC__) && __GNUC__>=2
-# define BN_UMULT_HIGH(a,b) ({ \
+# define BN_UMULT_HIGH(a,b) ({ \
register BN_ULONG ret; \
asm ("umulh %1,%2,%0" \
: "=r"(ret) \
: "r"(a), "r"(b)); \
- ret; })
+ ret; })
# endif /* compiler */
-# elif defined(_ARCH_PPC) && defined(__64BIT__) && defined(SIXTY_FOUR_BIT_LONG)
+# elif defined(_ARCH_PPC64) && defined(SIXTY_FOUR_BIT_LONG)
# if defined(__GNUC__) && __GNUC__>=2
-# define BN_UMULT_HIGH(a,b) ({ \
+# define BN_UMULT_HIGH(a,b) ({ \
register BN_ULONG ret; \
asm ("mulhdu %0,%1,%2" \
: "=r"(ret) \
: "r"(a), "r"(b)); \
- ret; })
+ ret; })
# endif /* compiler */
# elif (defined(__x86_64) || defined(__x86_64__)) && \
(defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT))
# if defined(__GNUC__) && __GNUC__>=2
-# define BN_UMULT_HIGH(a,b) ({ \
+# define BN_UMULT_HIGH(a,b) ({ \
register BN_ULONG ret,discard; \
asm ("mulq %3" \
: "=a"(discard),"=d"(ret) \
: "a"(a), "g"(b) \
: "cc"); \
- ret; })
-# define BN_UMULT_LOHI(low,high,a,b) \
+ ret; })
+# define BN_UMULT_LOHI(low,high,a,b) \
asm ("mulq %3" \
: "=a"(low),"=d"(high) \
: "a"(a),"g"(b) \
# endif
# elif defined(__mips) && (defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG))
# if defined(__GNUC__) && __GNUC__>=2
-# if __GNUC__>4 || (__GNUC__>=4 && __GNUC_MINOR__>=4)
- /* "h" constraint is no more since 4.4 */
-# define BN_UMULT_HIGH(a,b) (((__uint128_t)(a)*(b))>>64)
-# define BN_UMULT_LOHI(low,high,a,b) ({ \
- __uint128_t ret=(__uint128_t)(a)*(b); \
- (high)=ret>>64; (low)=ret; })
-# else
-# define BN_UMULT_HIGH(a,b) ({ \
+# define BN_UMULT_HIGH(a,b) ({ \
register BN_ULONG ret; \
asm ("dmultu %1,%2" \
: "=h"(ret) \
: "r"(a), "r"(b) : "l"); \
ret; })
-# define BN_UMULT_LOHI(low,high,a,b)\
+# define BN_UMULT_LOHI(low,high,a,b) \
asm ("dmultu %2,%3" \
: "=l"(low),"=h"(high) \
: "r"(a), "r"(b));
-# endif
# endif
# elif defined(__aarch64__) && defined(SIXTY_FOUR_BIT_LONG)
# if defined(__GNUC__) && __GNUC__>=2
-# define BN_UMULT_HIGH(a,b) ({ \
+# define BN_UMULT_HIGH(a,b) ({ \
register BN_ULONG ret; \
asm ("umulh %0,%1,%2" \
: "=r"(ret) \
: "r"(a), "r"(b)); \
- ret; })
+ ret; })
# endif
# endif /* cpu */
# endif /* OPENSSL_NO_ASM */
-/*************************************************************
- * Using the long long type
- */
-# define Lw(t) (((BN_ULONG)(t))&BN_MASK2)
-# define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2)
-
# ifdef BN_DEBUG_RAND
# define bn_clear_top2max(a) \
{ \
# endif
# ifdef BN_LLONG
+/*******************************************************************
+ * Using the long long type, has to be twice as wide as BN_ULONG...
+ */
+# define Lw(t) (((BN_ULONG)(t))&BN_MASK2)
+# define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2)
+
# define mul_add(r,a,w,c) { \
BN_ULLONG t; \
t=(BN_ULLONG)w * (a) + (r) + (c); \
void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
BN_ULONG *t);
-void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
- BN_ULONG *t);
-BN_ULONG bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
- int cl, int dl);
BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
int cl, int dl);
int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,
int *noinv);
-int bn_probable_prime_dh(BIGNUM *rnd, int bits,
- const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
-int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx);
-int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx);
-
static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits)
{
if (bits > (INT_MAX - BN_BITS2 + 1))
return bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2);
}
-#ifdef __cplusplus
-}
-#endif
-
#endif