Back to index

lightning-sunbird  0.9+nobinonly
ecp_192.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 for prime field curves.
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 #include "ecp.h"
00040 #include "mpi.h"
00041 #include "mplogic.h"
00042 #include "mpi-priv.h"
00043 #include <stdlib.h>
00044 
00045 #define ECP192_DIGITS ECL_CURVE_DIGITS(192)
00046 
00047 /* Fast modular reduction for p192 = 2^192 - 2^64 - 1.  a can be r. Uses
00048  * algorithm 7 from Brown, Hankerson, Lopez, Menezes. Software
00049  * Implementation of the NIST Elliptic Curves over Prime Fields. */
00050 mp_err
00051 ec_GFp_nistp192_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
00052 {
00053        mp_err res = MP_OKAY;
00054        mp_size a_used = MP_USED(a);
00055        mp_digit r3;
00056 #ifndef MPI_AMD64_ADD 
00057        mp_digit carry;
00058 #endif
00059 #ifdef ECL_THIRTY_TWO_BIT
00060        mp_digit a5a = 0, a5b = 0, a4a = 0, a4b = 0, a3a = 0, a3b = 0;
00061         mp_digit r0a, r0b, r1a, r1b, r2a, r2b;
00062 #else
00063        mp_digit a5 = 0, a4 = 0, a3 = 0;
00064         mp_digit r0, r1, r2;
00065 #endif
00066 
00067        /* reduction not needed if a is not larger than field size */
00068        if (a_used < ECP192_DIGITS) {
00069               if (a == r) {
00070                      return MP_OKAY;
00071               }
00072               return mp_copy(a, r);
00073        }
00074 
00075        /* for polynomials larger than twice the field size, use regular
00076         * reduction */
00077        if (a_used > ECP192_DIGITS*2) {
00078               MP_CHECKOK(mp_mod(a, &meth->irr, r));
00079        } else {
00080               /* copy out upper words of a */
00081 
00082 #ifdef ECL_THIRTY_TWO_BIT
00083 
00084               /* in all the math below,
00085                * nXb is most signifiant, nXa is least significant */
00086               switch (a_used) {
00087               case 12:
00088                      a5b = MP_DIGIT(a, 11);
00089               case 11:
00090                      a5a = MP_DIGIT(a, 10);
00091               case 10:
00092                      a4b = MP_DIGIT(a, 9);
00093               case 9:
00094                      a4a = MP_DIGIT(a, 8);
00095               case 8:
00096                      a3b = MP_DIGIT(a, 7);
00097               case 7:
00098                      a3a = MP_DIGIT(a, 6);
00099               }
00100 
00101 
00102                 r2b= MP_DIGIT(a, 5);
00103                 r2a= MP_DIGIT(a, 4);
00104                 r1b = MP_DIGIT(a, 3);
00105                 r1a = MP_DIGIT(a, 2);
00106                 r0b = MP_DIGIT(a, 1);
00107                 r0a = MP_DIGIT(a, 0);
00108 
00109               /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */
00110               MP_ADD_CARRY(r0a, a3a, r0a, 0,    carry);
00111               MP_ADD_CARRY(r0b, a3b, r0b, carry, carry);
00112               MP_ADD_CARRY(r1a, a3a, r1a, carry, carry);
00113               MP_ADD_CARRY(r1b, a3b, r1b, carry, carry);
00114               MP_ADD_CARRY(r2a, a4a, r2a, carry, carry);
00115               MP_ADD_CARRY(r2b, a4b, r2b, carry, carry);
00116               r3 = carry; carry = 0;
00117               MP_ADD_CARRY(r0a, a5a, r0a, 0,     carry);
00118               MP_ADD_CARRY(r0b, a5b, r0b, carry, carry);
00119               MP_ADD_CARRY(r1a, a5a, r1a, carry, carry);
00120               MP_ADD_CARRY(r1b, a5b, r1b, carry, carry);
00121               MP_ADD_CARRY(r2a, a5a, r2a, carry, carry);
00122               MP_ADD_CARRY(r2b, a5b, r2b, carry, carry);
00123               r3 += carry; 
00124               MP_ADD_CARRY(r1a, a4a, r1a, 0,     carry);
00125               MP_ADD_CARRY(r1b, a4b, r1b, carry, carry);
00126               MP_ADD_CARRY(r2a,   0, r2a, carry, carry);
00127               MP_ADD_CARRY(r2b,   0, r2b, carry, carry);
00128               r3 += carry;
00129 
00130               /* reduce out the carry */
00131               while (r3) {
00132                      MP_ADD_CARRY(r0a, r3, r0a, 0,     carry);
00133                      MP_ADD_CARRY(r0b,  0, r0b, carry, carry);
00134                      MP_ADD_CARRY(r1a, r3, r1a, carry, carry);
00135                      MP_ADD_CARRY(r1b,  0, r1b, carry, carry);
00136                      MP_ADD_CARRY(r2a,  0, r2a, carry, carry);
00137                      MP_ADD_CARRY(r2b,  0, r2b, carry, carry);
00138                      r3 = carry;
00139               }
00140 
00141               /* check for final reduction */
00142               /*
00143                * our field is 0xffffffffffffffff, 0xfffffffffffffffe,
00144                * 0xffffffffffffffff. That means we can only be over and need
00145                * one more reduction 
00146                *  if r2 == 0xffffffffffffffffff (same as r2+1 == 0) 
00147                *     and
00148                *     r1 == 0xffffffffffffffffff   or
00149                *     r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff
00150                * In all cases, we subtract the field (or add the 2's 
00151                * complement value (1,1,0)).  (r0, r1, r2)
00152                */
00153               if (((r2b == 0xffffffff) && (r2a == 0xffffffff) 
00154                      && (r1b == 0xffffffff) ) &&
00155                         ((r1a == 0xffffffff) || 
00156                          (r1a == 0xfffffffe) && (r0a == 0xffffffff) &&
00157                                    (r0b == 0xffffffff)) ) {
00158                      /* do a quick subtract */
00159                      MP_ADD_CARRY(r0a, 1, r0a, 0, carry);
00160                      r0b += carry;
00161                      r1a = r1b = r2a = r2b = 0;
00162               }
00163 
00164               /* set the lower words of r */
00165               if (a != r) {
00166                      MP_CHECKOK(s_mp_pad(r, 6));
00167               }
00168               MP_DIGIT(r, 5) = r2b;
00169               MP_DIGIT(r, 4) = r2a;
00170               MP_DIGIT(r, 3) = r1b;
00171               MP_DIGIT(r, 2) = r1a;
00172               MP_DIGIT(r, 1) = r0b;
00173               MP_DIGIT(r, 0) = r0a;
00174               MP_USED(r) = 6;
00175 #else
00176               switch (a_used) {
00177               case 6:
00178                      a5 = MP_DIGIT(a, 5);
00179               case 5:
00180                      a4 = MP_DIGIT(a, 4);
00181               case 4:
00182                      a3 = MP_DIGIT(a, 3);
00183               }
00184 
00185                 r2 = MP_DIGIT(a, 2);
00186                 r1 = MP_DIGIT(a, 1);
00187                 r0 = MP_DIGIT(a, 0);
00188 
00189               /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */
00190 #ifndef MPI_AMD64_ADD 
00191               MP_ADD_CARRY(r0, a3, r0, 0,     carry);
00192               MP_ADD_CARRY(r1, a3, r1, carry, carry);
00193               MP_ADD_CARRY(r2, a4, r2, carry, carry);
00194               r3 = carry; 
00195               MP_ADD_CARRY(r0, a5, r0, 0,     carry);
00196               MP_ADD_CARRY(r1, a5, r1, carry, carry);
00197               MP_ADD_CARRY(r2, a5, r2, carry, carry);
00198               r3 += carry; 
00199               MP_ADD_CARRY(r1, a4, r1, 0,     carry);
00200               MP_ADD_CARRY(r2,  0, r2, carry, carry);
00201               r3 += carry;
00202 
00203 #else 
00204                 r2 = MP_DIGIT(a, 2);
00205                 r1 = MP_DIGIT(a, 1);
00206                 r0 = MP_DIGIT(a, 0);
00207 
00208                 /* set the lower words of r */
00209                 __asm__ (
00210                 "xorq   %3,%3           \n\t"
00211                 "addq   %4,%0           \n\t"
00212                 "adcq   %4,%1           \n\t"
00213                 "adcq   %5,%2           \n\t"
00214                 "adcq   $0,%3           \n\t"
00215                 "addq   %6,%0           \n\t"
00216                 "adcq   %6,%1           \n\t"
00217                 "adcq   %6,%2           \n\t"
00218                 "adcq   $0,%3           \n\t"
00219                 "addq   %5,%1           \n\t"
00220                 "adcq   $0,%2           \n\t"
00221                 "adcq   $0,%3           \n\t"
00222                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3), 
00223                 "=r"(a4), "=r"(a5)
00224                 : "0" (r0), "1" (r1), "2" (r2), "3" (r3), 
00225                 "4" (a3), "5" (a4), "6"(a5)
00226                 : "%cc" );
00227 #endif 
00228 
00229               /* reduce out the carry */
00230               while (r3) {
00231 #ifndef MPI_AMD64_ADD
00232                      MP_ADD_CARRY(r0, r3, r0, 0,     carry);
00233                      MP_ADD_CARRY(r1, r3, r1, carry, carry);
00234                      MP_ADD_CARRY(r2,  0, r2, carry, carry);
00235                      r3 = carry;
00236 #else
00237                      a3=r3;
00238                             __asm__ (
00239                      "xorq   %3,%3           \n\t"
00240                      "addq   %4,%0           \n\t"
00241                      "adcq   %4,%1           \n\t"
00242                      "adcq   $0,%2           \n\t"
00243                      "adcq   $0,%3           \n\t"
00244                      : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3)
00245                      : "0" (r0), "1" (r1), "2" (r2), "3" (r3), "4"(a3)
00246                      : "%cc" );
00247 #endif
00248               }
00249 
00250               /* check for final reduction */
00251               /*
00252                * our field is 0xffffffffffffffff, 0xfffffffffffffffe,
00253                * 0xffffffffffffffff. That means we can only be over and need
00254                * one more reduction 
00255                *  if r2 == 0xffffffffffffffffff (same as r2+1 == 0) 
00256                *     and
00257                *     r1 == 0xffffffffffffffffff   or
00258                *     r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff
00259                * In all cases, we subtract the field (or add the 2's 
00260                * complement value (1,1,0)).  (r0, r1, r2)
00261                */
00262               if (r3 || ((r2 == MP_DIGIT_MAX) &&
00263                     ((r1 == MP_DIGIT_MAX) || 
00264                      ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) {
00265                      /* do a quick subtract */
00266                      r0++;
00267                      r1 = r2 = 0;
00268               }
00269               /* set the lower words of r */
00270               if (a != r) {
00271                      MP_CHECKOK(s_mp_pad(r, 3));
00272               }
00273               MP_DIGIT(r, 2) = r2;
00274               MP_DIGIT(r, 1) = r1;
00275               MP_DIGIT(r, 0) = r0;
00276               MP_USED(r) = 3;
00277 #endif
00278        }
00279 
00280   CLEANUP:
00281        return res;
00282 }
00283 
00284 #ifndef ECL_THIRTY_TWO_BIT
00285 /* Compute the sum of 192 bit curves. Do the work in-line since the
00286  * number of words are so small, we don't want to overhead of mp function
00287  * calls.  Uses optimized modular reduction for p192. 
00288  */
00289 mp_err
00290 ec_GFp_nistp192_add(const mp_int *a, const mp_int *b, mp_int *r, 
00291                      const GFMethod *meth)
00292 {
00293        mp_err res = MP_OKAY;
00294        mp_digit a0 = 0, a1 = 0, a2 = 0;
00295        mp_digit r0 = 0, r1 = 0, r2 = 0;
00296        mp_digit carry;
00297 
00298        switch(MP_USED(a)) {
00299        case 3:
00300               a2 = MP_DIGIT(a,2);
00301        case 2:
00302               a1 = MP_DIGIT(a,1);
00303        case 1:
00304               a0 = MP_DIGIT(a,0);
00305        }
00306        switch(MP_USED(b)) {
00307        case 3:
00308               r2 = MP_DIGIT(b,2);
00309        case 2:
00310               r1 = MP_DIGIT(b,1);
00311        case 1:
00312               r0 = MP_DIGIT(b,0);
00313        }
00314 
00315 #ifndef MPI_AMD64_ADD
00316        MP_ADD_CARRY(a0, r0, r0, 0,     carry);
00317        MP_ADD_CARRY(a1, r1, r1, carry, carry);
00318        MP_ADD_CARRY(a2, r2, r2, carry, carry);
00319 #else
00320        __asm__ (
00321                 "xorq   %3,%3           \n\t"
00322                 "addq   %4,%0           \n\t"
00323                 "adcq   %5,%1           \n\t"
00324                 "adcq   %6,%2           \n\t"
00325                 "adcq   $0,%3           \n\t"
00326                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
00327                 : "r" (a0), "r" (a1), "r" (a2), "0" (r0), 
00328                 "1" (r1), "2" (r2)
00329                 : "%cc" );
00330 #endif
00331 
00332        /* Do quick 'subract' if we've gone over 
00333         * (add the 2's complement of the curve field) */
00334        if (carry || ((r2 == MP_DIGIT_MAX) &&
00335                     ((r1 == MP_DIGIT_MAX) || 
00336                      ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) {
00337 #ifndef MPI_AMD64_ADD
00338               MP_ADD_CARRY(r0, 1, r0, 0,     carry);
00339               MP_ADD_CARRY(r1, 1, r1, carry, carry);
00340               MP_ADD_CARRY(r2, 0, r2, carry, carry);
00341 #else
00342               __asm__ (
00343                      "addq   $1,%0           \n\t"
00344                      "adcq   $1,%1           \n\t"
00345                      "adcq   $0,%2           \n\t"
00346                      : "=r"(r0), "=r"(r1), "=r"(r2)
00347                      : "0" (r0), "1" (r1), "2" (r2)
00348                      : "%cc" );
00349 #endif
00350        }
00351 
00352        
00353        MP_CHECKOK(s_mp_pad(r, 3));
00354        MP_DIGIT(r, 2) = r2;
00355        MP_DIGIT(r, 1) = r1;
00356        MP_DIGIT(r, 0) = r0;
00357        MP_SIGN(r) = MP_ZPOS;
00358        MP_USED(r) = 3;
00359        s_mp_clamp(r);
00360 
00361 
00362   CLEANUP:
00363        return res;
00364 }
00365 
00366 /* Compute the diff of 192 bit curves. Do the work in-line since the
00367  * number of words are so small, we don't want to overhead of mp function
00368  * calls.  Uses optimized modular reduction for p192. 
00369  */
00370 mp_err
00371 ec_GFp_nistp192_sub(const mp_int *a, const mp_int *b, mp_int *r, 
00372                      const GFMethod *meth)
00373 {
00374        mp_err res = MP_OKAY;
00375        mp_digit b0 = 0, b1 = 0, b2 = 0;
00376        mp_digit r0 = 0, r1 = 0, r2 = 0;
00377        mp_digit borrow;
00378 
00379        switch(MP_USED(a)) {
00380        case 3:
00381               r2 = MP_DIGIT(a,2);
00382        case 2:
00383               r1 = MP_DIGIT(a,1);
00384        case 1:
00385               r0 = MP_DIGIT(a,0);
00386        }
00387 
00388        switch(MP_USED(b)) {
00389        case 3:
00390               b2 = MP_DIGIT(b,2);
00391        case 2:
00392               b1 = MP_DIGIT(b,1);
00393        case 1:
00394               b0 = MP_DIGIT(b,0);
00395        }
00396 
00397 #ifndef MPI_AMD64_ADD
00398        MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
00399        MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
00400        MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
00401 #else
00402        __asm__ (
00403                 "xorq   %3,%3           \n\t"
00404                 "subq   %4,%0           \n\t"
00405                 "sbbq   %5,%1           \n\t"
00406                 "sbbq   %6,%2           \n\t"
00407                 "adcq   $0,%3           \n\t"
00408                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(borrow)
00409                 : "r" (b0), "r" (b1), "r" (b2), "0" (r0), 
00410                 "1" (r1), "2" (r2)
00411                 : "%cc" );
00412 #endif
00413 
00414        /* Do quick 'add' if we've gone under 0
00415         * (subtract the 2's complement of the curve field) */
00416        if (borrow) {
00417 #ifndef MPI_AMD64_ADD
00418               MP_SUB_BORROW(r0, 1, r0, 0,     borrow);
00419               MP_SUB_BORROW(r1, 1, r1, borrow, borrow);
00420               MP_SUB_BORROW(r2,  0, r2, borrow, borrow);
00421 #else
00422               __asm__ (
00423                      "subq   $1,%0           \n\t"
00424                      "sbbq   $1,%1           \n\t"
00425                      "sbbq   $0,%2           \n\t"
00426                      : "=r"(r0), "=r"(r1), "=r"(r2)
00427                      : "0" (r0), "1" (r1), "2" (r2)
00428                      : "%cc" );
00429 #endif
00430        }
00431 
00432        MP_CHECKOK(s_mp_pad(r, 3));
00433        MP_DIGIT(r, 2) = r2;
00434        MP_DIGIT(r, 1) = r1;
00435        MP_DIGIT(r, 0) = r0;
00436        MP_SIGN(r) = MP_ZPOS;
00437        MP_USED(r) = 3;
00438        s_mp_clamp(r);
00439 
00440   CLEANUP:
00441        return res;
00442 }
00443 
00444 #endif
00445 
00446 /* Compute the square of polynomial a, reduce modulo p192. Store the
00447  * result in r.  r could be a.  Uses optimized modular reduction for p192. 
00448  */
00449 mp_err
00450 ec_GFp_nistp192_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
00451 {
00452        mp_err res = MP_OKAY;
00453 
00454        MP_CHECKOK(mp_sqr(a, r));
00455        MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
00456   CLEANUP:
00457        return res;
00458 }
00459 
00460 /* Compute the product of two polynomials a and b, reduce modulo p192.
00461  * Store the result in r.  r could be a or b; a could be b.  Uses
00462  * optimized modular reduction for p192. */
00463 mp_err
00464 ec_GFp_nistp192_mul(const mp_int *a, const mp_int *b, mp_int *r,
00465                                    const GFMethod *meth)
00466 {
00467        mp_err res = MP_OKAY;
00468 
00469        MP_CHECKOK(mp_mul(a, b, r));
00470        MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
00471   CLEANUP:
00472        return res;
00473 }
00474 
00475 /* Divides two field elements. If a is NULL, then returns the inverse of
00476  * b. */
00477 mp_err
00478 ec_GFp_nistp192_div(const mp_int *a, const mp_int *b, mp_int *r,
00479                  const GFMethod *meth)
00480 {
00481        mp_err res = MP_OKAY;
00482        mp_int t;
00483 
00484        /* If a is NULL, then return the inverse of b, otherwise return a/b. */
00485        if (a == NULL) {
00486               return  mp_invmod(b, &meth->irr, r);
00487        } else {
00488               /* MPI doesn't support divmod, so we implement it using invmod and 
00489                * mulmod. */
00490               MP_CHECKOK(mp_init(&t));
00491               MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
00492               MP_CHECKOK(mp_mul(a, &t, r));
00493               MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
00494          CLEANUP:
00495               mp_clear(&t);
00496               return res;
00497        }
00498 }
00499 
00500 /* Wire in fast field arithmetic and precomputation of base point for
00501  * named curves. */
00502 mp_err
00503 ec_group_set_gfp192(ECGroup *group, ECCurveName name)
00504 {
00505        if (name == ECCurve_NIST_P192) {
00506               group->meth->field_mod = &ec_GFp_nistp192_mod;
00507               group->meth->field_mul = &ec_GFp_nistp192_mul;
00508               group->meth->field_sqr = &ec_GFp_nistp192_sqr;
00509               group->meth->field_div = &ec_GFp_nistp192_div;
00510 #ifndef ECL_THIRTY_TWO_BIT
00511               group->meth->field_add = &ec_GFp_nistp192_add;
00512               group->meth->field_sub = &ec_GFp_nistp192_sub;
00513 #endif
00514        }
00515        return MP_OKAY;
00516 }