Back to index

lightning-sunbird  0.9+nobinonly
ec2_193.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 binary polynomial 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  *   Sheueling Chang-Shantz <sheueling.chang@sun.com>,
00024  *   Stephen Fung <fungstep@hotmail.com>, and
00025  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories.
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either the GNU General Public License Version 2 or later (the "GPL"), or
00029  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK ***** */
00040 
00041 #include "ec2.h"
00042 #include "mp_gf2m.h"
00043 #include "mp_gf2m-priv.h"
00044 #include "mpi.h"
00045 #include "mpi-priv.h"
00046 #include <stdlib.h>
00047 
00048 /* Fast reduction for polynomials over a 193-bit curve. Assumes reduction
00049  * polynomial with terms {193, 15, 0}. */
00050 mp_err
00051 ec_GF2m_193_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
00052 {
00053        mp_err res = MP_OKAY;
00054        mp_digit *u, z;
00055 
00056        if (a != r) {
00057               MP_CHECKOK(mp_copy(a, r));
00058        }
00059 #ifdef ECL_SIXTY_FOUR_BIT
00060        if (MP_USED(r) < 7) {
00061               MP_CHECKOK(s_mp_pad(r, 7));
00062        }
00063        u = MP_DIGITS(r);
00064        MP_USED(r) = 7;
00065 
00066        /* u[6] only has 2 significant bits */
00067        z = u[6];
00068        u[3] ^= (z << 14) ^ (z >> 1);
00069        u[2] ^= (z << 63);
00070        z = u[5];
00071        u[3] ^= (z >> 50);
00072        u[2] ^= (z << 14) ^ (z >> 1);
00073        u[1] ^= (z << 63);
00074        z = u[4];
00075        u[2] ^= (z >> 50);
00076        u[1] ^= (z << 14) ^ (z >> 1);
00077        u[0] ^= (z << 63);
00078        z = u[3] >> 1;                            /* z only has 63 significant bits */
00079        u[1] ^= (z >> 49);
00080        u[0] ^= (z << 15) ^ z;
00081        /* clear bits above 193 */
00082        u[6] = u[5] = u[4] = 0;
00083        u[3] ^= z << 1;
00084 #else
00085        if (MP_USED(r) < 13) {
00086               MP_CHECKOK(s_mp_pad(r, 13));
00087        }
00088        u = MP_DIGITS(r);
00089        MP_USED(r) = 13;
00090 
00091        /* u[12] only has 2 significant bits */
00092        z = u[12];
00093        u[6] ^= (z << 14) ^ (z >> 1);
00094        u[5] ^= (z << 31);
00095        z = u[11];
00096        u[6] ^= (z >> 18);
00097        u[5] ^= (z << 14) ^ (z >> 1);
00098        u[4] ^= (z << 31);
00099        z = u[10];
00100        u[5] ^= (z >> 18);
00101        u[4] ^= (z << 14) ^ (z >> 1);
00102        u[3] ^= (z << 31);
00103        z = u[9];
00104        u[4] ^= (z >> 18);
00105        u[3] ^= (z << 14) ^ (z >> 1);
00106        u[2] ^= (z << 31);
00107        z = u[8];
00108        u[3] ^= (z >> 18);
00109        u[2] ^= (z << 14) ^ (z >> 1);
00110        u[1] ^= (z << 31);
00111        z = u[7];
00112        u[2] ^= (z >> 18);
00113        u[1] ^= (z << 14) ^ (z >> 1);
00114        u[0] ^= (z << 31);
00115        z = u[6] >> 1;                            /* z only has 31 significant bits */
00116        u[1] ^= (z >> 17);
00117        u[0] ^= (z << 15) ^ z;
00118        /* clear bits above 193 */
00119        u[12] = u[11] = u[10] = u[9] = u[8] = u[7] = 0;
00120        u[6] ^= z << 1;
00121 #endif
00122        s_mp_clamp(r);
00123 
00124   CLEANUP:
00125        return res;
00126 }
00127 
00128 /* Fast squaring for polynomials over a 193-bit curve. Assumes reduction
00129  * polynomial with terms {193, 15, 0}. */
00130 mp_err
00131 ec_GF2m_193_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
00132 {
00133        mp_err res = MP_OKAY;
00134        mp_digit *u, *v;
00135 
00136        v = MP_DIGITS(a);
00137 
00138 #ifdef ECL_SIXTY_FOUR_BIT
00139        if (MP_USED(a) < 4) {
00140               return mp_bsqrmod(a, meth->irr_arr, r);
00141        }
00142        if (MP_USED(r) < 7) {
00143               MP_CHECKOK(s_mp_pad(r, 7));
00144        }
00145        MP_USED(r) = 7;
00146 #else
00147        if (MP_USED(a) < 7) {
00148               return mp_bsqrmod(a, meth->irr_arr, r);
00149        }
00150        if (MP_USED(r) < 13) {
00151               MP_CHECKOK(s_mp_pad(r, 13));
00152        }
00153        MP_USED(r) = 13;
00154 #endif
00155        u = MP_DIGITS(r);
00156 
00157 #ifdef ECL_THIRTY_TWO_BIT
00158        u[12] = gf2m_SQR0(v[6]);
00159        u[11] = gf2m_SQR1(v[5]);
00160        u[10] = gf2m_SQR0(v[5]);
00161        u[9] = gf2m_SQR1(v[4]);
00162        u[8] = gf2m_SQR0(v[4]);
00163        u[7] = gf2m_SQR1(v[3]);
00164 #endif
00165        u[6] = gf2m_SQR0(v[3]);
00166        u[5] = gf2m_SQR1(v[2]);
00167        u[4] = gf2m_SQR0(v[2]);
00168        u[3] = gf2m_SQR1(v[1]);
00169        u[2] = gf2m_SQR0(v[1]);
00170        u[1] = gf2m_SQR1(v[0]);
00171        u[0] = gf2m_SQR0(v[0]);
00172        return ec_GF2m_193_mod(r, r, meth);
00173 
00174   CLEANUP:
00175        return res;
00176 }
00177 
00178 /* Fast multiplication for polynomials over a 193-bit curve. Assumes
00179  * reduction polynomial with terms {193, 15, 0}. */
00180 mp_err
00181 ec_GF2m_193_mul(const mp_int *a, const mp_int *b, mp_int *r,
00182                             const GFMethod *meth)
00183 {
00184        mp_err res = MP_OKAY;
00185        mp_digit a3 = 0, a2 = 0, a1 = 0, a0, b3 = 0, b2 = 0, b1 = 0, b0;
00186 
00187 #ifdef ECL_THIRTY_TWO_BIT
00188        mp_digit a6 = 0, a5 = 0, a4 = 0, b6 = 0, b5 = 0, b4 = 0;
00189        mp_digit rm[8];
00190 #endif
00191 
00192        if (a == b) {
00193               return ec_GF2m_193_sqr(a, r, meth);
00194        } else {
00195               switch (MP_USED(a)) {
00196 #ifdef ECL_THIRTY_TWO_BIT
00197               case 7:
00198                      a6 = MP_DIGIT(a, 6);
00199               case 6:
00200                      a5 = MP_DIGIT(a, 5);
00201               case 5:
00202                      a4 = MP_DIGIT(a, 4);
00203 #endif
00204               case 4:
00205                      a3 = MP_DIGIT(a, 3);
00206               case 3:
00207                      a2 = MP_DIGIT(a, 2);
00208               case 2:
00209                      a1 = MP_DIGIT(a, 1);
00210               default:
00211                      a0 = MP_DIGIT(a, 0);
00212               }
00213               switch (MP_USED(b)) {
00214 #ifdef ECL_THIRTY_TWO_BIT
00215               case 7:
00216                      b6 = MP_DIGIT(b, 6);
00217               case 6:
00218                      b5 = MP_DIGIT(b, 5);
00219               case 5:
00220                      b4 = MP_DIGIT(b, 4);
00221 #endif
00222               case 4:
00223                      b3 = MP_DIGIT(b, 3);
00224               case 3:
00225                      b2 = MP_DIGIT(b, 2);
00226               case 2:
00227                      b1 = MP_DIGIT(b, 1);
00228               default:
00229                      b0 = MP_DIGIT(b, 0);
00230               }
00231 #ifdef ECL_SIXTY_FOUR_BIT
00232               MP_CHECKOK(s_mp_pad(r, 8));
00233               s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0);
00234               MP_USED(r) = 8;
00235               s_mp_clamp(r);
00236 #else
00237               MP_CHECKOK(s_mp_pad(r, 14));
00238               s_bmul_3x3(MP_DIGITS(r) + 8, a6, a5, a4, b6, b5, b4);
00239               s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0);
00240               s_bmul_4x4(rm, a3, a6 ^ a2, a5 ^ a1, a4 ^ a0, b3, b6 ^ b2, b5 ^ b1,
00241                                b4 ^ b0);
00242               rm[7] ^= MP_DIGIT(r, 7);
00243               rm[6] ^= MP_DIGIT(r, 6);
00244               rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 13);
00245               rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 12);
00246               rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 11);
00247               rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 10);
00248               rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 9);
00249               rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 8);
00250               MP_DIGIT(r, 11) ^= rm[7];
00251               MP_DIGIT(r, 10) ^= rm[6];
00252               MP_DIGIT(r, 9) ^= rm[5];
00253               MP_DIGIT(r, 8) ^= rm[4];
00254               MP_DIGIT(r, 7) ^= rm[3];
00255               MP_DIGIT(r, 6) ^= rm[2];
00256               MP_DIGIT(r, 5) ^= rm[1];
00257               MP_DIGIT(r, 4) ^= rm[0];
00258               MP_USED(r) = 14;
00259               s_mp_clamp(r);
00260 #endif
00261               return ec_GF2m_193_mod(r, r, meth);
00262        }
00263 
00264   CLEANUP:
00265        return res;
00266 }
00267 
00268 /* Wire in fast field arithmetic for 193-bit curves. */
00269 mp_err
00270 ec_group_set_gf2m193(ECGroup *group, ECCurveName name)
00271 {
00272        group->meth->field_mod = &ec_GF2m_193_mod;
00273        group->meth->field_mul = &ec_GF2m_193_mul;
00274        group->meth->field_sqr = &ec_GF2m_193_sqr;
00275        return MP_OKAY;
00276 }