diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h
index 11fcbde4..3ef4a205 100644
--- a/mpi/mpi-internal.h
+++ b/mpi/mpi-internal.h
@@ -1,305 +1,305 @@
/* mpi-internal.h - Internal to the Multi Precision Integers
* Copyright (C) 1994, 1996, 1998, 2000, 2002,
* 2003 Free Software Foundation, Inc.
*
* This file is part of Libgcrypt.
*
* Libgcrypt is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* Libgcrypt is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
*
* Note: This code is heavily based on the GNU MP Library.
* Actually it's the same code with only minor changes in the
* way the data is stored; this is to support the abstraction
* of an optional secure memory allocation which may be used
* to avoid revealing of sensitive data due to paging etc.
*/
#ifndef G10_MPI_INTERNAL_H
#define G10_MPI_INTERNAL_H
#include "mpi-asm-defs.h"
#ifndef BITS_PER_MPI_LIMB
#if BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_INT
typedef unsigned int mpi_limb_t;
typedef signed int mpi_limb_signed_t;
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG
typedef unsigned long int mpi_limb_t;
typedef signed long int mpi_limb_signed_t;
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG_LONG
typedef unsigned long long int mpi_limb_t;
typedef signed long long int mpi_limb_signed_t;
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_SHORT
typedef unsigned short int mpi_limb_t;
typedef signed short int mpi_limb_signed_t;
#else
#error BYTES_PER_MPI_LIMB does not match any C type
#endif
#define BITS_PER_MPI_LIMB (8*BYTES_PER_MPI_LIMB)
#endif /*BITS_PER_MPI_LIMB*/
#include "mpi.h"
/* If KARATSUBA_THRESHOLD is not already defined, define it to a
* value which is good on most machines. */
/* tested 4, 16, 32 and 64, where 16 gave the best performance when
* checking a 768 and a 1024 bit ElGamal signature.
* (wk 22.12.97) */
#ifndef KARATSUBA_THRESHOLD
#define KARATSUBA_THRESHOLD 16
#endif
/* The code can't handle KARATSUBA_THRESHOLD smaller than 2. */
#if KARATSUBA_THRESHOLD < 2
#undef KARATSUBA_THRESHOLD
#define KARATSUBA_THRESHOLD 2
#endif
typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */
typedef int mpi_size_t; /* (must be a signed type) */
#define ABS(x) (x >= 0 ? x : -x)
#define MIN(l,o) ((l) < (o) ? (l) : (o))
#define MAX(h,i) ((h) > (i) ? (h) : (i))
#define RESIZE_IF_NEEDED(a,b) \
do { \
if( (a)->alloced < (b) ) \
mpi_resize((a), (b)); \
} while(0)
#define RESIZE_AND_CLEAR_IF_NEEDED(a,b) \
do { \
if( (a)->nlimbs < (b) ) \
mpi_resize((a), (b)); \
} while(0)
/* Copy N limbs from S to D. */
#define MPN_COPY( d, s, n) \
do { \
mpi_size_t _i; \
for( _i = 0; _i < (n); _i++ ) \
(d)[_i] = (s)[_i]; \
} while(0)
#define MPN_COPY_INCR( d, s, n) \
do { \
mpi_size_t _i; \
for( _i = 0; _i < (n); _i++ ) \
(d)[_i] = (s)[_i]; \
} while (0)
#define MPN_COPY_DECR( d, s, n ) \
do { \
mpi_size_t _i; \
for( _i = (n)-1; _i >= 0; _i--) \
(d)[_i] = (s)[_i]; \
} while(0)
/* Zero N limbs at D */
#define MPN_ZERO(d, n) \
do { \
int _i; \
for( _i = 0; _i < (n); _i++ ) \
(d)[_i] = 0; \
} while (0)
#define MPN_NORMALIZE(d, n) \
do { \
while( (n) > 0 ) { \
if( (d)[(n)-1] ) \
break; \
(n)--; \
} \
} while(0)
#define MPN_NORMALIZE_NOT_ZERO(d, n) \
do { \
for(;;) { \
if( (d)[(n)-1] ) \
break; \
(n)--; \
} \
} while(0)
#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
do { \
if( (size) < KARATSUBA_THRESHOLD ) \
mul_n_basecase (prodp, up, vp, size); \
else \
mul_n (prodp, up, vp, size, tspace); \
- } while (0);
+ } while (0)
/* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
* limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
* If this would yield overflow, DI should be the largest possible number
* (i.e., only ones). For correct operation, the most significant bit of D
* has to be set. Put the quotient in Q and the remainder in R.
*/
#define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \
do { \
mpi_limb_t _ql GCC_ATTR_UNUSED; \
mpi_limb_t _q, _r; \
mpi_limb_t _xh, _xl; \
umul_ppmm (_q, _ql, (nh), (di)); \
_q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */ \
umul_ppmm (_xh, _xl, _q, (d)); \
sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl); \
if( _xh ) { \
sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \
_q++; \
if( _xh) { \
sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \
_q++; \
} \
} \
if( _r >= (d) ) { \
_r -= (d); \
_q++; \
} \
(r) = _r; \
(q) = _q; \
} while (0)
/*-- mpiutil.c --*/
#define mpi_alloc_limb_space(n,f) _gcry_mpi_alloc_limb_space((n),(f))
mpi_ptr_t _gcry_mpi_alloc_limb_space( unsigned nlimbs, int sec );
void _gcry_mpi_free_limb_space( mpi_ptr_t a, unsigned int nlimbs );
void _gcry_mpi_assign_limb_space( gcry_mpi_t a, mpi_ptr_t ap, unsigned nlimbs );
/*-- mpi-bit.c --*/
#define mpi_rshift_limbs(a,n) _gcry_mpi_rshift_limbs ((a), (n))
#define mpi_lshift_limbs(a,n) _gcry_mpi_lshift_limbs ((a), (n))
void _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count );
void _gcry_mpi_lshift_limbs( gcry_mpi_t a, unsigned int count );
/*-- mpih-add.c --*/
mpi_limb_t _gcry_mpih_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb );
mpi_limb_t _gcry_mpih_add_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_ptr_t s2_ptr, mpi_size_t size);
mpi_limb_t _gcry_mpih_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
mpi_ptr_t s2_ptr, mpi_size_t s2_size);
/*-- mpih-sub.c --*/
mpi_limb_t _gcry_mpih_sub_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb );
mpi_limb_t _gcry_mpih_sub_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_ptr_t s2_ptr, mpi_size_t size);
mpi_limb_t _gcry_mpih_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
mpi_ptr_t s2_ptr, mpi_size_t s2_size);
/*-- mpih-cmp.c --*/
int _gcry_mpih_cmp( mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size );
/*-- mpih-mul.c --*/
struct karatsuba_ctx {
struct karatsuba_ctx *next;
mpi_ptr_t tspace;
unsigned int tspace_nlimbs;
mpi_size_t tspace_size;
mpi_ptr_t tp;
unsigned int tp_nlimbs;
mpi_size_t tp_size;
};
void _gcry_mpih_release_karatsuba_ctx( struct karatsuba_ctx *ctx );
mpi_limb_t _gcry_mpih_addmul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb);
mpi_limb_t _gcry_mpih_submul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb);
void _gcry_mpih_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
mpi_size_t size);
mpi_limb_t _gcry_mpih_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
mpi_ptr_t vp, mpi_size_t vsize);
void _gcry_mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size );
void _gcry_mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size,
mpi_ptr_t tspace);
void _gcry_mpih_mul_karatsuba_case( mpi_ptr_t prodp,
mpi_ptr_t up, mpi_size_t usize,
mpi_ptr_t vp, mpi_size_t vsize,
struct karatsuba_ctx *ctx );
/*-- mpih-mul_1.c (or xxx/cpu/ *.S) --*/
mpi_limb_t _gcry_mpih_mul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb);
/*-- mpih-div.c --*/
mpi_limb_t _gcry_mpih_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
mpi_limb_t divisor_limb);
mpi_limb_t _gcry_mpih_divrem( mpi_ptr_t qp, mpi_size_t qextra_limbs,
mpi_ptr_t np, mpi_size_t nsize,
mpi_ptr_t dp, mpi_size_t dsize);
mpi_limb_t _gcry_mpih_divmod_1( mpi_ptr_t quot_ptr,
mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
mpi_limb_t divisor_limb);
/*-- mpih-shift.c --*/
mpi_limb_t _gcry_mpih_lshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
unsigned cnt);
mpi_limb_t _gcry_mpih_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
unsigned cnt);
/*-- mpih-const-time.c --*/
#define mpih_set_cond(w,u,s,o) _gcry_mpih_set_cond ((w),(u),(s),(o))
#define mpih_add_n_cond(w,u,v,s,o) _gcry_mpih_add_n_cond ((w),(u),(v),(s),(o))
#define mpih_sub_n_cond(w,u,v,s,o) _gcry_mpih_sub_n_cond ((w),(u),(v),(s),(o))
#define mpih_swap_cond(u,v,s,o) _gcry_mpih_swap_cond ((u),(v),(s),(o))
#define mpih_abs_cond(w,u,s,o) _gcry_mpih_abs_cond ((w),(u),(s),(o))
#define mpih_mod(v,vs,u,us) _gcry_mpih_mod ((v),(vs),(u),(us))
void _gcry_mpih_set_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
unsigned long op_enable);
mpi_limb_t _gcry_mpih_add_n_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_ptr_t vp,
mpi_size_t usize, unsigned long op_enable);
mpi_limb_t _gcry_mpih_sub_n_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_ptr_t vp,
mpi_size_t usize, unsigned long op_enable);
void _gcry_mpih_swap_cond (mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t usize,
unsigned long op_enable);
void _gcry_mpih_abs_cond (mpi_ptr_t wp, mpi_ptr_t up,
mpi_size_t usize, unsigned long op_enable);
mpi_ptr_t _gcry_mpih_mod (mpi_ptr_t vp, mpi_size_t vsize,
mpi_ptr_t up, mpi_size_t usize);
int _gcry_mpih_cmp_ui (mpi_ptr_t up, mpi_size_t usize, unsigned long v);
/* Define stuff for longlong.h. */
#define W_TYPE_SIZE BITS_PER_MPI_LIMB
typedef mpi_limb_t UWtype;
typedef unsigned int UHWtype;
#if defined (__GNUC__)
typedef unsigned int UQItype __attribute__ ((mode (QI)));
typedef int SItype __attribute__ ((mode (SI)));
typedef unsigned int USItype __attribute__ ((mode (SI)));
typedef int DItype __attribute__ ((mode (DI)));
typedef unsigned int UDItype __attribute__ ((mode (DI)));
#else
typedef unsigned char UQItype;
typedef long SItype;
typedef unsigned long USItype;
#endif
#ifdef __GNUC__
#include "mpi-inline.h"
#endif
#endif /*G10_MPI_INTERNAL_H*/
diff --git a/mpi/mpi-pow.c b/mpi/mpi-pow.c
index 62b4a808..defd675e 100644
--- a/mpi/mpi-pow.c
+++ b/mpi/mpi-pow.c
@@ -1,772 +1,772 @@
/* mpi-pow.c - MPI functions for exponentiation
* Copyright (C) 1994, 1996, 1998, 2000, 2002
* 2003 Free Software Foundation, Inc.
* 2013 g10 Code GmbH
*
* This file is part of Libgcrypt.
*
* Libgcrypt is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* Libgcrypt is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this program; if not, see .
*
* Note: This code is heavily based on the GNU MP Library.
* Actually it's the same code with only minor changes in the
* way the data is stored; this is to support the abstraction
* of an optional secure memory allocation which may be used
* to avoid revealing of sensitive data due to paging etc.
*/
#include
#include
#include
#include
#include "mpi-internal.h"
#include "longlong.h"
/*
* When you need old implementation, please add compilation option
* -DUSE_ALGORITHM_SIMPLE_EXPONENTIATION
* or expose this line:
#define USE_ALGORITHM_SIMPLE_EXPONENTIATION 1
*/
#if defined(USE_ALGORITHM_SIMPLE_EXPONENTIATION)
/****************
* RES = BASE ^ EXPO mod MOD
*/
void
_gcry_mpi_powm (gcry_mpi_t res,
gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod)
{
/* Pointer to the limbs of the arguments, their size and signs. */
mpi_ptr_t rp, ep, mp, bp;
mpi_size_t esize, msize, bsize, rsize;
int msign, bsign, rsign;
/* Flags telling the secure allocation status of the arguments. */
int esec, msec, bsec;
/* Size of the result including space for temporary values. */
mpi_size_t size;
/* Helper. */
int mod_shift_cnt;
int negative_result;
mpi_ptr_t mp_marker = NULL;
mpi_ptr_t bp_marker = NULL;
mpi_ptr_t ep_marker = NULL;
mpi_ptr_t xp_marker = NULL;
unsigned int mp_nlimbs = 0;
unsigned int bp_nlimbs = 0;
unsigned int ep_nlimbs = 0;
unsigned int xp_nlimbs = 0;
mpi_ptr_t tspace = NULL;
mpi_size_t tsize = 0;
esize = expo->nlimbs;
msize = mod->nlimbs;
size = 2 * msize;
msign = mod->sign;
esec = mpi_is_secure(expo);
msec = mpi_is_secure(mod);
bsec = mpi_is_secure(base);
rp = res->d;
ep = expo->d;
MPN_NORMALIZE(ep, esize);
if (!msize)
_gcry_divide_by_zero();
if (!esize)
{
/* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 depending
on if MOD equals 1. */
res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
if (res->nlimbs)
{
RESIZE_IF_NEEDED (res, 1);
rp = res->d;
rp[0] = 1;
}
res->sign = 0;
goto leave;
}
/* Normalize MOD (i.e. make its most significant bit set) as
required by mpn_divrem. This will make the intermediate values
in the calculation slightly larger, but the correct result is
obtained after a final reduction using the original MOD value. */
mp_nlimbs = msec? msize:0;
mp = mp_marker = mpi_alloc_limb_space(msize, msec);
count_leading_zeros (mod_shift_cnt, mod->d[msize-1]);
if (mod_shift_cnt)
_gcry_mpih_lshift (mp, mod->d, msize, mod_shift_cnt);
else
MPN_COPY( mp, mod->d, msize );
bsize = base->nlimbs;
bsign = base->sign;
if (bsize > msize)
{
/* The base is larger than the module. Reduce it.
Allocate (BSIZE + 1) with space for remainder and quotient.
(The quotient is (bsize - msize + 1) limbs.) */
bp_nlimbs = bsec ? (bsize + 1):0;
bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec );
MPN_COPY ( bp, base->d, bsize );
/* We don't care about the quotient, store it above the
* remainder, at BP + MSIZE. */
_gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize );
bsize = msize;
/* Canonicalize the base, since we are going to multiply with it
quite a few times. */
MPN_NORMALIZE( bp, bsize );
}
else
bp = base->d;
if (!bsize)
{
res->nlimbs = 0;
res->sign = 0;
goto leave;
}
/* Make BASE, EXPO and MOD not overlap with RES. */
if ( rp == bp )
{
/* RES and BASE are identical. Allocate temp. space for BASE. */
gcry_assert (!bp_marker);
bp_nlimbs = bsec? bsize:0;
bp = bp_marker = mpi_alloc_limb_space( bsize, bsec );
MPN_COPY(bp, rp, bsize);
}
if ( rp == ep )
{
/* RES and EXPO are identical. Allocate temp. space for EXPO. */
ep_nlimbs = esec? esize:0;
ep = ep_marker = mpi_alloc_limb_space( esize, esec );
MPN_COPY(ep, rp, esize);
}
if ( rp == mp )
{
/* RES and MOD are identical. Allocate temporary space for MOD.*/
gcry_assert (!mp_marker);
mp_nlimbs = msec?msize:0;
mp = mp_marker = mpi_alloc_limb_space( msize, msec );
MPN_COPY(mp, rp, msize);
}
/* Copy base to the result. */
if (res->alloced < size)
{
mpi_resize (res, size);
rp = res->d;
}
MPN_COPY ( rp, bp, bsize );
rsize = bsize;
rsign = 0;
/* Main processing. */
{
mpi_size_t i;
mpi_ptr_t xp;
int c;
mpi_limb_t e;
mpi_limb_t carry_limb;
struct karatsuba_ctx karactx;
struct gcry_mpi w, u;
xp_nlimbs = msec? size:0;
xp = xp_marker = mpi_alloc_limb_space( size, msec );
w.sign = u.sign = 0;
w.flags = u.flags = 0;
w.alloced = w.nlimbs = size; /* RES->alloc may be longer. */
u.alloced = u.nlimbs = size;
memset( &karactx, 0, sizeof karactx );
negative_result = (ep[0] & 1) && bsign;
i = esize - 1;
e = ep[i];
count_leading_zeros (c, e);
e = (e << c) << 1; /* Shift the expo bits to the left, lose msb. */
c = BITS_PER_MPI_LIMB - 1 - c;
/* Main loop.
Make the result be pointed to alternately by XP and RP. This
helps us avoid block copying, which would otherwise be
necessary with the overlap restrictions of
_gcry_mpih_divmod. With 50% probability the result after this
loop will be in the area originally pointed by RP (==RES->d),
and with 50% probability in the area originally pointed to by XP. */
for (;;)
{
while (c)
{
mpi_ptr_t tp;
mpi_size_t xsize;
/*mpih_mul_n(xp, rp, rp, rsize);*/
if ( rsize < KARATSUBA_THRESHOLD )
_gcry_mpih_sqr_n_basecase( xp, rp, rsize );
else
{
if ( !tspace )
{
tsize = 2 * rsize;
tspace = mpi_alloc_limb_space( tsize, 0 );
}
else if ( tsize < (2*rsize) )
{
_gcry_mpi_free_limb_space (tspace, 0);
tsize = 2 * rsize;
tspace = mpi_alloc_limb_space (tsize, 0 );
}
_gcry_mpih_sqr_n (xp, rp, rsize, tspace);
}
xsize = 2 * rsize;
if ( xsize > msize )
{
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
xsize = msize;
}
tp = rp; rp = xp; xp = tp;
rsize = xsize;
/* To mitigate the Yarom/Falkner flush+reload cache
* side-channel attack on the RSA secret exponent, we do
* the multiplication regardless of the value of the
* high-bit of E. But to avoid this performance penalty
* we do it only if the exponent has been stored in secure
* memory and we can thus assume it is a secret exponent. */
if (esec || (mpi_limb_signed_t)e < 0)
{
/*mpih_mul( xp, rp, rsize, bp, bsize );*/
if( bsize < KARATSUBA_THRESHOLD )
_gcry_mpih_mul ( xp, rp, rsize, bp, bsize );
else
_gcry_mpih_mul_karatsuba_case (xp, rp, rsize, bp, bsize,
&karactx);
xsize = rsize + bsize;
if ( xsize > msize )
{
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
xsize = msize;
}
}
w.d = rp;
u.d = xp;
mpi_set_cond (&w, &u, ((mpi_limb_signed_t)e < 0));
e <<= 1;
c--;
}
i--;
if ( i < 0 )
break;
e = ep[i];
c = BITS_PER_MPI_LIMB;
}
/* We shifted MOD, the modulo reduction argument, left
MOD_SHIFT_CNT steps. Adjust the result by reducing it with the
original MOD.
Also make sure the result is put in RES->d (where it already
might be, see above). */
if ( mod_shift_cnt )
{
carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt);
rp = res->d;
if ( carry_limb )
{
rp[rsize] = carry_limb;
rsize++;
}
}
else if (res->d != rp)
{
MPN_COPY (res->d, rp, rsize);
rp = res->d;
}
if ( rsize >= msize )
{
_gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize);
rsize = msize;
}
/* Remove any leading zero words from the result. */
if ( mod_shift_cnt )
_gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt);
MPN_NORMALIZE (rp, rsize);
_gcry_mpih_release_karatsuba_ctx (&karactx );
}
/* Fixup for negative results. */
if ( negative_result && rsize )
{
if ( mod_shift_cnt )
_gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt);
_gcry_mpih_sub( rp, mp, msize, rp, rsize);
rsize = msize;
rsign = msign;
MPN_NORMALIZE(rp, rsize);
}
gcry_assert (res->d == rp);
res->nlimbs = rsize;
res->sign = rsign;
leave:
if (mp_marker)
_gcry_mpi_free_limb_space( mp_marker, mp_nlimbs );
if (bp_marker)
_gcry_mpi_free_limb_space( bp_marker, bp_nlimbs );
if (ep_marker)
_gcry_mpi_free_limb_space( ep_marker, ep_nlimbs );
if (xp_marker)
_gcry_mpi_free_limb_space( xp_marker, xp_nlimbs );
if (tspace)
_gcry_mpi_free_limb_space( tspace, 0 );
}
#else
/**
* Internal function to compute
*
* X = R * S mod M
*
* and set the size of X at the pointer XSIZE_P.
* Use karatsuba structure at KARACTX_P.
*
* Condition:
* RSIZE >= SSIZE
* Enough space for X is allocated beforehand.
*
* For generic cases, we can/should use gcry_mpi_mulm.
* This function is use for specific internal case.
*/
static void
mul_mod (mpi_ptr_t xp, mpi_size_t *xsize_p,
mpi_ptr_t rp, mpi_size_t rsize,
mpi_ptr_t sp, mpi_size_t ssize,
mpi_ptr_t mp, mpi_size_t msize,
struct karatsuba_ctx *karactx_p)
{
if( ssize < KARATSUBA_THRESHOLD )
_gcry_mpih_mul ( xp, rp, rsize, sp, ssize );
else
_gcry_mpih_mul_karatsuba_case (xp, rp, rsize, sp, ssize, karactx_p);
if (rsize + ssize > msize)
{
_gcry_mpih_divrem (xp + msize, 0, xp, rsize + ssize, mp, msize);
*xsize_p = msize;
}
else
*xsize_p = rsize + ssize;
}
#define SIZE_PRECOMP ((1 << (5 - 1)))
/****************
* RES = BASE ^ EXPO mod MOD
*
* To mitigate the Yarom/Falkner flush+reload cache side-channel
* attack on the RSA secret exponent, we don't use the square
* routine but multiplication.
*
* Reference:
* Handbook of Applied Cryptography
* Algorithm 14.83: Modified left-to-right k-ary exponentiation
*/
void
_gcry_mpi_powm (gcry_mpi_t res,
gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod)
{
/* Pointer to the limbs of the arguments, their size and signs. */
mpi_ptr_t rp, ep, mp, bp;
mpi_size_t esize, msize, bsize, rsize;
int msign, bsign, rsign;
/* Flags telling the secure allocation status of the arguments. */
int esec, msec, bsec;
/* Size of the result including space for temporary values. */
mpi_size_t size;
/* Helper. */
int mod_shift_cnt;
int negative_result;
mpi_ptr_t mp_marker = NULL;
mpi_ptr_t bp_marker = NULL;
mpi_ptr_t ep_marker = NULL;
mpi_ptr_t xp_marker = NULL;
unsigned int mp_nlimbs = 0;
unsigned int bp_nlimbs = 0;
unsigned int ep_nlimbs = 0;
unsigned int xp_nlimbs = 0;
mpi_ptr_t precomp[SIZE_PRECOMP]; /* Pre-computed array: BASE^1, ^3, ^5, ... */
mpi_size_t precomp_size[SIZE_PRECOMP];
mpi_size_t W;
mpi_ptr_t base_u;
mpi_size_t base_u_size;
mpi_size_t max_u_size;
esize = expo->nlimbs;
msize = mod->nlimbs;
size = 2 * msize;
msign = mod->sign;
ep = expo->d;
MPN_NORMALIZE(ep, esize);
if (esize * BITS_PER_MPI_LIMB > 512)
W = 5;
else if (esize * BITS_PER_MPI_LIMB > 256)
W = 4;
else if (esize * BITS_PER_MPI_LIMB > 128)
W = 3;
else if (esize * BITS_PER_MPI_LIMB > 64)
W = 2;
else
W = 1;
esec = mpi_is_secure(expo);
msec = mpi_is_secure(mod);
bsec = mpi_is_secure(base);
rp = res->d;
if (!msize)
_gcry_divide_by_zero();
if (!esize)
{
/* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 depending
on if MOD equals 1. */
res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
if (res->nlimbs)
{
RESIZE_IF_NEEDED (res, 1);
rp = res->d;
rp[0] = 1;
}
res->sign = 0;
goto leave;
}
/* Normalize MOD (i.e. make its most significant bit set) as
required by mpn_divrem. This will make the intermediate values
in the calculation slightly larger, but the correct result is
obtained after a final reduction using the original MOD value. */
mp_nlimbs = msec? msize:0;
mp = mp_marker = mpi_alloc_limb_space(msize, msec);
count_leading_zeros (mod_shift_cnt, mod->d[msize-1]);
if (mod_shift_cnt)
_gcry_mpih_lshift (mp, mod->d, msize, mod_shift_cnt);
else
MPN_COPY( mp, mod->d, msize );
bsize = base->nlimbs;
bsign = base->sign;
if (bsize > msize)
{
/* The base is larger than the module. Reduce it.
Allocate (BSIZE + 1) with space for remainder and quotient.
(The quotient is (bsize - msize + 1) limbs.) */
bp_nlimbs = bsec ? (bsize + 1):0;
bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec );
MPN_COPY ( bp, base->d, bsize );
/* We don't care about the quotient, store it above the
* remainder, at BP + MSIZE. */
_gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize );
bsize = msize;
/* Canonicalize the base, since we are going to multiply with it
quite a few times. */
MPN_NORMALIZE( bp, bsize );
}
else
bp = base->d;
if (!bsize)
{
res->nlimbs = 0;
res->sign = 0;
goto leave;
}
/* Make BASE, EXPO not overlap with RES. We don't need to check MOD
because that has already been copied to the MP var. */
if ( rp == bp )
{
/* RES and BASE are identical. Allocate temp. space for BASE. */
gcry_assert (!bp_marker);
bp_nlimbs = bsec? bsize:0;
bp = bp_marker = mpi_alloc_limb_space( bsize, bsec );
MPN_COPY(bp, rp, bsize);
}
if ( rp == ep )
{
/* RES and EXPO are identical. Allocate temp. space for EXPO. */
ep_nlimbs = esec? esize:0;
ep = ep_marker = mpi_alloc_limb_space( esize, esec );
MPN_COPY(ep, rp, esize);
}
/* Copy base to the result. */
if (res->alloced < size)
{
mpi_resize (res, size);
rp = res->d;
}
/* Main processing. */
{
mpi_size_t i, j, k;
mpi_ptr_t xp;
- mpi_size_t xsize;
+ mpi_size_t xsize = 0;
int c;
mpi_limb_t e;
mpi_limb_t carry_limb;
struct karatsuba_ctx karactx;
mpi_ptr_t tp;
xp_nlimbs = msec? size:0;
xp = xp_marker = mpi_alloc_limb_space( size, msec );
memset( &karactx, 0, sizeof karactx );
negative_result = (ep[0] & 1) && bsign;
/* Precompute PRECOMP[], BASE^(2 * i + 1), BASE^1, ^3, ^5, ... */
if (W > 1) /* X := BASE^2 */
mul_mod (xp, &xsize, bp, bsize, bp, bsize, mp, msize, &karactx);
base_u = precomp[0] = mpi_alloc_limb_space (bsize, esec);
base_u_size = max_u_size = precomp_size[0] = bsize;
MPN_COPY (precomp[0], bp, bsize);
for (i = 1; i < (1 << (W - 1)); i++)
{ /* PRECOMP[i] = BASE^(2 * i + 1) */
if (xsize >= base_u_size)
mul_mod (rp, &rsize, xp, xsize, base_u, base_u_size,
mp, msize, &karactx);
else
mul_mod (rp, &rsize, base_u, base_u_size, xp, xsize,
mp, msize, &karactx);
base_u = precomp[i] = mpi_alloc_limb_space (rsize, esec);
base_u_size = precomp_size[i] = rsize;
if (max_u_size < base_u_size)
max_u_size = base_u_size;
MPN_COPY (precomp[i], rp, rsize);
}
if (msize > max_u_size)
max_u_size = msize;
base_u = mpi_alloc_limb_space (max_u_size, esec);
MPN_ZERO (base_u, max_u_size);
i = esize - 1;
/* Main loop.
Make the result be pointed to alternately by XP and RP. This
helps us avoid block copying, which would otherwise be
necessary with the overlap restrictions of
_gcry_mpih_divmod. With 50% probability the result after this
loop will be in the area originally pointed by RP (==RES->d),
and with 50% probability in the area originally pointed to by XP. */
rsign = 0;
if (W == 1)
{
rsize = bsize;
}
else
{
rsize = msize;
MPN_ZERO (rp, rsize);
}
MPN_COPY ( rp, bp, bsize );
e = ep[i];
count_leading_zeros (c, e);
e = (e << c) << 1;
c = BITS_PER_MPI_LIMB - 1 - c;
j = 0;
for (;;)
if (e == 0)
{
j += c;
if ( --i < 0 )
break;
e = ep[i];
c = BITS_PER_MPI_LIMB;
}
else
{
int c0;
mpi_limb_t e0;
struct gcry_mpi w, u;
w.sign = u.sign = 0;
w.flags = u.flags = 0;
w.d = base_u;
count_leading_zeros (c0, e);
e = (e << c0);
c -= c0;
j += c0;
e0 = (e >> (BITS_PER_MPI_LIMB - W));
if (c >= W)
c0 = 0;
else
{
if ( --i < 0 )
{
e0 = (e >> (BITS_PER_MPI_LIMB - c));
j += c - W;
goto last_step;
}
else
{
c0 = c;
e = ep[i];
c = BITS_PER_MPI_LIMB;
e0 |= (e >> (BITS_PER_MPI_LIMB - (W - c0)));
}
}
e = e << (W - c0);
c -= (W - c0);
last_step:
count_trailing_zeros (c0, e0);
e0 = (e0 >> c0) >> 1;
for (j += W - c0; j >= 0; j--)
{
/*
* base_u <= precomp[e0]
* base_u_size <= precomp_size[e0]
*/
base_u_size = 0;
for (k = 0; k < (1<< (W - 1)); k++)
{
w.alloced = w.nlimbs = precomp_size[k];
u.alloced = u.nlimbs = precomp_size[k];
u.d = precomp[k];
mpi_set_cond (&w, &u, k == e0);
base_u_size |= ( precomp_size[k] & (0UL - (k == e0)) );
}
w.alloced = w.nlimbs = rsize;
u.alloced = u.nlimbs = rsize;
u.d = rp;
mpi_set_cond (&w, &u, j != 0);
base_u_size ^= ((base_u_size ^ rsize) & (0UL - (j != 0)));
mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size,
mp, msize, &karactx);
tp = rp; rp = xp; xp = tp;
rsize = xsize;
}
j = c0;
if ( i < 0 )
break;
}
while (j--)
{
mul_mod (xp, &xsize, rp, rsize, rp, rsize, mp, msize, &karactx);
tp = rp; rp = xp; xp = tp;
rsize = xsize;
}
/* We shifted MOD, the modulo reduction argument, left
MOD_SHIFT_CNT steps. Adjust the result by reducing it with the
original MOD.
Also make sure the result is put in RES->d (where it already
might be, see above). */
if ( mod_shift_cnt )
{
carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt);
rp = res->d;
if ( carry_limb )
{
rp[rsize] = carry_limb;
rsize++;
}
}
else if (res->d != rp)
{
MPN_COPY (res->d, rp, rsize);
rp = res->d;
}
if ( rsize >= msize )
{
_gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize);
rsize = msize;
}
/* Remove any leading zero words from the result. */
if ( mod_shift_cnt )
_gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt);
MPN_NORMALIZE (rp, rsize);
_gcry_mpih_release_karatsuba_ctx (&karactx );
for (i = 0; i < (1 << (W - 1)); i++)
_gcry_mpi_free_limb_space( precomp[i], esec ? precomp_size[i] : 0 );
_gcry_mpi_free_limb_space (base_u, esec ? max_u_size : 0);
}
/* Fixup for negative results. */
if ( negative_result && rsize )
{
if ( mod_shift_cnt )
_gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt);
_gcry_mpih_sub( rp, mp, msize, rp, rsize);
rsize = msize;
rsign = msign;
MPN_NORMALIZE(rp, rsize);
}
gcry_assert (res->d == rp);
res->nlimbs = rsize;
res->sign = rsign;
leave:
if (mp_marker)
_gcry_mpi_free_limb_space( mp_marker, mp_nlimbs );
if (bp_marker)
_gcry_mpi_free_limb_space( bp_marker, bp_nlimbs );
if (ep_marker)
_gcry_mpi_free_limb_space( ep_marker, ep_nlimbs );
if (xp_marker)
_gcry_mpi_free_limb_space( xp_marker, xp_nlimbs );
}
#endif
diff --git a/mpi/mpih-mul.c b/mpi/mpih-mul.c
index 8b6f06a3..aa454cfe 100644
--- a/mpi/mpih-mul.c
+++ b/mpi/mpih-mul.c
@@ -1,529 +1,529 @@
/* mpih-mul.c - MPI helper functions
* Copyright (C) 1994, 1996, 1998, 1999, 2000,
* 2001, 2002 Free Software Foundation, Inc.
*
* This file is part of Libgcrypt.
*
* Libgcrypt is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* Libgcrypt is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
*
* Note: This code is heavily based on the GNU MP Library.
* Actually it's the same code with only minor changes in the
* way the data is stored; this is to support the abstraction
* of an optional secure memory allocation which may be used
* to avoid revealing of sensitive data due to paging etc.
*/
#include
#include
#include
#include
#include "mpi-internal.h"
#include "longlong.h"
#include "g10lib.h"
#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
do { \
if( (size) < KARATSUBA_THRESHOLD ) \
mul_n_basecase (prodp, up, vp, size); \
else \
mul_n (prodp, up, vp, size, tspace); \
- } while (0);
+ } while (0)
#define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
do { \
if ((size) < KARATSUBA_THRESHOLD) \
_gcry_mpih_sqr_n_basecase (prodp, up, size); \
else \
_gcry_mpih_sqr_n (prodp, up, size, tspace); \
- } while (0);
+ } while (0)
/* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP),
* both with SIZE limbs, and store the result at PRODP. 2 * SIZE limbs are
* always stored. Return the most significant limb.
*
* Argument constraints:
* 1. PRODP != UP and PRODP != VP, i.e. the destination
* must be distinct from the multiplier and the multiplicand.
*
*
* Handle simple cases with traditional multiplication.
*
* This is the most critical code of multiplication. All multiplies rely
* on this, both small and huge. Small ones arrive here immediately. Huge
* ones arrive here as this is the base case for Karatsuba's recursive
* algorithm below.
*/
static mpi_limb_t
mul_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up,
mpi_ptr_t vp, mpi_size_t size)
{
mpi_size_t i;
mpi_limb_t cy;
mpi_limb_t v_limb;
/* Multiply by the first limb in V separately, as the result can be
* stored (not added) to PROD. We also avoid a loop for zeroing. */
v_limb = vp[0];
if( v_limb <= 1 ) {
if( v_limb == 1 )
MPN_COPY( prodp, up, size );
else
MPN_ZERO( prodp, size );
cy = 0;
}
else
cy = _gcry_mpih_mul_1( prodp, up, size, v_limb );
prodp[size] = cy;
prodp++;
/* For each iteration in the outer loop, multiply one limb from
* U with one limb from V, and add it to PROD. */
for( i = 1; i < size; i++ ) {
v_limb = vp[i];
if( v_limb <= 1 ) {
cy = 0;
if( v_limb == 1 )
cy = _gcry_mpih_add_n(prodp, prodp, up, size);
}
else
cy = _gcry_mpih_addmul_1(prodp, up, size, v_limb);
prodp[size] = cy;
prodp++;
}
return cy;
}
static void
mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
mpi_size_t size, mpi_ptr_t tspace )
{
if( size & 1 ) {
/* The size is odd, and the code below doesn't handle that.
* Multiply the least significant (size - 1) limbs with a recursive
* call, and handle the most significant limb of S1 and S2
* separately.
* A slightly faster way to do this would be to make the Karatsuba
* code below behave as if the size were even, and let it check for
* odd size in the end. I.e., in essence move this code to the end.
* Doing so would save us a recursive call, and potentially make the
* stack grow a lot less.
*/
mpi_size_t esize = size - 1; /* even size */
mpi_limb_t cy_limb;
MPN_MUL_N_RECURSE( prodp, up, vp, esize, tspace );
cy_limb = _gcry_mpih_addmul_1( prodp + esize, up, esize, vp[esize] );
prodp[esize + esize] = cy_limb;
cy_limb = _gcry_mpih_addmul_1( prodp + esize, vp, size, up[esize] );
prodp[esize + size] = cy_limb;
}
else {
/* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm.
*
* Split U in two pieces, U1 and U0, such that
* U = U0 + U1*(B**n),
* and V in V1 and V0, such that
* V = V0 + V1*(B**n).
*
* UV is then computed recursively using the identity
*
* 2n n n n
* UV = (B + B )U V + B (U -U )(V -V ) + (B + 1)U V
* 1 1 1 0 0 1 0 0
*
* Where B = 2**BITS_PER_MP_LIMB.
*/
mpi_size_t hsize = size >> 1;
mpi_limb_t cy;
int negflg;
/* Product H. ________________ ________________
* |_____U1 x V1____||____U0 x V0_____|
* Put result in upper part of PROD and pass low part of TSPACE
* as new TSPACE.
*/
MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize, tspace);
/* Product M. ________________
* |_(U1-U0)(V0-V1)_|
*/
if( _gcry_mpih_cmp(up + hsize, up, hsize) >= 0 ) {
_gcry_mpih_sub_n(prodp, up + hsize, up, hsize);
negflg = 0;
}
else {
_gcry_mpih_sub_n(prodp, up, up + hsize, hsize);
negflg = 1;
}
if( _gcry_mpih_cmp(vp + hsize, vp, hsize) >= 0 ) {
_gcry_mpih_sub_n(prodp + hsize, vp + hsize, vp, hsize);
negflg ^= 1;
}
else {
_gcry_mpih_sub_n(prodp + hsize, vp, vp + hsize, hsize);
/* No change of NEGFLG. */
}
/* Read temporary operands from low part of PROD.
* Put result in low part of TSPACE using upper part of TSPACE
* as new TSPACE.
*/
MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize, tspace + size);
/* Add/copy product H. */
MPN_COPY (prodp + hsize, prodp + size, hsize);
cy = _gcry_mpih_add_n( prodp + size, prodp + size,
prodp + size + hsize, hsize);
/* Add product M (if NEGFLG M is a negative number) */
if(negflg)
cy -= _gcry_mpih_sub_n(prodp + hsize, prodp + hsize, tspace, size);
else
cy += _gcry_mpih_add_n(prodp + hsize, prodp + hsize, tspace, size);
/* Product L. ________________ ________________
* |________________||____U0 x V0_____|
* Read temporary operands from low part of PROD.
* Put result in low part of TSPACE using upper part of TSPACE
* as new TSPACE.
*/
MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size);
/* Add/copy Product L (twice) */
cy += _gcry_mpih_add_n(prodp + hsize, prodp + hsize, tspace, size);
if( cy )
_gcry_mpih_add_1(prodp + hsize + size, prodp + hsize + size, hsize, cy);
MPN_COPY(prodp, tspace, hsize);
cy = _gcry_mpih_add_n(prodp + hsize, prodp + hsize, tspace + hsize, hsize);
if( cy )
_gcry_mpih_add_1(prodp + size, prodp + size, size, 1);
}
}
void
_gcry_mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size )
{
mpi_size_t i;
mpi_limb_t cy_limb;
mpi_limb_t v_limb;
/* Multiply by the first limb in V separately, as the result can be
* stored (not added) to PROD. We also avoid a loop for zeroing. */
v_limb = up[0];
if( v_limb <= 1 ) {
if( v_limb == 1 )
MPN_COPY( prodp, up, size );
else
MPN_ZERO(prodp, size);
cy_limb = 0;
}
else
cy_limb = _gcry_mpih_mul_1( prodp, up, size, v_limb );
prodp[size] = cy_limb;
prodp++;
/* For each iteration in the outer loop, multiply one limb from
* U with one limb from V, and add it to PROD. */
for( i=1; i < size; i++) {
v_limb = up[i];
if( v_limb <= 1 ) {
cy_limb = 0;
if( v_limb == 1 )
cy_limb = _gcry_mpih_add_n(prodp, prodp, up, size);
}
else
cy_limb = _gcry_mpih_addmul_1(prodp, up, size, v_limb);
prodp[size] = cy_limb;
prodp++;
}
}
void
_gcry_mpih_sqr_n( mpi_ptr_t prodp,
mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
{
if( size & 1 ) {
/* The size is odd, and the code below doesn't handle that.
* Multiply the least significant (size - 1) limbs with a recursive
* call, and handle the most significant limb of S1 and S2
* separately.
* A slightly faster way to do this would be to make the Karatsuba
* code below behave as if the size were even, and let it check for
* odd size in the end. I.e., in essence move this code to the end.
* Doing so would save us a recursive call, and potentially make the
* stack grow a lot less.
*/
mpi_size_t esize = size - 1; /* even size */
mpi_limb_t cy_limb;
MPN_SQR_N_RECURSE( prodp, up, esize, tspace );
cy_limb = _gcry_mpih_addmul_1( prodp + esize, up, esize, up[esize] );
prodp[esize + esize] = cy_limb;
cy_limb = _gcry_mpih_addmul_1( prodp + esize, up, size, up[esize] );
prodp[esize + size] = cy_limb;
}
else {
mpi_size_t hsize = size >> 1;
mpi_limb_t cy;
/* Product H. ________________ ________________
* |_____U1 x U1____||____U0 x U0_____|
* Put result in upper part of PROD and pass low part of TSPACE
* as new TSPACE.
*/
MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace);
/* Product M. ________________
* |_(U1-U0)(U0-U1)_|
*/
if( _gcry_mpih_cmp( up + hsize, up, hsize) >= 0 )
_gcry_mpih_sub_n( prodp, up + hsize, up, hsize);
else
_gcry_mpih_sub_n (prodp, up, up + hsize, hsize);
/* Read temporary operands from low part of PROD.
* Put result in low part of TSPACE using upper part of TSPACE
* as new TSPACE. */
MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size);
/* Add/copy product H */
MPN_COPY(prodp + hsize, prodp + size, hsize);
cy = _gcry_mpih_add_n(prodp + size, prodp + size,
prodp + size + hsize, hsize);
/* Add product M (if NEGFLG M is a negative number). */
cy -= _gcry_mpih_sub_n (prodp + hsize, prodp + hsize, tspace, size);
/* Product L. ________________ ________________
* |________________||____U0 x U0_____|
* Read temporary operands from low part of PROD.
* Put result in low part of TSPACE using upper part of TSPACE
* as new TSPACE. */
MPN_SQR_N_RECURSE (tspace, up, hsize, tspace + size);
/* Add/copy Product L (twice). */
cy += _gcry_mpih_add_n (prodp + hsize, prodp + hsize, tspace, size);
if( cy )
_gcry_mpih_add_1(prodp + hsize + size, prodp + hsize + size,
hsize, cy);
MPN_COPY(prodp, tspace, hsize);
cy = _gcry_mpih_add_n (prodp + hsize, prodp + hsize, tspace + hsize, hsize);
if( cy )
_gcry_mpih_add_1 (prodp + size, prodp + size, size, 1);
}
}
/* This should be made into an inline function in gmp.h. */
void
_gcry_mpih_mul_n( mpi_ptr_t prodp,
mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
{
int secure;
if( up == vp ) {
if( size < KARATSUBA_THRESHOLD )
_gcry_mpih_sqr_n_basecase( prodp, up, size );
else {
mpi_ptr_t tspace;
secure = _gcry_is_secure( up );
tspace = mpi_alloc_limb_space( 2 * size, secure );
_gcry_mpih_sqr_n( prodp, up, size, tspace );
_gcry_mpi_free_limb_space (tspace, 2 * size );
}
}
else {
if( size < KARATSUBA_THRESHOLD )
mul_n_basecase( prodp, up, vp, size );
else {
mpi_ptr_t tspace;
secure = _gcry_is_secure( up ) || _gcry_is_secure( vp );
tspace = mpi_alloc_limb_space( 2 * size, secure );
mul_n (prodp, up, vp, size, tspace);
_gcry_mpi_free_limb_space (tspace, 2 * size );
}
}
}
void
_gcry_mpih_mul_karatsuba_case( mpi_ptr_t prodp,
mpi_ptr_t up, mpi_size_t usize,
mpi_ptr_t vp, mpi_size_t vsize,
struct karatsuba_ctx *ctx )
{
mpi_limb_t cy;
if( !ctx->tspace || ctx->tspace_size < vsize ) {
if( ctx->tspace )
_gcry_mpi_free_limb_space( ctx->tspace, ctx->tspace_nlimbs );
ctx->tspace_nlimbs = 2 * vsize;
ctx->tspace = mpi_alloc_limb_space (2 * vsize,
(_gcry_is_secure (up)
|| _gcry_is_secure (vp)));
ctx->tspace_size = vsize;
}
MPN_MUL_N_RECURSE( prodp, up, vp, vsize, ctx->tspace );
prodp += vsize;
up += vsize;
usize -= vsize;
if( usize >= vsize ) {
if( !ctx->tp || ctx->tp_size < vsize ) {
if( ctx->tp )
_gcry_mpi_free_limb_space( ctx->tp, ctx->tp_nlimbs );
ctx->tp_nlimbs = 2 * vsize;
ctx->tp = mpi_alloc_limb_space (2 * vsize,
(_gcry_is_secure (up)
|| _gcry_is_secure (vp)));
ctx->tp_size = vsize;
}
do {
MPN_MUL_N_RECURSE( ctx->tp, up, vp, vsize, ctx->tspace );
cy = _gcry_mpih_add_n( prodp, prodp, ctx->tp, vsize );
_gcry_mpih_add_1( prodp + vsize, ctx->tp + vsize, vsize, cy );
prodp += vsize;
up += vsize;
usize -= vsize;
} while( usize >= vsize );
}
if( usize ) {
if( usize < KARATSUBA_THRESHOLD ) {
_gcry_mpih_mul( ctx->tspace, vp, vsize, up, usize );
}
else {
if( !ctx->next ) {
ctx->next = xcalloc( 1, sizeof *ctx );
}
_gcry_mpih_mul_karatsuba_case( ctx->tspace,
vp, vsize,
up, usize,
ctx->next );
}
cy = _gcry_mpih_add_n( prodp, prodp, ctx->tspace, vsize);
_gcry_mpih_add_1( prodp + vsize, ctx->tspace + vsize, usize, cy );
}
}
void
_gcry_mpih_release_karatsuba_ctx( struct karatsuba_ctx *ctx )
{
struct karatsuba_ctx *ctx2;
if( ctx->tp )
_gcry_mpi_free_limb_space( ctx->tp, ctx->tp_nlimbs );
if( ctx->tspace )
_gcry_mpi_free_limb_space( ctx->tspace, ctx->tspace_nlimbs );
for( ctx=ctx->next; ctx; ctx = ctx2 ) {
ctx2 = ctx->next;
if( ctx->tp )
_gcry_mpi_free_limb_space( ctx->tp, ctx->tp_nlimbs );
if( ctx->tspace )
_gcry_mpi_free_limb_space( ctx->tspace, ctx->tspace_nlimbs );
xfree( ctx );
}
}
/* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
* and v (pointed to by VP, with VSIZE limbs), and store the result at
* PRODP. USIZE + VSIZE limbs are always stored, but if the input
* operands are normalized. Return the most significant limb of the
* result.
*
* NOTE: The space pointed to by PRODP is overwritten before finished
* with U and V, so overlap is an error.
*
* Argument constraints:
* 1. USIZE >= VSIZE.
* 2. PRODP != UP and PRODP != VP, i.e. the destination
* must be distinct from the multiplier and the multiplicand.
*/
mpi_limb_t
_gcry_mpih_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
mpi_ptr_t vp, mpi_size_t vsize)
{
mpi_ptr_t prod_endp = prodp + usize + vsize - 1;
mpi_limb_t cy;
struct karatsuba_ctx ctx;
if( vsize < KARATSUBA_THRESHOLD ) {
mpi_size_t i;
mpi_limb_t v_limb;
if( !vsize )
return 0;
/* Multiply by the first limb in V separately, as the result can be
* stored (not added) to PROD. We also avoid a loop for zeroing. */
v_limb = vp[0];
if( v_limb <= 1 ) {
if( v_limb == 1 )
MPN_COPY( prodp, up, usize );
else
MPN_ZERO( prodp, usize );
cy = 0;
}
else
cy = _gcry_mpih_mul_1( prodp, up, usize, v_limb );
prodp[usize] = cy;
prodp++;
/* For each iteration in the outer loop, multiply one limb from
* U with one limb from V, and add it to PROD. */
for( i = 1; i < vsize; i++ ) {
v_limb = vp[i];
if( v_limb <= 1 ) {
cy = 0;
if( v_limb == 1 )
cy = _gcry_mpih_add_n(prodp, prodp, up, usize);
}
else
cy = _gcry_mpih_addmul_1(prodp, up, usize, v_limb);
prodp[usize] = cy;
prodp++;
}
return cy;
}
memset( &ctx, 0, sizeof ctx );
_gcry_mpih_mul_karatsuba_case( prodp, up, usize, vp, vsize, &ctx );
_gcry_mpih_release_karatsuba_ctx( &ctx );
return *prod_endp;
}
diff --git a/src/cipher-proto.h b/src/cipher-proto.h
index 36729165..3cf6f74c 100644
--- a/src/cipher-proto.h
+++ b/src/cipher-proto.h
@@ -1,276 +1,273 @@
/* cipher-proto.h - Internal declarations
* Copyright (C) 2008, 2011 Free Software Foundation, Inc.
*
* This file is part of Libgcrypt.
*
* Libgcrypt is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser general Public License as
* published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* Libgcrypt is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this program; if not, see .
*/
/* This file has been factored out from cipher.h so that it can be
used standalone in visibility.c . */
#ifndef G10_CIPHER_PROTO_H
#define G10_CIPHER_PROTO_H
-enum pk_encoding;
-
-
/* Definition of a function used to report selftest failures.
DOMAIN is a string describing the function block:
"cipher", "digest", "pubkey or "random",
ALGO is the algorithm under test,
WHAT is a string describing what has been tested,
DESC is a string describing the error. */
typedef void (*selftest_report_func_t)(const char *domain,
int algo,
const char *what,
const char *errdesc);
/* Definition of the selftest functions. */
typedef gpg_err_code_t (*selftest_func_t)
(int algo, int extended, selftest_report_func_t report);
/*
*
* Public key related definitions.
*
*/
/* Type for the pk_generate function. */
typedef gcry_err_code_t (*gcry_pk_generate_t) (gcry_sexp_t genparms,
gcry_sexp_t *r_skey);
/* Type for the pk_check_secret_key function. */
typedef gcry_err_code_t (*gcry_pk_check_secret_key_t) (gcry_sexp_t keyparms);
/* Type for the pk_encrypt function. */
typedef gcry_err_code_t (*gcry_pk_encrypt_t) (gcry_sexp_t *r_ciph,
gcry_sexp_t s_data,
gcry_sexp_t keyparms);
/* Type for the pk_decrypt function. */
typedef gcry_err_code_t (*gcry_pk_decrypt_t) (gcry_sexp_t *r_plain,
gcry_sexp_t s_data,
gcry_sexp_t keyparms);
/* Type for the pk_sign function. */
typedef gcry_err_code_t (*gcry_pk_sign_t) (gcry_sexp_t *r_sig,
gcry_sexp_t s_data,
gcry_sexp_t keyparms);
/* Type for the pk_verify function. */
typedef gcry_err_code_t (*gcry_pk_verify_t) (gcry_sexp_t s_sig,
gcry_sexp_t s_data,
gcry_sexp_t keyparms);
/* Type for the pk_get_nbits function. */
typedef unsigned (*gcry_pk_get_nbits_t) (gcry_sexp_t keyparms);
/* The type used to compute the keygrip. */
typedef gpg_err_code_t (*pk_comp_keygrip_t) (gcry_md_hd_t md,
gcry_sexp_t keyparm);
/* The type used to query an ECC curve name. */
typedef const char *(*pk_get_curve_t)(gcry_sexp_t keyparms, int iterator,
unsigned int *r_nbits);
/* The type used to query ECC curve parameters by name. */
typedef gcry_sexp_t (*pk_get_curve_param_t)(const char *name);
/* Module specification structure for public key algorithms. */
typedef struct gcry_pk_spec
{
int algo;
struct {
unsigned int disabled:1;
unsigned int fips:1;
} flags;
int use;
const char *name;
const char **aliases;
const char *elements_pkey;
const char *elements_skey;
const char *elements_enc;
const char *elements_sig;
const char *elements_grip;
gcry_pk_generate_t generate;
gcry_pk_check_secret_key_t check_secret_key;
gcry_pk_encrypt_t encrypt;
gcry_pk_decrypt_t decrypt;
gcry_pk_sign_t sign;
gcry_pk_verify_t verify;
gcry_pk_get_nbits_t get_nbits;
selftest_func_t selftest;
pk_comp_keygrip_t comp_keygrip;
pk_get_curve_t get_curve;
pk_get_curve_param_t get_curve_param;
} gcry_pk_spec_t;
/*
*
* Symmetric cipher related definitions.
*
*/
struct cipher_bulk_ops;
/* Type for the cipher_setkey function. */
typedef gcry_err_code_t (*gcry_cipher_setkey_t) (void *c,
const unsigned char *key,
unsigned keylen,
struct cipher_bulk_ops *bulk_ops);
/* Type for the cipher_encrypt function. */
typedef unsigned int (*gcry_cipher_encrypt_t) (void *c,
unsigned char *outbuf,
const unsigned char *inbuf);
/* Type for the cipher_decrypt function. */
typedef unsigned int (*gcry_cipher_decrypt_t) (void *c,
unsigned char *outbuf,
const unsigned char *inbuf);
/* Type for the cipher_stencrypt function. */
typedef void (*gcry_cipher_stencrypt_t) (void *c,
unsigned char *outbuf,
const unsigned char *inbuf,
size_t n);
/* Type for the cipher_stdecrypt function. */
typedef void (*gcry_cipher_stdecrypt_t) (void *c,
unsigned char *outbuf,
const unsigned char *inbuf,
size_t n);
/* The type used to convey additional information to a cipher. */
typedef gpg_err_code_t (*cipher_set_extra_info_t)
(void *c, int what, const void *buffer, size_t buflen);
/* The type used to set an IV directly in the algorithm module. */
typedef void (*cipher_setiv_func_t)(void *c, const byte *iv, size_t ivlen);
/* A structure to map OIDs to encryption modes. */
typedef struct gcry_cipher_oid_spec
{
const char *oid;
int mode;
} gcry_cipher_oid_spec_t;
/* Module specification structure for ciphers. */
typedef struct gcry_cipher_spec
{
int algo;
struct {
unsigned int disabled:1;
unsigned int fips:1;
} flags;
const char *name;
const char **aliases;
const gcry_cipher_oid_spec_t *oids;
size_t blocksize;
size_t keylen;
size_t contextsize;
gcry_cipher_setkey_t setkey;
gcry_cipher_encrypt_t encrypt;
gcry_cipher_decrypt_t decrypt;
gcry_cipher_stencrypt_t stencrypt;
gcry_cipher_stdecrypt_t stdecrypt;
selftest_func_t selftest;
cipher_set_extra_info_t set_extra_info;
cipher_setiv_func_t setiv;
} gcry_cipher_spec_t;
/*
*
* Message digest related definitions.
*
*/
/* Type for the md_init function. */
typedef void (*gcry_md_init_t) (void *c, unsigned int flags);
/* Type for the md_write function. */
typedef void (*gcry_md_write_t) (void *c, const void *buf, size_t nbytes);
/* Type for the md_final function. */
typedef void (*gcry_md_final_t) (void *c);
/* Type for the md_read function. */
typedef unsigned char *(*gcry_md_read_t) (void *c);
/* Type for the md_extract function. */
typedef void (*gcry_md_extract_t) (void *c, void *outbuf, size_t nbytes);
/* Type for the md_hash_buffers function. */
typedef void (*gcry_md_hash_buffers_t) (void *outbuf, size_t nbytes,
const gcry_buffer_t *iov,
int iovcnt);
typedef struct gcry_md_oid_spec
{
const char *oidstring;
} gcry_md_oid_spec_t;
/* Module specification structure for message digests. */
typedef struct gcry_md_spec
{
int algo;
struct {
unsigned int disabled:1;
unsigned int fips:1;
} flags;
const char *name;
const unsigned char *asnoid;
int asnlen;
const gcry_md_oid_spec_t *oids;
int mdlen;
gcry_md_init_t init;
gcry_md_write_t write;
gcry_md_final_t final;
gcry_md_read_t read;
gcry_md_extract_t extract;
gcry_md_hash_buffers_t hash_buffers;
size_t contextsize; /* allocate this amount of context */
selftest_func_t selftest;
} gcry_md_spec_t;
/* The selftest functions. */
gcry_error_t _gcry_cipher_selftest (int algo, int extended,
selftest_report_func_t report);
gcry_error_t _gcry_md_selftest (int algo, int extended,
selftest_report_func_t report);
gcry_error_t _gcry_pk_selftest (int algo, int extended,
selftest_report_func_t report);
gcry_error_t _gcry_mac_selftest (int algo, int extended,
selftest_report_func_t report);
gcry_error_t _gcry_kdf_selftest (int algo, int extended,
selftest_report_func_t report);
gcry_error_t _gcry_random_selftest (selftest_report_func_t report);
#endif /*G10_CIPHER_PROTO_H*/