• file
• revisions
• annotate
• diff
• comparison
• raw

security/nss/lib/freebl/ecl/ec2_mont.c@b8a032363ba2 (annotated)

security/nss/lib/freebl/ecl/ec2_mont.c

Thu, 22 Jan 2015 13:21:57 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Thu, 22 Jan 2015 13:21:57 +0100

branch

TOR_BUG_9701

changeset 15

b8a032363ba2

permissions

-rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

michael@0	1	/* This Source Code Form is subject to the terms of the Mozilla Public
michael@0	2	* License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0	3	* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0	4
michael@0	5	#include "ec2.h"
michael@0	6	#include "mplogic.h"
michael@0	7	#include "mp_gf2m.h"
michael@0	8	#include <stdlib.h>
michael@0	9
michael@0	10	/* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery
michael@0	11	* projective coordinates. Uses algorithm Mdouble in appendix of Lopez, J.
michael@0	12	* and Dahab, R. "Fast multiplication on elliptic curves over GF(2^m)
michael@0	13	* without precomputation". modified to not require precomputation of
michael@0	14	* c=b^{2^{m-1}}. */
michael@0	15	static mp_err
michael@0	16	gf2m_Mdouble(mp_int *x, mp_int *z, const ECGroup *group)
michael@0	17	{
michael@0	18	mp_err res = MP_OKAY;
michael@0	19	mp_int t1;
michael@0	20
michael@0	21	MP_DIGITS(&t1) = 0;
michael@0	22	MP_CHECKOK(mp_init(&t1));
michael@0	23
michael@0	24	MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));
michael@0	25	MP_CHECKOK(group->meth->field_sqr(z, &t1, group->meth));
michael@0	26	MP_CHECKOK(group->meth->field_mul(x, &t1, z, group->meth));
michael@0	27	MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));
michael@0	28	MP_CHECKOK(group->meth->field_sqr(&t1, &t1, group->meth));
michael@0	29	MP_CHECKOK(group->meth->
michael@0	30	field_mul(&group->curveb, &t1, &t1, group->meth));
michael@0	31	MP_CHECKOK(group->meth->field_add(x, &t1, x, group->meth));
michael@0	32
michael@0	33	CLEANUP:
michael@0	34	mp_clear(&t1);
michael@0	35	return res;
michael@0	36	}
michael@0	37
michael@0	38	/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in
michael@0	39	* Montgomery projective coordinates. Uses algorithm Madd in appendix of
michael@0	40	* Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over
michael@0	41	* GF(2^m) without precomputation". */
michael@0	42	static mp_err
michael@0	43	gf2m_Madd(const mp_int *x, mp_int *x1, mp_int *z1, mp_int *x2, mp_int *z2,
michael@0	44	const ECGroup *group)
michael@0	45	{
michael@0	46	mp_err res = MP_OKAY;
michael@0	47	mp_int t1, t2;
michael@0	48
michael@0	49	MP_DIGITS(&t1) = 0;
michael@0	50	MP_DIGITS(&t2) = 0;
michael@0	51	MP_CHECKOK(mp_init(&t1));
michael@0	52	MP_CHECKOK(mp_init(&t2));
michael@0	53
michael@0	54	MP_CHECKOK(mp_copy(x, &t1));
michael@0	55	MP_CHECKOK(group->meth->field_mul(x1, z2, x1, group->meth));
michael@0	56	MP_CHECKOK(group->meth->field_mul(z1, x2, z1, group->meth));
michael@0	57	MP_CHECKOK(group->meth->field_mul(x1, z1, &t2, group->meth));
michael@0	58	MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));
michael@0	59	MP_CHECKOK(group->meth->field_sqr(z1, z1, group->meth));
michael@0	60	MP_CHECKOK(group->meth->field_mul(z1, &t1, x1, group->meth));
michael@0	61	MP_CHECKOK(group->meth->field_add(x1, &t2, x1, group->meth));
michael@0	62
michael@0	63	CLEANUP:
michael@0	64	mp_clear(&t1);
michael@0	65	mp_clear(&t2);
michael@0	66	return res;
michael@0	67	}
michael@0	68
michael@0	69	/* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)
michael@0	70	* using Montgomery point multiplication algorithm Mxy() in appendix of
michael@0	71	* Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over
michael@0	72	* GF(2^m) without precomputation". Returns: 0 on error 1 if return value
michael@0	73	* should be the point at infinity 2 otherwise */
michael@0	74	static int
michael@0	75	gf2m_Mxy(const mp_int *x, const mp_int *y, mp_int *x1, mp_int *z1,
michael@0	76	mp_int *x2, mp_int *z2, const ECGroup *group)
michael@0	77	{
michael@0	78	mp_err res = MP_OKAY;
michael@0	79	int ret = 0;
michael@0	80	mp_int t3, t4, t5;
michael@0	81
michael@0	82	MP_DIGITS(&t3) = 0;
michael@0	83	MP_DIGITS(&t4) = 0;
michael@0	84	MP_DIGITS(&t5) = 0;
michael@0	85	MP_CHECKOK(mp_init(&t3));
michael@0	86	MP_CHECKOK(mp_init(&t4));
michael@0	87	MP_CHECKOK(mp_init(&t5));
michael@0	88
michael@0	89	if (mp_cmp_z(z1) == 0) {
michael@0	90	mp_zero(x2);
michael@0	91	mp_zero(z2);
michael@0	92	ret = 1;
michael@0	93	goto CLEANUP;
michael@0	94	}
michael@0	95
michael@0	96	if (mp_cmp_z(z2) == 0) {
michael@0	97	MP_CHECKOK(mp_copy(x, x2));
michael@0	98	MP_CHECKOK(group->meth->field_add(x, y, z2, group->meth));
michael@0	99	ret = 2;
michael@0	100	goto CLEANUP;
michael@0	101	}
michael@0	102
michael@0	103	MP_CHECKOK(mp_set_int(&t5, 1));
michael@0	104	if (group->meth->field_enc) {
michael@0	105	MP_CHECKOK(group->meth->field_enc(&t5, &t5, group->meth));
michael@0	106	}
michael@0	107
michael@0	108	MP_CHECKOK(group->meth->field_mul(z1, z2, &t3, group->meth));
michael@0	109
michael@0	110	MP_CHECKOK(group->meth->field_mul(z1, x, z1, group->meth));
michael@0	111	MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));
michael@0	112	MP_CHECKOK(group->meth->field_mul(z2, x, z2, group->meth));
michael@0	113	MP_CHECKOK(group->meth->field_mul(z2, x1, x1, group->meth));
michael@0	114	MP_CHECKOK(group->meth->field_add(z2, x2, z2, group->meth));
michael@0	115
michael@0	116	MP_CHECKOK(group->meth->field_mul(z2, z1, z2, group->meth));
michael@0	117	MP_CHECKOK(group->meth->field_sqr(x, &t4, group->meth));
michael@0	118	MP_CHECKOK(group->meth->field_add(&t4, y, &t4, group->meth));
michael@0	119	MP_CHECKOK(group->meth->field_mul(&t4, &t3, &t4, group->meth));
michael@0	120	MP_CHECKOK(group->meth->field_add(&t4, z2, &t4, group->meth));
michael@0	121
michael@0	122	MP_CHECKOK(group->meth->field_mul(&t3, x, &t3, group->meth));
michael@0	123	MP_CHECKOK(group->meth->field_div(&t5, &t3, &t3, group->meth));
michael@0	124	MP_CHECKOK(group->meth->field_mul(&t3, &t4, &t4, group->meth));
michael@0	125	MP_CHECKOK(group->meth->field_mul(x1, &t3, x2, group->meth));
michael@0	126	MP_CHECKOK(group->meth->field_add(x2, x, z2, group->meth));
michael@0	127
michael@0	128	MP_CHECKOK(group->meth->field_mul(z2, &t4, z2, group->meth));
michael@0	129	MP_CHECKOK(group->meth->field_add(z2, y, z2, group->meth));
michael@0	130
michael@0	131	ret = 2;
michael@0	132
michael@0	133	CLEANUP:
michael@0	134	mp_clear(&t3);
michael@0	135	mp_clear(&t4);
michael@0	136	mp_clear(&t5);
michael@0	137	if (res == MP_OKAY) {
michael@0	138	return ret;
michael@0	139	} else {
michael@0	140	return 0;
michael@0	141	}
michael@0	142	}
michael@0	143
michael@0	144	/* Computes R = nP based on algorithm 2P of Lopex, J. and Dahab, R. "Fast
michael@0	145	* multiplication on elliptic curves over GF(2^m) without
michael@0	146	* precomputation". Elliptic curve points P and R can be identical. Uses
michael@0	147	* Montgomery projective coordinates. */
michael@0	148	mp_err
michael@0	149	ec_GF2m_pt_mul_mont(const mp_int *n, const mp_int *px, const mp_int *py,
michael@0	150	mp_int *rx, mp_int *ry, const ECGroup *group)
michael@0	151	{
michael@0	152	mp_err res = MP_OKAY;
michael@0	153	mp_int x1, x2, z1, z2;
michael@0	154	int i, j;
michael@0	155	mp_digit top_bit, mask;
michael@0	156
michael@0	157	MP_DIGITS(&x1) = 0;
michael@0	158	MP_DIGITS(&x2) = 0;
michael@0	159	MP_DIGITS(&z1) = 0;
michael@0	160	MP_DIGITS(&z2) = 0;
michael@0	161	MP_CHECKOK(mp_init(&x1));
michael@0	162	MP_CHECKOK(mp_init(&x2));
michael@0	163	MP_CHECKOK(mp_init(&z1));
michael@0	164	MP_CHECKOK(mp_init(&z2));
michael@0	165
michael@0	166	/* if result should be point at infinity */
michael@0	167	if ((mp_cmp_z(n) == 0) || (ec_GF2m_pt_is_inf_aff(px, py) == MP_YES)) {
michael@0	168	MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
michael@0	169	goto CLEANUP;
michael@0	170	}
michael@0	171
michael@0	172	MP_CHECKOK(mp_copy(px, &x1)); /* x1 = px */
michael@0	173	MP_CHECKOK(mp_set_int(&z1, 1)); /* z1 = 1 */
michael@0	174	MP_CHECKOK(group->meth->field_sqr(&x1, &z2, group->meth)); /* z2 =
michael@0	175	* x1^2 =
michael@0	176	* px^2 */
michael@0	177	MP_CHECKOK(group->meth->field_sqr(&z2, &x2, group->meth));
michael@0	178	MP_CHECKOK(group->meth->field_add(&x2, &group->curveb, &x2, group->meth)); /* x2
michael@0	179	* =
michael@0	180	* px^4
michael@0	181	* +
michael@0	182	* b
michael@0	183	*/
michael@0	184
michael@0	185	/* find top-most bit and go one past it */
michael@0	186	i = MP_USED(n) - 1;
michael@0	187	j = MP_DIGIT_BIT - 1;
michael@0	188	top_bit = 1;
michael@0	189	top_bit <<= MP_DIGIT_BIT - 1;
michael@0	190	mask = top_bit;
michael@0	191	while (!(MP_DIGITS(n)[i] & mask)) {
michael@0	192	mask >>= 1;
michael@0	193	j--;
michael@0	194	}
michael@0	195	mask >>= 1;
michael@0	196	j--;
michael@0	197
michael@0	198	/* if top most bit was at word break, go to next word */
michael@0	199	if (!mask) {
michael@0	200	i--;
michael@0	201	j = MP_DIGIT_BIT - 1;
michael@0	202	mask = top_bit;
michael@0	203	}
michael@0	204
michael@0	205	for (; i >= 0; i--) {
michael@0	206	for (; j >= 0; j--) {
michael@0	207	if (MP_DIGITS(n)[i] & mask) {
michael@0	208	MP_CHECKOK(gf2m_Madd(px, &x1, &z1, &x2, &z2, group));
michael@0	209	MP_CHECKOK(gf2m_Mdouble(&x2, &z2, group));
michael@0	210	} else {
michael@0	211	MP_CHECKOK(gf2m_Madd(px, &x2, &z2, &x1, &z1, group));
michael@0	212	MP_CHECKOK(gf2m_Mdouble(&x1, &z1, group));
michael@0	213	}
michael@0	214	mask >>= 1;
michael@0	215	}
michael@0	216	j = MP_DIGIT_BIT - 1;
michael@0	217	mask = top_bit;
michael@0	218	}
michael@0	219
michael@0	220	/* convert out of "projective" coordinates */
michael@0	221	i = gf2m_Mxy(px, py, &x1, &z1, &x2, &z2, group);
michael@0	222	if (i == 0) {
michael@0	223	res = MP_BADARG;
michael@0	224	goto CLEANUP;
michael@0	225	} else if (i == 1) {
michael@0	226	MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
michael@0	227	} else {
michael@0	228	MP_CHECKOK(mp_copy(&x2, rx));
michael@0	229	MP_CHECKOK(mp_copy(&z2, ry));
michael@0	230	}
michael@0	231
michael@0	232	CLEANUP:
michael@0	233	mp_clear(&x1);
michael@0	234	mp_clear(&x2);
michael@0	235	mp_clear(&z1);
michael@0	236	mp_clear(&z2);
michael@0	237	return res;
michael@0	238	}