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$"); 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/crypto.h> 8380529Sdd#include <openssl/err.h> 8480529Sdd 8580529Sdd#include "mp.h" 8680529Sdd 8780529Sdd#define MPERR(s) do { warn s; abort(); } while (0) 8880529Sdd#define MPERRX(s) do { warnx s; abort(); } while (0) 8980529Sdd#define BN_ERRCHECK(msg, expr) do { \ 9080529Sdd if (!(expr)) _bnerr(msg); \ 9180529Sdd} while (0) 9280529Sdd 9380529Sddstatic void _bnerr(const char *); 9480529Sddstatic MINT *_dtom(const char *, const char *); 9580529Sddstatic MINT *_itom(const char *, short); 9680529Sddstatic void _madd(const char *, const MINT *, const MINT *, MINT *); 9780529Sddstatic int _mcmpa(const char *, const MINT *, const MINT *); 98160840Ssimonstatic void _mdiv(const char *, const MINT *, const MINT *, MINT *, MINT *, 99160840Ssimon BN_CTX *); 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 *); 106160840Ssimonstatic void _mult(const char *, const MINT *, const MINT *, MINT *, BN_CTX *); 107160840Ssimonstatic void _sdiv(const char *, const MINT *, short, MINT *, short *, BN_CTX *); 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 143189092Sedmp_gcd(const MINT *mp1, const MINT *mp2, MINT *rmp) 14480529Sdd{ 14580529Sdd BIGNUM b; 146160805Ssimon BN_CTX *c; 14780529Sdd 148160805Ssimon c = BN_CTX_new(); 149160805Ssimon if (c == NULL) 150160805Ssimon _bnerr("gcd"); 15180529Sdd BN_init(&b); 152160805Ssimon BN_ERRCHECK("gcd", BN_gcd(&b, mp1->bn, mp2->bn, c)); 15380529Sdd _moveb("gcd", &b, rmp); 15480529Sdd BN_free(&b); 155160805Ssimon BN_CTX_free(c); 15680529Sdd} 15780529Sdd 15880529Sdd/* 15980529Sdd * Make an MINT out of a short integer. Return value must be mfree()'d. 16080529Sdd */ 16180529Sddstatic MINT * 16280529Sdd_itom(const char *msg, short n) 16380529Sdd{ 16480529Sdd MINT *mp; 16580529Sdd char *s; 16680529Sdd 16780529Sdd asprintf(&s, "%x", n); 16880529Sdd if (s == NULL) 16980529Sdd MPERR(("%s", msg)); 17080529Sdd mp = _xtom(msg, s); 17180529Sdd free(s); 17280529Sdd return (mp); 17380529Sdd} 17480529Sdd 17580529SddMINT * 176189092Sedmp_itom(short n) 17780529Sdd{ 17880529Sdd 17980529Sdd return (_itom("itom", n)); 18080529Sdd} 18180529Sdd 18280529Sdd/* 18380529Sdd * Compute rmp=mp1+mp2. 18480529Sdd */ 18580529Sddstatic void 18680529Sdd_madd(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) 18780529Sdd{ 18880529Sdd BIGNUM b; 18980529Sdd 19080529Sdd BN_init(&b); 19180529Sdd BN_ERRCHECK(msg, BN_add(&b, mp1->bn, mp2->bn)); 19280529Sdd _moveb(msg, &b, rmp); 19380529Sdd BN_free(&b); 19480529Sdd} 19580529Sdd 19680529Sddvoid 197189092Sedmp_madd(const MINT *mp1, const MINT *mp2, MINT *rmp) 19880529Sdd{ 19980529Sdd 20080529Sdd _madd("madd", mp1, mp2, rmp); 20180529Sdd} 20280529Sdd 20380529Sdd/* 20480529Sdd * Return -1, 0, or 1 if mp1<mp2, mp1==mp2, or mp1>mp2, respectivley. 20580529Sdd */ 20680529Sddint 207189092Sedmp_mcmp(const MINT *mp1, const MINT *mp2) 20880529Sdd{ 20980529Sdd 21080529Sdd return (BN_cmp(mp1->bn, mp2->bn)); 21180529Sdd} 21280529Sdd 21380529Sdd/* 21480529Sdd * Same as mcmp but compares absolute values. 21580529Sdd */ 21680529Sddstatic int 21780529Sdd_mcmpa(const char *msg __unused, const MINT *mp1, const MINT *mp2) 21880529Sdd{ 21980529Sdd 22080529Sdd return (BN_ucmp(mp1->bn, mp2->bn)); 22180529Sdd} 22280529Sdd 22380529Sdd/* 22480529Sdd * Compute qmp=nmp/dmp and rmp=nmp%dmp. 22580529Sdd */ 22680529Sddstatic void 227160840Ssimon_mdiv(const char *msg, const MINT *nmp, const MINT *dmp, MINT *qmp, MINT *rmp, 228160840Ssimon BN_CTX *c) 22980529Sdd{ 23080529Sdd BIGNUM q, r; 23180529Sdd 23280529Sdd BN_init(&r); 23380529Sdd BN_init(&q); 234160805Ssimon BN_ERRCHECK(msg, BN_div(&q, &r, nmp->bn, dmp->bn, c)); 23580529Sdd _moveb(msg, &q, qmp); 23680529Sdd _moveb(msg, &r, rmp); 23780529Sdd BN_free(&q); 23880529Sdd BN_free(&r); 23980529Sdd} 24080529Sdd 24180529Sddvoid 242189092Sedmp_mdiv(const MINT *nmp, const MINT *dmp, MINT *qmp, MINT *rmp) 24380529Sdd{ 244160840Ssimon BN_CTX *c; 24580529Sdd 246160840Ssimon c = BN_CTX_new(); 247160840Ssimon if (c == NULL) 248160840Ssimon _bnerr("mdiv"); 249160840Ssimon _mdiv("mdiv", nmp, dmp, qmp, rmp, c); 250160840Ssimon BN_CTX_free(c); 25180529Sdd} 25280529Sdd 25380529Sdd/* 25480529Sdd * Free memory associated with an MINT. 25580529Sdd */ 25680529Sddstatic void 25780529Sdd_mfree(const char *msg __unused, MINT *mp) 25880529Sdd{ 25980529Sdd 26080529Sdd BN_clear(mp->bn); 26180529Sdd BN_free(mp->bn); 26280529Sdd free(mp); 26380529Sdd} 26480529Sdd 26580529Sddvoid 266189092Sedmp_mfree(MINT *mp) 26780529Sdd{ 26880529Sdd 26980529Sdd _mfree("mfree", mp); 27080529Sdd} 27180529Sdd 27280529Sdd/* 27380529Sdd * Read an integer from standard input and stick the result in mp. 27480529Sdd * The input is treated to be in base 10. This must be the silliest 27580529Sdd * API in existence; why can't the program read in a string and call 27680529Sdd * xtom()? (Or if base 10 is desires, perhaps dtom() could be 27780529Sdd * exported.) 27880529Sdd */ 27980529Sddvoid 280189092Sedmp_min(MINT *mp) 28180529Sdd{ 28280529Sdd MINT *rmp; 28380529Sdd char *line, *nline; 28480529Sdd size_t linelen; 28580529Sdd 28680529Sdd line = fgetln(stdin, &linelen); 28780529Sdd if (line == NULL) 28880529Sdd MPERR(("min")); 28980529Sdd nline = malloc(linelen); 29080529Sdd if (nline == NULL) 29180529Sdd MPERR(("min")); 29280529Sdd strncpy(nline, line, linelen); 29380529Sdd nline[linelen] = '\0'; 29480529Sdd rmp = _dtom("min", nline); 29580529Sdd _movem("min", rmp, mp); 29680529Sdd _mfree("min", rmp); 29780529Sdd free(nline); 29880529Sdd} 29980529Sdd 30080529Sdd/* 30180529Sdd * Print the value of mp to standard output in base 10. See blurb 30280529Sdd * above min() for why this is so useless. 30380529Sdd */ 30480529Sddvoid 305189092Sedmp_mout(const MINT *mp) 30680529Sdd{ 30780529Sdd char *s; 30880529Sdd 30980529Sdd s = _mtod("mout", mp); 31080529Sdd printf("%s", s); 31180529Sdd free(s); 31280529Sdd} 31380529Sdd 31480529Sdd/* 31580529Sdd * Set the value of tmp to the value of smp (i.e., tmp=smp). 31680529Sdd */ 31780529Sddvoid 318189092Sedmp_move(const MINT *smp, MINT *tmp) 31980529Sdd{ 32080529Sdd 32180529Sdd _movem("move", smp, tmp); 32280529Sdd} 32380529Sdd 32480529Sdd 32580529Sdd/* 32680529Sdd * Internal routine to set the value of tmp to that of sbp. 32780529Sdd */ 32880529Sddstatic void 32980529Sdd_moveb(const char *msg, const BIGNUM *sbp, MINT *tmp) 33080529Sdd{ 33180529Sdd 33280529Sdd BN_ERRCHECK(msg, BN_copy(tmp->bn, sbp)); 33380529Sdd} 33480529Sdd 33580529Sdd/* 33680529Sdd * Internal routine to set the value of tmp to that of smp. 33780529Sdd */ 33880529Sddstatic void 33980529Sdd_movem(const char *msg, const MINT *smp, MINT *tmp) 34080529Sdd{ 34180529Sdd 34280529Sdd BN_ERRCHECK(msg, BN_copy(tmp->bn, smp->bn)); 34380529Sdd} 34480529Sdd 34580529Sdd/* 34680529Sdd * Compute the square root of nmp and put the result in xmp. The 34780529Sdd * remainder goes in rmp. Should satisfy: rmp=nmp-(xmp*xmp). 34880529Sdd * 34980529Sdd * Note that the OpenSSL BIGNUM library does not have a square root 35080529Sdd * function, so this had to be implemented by hand using Newton's 35180529Sdd * recursive formula: 35280529Sdd * 35380529Sdd * x = (x + (n / x)) / 2 35480529Sdd * 35580529Sdd * where x is the square root of the positive number n. In the 35680529Sdd * beginning, x should be a reasonable guess, but the value 1, 35780529Sdd * although suboptimal, works, too; this is that is used below. 35880529Sdd */ 35980529Sddvoid 360189092Sedmp_msqrt(const MINT *nmp, MINT *xmp, MINT *rmp) 36180529Sdd{ 362160840Ssimon BN_CTX *c; 36380529Sdd MINT *tolerance; 36480529Sdd MINT *ox, *x; 36580529Sdd MINT *z1, *z2, *z3; 36680529Sdd short i; 36780529Sdd 368160840Ssimon c = BN_CTX_new(); 369160840Ssimon if (c == NULL) 370160840Ssimon _bnerr("msqrt"); 37180529Sdd tolerance = _itom("msqrt", 1); 37280529Sdd x = _itom("msqrt", 1); 37380529Sdd ox = _itom("msqrt", 0); 37480529Sdd z1 = _itom("msqrt", 0); 37580529Sdd z2 = _itom("msqrt", 0); 37680529Sdd z3 = _itom("msqrt", 0); 37780529Sdd do { 37880529Sdd _movem("msqrt", x, ox); 379160840Ssimon _mdiv("msqrt", nmp, x, z1, z2, c); 38080529Sdd _madd("msqrt", x, z1, z2); 381160840Ssimon _sdiv("msqrt", z2, 2, x, &i, c); 38280529Sdd _msub("msqrt", ox, x, z3); 38380529Sdd } while (_mcmpa("msqrt", z3, tolerance) == 1); 38480529Sdd _movem("msqrt", x, xmp); 385160840Ssimon _mult("msqrt", x, x, z1, c); 38680529Sdd _msub("msqrt", nmp, z1, z2); 38780529Sdd _movem("msqrt", z2, rmp); 38880529Sdd _mfree("msqrt", tolerance); 38980529Sdd _mfree("msqrt", ox); 39080529Sdd _mfree("msqrt", x); 39180529Sdd _mfree("msqrt", z1); 39280529Sdd _mfree("msqrt", z2); 39380529Sdd _mfree("msqrt", z3); 394160840Ssimon BN_CTX_free(c); 39580529Sdd} 39680529Sdd 39780529Sdd/* 39880529Sdd * Compute rmp=mp1-mp2. 39980529Sdd */ 40080529Sddstatic void 40180529Sdd_msub(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp) 40280529Sdd{ 40380529Sdd BIGNUM b; 40480529Sdd 40580529Sdd BN_init(&b); 40680529Sdd BN_ERRCHECK(msg, BN_sub(&b, mp1->bn, mp2->bn)); 40780529Sdd _moveb(msg, &b, rmp); 40880529Sdd BN_free(&b); 40980529Sdd} 41080529Sdd 41180529Sddvoid 412189092Sedmp_msub(const MINT *mp1, const MINT *mp2, MINT *rmp) 41380529Sdd{ 41480529Sdd 41580529Sdd _msub("msub", mp1, mp2, rmp); 41680529Sdd} 41780529Sdd 41880529Sdd/* 41980529Sdd * Return a decimal representation of mp. Return value must be 42080529Sdd * free()'d. 42180529Sdd */ 42280529Sddstatic char * 42380529Sdd_mtod(const char *msg, const MINT *mp) 42480529Sdd{ 42580529Sdd char *s, *s2; 42680529Sdd 42780529Sdd s = BN_bn2dec(mp->bn); 42880529Sdd if (s == NULL) 42980529Sdd _bnerr(msg); 43080529Sdd asprintf(&s2, "%s", s); 43180529Sdd if (s2 == NULL) 43280529Sdd MPERR(("%s", msg)); 43380529Sdd OPENSSL_free(s); 43480529Sdd return (s2); 43580529Sdd} 43680529Sdd 43780529Sdd/* 43880529Sdd * Return a hexadecimal representation of mp. Return value must be 43980529Sdd * free()'d. 44080529Sdd */ 44180529Sddstatic char * 44280529Sdd_mtox(const char *msg, const MINT *mp) 44380529Sdd{ 44480529Sdd char *p, *s, *s2; 44580529Sdd int len; 44680529Sdd 44780529Sdd s = BN_bn2hex(mp->bn); 44880529Sdd if (s == NULL) 44980529Sdd _bnerr(msg); 45080529Sdd asprintf(&s2, "%s", s); 45180529Sdd if (s2 == NULL) 45280529Sdd MPERR(("%s", msg)); 45380529Sdd OPENSSL_free(s); 45480529Sdd 45580529Sdd /* 45680529Sdd * This is a kludge for libgmp compatibility. The latter's 45780529Sdd * implementation of this function returns lower-case letters, 45880529Sdd * but BN_bn2hex returns upper-case. Some programs (e.g., 45980529Sdd * newkey(1)) are sensitive to this. Although it's probably 46080529Sdd * their fault, it's nice to be compatible. 46180529Sdd */ 46280529Sdd len = strlen(s2); 46380529Sdd for (p = s2; p < s2 + len; p++) 46480529Sdd *p = tolower(*p); 46580529Sdd 46680529Sdd return (s2); 46780529Sdd} 46880529Sdd 46980529Sddchar * 470189092Sedmp_mtox(const MINT *mp) 47180529Sdd{ 47280529Sdd 47380529Sdd return (_mtox("mtox", mp)); 47480529Sdd} 47580529Sdd 47680529Sdd/* 47780529Sdd * Compute rmp=mp1*mp2. 47880529Sdd */ 47980529Sddstatic void 480160840Ssimon_mult(const char *msg, const MINT *mp1, const MINT *mp2, MINT *rmp, BN_CTX *c) 48180529Sdd{ 48280529Sdd BIGNUM b; 48380529Sdd 48480529Sdd BN_init(&b); 485160805Ssimon BN_ERRCHECK(msg, BN_mul(&b, mp1->bn, mp2->bn, c)); 48680529Sdd _moveb(msg, &b, rmp); 48780529Sdd BN_free(&b); 48880529Sdd} 48980529Sdd 49080529Sddvoid 491189092Sedmp_mult(const MINT *mp1, const MINT *mp2, MINT *rmp) 49280529Sdd{ 493160840Ssimon BN_CTX *c; 49480529Sdd 495160840Ssimon c = BN_CTX_new(); 496160840Ssimon if (c == NULL) 497160840Ssimon _bnerr("mult"); 498160840Ssimon _mult("mult", mp1, mp2, rmp, c); 499160840Ssimon BN_CTX_free(c); 50080529Sdd} 50180529Sdd 50280529Sdd/* 50380529Sdd * Compute rmp=(bmp^emp)mod mmp. (Note that here and above rpow() '^' 50480529Sdd * means 'raise to power', not 'bitwise XOR'.) 50580529Sdd */ 50680529Sddvoid 507189092Sedmp_pow(const MINT *bmp, const MINT *emp, const MINT *mmp, MINT *rmp) 50880529Sdd{ 50980529Sdd BIGNUM b; 510160805Ssimon BN_CTX *c; 51180529Sdd 512160805Ssimon c = BN_CTX_new(); 513160805Ssimon if (c == NULL) 514160805Ssimon _bnerr("pow"); 51580529Sdd BN_init(&b); 516160805Ssimon BN_ERRCHECK("pow", BN_mod_exp(&b, bmp->bn, emp->bn, mmp->bn, c)); 51780529Sdd _moveb("pow", &b, rmp); 51880529Sdd BN_free(&b); 519160805Ssimon BN_CTX_free(c); 52080529Sdd} 52180529Sdd 52280529Sdd/* 52380529Sdd * Compute rmp=bmp^e. (See note above pow().) 52480529Sdd */ 52580529Sddvoid 526189092Sedmp_rpow(const MINT *bmp, short e, MINT *rmp) 52780529Sdd{ 52880529Sdd MINT *emp; 52980529Sdd BIGNUM b; 530160805Ssimon BN_CTX *c; 53180529Sdd 532160805Ssimon c = BN_CTX_new(); 533160805Ssimon if (c == NULL) 534160805Ssimon _bnerr("rpow"); 53580529Sdd BN_init(&b); 53680529Sdd emp = _itom("rpow", e); 537160805Ssimon BN_ERRCHECK("rpow", BN_exp(&b, bmp->bn, emp->bn, c)); 53880529Sdd _moveb("rpow", &b, rmp); 53980529Sdd _mfree("rpow", emp); 54080529Sdd BN_free(&b); 541160805Ssimon BN_CTX_free(c); 54280529Sdd} 54380529Sdd 54480529Sdd/* 54580529Sdd * Compute qmp=nmp/d and ro=nmp%d. 54680529Sdd */ 54780529Sddstatic void 548160840Ssimon_sdiv(const char *msg, const MINT *nmp, short d, MINT *qmp, short *ro, 549160840Ssimon BN_CTX *c) 55080529Sdd{ 55180529Sdd MINT *dmp, *rmp; 55280529Sdd BIGNUM q, r; 55380529Sdd char *s; 55480529Sdd 55580529Sdd BN_init(&q); 55680529Sdd BN_init(&r); 55780529Sdd dmp = _itom(msg, d); 55880529Sdd rmp = _itom(msg, 0); 559160805Ssimon BN_ERRCHECK(msg, BN_div(&q, &r, nmp->bn, dmp->bn, c)); 56080529Sdd _moveb(msg, &q, qmp); 56180529Sdd _moveb(msg, &r, rmp); 56280529Sdd s = _mtox(msg, rmp); 56380529Sdd errno = 0; 56480529Sdd *ro = strtol(s, NULL, 16); 56580529Sdd if (errno != 0) 56680529Sdd MPERR(("%s underflow or overflow", msg)); 56780529Sdd free(s); 56880529Sdd _mfree(msg, dmp); 56980529Sdd _mfree(msg, rmp); 57080529Sdd BN_free(&r); 57180529Sdd BN_free(&q); 57280529Sdd} 57380529Sdd 57480529Sddvoid 575189092Sedmp_sdiv(const MINT *nmp, short d, MINT *qmp, short *ro) 57680529Sdd{ 577160840Ssimon BN_CTX *c; 57880529Sdd 579160840Ssimon c = BN_CTX_new(); 580160840Ssimon if (c == NULL) 581160840Ssimon _bnerr("sdiv"); 582160840Ssimon _sdiv("sdiv", nmp, d, qmp, ro, c); 583160840Ssimon BN_CTX_free(c); 58480529Sdd} 58580529Sdd 58680529Sdd/* 58780529Sdd * Convert a hexadecimal string to an MINT. 58880529Sdd */ 58980529Sddstatic MINT * 59080529Sdd_xtom(const char *msg, const char *s) 59180529Sdd{ 59280529Sdd MINT *mp; 59380529Sdd 59480529Sdd mp = malloc(sizeof(*mp)); 59580529Sdd if (mp == NULL) 59680529Sdd MPERR(("%s", msg)); 59780529Sdd mp->bn = BN_new(); 59880529Sdd if (mp->bn == NULL) 59980529Sdd _bnerr(msg); 60080529Sdd BN_ERRCHECK(msg, BN_hex2bn(&mp->bn, s)); 60180529Sdd return (mp); 60280529Sdd} 60380529Sdd 60480529SddMINT * 605189092Sedmp_xtom(const char *s) 60680529Sdd{ 60780529Sdd 60880529Sdd return (_xtom("xtom", s)); 60980529Sdd} 610