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

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

security/nss/lib/freebl/ecl/ec2_193.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 "mp_gf2m.h"
michael@0	7	#include "mp_gf2m-priv.h"
michael@0	8	#include "mpi.h"
michael@0	9	#include "mpi-priv.h"
michael@0	10	#include <stdlib.h>
michael@0	11
michael@0	12	/* Fast reduction for polynomials over a 193-bit curve. Assumes reduction
michael@0	13	* polynomial with terms {193, 15, 0}. */
michael@0	14	mp_err
michael@0	15	ec_GF2m_193_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
michael@0	16	{
michael@0	17	mp_err res = MP_OKAY;
michael@0	18	mp_digit *u, z;
michael@0	19
michael@0	20	if (a != r) {
michael@0	21	MP_CHECKOK(mp_copy(a, r));
michael@0	22	}
michael@0	23	#ifdef ECL_SIXTY_FOUR_BIT
michael@0	24	if (MP_USED(r) < 7) {
michael@0	25	MP_CHECKOK(s_mp_pad(r, 7));
michael@0	26	}
michael@0	27	u = MP_DIGITS(r);
michael@0	28	MP_USED(r) = 7;
michael@0	29
michael@0	30	/* u[6] only has 2 significant bits */
michael@0	31	z = u[6];
michael@0	32	u[3] ^= (z << 14) ^ (z >> 1);
michael@0	33	u[2] ^= (z << 63);
michael@0	34	z = u[5];
michael@0	35	u[3] ^= (z >> 50);
michael@0	36	u[2] ^= (z << 14) ^ (z >> 1);
michael@0	37	u[1] ^= (z << 63);
michael@0	38	z = u[4];
michael@0	39	u[2] ^= (z >> 50);
michael@0	40	u[1] ^= (z << 14) ^ (z >> 1);
michael@0	41	u[0] ^= (z << 63);
michael@0	42	z = u[3] >> 1; /* z only has 63 significant bits */
michael@0	43	u[1] ^= (z >> 49);
michael@0	44	u[0] ^= (z << 15) ^ z;
michael@0	45	/* clear bits above 193 */
michael@0	46	u[6] = u[5] = u[4] = 0;
michael@0	47	u[3] ^= z << 1;
michael@0	48	#else
michael@0	49	if (MP_USED(r) < 13) {
michael@0	50	MP_CHECKOK(s_mp_pad(r, 13));
michael@0	51	}
michael@0	52	u = MP_DIGITS(r);
michael@0	53	MP_USED(r) = 13;
michael@0	54
michael@0	55	/* u[12] only has 2 significant bits */
michael@0	56	z = u[12];
michael@0	57	u[6] ^= (z << 14) ^ (z >> 1);
michael@0	58	u[5] ^= (z << 31);
michael@0	59	z = u[11];
michael@0	60	u[6] ^= (z >> 18);
michael@0	61	u[5] ^= (z << 14) ^ (z >> 1);
michael@0	62	u[4] ^= (z << 31);
michael@0	63	z = u[10];
michael@0	64	u[5] ^= (z >> 18);
michael@0	65	u[4] ^= (z << 14) ^ (z >> 1);
michael@0	66	u[3] ^= (z << 31);
michael@0	67	z = u[9];
michael@0	68	u[4] ^= (z >> 18);
michael@0	69	u[3] ^= (z << 14) ^ (z >> 1);
michael@0	70	u[2] ^= (z << 31);
michael@0	71	z = u[8];
michael@0	72	u[3] ^= (z >> 18);
michael@0	73	u[2] ^= (z << 14) ^ (z >> 1);
michael@0	74	u[1] ^= (z << 31);
michael@0	75	z = u[7];
michael@0	76	u[2] ^= (z >> 18);
michael@0	77	u[1] ^= (z << 14) ^ (z >> 1);
michael@0	78	u[0] ^= (z << 31);
michael@0	79	z = u[6] >> 1; /* z only has 31 significant bits */
michael@0	80	u[1] ^= (z >> 17);
michael@0	81	u[0] ^= (z << 15) ^ z;
michael@0	82	/* clear bits above 193 */
michael@0	83	u[12] = u[11] = u[10] = u[9] = u[8] = u[7] = 0;
michael@0	84	u[6] ^= z << 1;
michael@0	85	#endif
michael@0	86	s_mp_clamp(r);
michael@0	87
michael@0	88	CLEANUP:
michael@0	89	return res;
michael@0	90	}
michael@0	91
michael@0	92	/* Fast squaring for polynomials over a 193-bit curve. Assumes reduction
michael@0	93	* polynomial with terms {193, 15, 0}. */
michael@0	94	mp_err
michael@0	95	ec_GF2m_193_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
michael@0	96	{
michael@0	97	mp_err res = MP_OKAY;
michael@0	98	mp_digit *u, *v;
michael@0	99
michael@0	100	v = MP_DIGITS(a);
michael@0	101
michael@0	102	#ifdef ECL_SIXTY_FOUR_BIT
michael@0	103	if (MP_USED(a) < 4) {
michael@0	104	return mp_bsqrmod(a, meth->irr_arr, r);
michael@0	105	}
michael@0	106	if (MP_USED(r) < 7) {
michael@0	107	MP_CHECKOK(s_mp_pad(r, 7));
michael@0	108	}
michael@0	109	MP_USED(r) = 7;
michael@0	110	#else
michael@0	111	if (MP_USED(a) < 7) {
michael@0	112	return mp_bsqrmod(a, meth->irr_arr, r);
michael@0	113	}
michael@0	114	if (MP_USED(r) < 13) {
michael@0	115	MP_CHECKOK(s_mp_pad(r, 13));
michael@0	116	}
michael@0	117	MP_USED(r) = 13;
michael@0	118	#endif
michael@0	119	u = MP_DIGITS(r);
michael@0	120
michael@0	121	#ifdef ECL_THIRTY_TWO_BIT
michael@0	122	u[12] = gf2m_SQR0(v[6]);
michael@0	123	u[11] = gf2m_SQR1(v[5]);
michael@0	124	u[10] = gf2m_SQR0(v[5]);
michael@0	125	u[9] = gf2m_SQR1(v[4]);
michael@0	126	u[8] = gf2m_SQR0(v[4]);
michael@0	127	u[7] = gf2m_SQR1(v[3]);
michael@0	128	#endif
michael@0	129	u[6] = gf2m_SQR0(v[3]);
michael@0	130	u[5] = gf2m_SQR1(v[2]);
michael@0	131	u[4] = gf2m_SQR0(v[2]);
michael@0	132	u[3] = gf2m_SQR1(v[1]);
michael@0	133	u[2] = gf2m_SQR0(v[1]);
michael@0	134	u[1] = gf2m_SQR1(v[0]);
michael@0	135	u[0] = gf2m_SQR0(v[0]);
michael@0	136	return ec_GF2m_193_mod(r, r, meth);
michael@0	137
michael@0	138	CLEANUP:
michael@0	139	return res;
michael@0	140	}
michael@0	141
michael@0	142	/* Fast multiplication for polynomials over a 193-bit curve. Assumes
michael@0	143	* reduction polynomial with terms {193, 15, 0}. */
michael@0	144	mp_err
michael@0	145	ec_GF2m_193_mul(const mp_int *a, const mp_int *b, mp_int *r,
michael@0	146	const GFMethod *meth)
michael@0	147	{
michael@0	148	mp_err res = MP_OKAY;
michael@0	149	mp_digit a3 = 0, a2 = 0, a1 = 0, a0, b3 = 0, b2 = 0, b1 = 0, b0;
michael@0	150
michael@0	151	#ifdef ECL_THIRTY_TWO_BIT
michael@0	152	mp_digit a6 = 0, a5 = 0, a4 = 0, b6 = 0, b5 = 0, b4 = 0;
michael@0	153	mp_digit rm[8];
michael@0	154	#endif
michael@0	155
michael@0	156	if (a == b) {
michael@0	157	return ec_GF2m_193_sqr(a, r, meth);
michael@0	158	} else {
michael@0	159	switch (MP_USED(a)) {
michael@0	160	#ifdef ECL_THIRTY_TWO_BIT
michael@0	161	case 7:
michael@0	162	a6 = MP_DIGIT(a, 6);
michael@0	163	case 6:
michael@0	164	a5 = MP_DIGIT(a, 5);
michael@0	165	case 5:
michael@0	166	a4 = MP_DIGIT(a, 4);
michael@0	167	#endif
michael@0	168	case 4:
michael@0	169	a3 = MP_DIGIT(a, 3);
michael@0	170	case 3:
michael@0	171	a2 = MP_DIGIT(a, 2);
michael@0	172	case 2:
michael@0	173	a1 = MP_DIGIT(a, 1);
michael@0	174	default:
michael@0	175	a0 = MP_DIGIT(a, 0);
michael@0	176	}
michael@0	177	switch (MP_USED(b)) {
michael@0	178	#ifdef ECL_THIRTY_TWO_BIT
michael@0	179	case 7:
michael@0	180	b6 = MP_DIGIT(b, 6);
michael@0	181	case 6:
michael@0	182	b5 = MP_DIGIT(b, 5);
michael@0	183	case 5:
michael@0	184	b4 = MP_DIGIT(b, 4);
michael@0	185	#endif
michael@0	186	case 4:
michael@0	187	b3 = MP_DIGIT(b, 3);
michael@0	188	case 3:
michael@0	189	b2 = MP_DIGIT(b, 2);
michael@0	190	case 2:
michael@0	191	b1 = MP_DIGIT(b, 1);
michael@0	192	default:
michael@0	193	b0 = MP_DIGIT(b, 0);
michael@0	194	}
michael@0	195	#ifdef ECL_SIXTY_FOUR_BIT
michael@0	196	MP_CHECKOK(s_mp_pad(r, 8));
michael@0	197	s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0);
michael@0	198	MP_USED(r) = 8;
michael@0	199	s_mp_clamp(r);
michael@0	200	#else
michael@0	201	MP_CHECKOK(s_mp_pad(r, 14));
michael@0	202	s_bmul_3x3(MP_DIGITS(r) + 8, a6, a5, a4, b6, b5, b4);
michael@0	203	s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0);
michael@0	204	s_bmul_4x4(rm, a3, a6 ^ a2, a5 ^ a1, a4 ^ a0, b3, b6 ^ b2, b5 ^ b1,
michael@0	205	b4 ^ b0);
michael@0	206	rm[7] ^= MP_DIGIT(r, 7);
michael@0	207	rm[6] ^= MP_DIGIT(r, 6);
michael@0	208	rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 13);
michael@0	209	rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 12);
michael@0	210	rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 11);
michael@0	211	rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 10);
michael@0	212	rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 9);
michael@0	213	rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 8);
michael@0	214	MP_DIGIT(r, 11) ^= rm[7];
michael@0	215	MP_DIGIT(r, 10) ^= rm[6];
michael@0	216	MP_DIGIT(r, 9) ^= rm[5];
michael@0	217	MP_DIGIT(r, 8) ^= rm[4];
michael@0	218	MP_DIGIT(r, 7) ^= rm[3];
michael@0	219	MP_DIGIT(r, 6) ^= rm[2];
michael@0	220	MP_DIGIT(r, 5) ^= rm[1];
michael@0	221	MP_DIGIT(r, 4) ^= rm[0];
michael@0	222	MP_USED(r) = 14;
michael@0	223	s_mp_clamp(r);
michael@0	224	#endif
michael@0	225	return ec_GF2m_193_mod(r, r, meth);
michael@0	226	}
michael@0	227
michael@0	228	CLEANUP:
michael@0	229	return res;
michael@0	230	}
michael@0	231
michael@0	232	/* Wire in fast field arithmetic for 193-bit curves. */
michael@0	233	mp_err
michael@0	234	ec_group_set_gf2m193(ECGroup *group, ECCurveName name)
michael@0	235	{
michael@0	236	group->meth->field_mod = &ec_GF2m_193_mod;
michael@0	237	group->meth->field_mul = &ec_GF2m_193_mul;
michael@0	238	group->meth->field_sqr = &ec_GF2m_193_sqr;
michael@0	239	return MP_OKAY;
michael@0	240	}