ecp_smpl.c revision 9dc0df1bac950d6e491f9a7c7e4888f2b301cb15
/* crypto/ec/ecp_smpl.c */
/* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
* for the OpenSSL project.
* Includes code written by Bodo Moeller for the OpenSSL project.
*/
/* ====================================================================
* Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* distribution.
*
* 3. All advertising materials mentioning features or use of this
* software must display the following acknowledgment:
* "This product includes software developed by the OpenSSL Project
* for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
*
* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
* endorse or promote products derived from this software without
* prior written permission. For written permission, please contact
* openssl-core@openssl.org.
*
* 5. Products derived from this software may not be called "OpenSSL"
* nor may "OpenSSL" appear in their names without prior written
* permission of the OpenSSL Project.
*
* 6. Redistributions of any form whatsoever must retain the following
* acknowledgment:
* "This product includes software developed by the OpenSSL Project
* for use in the OpenSSL Toolkit (http://www.openssl.org/)"
*
* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
* ====================================================================
*
* This product includes cryptographic software written by Eric Young
* (eay@cryptsoft.com). This product includes software written by Tim
* Hudson (tjh@cryptsoft.com).
*
*/
/* ====================================================================
* Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
* Portions of this software developed by SUN MICROSYSTEMS, INC.,
* and contributed to the OpenSSL project.
*/
#include <openssl/symhacks.h>
#include "ec_lcl.h"
const EC_METHOD *EC_GFp_simple_method(void)
{
0 /* mul */,
0 /* precompute_mult */,
0 /* have_precompute_mult */,
0 /* field_div */,
0 /* field_encode */,
0 /* field_decode */,
0 /* field_set_to_one */ };
return &ret;
}
/* Most method functions in this file are designed to work with
* non-trivial representations of field elements if necessary
* (see ecp_mont.c): while standard modular addition and subtraction
* are used, the field_mul and field_sqr methods will be used for
* multiplication, and field_encode and field_decode (if defined)
* will be used for converting between representations.
* Functions ec_GFp_simple_points_make_affine() and
* ec_GFp_simple_point_get_affine_coordinates() specifically assume
* that if a non-trivial representation is used, it is a Montgomery
* representation (i.e. 'encoding' means multiplying by some factor R).
*/
{
group->a_is_minus3 = 0;
return 1;
}
{
}
{
BN_clear_free(&group->a);
BN_clear_free(&group->b);
}
{
return 1;
}
{
int ret = 0;
/* p must be a prime > 3 */
{
return 0;
}
{
return 0;
}
/* group->field */
/* group->a */
else
/* group->b */
/* group->a_is_minus3 */
ret = 1;
err:
return ret;
}
int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
{
int ret = 0;
if (p != NULL)
{
}
{
{
{
return 0;
}
if (a != NULL)
{
}
if (b != NULL)
{
}
}
else
{
if (a != NULL)
{
}
if (b != NULL)
{
}
}
}
ret = 1;
err:
if (new_ctx)
return ret;
}
{
}
{
int ret = 0;
{
{
goto err;
}
}
a = BN_CTX_get(ctx);
b = BN_CTX_get(ctx);
{
}
else
{
}
/* check the discriminant:
* y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
* 0 =< a, b < p */
if (BN_is_zero(a))
{
if (BN_is_zero(b)) goto err;
}
else if (!BN_is_zero(b))
{
/* tmp_1 = 4*a^3 */
/* tmp_2 = 27*b^2 */
if (BN_is_zero(a)) goto err;
}
ret = 1;
err:
return ret;
}
{
return 1;
}
{
}
{
BN_clear_free(&point->X);
BN_clear_free(&point->Y);
BN_clear_free(&point->Z);
}
{
return 1;
}
{
return 1;
}
{
int ret = 0;
{
return 0;
}
if (x != NULL)
{
{
}
}
if (y != NULL)
{
{
}
}
if (z != NULL)
{
int Z_is_one;
{
{
}
else
{
}
}
}
ret = 1;
err:
return ret;
}
{
int ret = 0;
{
{
return 0;
}
if (x != NULL)
{
}
if (y != NULL)
{
}
if (z != NULL)
{
}
}
else
{
if (x != NULL)
{
}
if (y != NULL)
{
}
if (z != NULL)
{
}
}
ret = 1;
err:
return ret;
}
{
{
/* unlike for projective coordinates, we do not tolerate this */
return 0;
}
}
{
int ret = 0;
{
return 0;
}
{
return 0;
}
Z = BN_CTX_get(ctx);
/* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
{
Z_ = Z;
}
else
{
}
{
{
if (x != NULL)
{
}
if (y != NULL)
{
}
}
else
{
if (x != NULL)
{
}
if (y != NULL)
{
}
}
}
else
{
{
goto err;
}
{
/* field_sqr works on standard representation */
}
else
{
}
if (x != NULL)
{
/* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
}
if (y != NULL)
{
{
/* field_mul works on standard representation */
}
else
{
}
/* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
}
}
ret = 1;
err:
return ret;
}
{
int ret = 0;
/* clear error queue*/
{
return 0;
}
x = BN_CTX_get(ctx);
y = BN_CTX_get(ctx);
/* Recover y. We have a Weierstrass equation
* y^2 = x^3 + a*x + b,
* so y is one of the square roots of x^3 + a*x + b.
*/
/* tmp1 := x^3 */
{
/* field_{sqr,mul} work on standard representation */
}
else
{
}
/* tmp1 := tmp1 + a*x */
if (group->a_is_minus3)
{
}
else
{
{
}
else
{
/* field_mul works on standard representation */
}
}
/* tmp1 := tmp1 + b */
{
}
else
{
}
{
unsigned long err = ERR_peek_last_error();
{
}
else
goto err;
}
{
if (BN_is_zero(y))
{
int kron;
if (kron == 1)
else
/* BN_mod_sqrt() should have cought this error (not a square) */
goto err;
}
}
{
goto err;
}
ret = 1;
err:
return ret;
}
size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
{
int used_ctx = 0;
BIGNUM *x, *y;
if ((form != POINT_CONVERSION_COMPRESSED)
&& (form != POINT_CONVERSION_UNCOMPRESSED)
&& (form != POINT_CONVERSION_HYBRID))
{
goto err;
}
{
/* encodes to a single 0 octet */
{
if (len < 1)
{
return 0;
}
buf[0] = 0;
}
return 1;
}
/* ret := required output buffer length */
/* if 'buf' is NULL, just return required length */
{
{
goto err;
}
{
return 0;
}
used_ctx = 1;
x = BN_CTX_get(ctx);
y = BN_CTX_get(ctx);
else
i = 1;
{
goto err;
}
while (skip > 0)
{
buf[i++] = 0;
skip--;
}
i += skip;
if (i != 1 + field_len)
{
goto err;
}
{
{
goto err;
}
while (skip > 0)
{
buf[i++] = 0;
skip--;
}
i += skip;
}
if (i != ret)
{
goto err;
}
}
if (used_ctx)
return ret;
err:
if (used_ctx)
return 0;
}
{
int y_bit;
BIGNUM *x, *y;
int ret = 0;
if (len == 0)
{
return 0;
}
&& (form != POINT_CONVERSION_UNCOMPRESSED)
&& (form != POINT_CONVERSION_HYBRID))
{
return 0;
}
{
return 0;
}
if (form == 0)
{
if (len != 1)
{
return 0;
}
}
{
return 0;
}
{
return 0;
}
x = BN_CTX_get(ctx);
y = BN_CTX_get(ctx);
{
goto err;
}
if (form == POINT_CONVERSION_COMPRESSED)
{
}
else
{
{
goto err;
}
if (form == POINT_CONVERSION_HYBRID)
{
{
goto err;
}
}
}
{
goto err;
}
ret = 1;
err:
return ret;
}
int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
{
const BIGNUM *p;
int ret = 0;
if (a == b)
if (EC_POINT_is_at_infinity(group, a))
return EC_POINT_copy(r, b);
if (EC_POINT_is_at_infinity(group, b))
return EC_POINT_copy(r, a);
{
return 0;
}
/* Note that in this function we must not read components of 'a' or 'b'
* once we have written the corresponding components of 'r'.
* ('r' might be one of 'a' or 'b'.)
*/
/* n1, n2 */
if (b->Z_is_one)
{
/* n1 = X_a */
/* n2 = Y_a */
}
else
{
/* n1 = X_a * Z_b^2 */
/* n2 = Y_a * Z_b^3 */
}
/* n3, n4 */
if (a->Z_is_one)
{
/* n3 = X_b */
/* n4 = Y_b */
}
else
{
/* n3 = X_b * Z_a^2 */
/* n4 = Y_b * Z_a^3 */
}
/* n5, n6 */
/* n5 = n1 - n3 */
/* n6 = n2 - n4 */
if (BN_is_zero(n5))
{
if (BN_is_zero(n6))
{
/* a is the same point as b */
goto end;
}
else
{
/* a is the inverse of b */
BN_zero(&r->Z);
r->Z_is_one = 0;
ret = 1;
goto end;
}
}
/* 'n7', 'n8' */
/* 'n7' = n1 + n3 */
/* 'n8' = n2 + n4 */
/* Z_r */
{
}
else
{
if (a->Z_is_one)
else if (b->Z_is_one)
else
}
r->Z_is_one = 0;
/* Z_r = Z_a * Z_b * n5 */
/* X_r */
/* X_r = n6^2 - n5^2 * 'n7' */
/* 'n9' */
/* n9 = n5^2 * 'n7' - 2 * X_r */
/* Y_r */
/* now 0 <= n0 < 2*p, and n0 is even */
/* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
ret = 1;
end:
if (ctx) /* otherwise we already called BN_CTX_end */
return ret;
}
{
const BIGNUM *p;
int ret = 0;
if (EC_POINT_is_at_infinity(group, a))
{
BN_zero(&r->Z);
r->Z_is_one = 0;
return 1;
}
{
return 0;
}
/* Note that in this function we must not read components of 'a'
* once we have written the corresponding components of 'r'.
* ('r' might the same as 'a'.)
*/
/* n1 */
if (a->Z_is_one)
{
/* n1 = 3 * X_a^2 + a_curve */
}
else if (group->a_is_minus3)
{
/* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
* = 3 * X_a^2 - 3 * Z_a^4 */
}
else
{
/* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
}
/* Z_r */
if (a->Z_is_one)
{
}
else
{
}
r->Z_is_one = 0;
/* Z_r = 2 * Y_a * Z_a */
/* n2 */
/* n2 = 4 * X_a * Y_a^2 */
/* X_r */
/* X_r = n1^2 - 2 * n2 */
/* n3 */
/* n3 = 8 * Y_a^4 */
/* Y_r */
/* Y_r = n1 * (n2 - X_r) - n3 */
ret = 1;
err:
return ret;
}
{
/* point is its own inverse */
return 1;
}
{
return BN_is_zero(&point->Z);
}
{
const BIGNUM *p;
int ret = -1;
return 1;
{
return -1;
}
/* We have a curve defined by a Weierstrass equation
* y^2 = x^3 + a*x + b.
* The point to consider is given in Jacobian projective coordinates
* where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
* Substituting this and multiplying by Z^6 transforms the above equation into
* Y^2 = X^3 + a*X*Z^4 + b*Z^6.
* To test this, we add up the right-hand side in 'rh'.
*/
/* rh := X^2 */
{
/* rh := (rh + a*Z^4)*X */
if (group->a_is_minus3)
{
}
else
{
}
/* rh := rh + b*Z^6 */
}
else
{
/* point->Z_is_one */
/* rh := (rh + a)*X */
/* rh := rh + b */
}
/* 'lh' := Y^2 */
err:
return ret;
}
{
/* return values:
* -1 error
* 0 equal (in affine coordinates)
* 1 not equal
*/
int ret = -1;
if (EC_POINT_is_at_infinity(group, a))
{
}
{
}
{
return -1;
}
/* We have to decide whether
* or equivalently, whether
* (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
*/
if (!b->Z_is_one)
{
}
else
tmp1_ = &a->X;
if (!a->Z_is_one)
{
}
else
tmp2_ = &b->X;
/* compare X_a*Z_b^2 with X_b*Z_a^2 */
{
goto end;
}
if (!b->Z_is_one)
{
/* tmp1_ = tmp1 */
}
else
tmp1_ = &a->Y;
if (!a->Z_is_one)
{
/* tmp2_ = tmp2 */
}
else
tmp2_ = &b->Y;
/* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
{
goto end;
}
/* points are equal */
ret = 0;
end:
return ret;
}
{
BIGNUM *x, *y;
int ret = 0;
return 1;
{
return 0;
}
x = BN_CTX_get(ctx);
y = BN_CTX_get(ctx);
{
goto err;
}
ret = 1;
err:
return ret;
}
int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
{
size_t i;
int ret = 0;
if (num == 0)
return 1;
{
return 0;
}
/* Before converting the individual points, compute inverses of all Z values.
* Modular inversion is rather slow, but luckily we can do with a single
* explicit inversion, plus about 3 multiplications per input value.
*/
pow2 = 1;
pow2 <<= 1;
/* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
* We need twice that. */
pow2 <<= 1;
/* The array is used as a binary tree, exactly as in heapsort:
*
* heap[1]
* heap[2] heap[3]
* heap[4] heap[5] heap[6] heap[7]
* heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
*
* We put the Z's in the last line;
* then we set each other node to the product of its two child-nodes (where
* empty or 0 entries are treated as ones);
* then we invert heap[1];
* then we invert each other node by replacing it by the product of its
* parent (after inversion) and its sibling (before inversion).
*/
for (i = 0; i < num; i++)
/* set each node to the product of its children */
{
{
{
}
else
{
{
}
else
{
}
}
}
}
/* invert heap[1] */
{
{
goto err;
}
}
{
/* in the Montgomery case, we just turned R*H (representing H)
* into 1/(R*H), but we need R*(1/H) (representing 1/H);
* i.e. we have need to multiply by the Montgomery factor twice */
}
/* set other heap[i]'s to their inverses */
{
/* i is even */
{
}
else
{
}
}
/* we have replaced all non-zero Z's by their inverses, now fix up all the points */
for (i = 0; i < num; i++)
{
if (!BN_is_zero(&p->Z))
{
/* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
{
}
else
{
}
p->Z_is_one = 1;
}
}
ret = 1;
err:
{
/* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
{
BN_clear_free(heap[i]);
}
}
return ret;
}
int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
{
}
{
}