linux-imx

/* mpi-pow.c  -  MPI functions

 *  Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc.

 *

 * This file is part of GnuPG.

 *

 * GnuPG is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 2 of the License, or

 * (at your option) any later version.

 *

 * GnuPG is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA

 *

 * Note: This code is heavily based on the GNU MP Library.

 *   Actually it's the same code with only minor changes in the

 *   way the data is stored; this is to support the abstraction

 *   of an optional secure memory allocation which may be used

 *   to avoid revealing of sensitive data due to paging etc.

 *   The GNU MP Library itself is published under the LGPL;

 *   however I decided to publish this code under the plain GPL.

 */

​

#include <linux/sched.h>

#include <linux/string.h>

#include "mpi-internal.h"

#include "longlong.h"

​

/****************

 * RES = BASE ^ EXP mod MOD

 */

int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)

{

    mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL;

    mpi_ptr_t xp_marker = NULL;

    mpi_ptr_t tspace = NULL;

    mpi_ptr_t rp, ep, mp, bp;

    mpi_size_t esize, msize, bsize, rsize;

    int msign, bsign, rsign;

    mpi_size_t size;

    int mod_shift_cnt;

    int negative_result;

    int assign_rp = 0;

    mpi_size_t tsize = 0;   /* to avoid compiler warning */

    /* fixme: we should check that the warning is void */

    int rc = -ENOMEM;

​

    esize = exp->nlimbs;

    msize = mod->nlimbs;

    size = 2 * msize;

    msign = mod->sign;

​

    rp = res->d;

    ep = exp->d;

​

    if (!msize)

        return -EINVAL;

​

    if (!esize) {

        /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0

         * depending on if MOD equals 1.  */

        res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;

        if (res->nlimbs) {

            if (mpi_resize(res, 1) < 0)

                goto enomem;

            rp = res->d;

            rp[0] = 1;

        }

        res->sign = 0;

        goto leave;

    }

​

    /* Normalize MOD (i.e. make its most significant bit set) as required by

     * mpn_divrem.  This will make the intermediate values in the calculation

     * slightly larger, but the correct result is obtained after a final

     * reduction using the original MOD value.  */

    mp = mp_marker = mpi_alloc_limb_space(msize);

    if (!mp)

        goto enomem;

    mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);

    if (mod_shift_cnt)

        mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);

    else

        MPN_COPY(mp, mod->d, msize);

​

    bsize = base->nlimbs;

    bsign = base->sign;