bn_gcd.c

RMI的处理器au1200系列所用的BOOTLOAD,包括SD卡启动USB启动硬盘启动网络启动,并初始化硬件的所有参数,支持内核调试.

/* crypto/bn/bn_gcd.c */
/* Copyright (C) 1995-1998 Eric Young ([e-mail])
 * All rights reserved.
 *
 * This package is an SSL implementation written
 * by Eric Young ([e-mail]).
 * The implementation was written so as to conform with Netscapes SSL.
 * 
 * This library is free for commercial and non-commercial use as long as
 * the following conditions are aheared to.  The following conditions
 * apply to all code found in this distribution, be it the RC4, RSA,
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 * included with this distribution is covered by the same copyright terms
 * except that the holder is Tim Hudson ([e-mail]).
 * 
 * Copyright remains Eric Young's, and as such any Copyright notices in
 * the code are not to be removed.
 * If this package is used in a product, Eric Young should be given attribution
 * as the author of the parts of the library used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 * 
 * 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 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.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    "This product includes cryptographic software written by
 *     Eric Young ([e-mail])"
 *    The word 'cryptographic' can be left out if the rouines from the library
 *    being used are not cryptographic related :-).
 * 4. If you include any Windows specific code (or a derivative thereof) from 
 *    the apps directory (application code) you must include an acknowledgement:
 *    "This product includes software written by Tim Hudson ([e-mail])"
 * 
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``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.
 * 
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */

#include <stdio.h>
#include "cryptlib.h"
#include "bn_lcl.h"

#include "workaround.h"

static BIGNUM *euclid(BIGNUM * a, BIGNUM * b);

int BN_gcd(BIGNUM * r, BIGNUM * in_a, BIGNUM * in_b, BN_CTX * ctx)
{
    BIGNUM *a, *b, *t;
    int ret = 0;

    bn_check_top(in_a);
    bn_check_top(in_b);

    BN_CTX_start(ctx);
    a = BN_CTX_get(ctx);
    b = BN_CTX_get(ctx);
    if (a == NULL || b == NULL)
	goto err;

    if (BN_copy(a, in_a) == NULL)
	goto err;
    if (BN_copy(b, in_b) == NULL)
	goto err;

    if (BN_cmp(a, b) < 0) {
	t = a;
	a = b;
	b = t;
    }
    t = euclid(a, b);
    if (t == NULL)
	goto err;

    if (BN_copy(r, t) == NULL)
	goto err;
    ret = 1;
  err:
    BN_CTX_end(ctx);
    return (ret);
}

static BIGNUM *euclid(BIGNUM * a, BIGNUM * b)
{
    BIGNUM *t;
    int shifts = 0;

    bn_check_top(a);
    bn_check_top(b);

    for (;;) {
	if (BN_is_zero(b))
	    break;

	if (BN_is_odd(a)) {
	    if (BN_is_odd(b)) {
		if (!BN_sub(a, a, b))
		    goto err;
		if (!BN_rshift1(a, a))
		    goto err;
		if (BN_cmp(a, b) < 0) {
		    t = a;
		    a = b;
		    b = t;
		}
	    } else {		/* a odd - b even */

		if (!BN_rshift1(b, b))
		    goto err;
		if (BN_cmp(a, b) < 0) {
		    t = a;
		    a = b;
		    b = t;
		}
	    }
	} else {		/* a is even */

	    if (BN_is_odd(b)) {
		if (!BN_rshift1(a, a))
		    goto err;
		if (BN_cmp(a, b) < 0) {
		    t = a;
		    a = b;
		    b = t;
		}
	    } else {		/* a even - b even */

		if (!BN_rshift1(a, a))
		    goto err;
		if (!BN_rshift1(b, b))
		    goto err;
		shifts++;
	    }
	}
    }
    if (shifts) {
	if (!BN_lshift(a, a, shifts))
	    goto err;
    }
    return (a);
  err:
    return (NULL);
}

/* solves ax == 1 (mod n) */
BIGNUM *BN_mod_inverse(BIGNUM * in, BIGNUM * a, const BIGNUM * n,
		       BN_CTX * ctx)
{
    BIGNUM *A, *B, *X, *Y, *M, *D, *R = NULL;
    BIGNUM *T, *ret = NULL;
    int sign;

    bn_check_top(a);
    bn_check_top(n);

    BN_CTX_start(ctx);
    A = BN_CTX_get(ctx);
    B = BN_CTX_get(ctx);
    X = BN_CTX_get(ctx);
    D = BN_CTX_get(ctx);
    M = BN_CTX_get(ctx);
    Y = BN_CTX_get(ctx);
    if (Y == NULL)
	goto err;

    if (in == NULL)
	R = BN_new();
    else
	R = in;
    if (R == NULL)
	goto err;

    if (!BN_zero(X))
	goto err;
    if (!BN_one(Y))
	goto err;
    if (BN_copy(A, a) == NULL)
	goto err;
    if (BN_copy(B, n) == NULL)
	goto err;
    sign = 1;

    while (!BN_is_zero(B)) {
	if (!BN_div(D, M, A, B, ctx))
	    goto err;
	T = A;
	A = B;
	B = M;
	/* T has a struct, M does not */

	if (!BN_mul(T, D, X, ctx))
	    goto err;
	if (!BN_add(T, T, Y))
	    goto err;
	M = Y;
	Y = X;
	X = T;
	sign = -sign;
    }
    if (sign < 0) {
	if (!BN_sub(Y, n, Y))
	    goto err;
    }

    if (BN_is_one(A)) {
	if (!BN_mod(R, Y, n, ctx))
	    goto err;
    } else {
	BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE);
	goto err;
    }
    ret = R;
  err:
    if ((ret == NULL) && (in == NULL))
	BN_free(R);
    BN_CTX_end(ctx);
    return (ret);
}