Back to index

lightning-sunbird  0.9+nobinonly
ecp_jac.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  *   Sheueling Chang-Shantz <sheueling.chang@sun.com>,
00024  *   Stephen Fung <fungstep@hotmail.com>, and
00025  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories.
00026  *   Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>,
00027  *   Nils Larsch <nla@trustcenter.de>, and
00028  *   Lenka Fibikova <fibikova@exp-math.uni-essen.de>, the OpenSSL Project
00029  *
00030  * Alternatively, the contents of this file may be used under the terms of
00031  * either the GNU General Public License Version 2 or later (the "GPL"), or
00032  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00033  * in which case the provisions of the GPL or the LGPL are applicable instead
00034  * of those above. If you wish to allow use of your version of this file only
00035  * under the terms of either the GPL or the LGPL, and not to allow others to
00036  * use your version of this file under the terms of the MPL, indicate your
00037  * decision by deleting the provisions above and replace them with the notice
00038  * and other provisions required by the GPL or the LGPL. If you do not delete
00039  * the provisions above, a recipient may use your version of this file under
00040  * the terms of any one of the MPL, the GPL or the LGPL.
00041  *
00042  * ***** END LICENSE BLOCK ***** */
00043 
00044 #include "ecp.h"
00045 #include "mplogic.h"
00046 #include <stdlib.h>
00047 #ifdef ECL_DEBUG
00048 #include <assert.h>
00049 #endif
00050 
00051 /* Converts a point P(px, py) from affine coordinates to Jacobian
00052  * projective coordinates R(rx, ry, rz). Assumes input is already
00053  * field-encoded using field_enc, and returns output that is still
00054  * field-encoded. */
00055 mp_err
00056 ec_GFp_pt_aff2jac(const mp_int *px, const mp_int *py, mp_int *rx,
00057                               mp_int *ry, mp_int *rz, const ECGroup *group)
00058 {
00059        mp_err res = MP_OKAY;
00060 
00061        if (ec_GFp_pt_is_inf_aff(px, py) == MP_YES) {
00062               MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz));
00063        } else {
00064               MP_CHECKOK(mp_copy(px, rx));
00065               MP_CHECKOK(mp_copy(py, ry));
00066               MP_CHECKOK(mp_set_int(rz, 1));
00067               if (group->meth->field_enc) {
00068                      MP_CHECKOK(group->meth->field_enc(rz, rz, group->meth));
00069               }
00070        }
00071   CLEANUP:
00072        return res;
00073 }
00074 
00075 /* Converts a point P(px, py, pz) from Jacobian projective coordinates to
00076  * affine coordinates R(rx, ry).  P and R can share x and y coordinates.
00077  * Assumes input is already field-encoded using field_enc, and returns
00078  * output that is still field-encoded. */
00079 mp_err
00080 ec_GFp_pt_jac2aff(const mp_int *px, const mp_int *py, const mp_int *pz,
00081                               mp_int *rx, mp_int *ry, const ECGroup *group)
00082 {
00083        mp_err res = MP_OKAY;
00084        mp_int z1, z2, z3;
00085 
00086        MP_DIGITS(&z1) = 0;
00087        MP_DIGITS(&z2) = 0;
00088        MP_DIGITS(&z3) = 0;
00089        MP_CHECKOK(mp_init(&z1));
00090        MP_CHECKOK(mp_init(&z2));
00091        MP_CHECKOK(mp_init(&z3));
00092 
00093        /* if point at infinity, then set point at infinity and exit */
00094        if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) {
00095               MP_CHECKOK(ec_GFp_pt_set_inf_aff(rx, ry));
00096               goto CLEANUP;
00097        }
00098 
00099        /* transform (px, py, pz) into (px / pz^2, py / pz^3) */
00100        if (mp_cmp_d(pz, 1) == 0) {
00101               MP_CHECKOK(mp_copy(px, rx));
00102               MP_CHECKOK(mp_copy(py, ry));
00103        } else {
00104               MP_CHECKOK(group->meth->field_div(NULL, pz, &z1, group->meth));
00105               MP_CHECKOK(group->meth->field_sqr(&z1, &z2, group->meth));
00106               MP_CHECKOK(group->meth->field_mul(&z1, &z2, &z3, group->meth));
00107               MP_CHECKOK(group->meth->field_mul(px, &z2, rx, group->meth));
00108               MP_CHECKOK(group->meth->field_mul(py, &z3, ry, group->meth));
00109        }
00110 
00111   CLEANUP:
00112        mp_clear(&z1);
00113        mp_clear(&z2);
00114        mp_clear(&z3);
00115        return res;
00116 }
00117 
00118 /* Checks if point P(px, py, pz) is at infinity. Uses Jacobian
00119  * coordinates. */
00120 mp_err
00121 ec_GFp_pt_is_inf_jac(const mp_int *px, const mp_int *py, const mp_int *pz)
00122 {
00123        return mp_cmp_z(pz);
00124 }
00125 
00126 /* Sets P(px, py, pz) to be the point at infinity.  Uses Jacobian
00127  * coordinates. */
00128 mp_err
00129 ec_GFp_pt_set_inf_jac(mp_int *px, mp_int *py, mp_int *pz)
00130 {
00131        mp_zero(pz);
00132        return MP_OKAY;
00133 }
00134 
00135 /* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and Q is
00136  * (qx, qy, 1).  Elliptic curve points P, Q, and R can all be identical.
00137  * Uses mixed Jacobian-affine coordinates. Assumes input is already
00138  * field-encoded using field_enc, and returns output that is still
00139  * field-encoded. Uses equation (2) from Brown, Hankerson, Lopez, and
00140  * Menezes. Software Implementation of the NIST Elliptic Curves Over Prime
00141  * Fields. */
00142 mp_err
00143 ec_GFp_pt_add_jac_aff(const mp_int *px, const mp_int *py, const mp_int *pz,
00144                                      const mp_int *qx, const mp_int *qy, mp_int *rx,
00145                                      mp_int *ry, mp_int *rz, const ECGroup *group)
00146 {
00147        mp_err res = MP_OKAY;
00148        mp_int A, B, C, D, C2, C3;
00149 
00150        MP_DIGITS(&A) = 0;
00151        MP_DIGITS(&B) = 0;
00152        MP_DIGITS(&C) = 0;
00153        MP_DIGITS(&D) = 0;
00154        MP_DIGITS(&C2) = 0;
00155        MP_DIGITS(&C3) = 0;
00156        MP_CHECKOK(mp_init(&A));
00157        MP_CHECKOK(mp_init(&B));
00158        MP_CHECKOK(mp_init(&C));
00159        MP_CHECKOK(mp_init(&D));
00160        MP_CHECKOK(mp_init(&C2));
00161        MP_CHECKOK(mp_init(&C3));
00162 
00163        /* If either P or Q is the point at infinity, then return the other
00164         * point */
00165        if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) {
00166               MP_CHECKOK(ec_GFp_pt_aff2jac(qx, qy, rx, ry, rz, group));
00167               goto CLEANUP;
00168        }
00169        if (ec_GFp_pt_is_inf_aff(qx, qy) == MP_YES) {
00170               MP_CHECKOK(mp_copy(px, rx));
00171               MP_CHECKOK(mp_copy(py, ry));
00172               MP_CHECKOK(mp_copy(pz, rz));
00173               goto CLEANUP;
00174        }
00175 
00176        /* A = qx * pz^2, B = qy * pz^3 */
00177        MP_CHECKOK(group->meth->field_sqr(pz, &A, group->meth));
00178        MP_CHECKOK(group->meth->field_mul(&A, pz, &B, group->meth));
00179        MP_CHECKOK(group->meth->field_mul(&A, qx, &A, group->meth));
00180        MP_CHECKOK(group->meth->field_mul(&B, qy, &B, group->meth));
00181 
00182        /* C = A - px, D = B - py */
00183        MP_CHECKOK(group->meth->field_sub(&A, px, &C, group->meth));
00184        MP_CHECKOK(group->meth->field_sub(&B, py, &D, group->meth));
00185 
00186        /* C2 = C^2, C3 = C^3 */
00187        MP_CHECKOK(group->meth->field_sqr(&C, &C2, group->meth));
00188        MP_CHECKOK(group->meth->field_mul(&C, &C2, &C3, group->meth));
00189 
00190        /* rz = pz * C */
00191        MP_CHECKOK(group->meth->field_mul(pz, &C, rz, group->meth));
00192 
00193        /* C = px * C^2 */
00194        MP_CHECKOK(group->meth->field_mul(px, &C2, &C, group->meth));
00195        /* A = D^2 */
00196        MP_CHECKOK(group->meth->field_sqr(&D, &A, group->meth));
00197 
00198        /* rx = D^2 - (C^3 + 2 * (px * C^2)) */
00199        MP_CHECKOK(group->meth->field_add(&C, &C, rx, group->meth));
00200        MP_CHECKOK(group->meth->field_add(&C3, rx, rx, group->meth));
00201        MP_CHECKOK(group->meth->field_sub(&A, rx, rx, group->meth));
00202 
00203        /* C3 = py * C^3 */
00204        MP_CHECKOK(group->meth->field_mul(py, &C3, &C3, group->meth));
00205 
00206        /* ry = D * (px * C^2 - rx) - py * C^3 */
00207        MP_CHECKOK(group->meth->field_sub(&C, rx, ry, group->meth));
00208        MP_CHECKOK(group->meth->field_mul(&D, ry, ry, group->meth));
00209        MP_CHECKOK(group->meth->field_sub(ry, &C3, ry, group->meth));
00210 
00211   CLEANUP:
00212        mp_clear(&A);
00213        mp_clear(&B);
00214        mp_clear(&C);
00215        mp_clear(&D);
00216        mp_clear(&C2);
00217        mp_clear(&C3);
00218        return res;
00219 }
00220 
00221 /* Computes R = 2P.  Elliptic curve points P and R can be identical.  Uses 
00222  * Jacobian coordinates.
00223  *
00224  * Assumes input is already field-encoded using field_enc, and returns 
00225  * output that is still field-encoded.
00226  *
00227  * This routine implements Point Doubling in the Jacobian Projective 
00228  * space as described in the paper "Efficient elliptic curve exponentiation 
00229  * using mixed coordinates", by H. Cohen, A Miyaji, T. Ono.
00230  */
00231 mp_err
00232 ec_GFp_pt_dbl_jac(const mp_int *px, const mp_int *py, const mp_int *pz,
00233                               mp_int *rx, mp_int *ry, mp_int *rz, const ECGroup *group)
00234 {
00235        mp_err res = MP_OKAY;
00236        mp_int t0, t1, M, S;
00237 
00238        MP_DIGITS(&t0) = 0;
00239        MP_DIGITS(&t1) = 0;
00240        MP_DIGITS(&M) = 0;
00241        MP_DIGITS(&S) = 0;
00242        MP_CHECKOK(mp_init(&t0));
00243        MP_CHECKOK(mp_init(&t1));
00244        MP_CHECKOK(mp_init(&M));
00245        MP_CHECKOK(mp_init(&S));
00246 
00247        if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) {
00248               MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz));
00249               goto CLEANUP;
00250        }
00251 
00252        if (mp_cmp_d(pz, 1) == 0) {
00253               /* M = 3 * px^2 + a */
00254               MP_CHECKOK(group->meth->field_sqr(px, &t0, group->meth));
00255               MP_CHECKOK(group->meth->field_add(&t0, &t0, &M, group->meth));
00256               MP_CHECKOK(group->meth->field_add(&t0, &M, &t0, group->meth));
00257               MP_CHECKOK(group->meth->
00258                                field_add(&t0, &group->curvea, &M, group->meth));
00259        } else if (mp_cmp_int(&group->curvea, -3) == 0) {
00260               /* M = 3 * (px + pz^2) * (px - pz^2) */
00261               MP_CHECKOK(group->meth->field_sqr(pz, &M, group->meth));
00262               MP_CHECKOK(group->meth->field_add(px, &M, &t0, group->meth));
00263               MP_CHECKOK(group->meth->field_sub(px, &M, &t1, group->meth));
00264               MP_CHECKOK(group->meth->field_mul(&t0, &t1, &M, group->meth));
00265               MP_CHECKOK(group->meth->field_add(&M, &M, &t0, group->meth));
00266               MP_CHECKOK(group->meth->field_add(&t0, &M, &M, group->meth));
00267        } else {
00268               /* M = 3 * (px^2) + a * (pz^4) */
00269               MP_CHECKOK(group->meth->field_sqr(px, &t0, group->meth));
00270               MP_CHECKOK(group->meth->field_add(&t0, &t0, &M, group->meth));
00271               MP_CHECKOK(group->meth->field_add(&t0, &M, &t0, group->meth));
00272               MP_CHECKOK(group->meth->field_sqr(pz, &M, group->meth));
00273               MP_CHECKOK(group->meth->field_sqr(&M, &M, group->meth));
00274               MP_CHECKOK(group->meth->
00275                                field_mul(&M, &group->curvea, &M, group->meth));
00276               MP_CHECKOK(group->meth->field_add(&M, &t0, &M, group->meth));
00277        }
00278 
00279        /* rz = 2 * py * pz */
00280        /* t0 = 4 * py^2 */
00281        if (mp_cmp_d(pz, 1) == 0) {
00282               MP_CHECKOK(group->meth->field_add(py, py, rz, group->meth));
00283               MP_CHECKOK(group->meth->field_sqr(rz, &t0, group->meth));
00284        } else {
00285               MP_CHECKOK(group->meth->field_add(py, py, &t0, group->meth));
00286               MP_CHECKOK(group->meth->field_mul(&t0, pz, rz, group->meth));
00287               MP_CHECKOK(group->meth->field_sqr(&t0, &t0, group->meth));
00288        }
00289 
00290        /* S = 4 * px * py^2 = px * (2 * py)^2 */
00291        MP_CHECKOK(group->meth->field_mul(px, &t0, &S, group->meth));
00292 
00293        /* rx = M^2 - 2 * S */
00294        MP_CHECKOK(group->meth->field_add(&S, &S, &t1, group->meth));
00295        MP_CHECKOK(group->meth->field_sqr(&M, rx, group->meth));
00296        MP_CHECKOK(group->meth->field_sub(rx, &t1, rx, group->meth));
00297 
00298        /* ry = M * (S - rx) - 8 * py^4 */
00299        MP_CHECKOK(group->meth->field_sqr(&t0, &t1, group->meth));
00300        if (mp_isodd(&t1)) {
00301               MP_CHECKOK(mp_add(&t1, &group->meth->irr, &t1));
00302        }
00303        MP_CHECKOK(mp_div_2(&t1, &t1));
00304        MP_CHECKOK(group->meth->field_sub(&S, rx, &S, group->meth));
00305        MP_CHECKOK(group->meth->field_mul(&M, &S, &M, group->meth));
00306        MP_CHECKOK(group->meth->field_sub(&M, &t1, ry, group->meth));
00307 
00308   CLEANUP:
00309        mp_clear(&t0);
00310        mp_clear(&t1);
00311        mp_clear(&M);
00312        mp_clear(&S);
00313        return res;
00314 }
00315 
00316 /* by default, this routine is unused and thus doesn't need to be compiled */
00317 #ifdef ECL_ENABLE_GFP_PT_MUL_JAC
00318 /* Computes R = nP where R is (rx, ry) and P is (px, py). The parameters
00319  * a, b and p are the elliptic curve coefficients and the prime that
00320  * determines the field GFp.  Elliptic curve points P and R can be
00321  * identical.  Uses mixed Jacobian-affine coordinates. Assumes input is
00322  * already field-encoded using field_enc, and returns output that is still 
00323  * field-encoded. Uses 4-bit window method. */
00324 mp_err
00325 ec_GFp_pt_mul_jac(const mp_int *n, const mp_int *px, const mp_int *py,
00326                               mp_int *rx, mp_int *ry, const ECGroup *group)
00327 {
00328        mp_err res = MP_OKAY;
00329        mp_int precomp[16][2], rz;
00330        int i, ni, d;
00331 
00332        MP_DIGITS(&rz) = 0;
00333        for (i = 0; i < 16; i++) {
00334               MP_DIGITS(&precomp[i][0]) = 0;
00335               MP_DIGITS(&precomp[i][1]) = 0;
00336        }
00337 
00338        ARGCHK(group != NULL, MP_BADARG);
00339        ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG);
00340 
00341        /* initialize precomputation table */
00342        for (i = 0; i < 16; i++) {
00343               MP_CHECKOK(mp_init(&precomp[i][0]));
00344               MP_CHECKOK(mp_init(&precomp[i][1]));
00345        }
00346 
00347        /* fill precomputation table */
00348        mp_zero(&precomp[0][0]);
00349        mp_zero(&precomp[0][1]);
00350        MP_CHECKOK(mp_copy(px, &precomp[1][0]));
00351        MP_CHECKOK(mp_copy(py, &precomp[1][1]));
00352        for (i = 2; i < 16; i++) {
00353               MP_CHECKOK(group->
00354                                point_add(&precomp[1][0], &precomp[1][1],
00355                                                   &precomp[i - 1][0], &precomp[i - 1][1],
00356                                                   &precomp[i][0], &precomp[i][1], group));
00357        }
00358 
00359        d = (mpl_significant_bits(n) + 3) / 4;
00360 
00361        /* R = inf */
00362        MP_CHECKOK(mp_init(&rz));
00363        MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz));
00364 
00365        for (i = d - 1; i >= 0; i--) {
00366               /* compute window ni */
00367               ni = MP_GET_BIT(n, 4 * i + 3);
00368               ni <<= 1;
00369               ni |= MP_GET_BIT(n, 4 * i + 2);
00370               ni <<= 1;
00371               ni |= MP_GET_BIT(n, 4 * i + 1);
00372               ni <<= 1;
00373               ni |= MP_GET_BIT(n, 4 * i);
00374               /* R = 2^4 * R */
00375               MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group));
00376               MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group));
00377               MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group));
00378               MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group));
00379               /* R = R + (ni * P) */
00380               MP_CHECKOK(ec_GFp_pt_add_jac_aff
00381                                (rx, ry, &rz, &precomp[ni][0], &precomp[ni][1], rx, ry,
00382                                    &rz, group));
00383        }
00384 
00385        /* convert result S to affine coordinates */
00386        MP_CHECKOK(ec_GFp_pt_jac2aff(rx, ry, &rz, rx, ry, group));
00387 
00388   CLEANUP:
00389        mp_clear(&rz);
00390        for (i = 0; i < 16; i++) {
00391               mp_clear(&precomp[i][0]);
00392               mp_clear(&precomp[i][1]);
00393        }
00394        return res;
00395 }
00396 #endif
00397 
00398 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G + 
00399  * k2 * P(x, y), where G is the generator (base point) of the group of
00400  * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
00401  * Uses mixed Jacobian-affine coordinates. Input and output values are
00402  * assumed to be NOT field-encoded. Uses algorithm 15 (simultaneous
00403  * multiple point multiplication) from Brown, Hankerson, Lopez, Menezes.
00404  * Software Implementation of the NIST Elliptic Curves over Prime Fields. */
00405 mp_err
00406 ec_GFp_pts_mul_jac(const mp_int *k1, const mp_int *k2, const mp_int *px,
00407                                const mp_int *py, mp_int *rx, mp_int *ry,
00408                                const ECGroup *group)
00409 {
00410        mp_err res = MP_OKAY;
00411        mp_int precomp[4][4][2];
00412        mp_int rz;
00413        const mp_int *a, *b;
00414        int i, j;
00415        int ai, bi, d;
00416 
00417        for (i = 0; i < 4; i++) {
00418               for (j = 0; j < 4; j++) {
00419                      MP_DIGITS(&precomp[i][j][0]) = 0;
00420                      MP_DIGITS(&precomp[i][j][1]) = 0;
00421               }
00422        }
00423        MP_DIGITS(&rz) = 0;
00424 
00425        ARGCHK(group != NULL, MP_BADARG);
00426        ARGCHK(!((k1 == NULL)
00427                       && ((k2 == NULL) || (px == NULL)
00428                              || (py == NULL))), MP_BADARG);
00429 
00430        /* if some arguments are not defined used ECPoint_mul */
00431        if (k1 == NULL) {
00432               return ECPoint_mul(group, k2, px, py, rx, ry);
00433        } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) {
00434               return ECPoint_mul(group, k1, NULL, NULL, rx, ry);
00435        }
00436 
00437        /* initialize precomputation table */
00438        for (i = 0; i < 4; i++) {
00439               for (j = 0; j < 4; j++) {
00440                      MP_CHECKOK(mp_init(&precomp[i][j][0]));
00441                      MP_CHECKOK(mp_init(&precomp[i][j][1]));
00442               }
00443        }
00444 
00445        /* fill precomputation table */
00446        /* assign {k1, k2} = {a, b} such that len(a) >= len(b) */
00447        if (mpl_significant_bits(k1) < mpl_significant_bits(k2)) {
00448               a = k2;
00449               b = k1;
00450               if (group->meth->field_enc) {
00451                      MP_CHECKOK(group->meth->
00452                                       field_enc(px, &precomp[1][0][0], group->meth));
00453                      MP_CHECKOK(group->meth->
00454                                       field_enc(py, &precomp[1][0][1], group->meth));
00455               } else {
00456                      MP_CHECKOK(mp_copy(px, &precomp[1][0][0]));
00457                      MP_CHECKOK(mp_copy(py, &precomp[1][0][1]));
00458               }
00459               MP_CHECKOK(mp_copy(&group->genx, &precomp[0][1][0]));
00460               MP_CHECKOK(mp_copy(&group->geny, &precomp[0][1][1]));
00461        } else {
00462               a = k1;
00463               b = k2;
00464               MP_CHECKOK(mp_copy(&group->genx, &precomp[1][0][0]));
00465               MP_CHECKOK(mp_copy(&group->geny, &precomp[1][0][1]));
00466               if (group->meth->field_enc) {
00467                      MP_CHECKOK(group->meth->
00468                                       field_enc(px, &precomp[0][1][0], group->meth));
00469                      MP_CHECKOK(group->meth->
00470                                       field_enc(py, &precomp[0][1][1], group->meth));
00471               } else {
00472                      MP_CHECKOK(mp_copy(px, &precomp[0][1][0]));
00473                      MP_CHECKOK(mp_copy(py, &precomp[0][1][1]));
00474               }
00475        }
00476        /* precompute [*][0][*] */
00477        mp_zero(&precomp[0][0][0]);
00478        mp_zero(&precomp[0][0][1]);
00479        MP_CHECKOK(group->
00480                         point_dbl(&precomp[1][0][0], &precomp[1][0][1],
00481                                            &precomp[2][0][0], &precomp[2][0][1], group));
00482        MP_CHECKOK(group->
00483                         point_add(&precomp[1][0][0], &precomp[1][0][1],
00484                                            &precomp[2][0][0], &precomp[2][0][1],
00485                                            &precomp[3][0][0], &precomp[3][0][1], group));
00486        /* precompute [*][1][*] */
00487        for (i = 1; i < 4; i++) {
00488               MP_CHECKOK(group->
00489                                point_add(&precomp[0][1][0], &precomp[0][1][1],
00490                                                   &precomp[i][0][0], &precomp[i][0][1],
00491                                                   &precomp[i][1][0], &precomp[i][1][1], group));
00492        }
00493        /* precompute [*][2][*] */
00494        MP_CHECKOK(group->
00495                         point_dbl(&precomp[0][1][0], &precomp[0][1][1],
00496                                            &precomp[0][2][0], &precomp[0][2][1], group));
00497        for (i = 1; i < 4; i++) {
00498               MP_CHECKOK(group->
00499                                point_add(&precomp[0][2][0], &precomp[0][2][1],
00500                                                   &precomp[i][0][0], &precomp[i][0][1],
00501                                                   &precomp[i][2][0], &precomp[i][2][1], group));
00502        }
00503        /* precompute [*][3][*] */
00504        MP_CHECKOK(group->
00505                         point_add(&precomp[0][1][0], &precomp[0][1][1],
00506                                            &precomp[0][2][0], &precomp[0][2][1],
00507                                            &precomp[0][3][0], &precomp[0][3][1], group));
00508        for (i = 1; i < 4; i++) {
00509               MP_CHECKOK(group->
00510                                point_add(&precomp[0][3][0], &precomp[0][3][1],
00511                                                   &precomp[i][0][0], &precomp[i][0][1],
00512                                                   &precomp[i][3][0], &precomp[i][3][1], group));
00513        }
00514 
00515        d = (mpl_significant_bits(a) + 1) / 2;
00516 
00517        /* R = inf */
00518        MP_CHECKOK(mp_init(&rz));
00519        MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz));
00520 
00521        for (i = d - 1; i >= 0; i--) {
00522               ai = MP_GET_BIT(a, 2 * i + 1);
00523               ai <<= 1;
00524               ai |= MP_GET_BIT(a, 2 * i);
00525               bi = MP_GET_BIT(b, 2 * i + 1);
00526               bi <<= 1;
00527               bi |= MP_GET_BIT(b, 2 * i);
00528               /* R = 2^2 * R */
00529               MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group));
00530               MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group));
00531               /* R = R + (ai * A + bi * B) */
00532               MP_CHECKOK(ec_GFp_pt_add_jac_aff
00533                                (rx, ry, &rz, &precomp[ai][bi][0], &precomp[ai][bi][1],
00534                                    rx, ry, &rz, group));
00535        }
00536 
00537        MP_CHECKOK(ec_GFp_pt_jac2aff(rx, ry, &rz, rx, ry, group));
00538 
00539        if (group->meth->field_dec) {
00540               MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
00541               MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
00542        }
00543 
00544   CLEANUP:
00545        mp_clear(&rz);
00546        for (i = 0; i < 4; i++) {
00547               for (j = 0; j < 4; j++) {
00548                      mp_clear(&precomp[i][j][0]);
00549                      mp_clear(&precomp[i][j][1]);
00550               }
00551        }
00552        return res;
00553 }