diff options
Diffstat (limited to 'lib/libmp')
| -rw-r--r-- | lib/libmp/Makefile | 18 | ||||
| -rw-r--r-- | lib/libmp/Makefile.depend | 16 | ||||
| -rw-r--r-- | lib/libmp/Symbol.map | 22 | ||||
| -rw-r--r-- | lib/libmp/libmp.3 | 312 | ||||
| -rw-r--r-- | lib/libmp/mp.h | 31 | ||||
| -rw-r--r-- | lib/libmp/mpasbn.c | 629 | ||||
| -rw-r--r-- | lib/libmp/tests/Makefile | 6 | ||||
| -rw-r--r-- | lib/libmp/tests/Makefile.depend | 18 | ||||
| -rw-r--r-- | lib/libmp/tests/legacy_test.c | 209 |
9 files changed, 1261 insertions, 0 deletions
diff --git a/lib/libmp/Makefile b/lib/libmp/Makefile new file mode 100644 index 000000000000..3ef85cee79c0 --- /dev/null +++ b/lib/libmp/Makefile @@ -0,0 +1,18 @@ +.include <src.opts.mk> + +LIB= mp +SHLIB_MAJOR= 7 +LIBADD= crypto +MAN= libmp.3 +INCS= mp.h +SRCS= mpasbn.c + +CFLAGS+= -I${SRCTOP}/crypto + +VERSION_DEF= ${SRCTOP}/lib/libc/Versions.def +SYMBOL_MAPS= ${.CURDIR}/Symbol.map + +HAS_TESTS= +SUBDIR.${MK_TESTS}+= tests + +.include <bsd.lib.mk> diff --git a/lib/libmp/Makefile.depend b/lib/libmp/Makefile.depend new file mode 100644 index 000000000000..341f44c61163 --- /dev/null +++ b/lib/libmp/Makefile.depend @@ -0,0 +1,16 @@ +# Autogenerated - do NOT edit! + +DIRDEPS = \ + include \ + include/xlocale \ + lib/${CSU_DIR} \ + lib/libc \ + lib/libcompiler_rt \ + secure/lib/libcrypto \ + + +.include <dirdeps.mk> + +.if ${DEP_RELDIR} == ${_DEP_RELDIR} +# local dependencies - needed for -jN in clean tree +.endif diff --git a/lib/libmp/Symbol.map b/lib/libmp/Symbol.map new file mode 100644 index 000000000000..f00906af6337 --- /dev/null +++ b/lib/libmp/Symbol.map @@ -0,0 +1,22 @@ +/* + */ + +FBSD_1.1 { + mp_gcd; + mp_itom; + mp_madd; + mp_mcmp; + mp_mdiv; + mp_mfree; + mp_min; + mp_mout; + mp_move; + mp_msqrt; + mp_msub; + mp_mtox; + mp_mult; + mp_pow; + mp_rpow; + mp_sdiv; + mp_xtom; +}; diff --git a/lib/libmp/libmp.3 b/lib/libmp/libmp.3 new file mode 100644 index 000000000000..d0686985c621 --- /dev/null +++ b/lib/libmp/libmp.3 @@ -0,0 +1,312 @@ +.\" +.\" Copyright (c) 2001 Dima Dorfman. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" This manual page is based on the mp(3X) manual page from Sun Release +.\" 4.1, dated 7 September 1989. It's an old, crufty, and relatively ugly +.\" manual page, but it does document what appears to be the "traditional" +.\" libmp interface. +.\" +.\" See above for rationale for this date. +.Dd September 7, 1989 +.Dt LIBMP 3 +.Os +.Sh NAME +.Nm libmp +.Nd traditional BSD multiple precision integer arithmetic library +.Sh SYNOPSIS +.In mp.h +.Pp +Function prototypes are given in the main body of the text. +.Pp +Applications using this interface must be linked with +.Fl l Ns Ar mp +(this library) +and +.Fl l Ns Ar crypto +.Pq Xr crypto 3 . +.Sh DESCRIPTION +.Bf -symbolic +This interface is obsolete in favor of the +.Xr crypto 3 +.Vt BIGNUM +library. +.Ef +.Pp +.Nm +is the traditional +.Bx +multiple precision integer arithmetic library. +It has a number of problems, +and is unsuitable for use in any programs where reliability is a concern. +It is provided here for compatibility only. +.Pp +These routines perform arithmetic on integers of arbitrary precision +stored using the defined type +.Vt MINT . +Pointers to +.Vt MINT +are initialized using +.Fn mp_itom +or +.Fn mp_xtom , +and must be recycled with +.Fn mp_mfree +when they are no longer needed. +Routines which store a result in one of their arguments expect that +the latter has also been initialized prior to being passed to it. +The following routines are defined and implemented: +.Pp +.Ft "MINT *" Ns +.Fn mp_itom "short n" ; +.Pp +.Ft "MINT *" Ns +.Fn mp_xtom "const char *s" ; +.Pp +.Ft "char *" Ns +.Fn mp_mtox "const MINT *mp" ; +.Pp +.Ft void +.Fn mp_mfree "MINT *mp" ; +.Bd -ragged -offset indent +.Fn mp_itom +returns an +.Vt MINT +with the value of +.Fa n . +.Fn mp_xtom +returns an +.Vt MINT +with the value of +.Fa s , +which is treated to be in hexadecimal. +The return values from +.Fn mp_itom +and +.Fn mp_xtom +must be released with +.Fn mp_mfree +when they are no longer needed. +.Fn mp_mtox +returns a null-terminated hexadecimal string having the value of +.Fa mp ; +its return value must be released with +.Fn free +.Pq Xr free 3 +when it is no longer needed. +.Ed +.Pp +.Ft void +.Fn mp_madd "const MINT *mp1" "const MINT *mp2" "MINT *rmp" ; +.Pp +.Ft void +.Fn mp_msub "const MINT *mp1" "const MINT *mp2" "MINT *rmp" ; +.Pp +.Ft void +.Fn mp_mult "const MINT *mp1" "const MINT *mp2" "MINT *rmp" ; +.Bd -ragged -offset indent +.Fn mp_madd , +.Fn mp_msub , +and +.Fn mp_mult +store the sum, difference, or product, respectively, of +.Fa mp1 +and +.Fa mp2 +in +.Fa rmp . +.Ed +.Pp +.Ft void +.Fn mp_mdiv "const MINT *nmp" "const MINT *dmp" "MINT *qmp" "MINT *rmp" ; +.Pp +.Ft void +.Fn mp_sdiv "const MINT *nmp" "short d" "MINT *qmp" "short *ro" ; +.Bd -ragged -offset indent +.Fn mp_mdiv +computes the quotient and remainder of +.Fa nmp +and +.Fa dmp +and stores the result in +.Fa qmp +and +.Fa rmp , +respectively. +.Fn mp_sdiv +is similar to +.Fn mp_mdiv +except the divisor +.Fa ( dmp +or +.Fa d ) +and remainder +.Fa ( rmp +or +.Fa ro ) +are ordinary integers. +.Ed +.Pp +.Ft void +.Fn mp_pow "const MINT *bmp" "const MINT *emp" "const MINT *mmp" "MINT *rmp" ; +.Pp +.Ft void +.Fn mp_rpow "const MINT *bmp" "short e" "MINT *rmp" ; +.Bd -ragged -offset indent +.Fn mp_rpow +computes the result of +.Fa bmp +raised to the +.Fa emp Ns th +power and reduced modulo +.Fa mmp ; +the result is stored in +.Fa rmp . +.Fn mp_pow +computes the result of +.Fa bmp +raised to the +.Fa e Ns th +power and stores the result in +.Fa rmp . +.Ed +.Pp +.Ft void +.Fn mp_min "MINT *mp" ; +.Pp +.Ft void +.Fn mp_mout "const MINT *mp" ; +.Bd -ragged -offset indent +.Fn mp_min +reads a line from standard input, tries to interpret it as a decimal +number, and if successful, stores the result in +.Fa mp . +.Fn mp_mout +prints the value, in decimal, of +.Fa mp +to standard output (without a trailing newline). +.Ed +.Pp +.Ft void +.Fn mp_gcd "const MINT *mp1" "const MINT *mp2" "MINT *rmp" ; +.Bd -ragged -offset indent +.Fn mp_gcd +computes the greatest common divisor of +.Fa mp1 +and +.Fa mp2 +and stores the result in +.Fa rmp . +.Ed +.Pp +.Ft int +.Fn mp_mcmp "const MINT *mp1" "const MINT *mp2" ; +.Bd -ragged -offset indent +.Fa mcmp +compares the values of +.Fa mp1 +and +.Fa mp2 +and returns +0 if the two values are equal, +a value greater than 0 if +.Fa mp1 +is greater than +.Fa mp2 , +and a value less than 0 if +.Fa mp2 +is greater than +.Fa mp1 . +.Ed +.Pp +.Ft void +.Fn mp_move "const MINT *smp" "MINT *tmp" ; +.Bd -ragged -offset indent +.Fn mp_move +copies the value of +.Fa smp +to +.Fa tmp +(both values must be initialized). +.Ed +.Pp +.Ft void +.Fn mp_msqrt "const MINT *nmp" "MINT *xmp" "MINT *rmp" ; +.Bd -ragged -offset indent +.Fn mp_msqrt +computes the square root and remainder of +.Fa nmp +and stores them in +.Fa xmp +and +.Fa rmp , +respectively. +.Ed +.Sh IMPLEMENTATION NOTES +This version of +.Nm +is implemented in terms of the +.Xr crypto 3 +.Vt BIGNUM +library. +.Sh DIAGNOSTICS +Running out of memory or illegal operations result in error messages +on standard error and a call to +.Xr abort 3 . +.Sh SEE ALSO +.Xr abort 3 , +.Xr bn 3 , +.Xr crypto 3 , +.Xr free 3 , +.Xr malloc 3 , +.Xr math 3 +.Sh HISTORY +A +.Nm +library appeared in +.Bx 4.3 . +.Fx 2.2 +shipped with a +.Nm +implemented in terms of +.Nm libgmp . +This implementation appeared in +.Fx 5.0 . +.Sh BUGS +Errors are reported via output to standard error and abnormal +program termination instead of via return values. +The application cannot control this behavior. +.Pp +It is not clear whether the string returned by +.Fn mp_mtox +may be written to by the caller. +This implementation allows it, but others may not. +Ideally, +.Fn mp_mtox +would take a pointer to a buffer to fill in. +.Pp +It is not clear whether using the same variable as both source and +destination in a single invocation is permitted. +Some of the calls in this implementation allow this, while others +do not. diff --git a/lib/libmp/mp.h b/lib/libmp/mp.h new file mode 100644 index 000000000000..16a6d040bc29 --- /dev/null +++ b/lib/libmp/mp.h @@ -0,0 +1,31 @@ + +#ifndef _MP_H_ +#define _MP_H_ + +#ifndef HEADER_BN_H_ +#include <openssl/bn.h> +#endif + +typedef struct _mint { + BIGNUM *bn; +} MINT; + +void mp_gcd(const MINT *, const MINT *, MINT *); +MINT *mp_itom(short); +void mp_madd(const MINT *, const MINT *, MINT *); +int mp_mcmp(const MINT *, const MINT *); +void mp_mdiv(const MINT *, const MINT *, MINT *, MINT *); +void mp_mfree(MINT *); +void mp_min(MINT *); +void mp_mout(const MINT *); +void mp_move(const MINT *, MINT *); +void mp_msqrt(const MINT *, MINT *, MINT *); +void mp_msub(const MINT *, const MINT *, MINT *); +char *mp_mtox(const MINT *); +void mp_mult(const MINT *, const MINT *, MINT *); +void mp_pow(const MINT *, const MINT *, const MINT *, MINT *); +void mp_rpow(const MINT *, short, MINT *); +void mp_sdiv(const MINT *, short, MINT *, short *); +MINT *mp_xtom(const char *); + +#endif /* !_MP_H_ */ diff --git a/lib/libmp/mpasbn.c b/lib/libmp/mpasbn.c new file mode 100644 index 000000000000..7ccbeccd15eb --- /dev/null +++ b/lib/libmp/mpasbn.c @@ -0,0 +1,629 @@ +/*- + * SPDX-License-Identifier: BSD-2-Clause + * + * Copyright (c) 2001 Dima Dorfman. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +/* + * This is the traditional Berkeley MP library implemented in terms of + * the OpenSSL BIGNUM library. It was written to replace libgmp, and + * is meant to be as compatible with the latter as feasible. + * + * There seems to be a lack of documentation for the Berkeley MP + * interface. All I could find was libgmp documentation (which didn't + * talk about the semantics of the functions) and an old SunOS 4.1 + * manual page from 1989. The latter wasn't very detailed, either, + * but at least described what the function's arguments were. In + * general the interface seems to be archaic, somewhat poorly + * designed, and poorly, if at all, documented. It is considered + * harmful. + * + * Miscellaneous notes on this implementation: + * + * - The SunOS manual page mentioned above indicates that if an error + * occurs, the library should "produce messages and core images." + * Given that most of the functions don't have return values (and + * thus no sane way of alerting the caller to an error), this seems + * reasonable. The MPERR and MPERRX macros call warn and warnx, + * respectively, then abort(). + * + * - All the functions which take an argument to be "filled in" + * assume that the argument has been initialized by one of the *tom() + * routines before being passed to it. I never saw this documented + * anywhere, but this seems to be consistent with the way this + * library is used. + * + * - msqrt() is the only routine which had to be implemented which + * doesn't have a close counterpart in the OpenSSL BIGNUM library. + * It was implemented by hand using Newton's recursive formula. + * Doing it this way, although more error-prone, has the positive + * sideaffect of testing a lot of other functions; if msqrt() + * produces the correct results, most of the other routines will as + * well. + * + * - Internal-use-only routines (i.e., those defined here statically + * and not in mp.h) have an underscore prepended to their name (this + * is more for aesthetical reasons than technical). All such + * routines take an extra argument, 'msg', that denotes what they + * should call themselves in an error message. This is so a user + * doesn't get an error message from a function they didn't call. + */ + +#include <sys/cdefs.h> +#include <ctype.h> +#include <err.h> +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <openssl/crypto.h> +#include <openssl/err.h> + +#include "mp.h" + +#define MPERR(s) do { warn s; abort(); } while (0) +#define MPERRX(s) do { warnx s; abort(); } while (0) +#define BN_ERRCHECK(msg, expr) do { \ + if (!(expr)) _bnerr(msg); \ +} while (0) + +static void _bnerr(const char *); +static MINT *_dtom(const char *, const char *); +static MINT *_itom(const char *, short); +static void _madd(const char *, const MINT *, const MINT *, MINT *); +static int _mcmpa(const char *, const MINT *, const MINT *); +static void _mdiv(const char *, const MINT *, const MINT *, MINT *, MINT *, + BN_CTX *); +static void _mfree(const char *, MINT *); +static void _moveb(const char *, const BIGNUM *, MINT *); +static void _movem(const char *, const MINT *, MINT *); +static void _msub(const char *, const MINT *, const MINT *, MINT *); +static char *_mtod(const char *, const MINT *); +static char *_mtox(const char *, const MINT *); +static void _mult(const char *, const MINT *, const MINT *, MINT *, BN_CTX *); +static void _sdiv(const char *, const MINT *, short, MINT *, short *, BN_CTX *); +static MINT *_xtom(const char *, const char *); + +/* + * Report an error from one of the BN_* functions using MPERRX. + */ +static void +_bnerr(const char *msg) +{ + + ERR_load_crypto_strings(); + MPERRX(("%s: %s", msg, ERR_reason_error_string(ERR_get_error()))); +} + +/* + * Convert a decimal string to an MINT. + */ +static MINT * +_dtom(const char *msg, const char *s) +{ + MINT *mp; + + mp = malloc(sizeof(*mp)); + if (mp == NULL) + MPERR(("%s", msg)); + mp->bn = BN_new(); + if (mp->bn == NULL) + _bnerr(msg); + BN_ERRCHECK(msg, BN_dec2bn(&mp->bn, s)); + return (mp); +} + +/* + * Compute the greatest common divisor of mp1 and mp2; result goes in rmp. + */ +void +mp_gcd(const MINT *mp1, const MINT *mp2, MINT *rmp) +{ + BIGNUM *b; + BN_CTX *c; + + b = NULL; + c = BN_CTX_new(); + if (c != NULL) + b = BN_new(); + if (c == NULL || b == NULL) + _bnerr("gcd"); + BN_ERRCHECK("gcd", BN_gcd(b, mp1->bn, mp2->bn, c)); + _moveb("gcd", b, rmp); + BN_free(b); + BN_CTX_free(c); +} + +/* + * Make an MINT out of a short integer. Return value must be mfree()'d. + */ +static MINT * +_itom(const char *msg, short n) +{ + MINT *mp; + char *s; + + asprintf(&s, "%x", n); + if (s == NULL) + MPERR(("%s", msg)); + mp = _xtom(msg, s); + free(s); + return (mp); +} + +MINT * +mp_itom(short n) +{ + + return (_itom("itom", n)); +} + +/* + * Compute rmp=mp1+mp2. + */ +static void +_madd(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) +{ + BIGNUM *b; + + b = BN_new(); + if (b == NULL) + _bnerr(msg); + BN_ERRCHECK(msg, BN_add(b, mp1->bn, mp2->bn)); + _moveb(msg, b, rmp); + BN_free(b); +} + +void +mp_madd(const MINT *mp1, const MINT *mp2, MINT *rmp) +{ + + _madd("madd", mp1, mp2, rmp); +} + +/* + * Return -1, 0, or 1 if mp1<mp2, mp1==mp2, or mp1>mp2, respectivley. + */ +int +mp_mcmp(const MINT *mp1, const MINT *mp2) +{ + + return (BN_cmp(mp1->bn, mp2->bn)); +} + +/* + * Same as mcmp but compares absolute values. + */ +static int +_mcmpa(const char *msg __unused, const MINT *mp1, const MINT *mp2) +{ + + return (BN_ucmp(mp1->bn, mp2->bn)); +} + +/* + * Compute qmp=nmp/dmp and rmp=nmp%dmp. + */ +static void +_mdiv(const char *msg, const MINT *nmp, const MINT *dmp, MINT *qmp, MINT *rmp, + BN_CTX *c) +{ + BIGNUM *q, *r; + + q = NULL; + r = BN_new(); + if (r != NULL) + q = BN_new(); + if (r == NULL || q == NULL) + _bnerr(msg); + BN_ERRCHECK(msg, BN_div(q, r, nmp->bn, dmp->bn, c)); + _moveb(msg, q, qmp); + _moveb(msg, r, rmp); + BN_free(q); + BN_free(r); +} + +void +mp_mdiv(const MINT *nmp, const MINT *dmp, MINT *qmp, MINT *rmp) +{ + BN_CTX *c; + + c = BN_CTX_new(); + if (c == NULL) + _bnerr("mdiv"); + _mdiv("mdiv", nmp, dmp, qmp, rmp, c); + BN_CTX_free(c); +} + +/* + * Free memory associated with an MINT. + */ +static void +_mfree(const char *msg __unused, MINT *mp) +{ + + BN_clear(mp->bn); + BN_free(mp->bn); + free(mp); +} + +void +mp_mfree(MINT *mp) +{ + + _mfree("mfree", mp); +} + +/* + * Read an integer from standard input and stick the result in mp. + * The input is treated to be in base 10. This must be the silliest + * API in existence; why can't the program read in a string and call + * xtom()? (Or if base 10 is desires, perhaps dtom() could be + * exported.) + */ +void +mp_min(MINT *mp) +{ + MINT *rmp; + char *line, *nline; + size_t linelen; + + line = fgetln(stdin, &linelen); + if (line == NULL) + MPERR(("min")); + nline = malloc(linelen + 1); + if (nline == NULL) + MPERR(("min")); + memcpy(nline, line, linelen); + nline[linelen] = '\0'; + rmp = _dtom("min", nline); + _movem("min", rmp, mp); + _mfree("min", rmp); + free(nline); +} + +/* + * Print the value of mp to standard output in base 10. See blurb + * above min() for why this is so useless. + */ +void +mp_mout(const MINT *mp) +{ + char *s; + + s = _mtod("mout", mp); + printf("%s", s); + free(s); +} + +/* + * Set the value of tmp to the value of smp (i.e., tmp=smp). + */ +void +mp_move(const MINT *smp, MINT *tmp) +{ + + _movem("move", smp, tmp); +} + + +/* + * Internal routine to set the value of tmp to that of sbp. + */ +static void +_moveb(const char *msg, const BIGNUM *sbp, MINT *tmp) +{ + + BN_ERRCHECK(msg, BN_copy(tmp->bn, sbp)); +} + +/* + * Internal routine to set the value of tmp to that of smp. + */ +static void +_movem(const char *msg, const MINT *smp, MINT *tmp) +{ + + BN_ERRCHECK(msg, BN_copy(tmp->bn, smp->bn)); +} + +/* + * Compute the square root of nmp and put the result in xmp. The + * remainder goes in rmp. Should satisfy: rmp=nmp-(xmp*xmp). + * + * Note that the OpenSSL BIGNUM library does not have a square root + * function, so this had to be implemented by hand using Newton's + * recursive formula: + * + * x = (x + (n / x)) / 2 + * + * where x is the square root of the positive number n. In the + * beginning, x should be a reasonable guess, but the value 1, + * although suboptimal, works, too; this is that is used below. + */ +void +mp_msqrt(const MINT *nmp, MINT *xmp, MINT *rmp) +{ + BN_CTX *c; + MINT *tolerance; + MINT *ox, *x; + MINT *z1, *z2, *z3; + short i; + + c = BN_CTX_new(); + if (c == NULL) + _bnerr("msqrt"); + tolerance = _itom("msqrt", 1); + x = _itom("msqrt", 1); + ox = _itom("msqrt", 0); + z1 = _itom("msqrt", 0); + z2 = _itom("msqrt", 0); + z3 = _itom("msqrt", 0); + do { + _movem("msqrt", x, ox); + _mdiv("msqrt", nmp, x, z1, z2, c); + _madd("msqrt", x, z1, z2); + _sdiv("msqrt", z2, 2, x, &i, c); + _msub("msqrt", ox, x, z3); + } while (_mcmpa("msqrt", z3, tolerance) == 1); + _movem("msqrt", x, xmp); + _mult("msqrt", x, x, z1, c); + _msub("msqrt", nmp, z1, z2); + _movem("msqrt", z2, rmp); + _mfree("msqrt", tolerance); + _mfree("msqrt", ox); + _mfree("msqrt", x); + _mfree("msqrt", z1); + _mfree("msqrt", z2); + _mfree("msqrt", z3); + BN_CTX_free(c); +} + +/* + * Compute rmp=mp1-mp2. + */ +static void +_msub(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) +{ + BIGNUM *b; + + b = BN_new(); + if (b == NULL) + _bnerr(msg); + BN_ERRCHECK(msg, BN_sub(b, mp1->bn, mp2->bn)); + _moveb(msg, b, rmp); + BN_free(b); +} + +void +mp_msub(const MINT *mp1, const MINT *mp2, MINT *rmp) +{ + + _msub("msub", mp1, mp2, rmp); +} + +/* + * Return a decimal representation of mp. Return value must be + * free()'d. + */ +static char * +_mtod(const char *msg, const MINT *mp) +{ + char *s, *s2; + + s = BN_bn2dec(mp->bn); + if (s == NULL) + _bnerr(msg); + asprintf(&s2, "%s", s); + if (s2 == NULL) + MPERR(("%s", msg)); + OPENSSL_free(s); + return (s2); +} + +/* + * Return a hexadecimal representation of mp. Return value must be + * free()'d. + */ +static char * +_mtox(const char *msg, const MINT *mp) +{ + char *p, *s, *s2; + int len; + + s = BN_bn2hex(mp->bn); + if (s == NULL) + _bnerr(msg); + asprintf(&s2, "%s", s); + if (s2 == NULL) + MPERR(("%s", msg)); + OPENSSL_free(s); + + /* + * This is a kludge for libgmp compatibility. The latter's + * implementation of this function returns lower-case letters, + * but BN_bn2hex returns upper-case. Some programs (e.g., + * newkey(1)) are sensitive to this. Although it's probably + * their fault, it's nice to be compatible. + */ + len = strlen(s2); + for (p = s2; p < s2 + len; p++) + *p = tolower(*p); + + return (s2); +} + +char * +mp_mtox(const MINT *mp) +{ + + return (_mtox("mtox", mp)); +} + +/* + * Compute rmp=mp1*mp2. + */ +static void +_mult(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp, BN_CTX *c) +{ + BIGNUM *b; + + b = BN_new(); + if (b == NULL) + _bnerr(msg); + BN_ERRCHECK(msg, BN_mul(b, mp1->bn, mp2->bn, c)); + _moveb(msg, b, rmp); + BN_free(b); +} + +void +mp_mult(const MINT *mp1, const MINT *mp2, MINT *rmp) +{ + BN_CTX *c; + + c = BN_CTX_new(); + if (c == NULL) + _bnerr("mult"); + _mult("mult", mp1, mp2, rmp, c); + BN_CTX_free(c); +} + +/* + * Compute rmp=(bmp^emp)mod mmp. (Note that here and above rpow() '^' + * means 'raise to power', not 'bitwise XOR'.) + */ +void +mp_pow(const MINT *bmp, const MINT *emp, const MINT *mmp, MINT *rmp) +{ + BIGNUM *b; + BN_CTX *c; + + b = NULL; + c = BN_CTX_new(); + if (c != NULL) + b = BN_new(); + if (c == NULL || b == NULL) + _bnerr("pow"); + BN_ERRCHECK("pow", BN_mod_exp(b, bmp->bn, emp->bn, mmp->bn, c)); + _moveb("pow", b, rmp); + BN_free(b); + BN_CTX_free(c); +} + +/* + * Compute rmp=bmp^e. (See note above pow().) + */ +void +mp_rpow(const MINT *bmp, short e, MINT *rmp) +{ + MINT *emp; + BIGNUM *b; + BN_CTX *c; + + b = NULL; + c = BN_CTX_new(); + if (c != NULL) + b = BN_new(); + if (c == NULL || b == NULL) + _bnerr("rpow"); + emp = _itom("rpow", e); + BN_ERRCHECK("rpow", BN_exp(b, bmp->bn, emp->bn, c)); + _moveb("rpow", b, rmp); + _mfree("rpow", emp); + BN_free(b); + BN_CTX_free(c); +} + +/* + * Compute qmp=nmp/d and ro=nmp%d. + */ +static void +_sdiv(const char *msg, const MINT *nmp, short d, MINT *qmp, short *ro, + BN_CTX *c) +{ + MINT *dmp, *rmp; + BIGNUM *q, *r; + char *s; + + r = NULL; + q = BN_new(); + if (q != NULL) + r = BN_new(); + if (q == NULL || r == NULL) + _bnerr(msg); + dmp = _itom(msg, d); + rmp = _itom(msg, 0); + BN_ERRCHECK(msg, BN_div(q, r, nmp->bn, dmp->bn, c)); + _moveb(msg, q, qmp); + _moveb(msg, r, rmp); + s = _mtox(msg, rmp); + errno = 0; + *ro = strtol(s, NULL, 16); + if (errno != 0) + MPERR(("%s underflow or overflow", msg)); + free(s); + _mfree(msg, dmp); + _mfree(msg, rmp); + BN_free(r); + BN_free(q); +} + +void +mp_sdiv(const MINT *nmp, short d, MINT *qmp, short *ro) +{ + BN_CTX *c; + + c = BN_CTX_new(); + if (c == NULL) + _bnerr("sdiv"); + _sdiv("sdiv", nmp, d, qmp, ro, c); + BN_CTX_free(c); +} + +/* + * Convert a hexadecimal string to an MINT. + */ +static MINT * +_xtom(const char *msg, const char *s) +{ + MINT *mp; + + mp = malloc(sizeof(*mp)); + if (mp == NULL) + MPERR(("%s", msg)); + mp->bn = BN_new(); + if (mp->bn == NULL) + _bnerr(msg); + BN_ERRCHECK(msg, BN_hex2bn(&mp->bn, s)); + return (mp); +} + +MINT * +mp_xtom(const char *s) +{ + + return (_xtom("xtom", s)); +} diff --git a/lib/libmp/tests/Makefile b/lib/libmp/tests/Makefile new file mode 100644 index 000000000000..4d66ca659376 --- /dev/null +++ b/lib/libmp/tests/Makefile @@ -0,0 +1,6 @@ +TAP_TESTS_C+= legacy_test + +WARNS?= 3 +LIBADD+= mp + +.include <bsd.test.mk> diff --git a/lib/libmp/tests/Makefile.depend b/lib/libmp/tests/Makefile.depend new file mode 100644 index 000000000000..8f19138c1948 --- /dev/null +++ b/lib/libmp/tests/Makefile.depend @@ -0,0 +1,18 @@ +# Autogenerated - do NOT edit! + +DIRDEPS = \ + gnu/lib/csu \ + include \ + include/xlocale \ + lib/${CSU_DIR} \ + lib/libc \ + lib/libcompiler_rt \ + lib/libmp \ + secure/lib/libcrypto \ + + +.include <dirdeps.mk> + +.if ${DEP_RELDIR} == ${_DEP_RELDIR} +# local dependencies - needed for -jN in clean tree +.endif diff --git a/lib/libmp/tests/legacy_test.c b/lib/libmp/tests/legacy_test.c new file mode 100644 index 000000000000..8e3a4d10a0b9 --- /dev/null +++ b/lib/libmp/tests/legacy_test.c @@ -0,0 +1,209 @@ +/*- + * Copyright (c) 2006, Simon L. Nielsen <simon@FreeBSD.org> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + */ +#include <sys/cdefs.h> +#include <mp.h> +#include <stdio.h> +#include <string.h> +#include <sysexits.h> + +MINT *c0, *c1, *c2, *c3, *c5, *c6, *c8, *c10, *c14, *c15, *c25, \ + *c42,*c43, *c44, *c45, *t0, *t1; +static int tnr = 0; + +static void +testmcmp(const MINT *mp1, const MINT *mp2, const char *tname) +{ + + if (mp_mcmp(mp1, mp2) == 0) + printf("ok %d - %s\n", ++tnr, tname); + else + printf("not ok - %d %s\n", ++tnr, tname); +} + +static void +testsimpel(void) +{ + const char str42[] = "2a"; + MINT *t2; + char *s; + + mp_madd(c42, c1, t0); + testmcmp(c43, t0, "madd0"); + mp_madd(t0, c1, t0); + testmcmp(c44, t0, "madd1"); + mp_msub(t0, c1, t0); + testmcmp(c43, t0, "msub0"); + mp_msub(t0, c1, t0); + testmcmp(c42, t0, "msub1"); + mp_move(c42, t0); + testmcmp(c42, t0, "move0"); + + t2 = mp_xtom(str42); + testmcmp(c42, t2, "xtom"); + s = mp_mtox(t2); + if (strcmp(str42, s) == 0) + printf("ok %d - %s\n", ++tnr, "mtox0"); + else + printf("not ok %d - %s\n", ++tnr, "mtox0"); + mp_mfree(t2); +} + +static void +testgcd(void) +{ + + mp_gcd(c10, c15, t0); + testmcmp(t0, c5, "gcd0"); +} + +static void +testmsqrt(void) +{ + + mp_msqrt(c25, t0, t1); + testmcmp(t0, c5, "msqrt0"); + testmcmp(t1, c0, "msqrt1"); + mp_msqrt(c42, t0, t1); + testmcmp(t0, c6, "msqrt2"); + testmcmp(t1, c6, "msqrt3"); +} + +static void +testdiv(void) +{ + short ro; + MINT *t2; + + mp_mdiv(c42, c5, t0, t1); + testmcmp(t0, c8, "mdiv0"); + testmcmp(t1, c2, "mdiv1"); + + mp_mdiv(c10, c8, t0, t1); + testmcmp(t0, c1, "mdiv2"); + testmcmp(t1, c2, "mdiv3"); + + mp_sdiv(c42, 5, t0, &ro); + testmcmp(t0, c8, "sdiv0"); + t2 = mp_itom(ro); // Simpler to use common testmcmp() + testmcmp(t2, c2, "sdiv1"); + mp_mfree(t2); + + mp_sdiv(c10, 8, t0, &ro); + testmcmp(t0, c1, "sdiv2"); + t2 = mp_itom(ro); // Simpler to use common testmcmp() + testmcmp(t2, c2, "sdiv3"); + mp_mfree(t2); +} + +static void +testmult(void) +{ + + mp_mult(c5, c2, t0); + testmcmp(t0, c10, "mmult0"); + mp_mult(c3, c14, t0); + testmcmp(t0, c42, "mmult1"); +} + +static void +testpow(void) +{ + + mp_pow(c2, c3, c10, t0); + testmcmp(t0, c8, "pow0"); + mp_pow(c2, c3, c3, t0); + testmcmp(t0, c2, "pow1"); + mp_rpow(c2, 3, t0); + testmcmp(t0, c8, "rpow0"); +} + +/* + * This program performs some very basic tests of libmp(3). It is by + * no means expected to perform a complete test of the library for + * correctness, but is meant to test the API to make sure libmp (or + * libcrypto) updates don't totally break the library. + */ +int +main(int argc, char *argv[]) +{ + + printf("1..25\n"); + + /* + * Init "constants" variables - done in this somewhat + * cumbersome way to in theory be able to check for memory + * leaks. + */ + c0 = mp_itom(0); + c1 = mp_itom(1); + c2 = mp_itom(2); + c3 = mp_itom(3); + c5 = mp_itom(5); + c6 = mp_itom(6); + c8 = mp_itom(8); + c10 = mp_itom(10); + c14 = mp_itom(14); + c15 = mp_itom(15); + c25 = mp_itom(25); + c42 = mp_itom(42); + c43 = mp_itom(43); + c44 = mp_itom(44); + c45 = mp_itom(45); + + // Init temp variables + t0 = mp_itom(0); + t1 = mp_itom(0); + + // Run tests + testsimpel(); + testgcd(); + testdiv(); + testmult(); + testpow(); + testmsqrt(); + + // Cleanup + mp_mfree(c0); + mp_mfree(c1); + mp_mfree(c2); + mp_mfree(c3); + mp_mfree(c5); + mp_mfree(c6); + mp_mfree(c8); + mp_mfree(c10); + mp_mfree(c14); + mp_mfree(c15); + mp_mfree(c25); + mp_mfree(c42); + mp_mfree(c43); + mp_mfree(c44); + mp_mfree(c45); + mp_mfree(t0); + mp_mfree(t1); + + return (EX_OK); +} |