Date: Fri, 13 Jul 2001 06:55:25 -0700 From: Dima Dorfman <dima@unixfreak.org> To: arch@freebsd.org Subject: Getting rid of libgmp Message-ID: <20010713135525.37C293E2F@bazooka.unixfreak.org>
next in thread | raw e-mail | index | archive | help
Hi folks, A week or so ago there was a thread on -current about removing libgmp. It was generally agreed that this was a good idea, but (as usual) somebody has to do the work, and some people wanted FreeBSD to continue to supply a libmp-compatible interface. To satisfy both groups, I propose that we import a libmp that is implemented in terms of the OpenSSL BIGNUM library. Attached below is a sharball of such an implementation. I couldn't find very good documentation on the libmp interface, but I've tested this with most[1] of the software in FreeBSD that uses libmp, and all programs work as well as they did before. The library is quite small; all functions except msqrt() have a BIGNUM equivilent. It requires that the program using it be linked with -lcrypto[2]. Comments? Suggestions? Thanks, Dima Dorfman dima@unixfreak.org [1] I wasn't able to test Kerberized telnet, but it looks like it uses the same code as the non-Kerberized one, so I don't think there will be a problem. [2] Someone said it was possible to factor out the BIGNUM bits out of libcrypto; this is obviously possible, but they depend on so many other parts of the OpenSSL library (e.g., its elaborate error mechanism, BIO, etc.) that I think it isn't worth it. That said, it's something somebody might want to look into later. # This is a shell archive. Save it in a file, remove anything before # this line, and then unpack it by entering "sh file". Note, it may # create directories; files and directories will be owned by you and # have default permissions. # # This archive contains: # # libmp # libmp/Makefile # libmp/mp.h # libmp/mpasbn.c # echo c - libmp mkdir -p libmp > /dev/null 2>&1 echo x - libmp/Makefile sed 's/^X//' >libmp/Makefile << 'END-of-libmp/Makefile' X# $FreeBSD$ X XLIB= mp XCFLAGS+= -ansi -pedantic XWARNS?= 2 XNO_WERROR= yes XSHLIB_MAJOR= 4 XSRCS= mpasbn.c X Xbeforeinstall: X ${INSTALL} -C -o ${BINOWN} -g ${BINGRP} -m 444 \ X ${.CURDIR}/mp.h ${DESTDIR}/usr/include X X.include <bsd.lib.mk> END-of-libmp/Makefile echo x - libmp/mp.h sed 's/^X//' >libmp/mp.h << 'END-of-libmp/mp.h' X#ifndef _MP_H_ X#define _MP_H_ X X#include <openssl/bn.h> X Xtypedef struct _mint { X BIGNUM *bn; X} MINT; X X Xvoid gcd(const MINT *, const MINT *, MINT *); XMINT *itom(short); Xvoid madd(const MINT *, const MINT *, MINT *); Xint mcmp(const MINT *, const MINT *); Xvoid mdiv(const MINT *, const MINT *, MINT *, MINT *); Xvoid mfree(MINT *); Xvoid min(MINT *); Xvoid mout(const MINT *); Xvoid move(const MINT *, MINT *); Xvoid msqrt(const MINT *, MINT *, MINT *); Xvoid msub(const MINT *, const MINT *, MINT *); Xchar *mtox(const MINT *); Xvoid mult(const MINT *, const MINT *, MINT *); Xvoid pow(const MINT *, const MINT *, const MINT *, MINT *); Xvoid rpow(const MINT *, short, MINT *); Xvoid sdiv(const MINT *, short, MINT *, short *); XMINT *xtom(const char *); X X#endif /* !_MP_H_ */ END-of-libmp/mp.h echo x - libmp/mpasbn.c sed 's/^X//' >libmp/mpasbn.c << 'END-of-libmp/mpasbn.c' X/* X * Copyright (c) 2001, Dima Dorfman. X * All rights reserved. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * X * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X/* X * This is the traditional Berkeley MP library implemented in terms of X * the OpenSSL BIGNUM library. It was written to replace libgmp, and X * is meant to be as compatible with the latter as feasible. X * X * There seems to be a lack of documentation for the Berkeley MP X * interface. All I could find was libgmp documentation (which didn't X * talk about the semantics of the functions) and an old SunOS 4.1 X * manual page from 1989. The latter wasn't very detailed, either, X * but at least described what the function's arguments were. In X * general the interface seems to be archaic, somewhat poorly X * designed, and poorly, if at all, documented. It is considered X * harmful. X * X * Miscellaneous notes on this implementation: X * X * - The SunOS manual page mentioned above indicates that if an error X * occurs, the library should "produce messages and core images." X * Given that most of the functions don't have return values (and X * thus no sane way of alerting the caller to an error), this seems X * reasonable. The MPERR and MPERRX macros call warn and warnx, X * respectively, then abort(). X * X * - All the functions which take an argument to be "filled in" X * assume that the argument has been initialized by one of the *tom() X * routines before being passed to it. I never saw this documented X * anywhere, but this seems to be consistent with the way this X * library is used. X * X * - msqrt() is the only routine which had to be implemented which X * doesn't have a close counterpart in the OpenSSL BIGNUM library. X * It was implemented by hand using Newton's recursive formula. X * Doing it this way, although more error-prone, has the positive X * sideaffect of testing a lot of other functions; if msqrt() X * produces the correct results, most of the other routines will as X * well. X * X * - Internal-use-only routines (i.e., those defined here statically X * and not in mp.h) have an underscore prepended to their name (this X * is more for aesthetical reasons than technical). All such X * routines take an extra argument, 'msg', that denotes what they X * should call themselves in an error message. This is so a user X * doesn't get an error message from a function they didn't call. X */ X X#ifndef lint Xstatic const char rcsid[] = X "$FreeBSD$"; X#endif /* not lint */ X X#include <ctype.h> X#include <err.h> X#include <errno.h> X#include <stdio.h> X#include <stdlib.h> X#include <string.h> X X#include <openssl/bn.h> X#include <openssl/crypto.h> X#include <openssl/err.h> X X#include "mp.h" X X#define MPERR(s) do { warn s; abort(); } while (0) X#define MPERRX(s) do { warnx s; abort(); } while (0) X#define BN_ERRCHECK(msg, expr) do { \ X if (!(expr)) _bnerr(msg); \ X} while (0) X Xstatic void _bnerr(const char *); Xstatic MINT *_dtom(const char *, const char *); Xstatic MINT *_itom(const char *, short); Xstatic void _madd(const char *, const MINT *, const MINT *, MINT *); Xstatic int _mcmpa(const char *, const MINT *, const MINT *); Xstatic void _mdiv(const char *, const MINT *, const MINT *, MINT *, MINT *); Xstatic void _mfree(const char *, MINT *); Xstatic void _moveb(const char *, const BIGNUM *, MINT *); Xstatic void _movem(const char *, const MINT *, MINT *); Xstatic void _msub(const char *, const MINT *, const MINT *, MINT *); Xstatic char *_mtod(const char *, const MINT *); Xstatic char *_mtox(const char *, const MINT *); Xstatic void _mult(const char *, const MINT *, const MINT *, MINT *); Xstatic void _sdiv(const char *, const MINT *, short, MINT *, short *); Xstatic MINT *_xtom(const char *, const char *); X X/* X * Report an error from one of the BN_* functions using MPERRX. X */ Xstatic void X_bnerr(const char *msg) X{ X X ERR_load_crypto_strings(); X MPERRX(("%s: %s", msg, ERR_reason_error_string(ERR_get_error()))); X} X X/* X * Convert a decimal string to an MINT. X */ Xstatic MINT * X_dtom(const char *msg, const char *s) X{ X MINT *mp; X X mp = malloc(sizeof(*mp)); X if (mp == NULL) X MPERR(("%s", msg)); X mp->bn = BN_new(); X if (mp->bn == NULL) X _bnerr(msg); X BN_ERRCHECK(msg, BN_dec2bn(&mp->bn, s)); X return (mp); X} X X/* X * Compute the greatest common divisor of mp1 and mp2; result goes in rmp. X */ Xvoid Xgcd(const MINT *mp1, const MINT *mp2, MINT *rmp) X{ X BIGNUM b; X BN_CTX c; X X BN_CTX_init(&c); X BN_init(&b); X BN_ERRCHECK("gcd", BN_gcd(&b, mp1->bn, mp2->bn, &c)); X _moveb("gcd", &b, rmp); X BN_free(&b); X BN_CTX_free(&c); X} X X/* X * Make an MINT out of a short integer. Return value must be mfree()'d. X */ Xstatic MINT * X_itom(const char *msg, short n) X{ X MINT *mp; X char *s; X X asprintf(&s, "%x", n); X if (s == NULL) X MPERR(("%s", msg)); X mp = _xtom(msg, s); X free(s); X return (mp); X} X XMINT * Xitom(short n) X{ X X return (_itom("itom", n)); X} X X/* X * Compute rmp=mp1+mp2. X */ Xstatic void X_madd(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) X{ X BIGNUM b; X X BN_init(&b); X BN_ERRCHECK(msg, BN_add(&b, mp1->bn, mp2->bn)); X _moveb(msg, &b, rmp); X BN_free(&b); X} X Xvoid Xmadd(const MINT *mp1, const MINT *mp2, MINT *rmp) X{ X X _madd("madd", mp1, mp2, rmp); X} X X/* X * Return -1, 0, or 1 if mp1<mp2, mp1==mp2, or mp1>mp2, respectivley. X */ Xint Xmcmp(const MINT *mp1, const MINT *mp2) X{ X X return (BN_cmp(mp1->bn, mp2->bn)); X} X X/* X * Same as mcmp but compares absolute values. X */ Xstatic int X_mcmpa(const char *msg __unused, const MINT *mp1, const MINT *mp2) X{ X X return (BN_ucmp(mp1->bn, mp2->bn)); X} X X/* X * Compute qmp=nmp/dmp and rmp=nmp%dmp. X */ Xstatic void X_mdiv(const char *msg, const MINT *nmp, const MINT *dmp, MINT *qmp, MINT *rmp) X{ X BIGNUM q, r; X BN_CTX c; X X BN_CTX_init(&c); X BN_init(&r); X BN_init(&q); X BN_ERRCHECK(msg, BN_div(&q, &r, nmp->bn, dmp->bn, &c)); X _moveb(msg, &q, qmp); X _moveb(msg, &r, rmp); X BN_free(&q); X BN_free(&r); X BN_CTX_free(&c); X} X Xvoid Xmdiv(const MINT *nmp, const MINT *dmp, MINT *qmp, MINT *rmp) X{ X X _mdiv("mdiv", nmp, dmp, qmp, rmp); X} X X/* X * Free memory associated with an MINT. X */ Xstatic void X_mfree(const char *msg __unused, MINT *mp) X{ X X BN_clear(mp->bn); X BN_free(mp->bn); X free(mp); X} X Xvoid Xmfree(MINT *mp) X{ X X _mfree("mfree", mp); X} X X/* X * Read an integer from standard input and stick the result in mp. X * The input is treated to be in base 10. This must be the silliest X * API in existence; why can't the program read in a string and call X * xtom()? (Or if base 10 is desires, perhaps dtom() could be X * exported.) X */ Xvoid Xmin(MINT *mp) X{ X MINT *rmp; X char *line, *nline; X size_t linelen; X X line = fgetln(stdin, &linelen); X if (line == NULL) X MPERR(("min")); X nline = malloc(linelen); X if (nline == NULL) X MPERR(("min")); X strncpy(nline, line, linelen); X nline[linelen] = '\0'; X rmp = _dtom("min", nline); X _movem("min", rmp, mp); X _mfree("min", rmp); X free(nline); X} X X/* X * Print the value of mp to standard output in base 10. See blurb X * above min() for why this is so useless. X */ Xvoid Xmout(const MINT *mp) X{ X char *s; X X s = _mtod("mout", mp); X printf("%s", s); X free(s); X} X X/* X * Set the value of tmp to the value of smp (i.e., tmp=smp). X */ Xvoid Xmove(const MINT *smp, MINT *tmp) X{ X X _movem("move", smp, tmp); X} X X X/* X * Internal routine to set the value of tmp to that of sbp. X */ Xstatic void X_moveb(const char *msg, const BIGNUM *sbp, MINT *tmp) X{ X X BN_ERRCHECK(msg, BN_copy(tmp->bn, sbp)); X} X X/* X * Internal routine to set the value of tmp to that of smp. X */ Xstatic void X_movem(const char *msg, const MINT *smp, MINT *tmp) X{ X X BN_ERRCHECK(msg, BN_copy(tmp->bn, smp->bn)); X} X X/* X * Compute the square root of nmp and put the result in xmp. The X * remainder goes in rmp. Should satisfy: rmp=nmp-(xmp*xmp). X * X * Note that the OpenSSL BIGNUM library does not have a square root X * function, so this had to be implemented by hand using Newton's X * recursive formula: X * X * x = (x + (n / x)) / 2 X * X * where x is the square root of the positive number n. In the X * beginning, x should be a reasonable guess, but the value 1, X * although suboptimal, works, too; this is that is used below. X */ Xvoid Xmsqrt(const MINT *nmp, MINT *xmp, MINT *rmp) X{ X MINT *tolerance; X MINT *ox, *x; X MINT *z1, *z2, *z3; X short i; X X tolerance = _itom("msqrt", 1); X x = _itom("msqrt", 1); X ox = _itom("msqrt", 0); X z1 = _itom("msqrt", 0); X z2 = _itom("msqrt", 0); X z3 = _itom("msqrt", 0); X do { X _movem("msqrt", x, ox); X _mdiv("msqrt", nmp, x, z1, z2); X _madd("msqrt", x, z1, z2); X _sdiv("msqrt", z2, 2, x, &i); X _msub("msqrt", ox, x, z3); X } while (_mcmpa("msqrt", z3, tolerance) == 1); X _movem("msqrt", x, xmp); X _mult("msqrt", x, x, z1); X _msub("msqrt", nmp, z1, z2); X _movem("msqrt", z2, rmp); X _mfree("msqrt", tolerance); X _mfree("msqrt", ox); X _mfree("msqrt", x); X _mfree("msqrt", z1); X _mfree("msqrt", z2); X _mfree("msqrt", z3); X} X X/* X * Compute rmp=mp1-mp2. X */ Xstatic void X_msub(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) X{ X BIGNUM b; X X BN_init(&b); X BN_ERRCHECK(msg, BN_sub(&b, mp1->bn, mp2->bn)); X _moveb(msg, &b, rmp); X BN_free(&b); X} X Xvoid Xmsub(const MINT *mp1, const MINT *mp2, MINT *rmp) X{ X X _msub("msub", mp1, mp2, rmp); X} X X/* X * Return a decimal representation of mp. Return value must be X * free()'d. X */ Xstatic char * X_mtod(const char *msg, const MINT *mp) X{ X char *s, *s2; X X s = BN_bn2dec(mp->bn); X if (s == NULL) X _bnerr(msg); X asprintf(&s2, "%s", s); X if (s2 == NULL) X MPERR(("%s", msg)); X OPENSSL_free(s); X return (s2); X} X X/* X * Return a hexadecimal representation of mp. Return value must be X * free()'d. X */ Xstatic char * X_mtox(const char *msg, const MINT *mp) X{ X char *p, *s, *s2; X int len; X X s = BN_bn2hex(mp->bn); X if (s == NULL) X _bnerr(msg); X asprintf(&s2, "%s", s); X if (s2 == NULL) X MPERR(("%s", msg)); X OPENSSL_free(s); X X /* X * This is a kludge for libgmp compatibility. The latter's X * implementation of this function returns lower-case letters, X * but BN_bn2hex returns upper-case. Some programs (e.g., X * newkey(1)) are sensitive to this. Although it's probably X * their fault, it's nice to be compatible. X */ X len = strlen(s2); X for (p = s2; p < s2 + len; p++) X *p = tolower(*p); X X return (s2); X} X Xchar * Xmtox(const MINT *mp) X{ X X return (_mtox("mtox", mp)); X} X X/* X * Compute rmp=mp1*mp2. X */ Xstatic void X_mult(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) X{ X BIGNUM b; X BN_CTX c; X X BN_CTX_init(&c); X BN_init(&b); X BN_ERRCHECK(msg, BN_mul(&b, mp1->bn, mp2->bn, &c)); X _moveb(msg, &b, rmp); X BN_free(&b); X BN_CTX_free(&c); X} X Xvoid Xmult(const MINT *mp1, const MINT *mp2, MINT *rmp) X{ X X _mult("mult", mp1, mp2, rmp); X} X X/* X * Compute rmp=(bmp^emp)mod mmp. (Note that here and above rpow() '^' X * means 'raise to power', not 'bitwise XOR'.) X */ Xvoid Xpow(const MINT *bmp, const MINT *emp, const MINT *mmp, MINT *rmp) X{ X BIGNUM b; X BN_CTX c; X X BN_CTX_init(&c); X BN_init(&b); X BN_ERRCHECK("pow", BN_mod_exp(&b, bmp->bn, emp->bn, mmp->bn, &c)); X _moveb("pow", &b, rmp); X BN_free(&b); X BN_CTX_free(&c); X} X X/* X * Compute rmp=bmp^e. (See note above pow().) X */ Xvoid Xrpow(const MINT *bmp, short e, MINT *rmp) X{ X MINT *emp; X BIGNUM b; X BN_CTX c; X X BN_CTX_init(&c); X BN_init(&b); X emp = _itom("rpow", e); X BN_ERRCHECK("rpow", BN_exp(&b, bmp->bn, emp->bn, &c)); X _moveb("rpow", &b, rmp); X _mfree("rpow", emp); X BN_free(&b); X BN_CTX_free(&c); X} X X/* X * Compute qmp=nmp/d and ro=nmp%d. X */ Xstatic void X_sdiv(const char *msg, const MINT *nmp, short d, MINT *qmp, short *ro) X{ X MINT *dmp, *rmp; X BIGNUM q, r; X BN_CTX c; X char *s; X X BN_CTX_init(&c); X BN_init(&q); X BN_init(&r); X dmp = _itom(msg, d); X rmp = _itom(msg, 0); X BN_ERRCHECK(msg, BN_div(&q, &r, nmp->bn, dmp->bn, &c)); X _moveb(msg, &q, qmp); X _moveb(msg, &r, rmp); X s = _mtox(msg, rmp); X errno = 0; X *ro = strtol(s, NULL, 16); X if (errno != 0) X MPERR(("%s underflow or overflow", msg)); X free(s); X _mfree(msg, dmp); X _mfree(msg, rmp); X BN_free(&r); X BN_free(&q); X BN_CTX_free(&c); X} X Xvoid Xsdiv(const MINT *nmp, short d, MINT *qmp, short *ro) X{ X X _sdiv("sdiv", nmp, d, qmp, ro); X} X X/* X * Convert a hexadecimal string to an MINT. X */ Xstatic MINT * X_xtom(const char *msg, const char *s) X{ X MINT *mp; X X mp = malloc(sizeof(*mp)); X if (mp == NULL) X MPERR(("%s", msg)); X mp->bn = BN_new(); X if (mp->bn == NULL) X _bnerr(msg); X BN_ERRCHECK(msg, BN_hex2bn(&mp->bn, s)); X return (mp); X} X XMINT * Xxtom(const char *s) X{ X X return (_xtom("xtom", s)); X} END-of-libmp/mpasbn.c exit To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20010713135525.37C293E2F>