Back to index

lightning-sunbird  0.9+nobinonly
ecp_mont.c
Go to the documentation of this file.
00001 /* 
00002  * ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the elliptic curve math library.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Sun Microsystems, Inc.
00019  * Portions created by the Initial Developer are Copyright (C) 2003
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 /* Uses Montgomery reduction for field arithmetic.  See mpi/mpmontg.c for
00040  * code implementation. */
00041 
00042 #include "mpi.h"
00043 #include "mplogic.h"
00044 #include "mpi-priv.h"
00045 #include "ecl-priv.h"
00046 #include "ecp.h"
00047 #include <stdlib.h>
00048 #include <stdio.h>
00049 
00050 /* Construct a generic GFMethod for arithmetic over prime fields with
00051  * irreducible irr. */
00052 GFMethod *
00053 GFMethod_consGFp_mont(const mp_int *irr)
00054 {
00055        mp_err res = MP_OKAY;
00056        int i;
00057        GFMethod *meth = NULL;
00058        mp_mont_modulus *mmm;
00059 
00060        meth = GFMethod_consGFp(irr);
00061        if (meth == NULL)
00062               return NULL;
00063 
00064        mmm = (mp_mont_modulus *) malloc(sizeof(mp_mont_modulus));
00065        if (mmm == NULL) {
00066               res = MP_MEM;
00067               goto CLEANUP;
00068        }
00069 
00070        meth->field_mul = &ec_GFp_mul_mont;
00071        meth->field_sqr = &ec_GFp_sqr_mont;
00072        meth->field_div = &ec_GFp_div_mont;
00073        meth->field_enc = &ec_GFp_enc_mont;
00074        meth->field_dec = &ec_GFp_dec_mont;
00075        meth->extra1 = mmm;
00076        meth->extra2 = NULL;
00077        meth->extra_free = &ec_GFp_extra_free_mont;
00078 
00079        mmm->N = meth->irr;
00080        i = mpl_significant_bits(&meth->irr);
00081        i += MP_DIGIT_BIT - 1;
00082        mmm->b = i - i % MP_DIGIT_BIT;
00083        mmm->n0prime = 0 - s_mp_invmod_radix(MP_DIGIT(&meth->irr, 0));
00084 
00085   CLEANUP:
00086        if (res != MP_OKAY) {
00087               GFMethod_free(meth);
00088               return NULL;
00089        }
00090        return meth;
00091 }
00092 
00093 /* Wrapper functions for generic prime field arithmetic. */
00094 
00095 /* Field multiplication using Montgomery reduction. */
00096 mp_err
00097 ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r,
00098                             const GFMethod *meth)
00099 {
00100        mp_err res = MP_OKAY;
00101 
00102 #ifdef MP_MONT_USE_MP_MUL
00103        /* if MP_MONT_USE_MP_MUL is defined, then the function s_mp_mul_mont
00104         * is not implemented and we have to use mp_mul and s_mp_redc directly 
00105         */
00106        MP_CHECKOK(mp_mul(a, b, r));
00107        MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1));
00108 #else
00109        mp_int s;
00110 
00111        MP_DIGITS(&s) = 0;
00112        /* s_mp_mul_mont doesn't allow source and destination to be the same */
00113        if ((a == r) || (b == r)) {
00114               MP_CHECKOK(mp_init(&s));
00115               MP_CHECKOK(s_mp_mul_mont
00116                                (a, b, &s, (mp_mont_modulus *) meth->extra1));
00117               MP_CHECKOK(mp_copy(&s, r));
00118               mp_clear(&s);
00119        } else {
00120               return s_mp_mul_mont(a, b, r, (mp_mont_modulus *) meth->extra1);
00121        }
00122 #endif
00123   CLEANUP:
00124        return res;
00125 }
00126 
00127 /* Field squaring using Montgomery reduction. */
00128 mp_err
00129 ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
00130 {
00131        return ec_GFp_mul_mont(a, a, r, meth);
00132 }
00133 
00134 /* Field division using Montgomery reduction. */
00135 mp_err
00136 ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r,
00137                             const GFMethod *meth)
00138 {
00139        mp_err res = MP_OKAY;
00140 
00141        /* if A=aZ represents a encoded in montgomery coordinates with Z and # 
00142         * and \ respectively represent multiplication and division in
00143         * montgomery coordinates, then A\B = (a/b)Z = (A/B)Z and Binv =
00144         * (1/b)Z = (1/B)(Z^2) where B # Binv = Z */
00145        MP_CHECKOK(ec_GFp_div(a, b, r, meth));
00146        MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
00147        if (a == NULL) {
00148               MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
00149        }
00150   CLEANUP:
00151        return res;
00152 }
00153 
00154 /* Encode a field element in Montgomery form. See s_mp_to_mont in
00155  * mpi/mpmontg.c */
00156 mp_err
00157 ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
00158 {
00159        mp_mont_modulus *mmm;
00160        mp_err res = MP_OKAY;
00161 
00162        mmm = (mp_mont_modulus *) meth->extra1;
00163        MP_CHECKOK(mpl_lsh(a, r, mmm->b));
00164        MP_CHECKOK(mp_mod(r, &mmm->N, r));
00165   CLEANUP:
00166        return res;
00167 }
00168 
00169 /* Decode a field element from Montgomery form. */
00170 mp_err
00171 ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
00172 {
00173        mp_err res = MP_OKAY;
00174 
00175        if (a != r) {
00176               MP_CHECKOK(mp_copy(a, r));
00177        }
00178        MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1));
00179   CLEANUP:
00180        return res;
00181 }
00182 
00183 /* Free the memory allocated to the extra fields of Montgomery GFMethod
00184  * object. */
00185 void
00186 ec_GFp_extra_free_mont(GFMethod *meth)
00187 {
00188        if (meth->extra1 != NULL) {
00189               free(meth->extra1);
00190               meth->extra1 = NULL;
00191        }
00192 }