Back to index

lightning-sunbird  0.9+nobinonly
ecl_gf.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  *   Stephen Fung <fungstep@hotmail.com> and
00024  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either the GNU General Public License Version 2 or later (the "GPL"), or
00028  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 #include "mpi.h"
00041 #include "mp_gf2m.h"
00042 #include "ecl-priv.h"
00043 #include "mpi-priv.h"
00044 #include <stdlib.h>
00045 
00046 /* Allocate memory for a new GFMethod object. */
00047 GFMethod *
00048 GFMethod_new()
00049 {
00050        mp_err res = MP_OKAY;
00051        GFMethod *meth;
00052        meth = (GFMethod *) malloc(sizeof(GFMethod));
00053        if (meth == NULL)
00054               return NULL;
00055        meth->constructed = MP_YES;
00056        MP_DIGITS(&meth->irr) = 0;
00057        meth->extra_free = NULL;
00058        MP_CHECKOK(mp_init(&meth->irr));
00059 
00060   CLEANUP:
00061        if (res != MP_OKAY) {
00062               GFMethod_free(meth);
00063               return NULL;
00064        }
00065        return meth;
00066 }
00067 
00068 /* Construct a generic GFMethod for arithmetic over prime fields with
00069  * irreducible irr. */
00070 GFMethod *
00071 GFMethod_consGFp(const mp_int *irr)
00072 {
00073        mp_err res = MP_OKAY;
00074        GFMethod *meth = NULL;
00075 
00076        meth = GFMethod_new();
00077        if (meth == NULL)
00078               return NULL;
00079 
00080        MP_CHECKOK(mp_copy(irr, &meth->irr));
00081        meth->irr_arr[0] = mpl_significant_bits(irr);
00082        meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] =
00083               meth->irr_arr[4] = 0;
00084        switch(MP_USED(&meth->irr)) {
00085        /* maybe we need 1 and 2 words here as well?*/
00086        case 3:
00087               meth->field_add = &ec_GFp_add_3;
00088               meth->field_sub = &ec_GFp_sub_3;
00089               break;
00090        case 4:
00091               meth->field_add = &ec_GFp_add_4;
00092               meth->field_sub = &ec_GFp_sub_4;
00093               break;
00094        case 5:
00095               meth->field_add = &ec_GFp_add_5;
00096               meth->field_sub = &ec_GFp_sub_5;
00097               break;
00098        case 6:
00099               meth->field_add = &ec_GFp_add_6;
00100               meth->field_sub = &ec_GFp_sub_6;
00101               break;
00102        default:
00103               meth->field_add = &ec_GFp_add;
00104               meth->field_sub = &ec_GFp_sub;
00105        }
00106        meth->field_neg = &ec_GFp_neg;
00107        meth->field_mod = &ec_GFp_mod;
00108        meth->field_mul = &ec_GFp_mul;
00109        meth->field_sqr = &ec_GFp_sqr;
00110        meth->field_div = &ec_GFp_div;
00111        meth->field_enc = NULL;
00112        meth->field_dec = NULL;
00113        meth->extra1 = NULL;
00114        meth->extra2 = NULL;
00115        meth->extra_free = NULL;
00116 
00117   CLEANUP:
00118        if (res != MP_OKAY) {
00119               GFMethod_free(meth);
00120               return NULL;
00121        }
00122        return meth;
00123 }
00124 
00125 /* Construct a generic GFMethod for arithmetic over binary polynomial
00126  * fields with irreducible irr that has array representation irr_arr (see
00127  * ecl-priv.h for description of the representation).  If irr_arr is NULL, 
00128  * then it is constructed from the bitstring representation. */
00129 GFMethod *
00130 GFMethod_consGF2m(const mp_int *irr, const unsigned int irr_arr[5])
00131 {
00132        mp_err res = MP_OKAY;
00133        int ret;
00134        GFMethod *meth = NULL;
00135 
00136        meth = GFMethod_new();
00137        if (meth == NULL)
00138               return NULL;
00139 
00140        MP_CHECKOK(mp_copy(irr, &meth->irr));
00141        if (irr_arr != NULL) {
00142               /* Irreducible polynomials are either trinomials or pentanomials. */
00143               meth->irr_arr[0] = irr_arr[0];
00144               meth->irr_arr[1] = irr_arr[1];
00145               meth->irr_arr[2] = irr_arr[2];
00146               if (irr_arr[2] > 0) {
00147                      meth->irr_arr[3] = irr_arr[3];
00148                      meth->irr_arr[4] = irr_arr[4];
00149               } else {
00150                      meth->irr_arr[3] = meth->irr_arr[4] = 0;
00151               }
00152        } else {
00153               ret = mp_bpoly2arr(irr, meth->irr_arr, 5);
00154               /* Irreducible polynomials are either trinomials or pentanomials. */
00155               if ((ret != 5) && (ret != 3)) {
00156                      res = MP_UNDEF;
00157                      goto CLEANUP;
00158               }
00159        }
00160        meth->field_add = &ec_GF2m_add;
00161        meth->field_neg = &ec_GF2m_neg;
00162        meth->field_sub = &ec_GF2m_add;
00163        meth->field_mod = &ec_GF2m_mod;
00164        meth->field_mul = &ec_GF2m_mul;
00165        meth->field_sqr = &ec_GF2m_sqr;
00166        meth->field_div = &ec_GF2m_div;
00167        meth->field_enc = NULL;
00168        meth->field_dec = NULL;
00169        meth->extra1 = NULL;
00170        meth->extra2 = NULL;
00171        meth->extra_free = NULL;
00172 
00173   CLEANUP:
00174        if (res != MP_OKAY) {
00175               GFMethod_free(meth);
00176               return NULL;
00177        }
00178        return meth;
00179 }
00180 
00181 /* Free the memory allocated (if any) to a GFMethod object. */
00182 void
00183 GFMethod_free(GFMethod *meth)
00184 {
00185        if (meth == NULL)
00186               return;
00187        if (meth->constructed == MP_NO)
00188               return;
00189        mp_clear(&meth->irr);
00190        if (meth->extra_free != NULL)
00191               meth->extra_free(meth);
00192        free(meth);
00193 }
00194 
00195 /* Wrapper functions for generic prime field arithmetic. */
00196 
00197 /* Add two field elements.  Assumes that 0 <= a, b < meth->irr */
00198 mp_err
00199 ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
00200                  const GFMethod *meth)
00201 {
00202        /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */
00203        mp_err res;
00204 
00205        if ((res = mp_add(a, b, r)) != MP_OKAY) {
00206               return res;
00207        }
00208        if (mp_cmp(r, &meth->irr) >= 0) {
00209               return mp_sub(r, &meth->irr, r);
00210        }
00211        return res;
00212 }
00213 
00214 /* Negates a field element.  Assumes that 0 <= a < meth->irr */
00215 mp_err
00216 ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
00217 {
00218        /* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */
00219 
00220        if (mp_cmp_z(a) == 0) {
00221               mp_zero(r);
00222               return MP_OKAY;
00223        }
00224        return mp_sub(&meth->irr, a, r);
00225 }
00226 
00227 /* Subtracts two field elements.  Assumes that 0 <= a, b < meth->irr */
00228 mp_err
00229 ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
00230                  const GFMethod *meth)
00231 {
00232        mp_err res = MP_OKAY;
00233 
00234        /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */
00235        res = mp_sub(a, b, r);
00236        if (res == MP_RANGE) {
00237               MP_CHECKOK(mp_sub(b, a, r));
00238               if (mp_cmp_z(r) < 0) {
00239                      MP_CHECKOK(mp_add(r, &meth->irr, r));
00240               }
00241               MP_CHECKOK(ec_GFp_neg(r, r, meth));
00242        }
00243        if (mp_cmp_z(r) < 0) {
00244               MP_CHECKOK(mp_add(r, &meth->irr, r));
00245        }
00246   CLEANUP:
00247        return res;
00248 }
00249 /* 
00250  * Inline adds for small curve lengths.
00251  */
00252 /* 3 words */
00253 mp_err
00254 ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r, 
00255                      const GFMethod *meth)
00256 {
00257        mp_err res = MP_OKAY;
00258        mp_digit a0 = 0, a1 = 0, a2 = 0;
00259        mp_digit r0 = 0, r1 = 0, r2 = 0;
00260        mp_digit carry;
00261 
00262        switch(MP_USED(a)) {
00263        case 3:
00264               a2 = MP_DIGIT(a,2);
00265        case 2:
00266               a1 = MP_DIGIT(a,1);
00267        case 1:
00268               a0 = MP_DIGIT(a,0);
00269        }
00270        switch(MP_USED(b)) {
00271        case 3:
00272               r2 = MP_DIGIT(b,2);
00273        case 2:
00274               r1 = MP_DIGIT(b,1);
00275        case 1:
00276               r0 = MP_DIGIT(b,0);
00277        }
00278 
00279 #ifndef MPI_AMD64_ADD
00280        MP_ADD_CARRY(a0, r0, r0, 0,     carry);
00281        MP_ADD_CARRY(a1, r1, r1, carry, carry);
00282        MP_ADD_CARRY(a2, r2, r2, carry, carry);
00283 #else
00284        __asm__ (
00285                 "xorq   %3,%3           \n\t"
00286                 "addq   %4,%0           \n\t"
00287                 "adcq   %5,%1           \n\t"
00288                 "adcq   %6,%2           \n\t"
00289                 "adcq   $0,%3           \n\t"
00290                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
00291                 : "r" (a0), "r" (a1), "r" (a2),
00292                 "0" (r0), "1" (r1), "2" (r2)
00293                 : "%cc" );
00294 #endif
00295 
00296        MP_CHECKOK(s_mp_pad(r, 3));
00297        MP_DIGIT(r, 2) = r2;
00298        MP_DIGIT(r, 1) = r1;
00299        MP_DIGIT(r, 0) = r0;
00300        MP_SIGN(r) = MP_ZPOS;
00301        MP_USED(r) = 3;
00302 
00303        /* Do quick 'subract' if we've gone over 
00304         * (add the 2's complement of the curve field) */
00305         a2 = MP_DIGIT(&meth->irr,2);
00306        if (carry ||  r2 >  a2 ||
00307               ((r2 == a2) && mp_cmp(r,&meth->irr) != MP_LT)) {
00308               a1 = MP_DIGIT(&meth->irr,1);
00309               a0 = MP_DIGIT(&meth->irr,0);
00310 #ifndef MPI_AMD64_ADD
00311               MP_SUB_BORROW(r0, a0, r0, 0,     carry);
00312               MP_SUB_BORROW(r1, a1, r1, carry, carry);
00313               MP_SUB_BORROW(r2, a2, r2, carry, carry);
00314 #else
00315               __asm__ (
00316                      "subq   %3,%0           \n\t"
00317                      "sbbq   %4,%1           \n\t"
00318                      "sbbq   %5,%2           \n\t"
00319                      : "=r"(r0), "=r"(r1), "=r"(r2)
00320                      : "r" (a0), "r" (a1), "r" (a2),
00321                        "0" (r0), "1" (r1), "2" (r2)
00322                      : "%cc" );
00323 #endif
00324               MP_DIGIT(r, 2) = r2;
00325               MP_DIGIT(r, 1) = r1;
00326               MP_DIGIT(r, 0) = r0;
00327        }
00328        
00329        s_mp_clamp(r);
00330 
00331   CLEANUP:
00332        return res;
00333 }
00334 
00335 /* 4 words */
00336 mp_err
00337 ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r, 
00338                      const GFMethod *meth)
00339 {
00340        mp_err res = MP_OKAY;
00341        mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0;
00342        mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
00343        mp_digit carry;
00344 
00345        switch(MP_USED(a)) {
00346        case 4:
00347               a3 = MP_DIGIT(a,3);
00348        case 3:
00349               a2 = MP_DIGIT(a,2);
00350        case 2:
00351               a1 = MP_DIGIT(a,1);
00352        case 1:
00353               a0 = MP_DIGIT(a,0);
00354        }
00355        switch(MP_USED(b)) {
00356        case 4:
00357               r3 = MP_DIGIT(b,3);
00358        case 3:
00359               r2 = MP_DIGIT(b,2);
00360        case 2:
00361               r1 = MP_DIGIT(b,1);
00362        case 1:
00363               r0 = MP_DIGIT(b,0);
00364        }
00365 
00366 #ifndef MPI_AMD64_ADD
00367        MP_ADD_CARRY(a0, r0, r0, 0,     carry);
00368        MP_ADD_CARRY(a1, r1, r1, carry, carry);
00369        MP_ADD_CARRY(a2, r2, r2, carry, carry);
00370        MP_ADD_CARRY(a3, r3, r3, carry, carry);
00371 #else
00372        __asm__ (
00373                 "xorq   %4,%4           \n\t"
00374                 "addq   %5,%0           \n\t"
00375                 "adcq   %6,%1           \n\t"
00376                 "adcq   %7,%2           \n\t"
00377                 "adcq   %8,%3           \n\t"
00378                 "adcq   $0,%4           \n\t"
00379                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry)
00380                 : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
00381                 "0" (r0), "1" (r1), "2" (r2), "3" (r3)
00382                 : "%cc" );
00383 #endif
00384 
00385        MP_CHECKOK(s_mp_pad(r, 4));
00386        MP_DIGIT(r, 3) = r3;
00387        MP_DIGIT(r, 2) = r2;
00388        MP_DIGIT(r, 1) = r1;
00389        MP_DIGIT(r, 0) = r0;
00390        MP_SIGN(r) = MP_ZPOS;
00391        MP_USED(r) = 4;
00392 
00393        /* Do quick 'subract' if we've gone over 
00394         * (add the 2's complement of the curve field) */
00395         a3 = MP_DIGIT(&meth->irr,3);
00396        if (carry ||  r3 >  a3 ||
00397               ((r3 == a3) && mp_cmp(r,&meth->irr) != MP_LT)) {
00398               a2 = MP_DIGIT(&meth->irr,2);
00399               a1 = MP_DIGIT(&meth->irr,1);
00400               a0 = MP_DIGIT(&meth->irr,0);
00401 #ifndef MPI_AMD64_ADD
00402               MP_SUB_BORROW(r0, a0, r0, 0,     carry);
00403               MP_SUB_BORROW(r1, a1, r1, carry, carry);
00404               MP_SUB_BORROW(r2, a2, r2, carry, carry);
00405               MP_SUB_BORROW(r3, a3, r3, carry, carry);
00406 #else
00407               __asm__ (
00408                      "subq   %4,%0           \n\t"
00409                      "sbbq   %5,%1           \n\t"
00410                      "sbbq   %6,%2           \n\t"
00411                      "sbbq   %7,%3           \n\t"
00412                      : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
00413                      : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
00414                        "0" (r0), "1" (r1), "2" (r2), "3" (r3)
00415                      : "%cc" );
00416 #endif
00417               MP_DIGIT(r, 3) = r3;
00418               MP_DIGIT(r, 2) = r2;
00419               MP_DIGIT(r, 1) = r1;
00420               MP_DIGIT(r, 0) = r0;
00421        }
00422        
00423        s_mp_clamp(r);
00424 
00425   CLEANUP:
00426        return res;
00427 }
00428 
00429 /* 5 words */
00430 mp_err
00431 ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r, 
00432                      const GFMethod *meth)
00433 {
00434        mp_err res = MP_OKAY;
00435        mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0;
00436        mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
00437        mp_digit carry;
00438 
00439        switch(MP_USED(a)) {
00440        case 5:
00441               a4 = MP_DIGIT(a,4);
00442        case 4:
00443               a3 = MP_DIGIT(a,3);
00444        case 3:
00445               a2 = MP_DIGIT(a,2);
00446        case 2:
00447               a1 = MP_DIGIT(a,1);
00448        case 1:
00449               a0 = MP_DIGIT(a,0);
00450        }
00451        switch(MP_USED(b)) {
00452        case 5:
00453               r4 = MP_DIGIT(b,4);
00454        case 4:
00455               r3 = MP_DIGIT(b,3);
00456        case 3:
00457               r2 = MP_DIGIT(b,2);
00458        case 2:
00459               r1 = MP_DIGIT(b,1);
00460        case 1:
00461               r0 = MP_DIGIT(b,0);
00462        }
00463 
00464        MP_ADD_CARRY(a0, r0, r0, 0,     carry);
00465        MP_ADD_CARRY(a1, r1, r1, carry, carry);
00466        MP_ADD_CARRY(a2, r2, r2, carry, carry);
00467        MP_ADD_CARRY(a3, r3, r3, carry, carry);
00468        MP_ADD_CARRY(a4, r4, r4, carry, carry);
00469 
00470        MP_CHECKOK(s_mp_pad(r, 5));
00471        MP_DIGIT(r, 4) = r4;
00472        MP_DIGIT(r, 3) = r3;
00473        MP_DIGIT(r, 2) = r2;
00474        MP_DIGIT(r, 1) = r1;
00475        MP_DIGIT(r, 0) = r0;
00476        MP_SIGN(r) = MP_ZPOS;
00477        MP_USED(r) = 5;
00478 
00479        /* Do quick 'subract' if we've gone over 
00480         * (add the 2's complement of the curve field) */
00481         a4 = MP_DIGIT(&meth->irr,4);
00482        if (carry ||  r4 >  a4 ||
00483               ((r4 == a4) && mp_cmp(r,&meth->irr) != MP_LT)) {
00484               a3 = MP_DIGIT(&meth->irr,3);
00485               a2 = MP_DIGIT(&meth->irr,2);
00486               a1 = MP_DIGIT(&meth->irr,1);
00487               a0 = MP_DIGIT(&meth->irr,0);
00488               MP_SUB_BORROW(r0, a0, r0, 0,     carry);
00489               MP_SUB_BORROW(r1, a1, r1, carry, carry);
00490               MP_SUB_BORROW(r2, a2, r2, carry, carry);
00491               MP_SUB_BORROW(r3, a3, r3, carry, carry);
00492               MP_SUB_BORROW(r4, a4, r4, carry, carry);
00493               MP_DIGIT(r, 4) = r4;
00494               MP_DIGIT(r, 3) = r3;
00495               MP_DIGIT(r, 2) = r2;
00496               MP_DIGIT(r, 1) = r1;
00497               MP_DIGIT(r, 0) = r0;
00498        }
00499        
00500        s_mp_clamp(r);
00501 
00502   CLEANUP:
00503        return res;
00504 }
00505 
00506 /* 6 words */
00507 mp_err
00508 ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r, 
00509                      const GFMethod *meth)
00510 {
00511        mp_err res = MP_OKAY;
00512        mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0;
00513        mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
00514        mp_digit carry;
00515 
00516        switch(MP_USED(a)) {
00517        case 6:
00518               a5 = MP_DIGIT(a,5);
00519        case 5:
00520               a4 = MP_DIGIT(a,4);
00521        case 4:
00522               a3 = MP_DIGIT(a,3);
00523        case 3:
00524               a2 = MP_DIGIT(a,2);
00525        case 2:
00526               a1 = MP_DIGIT(a,1);
00527        case 1:
00528               a0 = MP_DIGIT(a,0);
00529        }
00530        switch(MP_USED(b)) {
00531        case 6:
00532               r5 = MP_DIGIT(b,5);
00533        case 5:
00534               r4 = MP_DIGIT(b,4);
00535        case 4:
00536               r3 = MP_DIGIT(b,3);
00537        case 3:
00538               r2 = MP_DIGIT(b,2);
00539        case 2:
00540               r1 = MP_DIGIT(b,1);
00541        case 1:
00542               r0 = MP_DIGIT(b,0);
00543        }
00544 
00545        MP_ADD_CARRY(a0, r0, r0, 0,     carry);
00546        MP_ADD_CARRY(a1, r1, r1, carry, carry);
00547        MP_ADD_CARRY(a2, r2, r2, carry, carry);
00548        MP_ADD_CARRY(a3, r3, r3, carry, carry);
00549        MP_ADD_CARRY(a4, r4, r4, carry, carry);
00550        MP_ADD_CARRY(a5, r5, r5, carry, carry);
00551 
00552        MP_CHECKOK(s_mp_pad(r, 6));
00553        MP_DIGIT(r, 5) = r5;
00554        MP_DIGIT(r, 4) = r4;
00555        MP_DIGIT(r, 3) = r3;
00556        MP_DIGIT(r, 2) = r2;
00557        MP_DIGIT(r, 1) = r1;
00558        MP_DIGIT(r, 0) = r0;
00559        MP_SIGN(r) = MP_ZPOS;
00560        MP_USED(r) = 6;
00561 
00562        /* Do quick 'subract' if we've gone over 
00563         * (add the 2's complement of the curve field) */
00564        a5 = MP_DIGIT(&meth->irr,5);
00565        if (carry ||  r5 >  a5 ||
00566               ((r5 == a5) && mp_cmp(r,&meth->irr) != MP_LT)) {
00567               a4 = MP_DIGIT(&meth->irr,4);
00568               a3 = MP_DIGIT(&meth->irr,3);
00569               a2 = MP_DIGIT(&meth->irr,2);
00570               a1 = MP_DIGIT(&meth->irr,1);
00571               a0 = MP_DIGIT(&meth->irr,0);
00572               MP_SUB_BORROW(r0, a0, r0, 0,     carry);
00573               MP_SUB_BORROW(r1, a1, r1, carry, carry);
00574               MP_SUB_BORROW(r2, a2, r2, carry, carry);
00575               MP_SUB_BORROW(r3, a3, r3, carry, carry);
00576               MP_SUB_BORROW(r4, a4, r4, carry, carry);
00577               MP_SUB_BORROW(r5, a5, r5, carry, carry);
00578               MP_DIGIT(r, 5) = r5;
00579               MP_DIGIT(r, 4) = r4;
00580               MP_DIGIT(r, 3) = r3;
00581               MP_DIGIT(r, 2) = r2;
00582               MP_DIGIT(r, 1) = r1;
00583               MP_DIGIT(r, 0) = r0;
00584        }
00585        
00586        s_mp_clamp(r);
00587 
00588   CLEANUP:
00589        return res;
00590 }
00591 
00592 /*
00593  * The following subraction functions do in-line subractions based
00594  * on our curve size.
00595  *
00596  * ... 3 words
00597  */
00598 mp_err
00599 ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r, 
00600                      const GFMethod *meth)
00601 {
00602        mp_err res = MP_OKAY;
00603        mp_digit b0 = 0, b1 = 0, b2 = 0;
00604        mp_digit r0 = 0, r1 = 0, r2 = 0;
00605        mp_digit borrow;
00606 
00607        switch(MP_USED(a)) {
00608        case 3:
00609               r2 = MP_DIGIT(a,2);
00610        case 2:
00611               r1 = MP_DIGIT(a,1);
00612        case 1:
00613               r0 = MP_DIGIT(a,0);
00614        }
00615        switch(MP_USED(b)) {
00616        case 3:
00617               b2 = MP_DIGIT(b,2);
00618        case 2:
00619               b1 = MP_DIGIT(b,1);
00620        case 1:
00621               b0 = MP_DIGIT(b,0);
00622        }
00623 
00624 #ifndef MPI_AMD64_ADD
00625        MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
00626        MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
00627        MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
00628 #else
00629        __asm__ (
00630                 "xorq   %3,%3           \n\t"
00631                 "subq   %4,%0           \n\t"
00632                 "sbbq   %5,%1           \n\t"
00633                 "sbbq   %6,%2           \n\t"
00634                 "adcq   $0,%3           \n\t"
00635                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r" (borrow)
00636                 : "r" (b0), "r" (b1), "r" (b2), 
00637                 "0" (r0), "1" (r1), "2" (r2)
00638                 : "%cc" );
00639 #endif
00640 
00641        /* Do quick 'add' if we've gone under 0
00642         * (subtract the 2's complement of the curve field) */
00643        if (borrow) {
00644               b2 = MP_DIGIT(&meth->irr,2);
00645               b1 = MP_DIGIT(&meth->irr,1);
00646               b0 = MP_DIGIT(&meth->irr,0);
00647 #ifndef MPI_AMD64_ADD
00648               MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
00649               MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
00650               MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
00651 #else
00652               __asm__ (
00653                      "addq   %3,%0           \n\t"
00654                      "adcq   %4,%1           \n\t"
00655                      "adcq   %5,%2           \n\t"
00656                      : "=r"(r0), "=r"(r1), "=r"(r2)
00657                      : "r" (b0), "r" (b1), "r" (b2),
00658                        "0" (r0), "1" (r1), "2" (r2)
00659                      : "%cc" );
00660 #endif
00661        }
00662 
00663 #ifdef MPI_AMD64_ADD
00664        /* compiler fakeout? */
00665        if ((r2 == b0) && (r1 == b0) && (r0 == b0)) { 
00666               MP_CHECKOK(s_mp_pad(r, 4));
00667        } 
00668 #endif
00669        MP_CHECKOK(s_mp_pad(r, 3));
00670        MP_DIGIT(r, 2) = r2;
00671        MP_DIGIT(r, 1) = r1;
00672        MP_DIGIT(r, 0) = r0;
00673        MP_SIGN(r) = MP_ZPOS;
00674        MP_USED(r) = 3;
00675        s_mp_clamp(r);
00676 
00677   CLEANUP:
00678        return res;
00679 }
00680 
00681 /* 4 words */
00682 mp_err
00683 ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r, 
00684                      const GFMethod *meth)
00685 {
00686        mp_err res = MP_OKAY;
00687        mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0;
00688        mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
00689        mp_digit borrow;
00690 
00691        switch(MP_USED(a)) {
00692        case 4:
00693               r3 = MP_DIGIT(a,3);
00694        case 3:
00695               r2 = MP_DIGIT(a,2);
00696        case 2:
00697               r1 = MP_DIGIT(a,1);
00698        case 1:
00699               r0 = MP_DIGIT(a,0);
00700        }
00701        switch(MP_USED(b)) {
00702        case 4:
00703               b3 = MP_DIGIT(b,3);
00704        case 3:
00705               b2 = MP_DIGIT(b,2);
00706        case 2:
00707               b1 = MP_DIGIT(b,1);
00708        case 1:
00709               b0 = MP_DIGIT(b,0);
00710        }
00711 
00712 #ifndef MPI_AMD64_ADD
00713        MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
00714        MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
00715        MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
00716        MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
00717 #else
00718        __asm__ (
00719                 "xorq   %4,%4           \n\t"
00720                 "subq   %5,%0           \n\t"
00721                 "sbbq   %6,%1           \n\t"
00722                 "sbbq   %7,%2           \n\t"
00723                 "sbbq   %8,%3           \n\t"
00724                 "adcq   $0,%4           \n\t"
00725                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r" (borrow)
00726                 : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
00727                 "0" (r0), "1" (r1), "2" (r2), "3" (r3)
00728                 : "%cc" );
00729 #endif
00730 
00731        /* Do quick 'add' if we've gone under 0
00732         * (subtract the 2's complement of the curve field) */
00733        if (borrow) {
00734               b3 = MP_DIGIT(&meth->irr,3);
00735               b2 = MP_DIGIT(&meth->irr,2);
00736               b1 = MP_DIGIT(&meth->irr,1);
00737               b0 = MP_DIGIT(&meth->irr,0);
00738 #ifndef MPI_AMD64_ADD
00739               MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
00740               MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
00741               MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
00742               MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
00743 #else
00744               __asm__ (
00745                      "addq   %4,%0           \n\t"
00746                      "adcq   %5,%1           \n\t"
00747                      "adcq   %6,%2           \n\t"
00748                      "adcq   %7,%3           \n\t"
00749                      : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
00750                      : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
00751                        "0" (r0), "1" (r1), "2" (r2), "3" (r3)
00752                      : "%cc" );
00753 #endif
00754        }
00755 #ifdef MPI_AMD64_ADD
00756        /* compiler fakeout? */
00757        if ((r3 == b0) && (r1 == b0) && (r0 == b0)) { 
00758               MP_CHECKOK(s_mp_pad(r, 4));
00759        } 
00760 #endif
00761        MP_CHECKOK(s_mp_pad(r, 4));
00762        MP_DIGIT(r, 3) = r3;
00763        MP_DIGIT(r, 2) = r2;
00764        MP_DIGIT(r, 1) = r1;
00765        MP_DIGIT(r, 0) = r0;
00766        MP_SIGN(r) = MP_ZPOS;
00767        MP_USED(r) = 4;
00768        s_mp_clamp(r);
00769 
00770   CLEANUP:
00771        return res;
00772 }
00773 
00774 /* 5 words */
00775 mp_err
00776 ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r, 
00777                      const GFMethod *meth)
00778 {
00779        mp_err res = MP_OKAY;
00780        mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0;
00781        mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
00782        mp_digit borrow;
00783 
00784        switch(MP_USED(a)) {
00785        case 5:
00786               r4 = MP_DIGIT(a,4);
00787        case 4:
00788               r3 = MP_DIGIT(a,3);
00789        case 3:
00790               r2 = MP_DIGIT(a,2);
00791        case 2:
00792               r1 = MP_DIGIT(a,1);
00793        case 1:
00794               r0 = MP_DIGIT(a,0);
00795        }
00796        switch(MP_USED(b)) {
00797        case 5:
00798               b4 = MP_DIGIT(b,4);
00799        case 4:
00800               b3 = MP_DIGIT(b,3);
00801        case 3:
00802               b2 = MP_DIGIT(b,2);
00803        case 2:
00804               b1 = MP_DIGIT(b,1);
00805        case 1:
00806               b0 = MP_DIGIT(b,0);
00807        }
00808 
00809        MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
00810        MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
00811        MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
00812        MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
00813        MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
00814 
00815        /* Do quick 'add' if we've gone under 0
00816         * (subtract the 2's complement of the curve field) */
00817        if (borrow) {
00818               b4 = MP_DIGIT(&meth->irr,4);
00819               b3 = MP_DIGIT(&meth->irr,3);
00820               b2 = MP_DIGIT(&meth->irr,2);
00821               b1 = MP_DIGIT(&meth->irr,1);
00822               b0 = MP_DIGIT(&meth->irr,0);
00823               MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
00824               MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
00825               MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
00826               MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
00827        }
00828        MP_CHECKOK(s_mp_pad(r, 5));
00829        MP_DIGIT(r, 4) = r4;
00830        MP_DIGIT(r, 3) = r3;
00831        MP_DIGIT(r, 2) = r2;
00832        MP_DIGIT(r, 1) = r1;
00833        MP_DIGIT(r, 0) = r0;
00834        MP_SIGN(r) = MP_ZPOS;
00835        MP_USED(r) = 5;
00836        s_mp_clamp(r);
00837 
00838   CLEANUP:
00839        return res;
00840 }
00841 
00842 /* 6 words */
00843 mp_err
00844 ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r, 
00845                      const GFMethod *meth)
00846 {
00847        mp_err res = MP_OKAY;
00848        mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0;
00849        mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
00850        mp_digit borrow;
00851 
00852        switch(MP_USED(a)) {
00853        case 6:
00854               r5 = MP_DIGIT(a,5);
00855        case 5:
00856               r4 = MP_DIGIT(a,4);
00857        case 4:
00858               r3 = MP_DIGIT(a,3);
00859        case 3:
00860               r2 = MP_DIGIT(a,2);
00861        case 2:
00862               r1 = MP_DIGIT(a,1);
00863        case 1:
00864               r0 = MP_DIGIT(a,0);
00865        }
00866        switch(MP_USED(b)) {
00867        case 6:
00868               b5 = MP_DIGIT(b,5);
00869        case 5:
00870               b4 = MP_DIGIT(b,4);
00871        case 4:
00872               b3 = MP_DIGIT(b,3);
00873        case 3:
00874               b2 = MP_DIGIT(b,2);
00875        case 2:
00876               b1 = MP_DIGIT(b,1);
00877        case 1:
00878               b0 = MP_DIGIT(b,0);
00879        }
00880 
00881        MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
00882        MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
00883        MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
00884        MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
00885        MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
00886        MP_SUB_BORROW(r5, b5, r5, borrow, borrow);
00887 
00888        /* Do quick 'add' if we've gone under 0
00889         * (subtract the 2's complement of the curve field) */
00890        if (borrow) {
00891               b5 = MP_DIGIT(&meth->irr,5);
00892               b4 = MP_DIGIT(&meth->irr,4);
00893               b3 = MP_DIGIT(&meth->irr,3);
00894               b2 = MP_DIGIT(&meth->irr,2);
00895               b1 = MP_DIGIT(&meth->irr,1);
00896               b0 = MP_DIGIT(&meth->irr,0);
00897               MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
00898               MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
00899               MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
00900               MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
00901               MP_ADD_CARRY(b4, r4, r4, borrow, borrow);
00902        }
00903 
00904        MP_CHECKOK(s_mp_pad(r, 6));
00905        MP_DIGIT(r, 5) = r5;
00906        MP_DIGIT(r, 4) = r4;
00907        MP_DIGIT(r, 3) = r3;
00908        MP_DIGIT(r, 2) = r2;
00909        MP_DIGIT(r, 1) = r1;
00910        MP_DIGIT(r, 0) = r0;
00911        MP_SIGN(r) = MP_ZPOS;
00912        MP_USED(r) = 6;
00913        s_mp_clamp(r);
00914 
00915   CLEANUP:
00916        return res;
00917 }
00918 
00919 
00920 /* Reduces an integer to a field element. */
00921 mp_err
00922 ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
00923 {
00924        return mp_mod(a, &meth->irr, r);
00925 }
00926 
00927 /* Multiplies two field elements. */
00928 mp_err
00929 ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
00930                  const GFMethod *meth)
00931 {
00932        return mp_mulmod(a, b, &meth->irr, r);
00933 }
00934 
00935 /* Squares a field element. */
00936 mp_err
00937 ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
00938 {
00939        return mp_sqrmod(a, &meth->irr, r);
00940 }
00941 
00942 /* Divides two field elements. If a is NULL, then returns the inverse of
00943  * b. */
00944 mp_err
00945 ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
00946                  const GFMethod *meth)
00947 {
00948        mp_err res = MP_OKAY;
00949        mp_int t;
00950 
00951        /* If a is NULL, then return the inverse of b, otherwise return a/b. */
00952        if (a == NULL) {
00953               return mp_invmod(b, &meth->irr, r);
00954        } else {
00955               /* MPI doesn't support divmod, so we implement it using invmod and 
00956                * mulmod. */
00957               MP_CHECKOK(mp_init(&t));
00958               MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
00959               MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r));
00960          CLEANUP:
00961               mp_clear(&t);
00962               return res;
00963        }
00964 }
00965 
00966 /* Wrapper functions for generic binary polynomial field arithmetic. */
00967 
00968 /* Adds two field elements. */
00969 mp_err
00970 ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
00971                      const GFMethod *meth)
00972 {
00973        return mp_badd(a, b, r);
00974 }
00975 
00976 /* Negates a field element. Note that for binary polynomial fields, the
00977  * negation of a field element is the field element itself. */
00978 mp_err
00979 ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
00980 {
00981        if (a == r) {
00982               return MP_OKAY;
00983        } else {
00984               return mp_copy(a, r);
00985        }
00986 }
00987 
00988 /* Reduces a binary polynomial to a field element. */
00989 mp_err
00990 ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
00991 {
00992        return mp_bmod(a, meth->irr_arr, r);
00993 }
00994 
00995 /* Multiplies two field elements. */
00996 mp_err
00997 ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
00998                      const GFMethod *meth)
00999 {
01000        return mp_bmulmod(a, b, meth->irr_arr, r);
01001 }
01002 
01003 /* Squares a field element. */
01004 mp_err
01005 ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
01006 {
01007        return mp_bsqrmod(a, meth->irr_arr, r);
01008 }
01009 
01010 /* Divides two field elements. If a is NULL, then returns the inverse of
01011  * b. */
01012 mp_err
01013 ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
01014                      const GFMethod *meth)
01015 {
01016        mp_err res = MP_OKAY;
01017        mp_int t;
01018 
01019        /* If a is NULL, then return the inverse of b, otherwise return a/b. */
01020        if (a == NULL) {
01021               /* The GF(2^m) portion of MPI doesn't support invmod, so we
01022                * compute 1/b. */
01023               MP_CHECKOK(mp_init(&t));
01024               MP_CHECKOK(mp_set_int(&t, 1));
01025               MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r));
01026          CLEANUP:
01027               mp_clear(&t);
01028               return res;
01029        } else {
01030               return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r);
01031        }
01032 }