1 /* crypto/ec/ecp_oct.c */
2 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3 * for the OpenSSL project.
4 * Includes code written by Bodo Moeller for the OpenSSL project.
6 /* ====================================================================
7 * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in
18 * the documentation and/or other materials provided with the
21 * 3. All advertising materials mentioning features or use of this
22 * software must display the following acknowledgment:
23 * "This product includes software developed by the OpenSSL Project
24 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
26 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27 * endorse or promote products derived from this software without
28 * prior written permission. For written permission, please contact
29 * openssl-core@openssl.org.
31 * 5. Products derived from this software may not be called "OpenSSL"
32 * nor may "OpenSSL" appear in their names without prior written
33 * permission of the OpenSSL Project.
35 * 6. Redistributions of any form whatsoever must retain the following
37 * "This product includes software developed by the OpenSSL Project
38 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
40 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
44 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51 * OF THE POSSIBILITY OF SUCH DAMAGE.
52 * ====================================================================
54 * This product includes cryptographic software written by Eric Young
55 * (eay@cryptsoft.com). This product includes software written by Tim
56 * Hudson (tjh@cryptsoft.com).
59 /* ====================================================================
60 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
61 * Portions of this software developed by SUN MICROSYSTEMS, INC.,
62 * and contributed to the OpenSSL project.
65 #include <openssl/err.h>
66 #include <openssl/symhacks.h>
70 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP
*group
, EC_POINT
*point
,
71 const BIGNUM
*x_
, int y_bit
, BN_CTX
*ctx
)
73 BN_CTX
*new_ctx
= NULL
;
74 BIGNUM
*tmp1
, *tmp2
, *x
, *y
;
77 /* clear error queue*/
82 ctx
= new_ctx
= BN_CTX_new();
90 tmp1
= BN_CTX_get(ctx
);
91 tmp2
= BN_CTX_get(ctx
);
94 if (y
== NULL
) goto err
;
97 * Recover y. We have a Weierstrass equation
98 * y^2 = x^3 + a*x + b,
99 * so y is one of the square roots of x^3 + a*x + b.
103 if (!BN_nnmod(x
, x_
, group
->field
,ctx
)) goto err
;
104 if (group
->meth
->field_decode
== 0)
106 /* field_{sqr,mul} work on standard representation */
107 if (!group
->meth
->field_sqr(group
, tmp2
, x_
, ctx
)) goto err
;
108 if (!group
->meth
->field_mul(group
, tmp1
, tmp2
, x_
, ctx
)) goto err
;
112 if (!BN_mod_sqr(tmp2
, x_
, group
->field
, ctx
)) goto err
;
113 if (!BN_mod_mul(tmp1
, tmp2
, x_
, group
->field
, ctx
)) goto err
;
116 /* tmp1 := tmp1 + a*x */
117 if (group
->a_is_minus3
)
119 if (!BN_mod_lshift1_quick(tmp2
, x
, group
->field
)) goto err
;
120 if (!BN_mod_add_quick(tmp2
, tmp2
, x
, group
->field
)) goto err
;
121 if (!BN_mod_sub_quick(tmp1
, tmp1
, tmp2
, group
->field
)) goto err
;
125 if (group
->meth
->field_decode
)
127 if (!group
->meth
->field_decode(group
, tmp2
, group
->a
, ctx
)) goto err
;
128 if (!BN_mod_mul(tmp2
, tmp2
, x
, group
->field
, ctx
)) goto err
;
132 /* field_mul works on standard representation */
133 if (!group
->meth
->field_mul(group
, tmp2
, group
->a
, x
, ctx
)) goto err
;
136 if (!BN_mod_add_quick(tmp1
, tmp1
, tmp2
, group
->field
)) goto err
;
139 /* tmp1 := tmp1 + b */
140 if (group
->meth
->field_decode
)
142 if (!group
->meth
->field_decode(group
, tmp2
, group
->b
, ctx
)) goto err
;
143 if (!BN_mod_add_quick(tmp1
, tmp1
, tmp2
, group
->field
)) goto err
;
147 if (!BN_mod_add_quick(tmp1
, tmp1
, group
->b
, group
->field
)) goto err
;
150 if (!BN_mod_sqrt(y
, tmp1
, group
->field
, ctx
))
152 unsigned long err
= ERR_peek_last_error();
154 if (ERR_GET_LIB(err
) == ERR_LIB_BN
&& ERR_GET_REASON(err
) == BN_R_NOT_A_SQUARE
)
157 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES
, EC_R_INVALID_COMPRESSED_POINT
);
160 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES
, ERR_R_BN_LIB
);
164 if (y_bit
!= BN_is_odd(y
))
170 kron
= BN_kronecker(x
, group
->field
, ctx
);
171 if (kron
== -2) goto err
;
174 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES
, EC_R_INVALID_COMPRESSION_BIT
);
176 /* BN_mod_sqrt() should have cought this error (not a square) */
177 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES
, EC_R_INVALID_COMPRESSED_POINT
);
180 if (!BN_usub(y
, group
->field
, y
)) goto err
;
182 if (y_bit
!= BN_is_odd(y
))
184 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES
, ERR_R_INTERNAL_ERROR
);
188 if (!EC_POINT_set_affine_coordinates_GFp(group
, point
, x
, y
, ctx
)) goto err
;
195 BN_CTX_free(new_ctx
);
200 size_t ec_GFp_simple_point2oct(const EC_GROUP
*group
, const EC_POINT
*point
, point_conversion_form_t form
,
201 unsigned char *buf
, size_t len
, BN_CTX
*ctx
)
204 BN_CTX
*new_ctx
= NULL
;
207 size_t field_len
, i
, skip
;
209 if ((form
!= POINT_CONVERSION_COMPRESSED
)
210 && (form
!= POINT_CONVERSION_UNCOMPRESSED
)
211 && (form
!= POINT_CONVERSION_HYBRID
))
213 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT
, EC_R_INVALID_FORM
);
217 if (EC_POINT_is_at_infinity(group
, point
))
219 /* encodes to a single 0 octet */
224 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT
, EC_R_BUFFER_TOO_SMALL
);
233 /* ret := required output buffer length */
234 field_len
= BN_num_bytes(group
->field
);
235 ret
= (form
== POINT_CONVERSION_COMPRESSED
) ? 1 + field_len
: 1 + 2*field_len
;
237 /* if 'buf' is NULL, just return required length */
242 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT
, EC_R_BUFFER_TOO_SMALL
);
248 ctx
= new_ctx
= BN_CTX_new();
257 if (y
== NULL
) goto err
;
259 if (!EC_POINT_get_affine_coordinates_GFp(group
, point
, x
, y
, ctx
)) goto err
;
261 if ((form
== POINT_CONVERSION_COMPRESSED
|| form
== POINT_CONVERSION_HYBRID
) && BN_is_odd(y
))
268 skip
= field_len
- BN_num_bytes(x
);
269 if (skip
> field_len
)
271 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT
, ERR_R_INTERNAL_ERROR
);
279 skip
= BN_bn2bin(x
, buf
+ i
);
281 if (i
!= 1 + field_len
)
283 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT
, ERR_R_INTERNAL_ERROR
);
287 if (form
== POINT_CONVERSION_UNCOMPRESSED
|| form
== POINT_CONVERSION_HYBRID
)
289 skip
= field_len
- BN_num_bytes(y
);
290 if (skip
> field_len
)
292 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT
, ERR_R_INTERNAL_ERROR
);
300 skip
= BN_bn2bin(y
, buf
+ i
);
306 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT
, ERR_R_INTERNAL_ERROR
);
314 BN_CTX_free(new_ctx
);
321 BN_CTX_free(new_ctx
);
326 int ec_GFp_simple_oct2point(const EC_GROUP
*group
, EC_POINT
*point
,
327 const unsigned char *buf
, size_t len
, BN_CTX
*ctx
)
329 point_conversion_form_t form
;
331 BN_CTX
*new_ctx
= NULL
;
333 size_t field_len
, enc_len
;
338 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_BUFFER_TOO_SMALL
);
344 if ((form
!= 0) && (form
!= POINT_CONVERSION_COMPRESSED
)
345 && (form
!= POINT_CONVERSION_UNCOMPRESSED
)
346 && (form
!= POINT_CONVERSION_HYBRID
))
348 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_INVALID_ENCODING
);
351 if ((form
== 0 || form
== POINT_CONVERSION_UNCOMPRESSED
) && y_bit
)
353 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_INVALID_ENCODING
);
361 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_INVALID_ENCODING
);
365 return EC_POINT_set_to_infinity(group
, point
);
368 field_len
= BN_num_bytes(group
->field
);
369 enc_len
= (form
== POINT_CONVERSION_COMPRESSED
) ? 1 + field_len
: 1 + 2*field_len
;
373 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_INVALID_ENCODING
);
379 ctx
= new_ctx
= BN_CTX_new();
387 if (y
== NULL
) goto err
;
389 if (!BN_bin2bn(buf
+ 1, field_len
, x
)) goto err
;
390 if (BN_ucmp(x
, group
->field
) >= 0)
392 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_INVALID_ENCODING
);
396 if (form
== POINT_CONVERSION_COMPRESSED
)
398 if (!EC_POINT_set_compressed_coordinates_GFp(group
, point
, x
, y_bit
, ctx
)) goto err
;
402 if (!BN_bin2bn(buf
+ 1 + field_len
, field_len
, y
)) goto err
;
403 if (BN_ucmp(y
, group
->field
) >= 0)
405 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_INVALID_ENCODING
);
408 if (form
== POINT_CONVERSION_HYBRID
)
410 if (y_bit
!= BN_is_odd(y
))
412 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_INVALID_ENCODING
);
417 if (!EC_POINT_set_affine_coordinates_GFp(group
, point
, x
, y
, ctx
)) goto err
;
420 if (!EC_POINT_is_on_curve(group
, point
, ctx
)) /* test required by X9.62 */
422 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT
, EC_R_POINT_IS_NOT_ON_CURVE
);
431 BN_CTX_free(new_ctx
);