Back to index

lightning-sunbird  0.9+nobinonly
ecp_256.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>
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 /* Fast modular reduction for p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1.  a can be r. 
00046  * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to 
00047  * Elliptic Curve Cryptography. */
00048 mp_err
00049 ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
00050 {
00051        mp_err res = MP_OKAY;
00052        mp_size a_used = MP_USED(a);
00053        int a_bits = mpl_significant_bits(a);
00054        mp_digit carry;
00055 
00056 #ifdef ECL_THIRTY_TWO_BIT
00057        mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0;
00058        mp_digit r0, r1, r2, r3, r4, r5, r6, r7;
00059        int r8; /* must be a signed value ! */
00060 #else
00061        mp_digit a4=0, a5=0, a6=0, a7=0;
00062        mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l;
00063        mp_digit r0, r1, r2, r3;
00064        int r4; /* must be a signed value ! */
00065 #endif
00066        /* for polynomials larger than twice the field size 
00067         * use regular reduction */
00068        if (a_bits < 256) {
00069               if (a == r) return MP_OKAY;
00070               return mp_copy(a,r);
00071        }
00072        if (a_bits > 512)  {
00073               MP_CHECKOK(mp_mod(a, &meth->irr, r));
00074        } else {
00075 
00076 #ifdef ECL_THIRTY_TWO_BIT
00077               switch (a_used) {
00078               case 16:
00079                      a15 = MP_DIGIT(a,15);
00080               case 15:
00081                      a14 = MP_DIGIT(a,14);
00082               case 14:
00083                      a13 = MP_DIGIT(a,13);
00084               case 13:
00085                      a12 = MP_DIGIT(a,12);
00086               case 12:
00087                      a11 = MP_DIGIT(a,11);
00088               case 11:
00089                      a10 = MP_DIGIT(a,10);
00090               case 10:
00091                      a9 = MP_DIGIT(a,9);
00092               case 9:
00093                      a8 = MP_DIGIT(a,8);
00094               }
00095 
00096               r0 = MP_DIGIT(a,0);
00097               r1 = MP_DIGIT(a,1);
00098               r2 = MP_DIGIT(a,2);
00099               r3 = MP_DIGIT(a,3);
00100               r4 = MP_DIGIT(a,4);
00101               r5 = MP_DIGIT(a,5);
00102               r6 = MP_DIGIT(a,6);
00103               r7 = MP_DIGIT(a,7);
00104 
00105               /* sum 1 */
00106               MP_ADD_CARRY(r3, a11, r3, 0,     carry);
00107               MP_ADD_CARRY(r4, a12, r4, carry, carry);
00108               MP_ADD_CARRY(r5, a13, r5, carry, carry);
00109               MP_ADD_CARRY(r6, a14, r6, carry, carry);
00110               MP_ADD_CARRY(r7, a15, r7, carry, carry);
00111               r8 = carry;
00112               MP_ADD_CARRY(r3, a11, r3, 0,     carry);
00113               MP_ADD_CARRY(r4, a12, r4, carry, carry);
00114               MP_ADD_CARRY(r5, a13, r5, carry, carry);
00115               MP_ADD_CARRY(r6, a14, r6, carry, carry);
00116               MP_ADD_CARRY(r7, a15, r7, carry, carry);
00117               r8 += carry;
00118               /* sum 2 */
00119               MP_ADD_CARRY(r3, a12, r3, 0,     carry);
00120               MP_ADD_CARRY(r4, a13, r4, carry, carry);
00121               MP_ADD_CARRY(r5, a14, r5, carry, carry);
00122               MP_ADD_CARRY(r6, a15, r6, carry, carry);
00123               MP_ADD_CARRY(r7,   0, r7, carry, carry);
00124               r8 += carry;
00125               /* combine last bottom of sum 3 with second sum 2 */
00126               MP_ADD_CARRY(r0, a8,  r0, 0,     carry);
00127               MP_ADD_CARRY(r1, a9,  r1, carry, carry);
00128               MP_ADD_CARRY(r2, a10, r2, carry, carry);
00129               MP_ADD_CARRY(r3, a12, r3, carry, carry);
00130               MP_ADD_CARRY(r4, a13, r4, carry, carry);
00131               MP_ADD_CARRY(r5, a14, r5, carry, carry);
00132               MP_ADD_CARRY(r6, a15, r6, carry, carry);
00133               MP_ADD_CARRY(r7, a15, r7, carry, carry); /* from sum 3 */
00134               r8 += carry;
00135               /* sum 3 (rest of it)*/
00136               MP_ADD_CARRY(r6, a14, r6, 0,     carry);
00137               MP_ADD_CARRY(r7,   0, r7, carry, carry);
00138               r8 += carry;
00139               /* sum 4 (rest of it)*/
00140               MP_ADD_CARRY(r0, a9,  r0, 0,     carry);
00141               MP_ADD_CARRY(r1, a10, r1, carry, carry);
00142               MP_ADD_CARRY(r2, a11, r2, carry, carry);
00143               MP_ADD_CARRY(r3, a13, r3, carry, carry);
00144               MP_ADD_CARRY(r4, a14, r4, carry, carry);
00145               MP_ADD_CARRY(r5, a15, r5, carry, carry);
00146               MP_ADD_CARRY(r6, a13, r6, carry, carry);
00147               MP_ADD_CARRY(r7, a8,  r7, carry, carry);
00148               r8 += carry;
00149               /* diff 5 */
00150               MP_SUB_BORROW(r0, a11, r0, 0,     carry);
00151               MP_SUB_BORROW(r1, a12, r1, carry, carry);
00152               MP_SUB_BORROW(r2, a13, r2, carry, carry);
00153               MP_SUB_BORROW(r3,   0, r3, carry, carry);
00154               MP_SUB_BORROW(r4,   0, r4, carry, carry);
00155               MP_SUB_BORROW(r5,   0, r5, carry, carry);
00156               MP_SUB_BORROW(r6, a8,  r6, carry, carry);
00157               MP_SUB_BORROW(r7, a10, r7, carry, carry);
00158               r8 -= carry;
00159               /* diff 6 */
00160               MP_SUB_BORROW(r0, a12, r0, 0,     carry);
00161               MP_SUB_BORROW(r1, a13, r1, carry, carry);
00162               MP_SUB_BORROW(r2, a14, r2, carry, carry);
00163               MP_SUB_BORROW(r3, a15, r3, carry, carry);
00164               MP_SUB_BORROW(r4,   0, r4, carry, carry);
00165               MP_SUB_BORROW(r5,   0, r5, carry, carry);
00166               MP_SUB_BORROW(r6, a9,  r6, carry, carry);
00167               MP_SUB_BORROW(r7, a11, r7, carry, carry);
00168               r8 -= carry;
00169               /* diff 7 */
00170               MP_SUB_BORROW(r0, a13, r0, 0,     carry);
00171               MP_SUB_BORROW(r1, a14, r1, carry, carry);
00172               MP_SUB_BORROW(r2, a15, r2, carry, carry);
00173               MP_SUB_BORROW(r3, a8,  r3, carry, carry);
00174               MP_SUB_BORROW(r4, a9,  r4, carry, carry);
00175               MP_SUB_BORROW(r5, a10, r5, carry, carry);
00176               MP_SUB_BORROW(r6, 0,   r6, carry, carry);
00177               MP_SUB_BORROW(r7, a12, r7, carry, carry);
00178               r8 -= carry;
00179               /* diff 8 */
00180               MP_SUB_BORROW(r0, a14, r0, 0,     carry);
00181               MP_SUB_BORROW(r1, a15, r1, carry, carry);
00182               MP_SUB_BORROW(r2, 0,   r2, carry, carry);
00183               MP_SUB_BORROW(r3, a9,  r3, carry, carry);
00184               MP_SUB_BORROW(r4, a10, r4, carry, carry);
00185               MP_SUB_BORROW(r5, a11, r5, carry, carry);
00186               MP_SUB_BORROW(r6, 0,   r6, carry, carry);
00187               MP_SUB_BORROW(r7, a13, r7, carry, carry);
00188               r8 -= carry;
00189 
00190               /* reduce the overflows */
00191               while (r8 > 0) {
00192                      mp_digit r8_d = r8;
00193                      MP_ADD_CARRY(r0, r8_d,         r0, 0,     carry);
00194                      MP_ADD_CARRY(r1, 0,            r1, carry, carry);
00195                      MP_ADD_CARRY(r2, 0,            r2, carry, carry);
00196                      MP_ADD_CARRY(r3, -r8_d,        r3, carry, carry);
00197                      MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry, carry);
00198                      MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry, carry);
00199                      MP_ADD_CARRY(r6, -(r8_d+1),    r6, carry, carry);
00200                      MP_ADD_CARRY(r7, (r8_d-1),     r7, carry, carry);
00201                      r8 = carry;
00202               }
00203 
00204               /* reduce the underflows */
00205               while (r8 < 0) {
00206                      mp_digit r8_d = -r8;
00207                      MP_SUB_BORROW(r0, r8_d,         r0, 0,     carry);
00208                      MP_SUB_BORROW(r1, 0,            r1, carry, carry);
00209                      MP_SUB_BORROW(r2, 0,            r2, carry, carry);
00210                      MP_SUB_BORROW(r3, -r8_d,        r3, carry, carry);
00211                      MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry, carry);
00212                      MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry, carry);
00213                      MP_SUB_BORROW(r6, -(r8_d+1),    r6, carry, carry);
00214                      MP_SUB_BORROW(r7, (r8_d-1),     r7, carry, carry);
00215                      r8 = -carry;
00216               }
00217               if (a != r) {
00218                      MP_CHECKOK(s_mp_pad(r,8));
00219               }
00220               MP_SIGN(r) = MP_ZPOS;
00221               MP_USED(r) = 8;
00222 
00223               MP_DIGIT(r,7) = r7;
00224               MP_DIGIT(r,6) = r6;
00225               MP_DIGIT(r,5) = r5;
00226               MP_DIGIT(r,4) = r4;
00227               MP_DIGIT(r,3) = r3;
00228               MP_DIGIT(r,2) = r2;
00229               MP_DIGIT(r,1) = r1;
00230               MP_DIGIT(r,0) = r0;
00231 
00232               /* final reduction if necessary */
00233               if ((r7 == MP_DIGIT_MAX) &&
00234                      ((r6 > 1) || ((r6 == 1) &&
00235                      (r5 || r4 || r3 || 
00236                             ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX)
00237                               && (r0 == MP_DIGIT_MAX)))))) {
00238                      MP_CHECKOK(mp_sub(r, &meth->irr, r));
00239               }
00240 #ifdef notdef
00241                      
00242 
00243               /* smooth the negatives */
00244               while (MP_SIGN(r) != MP_ZPOS) {
00245                      MP_CHECKOK(mp_add(r, &meth->irr, r));
00246               }
00247               while (MP_USED(r) > 8) {
00248                      MP_CHECKOK(mp_sub(r, &meth->irr, r));
00249               }
00250 
00251               /* final reduction if necessary */
00252               if (MP_DIGIT(r,7) >= MP_DIGIT(&meth->irr,7)) {
00253                   if (mp_cmp(r,&meth->irr) != MP_LT) {
00254                      MP_CHECKOK(mp_sub(r, &meth->irr, r));
00255                   }
00256               }
00257 #endif
00258               s_mp_clamp(r);
00259 #else
00260               switch (a_used) {
00261               case 8:
00262                      a7 = MP_DIGIT(a,7);
00263               case 7:
00264                      a6 = MP_DIGIT(a,6);
00265               case 6:
00266                      a5 = MP_DIGIT(a,5);
00267               case 5:
00268                      a4 = MP_DIGIT(a,4);
00269               }
00270               a7l = a7 << 32;
00271               a7h = a7 >> 32;
00272               a6l = a6 << 32;
00273               a6h = a6 >> 32;
00274               a5l = a5 << 32;
00275               a5h = a5 >> 32;
00276               a4l = a4 << 32;
00277               a4h = a4 >> 32;
00278               r3 = MP_DIGIT(a,3);
00279               r2 = MP_DIGIT(a,2);
00280               r1 = MP_DIGIT(a,1);
00281               r0 = MP_DIGIT(a,0);
00282 
00283               /* sum 1 */
00284               MP_ADD_CARRY(r1, a5h << 32, r1, 0,     carry);
00285               MP_ADD_CARRY(r2, a6,        r2, carry, carry);
00286               MP_ADD_CARRY(r3, a7,        r3, carry, carry);
00287               r4 = carry;
00288               MP_ADD_CARRY(r1, a5h << 32, r1, 0,     carry);
00289               MP_ADD_CARRY(r2, a6,        r2, carry, carry);
00290               MP_ADD_CARRY(r3, a7,        r3, carry, carry);
00291               r4 += carry;
00292               /* sum 2 */
00293               MP_ADD_CARRY(r1, a6l,       r1, 0,     carry);
00294               MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
00295               MP_ADD_CARRY(r3, a7h,       r3, carry, carry);
00296               r4 += carry;
00297               MP_ADD_CARRY(r1, a6l,       r1, 0,     carry);
00298               MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
00299               MP_ADD_CARRY(r3, a7h,       r3, carry, carry);
00300               r4 += carry;
00301 
00302               /* sum 3 */
00303               MP_ADD_CARRY(r0, a4,        r0, 0,     carry);
00304               MP_ADD_CARRY(r1, a5l >> 32, r1, carry, carry);
00305               MP_ADD_CARRY(r2, 0,         r2, carry, carry);
00306               MP_ADD_CARRY(r3, a7,        r3, carry, carry);
00307               r4 += carry;
00308               /* sum 4 */
00309               MP_ADD_CARRY(r0, a4h | a5l,     r0, 0,     carry);
00310               MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry, carry);
00311               MP_ADD_CARRY(r2, a7,            r2, carry, carry);
00312               MP_ADD_CARRY(r3, a6h | a4l,     r3, carry, carry);
00313               r4 += carry;
00314               /* diff 5 */
00315               MP_SUB_BORROW(r0, a5h | a6l,    r0, 0,     carry);
00316               MP_SUB_BORROW(r1, a6h,          r1, carry, carry);
00317               MP_SUB_BORROW(r2, 0,            r2, carry, carry);
00318               MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry, carry);
00319               r4 -= carry;
00320               /* diff 6 */
00321               MP_SUB_BORROW(r0, a6,              r0, 0,     carry);
00322               MP_SUB_BORROW(r1, a7,           r1, carry, carry);
00323               MP_SUB_BORROW(r2, 0,            r2, carry, carry);
00324               MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry, carry);
00325               r4 -= carry;
00326               /* diff 7 */
00327               MP_SUB_BORROW(r0, a6h|a7l,  r0, 0,     carry);
00328               MP_SUB_BORROW(r1, a7h|a4l,      r1, carry, carry);
00329               MP_SUB_BORROW(r2, a4h|a5l,      r2, carry, carry);
00330               MP_SUB_BORROW(r3, a6l,          r3, carry, carry);
00331               r4 -= carry;
00332               /* diff 8 */
00333               MP_SUB_BORROW(r0, a7,               r0, 0,     carry);
00334               MP_SUB_BORROW(r1, a4h<<32,      r1, carry, carry);
00335               MP_SUB_BORROW(r2, a5,           r2, carry, carry);
00336               MP_SUB_BORROW(r3, a6h<<32,      r3, carry, carry);
00337               r4 -= carry;
00338 
00339               /* reduce the overflows */
00340               while (r4 > 0) {
00341                      mp_digit r4_long = r4;
00342                      mp_digit r4l = (r4_long << 32);
00343                      MP_ADD_CARRY(r0, r4_long,      r0, 0,     carry);
00344                      MP_ADD_CARRY(r1, -r4l,         r1, carry, carry);
00345                      MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry, carry);
00346                      MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry, carry);
00347                      r4 = carry;
00348               }
00349 
00350               /* reduce the underflows */
00351               while (r4 < 0) {
00352                      mp_digit r4_long = -r4;
00353                      mp_digit r4l = (r4_long << 32);
00354                      MP_SUB_BORROW(r0, r4_long,      r0, 0,     carry);
00355                      MP_SUB_BORROW(r1, -r4l,         r1, carry, carry);
00356                      MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry, carry);
00357                      MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry, carry);
00358                      r4 = -carry;
00359               }
00360 
00361               if (a != r) {
00362                      MP_CHECKOK(s_mp_pad(r,4));
00363               }
00364               MP_SIGN(r) = MP_ZPOS;
00365               MP_USED(r) = 4;
00366 
00367               MP_DIGIT(r,3) = r3;
00368               MP_DIGIT(r,2) = r2;
00369               MP_DIGIT(r,1) = r1;
00370               MP_DIGIT(r,0) = r0;
00371 
00372               /* final reduction if necessary */
00373               if ((r3 > 0xFFFFFFFF00000001ULL) ||
00374                      ((r3 == 0xFFFFFFFF00000001ULL) && 
00375                      (r2 || (r1 >> 32)|| 
00376                             (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) {
00377                      /* very rare, just use mp_sub */
00378                      MP_CHECKOK(mp_sub(r, &meth->irr, r));
00379               }
00380                      
00381               s_mp_clamp(r);
00382 #endif
00383        }
00384 
00385   CLEANUP:
00386        return res;
00387 }
00388 
00389 /* Compute the square of polynomial a, reduce modulo p256. Store the
00390  * result in r.  r could be a.  Uses optimized modular reduction for p256. 
00391  */
00392 mp_err
00393 ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
00394 {
00395        mp_err res = MP_OKAY;
00396 
00397        MP_CHECKOK(mp_sqr(a, r));
00398        MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
00399   CLEANUP:
00400        return res;
00401 }
00402 
00403 /* Compute the product of two polynomials a and b, reduce modulo p256.
00404  * Store the result in r.  r could be a or b; a could be b.  Uses
00405  * optimized modular reduction for p256. */
00406 mp_err
00407 ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r,
00408                                    const GFMethod *meth)
00409 {
00410        mp_err res = MP_OKAY;
00411 
00412        MP_CHECKOK(mp_mul(a, b, r));
00413        MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
00414   CLEANUP:
00415        return res;
00416 }
00417 
00418 /* Wire in fast field arithmetic and precomputation of base point for
00419  * named curves. */
00420 mp_err
00421 ec_group_set_gfp256(ECGroup *group, ECCurveName name)
00422 {
00423        if (name == ECCurve_NIST_P256) {
00424               group->meth->field_mod = &ec_GFp_nistp256_mod;
00425               group->meth->field_mul = &ec_GFp_nistp256_mul;
00426               group->meth->field_sqr = &ec_GFp_nistp256_sqr;
00427        }
00428        return MP_OKAY;
00429 }