mpasbn.c revision 84212
180529Sdd/* 280529Sdd * Copyright (c) 2001 Dima Dorfman. 380529Sdd * All rights reserved. 480529Sdd * 580529Sdd * Redistribution and use in source and binary forms, with or without 680529Sdd * modification, are permitted provided that the following conditions 780529Sdd * are met: 880529Sdd * 1. Redistributions of source code must retain the above copyright 980529Sdd * notice, this list of conditions and the following disclaimer. 1080529Sdd * 2. Redistributions in binary form must reproduce the above copyright 1180529Sdd * notice, this list of conditions and the following disclaimer in the 1280529Sdd * documentation and/or other materials provided with the distribution. 1380529Sdd * 1480529Sdd * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1580529Sdd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1680529Sdd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1780529Sdd * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1880529Sdd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1980529Sdd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2080529Sdd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2180529Sdd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2280529Sdd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2380529Sdd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2480529Sdd * SUCH DAMAGE. 2580529Sdd */ 2680529Sdd 2780529Sdd/* 2880529Sdd * This is the traditional Berkeley MP library implemented in terms of 2980529Sdd * the OpenSSL BIGNUM library. It was written to replace libgmp, and 3080529Sdd * is meant to be as compatible with the latter as feasible. 3180529Sdd * 3280529Sdd * There seems to be a lack of documentation for the Berkeley MP 3380529Sdd * interface. All I could find was libgmp documentation (which didn't 3480529Sdd * talk about the semantics of the functions) and an old SunOS 4.1 3580529Sdd * manual page from 1989. The latter wasn't very detailed, either, 3680529Sdd * but at least described what the function's arguments were. In 3780529Sdd * general the interface seems to be archaic, somewhat poorly 3880529Sdd * designed, and poorly, if at all, documented. It is considered 3980529Sdd * harmful. 4080529Sdd * 4180529Sdd * Miscellaneous notes on this implementation: 4280529Sdd * 4380529Sdd * - The SunOS manual page mentioned above indicates that if an error 4480529Sdd * occurs, the library should "produce messages and core images." 4580529Sdd * Given that most of the functions don't have return values (and 4680529Sdd * thus no sane way of alerting the caller to an error), this seems 4780529Sdd * reasonable. The MPERR and MPERRX macros call warn and warnx, 4880529Sdd * respectively, then abort(). 4980529Sdd * 5080529Sdd * - All the functions which take an argument to be "filled in" 5180529Sdd * assume that the argument has been initialized by one of the *tom() 5280529Sdd * routines before being passed to it. I never saw this documented 5380529Sdd * anywhere, but this seems to be consistent with the way this 5480529Sdd * library is used. 5580529Sdd * 5680529Sdd * - msqrt() is the only routine which had to be implemented which 5780529Sdd * doesn't have a close counterpart in the OpenSSL BIGNUM library. 5880529Sdd * It was implemented by hand using Newton's recursive formula. 5980529Sdd * Doing it this way, although more error-prone, has the positive 6080529Sdd * sideaffect of testing a lot of other functions; if msqrt() 6180529Sdd * produces the correct results, most of the other routines will as 6280529Sdd * well. 6380529Sdd * 6480529Sdd * - Internal-use-only routines (i.e., those defined here statically 6580529Sdd * and not in mp.h) have an underscore prepended to their name (this 6680529Sdd * is more for aesthetical reasons than technical). All such 6780529Sdd * routines take an extra argument, 'msg', that denotes what they 6880529Sdd * should call themselves in an error message. This is so a user 6980529Sdd * doesn't get an error message from a function they didn't call. 7080529Sdd */ 7180529Sdd 7284212Sdillon#include <sys/cdefs.h> 7384212Sdillon__FBSDID("$FreeBSD: head/lib/libmp/mpasbn.c 84212 2001-09-30 21:58:17Z dillon $"); 7480529Sdd 7580529Sdd#include <ctype.h> 7680529Sdd#include <err.h> 7780529Sdd#include <errno.h> 7880529Sdd#include <stdio.h> 7980529Sdd#include <stdlib.h> 8080529Sdd#include <string.h> 8180529Sdd 8280529Sdd#include <openssl/bn.h> 8380529Sdd#include <openssl/crypto.h> 8480529Sdd#include <openssl/err.h> 8580529Sdd 8680529Sdd#include "mp.h" 8780529Sdd 8880529Sdd#define MPERR(s) do { warn s; abort(); } while (0) 8980529Sdd#define MPERRX(s) do { warnx s; abort(); } while (0) 9080529Sdd#define BN_ERRCHECK(msg, expr) do { \ 9180529Sdd if (!(expr)) _bnerr(msg); \ 9280529Sdd} while (0) 9380529Sdd 9480529Sddstatic void _bnerr(const char *); 9580529Sddstatic MINT *_dtom(const char *, const char *); 9680529Sddstatic MINT *_itom(const char *, short); 9780529Sddstatic void _madd(const char *, const MINT *, const MINT *, MINT *); 9880529Sddstatic int _mcmpa(const char *, const MINT *, const MINT *); 9980529Sddstatic void _mdiv(const char *, const MINT *, const MINT *, MINT *, MINT *); 10080529Sddstatic void _mfree(const char *, MINT *); 10180529Sddstatic void _moveb(const char *, const BIGNUM *, MINT *); 10280529Sddstatic void _movem(const char *, const MINT *, MINT *); 10380529Sddstatic void _msub(const char *, const MINT *, const MINT *, MINT *); 10480529Sddstatic char *_mtod(const char *, const MINT *); 10580529Sddstatic char *_mtox(const char *, const MINT *); 10680529Sddstatic void _mult(const char *, const MINT *, const MINT *, MINT *); 10780529Sddstatic void _sdiv(const char *, const MINT *, short, MINT *, short *); 10880529Sddstatic MINT *_xtom(const char *, const char *); 10980529Sdd 11080529Sdd/* 11180529Sdd * Report an error from one of the BN_* functions using MPERRX. 11280529Sdd */ 11380529Sddstatic void 11480529Sdd_bnerr(const char *msg) 11580529Sdd{ 11680529Sdd 11780529Sdd ERR_load_crypto_strings(); 11880529Sdd MPERRX(("%s: %s", msg, ERR_reason_error_string(ERR_get_error()))); 11980529Sdd} 12080529Sdd 12180529Sdd/* 12280529Sdd * Convert a decimal string to an MINT. 12380529Sdd */ 12480529Sddstatic MINT * 12580529Sdd_dtom(const char *msg, const char *s) 12680529Sdd{ 12780529Sdd MINT *mp; 12880529Sdd 12980529Sdd mp = malloc(sizeof(*mp)); 13080529Sdd if (mp == NULL) 13180529Sdd MPERR(("%s", msg)); 13280529Sdd mp->bn = BN_new(); 13380529Sdd if (mp->bn == NULL) 13480529Sdd _bnerr(msg); 13580529Sdd BN_ERRCHECK(msg, BN_dec2bn(&mp->bn, s)); 13680529Sdd return (mp); 13780529Sdd} 13880529Sdd 13980529Sdd/* 14080529Sdd * Compute the greatest common divisor of mp1 and mp2; result goes in rmp. 14180529Sdd */ 14280529Sddvoid 14380529Sddgcd(const MINT *mp1, const MINT *mp2, MINT *rmp) 14480529Sdd{ 14580529Sdd BIGNUM b; 14680529Sdd BN_CTX c; 14780529Sdd 14880529Sdd BN_CTX_init(&c); 14980529Sdd BN_init(&b); 15080529Sdd BN_ERRCHECK("gcd", BN_gcd(&b, mp1->bn, mp2->bn, &c)); 15180529Sdd _moveb("gcd", &b, rmp); 15280529Sdd BN_free(&b); 15380529Sdd BN_CTX_free(&c); 15480529Sdd} 15580529Sdd 15680529Sdd/* 15780529Sdd * Make an MINT out of a short integer. Return value must be mfree()'d. 15880529Sdd */ 15980529Sddstatic MINT * 16080529Sdd_itom(const char *msg, short n) 16180529Sdd{ 16280529Sdd MINT *mp; 16380529Sdd char *s; 16480529Sdd 16580529Sdd asprintf(&s, "%x", n); 16680529Sdd if (s == NULL) 16780529Sdd MPERR(("%s", msg)); 16880529Sdd mp = _xtom(msg, s); 16980529Sdd free(s); 17080529Sdd return (mp); 17180529Sdd} 17280529Sdd 17380529SddMINT * 17480529Sdditom(short n) 17580529Sdd{ 17680529Sdd 17780529Sdd return (_itom("itom", n)); 17880529Sdd} 17980529Sdd 18080529Sdd/* 18180529Sdd * Compute rmp=mp1+mp2. 18280529Sdd */ 18380529Sddstatic void 18480529Sdd_madd(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) 18580529Sdd{ 18680529Sdd BIGNUM b; 18780529Sdd 18880529Sdd BN_init(&b); 18980529Sdd BN_ERRCHECK(msg, BN_add(&b, mp1->bn, mp2->bn)); 19080529Sdd _moveb(msg, &b, rmp); 19180529Sdd BN_free(&b); 19280529Sdd} 19380529Sdd 19480529Sddvoid 19580529Sddmadd(const MINT *mp1, const MINT *mp2, MINT *rmp) 19680529Sdd{ 19780529Sdd 19880529Sdd _madd("madd", mp1, mp2, rmp); 19980529Sdd} 20080529Sdd 20180529Sdd/* 20280529Sdd * Return -1, 0, or 1 if mp1<mp2, mp1==mp2, or mp1>mp2, respectivley. 20380529Sdd */ 20480529Sddint 20580529Sddmcmp(const MINT *mp1, const MINT *mp2) 20680529Sdd{ 20780529Sdd 20880529Sdd return (BN_cmp(mp1->bn, mp2->bn)); 20980529Sdd} 21080529Sdd 21180529Sdd/* 21280529Sdd * Same as mcmp but compares absolute values. 21380529Sdd */ 21480529Sddstatic int 21580529Sdd_mcmpa(const char *msg __unused, const MINT *mp1, const MINT *mp2) 21680529Sdd{ 21780529Sdd 21880529Sdd return (BN_ucmp(mp1->bn, mp2->bn)); 21980529Sdd} 22080529Sdd 22180529Sdd/* 22280529Sdd * Compute qmp=nmp/dmp and rmp=nmp%dmp. 22380529Sdd */ 22480529Sddstatic void 22580529Sdd_mdiv(const char *msg, const MINT *nmp, const MINT *dmp, MINT *qmp, MINT *rmp) 22680529Sdd{ 22780529Sdd BIGNUM q, r; 22880529Sdd BN_CTX c; 22980529Sdd 23080529Sdd BN_CTX_init(&c); 23180529Sdd BN_init(&r); 23280529Sdd BN_init(&q); 23380529Sdd BN_ERRCHECK(msg, BN_div(&q, &r, nmp->bn, dmp->bn, &c)); 23480529Sdd _moveb(msg, &q, qmp); 23580529Sdd _moveb(msg, &r, rmp); 23680529Sdd BN_free(&q); 23780529Sdd BN_free(&r); 23880529Sdd BN_CTX_free(&c); 23980529Sdd} 24080529Sdd 24180529Sddvoid 24280529Sddmdiv(const MINT *nmp, const MINT *dmp, MINT *qmp, MINT *rmp) 24380529Sdd{ 24480529Sdd 24580529Sdd _mdiv("mdiv", nmp, dmp, qmp, rmp); 24680529Sdd} 24780529Sdd 24880529Sdd/* 24980529Sdd * Free memory associated with an MINT. 25080529Sdd */ 25180529Sddstatic void 25280529Sdd_mfree(const char *msg __unused, MINT *mp) 25380529Sdd{ 25480529Sdd 25580529Sdd BN_clear(mp->bn); 25680529Sdd BN_free(mp->bn); 25780529Sdd free(mp); 25880529Sdd} 25980529Sdd 26080529Sddvoid 26180529Sddmfree(MINT *mp) 26280529Sdd{ 26380529Sdd 26480529Sdd _mfree("mfree", mp); 26580529Sdd} 26680529Sdd 26780529Sdd/* 26880529Sdd * Read an integer from standard input and stick the result in mp. 26980529Sdd * The input is treated to be in base 10. This must be the silliest 27080529Sdd * API in existence; why can't the program read in a string and call 27180529Sdd * xtom()? (Or if base 10 is desires, perhaps dtom() could be 27280529Sdd * exported.) 27380529Sdd */ 27480529Sddvoid 27580529Sddmin(MINT *mp) 27680529Sdd{ 27780529Sdd MINT *rmp; 27880529Sdd char *line, *nline; 27980529Sdd size_t linelen; 28080529Sdd 28180529Sdd line = fgetln(stdin, &linelen); 28280529Sdd if (line == NULL) 28380529Sdd MPERR(("min")); 28480529Sdd nline = malloc(linelen); 28580529Sdd if (nline == NULL) 28680529Sdd MPERR(("min")); 28780529Sdd strncpy(nline, line, linelen); 28880529Sdd nline[linelen] = '\0'; 28980529Sdd rmp = _dtom("min", nline); 29080529Sdd _movem("min", rmp, mp); 29180529Sdd _mfree("min", rmp); 29280529Sdd free(nline); 29380529Sdd} 29480529Sdd 29580529Sdd/* 29680529Sdd * Print the value of mp to standard output in base 10. See blurb 29780529Sdd * above min() for why this is so useless. 29880529Sdd */ 29980529Sddvoid 30080529Sddmout(const MINT *mp) 30180529Sdd{ 30280529Sdd char *s; 30380529Sdd 30480529Sdd s = _mtod("mout", mp); 30580529Sdd printf("%s", s); 30680529Sdd free(s); 30780529Sdd} 30880529Sdd 30980529Sdd/* 31080529Sdd * Set the value of tmp to the value of smp (i.e., tmp=smp). 31180529Sdd */ 31280529Sddvoid 31380529Sddmove(const MINT *smp, MINT *tmp) 31480529Sdd{ 31580529Sdd 31680529Sdd _movem("move", smp, tmp); 31780529Sdd} 31880529Sdd 31980529Sdd 32080529Sdd/* 32180529Sdd * Internal routine to set the value of tmp to that of sbp. 32280529Sdd */ 32380529Sddstatic void 32480529Sdd_moveb(const char *msg, const BIGNUM *sbp, MINT *tmp) 32580529Sdd{ 32680529Sdd 32780529Sdd BN_ERRCHECK(msg, BN_copy(tmp->bn, sbp)); 32880529Sdd} 32980529Sdd 33080529Sdd/* 33180529Sdd * Internal routine to set the value of tmp to that of smp. 33280529Sdd */ 33380529Sddstatic void 33480529Sdd_movem(const char *msg, const MINT *smp, MINT *tmp) 33580529Sdd{ 33680529Sdd 33780529Sdd BN_ERRCHECK(msg, BN_copy(tmp->bn, smp->bn)); 33880529Sdd} 33980529Sdd 34080529Sdd/* 34180529Sdd * Compute the square root of nmp and put the result in xmp. The 34280529Sdd * remainder goes in rmp. Should satisfy: rmp=nmp-(xmp*xmp). 34380529Sdd * 34480529Sdd * Note that the OpenSSL BIGNUM library does not have a square root 34580529Sdd * function, so this had to be implemented by hand using Newton's 34680529Sdd * recursive formula: 34780529Sdd * 34880529Sdd * x = (x + (n / x)) / 2 34980529Sdd * 35080529Sdd * where x is the square root of the positive number n. In the 35180529Sdd * beginning, x should be a reasonable guess, but the value 1, 35280529Sdd * although suboptimal, works, too; this is that is used below. 35380529Sdd */ 35480529Sddvoid 35580529Sddmsqrt(const MINT *nmp, MINT *xmp, MINT *rmp) 35680529Sdd{ 35780529Sdd MINT *tolerance; 35880529Sdd MINT *ox, *x; 35980529Sdd MINT *z1, *z2, *z3; 36080529Sdd short i; 36180529Sdd 36280529Sdd tolerance = _itom("msqrt", 1); 36380529Sdd x = _itom("msqrt", 1); 36480529Sdd ox = _itom("msqrt", 0); 36580529Sdd z1 = _itom("msqrt", 0); 36680529Sdd z2 = _itom("msqrt", 0); 36780529Sdd z3 = _itom("msqrt", 0); 36880529Sdd do { 36980529Sdd _movem("msqrt", x, ox); 37080529Sdd _mdiv("msqrt", nmp, x, z1, z2); 37180529Sdd _madd("msqrt", x, z1, z2); 37280529Sdd _sdiv("msqrt", z2, 2, x, &i); 37380529Sdd _msub("msqrt", ox, x, z3); 37480529Sdd } while (_mcmpa("msqrt", z3, tolerance) == 1); 37580529Sdd _movem("msqrt", x, xmp); 37680529Sdd _mult("msqrt", x, x, z1); 37780529Sdd _msub("msqrt", nmp, z1, z2); 37880529Sdd _movem("msqrt", z2, rmp); 37980529Sdd _mfree("msqrt", tolerance); 38080529Sdd _mfree("msqrt", ox); 38180529Sdd _mfree("msqrt", x); 38280529Sdd _mfree("msqrt", z1); 38380529Sdd _mfree("msqrt", z2); 38480529Sdd _mfree("msqrt", z3); 38580529Sdd} 38680529Sdd 38780529Sdd/* 38880529Sdd * Compute rmp=mp1-mp2. 38980529Sdd */ 39080529Sddstatic void 39180529Sdd_msub(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) 39280529Sdd{ 39380529Sdd BIGNUM b; 39480529Sdd 39580529Sdd BN_init(&b); 39680529Sdd BN_ERRCHECK(msg, BN_sub(&b, mp1->bn, mp2->bn)); 39780529Sdd _moveb(msg, &b, rmp); 39880529Sdd BN_free(&b); 39980529Sdd} 40080529Sdd 40180529Sddvoid 40280529Sddmsub(const MINT *mp1, const MINT *mp2, MINT *rmp) 40380529Sdd{ 40480529Sdd 40580529Sdd _msub("msub", mp1, mp2, rmp); 40680529Sdd} 40780529Sdd 40880529Sdd/* 40980529Sdd * Return a decimal representation of mp. Return value must be 41080529Sdd * free()'d. 41180529Sdd */ 41280529Sddstatic char * 41380529Sdd_mtod(const char *msg, const MINT *mp) 41480529Sdd{ 41580529Sdd char *s, *s2; 41680529Sdd 41780529Sdd s = BN_bn2dec(mp->bn); 41880529Sdd if (s == NULL) 41980529Sdd _bnerr(msg); 42080529Sdd asprintf(&s2, "%s", s); 42180529Sdd if (s2 == NULL) 42280529Sdd MPERR(("%s", msg)); 42380529Sdd OPENSSL_free(s); 42480529Sdd return (s2); 42580529Sdd} 42680529Sdd 42780529Sdd/* 42880529Sdd * Return a hexadecimal representation of mp. Return value must be 42980529Sdd * free()'d. 43080529Sdd */ 43180529Sddstatic char * 43280529Sdd_mtox(const char *msg, const MINT *mp) 43380529Sdd{ 43480529Sdd char *p, *s, *s2; 43580529Sdd int len; 43680529Sdd 43780529Sdd s = BN_bn2hex(mp->bn); 43880529Sdd if (s == NULL) 43980529Sdd _bnerr(msg); 44080529Sdd asprintf(&s2, "%s", s); 44180529Sdd if (s2 == NULL) 44280529Sdd MPERR(("%s", msg)); 44380529Sdd OPENSSL_free(s); 44480529Sdd 44580529Sdd /* 44680529Sdd * This is a kludge for libgmp compatibility. The latter's 44780529Sdd * implementation of this function returns lower-case letters, 44880529Sdd * but BN_bn2hex returns upper-case. Some programs (e.g., 44980529Sdd * newkey(1)) are sensitive to this. Although it's probably 45080529Sdd * their fault, it's nice to be compatible. 45180529Sdd */ 45280529Sdd len = strlen(s2); 45380529Sdd for (p = s2; p < s2 + len; p++) 45480529Sdd *p = tolower(*p); 45580529Sdd 45680529Sdd return (s2); 45780529Sdd} 45880529Sdd 45980529Sddchar * 46080529Sddmtox(const MINT *mp) 46180529Sdd{ 46280529Sdd 46380529Sdd return (_mtox("mtox", mp)); 46480529Sdd} 46580529Sdd 46680529Sdd/* 46780529Sdd * Compute rmp=mp1*mp2. 46880529Sdd */ 46980529Sddstatic void 47080529Sdd_mult(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) 47180529Sdd{ 47280529Sdd BIGNUM b; 47380529Sdd BN_CTX c; 47480529Sdd 47580529Sdd BN_CTX_init(&c); 47680529Sdd BN_init(&b); 47780529Sdd BN_ERRCHECK(msg, BN_mul(&b, mp1->bn, mp2->bn, &c)); 47880529Sdd _moveb(msg, &b, rmp); 47980529Sdd BN_free(&b); 48080529Sdd BN_CTX_free(&c); 48180529Sdd} 48280529Sdd 48380529Sddvoid 48480529Sddmult(const MINT *mp1, const MINT *mp2, MINT *rmp) 48580529Sdd{ 48680529Sdd 48780529Sdd _mult("mult", mp1, mp2, rmp); 48880529Sdd} 48980529Sdd 49080529Sdd/* 49180529Sdd * Compute rmp=(bmp^emp)mod mmp. (Note that here and above rpow() '^' 49280529Sdd * means 'raise to power', not 'bitwise XOR'.) 49380529Sdd */ 49480529Sddvoid 49580529Sddpow(const MINT *bmp, const MINT *emp, const MINT *mmp, MINT *rmp) 49680529Sdd{ 49780529Sdd BIGNUM b; 49880529Sdd BN_CTX c; 49980529Sdd 50080529Sdd BN_CTX_init(&c); 50180529Sdd BN_init(&b); 50280529Sdd BN_ERRCHECK("pow", BN_mod_exp(&b, bmp->bn, emp->bn, mmp->bn, &c)); 50380529Sdd _moveb("pow", &b, rmp); 50480529Sdd BN_free(&b); 50580529Sdd BN_CTX_free(&c); 50680529Sdd} 50780529Sdd 50880529Sdd/* 50980529Sdd * Compute rmp=bmp^e. (See note above pow().) 51080529Sdd */ 51180529Sddvoid 51280529Sddrpow(const MINT *bmp, short e, MINT *rmp) 51380529Sdd{ 51480529Sdd MINT *emp; 51580529Sdd BIGNUM b; 51680529Sdd BN_CTX c; 51780529Sdd 51880529Sdd BN_CTX_init(&c); 51980529Sdd BN_init(&b); 52080529Sdd emp = _itom("rpow", e); 52180529Sdd BN_ERRCHECK("rpow", BN_exp(&b, bmp->bn, emp->bn, &c)); 52280529Sdd _moveb("rpow", &b, rmp); 52380529Sdd _mfree("rpow", emp); 52480529Sdd BN_free(&b); 52580529Sdd BN_CTX_free(&c); 52680529Sdd} 52780529Sdd 52880529Sdd/* 52980529Sdd * Compute qmp=nmp/d and ro=nmp%d. 53080529Sdd */ 53180529Sddstatic void 53280529Sdd_sdiv(const char *msg, const MINT *nmp, short d, MINT *qmp, short *ro) 53380529Sdd{ 53480529Sdd MINT *dmp, *rmp; 53580529Sdd BIGNUM q, r; 53680529Sdd BN_CTX c; 53780529Sdd char *s; 53880529Sdd 53980529Sdd BN_CTX_init(&c); 54080529Sdd BN_init(&q); 54180529Sdd BN_init(&r); 54280529Sdd dmp = _itom(msg, d); 54380529Sdd rmp = _itom(msg, 0); 54480529Sdd BN_ERRCHECK(msg, BN_div(&q, &r, nmp->bn, dmp->bn, &c)); 54580529Sdd _moveb(msg, &q, qmp); 54680529Sdd _moveb(msg, &r, rmp); 54780529Sdd s = _mtox(msg, rmp); 54880529Sdd errno = 0; 54980529Sdd *ro = strtol(s, NULL, 16); 55080529Sdd if (errno != 0) 55180529Sdd MPERR(("%s underflow or overflow", msg)); 55280529Sdd free(s); 55380529Sdd _mfree(msg, dmp); 55480529Sdd _mfree(msg, rmp); 55580529Sdd BN_free(&r); 55680529Sdd BN_free(&q); 55780529Sdd BN_CTX_free(&c); 55880529Sdd} 55980529Sdd 56080529Sddvoid 56180529Sddsdiv(const MINT *nmp, short d, MINT *qmp, short *ro) 56280529Sdd{ 56380529Sdd 56480529Sdd _sdiv("sdiv", nmp, d, qmp, ro); 56580529Sdd} 56680529Sdd 56780529Sdd/* 56880529Sdd * Convert a hexadecimal string to an MINT. 56980529Sdd */ 57080529Sddstatic MINT * 57180529Sdd_xtom(const char *msg, const char *s) 57280529Sdd{ 57380529Sdd MINT *mp; 57480529Sdd 57580529Sdd mp = malloc(sizeof(*mp)); 57680529Sdd if (mp == NULL) 57780529Sdd MPERR(("%s", msg)); 57880529Sdd mp->bn = BN_new(); 57980529Sdd if (mp->bn == NULL) 58080529Sdd _bnerr(msg); 58180529Sdd BN_ERRCHECK(msg, BN_hex2bn(&mp->bn, s)); 58280529Sdd return (mp); 58380529Sdd} 58480529Sdd 58580529SddMINT * 58680529Sddxtom(const char *s) 58780529Sdd{ 58880529Sdd 58980529Sdd return (_xtom("xtom", s)); 59080529Sdd} 591