f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * ***** BEGIN LICENSE BLOCK *****
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Version: MPL 1.1/GPL 2.0/LGPL 2.1
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The contents of this file are subject to the Mozilla Public License Version
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * 1.1 (the "License"); you may not use this file except in compliance with
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the License. You may obtain a copy of the License at
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Software distributed under the License is distributed on an "AS IS" basis,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * for the specific language governing rights and limitations under the
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The Original Code is the elliptic curve math library.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The Initial Developer of the Original Code is
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Sun Microsystems, Inc.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Portions created by the Initial Developer are Copyright (C) 2003
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the Initial Developer. All Rights Reserved.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Contributor(s):
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Alternatively, the contents of this file may be used under the terms of
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * in which case the provisions of the GPL or the LGPL are applicable instead
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * of those above. If you wish to allow use of your version of this file only
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * under the terms of either the GPL or the LGPL, and not to allow others to
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * use your version of this file under the terms of the MPL, indicate your
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * decision by deleting the provisions above and replace them with the notice
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * and other provisions required by the GPL or the LGPL. If you do not delete
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the provisions above, a recipient may use your version of this file under
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the terms of any one of the MPL, the GPL or the LGPL.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * ***** END LICENSE BLOCK ***** */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Use is subject to license terms.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Sun elects to use this software under the MPL license.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#pragma ident "%Z%%M% %I% %E% SMI"
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Elliptic curve scalar-point multiplication. Computes R(x, y) = k * P(x,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * y). If x, y = NULL, then P is assumed to be the generator (base point)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * of the group of points on the elliptic curve. Input and output values
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * are assumed to be NOT field-encoded. */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersECPoint_mul(const ECGroup *group, const mp_int *k, const mp_int *px,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* want scalar to be less than or equal to group order */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->base_point_mul(&kt, rx, ry, group));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_enc(px, rx, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_enc(py, ry, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->point_mul(&kt, rx, ry, rx, ry, group));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->point_mul(&kt, px, py, rx, ry, group));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G +
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * k2 * P(x, y), where G is the generator (base point) of the group of
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Input and output values are assumed to be NOT field-encoded. */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersec_pts_mul_basic(const mp_int *k1, const mp_int *k2, const mp_int *px,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* if some arguments are not defined used ECPoint_mul */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(ECPoint_mul(group, k1, NULL, NULL, &sx, &sy));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(ECPoint_mul(group, k2, px, py, rx, ry));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_enc(&sx, &sx, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_enc(&sy, &sy, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_enc(rx, rx, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_enc(ry, ry, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->point_add(&sx, &sy, rx, ry, rx, ry, group));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G +
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * k2 * P(x, y), where G is the generator (base point) of the group of
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Input and output values are assumed to be NOT field-encoded. Uses
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * algorithm 15 (simultaneous multiple point multiplication) from Brown,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Hankerson, Lopez, Menezes. Software Implementation of the NIST
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Elliptic Curves over Prime Fields. */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersec_pts_mul_simul_w2(const mp_int *k1, const mp_int *k2, const mp_int *px,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers const mp_int *a, *b;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* if some arguments are not defined used ECPoint_mul */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* initialize precomputation table */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (i = 0; i < 4; i++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (j = 0; j < 4; j++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (i = 0; i < 4; i++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (j = 0; j < 4; j++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* fill precomputation table */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* assign {k1, k2} = {a, b} such that len(a) >= len(b) */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (mpl_significant_bits(k1) < mpl_significant_bits(k2)) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(mp_copy(&group->genx, &precomp[0][1][0]));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(mp_copy(&group->geny, &precomp[0][1][1]));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(mp_copy(&group->genx, &precomp[1][0][0]));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(mp_copy(&group->geny, &precomp[1][0][1]));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* precompute [*][0][*] */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* precompute [*][1][*] */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* precompute [*][2][*] */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* precompute [*][3][*] */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* R = inf */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (i = d - 1; i >= 0; i--) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* R = 2^2 * R */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->point_dbl(rx, ry, rx, ry, group));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->point_dbl(rx, ry, rx, ry, group));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* R = R + (ai * A + bi * B) */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (i = 0; i < 4; i++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (j = 0; j < 4; j++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G +
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * k2 * P(x, y), where G is the generator (base point) of the group of
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Input and output values are assumed to be NOT field-encoded. */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersECPoints_mul(const ECGroup *group, const mp_int *k1, const mp_int *k2,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers const mp_int *px, const mp_int *py, mp_int *rx, mp_int *ry)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* want scalar to be less than or equal to group order */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* if points_mul is defined, then use it */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers res = group->points_mul(k1p, k2p, px, py, rx, ry, group);