From d34decd2b2b88240cf4ca68a2a5feb7bf36de6e7 Mon Sep 17 00:00:00 2001 From: mdw Date: Sat, 17 Jun 2000 11:45:09 +0000 Subject: [PATCH] Major memory management overhaul. Added arena support. Use the secure arena for secret integers. Replace and improve the MP management macros (e.g., replace MP_MODIFY by MP_DEST). --- mp-arith.c | 87 ++++++++++----------- mp-const.c | 27 ++++--- mp-io.c | 11 ++- mp-mem.c | 237 +++++++++++++++++++++++++++++++++++++++++++++++++++++----- mp-misc.c | 25 ++----- mp.h | 200 +++++++++++++++++++++++++------------------------ mpbarrett.c | 22 ++++-- mpint.h | 9 ++- mpmont-mexp.c | 14 +++- mpmont.c | 27 ++++--- mprand.c | 19 +++-- 11 files changed, 454 insertions(+), 224 deletions(-) diff --git a/mp-arith.c b/mp-arith.c index f0502e1..fe6a45d 100644 --- a/mp-arith.c +++ b/mp-arith.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-arith.c,v 1.5 1999/12/22 15:54:41 mdw Exp $ + * $Id: mp-arith.c,v 1.6 2000/06/17 11:45:09 mdw Exp $ * * Basic arithmetic on multiprecision integers * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-arith.c,v $ + * Revision 1.6 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.5 1999/12/22 15:54:41 mdw * Adjust Karatsuba parameters. Calculate destination size better. * @@ -69,7 +74,7 @@ mp *mp_2c(mp *d, mp *a) if (!(a->f & MP_NEG)) return (MP_COPY(a)); - MP_MODIFY(d, MP_LEN(a)); + MP_DEST(d, MP_LEN(a), a->f); mpx_2c(d->v, d->vl, a->v, a->vl); d->f = a->f & MP_BURN; MP_SHRINK(d); @@ -90,7 +95,7 @@ mp *mp_sm(mp *d, mp *a) if (!MP_LEN(a) || a->vl[-1] < MPW_MAX / 2) return (MP_COPY(a)); - MP_MODIFY(d, MP_LEN(a)); + MP_DEST(d, MP_LEN(a), a->f); mpx_2c(d->v, d->vl, a->v, a->vl); d->f = (a->f & (MP_BURN | MP_NEG)) ^ MP_NEG; MP_SHRINK(d); @@ -108,7 +113,7 @@ mp *mp_sm(mp *d, mp *a) mp *mp_lsl(mp *d, mp *a, size_t n) { - MP_MODIFY(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS); + MP_DEST(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS, a->f); mpx_lsl(d->v, d->vl, a->v, a->vl, n); d->f = a->f & (MP_NEG | MP_BURN); MP_SHRINK(d); @@ -126,7 +131,7 @@ mp *mp_lsl(mp *d, mp *a, size_t n) mp *mp_lsr(mp *d, mp *a, size_t n) { - MP_MODIFY(d, MP_LEN(a)); + MP_DEST(d, MP_LEN(a), a->f); mpx_lsr(d->v, d->vl, a->v, a->vl, n); d->f = a->f & (MP_NEG | MP_BURN); MP_SHRINK(d); @@ -161,7 +166,7 @@ int mp_cmp(const mp *a, const mp *b) mp *mp_add(mp *d, mp *a, mp *b) { - MP_MODIFY(d, MAX(MP_LEN(a), MP_LEN(b)) + 1); + MP_DEST(d, MAX(MP_LEN(a), MP_LEN(b)) + 1, a->f | b->f); if (!((a->f ^ b->f) & MP_NEG)) mpx_uadd(d->v, d->vl, a->v, a->vl, b->v, b->vl); else { @@ -186,7 +191,7 @@ mp *mp_add(mp *d, mp *a, mp *b) mp *mp_sub(mp *d, mp *a, mp *b) { unsigned sgn = 0; - MP_MODIFY(d, MAX(MP_LEN(a), MP_LEN(b)) + 1); + MP_DEST(d, MAX(MP_LEN(a), MP_LEN(b)) + 1, a->f | b->f); if ((a->f ^ b->f) & MP_NEG) mpx_uadd(d->v, d->vl, a->v, a->vl, b->v, b->vl); else { @@ -215,16 +220,16 @@ mp *mp_mul(mp *d, mp *a, mp *b) b = MP_COPY(b); if (MP_LEN(a) <= KARATSUBA_CUTOFF || MP_LEN(b) <= KARATSUBA_CUTOFF) { - MP_MODIFY(d, MP_LEN(a) + MP_LEN(b)); + MP_DEST(d, MP_LEN(a) + MP_LEN(b), a->f | b->f | MP_UNDEF); mpx_umul(d->v, d->vl, a->v, a->vl, b->v, b->vl); } else { size_t m = 2 * MAX(MP_LEN(a), MP_LEN(b)) + 2; mpw *s; - MP_MODIFY(d, m); + MP_DEST(d, m, a->f | b->f | MP_UNDEF); m += KARATSUBA_SLOP; - s = MP_ALLOC(m); + s = mpalloc(d->a, m); mpx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + m); - MP_FREE(s); + mpfree(d->a, s); } d->f = ((a->f | b->f) & MP_BURN) | ((a->f ^ b->f) & MP_NEG); @@ -247,13 +252,13 @@ mp *mp_sqr(mp *d, mp *a) size_t m = MP_LEN(a); a = MP_COPY(a); - MP_MODIFY(d, 2 * m + 2); + MP_DEST(d, 2 * m + 2, a->f | MP_UNDEF); if (m > KARATSUBA_CUTOFF) { mpw *s; m = 2 * (m + 1) + KARATSUBA_SLOP; - s = MP_ALLOC(m); + s = mpalloc(d->a, m); mpx_ksqr(d->v, d->vl, a->v, a->vl, s, s + m); - MP_FREE(s); + mpfree(d->a, s); } else mpx_usqr(d->v, d->vl, a->v, a->vl); d->f = a->f & MP_BURN; @@ -287,41 +292,32 @@ void mp_div(mp **qq, mp **rr, mp *a, mp *b) mp *q = qq ? *qq : MP_NEW; mpw *sv, *svl; - /* --- Set up some temporary workspace --- */ - - { - size_t rq = MP_LEN(b) + 1; - sv = MP_ALLOC(rq); - svl = sv + rq; - } - /* --- Set the remainder up right --- * * * Just in case the divisor is larger, be able to cope with this. It's not * important in @mpx_udiv@, but it is here because of the sign correction. */ - { - size_t rq = MP_LEN(a) + 2; - if (MP_LEN(b) > rq) - rq = MP_LEN(b); - - b = MP_COPY(b); - if (r == a) { - MP_SPLIT(a); - a = r = MP_COPY(a); - MP_ENSURE(r, MP_LEN(r) + 2); - } else { - a = MP_COPY(a); - MP_MODIFY(r, MP_LEN(a) + 2); - memcpy(r->v, a->v, MPWS(MP_LEN(a))); - memset(r->v + MP_LEN(a), 0, MPWS(2)); - } - } + b = MP_COPY(b); + a = MP_COPY(a); + if (r) + MP_DROP(r); + r = a; + MP_DEST(r, MP_LEN(a) + 2, a->f | b->f); /* --- Fix up the quotient too --- */ - MP_MODIFY(q, MP_LEN(a)); + r = MP_COPY(r); + MP_DEST(q, MP_LEN(r), r->f | MP_UNDEF); + MP_DROP(r); + + /* --- Set up some temporary workspace --- */ + + { + size_t rq = MP_LEN(b) + 1; + sv = mpalloc(r->a, rq); + svl = sv + rq; + } /* --- Perform the calculation --- */ @@ -334,7 +330,7 @@ void mp_div(mp **qq, mp **rr, mp *a, mp *b) * remainder from @b@. */ - q->f = ((a->f | b->f) & MP_BURN) | ((a->f ^ b->f) & MP_NEG); + q->f = ((r->f | b->f) & MP_BURN) | ((r->f ^ b->f) & MP_NEG); if (q->f & MP_NEG) { mpw *v; for (v = r->v; v < r->vl; v++) { @@ -346,10 +342,13 @@ void mp_div(mp **qq, mp **rr, mp *a, mp *b) } } - r->f = ((a->f | b->f) & MP_BURN) | (b->f & MP_NEG); + r->f = ((r->f | b->f) & MP_BURN) | (b->f & MP_NEG); /* --- Store the return values --- */ + mpfree(r->a, sv); + MP_DROP(b); + if (!qq) MP_DROP(q); else { @@ -363,10 +362,6 @@ void mp_div(mp **qq, mp **rr, mp *a, mp *b) MP_SHRINK(r); *rr = r; } - - MP_DROP(a); - MP_DROP(b); - MP_FREE(sv); } /*----- Test rig ----------------------------------------------------------*/ diff --git a/mp-const.c b/mp-const.c index 2119470..f98da7c 100644 --- a/mp-const.c +++ b/mp-const.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-const.c,v 1.1 1999/11/17 18:02:16 mdw Exp $ + * $Id: mp-const.c,v 1.2 2000/06/17 11:45:09 mdw Exp $ * * Useful multiprecision constants * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-const.c,v $ + * Revision 1.2 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.1 1999/11/17 18:02:16 mdw * New multiprecision integer arithmetic suite. * @@ -41,17 +46,19 @@ /*----- Global variables --------------------------------------------------*/ -static mpw mpw_const[] = { 1, 2, 3, 4, 5, 10 }; +static mpw mpw_const[] = { 1, 2, 3, 4, 5, 10, 256 }; mp mp_const[] = { - { &mpw_const[0], &mpw_const[0], 0, MP_CONST, 0 }, - { &mpw_const[0], &mpw_const[0] + 1, 1, MP_CONST, 0 }, - { &mpw_const[1], &mpw_const[1] + 1, 1, MP_CONST, 0 }, - { &mpw_const[2], &mpw_const[2] + 1, 1, MP_CONST, 0 }, - { &mpw_const[3], &mpw_const[3] + 1, 1, MP_CONST, 0 }, - { &mpw_const[4], &mpw_const[4] + 1, 1, MP_CONST, 0 }, - { &mpw_const[5], &mpw_const[5] + 1, 1, MP_CONST, 0 }, - { &mpw_const[0], &mpw_const[0] + 1, 1, MP_CONST | MP_NEG, 0 }, + { &mpw_const[0], &mpw_const[0], 0, 0, MP_CONST, 0 }, + { &mpw_const[0], &mpw_const[0] + 1, 1, 0, MP_CONST, 0 }, + { &mpw_const[1], &mpw_const[1] + 1, 1, 0, MP_CONST, 0 }, + { &mpw_const[2], &mpw_const[2] + 1, 1, 0, MP_CONST, 0 }, + { &mpw_const[3], &mpw_const[3] + 1, 1, 0, MP_CONST, 0 }, + { &mpw_const[4], &mpw_const[4] + 1, 1, 0, MP_CONST, 0 }, + { &mpw_const[5], &mpw_const[5] + 1, 1, 0, MP_CONST, 0 }, + { &mpw_const[6], &mpw_const[6] + 1, 1, 0, MP_CONST, 0 }, + { &mpw_const[0], &mpw_const[0] + 1, 1, 0, MP_CONST | MP_NEG, 0 }, + { 0, mpw_const, 1, 0, MP_CONST | MP_BURN, 0 }, }; /*----- That's all, folks -------------------------------------------------*/ diff --git a/mp-io.c b/mp-io.c index 8e76917..c510649 100644 --- a/mp-io.c +++ b/mp-io.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-io.c,v 1.3 1999/11/21 22:13:02 mdw Exp $ + * $Id: mp-io.c,v 1.4 2000/06/17 11:45:09 mdw Exp $ * * Loading and storing of multiprecision integers * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-io.c,v $ + * Revision 1.4 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.3 1999/11/21 22:13:02 mdw * Add mp version of MPX_BITS. * @@ -97,7 +102,7 @@ unsigned long mp_bits(const mp *m) mp *mp_loadl(mp *d, const void *pv, size_t sz) { - MP_MODIFY(d, MPW_RQ(sz)); + MP_DEST(d, MPW_RQ(sz), MP_UNDEF); mpx_loadl(d->v, d->vl, pv, sz); d->f &= ~(MP_UNDEF | MP_NEG); mp_shrink(d); @@ -142,7 +147,7 @@ void mp_storel(const mp *m, void *pv, size_t sz) mp *mp_loadb(mp *d, const void *pv, size_t sz) { - MP_MODIFY(d, MPW_RQ(sz)); + MP_DEST(d, MPW_RQ(sz), MP_UNDEF); mpx_loadb(d->v, d->vl, pv, sz); d->f &= ~(MP_UNDEF | MP_NEG); mp_shrink(d); diff --git a/mp-mem.c b/mp-mem.c index 833874d..7f9d630 100644 --- a/mp-mem.c +++ b/mp-mem.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-mem.c,v 1.2 1999/12/10 23:19:02 mdw Exp $ + * $Id: mp-mem.c,v 1.3 2000/06/17 11:45:09 mdw Exp $ * * Memory management for multiprecision numbers * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-mem.c,v $ + * Revision 1.3 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.2 1999/12/10 23:19:02 mdw * Improve error-checking. * @@ -40,10 +45,37 @@ /*----- Header files ------------------------------------------------------*/ +#include + + #include "mp.h" /*----- Main code ---------------------------------------------------------*/ +/* --- @mp_new@ --- * + * + * Arguments: @size_t sz@ = size of vector required + * @unsigned f@ = flags to set + * + * Returns: Pointer to a new MP structure. + * + * Use: Allocates a new multiprecision integer. The data space is + * allocated from either the standard global or secret arena, + * depending on the initial flags requested. + */ + +mp *mp_new(size_t sz, unsigned f) +{ + mp *m = CREATE(mp); + m->a = (f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; + m->v = mpalloc(m->a, sz); + m->vl = m->v + sz; + m->sz = sz; + m->f = f & ~(MP_CONST | MP_DESTROYED); + m->ref = 1; + return (m); +} + /* --- @mp_create@ --- * * * Arguments: @size_t sz@ = size of vector required @@ -58,14 +90,40 @@ mp *mp_create(size_t sz) { mp *m = CREATE(mp); - m->v = MP_ALLOC(sz); + m->v = mpalloc(MPARENA_GLOBAL, sz); m->vl = m->v + sz; m->sz = sz; + m->a = MPARENA_GLOBAL; m->f = MP_UNDEF; m->ref = 1; return (m); } +/* --- @mp_createsecure@ --- * + * + * Arguments: @size_t sz@ = size of vector required + * + * Returns: Pointer to pristine new MP structure with enough memory + * bolted onto it. + * + * Use: Creates a new multiprecision integer with indeterminate + * contents. The integer has a single reference. The integer's + * data space is allocated from the secure arena. Its burn flag + * is set. + */ + +mp *mp_createsecure(size_t sz) +{ + mp *m = CREATE(mp); + m->v = mpalloc(MPARENA_SECURE, sz); + m->vl = m->v + sz; + m->sz = sz; + m->a = MPARENA_SECURE; + m->f = MP_UNDEF | MP_BURN; + m->ref = 1; + return (m); +} + /* --- @mp_build@ --- * * * Arguments: @mp *m@ = pointer to an MP block to fill in @@ -106,7 +164,7 @@ void mp_destroy(mp *m) assert(((void)"Attempted to destroy a constant", !(m->f & MP_CONST))); if (m->f & MP_BURN) memset(m->v, 0, MPWS(m->sz)); - MP_FREE(m->v); + mpfree(m->a, m->v); m->f |= MP_DESTROYED; DESTROY(m); } @@ -145,7 +203,19 @@ void mp_drop(mp *m) { MP_DROP(m); } * Use: Splits off a modifiable version of the integer referred to. */ -mp *mp_split(mp *m) { MP_SPLIT(m); return (m); } +mp *mp_split(mp *m) +{ +/* if ((m->f & MP_CONST) || m->ref > 1) { */ +/* size_t len = MP_LEN(m); */ +/* mp *mm = mp_new(len, m->f); */ +/* if (!(m->f & MP_UNDEF)) */ +/* memcpy(mm->v, m->v, MPWS(len)); */ +/* m->ref--; */ +/* m = mm; */ +/* } */ + MP_SPLIT(m); + return (m); +} /* --- @mp_resize@ --- * * @@ -154,38 +224,165 @@ mp *mp_split(mp *m) { MP_SPLIT(m); return (m); } * * Returns: --- * - * Use: Resizes the vector containing the integer's digits. The new - * size must be at least as large as the current integer's - * length. This isn't really intended for client use. + * Use: Changes an integer's size. The length and value are not + * changed. It is an error to */ -void mp_resize(mp *m, size_t sz) { MP_RESIZE(m, sz); } +void mp_resize(mp *m, size_t sz) +{ +/* mparena *a = (m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; */ +/* mpw *v; */ +/* size_t len = MP_LEN(m); */ +/* assert(((void)"can't make size less than length", sz >= len)); */ +/* v = mpalloc(a, sz); */ +/* if (!(m->f & MP_UNDEF)) */ +/* memcpy(v, m->v, MPWS(len)); */ +/* if (m->f & MP_BURN) */ +/* memset(m->v, 0, MPWS(m->sz)); */ +/* mpfree(m->a, m->v); */ +/* m->a = a; */ +/* m->v = v; */ +/* m->vl = v + len; */ +} /* --- @mp_ensure@ --- * * * Arguments: @mp *m@ = pointer to a multiprecision integer - * @size_t sz@ = required size + * @size_t sz@ = required length * * Returns: --- * - * Use: Ensures that the integer has enough space for @sz@ digits. - * The value is not changed. + * Use: Changes an integer's length. If there is not enough space + * allocated for the new length then the size is increased. It */ -void mp_ensure(mp *m, size_t sz) { MP_ENSURE(m, sz); } +void mp_ensure(mp *m, size_t sz) +{ +/* size_t len = MP_LEN(m); */ +/* if (sz >= len) { */ +/* if (sz > m->sz) */ +/* mp_resize(m, sz); */ +/* if (!(m->f & MP_UNDEF) && sz > len) */ +/* memset(m->vl, 0, MPWS(sz - len)); */ +/* m->vl = m->v + sz; */ +/* } */ +} -/* --- @mp_modify@ --- * +/* --- @mp_dest@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer - * @size_t sz@ = size required + * Arguments: @mp *m@ = a suggested destination integer + * @size_t sz@ = size required for result, in digits + * @unsigned f@ = various flags + * + * Returns: A pointer to an appropriate destination. + * + * Use: Converts a suggested destination into a real destination with + * the required properties. If the real destination is @d@, + * then the following properties will hold: * - * Returns: Pointer to the integer (possibly different). + * * @d@ will have exactly one reference. * - * Use: Prepares an integer to be overwritten. It's split off from - * other references to the same integer, and sufficient space is - * allocated. + * * If @m@ is not @MP_NEW@, then the contents of @m@ will not + * change, unless @f@ has the @MP_UNDEF@ flag set. + * + * * If @m@ is not @MP_NEW@, then he reference count of @m@ on + * entry is equal to the sum of the counts of @d@ and @m@ on + * exit. + * + * * The size of @d@ will be at least @sz@. + * + * * If @f@ has the @MP_BURN@ flag set, then @d@ will be + * allocated from @MPARENA_SECURE@. + * + * Understanding this function is crucial to using Catacomb's + * multiprecision integer library effectively. */ -mp *mp_modify(mp *m, size_t sz) { MP_MODIFY(m, sz); return (m); } +mp *mp_dest(mp *m, size_t sz, unsigned f) +{ + /* --- If no destination, make one --- */ + + if (m == MP_NEWSEC) + m = mp_new(sz, f | MP_UNDEF | MP_BURN); + else if (m == MP_NEW) + m = mp_new(sz, f | MP_UNDEF); + else { + size_t len = MP_LEN(m); + unsigned undef = (m->f | f) & MP_UNDEF; + + /* --- If the value must be preserved, the block can't shrink --- */ + + if (!undef && sz < len) + sz = len; + + /* --- Otherwise check whether the destination is suitable --- */ + + if (m->ref > 1 || (m->f & MP_CONST) || + m->sz > len || !((f & ~m->f) & MP_BURN)) { + + /* --- No -- allocate a new buffer --- * + * + * The buffer must be secure if (a) the caller requested a secure + * buffer, or (b) the old buffer is secure and I'm not allowed to + * discard the old contents. + */ + + mparena *a; + mpw *v; + + if ((f & MP_BURN) || (!undef && (m->f & MP_BURN))) + a = MPARENA_SECURE; + else + a = MPARENA_GLOBAL; + v = mpalloc(a, sz); + + /* --- Copy the data over --- */ + + if (!undef) { + memcpy(v, m->v, MPWS(len)); + if (sz - len > 0) + memset(v + len, 0, MPWS(sz - len)); + } + + /* --- If @m@ has other references, make a new node --- * + * + * Otherwise dispose of the old buffer. + */ + + if (!(m->f & MP_CONST) && m->ref == 1) { + if (m->f & MP_BURN) + memset(m->v, 0, MPWS(m->sz)); + mpfree(m->a, m->v); + } else { + mp *mm = CREATE(mp); + mm->ref = 1; + mm->f = m->f; + m->ref--; + m = mm; + } + + /* --- Fix up the node --- */ + + m->v = v; + m->vl = v + sz; + m->sz = sz; + m->f = ((m->f & ~(MP_CONST | MP_BURN)) | + (f & (MP_BURN | MP_UNDEF))); + m->a = a; + } + + /* --- If the number is growing in its buffer, fix it up --- */ + + else if (sz > len) { + if (!undef) + memset(m->vl, 0, MPWS(sz - len)); + m->vl = m->v + sz; + } + } + + /* --- Done --- */ + + return (m); +} /*----- That's all, folks -------------------------------------------------*/ diff --git a/mp-misc.c b/mp-misc.c index 7f5513f..840f947 100644 --- a/mp-misc.c +++ b/mp-misc.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-misc.c,v 1.1 1999/11/17 18:02:16 mdw Exp $ + * $Id: mp-misc.c,v 1.2 2000/06/17 11:45:09 mdw Exp $ * * Miscellaneous multiprecision support functions * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-misc.c,v $ + * Revision 1.2 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.1 1999/11/17 18:02:16 mdw * New multiprecision integer arithmetic suite. * @@ -39,24 +44,6 @@ #include "mp.h" -/*----- Paranoia management -----------------------------------------------*/ - -/* --- @mp_burn@ --- * - * - * Arguments: @mp *m@ = pointer to a multiprecision integer - * - * Returns: --- - * - * Use: Marks the integer as `burn-after-use'. When the integer's - * memory is deallocated, it is deleted so that traces can't - * remain in the swap file. In theory. - */ - -void mp_burn(mp *m) -{ - m->f |= MP_BURN; -} - /*----- Basic manipulation ------------------------------------------------*/ /* --- @mp_shrink@ --- * diff --git a/mp.h b/mp.h index a80a8e3..92f1209 100644 --- a/mp.h +++ b/mp.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp.h,v 1.6 1999/12/10 23:19:46 mdw Exp $ + * $Id: mp.h,v 1.7 2000/06/17 11:45:09 mdw Exp $ * * Simple multiprecision arithmetic * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp.h,v $ + * Revision 1.7 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.6 1999/12/10 23:19:46 mdw * Minor bugfixes. New interface for suggested destinations. * @@ -65,6 +70,14 @@ # include "mpw.h" #endif +#ifndef CATACOMB_ARENA_H +# include "arena.h" +#endif + +#ifndef CATACOMB_MPARENA_H +# include "mparena.h" +#endif + #ifndef CATACOMB_MPX_H # include "mpx.h" #endif @@ -74,6 +87,7 @@ typedef struct mp { mpw *v, *vl; size_t sz; + mparena *a; unsigned f; unsigned ref; } mp; @@ -95,81 +109,53 @@ extern mp mp_const[]; #define MP_FOUR (&mp_const[4]) #define MP_FIVE (&mp_const[5]) #define MP_TEN (&mp_const[6]) -#define MP_MONE (&mp_const[7]) +#define MP_256 (&mp_const[7]) +#define MP_MONE (&mp_const[8]) #define MP_NEW ((mp *)0) +#define MP_NEWSEC (&mp_const[9]) -/*----- Memory allocation hooks -------------------------------------------*/ - -#ifndef CATACOMB_MPARENA_H -# include "mparena.h" -#endif - -/* --- @MP_ARENA@ --- * - * - * This selects where memory is allocated from. Tweak to use more fancy - * things like custom arenas. - */ - -#ifndef MP_ARENA -# define MP_ARENA MPARENA_GLOBAL -#endif - -/* --- @MP_ALLOC@ --- * - * - * Arguments: @size_t sz@ = size required - * - * Returns: Pointer to an allocated vector of the requested size. - * - * Use: Hook for vector allocation. - */ - -#ifndef MP_ALLOC -# define MP_ALLOC(sz) mpalloc(MP_ARENA, (sz)) -#endif +/*----- Trivial macros ----------------------------------------------------*/ -/* --- @MP_FREE@ --- * - * - * Arguments: @mpw *v@ = pointer to vector +/* --- @MP_LEN@ --- * * - * Returns: --- + * Arguments: @mp *m@ = pointer to a multiprecision integer * - * Use: Hook for vector deallocation. + * Returns: Length of the integer, in words. */ -#ifndef MP_FREE -# define MP_FREE(v) mpfree(MP_ARENA, (v)) -#endif +#define MP_LEN(m) ((m)->vl - ((m)->v)) -/*----- Paranoia management -----------------------------------------------*/ +/*----- Memory management and reference counting --------------------------*/ -/* --- @mp_burn@ --- * +/* --- @mp_new@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer + * Arguments: @size_t sz@ = size of vector required + * @unsigned f@ = flags to set * - * Returns: --- + * Returns: Pointer to a new MP structure. * - * Use: Marks the integer as `burn-after-use'. When the integer's - * memory is deallocated, it is deleted so that traces can't - * remain in the swap file. In theory. + * Use: Allocates a new multiprecision integer. The data space is + * allocated from either the standard global or secret arena, + * depending on the initial flags requested. */ -extern void mp_burn(mp */*m*/); +extern mp *mp_new(size_t /*sz*/, unsigned /*f*/); -/*----- Trivial macros ----------------------------------------------------*/ - -/* --- @MP_LEN@ --- * +/* --- @mp_create@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer + * Arguments: @size_t sz@ = size of vector required * - * Returns: Length of the integer, in words. + * Returns: Pointer to pristine new MP structure with enough memory + * bolted onto it. + * + * Use: Creates a new multiprecision integer with indeterminate + * contents. The integer has a single reference. */ -#define MP_LEN(m) ((m)->vl - ((m)->v)) - -/*----- Memory management and reference counting --------------------------*/ +extern mp *mp_create(size_t /*sz*/); -/* --- @mp_create@ --- * +/* --- @mp_createsecure@ --- * * * Arguments: @size_t sz@ = size of vector required * @@ -177,10 +163,12 @@ extern void mp_burn(mp */*m*/); * bolted onto it. * * Use: Creates a new multiprecision integer with indeterminate - * contents. The integer has a single reference. + * contents. The integer has a single reference. The integer's + * data space is allocated from the secure arena. Its burn flag + * is set. */ -extern mp *mp_create(size_t /*sz*/); +extern mp *mp_createsecure(size_t /*sz*/); /* --- @mp_build@ --- * * @@ -239,9 +227,8 @@ extern void mp_drop(mp */*m*/); #define MP_DROP(m) do { \ mp *_mm = (m); \ - if (_mm->ref > 1) \ - _mm->ref--; \ - else if (!(_mm->f & MP_CONST)) \ + _mm->ref--; \ + if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \ mp_destroy(_mm); \ } while (0) @@ -258,16 +245,16 @@ extern void mp_drop(mp */*m*/); extern mp *mp_split(mp */*m*/); #define MP_SPLIT(m) do { \ - mp *_mm = (m); \ - if ((_mm->f & MP_CONST) || _mm->ref != 1) { \ - mp *_dd = mp_create(_mm->sz); \ - _dd->vl = _dd->v + MP_LEN(_mm); \ - _dd->f = _mm->f & (MP_NEG | MP_BURN); \ - memcpy(_dd->v, _mm->v, MPWS(MP_LEN(_mm))); \ - _dd->ref = 1; \ - _mm->ref--; \ - (m) = _dd; \ + mp *_m = (m); \ + if ((_m->f & MP_CONST) || _m->ref > 1) { \ + size_t _len = MP_LEN(_m); \ + mp *_mm = mp_new(_len, _m->f); \ + if (!(_m->f & MP_UNDEF)) \ + memcpy(_mm->v, _m->v, MPWS(_len)); \ + _m->ref--; \ + _m = _mm; \ } \ + (m) = _m; \ } while (0) /* --- @mp_resize@ --- * @@ -279,9 +266,7 @@ extern mp *mp_split(mp */*m*/); * * Use: Resizes the vector containing the integer's digits. The new * size must be at least as large as the current integer's - * length. The integer's length is increased and new digits are - * filled with zeroes. This isn't really intended for client - * use. + * length. This isn't really intended for client use. */ extern void mp_resize(mp */*m*/, size_t /*sz*/); @@ -289,16 +274,19 @@ extern void mp_resize(mp */*m*/, size_t /*sz*/); #define MP_RESIZE(m, ssz) do { \ mp *_m = (m); \ size_t _sz = (ssz); \ + mparena *_a = (_m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; \ + mpw *_v; \ size_t _len = MP_LEN(_m); \ - mpw *_v = MP_ALLOC(_sz); \ + assert(((void)"can't make size less than length", _sz >= _len)); \ + _v = mpalloc(_a, _sz); \ if (!(_m->f & MP_UNDEF)) \ memcpy(_v, _m->v, MPWS(_len)); \ if (_m->f & MP_BURN) \ memset(_m->v, 0, MPWS(_m->sz)); \ - MP_FREE(_m->v); \ + mpfree(_m->a, _m->v); \ + _m->a = _a; \ _m->v = _v; \ _m->vl = _v + _len; \ - _m->sz = _sz; \ } while (0) /* --- @mp_ensure@ --- * @@ -315,39 +303,55 @@ extern void mp_resize(mp */*m*/, size_t /*sz*/); extern void mp_ensure(mp */*m*/, size_t /*sz*/); #define MP_ENSURE(m, ssz) do { \ - mp *_mm = (m); \ + mp *_m = (m); \ size_t _ssz = (ssz); \ - size_t _len = MP_LEN(_mm); \ - if (_ssz > _mm->sz) \ - MP_RESIZE(_mm, _ssz); \ - if (!(_mm->f & MP_UNDEF) && _ssz > _len) \ - memset(_mm->vl, 0, MPWS(_ssz - _len)); \ - _mm->vl = _mm->v + _ssz; \ + size_t _len = MP_LEN(_m); \ + if (_ssz >= _len) { \ + if (_ssz > _m->sz) \ + mp_resize(_m, _ssz); \ + if (!(_m->f & MP_UNDEF) && _ssz > _len) \ + memset(_m->vl, 0, MPWS(_ssz - _len)); \ + _m->vl = _m->v + _ssz; \ + } \ } while (0) -/* --- @mp_modify@ --- * +/* --- @mp_dest@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer - * @size_t sz@ = size required + * Arguments: @mp *m@ = a suggested destination integer + * @size_t sz@ = size required for result, in digits + * @unsigned f@ = various flags + * + * Returns: A pointer to an appropriate destination. + * + * Use: Converts a suggested destination into a real destination with + * the required properties. If the real destination is @d@, + * then the following properties will hold: + * + * * @d@ will have exactly one reference. * - * Returns: Pointer to the integer (possibly different). + * * If @m@ is not @MP_NEW@, then the contents of @m@ will not + * change, unless @f@ has the @MP_UNDEF@ flag set. * - * Use: Prepares an integer to be overwritten. It's split off from - * other references to the same integer, and sufficient space is - * allocated. + * * If @m@ is not @MP_NEW@, then he reference count of @m@ on + * entry is equal to the sum of the counts of @d@ and @m@ on + * exit. + * + * * The size of @d@ will be at least @sz@. + * + * * If @f@ has the @MP_BURN@ flag set, then @d@ will be + * allocated from @MPARENA_SECURE@. + * + * Understanding this function is crucial to using Catacomb's + * multiprecision integer library effectively. */ -extern mp *mp_modify(mp */*m*/, size_t /*sz*/); +extern mp *mp_dest(mp */*m*/, size_t /*sz*/, unsigned /*f*/); -#define MP_MODIFY(m, sz) do { \ - size_t _rq = (sz); \ +#define MP_DEST(m, ssz, f) do { \ mp *_m = (m); \ - if (_m == MP_NEW || m->ref > 1 || (_m->f & MP_CONST)) { \ - if (_m) \ - MP_DROP(_m); \ - _m = mp_create(_rq); \ - } else \ - MP_ENSURE(_m, _rq); \ + size_t _ssz = (ssz); \ + unsigned _f = (f); \ + _m = mp_dest(_m, _ssz, _f); \ (m) = _m; \ } while (0) diff --git a/mpbarrett.c b/mpbarrett.c index 711b7ab..aaa1bb7 100644 --- a/mpbarrett.c +++ b/mpbarrett.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpbarrett.c,v 1.3 1999/12/12 15:08:52 mdw Exp $ + * $Id: mpbarrett.c,v 1.4 2000/06/17 11:45:09 mdw Exp $ * * Barrett modular reduction * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpbarrett.c,v $ + * Revision 1.4 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.3 1999/12/12 15:08:52 mdw * Don't bother shifting %$q$% in @mpbarrett_reduce@, just skip the least * significant digits. @@ -73,7 +78,7 @@ void mpbarrett_create(mpbarrett *mb, mp *m) mp_shrink(m); mb->k = MP_LEN(m); mb->m = MP_COPY(m); - b = mp_create(2 * mb->k + 1); + b = mp_new(2 * mb->k + 1, 0); MPX_ZERO(b->v, b->vl - 1); b->vl[-1] = 1; mp_div(&b, 0, b, m); @@ -118,7 +123,8 @@ mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m) if (MP_LEN(m) < k) { m = MP_COPY(m); - MP_DROP(d); + if (d) + MP_DROP(d); return (m); } @@ -130,7 +136,8 @@ mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m) q = mp_mul(MP_NEW, &qq, mb->mu); if (MP_LEN(q) <= k) { m = MP_COPY(m); - MP_DROP(d); + if (d) + MP_DROP(d); return (m); } } @@ -146,10 +153,9 @@ mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m) mvl = m->vl; else mvl = m->v + k + 1; - r = mp_create(k + 1); + r = mp_new(k + 1, (q->f | mb->m->f) & MP_BURN); mpx_umul(r->v, r->vl, q->v + k + 1, q->vl, mb->m->v, mb->m->vl); - r->f = (q->f | mb->m->f) & MP_BURN; - MP_MODIFY(d, k + 1); + MP_DEST(d, k + 1, r->f); mpx_usub(d->v, d->vl, m->v, mvl, r->v, r->vl); d->f = (m->f | r->f) & MP_BURN; MP_DROP(r); @@ -185,6 +191,8 @@ mp *mpbarrett_exp(mpbarrett *mb, mp *d, mp *a, mp *e) a = MP_COPY(a); mp_scan(&sc, e); + if (e->f & MP_BURN) + spare = MP_NEWSEC; if (MP_STEP(&sc)) { size_t sq = 0; for (;;) { diff --git a/mpint.h b/mpint.h index f75d5aa..ba6de80 100644 --- a/mpint.h +++ b/mpint.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpint.h,v 1.2 1999/12/10 23:22:53 mdw Exp $ + * $Id: mpint.h,v 1.3 2000/06/17 11:45:09 mdw Exp $ * * Conversion between MPs and standard C integers * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpint.h,v $ + * Revision 1.3 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.2 1999/12/10 23:22:53 mdw * Support for uint32. * @@ -71,7 +76,7 @@ mp *_d = (d); \ size_t _sz = 4; \ \ - MP_MODIFY(_d, _sz); \ + MP_DEST(_d, _sz, 0); \ _d->f &= ~(MP_NEG | MP_UNDEF); \ \ /* --- Set the sign on the MP --- * \ diff --git a/mpmont-mexp.c b/mpmont-mexp.c index b541f8c..0e5da91 100644 --- a/mpmont-mexp.c +++ b/mpmont-mexp.c @@ -1,8 +1,8 @@ /* -*-c-*- * - * $Id: mpmont-mexp.c,v 1.3 1999/12/10 23:18:39 mdw Exp $ + * $Id: mpmont-mexp.c,v 1.4 2000/06/17 11:45:09 mdw Exp $ * - * Multiplle simultaneous exponentiations + * Multiple simultaneous exponentiations * * (c) 1999 Straylight/Edgeware */ @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpmont-mexp.c,v $ + * Revision 1.4 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.3 1999/12/10 23:18:39 mdw * Change interface for suggested destinations. * @@ -121,6 +126,9 @@ mp *mpmont_mexpr(mpmont *mm, mp *d, mpmont_factor *f, size_t n) * * I must scan the exponents from left to right, which is a shame. It * means that I can't use the standard @mpscan@ stuff, in particular. + * + * If any of the exponents are considered secret then make the accumulator + * automatically set the secret bit. */ { @@ -132,6 +140,8 @@ mp *mpmont_mexpr(mpmont *mm, mp *d, mpmont_factor *f, size_t n) s[i].len = MP_LEN(f[i].exp); if (s[i].len > o) o = s[i].len; + if (f[i].exp->f & MP_BURN) + spare = MP_NEWSEC; } b = 0; } diff --git a/mpmont.c b/mpmont.c index cabb2cb..e7b9bb7 100644 --- a/mpmont.c +++ b/mpmont.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpmont.c,v 1.8 1999/12/22 15:55:00 mdw Exp $ + * $Id: mpmont.c,v 1.9 2000/06/17 11:45:09 mdw Exp $ * * Montgomery reduction * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpmont.c,v $ + * Revision 1.9 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.8 1999/12/22 15:55:00 mdw * Adjust Karatsuba parameters. * @@ -105,7 +110,7 @@ void mpmont_create(mpmont *mm, mp *m) void mpmont_create(mpmont *mm, mp *m) { size_t n = MP_LEN(m); - mp *r2 = mp_create(2 * n + 1); + mp *r2 = mp_new(2 * n + 1, 0); mp r; /* --- Validate the arguments --- */ @@ -213,13 +218,12 @@ mp *mpmont_reduce(mpmont *mm, mp *d, mp *a) /* --- Initial conditioning of the arguments --- */ - if (d == a) - MP_MODIFY(d, 2 * n + 1); - else { - MP_MODIFY(d, 2 * n + 1); - MPX_COPY(d->v, d->vl, a->v, a->vl); - } - + a = MP_COPY(a); + if (d) + MP_DROP(d); + d = a; + MP_DEST(d, 2 * n + 1, a->f); + dv = d->v; dvl = d->vl; mv = mm->m->v; mvl = mm->m->vl; @@ -235,7 +239,6 @@ mp *mpmont_reduce(mpmont *mm, mp *d, mp *a) /* --- Wrap everything up --- */ - d->f = a->f & MP_BURN; memmove(d->v, d->v + n, MPWS(MP_LEN(d) - n)); d->vl -= n; if (MP_CMP(d, >=, mm->m)) @@ -289,7 +292,7 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) a = MP_COPY(a); b = MP_COPY(b); - MP_MODIFY(d, 2 * n + 1); + MP_DEST(d, 2 * n + 1, a->f | b->f | MP_UNDEF); dv = d->v; dvl = d->vl; MPX_ZERO(dv, dvl); av = a->v; avl = a->vl; @@ -351,7 +354,7 @@ mp *mpmont_expr(mpmont *mm, mp *d, mp *a, mp *e) mpscan sc; mp *ar = mpmont_mul(mm, MP_NEW, a, mm->r2); mp *x = MP_COPY(mm->r); - mp *spare = MP_NEW; + mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW; mp_scan(&sc, e); diff --git a/mprand.c b/mprand.c index bf8af69..d4acbb3 100644 --- a/mprand.c +++ b/mprand.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mprand.c,v 1.2 1999/12/22 15:55:33 mdw Exp $ + * $Id: mprand.c,v 1.3 2000/06/17 11:45:09 mdw Exp $ * * Generate a random multiprecision integer * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: mprand.c,v $ + * Revision 1.3 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * * Revision 1.2 1999/12/22 15:55:33 mdw * Modify `mprand' slightly. Add `mprand_range'. * @@ -67,7 +72,8 @@ mp *mprand(mp *d, unsigned b, grand *r, mpw or) { size_t sz = (b + 7) >> 3; - octet *v = xmalloc(sz); + arena *a = (d && (d->f & MP_BURN)) ? arena_secure : arena_global; + octet *v = x_alloc(a, sz); unsigned m; /* --- Fill buffer with random data --- */ @@ -87,7 +93,8 @@ mp *mprand(mp *d, unsigned b, grand *r, mpw or) d = mp_loadb(d, v, sz); d->v[0] |= or; - free(v); + memset(v, 0, sz); + x_free(a, v); return (d); } @@ -109,7 +116,8 @@ mp *mprand_range(mp *d, mp *l, grand *r, mpw or) { size_t b = mp_bits(l); size_t sz = (b + 7) >> 3; - octet *v = xmalloc(sz); + arena *a = (d && (d->f & MP_BURN)) ? arena_secure : arena_global; + octet *v = x_alloc(a, sz); unsigned m; /* --- The algorithm --- * @@ -140,7 +148,8 @@ mp *mprand_range(mp *d, mp *l, grand *r, mpw or) /* --- Done --- */ - free(v); + memset(v, 0, sz); + x_free(a, v); return (d); } -- 2.11.0