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>