wolfSSL - wolfSSL SSL/TLS library, support up to TLS1.3

Users » wolfSSL » Code » wolfSSL

wolfSSL SSL/TLS library, support up to TLS1.3

Dependents: CyaSSL-Twitter-OAuth4Tw Example-client-tls-cert TwitterReader TweetTest ... more

wolfcrypt/src/tfm.c@0:d92f9d21154c, 2015-06-26 (annotated)

Committer:: wolfSSL
Date:: Fri Jun 26 00:39:20 2015 +0000
Revision:: 0:d92f9d21154c

wolfSSL 3.6.0

Who changed what in which revision?

User	Revision	Line number	New contents of line
wolfSSL	0:d92f9d21154c	1	/* tfm.c
wolfSSL	0:d92f9d21154c	2	*
wolfSSL	0:d92f9d21154c	3	* Copyright (C) 2006-2015 wolfSSL Inc.
wolfSSL	0:d92f9d21154c	4	*
wolfSSL	0:d92f9d21154c	5	* This file is part of wolfSSL. (formerly known as CyaSSL)
wolfSSL	0:d92f9d21154c	6	*
wolfSSL	0:d92f9d21154c	7	* wolfSSL is free software; you can redistribute it and/or modify
wolfSSL	0:d92f9d21154c	8	* it under the terms of the GNU General Public License as published by
wolfSSL	0:d92f9d21154c	9	* the Free Software Foundation; either version 2 of the License, or
wolfSSL	0:d92f9d21154c	10	* (at your option) any later version.
wolfSSL	0:d92f9d21154c	11	*
wolfSSL	0:d92f9d21154c	12	* wolfSSL is distributed in the hope that it will be useful,
wolfSSL	0:d92f9d21154c	13	* but WITHOUT ANY WARRANTY; without even the implied warranty of
wolfSSL	0:d92f9d21154c	14	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
wolfSSL	0:d92f9d21154c	15	* GNU General Public License for more details.
wolfSSL	0:d92f9d21154c	16	*
wolfSSL	0:d92f9d21154c	17	* You should have received a copy of the GNU General Public License
wolfSSL	0:d92f9d21154c	18	* along with this program; if not, write to the Free Software
wolfSSL	0:d92f9d21154c	19	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
wolfSSL	0:d92f9d21154c	20	*/
wolfSSL	0:d92f9d21154c	21
wolfSSL	0:d92f9d21154c	22
wolfSSL	0:d92f9d21154c	23	/*
wolfSSL	0:d92f9d21154c	24	* Based on public domain TomsFastMath 0.10 by Tom St Denis, tomstdenis@iahu.ca,
wolfSSL	0:d92f9d21154c	25	* http://math.libtomcrypt.com
wolfSSL	0:d92f9d21154c	26	*/
wolfSSL	0:d92f9d21154c	27
wolfSSL	0:d92f9d21154c	28	/**
wolfSSL	0:d92f9d21154c	29	* Edited by Moisés Guimarães (moisesguimaraesm@gmail.com)
wolfSSL	0:d92f9d21154c	30	* to fit CyaSSL's needs.
wolfSSL	0:d92f9d21154c	31	*/
wolfSSL	0:d92f9d21154c	32
wolfSSL	0:d92f9d21154c	33	#ifdef HAVE_CONFIG_H
wolfSSL	0:d92f9d21154c	34	#include <config.h>
wolfSSL	0:d92f9d21154c	35	#endif
wolfSSL	0:d92f9d21154c	36
wolfSSL	0:d92f9d21154c	37	/* in case user set USE_FAST_MATH there */
wolfSSL	0:d92f9d21154c	38	#include <wolfssl/wolfcrypt/settings.h>
wolfSSL	0:d92f9d21154c	39
wolfSSL	0:d92f9d21154c	40	#ifdef USE_FAST_MATH
wolfSSL	0:d92f9d21154c	41
wolfSSL	0:d92f9d21154c	42	#include <wolfssl/wolfcrypt/tfm.h>
wolfSSL	0:d92f9d21154c	43	#include <wolfcrypt/src/asm.c> /* will define asm MACROS or C ones */
wolfSSL	0:d92f9d21154c	44
wolfSSL	0:d92f9d21154c	45
wolfSSL	0:d92f9d21154c	46	/* math settings check */
wolfSSL	0:d92f9d21154c	47	word32 CheckRunTimeSettings(void)
wolfSSL	0:d92f9d21154c	48	{
wolfSSL	0:d92f9d21154c	49	return CTC_SETTINGS;
wolfSSL	0:d92f9d21154c	50	}
wolfSSL	0:d92f9d21154c	51
wolfSSL	0:d92f9d21154c	52
wolfSSL	0:d92f9d21154c	53	/* math settings size check */
wolfSSL	0:d92f9d21154c	54	word32 CheckRunTimeFastMath(void)
wolfSSL	0:d92f9d21154c	55	{
wolfSSL	0:d92f9d21154c	56	return FP_SIZE;
wolfSSL	0:d92f9d21154c	57	}
wolfSSL	0:d92f9d21154c	58
wolfSSL	0:d92f9d21154c	59
wolfSSL	0:d92f9d21154c	60	/* Functions */
wolfSSL	0:d92f9d21154c	61
wolfSSL	0:d92f9d21154c	62	void fp_add(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	63	{
wolfSSL	0:d92f9d21154c	64	int sa, sb;
wolfSSL	0:d92f9d21154c	65
wolfSSL	0:d92f9d21154c	66	/* get sign of both inputs */
wolfSSL	0:d92f9d21154c	67	sa = a->sign;
wolfSSL	0:d92f9d21154c	68	sb = b->sign;
wolfSSL	0:d92f9d21154c	69
wolfSSL	0:d92f9d21154c	70	/* handle two cases, not four */
wolfSSL	0:d92f9d21154c	71	if (sa == sb) {
wolfSSL	0:d92f9d21154c	72	/* both positive or both negative */
wolfSSL	0:d92f9d21154c	73	/* add their magnitudes, copy the sign */
wolfSSL	0:d92f9d21154c	74	c->sign = sa;
wolfSSL	0:d92f9d21154c	75	s_fp_add (a, b, c);
wolfSSL	0:d92f9d21154c	76	} else {
wolfSSL	0:d92f9d21154c	77	/* one positive, the other negative */
wolfSSL	0:d92f9d21154c	78	/* subtract the one with the greater magnitude from */
wolfSSL	0:d92f9d21154c	79	/* the one of the lesser magnitude. The result gets */
wolfSSL	0:d92f9d21154c	80	/* the sign of the one with the greater magnitude. */
wolfSSL	0:d92f9d21154c	81	if (fp_cmp_mag (a, b) == FP_LT) {
wolfSSL	0:d92f9d21154c	82	c->sign = sb;
wolfSSL	0:d92f9d21154c	83	s_fp_sub (b, a, c);
wolfSSL	0:d92f9d21154c	84	} else {
wolfSSL	0:d92f9d21154c	85	c->sign = sa;
wolfSSL	0:d92f9d21154c	86	s_fp_sub (a, b, c);
wolfSSL	0:d92f9d21154c	87	}
wolfSSL	0:d92f9d21154c	88	}
wolfSSL	0:d92f9d21154c	89	}
wolfSSL	0:d92f9d21154c	90
wolfSSL	0:d92f9d21154c	91	/* unsigned addition */
wolfSSL	0:d92f9d21154c	92	void s_fp_add(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	93	{
wolfSSL	0:d92f9d21154c	94	int x, y, oldused;
wolfSSL	0:d92f9d21154c	95	register fp_word t;
wolfSSL	0:d92f9d21154c	96
wolfSSL	0:d92f9d21154c	97	y = MAX(a->used, b->used);
wolfSSL	0:d92f9d21154c	98	oldused = MIN(c->used, FP_SIZE); /* help static analysis w/ largest size */
wolfSSL	0:d92f9d21154c	99	c->used = y;
wolfSSL	0:d92f9d21154c	100
wolfSSL	0:d92f9d21154c	101	t = 0;
wolfSSL	0:d92f9d21154c	102	for (x = 0; x < y; x++) {
wolfSSL	0:d92f9d21154c	103	t += ((fp_word)a->dp[x]) + ((fp_word)b->dp[x]);
wolfSSL	0:d92f9d21154c	104	c->dp[x] = (fp_digit)t;
wolfSSL	0:d92f9d21154c	105	t >>= DIGIT_BIT;
wolfSSL	0:d92f9d21154c	106	}
wolfSSL	0:d92f9d21154c	107	if (t != 0 && x < FP_SIZE) {
wolfSSL	0:d92f9d21154c	108	c->dp[c->used++] = (fp_digit)t;
wolfSSL	0:d92f9d21154c	109	++x;
wolfSSL	0:d92f9d21154c	110	}
wolfSSL	0:d92f9d21154c	111
wolfSSL	0:d92f9d21154c	112	c->used = x;
wolfSSL	0:d92f9d21154c	113	for (; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	114	c->dp[x] = 0;
wolfSSL	0:d92f9d21154c	115	}
wolfSSL	0:d92f9d21154c	116	fp_clamp(c);
wolfSSL	0:d92f9d21154c	117	}
wolfSSL	0:d92f9d21154c	118
wolfSSL	0:d92f9d21154c	119	/* c = a - b */
wolfSSL	0:d92f9d21154c	120	void fp_sub(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	121	{
wolfSSL	0:d92f9d21154c	122	int sa, sb;
wolfSSL	0:d92f9d21154c	123
wolfSSL	0:d92f9d21154c	124	sa = a->sign;
wolfSSL	0:d92f9d21154c	125	sb = b->sign;
wolfSSL	0:d92f9d21154c	126
wolfSSL	0:d92f9d21154c	127	if (sa != sb) {
wolfSSL	0:d92f9d21154c	128	/* subtract a negative from a positive, OR */
wolfSSL	0:d92f9d21154c	129	/* subtract a positive from a negative. */
wolfSSL	0:d92f9d21154c	130	/* In either case, ADD their magnitudes, */
wolfSSL	0:d92f9d21154c	131	/* and use the sign of the first number. */
wolfSSL	0:d92f9d21154c	132	c->sign = sa;
wolfSSL	0:d92f9d21154c	133	s_fp_add (a, b, c);
wolfSSL	0:d92f9d21154c	134	} else {
wolfSSL	0:d92f9d21154c	135	/* subtract a positive from a positive, OR */
wolfSSL	0:d92f9d21154c	136	/* subtract a negative from a negative. */
wolfSSL	0:d92f9d21154c	137	/* First, take the difference between their */
wolfSSL	0:d92f9d21154c	138	/* magnitudes, then... */
wolfSSL	0:d92f9d21154c	139	if (fp_cmp_mag (a, b) != FP_LT) {
wolfSSL	0:d92f9d21154c	140	/* Copy the sign from the first */
wolfSSL	0:d92f9d21154c	141	c->sign = sa;
wolfSSL	0:d92f9d21154c	142	/* The first has a larger or equal magnitude */
wolfSSL	0:d92f9d21154c	143	s_fp_sub (a, b, c);
wolfSSL	0:d92f9d21154c	144	} else {
wolfSSL	0:d92f9d21154c	145	/* The result has the opposite sign from */
wolfSSL	0:d92f9d21154c	146	/* the first number. */
wolfSSL	0:d92f9d21154c	147	c->sign = (sa == FP_ZPOS) ? FP_NEG : FP_ZPOS;
wolfSSL	0:d92f9d21154c	148	/* The second has a larger magnitude */
wolfSSL	0:d92f9d21154c	149	s_fp_sub (b, a, c);
wolfSSL	0:d92f9d21154c	150	}
wolfSSL	0:d92f9d21154c	151	}
wolfSSL	0:d92f9d21154c	152	}
wolfSSL	0:d92f9d21154c	153
wolfSSL	0:d92f9d21154c	154	/* unsigned subtraction \|\|a\|\| >= \|\|b\|\| ALWAYS! */
wolfSSL	0:d92f9d21154c	155	void s_fp_sub(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	156	{
wolfSSL	0:d92f9d21154c	157	int x, oldbused, oldused;
wolfSSL	0:d92f9d21154c	158	fp_word t;
wolfSSL	0:d92f9d21154c	159
wolfSSL	0:d92f9d21154c	160	oldused = c->used;
wolfSSL	0:d92f9d21154c	161	oldbused = b->used;
wolfSSL	0:d92f9d21154c	162	c->used = a->used;
wolfSSL	0:d92f9d21154c	163	t = 0;
wolfSSL	0:d92f9d21154c	164	for (x = 0; x < oldbused; x++) {
wolfSSL	0:d92f9d21154c	165	t = ((fp_word)a->dp[x]) - (((fp_word)b->dp[x]) + t);
wolfSSL	0:d92f9d21154c	166	c->dp[x] = (fp_digit)t;
wolfSSL	0:d92f9d21154c	167	t = (t >> DIGIT_BIT)&1;
wolfSSL	0:d92f9d21154c	168	}
wolfSSL	0:d92f9d21154c	169	for (; x < a->used; x++) {
wolfSSL	0:d92f9d21154c	170	t = ((fp_word)a->dp[x]) - t;
wolfSSL	0:d92f9d21154c	171	c->dp[x] = (fp_digit)t;
wolfSSL	0:d92f9d21154c	172	t = (t >> DIGIT_BIT)&1;
wolfSSL	0:d92f9d21154c	173	}
wolfSSL	0:d92f9d21154c	174	for (; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	175	c->dp[x] = 0;
wolfSSL	0:d92f9d21154c	176	}
wolfSSL	0:d92f9d21154c	177	fp_clamp(c);
wolfSSL	0:d92f9d21154c	178	}
wolfSSL	0:d92f9d21154c	179
wolfSSL	0:d92f9d21154c	180	/* c = a * b */
wolfSSL	0:d92f9d21154c	181	void fp_mul(fp_int A, fp_int B, fp_int *C)
wolfSSL	0:d92f9d21154c	182	{
wolfSSL	0:d92f9d21154c	183	int y, yy;
wolfSSL	0:d92f9d21154c	184
wolfSSL	0:d92f9d21154c	185	y = MAX(A->used, B->used);
wolfSSL	0:d92f9d21154c	186	yy = MIN(A->used, B->used);
wolfSSL	0:d92f9d21154c	187
wolfSSL	0:d92f9d21154c	188	/* call generic if we're out of range */
wolfSSL	0:d92f9d21154c	189	if (y + yy > FP_SIZE) {
wolfSSL	0:d92f9d21154c	190	fp_mul_comba(A, B, C);
wolfSSL	0:d92f9d21154c	191	return ;
wolfSSL	0:d92f9d21154c	192	}
wolfSSL	0:d92f9d21154c	193
wolfSSL	0:d92f9d21154c	194	/* pick a comba (unrolled 4/8/16/32 x or rolled) based on the size
wolfSSL	0:d92f9d21154c	195	of the largest input. We also want to avoid doing excess mults if the
wolfSSL	0:d92f9d21154c	196	inputs are not close to the next power of two. That is, for example,
wolfSSL	0:d92f9d21154c	197	if say y=17 then we would do (32-17)^2 = 225 unneeded multiplications
wolfSSL	0:d92f9d21154c	198	*/
wolfSSL	0:d92f9d21154c	199
wolfSSL	0:d92f9d21154c	200	#ifdef TFM_MUL3
wolfSSL	0:d92f9d21154c	201	if (y <= 3) {
wolfSSL	0:d92f9d21154c	202	fp_mul_comba3(A,B,C);
wolfSSL	0:d92f9d21154c	203	return;
wolfSSL	0:d92f9d21154c	204	}
wolfSSL	0:d92f9d21154c	205	#endif
wolfSSL	0:d92f9d21154c	206	#ifdef TFM_MUL4
wolfSSL	0:d92f9d21154c	207	if (y == 4) {
wolfSSL	0:d92f9d21154c	208	fp_mul_comba4(A,B,C);
wolfSSL	0:d92f9d21154c	209	return;
wolfSSL	0:d92f9d21154c	210	}
wolfSSL	0:d92f9d21154c	211	#endif
wolfSSL	0:d92f9d21154c	212	#ifdef TFM_MUL6
wolfSSL	0:d92f9d21154c	213	if (y <= 6) {
wolfSSL	0:d92f9d21154c	214	fp_mul_comba6(A,B,C);
wolfSSL	0:d92f9d21154c	215	return;
wolfSSL	0:d92f9d21154c	216	}
wolfSSL	0:d92f9d21154c	217	#endif
wolfSSL	0:d92f9d21154c	218	#ifdef TFM_MUL7
wolfSSL	0:d92f9d21154c	219	if (y == 7) {
wolfSSL	0:d92f9d21154c	220	fp_mul_comba7(A,B,C);
wolfSSL	0:d92f9d21154c	221	return;
wolfSSL	0:d92f9d21154c	222	}
wolfSSL	0:d92f9d21154c	223	#endif
wolfSSL	0:d92f9d21154c	224	#ifdef TFM_MUL8
wolfSSL	0:d92f9d21154c	225	if (y == 8) {
wolfSSL	0:d92f9d21154c	226	fp_mul_comba8(A,B,C);
wolfSSL	0:d92f9d21154c	227	return;
wolfSSL	0:d92f9d21154c	228	}
wolfSSL	0:d92f9d21154c	229	#endif
wolfSSL	0:d92f9d21154c	230	#ifdef TFM_MUL9
wolfSSL	0:d92f9d21154c	231	if (y == 9) {
wolfSSL	0:d92f9d21154c	232	fp_mul_comba9(A,B,C);
wolfSSL	0:d92f9d21154c	233	return;
wolfSSL	0:d92f9d21154c	234	}
wolfSSL	0:d92f9d21154c	235	#endif
wolfSSL	0:d92f9d21154c	236	#ifdef TFM_MUL12
wolfSSL	0:d92f9d21154c	237	if (y <= 12) {
wolfSSL	0:d92f9d21154c	238	fp_mul_comba12(A,B,C);
wolfSSL	0:d92f9d21154c	239	return;
wolfSSL	0:d92f9d21154c	240	}
wolfSSL	0:d92f9d21154c	241	#endif
wolfSSL	0:d92f9d21154c	242	#ifdef TFM_MUL17
wolfSSL	0:d92f9d21154c	243	if (y <= 17) {
wolfSSL	0:d92f9d21154c	244	fp_mul_comba17(A,B,C);
wolfSSL	0:d92f9d21154c	245	return;
wolfSSL	0:d92f9d21154c	246	}
wolfSSL	0:d92f9d21154c	247	#endif
wolfSSL	0:d92f9d21154c	248
wolfSSL	0:d92f9d21154c	249	#ifdef TFM_SMALL_SET
wolfSSL	0:d92f9d21154c	250	if (y <= 16) {
wolfSSL	0:d92f9d21154c	251	fp_mul_comba_small(A,B,C);
wolfSSL	0:d92f9d21154c	252	return;
wolfSSL	0:d92f9d21154c	253	}
wolfSSL	0:d92f9d21154c	254	#endif
wolfSSL	0:d92f9d21154c	255	#if defined(TFM_MUL20)
wolfSSL	0:d92f9d21154c	256	if (y <= 20) {
wolfSSL	0:d92f9d21154c	257	fp_mul_comba20(A,B,C);
wolfSSL	0:d92f9d21154c	258	return;
wolfSSL	0:d92f9d21154c	259	}
wolfSSL	0:d92f9d21154c	260	#endif
wolfSSL	0:d92f9d21154c	261	#if defined(TFM_MUL24)
wolfSSL	0:d92f9d21154c	262	if (yy >= 16 && y <= 24) {
wolfSSL	0:d92f9d21154c	263	fp_mul_comba24(A,B,C);
wolfSSL	0:d92f9d21154c	264	return;
wolfSSL	0:d92f9d21154c	265	}
wolfSSL	0:d92f9d21154c	266	#endif
wolfSSL	0:d92f9d21154c	267	#if defined(TFM_MUL28)
wolfSSL	0:d92f9d21154c	268	if (yy >= 20 && y <= 28) {
wolfSSL	0:d92f9d21154c	269	fp_mul_comba28(A,B,C);
wolfSSL	0:d92f9d21154c	270	return;
wolfSSL	0:d92f9d21154c	271	}
wolfSSL	0:d92f9d21154c	272	#endif
wolfSSL	0:d92f9d21154c	273	#if defined(TFM_MUL32)
wolfSSL	0:d92f9d21154c	274	if (yy >= 24 && y <= 32) {
wolfSSL	0:d92f9d21154c	275	fp_mul_comba32(A,B,C);
wolfSSL	0:d92f9d21154c	276	return;
wolfSSL	0:d92f9d21154c	277	}
wolfSSL	0:d92f9d21154c	278	#endif
wolfSSL	0:d92f9d21154c	279	#if defined(TFM_MUL48)
wolfSSL	0:d92f9d21154c	280	if (yy >= 40 && y <= 48) {
wolfSSL	0:d92f9d21154c	281	fp_mul_comba48(A,B,C);
wolfSSL	0:d92f9d21154c	282	return;
wolfSSL	0:d92f9d21154c	283	}
wolfSSL	0:d92f9d21154c	284	#endif
wolfSSL	0:d92f9d21154c	285	#if defined(TFM_MUL64)
wolfSSL	0:d92f9d21154c	286	if (yy >= 56 && y <= 64) {
wolfSSL	0:d92f9d21154c	287	fp_mul_comba64(A,B,C);
wolfSSL	0:d92f9d21154c	288	return;
wolfSSL	0:d92f9d21154c	289	}
wolfSSL	0:d92f9d21154c	290	#endif
wolfSSL	0:d92f9d21154c	291	fp_mul_comba(A,B,C);
wolfSSL	0:d92f9d21154c	292	}
wolfSSL	0:d92f9d21154c	293
wolfSSL	0:d92f9d21154c	294	void fp_mul_2(fp_int * a, fp_int * b)
wolfSSL	0:d92f9d21154c	295	{
wolfSSL	0:d92f9d21154c	296	int x, oldused;
wolfSSL	0:d92f9d21154c	297
wolfSSL	0:d92f9d21154c	298	oldused = b->used;
wolfSSL	0:d92f9d21154c	299	b->used = a->used;
wolfSSL	0:d92f9d21154c	300
wolfSSL	0:d92f9d21154c	301	{
wolfSSL	0:d92f9d21154c	302	register fp_digit r, rr, tmpa, tmpb;
wolfSSL	0:d92f9d21154c	303
wolfSSL	0:d92f9d21154c	304	/* alias for source */
wolfSSL	0:d92f9d21154c	305	tmpa = a->dp;
wolfSSL	0:d92f9d21154c	306
wolfSSL	0:d92f9d21154c	307	/* alias for dest */
wolfSSL	0:d92f9d21154c	308	tmpb = b->dp;
wolfSSL	0:d92f9d21154c	309
wolfSSL	0:d92f9d21154c	310	/* carry */
wolfSSL	0:d92f9d21154c	311	r = 0;
wolfSSL	0:d92f9d21154c	312	for (x = 0; x < a->used; x++) {
wolfSSL	0:d92f9d21154c	313
wolfSSL	0:d92f9d21154c	314	/* get what will be the next carry bit from the
wolfSSL	0:d92f9d21154c	315	* MSB of the current digit
wolfSSL	0:d92f9d21154c	316	*/
wolfSSL	0:d92f9d21154c	317	rr = *tmpa >> ((fp_digit)(DIGIT_BIT - 1));
wolfSSL	0:d92f9d21154c	318
wolfSSL	0:d92f9d21154c	319	/* now shift up this digit, add in the carry [from the previous] */
wolfSSL	0:d92f9d21154c	320	tmpb++ = ((tmpa++ << ((fp_digit)1)) \| r);
wolfSSL	0:d92f9d21154c	321
wolfSSL	0:d92f9d21154c	322	/* copy the carry that would be from the source
wolfSSL	0:d92f9d21154c	323	* digit into the next iteration
wolfSSL	0:d92f9d21154c	324	*/
wolfSSL	0:d92f9d21154c	325	r = rr;
wolfSSL	0:d92f9d21154c	326	}
wolfSSL	0:d92f9d21154c	327
wolfSSL	0:d92f9d21154c	328	/* new leading digit? */
wolfSSL	0:d92f9d21154c	329	if (r != 0 && b->used != (FP_SIZE-1)) {
wolfSSL	0:d92f9d21154c	330	/* add a MSB which is always 1 at this point */
wolfSSL	0:d92f9d21154c	331	*tmpb = 1;
wolfSSL	0:d92f9d21154c	332	++(b->used);
wolfSSL	0:d92f9d21154c	333	}
wolfSSL	0:d92f9d21154c	334
wolfSSL	0:d92f9d21154c	335	/* now zero any excess digits on the destination
wolfSSL	0:d92f9d21154c	336	* that we didn't write to
wolfSSL	0:d92f9d21154c	337	*/
wolfSSL	0:d92f9d21154c	338	tmpb = b->dp + b->used;
wolfSSL	0:d92f9d21154c	339	for (x = b->used; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	340	*tmpb++ = 0;
wolfSSL	0:d92f9d21154c	341	}
wolfSSL	0:d92f9d21154c	342	}
wolfSSL	0:d92f9d21154c	343	b->sign = a->sign;
wolfSSL	0:d92f9d21154c	344	}
wolfSSL	0:d92f9d21154c	345
wolfSSL	0:d92f9d21154c	346	/* c = a * b */
wolfSSL	0:d92f9d21154c	347	void fp_mul_d(fp_int a, fp_digit b, fp_int c)
wolfSSL	0:d92f9d21154c	348	{
wolfSSL	0:d92f9d21154c	349	fp_word w;
wolfSSL	0:d92f9d21154c	350	int x, oldused;
wolfSSL	0:d92f9d21154c	351
wolfSSL	0:d92f9d21154c	352	oldused = c->used;
wolfSSL	0:d92f9d21154c	353	c->used = a->used;
wolfSSL	0:d92f9d21154c	354	c->sign = a->sign;
wolfSSL	0:d92f9d21154c	355	w = 0;
wolfSSL	0:d92f9d21154c	356	for (x = 0; x < a->used; x++) {
wolfSSL	0:d92f9d21154c	357	w = ((fp_word)a->dp[x]) * ((fp_word)b) + w;
wolfSSL	0:d92f9d21154c	358	c->dp[x] = (fp_digit)w;
wolfSSL	0:d92f9d21154c	359	w = w >> DIGIT_BIT;
wolfSSL	0:d92f9d21154c	360	}
wolfSSL	0:d92f9d21154c	361	if (w != 0 && (a->used != FP_SIZE)) {
wolfSSL	0:d92f9d21154c	362	c->dp[c->used++] = (fp_digit) w;
wolfSSL	0:d92f9d21154c	363	++x;
wolfSSL	0:d92f9d21154c	364	}
wolfSSL	0:d92f9d21154c	365	for (; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	366	c->dp[x] = 0;
wolfSSL	0:d92f9d21154c	367	}
wolfSSL	0:d92f9d21154c	368	fp_clamp(c);
wolfSSL	0:d92f9d21154c	369	}
wolfSSL	0:d92f9d21154c	370
wolfSSL	0:d92f9d21154c	371	/* c = a * 2*d /
wolfSSL	0:d92f9d21154c	372	void fp_mul_2d(fp_int a, int b, fp_int c)
wolfSSL	0:d92f9d21154c	373	{
wolfSSL	0:d92f9d21154c	374	fp_digit carry, carrytmp, shift;
wolfSSL	0:d92f9d21154c	375	int x;
wolfSSL	0:d92f9d21154c	376
wolfSSL	0:d92f9d21154c	377	/* copy it */
wolfSSL	0:d92f9d21154c	378	fp_copy(a, c);
wolfSSL	0:d92f9d21154c	379
wolfSSL	0:d92f9d21154c	380	/* handle whole digits */
wolfSSL	0:d92f9d21154c	381	if (b >= DIGIT_BIT) {
wolfSSL	0:d92f9d21154c	382	fp_lshd(c, b/DIGIT_BIT);
wolfSSL	0:d92f9d21154c	383	}
wolfSSL	0:d92f9d21154c	384	b %= DIGIT_BIT;
wolfSSL	0:d92f9d21154c	385
wolfSSL	0:d92f9d21154c	386	/* shift the digits */
wolfSSL	0:d92f9d21154c	387	if (b != 0) {
wolfSSL	0:d92f9d21154c	388	carry = 0;
wolfSSL	0:d92f9d21154c	389	shift = DIGIT_BIT - b;
wolfSSL	0:d92f9d21154c	390	for (x = 0; x < c->used; x++) {
wolfSSL	0:d92f9d21154c	391	carrytmp = c->dp[x] >> shift;
wolfSSL	0:d92f9d21154c	392	c->dp[x] = (c->dp[x] << b) + carry;
wolfSSL	0:d92f9d21154c	393	carry = carrytmp;
wolfSSL	0:d92f9d21154c	394	}
wolfSSL	0:d92f9d21154c	395	/* store last carry if room */
wolfSSL	0:d92f9d21154c	396	if (carry && x < FP_SIZE) {
wolfSSL	0:d92f9d21154c	397	c->dp[c->used++] = carry;
wolfSSL	0:d92f9d21154c	398	}
wolfSSL	0:d92f9d21154c	399	}
wolfSSL	0:d92f9d21154c	400	fp_clamp(c);
wolfSSL	0:d92f9d21154c	401	}
wolfSSL	0:d92f9d21154c	402
wolfSSL	0:d92f9d21154c	403	/* generic PxQ multiplier */
wolfSSL	0:d92f9d21154c	404	#if defined(HAVE_INTEL_MULX)
wolfSSL	0:d92f9d21154c	405
wolfSSL	0:d92f9d21154c	406	INLINE static void fp_mul_comba_mulx(fp_int A, fp_int B, fp_int *C)
wolfSSL	0:d92f9d21154c	407
wolfSSL	0:d92f9d21154c	408	{
wolfSSL	0:d92f9d21154c	409	int ix, iy, iz, pa;
wolfSSL	0:d92f9d21154c	410	fp_int tmp, *dst;
wolfSSL	0:d92f9d21154c	411
wolfSSL	0:d92f9d21154c	412	/* get size of output and trim */
wolfSSL	0:d92f9d21154c	413	pa = A->used + B->used;
wolfSSL	0:d92f9d21154c	414	if (pa >= FP_SIZE) {
wolfSSL	0:d92f9d21154c	415	pa = FP_SIZE-1;
wolfSSL	0:d92f9d21154c	416	}
wolfSSL	0:d92f9d21154c	417
wolfSSL	0:d92f9d21154c	418	if (A == C \|\| B == C) {
wolfSSL	0:d92f9d21154c	419	fp_init(&tmp);
wolfSSL	0:d92f9d21154c	420	dst = &tmp;
wolfSSL	0:d92f9d21154c	421	} else {
wolfSSL	0:d92f9d21154c	422	fp_zero(C);
wolfSSL	0:d92f9d21154c	423	dst = C;
wolfSSL	0:d92f9d21154c	424	}
wolfSSL	0:d92f9d21154c	425
wolfSSL	0:d92f9d21154c	426	TFM_INTEL_MUL_COMBA(A, B, dst) ;
wolfSSL	0:d92f9d21154c	427
wolfSSL	0:d92f9d21154c	428	dst->used = pa;
wolfSSL	0:d92f9d21154c	429	dst->sign = A->sign ^ B->sign;
wolfSSL	0:d92f9d21154c	430	fp_clamp(dst);
wolfSSL	0:d92f9d21154c	431	fp_copy(dst, C);
wolfSSL	0:d92f9d21154c	432	}
wolfSSL	0:d92f9d21154c	433	#endif
wolfSSL	0:d92f9d21154c	434
wolfSSL	0:d92f9d21154c	435	void fp_mul_comba(fp_int A, fp_int B, fp_int *C)
wolfSSL	0:d92f9d21154c	436	{
wolfSSL	0:d92f9d21154c	437	int ix, iy, iz, tx, ty, pa;
wolfSSL	0:d92f9d21154c	438	fp_digit c0, c1, c2, tmpx, tmpy;
wolfSSL	0:d92f9d21154c	439	fp_int tmp, *dst;
wolfSSL	0:d92f9d21154c	440
wolfSSL	0:d92f9d21154c	441	IF_HAVE_INTEL_MULX(fp_mul_comba_mulx(A, B, C), return) ;
wolfSSL	0:d92f9d21154c	442
wolfSSL	0:d92f9d21154c	443	COMBA_START;
wolfSSL	0:d92f9d21154c	444	COMBA_CLEAR;
wolfSSL	0:d92f9d21154c	445
wolfSSL	0:d92f9d21154c	446	/* get size of output and trim */
wolfSSL	0:d92f9d21154c	447	pa = A->used + B->used;
wolfSSL	0:d92f9d21154c	448	if (pa >= FP_SIZE) {
wolfSSL	0:d92f9d21154c	449	pa = FP_SIZE-1;
wolfSSL	0:d92f9d21154c	450	}
wolfSSL	0:d92f9d21154c	451
wolfSSL	0:d92f9d21154c	452	if (A == C \|\| B == C) {
wolfSSL	0:d92f9d21154c	453	fp_init(&tmp);
wolfSSL	0:d92f9d21154c	454	dst = &tmp;
wolfSSL	0:d92f9d21154c	455	} else {
wolfSSL	0:d92f9d21154c	456	fp_zero(C);
wolfSSL	0:d92f9d21154c	457	dst = C;
wolfSSL	0:d92f9d21154c	458	}
wolfSSL	0:d92f9d21154c	459
wolfSSL	0:d92f9d21154c	460	for (ix = 0; ix < pa; ix++) {
wolfSSL	0:d92f9d21154c	461	/* get offsets into the two bignums */
wolfSSL	0:d92f9d21154c	462	ty = MIN(ix, B->used-1);
wolfSSL	0:d92f9d21154c	463	tx = ix - ty;
wolfSSL	0:d92f9d21154c	464
wolfSSL	0:d92f9d21154c	465	/* setup temp aliases */
wolfSSL	0:d92f9d21154c	466	tmpx = A->dp + tx;
wolfSSL	0:d92f9d21154c	467	tmpy = B->dp + ty;
wolfSSL	0:d92f9d21154c	468
wolfSSL	0:d92f9d21154c	469	/* this is the number of times the loop will iterrate, essentially its
wolfSSL	0:d92f9d21154c	470	while (tx++ < a->used && ty-- >= 0) { ... }
wolfSSL	0:d92f9d21154c	471	*/
wolfSSL	0:d92f9d21154c	472	iy = MIN(A->used-tx, ty+1);
wolfSSL	0:d92f9d21154c	473
wolfSSL	0:d92f9d21154c	474	/* execute loop */
wolfSSL	0:d92f9d21154c	475	COMBA_FORWARD;
wolfSSL	0:d92f9d21154c	476	for (iz = 0; iz < iy; ++iz) {
wolfSSL	0:d92f9d21154c	477	/* TAO change COMBA_ADD back to MULADD */
wolfSSL	0:d92f9d21154c	478	MULADD(tmpx++, tmpy--);
wolfSSL	0:d92f9d21154c	479	}
wolfSSL	0:d92f9d21154c	480
wolfSSL	0:d92f9d21154c	481	/* store term */
wolfSSL	0:d92f9d21154c	482	COMBA_STORE(dst->dp[ix]);
wolfSSL	0:d92f9d21154c	483	}
wolfSSL	0:d92f9d21154c	484	COMBA_FINI;
wolfSSL	0:d92f9d21154c	485
wolfSSL	0:d92f9d21154c	486	dst->used = pa;
wolfSSL	0:d92f9d21154c	487	dst->sign = A->sign ^ B->sign;
wolfSSL	0:d92f9d21154c	488	fp_clamp(dst);
wolfSSL	0:d92f9d21154c	489	fp_copy(dst, C);
wolfSSL	0:d92f9d21154c	490	}
wolfSSL	0:d92f9d21154c	491
wolfSSL	0:d92f9d21154c	492	/* a/b => cb + d == a */
wolfSSL	0:d92f9d21154c	493	int fp_div(fp_int a, fp_int b, fp_int c, fp_int d)
wolfSSL	0:d92f9d21154c	494	{
wolfSSL	0:d92f9d21154c	495	fp_int q, x, y, t1, t2;
wolfSSL	0:d92f9d21154c	496	int n, t, i, norm, neg;
wolfSSL	0:d92f9d21154c	497
wolfSSL	0:d92f9d21154c	498	/* is divisor zero ? */
wolfSSL	0:d92f9d21154c	499	if (fp_iszero (b) == 1) {
wolfSSL	0:d92f9d21154c	500	return FP_VAL;
wolfSSL	0:d92f9d21154c	501	}
wolfSSL	0:d92f9d21154c	502
wolfSSL	0:d92f9d21154c	503	/* if a < b then q=0, r = a */
wolfSSL	0:d92f9d21154c	504	if (fp_cmp_mag (a, b) == FP_LT) {
wolfSSL	0:d92f9d21154c	505	if (d != NULL) {
wolfSSL	0:d92f9d21154c	506	fp_copy (a, d);
wolfSSL	0:d92f9d21154c	507	}
wolfSSL	0:d92f9d21154c	508	if (c != NULL) {
wolfSSL	0:d92f9d21154c	509	fp_zero (c);
wolfSSL	0:d92f9d21154c	510	}
wolfSSL	0:d92f9d21154c	511	return FP_OKAY;
wolfSSL	0:d92f9d21154c	512	}
wolfSSL	0:d92f9d21154c	513
wolfSSL	0:d92f9d21154c	514	fp_init(&q);
wolfSSL	0:d92f9d21154c	515	q.used = a->used + 2;
wolfSSL	0:d92f9d21154c	516
wolfSSL	0:d92f9d21154c	517	fp_init(&t1);
wolfSSL	0:d92f9d21154c	518	fp_init(&t2);
wolfSSL	0:d92f9d21154c	519	fp_init_copy(&x, a);
wolfSSL	0:d92f9d21154c	520	fp_init_copy(&y, b);
wolfSSL	0:d92f9d21154c	521
wolfSSL	0:d92f9d21154c	522	/* fix the sign */
wolfSSL	0:d92f9d21154c	523	neg = (a->sign == b->sign) ? FP_ZPOS : FP_NEG;
wolfSSL	0:d92f9d21154c	524	x.sign = y.sign = FP_ZPOS;
wolfSSL	0:d92f9d21154c	525
wolfSSL	0:d92f9d21154c	526	/* normalize both x and y, ensure that y >= b/2, [b == 2*DIGIT_BIT] /
wolfSSL	0:d92f9d21154c	527	norm = fp_count_bits(&y) % DIGIT_BIT;
wolfSSL	0:d92f9d21154c	528	if (norm < (int)(DIGIT_BIT-1)) {
wolfSSL	0:d92f9d21154c	529	norm = (DIGIT_BIT-1) - norm;
wolfSSL	0:d92f9d21154c	530	fp_mul_2d (&x, norm, &x);
wolfSSL	0:d92f9d21154c	531	fp_mul_2d (&y, norm, &y);
wolfSSL	0:d92f9d21154c	532	} else {
wolfSSL	0:d92f9d21154c	533	norm = 0;
wolfSSL	0:d92f9d21154c	534	}
wolfSSL	0:d92f9d21154c	535
wolfSSL	0:d92f9d21154c	536	/* note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4 */
wolfSSL	0:d92f9d21154c	537	n = x.used - 1;
wolfSSL	0:d92f9d21154c	538	t = y.used - 1;
wolfSSL	0:d92f9d21154c	539
wolfSSL	0:d92f9d21154c	540	/* while (x >= ybn-t) do { q[n-t] += 1; x -= yb*{n-t} } /
wolfSSL	0:d92f9d21154c	541	fp_lshd (&y, n - t); /* y = yb{n-t} /
wolfSSL	0:d92f9d21154c	542
wolfSSL	0:d92f9d21154c	543	while (fp_cmp (&x, &y) != FP_LT) {
wolfSSL	0:d92f9d21154c	544	++(q.dp[n - t]);
wolfSSL	0:d92f9d21154c	545	fp_sub (&x, &y, &x);
wolfSSL	0:d92f9d21154c	546	}
wolfSSL	0:d92f9d21154c	547
wolfSSL	0:d92f9d21154c	548	/* reset y by shifting it back down */
wolfSSL	0:d92f9d21154c	549	fp_rshd (&y, n - t);
wolfSSL	0:d92f9d21154c	550
wolfSSL	0:d92f9d21154c	551	/* step 3. for i from n down to (t + 1) */
wolfSSL	0:d92f9d21154c	552	for (i = n; i >= (t + 1); i--) {
wolfSSL	0:d92f9d21154c	553	if (i > x.used) {
wolfSSL	0:d92f9d21154c	554	continue;
wolfSSL	0:d92f9d21154c	555	}
wolfSSL	0:d92f9d21154c	556
wolfSSL	0:d92f9d21154c	557	/* step 3.1 if xi == yt then set q{i-t-1} to b-1,
wolfSSL	0:d92f9d21154c	558	* otherwise set q{i-t-1} to (xib + x{i-1})/yt /
wolfSSL	0:d92f9d21154c	559	if (x.dp[i] == y.dp[t]) {
wolfSSL	0:d92f9d21154c	560	q.dp[i - t - 1] = (fp_digit) ((((fp_word)1) << DIGIT_BIT) - 1);
wolfSSL	0:d92f9d21154c	561	} else {
wolfSSL	0:d92f9d21154c	562	fp_word tmp;
wolfSSL	0:d92f9d21154c	563	tmp = ((fp_word) x.dp[i]) << ((fp_word) DIGIT_BIT);
wolfSSL	0:d92f9d21154c	564	tmp \|= ((fp_word) x.dp[i - 1]);
wolfSSL	0:d92f9d21154c	565	tmp /= ((fp_word)y.dp[t]);
wolfSSL	0:d92f9d21154c	566	q.dp[i - t - 1] = (fp_digit) (tmp);
wolfSSL	0:d92f9d21154c	567	}
wolfSSL	0:d92f9d21154c	568
wolfSSL	0:d92f9d21154c	569	/* while (q{i-t-1} * (yt * b + y{t-1})) >
wolfSSL	0:d92f9d21154c	570	xi * b*2 + xi-1 b + xi-2
wolfSSL	0:d92f9d21154c	571
wolfSSL	0:d92f9d21154c	572	do q{i-t-1} -= 1;
wolfSSL	0:d92f9d21154c	573	*/
wolfSSL	0:d92f9d21154c	574	q.dp[i - t - 1] = (q.dp[i - t - 1] + 1);
wolfSSL	0:d92f9d21154c	575	do {
wolfSSL	0:d92f9d21154c	576	q.dp[i - t - 1] = (q.dp[i - t - 1] - 1);
wolfSSL	0:d92f9d21154c	577
wolfSSL	0:d92f9d21154c	578	/* find left hand */
wolfSSL	0:d92f9d21154c	579	fp_zero (&t1);
wolfSSL	0:d92f9d21154c	580	t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1];
wolfSSL	0:d92f9d21154c	581	t1.dp[1] = y.dp[t];
wolfSSL	0:d92f9d21154c	582	t1.used = 2;
wolfSSL	0:d92f9d21154c	583	fp_mul_d (&t1, q.dp[i - t - 1], &t1);
wolfSSL	0:d92f9d21154c	584
wolfSSL	0:d92f9d21154c	585	/* find right hand */
wolfSSL	0:d92f9d21154c	586	t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2];
wolfSSL	0:d92f9d21154c	587	t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1];
wolfSSL	0:d92f9d21154c	588	t2.dp[2] = x.dp[i];
wolfSSL	0:d92f9d21154c	589	t2.used = 3;
wolfSSL	0:d92f9d21154c	590	} while (fp_cmp_mag(&t1, &t2) == FP_GT);
wolfSSL	0:d92f9d21154c	591
wolfSSL	0:d92f9d21154c	592	/* step 3.3 x = x - q{i-t-1} * y * b*{i-t-1} /
wolfSSL	0:d92f9d21154c	593	fp_mul_d (&y, q.dp[i - t - 1], &t1);
wolfSSL	0:d92f9d21154c	594	fp_lshd (&t1, i - t - 1);
wolfSSL	0:d92f9d21154c	595	fp_sub (&x, &t1, &x);
wolfSSL	0:d92f9d21154c	596
wolfSSL	0:d92f9d21154c	597	/* if x < 0 then { x = x + yb{i-t-1}; q{i-t-1} -= 1; } /
wolfSSL	0:d92f9d21154c	598	if (x.sign == FP_NEG) {
wolfSSL	0:d92f9d21154c	599	fp_copy (&y, &t1);
wolfSSL	0:d92f9d21154c	600	fp_lshd (&t1, i - t - 1);
wolfSSL	0:d92f9d21154c	601	fp_add (&x, &t1, &x);
wolfSSL	0:d92f9d21154c	602	q.dp[i - t - 1] = q.dp[i - t - 1] - 1;
wolfSSL	0:d92f9d21154c	603	}
wolfSSL	0:d92f9d21154c	604	}
wolfSSL	0:d92f9d21154c	605
wolfSSL	0:d92f9d21154c	606	/* now q is the quotient and x is the remainder
wolfSSL	0:d92f9d21154c	607	* [which we have to normalize]
wolfSSL	0:d92f9d21154c	608	*/
wolfSSL	0:d92f9d21154c	609
wolfSSL	0:d92f9d21154c	610	/* get sign before writing to c */
wolfSSL	0:d92f9d21154c	611	x.sign = x.used == 0 ? FP_ZPOS : a->sign;
wolfSSL	0:d92f9d21154c	612
wolfSSL	0:d92f9d21154c	613	if (c != NULL) {
wolfSSL	0:d92f9d21154c	614	fp_clamp (&q);
wolfSSL	0:d92f9d21154c	615	fp_copy (&q, c);
wolfSSL	0:d92f9d21154c	616	c->sign = neg;
wolfSSL	0:d92f9d21154c	617	}
wolfSSL	0:d92f9d21154c	618
wolfSSL	0:d92f9d21154c	619	if (d != NULL) {
wolfSSL	0:d92f9d21154c	620	fp_div_2d (&x, norm, &x, NULL);
wolfSSL	0:d92f9d21154c	621
wolfSSL	0:d92f9d21154c	622	/* the following is a kludge, essentially we were seeing the right remainder but
wolfSSL	0:d92f9d21154c	623	with excess digits that should have been zero
wolfSSL	0:d92f9d21154c	624	*/
wolfSSL	0:d92f9d21154c	625	for (i = b->used; i < x.used; i++) {
wolfSSL	0:d92f9d21154c	626	x.dp[i] = 0;
wolfSSL	0:d92f9d21154c	627	}
wolfSSL	0:d92f9d21154c	628	fp_clamp(&x);
wolfSSL	0:d92f9d21154c	629	fp_copy (&x, d);
wolfSSL	0:d92f9d21154c	630	}
wolfSSL	0:d92f9d21154c	631
wolfSSL	0:d92f9d21154c	632	return FP_OKAY;
wolfSSL	0:d92f9d21154c	633	}
wolfSSL	0:d92f9d21154c	634
wolfSSL	0:d92f9d21154c	635	/* b = a/2 */
wolfSSL	0:d92f9d21154c	636	void fp_div_2(fp_int * a, fp_int * b)
wolfSSL	0:d92f9d21154c	637	{
wolfSSL	0:d92f9d21154c	638	int x, oldused;
wolfSSL	0:d92f9d21154c	639
wolfSSL	0:d92f9d21154c	640	oldused = b->used;
wolfSSL	0:d92f9d21154c	641	b->used = a->used;
wolfSSL	0:d92f9d21154c	642	{
wolfSSL	0:d92f9d21154c	643	register fp_digit r, rr, tmpa, tmpb;
wolfSSL	0:d92f9d21154c	644
wolfSSL	0:d92f9d21154c	645	/* source alias */
wolfSSL	0:d92f9d21154c	646	tmpa = a->dp + b->used - 1;
wolfSSL	0:d92f9d21154c	647
wolfSSL	0:d92f9d21154c	648	/* dest alias */
wolfSSL	0:d92f9d21154c	649	tmpb = b->dp + b->used - 1;
wolfSSL	0:d92f9d21154c	650
wolfSSL	0:d92f9d21154c	651	/* carry */
wolfSSL	0:d92f9d21154c	652	r = 0;
wolfSSL	0:d92f9d21154c	653	for (x = b->used - 1; x >= 0; x--) {
wolfSSL	0:d92f9d21154c	654	/* get the carry for the next iteration */
wolfSSL	0:d92f9d21154c	655	rr = *tmpa & 1;
wolfSSL	0:d92f9d21154c	656
wolfSSL	0:d92f9d21154c	657	/* shift the current digit, add in carry and store */
wolfSSL	0:d92f9d21154c	658	tmpb-- = (tmpa-- >> 1) \| (r << (DIGIT_BIT - 1));
wolfSSL	0:d92f9d21154c	659
wolfSSL	0:d92f9d21154c	660	/* forward carry to next iteration */
wolfSSL	0:d92f9d21154c	661	r = rr;
wolfSSL	0:d92f9d21154c	662	}
wolfSSL	0:d92f9d21154c	663
wolfSSL	0:d92f9d21154c	664	/* zero excess digits */
wolfSSL	0:d92f9d21154c	665	tmpb = b->dp + b->used;
wolfSSL	0:d92f9d21154c	666	for (x = b->used; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	667	*tmpb++ = 0;
wolfSSL	0:d92f9d21154c	668	}
wolfSSL	0:d92f9d21154c	669	}
wolfSSL	0:d92f9d21154c	670	b->sign = a->sign;
wolfSSL	0:d92f9d21154c	671	fp_clamp (b);
wolfSSL	0:d92f9d21154c	672	}
wolfSSL	0:d92f9d21154c	673
wolfSSL	0:d92f9d21154c	674	/* c = a / 2*b /
wolfSSL	0:d92f9d21154c	675	void fp_div_2d(fp_int a, int b, fp_int c, fp_int *d)
wolfSSL	0:d92f9d21154c	676	{
wolfSSL	0:d92f9d21154c	677	int D;
wolfSSL	0:d92f9d21154c	678	fp_int t;
wolfSSL	0:d92f9d21154c	679
wolfSSL	0:d92f9d21154c	680	/* if the shift count is <= 0 then we do no work */
wolfSSL	0:d92f9d21154c	681	if (b <= 0) {
wolfSSL	0:d92f9d21154c	682	fp_copy (a, c);
wolfSSL	0:d92f9d21154c	683	if (d != NULL) {
wolfSSL	0:d92f9d21154c	684	fp_zero (d);
wolfSSL	0:d92f9d21154c	685	}
wolfSSL	0:d92f9d21154c	686	return;
wolfSSL	0:d92f9d21154c	687	}
wolfSSL	0:d92f9d21154c	688
wolfSSL	0:d92f9d21154c	689	fp_init(&t);
wolfSSL	0:d92f9d21154c	690
wolfSSL	0:d92f9d21154c	691	/* get the remainder */
wolfSSL	0:d92f9d21154c	692	if (d != NULL) {
wolfSSL	0:d92f9d21154c	693	fp_mod_2d (a, b, &t);
wolfSSL	0:d92f9d21154c	694	}
wolfSSL	0:d92f9d21154c	695
wolfSSL	0:d92f9d21154c	696	/* copy */
wolfSSL	0:d92f9d21154c	697	fp_copy(a, c);
wolfSSL	0:d92f9d21154c	698
wolfSSL	0:d92f9d21154c	699	/* shift by as many digits in the bit count */
wolfSSL	0:d92f9d21154c	700	if (b >= (int)DIGIT_BIT) {
wolfSSL	0:d92f9d21154c	701	fp_rshd (c, b / DIGIT_BIT);
wolfSSL	0:d92f9d21154c	702	}
wolfSSL	0:d92f9d21154c	703
wolfSSL	0:d92f9d21154c	704	/* shift any bit count < DIGIT_BIT */
wolfSSL	0:d92f9d21154c	705	D = (b % DIGIT_BIT);
wolfSSL	0:d92f9d21154c	706	if (D != 0) {
wolfSSL	0:d92f9d21154c	707	fp_rshb(c, D);
wolfSSL	0:d92f9d21154c	708	}
wolfSSL	0:d92f9d21154c	709	fp_clamp (c);
wolfSSL	0:d92f9d21154c	710	if (d != NULL) {
wolfSSL	0:d92f9d21154c	711	fp_copy (&t, d);
wolfSSL	0:d92f9d21154c	712	}
wolfSSL	0:d92f9d21154c	713	}
wolfSSL	0:d92f9d21154c	714
wolfSSL	0:d92f9d21154c	715	/* c = a mod b, 0 <= c < b */
wolfSSL	0:d92f9d21154c	716	int fp_mod(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	717	{
wolfSSL	0:d92f9d21154c	718	fp_int t;
wolfSSL	0:d92f9d21154c	719	int err;
wolfSSL	0:d92f9d21154c	720
wolfSSL	0:d92f9d21154c	721	fp_init(&t);
wolfSSL	0:d92f9d21154c	722	if ((err = fp_div(a, b, NULL, &t)) != FP_OKAY) {
wolfSSL	0:d92f9d21154c	723	return err;
wolfSSL	0:d92f9d21154c	724	}
wolfSSL	0:d92f9d21154c	725	if (t.sign != b->sign) {
wolfSSL	0:d92f9d21154c	726	fp_add(&t, b, c);
wolfSSL	0:d92f9d21154c	727	} else {
wolfSSL	0:d92f9d21154c	728	fp_copy(&t, c);
wolfSSL	0:d92f9d21154c	729	}
wolfSSL	0:d92f9d21154c	730	return FP_OKAY;
wolfSSL	0:d92f9d21154c	731	}
wolfSSL	0:d92f9d21154c	732
wolfSSL	0:d92f9d21154c	733	/* c = a mod 2*d /
wolfSSL	0:d92f9d21154c	734	void fp_mod_2d(fp_int a, int b, fp_int c)
wolfSSL	0:d92f9d21154c	735	{
wolfSSL	0:d92f9d21154c	736	int x;
wolfSSL	0:d92f9d21154c	737
wolfSSL	0:d92f9d21154c	738	/* zero if count less than or equal to zero */
wolfSSL	0:d92f9d21154c	739	if (b <= 0) {
wolfSSL	0:d92f9d21154c	740	fp_zero(c);
wolfSSL	0:d92f9d21154c	741	return;
wolfSSL	0:d92f9d21154c	742	}
wolfSSL	0:d92f9d21154c	743
wolfSSL	0:d92f9d21154c	744	/* get copy of input */
wolfSSL	0:d92f9d21154c	745	fp_copy(a, c);
wolfSSL	0:d92f9d21154c	746
wolfSSL	0:d92f9d21154c	747	/* if 2*d is larger than we just return /
wolfSSL	0:d92f9d21154c	748	if (b >= (DIGIT_BIT * a->used)) {
wolfSSL	0:d92f9d21154c	749	return;
wolfSSL	0:d92f9d21154c	750	}
wolfSSL	0:d92f9d21154c	751
wolfSSL	0:d92f9d21154c	752	/* zero digits above the last digit of the modulus */
wolfSSL	0:d92f9d21154c	753	for (x = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1); x < c->used; x++) {
wolfSSL	0:d92f9d21154c	754	c->dp[x] = 0;
wolfSSL	0:d92f9d21154c	755	}
wolfSSL	0:d92f9d21154c	756	/* clear the digit that is not completely outside/inside the modulus */
wolfSSL	0:d92f9d21154c	757	c->dp[b / DIGIT_BIT] &= ~((fp_digit)0) >> (DIGIT_BIT - b);
wolfSSL	0:d92f9d21154c	758	fp_clamp (c);
wolfSSL	0:d92f9d21154c	759	}
wolfSSL	0:d92f9d21154c	760
wolfSSL	0:d92f9d21154c	761	static int fp_invmod_slow (fp_int * a, fp_int * b, fp_int * c)
wolfSSL	0:d92f9d21154c	762	{
wolfSSL	0:d92f9d21154c	763	fp_int x, y, u, v, A, B, C, D;
wolfSSL	0:d92f9d21154c	764	int res;
wolfSSL	0:d92f9d21154c	765
wolfSSL	0:d92f9d21154c	766	/* b cannot be negative */
wolfSSL	0:d92f9d21154c	767	if (b->sign == FP_NEG \|\| fp_iszero(b) == 1) {
wolfSSL	0:d92f9d21154c	768	return FP_VAL;
wolfSSL	0:d92f9d21154c	769	}
wolfSSL	0:d92f9d21154c	770
wolfSSL	0:d92f9d21154c	771	/* init temps */
wolfSSL	0:d92f9d21154c	772	fp_init(&x); fp_init(&y);
wolfSSL	0:d92f9d21154c	773	fp_init(&u); fp_init(&v);
wolfSSL	0:d92f9d21154c	774	fp_init(&A); fp_init(&B);
wolfSSL	0:d92f9d21154c	775	fp_init(&C); fp_init(&D);
wolfSSL	0:d92f9d21154c	776
wolfSSL	0:d92f9d21154c	777	/* x = a, y = b */
wolfSSL	0:d92f9d21154c	778	if ((res = fp_mod(a, b, &x)) != FP_OKAY) {
wolfSSL	0:d92f9d21154c	779	return res;
wolfSSL	0:d92f9d21154c	780	}
wolfSSL	0:d92f9d21154c	781	fp_copy(b, &y);
wolfSSL	0:d92f9d21154c	782
wolfSSL	0:d92f9d21154c	783	/* 2. [modified] if x,y are both even then return an error! */
wolfSSL	0:d92f9d21154c	784	if (fp_iseven (&x) == 1 && fp_iseven (&y) == 1) {
wolfSSL	0:d92f9d21154c	785	return FP_VAL;
wolfSSL	0:d92f9d21154c	786	}
wolfSSL	0:d92f9d21154c	787
wolfSSL	0:d92f9d21154c	788	/* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
wolfSSL	0:d92f9d21154c	789	fp_copy (&x, &u);
wolfSSL	0:d92f9d21154c	790	fp_copy (&y, &v);
wolfSSL	0:d92f9d21154c	791	fp_set (&A, 1);
wolfSSL	0:d92f9d21154c	792	fp_set (&D, 1);
wolfSSL	0:d92f9d21154c	793
wolfSSL	0:d92f9d21154c	794	top:
wolfSSL	0:d92f9d21154c	795	/* 4. while u is even do */
wolfSSL	0:d92f9d21154c	796	while (fp_iseven (&u) == 1) {
wolfSSL	0:d92f9d21154c	797	/* 4.1 u = u/2 */
wolfSSL	0:d92f9d21154c	798	fp_div_2 (&u, &u);
wolfSSL	0:d92f9d21154c	799
wolfSSL	0:d92f9d21154c	800	/* 4.2 if A or B is odd then */
wolfSSL	0:d92f9d21154c	801	if (fp_isodd (&A) == 1 \|\| fp_isodd (&B) == 1) {
wolfSSL	0:d92f9d21154c	802	/* A = (A+y)/2, B = (B-x)/2 */
wolfSSL	0:d92f9d21154c	803	fp_add (&A, &y, &A);
wolfSSL	0:d92f9d21154c	804	fp_sub (&B, &x, &B);
wolfSSL	0:d92f9d21154c	805	}
wolfSSL	0:d92f9d21154c	806	/* A = A/2, B = B/2 */
wolfSSL	0:d92f9d21154c	807	fp_div_2 (&A, &A);
wolfSSL	0:d92f9d21154c	808	fp_div_2 (&B, &B);
wolfSSL	0:d92f9d21154c	809	}
wolfSSL	0:d92f9d21154c	810
wolfSSL	0:d92f9d21154c	811	/* 5. while v is even do */
wolfSSL	0:d92f9d21154c	812	while (fp_iseven (&v) == 1) {
wolfSSL	0:d92f9d21154c	813	/* 5.1 v = v/2 */
wolfSSL	0:d92f9d21154c	814	fp_div_2 (&v, &v);
wolfSSL	0:d92f9d21154c	815
wolfSSL	0:d92f9d21154c	816	/* 5.2 if C or D is odd then */
wolfSSL	0:d92f9d21154c	817	if (fp_isodd (&C) == 1 \|\| fp_isodd (&D) == 1) {
wolfSSL	0:d92f9d21154c	818	/* C = (C+y)/2, D = (D-x)/2 */
wolfSSL	0:d92f9d21154c	819	fp_add (&C, &y, &C);
wolfSSL	0:d92f9d21154c	820	fp_sub (&D, &x, &D);
wolfSSL	0:d92f9d21154c	821	}
wolfSSL	0:d92f9d21154c	822	/* C = C/2, D = D/2 */
wolfSSL	0:d92f9d21154c	823	fp_div_2 (&C, &C);
wolfSSL	0:d92f9d21154c	824	fp_div_2 (&D, &D);
wolfSSL	0:d92f9d21154c	825	}
wolfSSL	0:d92f9d21154c	826
wolfSSL	0:d92f9d21154c	827	/* 6. if u >= v then */
wolfSSL	0:d92f9d21154c	828	if (fp_cmp (&u, &v) != FP_LT) {
wolfSSL	0:d92f9d21154c	829	/* u = u - v, A = A - C, B = B - D */
wolfSSL	0:d92f9d21154c	830	fp_sub (&u, &v, &u);
wolfSSL	0:d92f9d21154c	831	fp_sub (&A, &C, &A);
wolfSSL	0:d92f9d21154c	832	fp_sub (&B, &D, &B);
wolfSSL	0:d92f9d21154c	833	} else {
wolfSSL	0:d92f9d21154c	834	/* v - v - u, C = C - A, D = D - B */
wolfSSL	0:d92f9d21154c	835	fp_sub (&v, &u, &v);
wolfSSL	0:d92f9d21154c	836	fp_sub (&C, &A, &C);
wolfSSL	0:d92f9d21154c	837	fp_sub (&D, &B, &D);
wolfSSL	0:d92f9d21154c	838	}
wolfSSL	0:d92f9d21154c	839
wolfSSL	0:d92f9d21154c	840	/* if not zero goto step 4 */
wolfSSL	0:d92f9d21154c	841	if (fp_iszero (&u) == 0)
wolfSSL	0:d92f9d21154c	842	goto top;
wolfSSL	0:d92f9d21154c	843
wolfSSL	0:d92f9d21154c	844	/* now a = C, b = D, gcd == gv /
wolfSSL	0:d92f9d21154c	845
wolfSSL	0:d92f9d21154c	846	/* if v != 1 then there is no inverse */
wolfSSL	0:d92f9d21154c	847	if (fp_cmp_d (&v, 1) != FP_EQ) {
wolfSSL	0:d92f9d21154c	848	return FP_VAL;
wolfSSL	0:d92f9d21154c	849	}
wolfSSL	0:d92f9d21154c	850
wolfSSL	0:d92f9d21154c	851	/* if its too low */
wolfSSL	0:d92f9d21154c	852	while (fp_cmp_d(&C, 0) == FP_LT) {
wolfSSL	0:d92f9d21154c	853	fp_add(&C, b, &C);
wolfSSL	0:d92f9d21154c	854	}
wolfSSL	0:d92f9d21154c	855
wolfSSL	0:d92f9d21154c	856	/* too big */
wolfSSL	0:d92f9d21154c	857	while (fp_cmp_mag(&C, b) != FP_LT) {
wolfSSL	0:d92f9d21154c	858	fp_sub(&C, b, &C);
wolfSSL	0:d92f9d21154c	859	}
wolfSSL	0:d92f9d21154c	860
wolfSSL	0:d92f9d21154c	861	/* C is now the inverse */
wolfSSL	0:d92f9d21154c	862	fp_copy(&C, c);
wolfSSL	0:d92f9d21154c	863	return FP_OKAY;
wolfSSL	0:d92f9d21154c	864	}
wolfSSL	0:d92f9d21154c	865
wolfSSL	0:d92f9d21154c	866
wolfSSL	0:d92f9d21154c	867	/* c = 1/a (mod b) for odd b only */
wolfSSL	0:d92f9d21154c	868	int fp_invmod(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	869	{
wolfSSL	0:d92f9d21154c	870	fp_int x, y, u, v, B, D;
wolfSSL	0:d92f9d21154c	871	int neg, loop_check = 0;
wolfSSL	0:d92f9d21154c	872
wolfSSL	0:d92f9d21154c	873	/* 2. [modified] b must be odd */
wolfSSL	0:d92f9d21154c	874	if (fp_iseven (b) == FP_YES) {
wolfSSL	0:d92f9d21154c	875	return fp_invmod_slow(a,b,c);
wolfSSL	0:d92f9d21154c	876	}
wolfSSL	0:d92f9d21154c	877
wolfSSL	0:d92f9d21154c	878	/* init all our temps */
wolfSSL	0:d92f9d21154c	879	fp_init(&x); fp_init(&y);
wolfSSL	0:d92f9d21154c	880	fp_init(&u); fp_init(&v);
wolfSSL	0:d92f9d21154c	881	fp_init(&B); fp_init(&D);
wolfSSL	0:d92f9d21154c	882
wolfSSL	0:d92f9d21154c	883	/* x == modulus, y == value to invert */
wolfSSL	0:d92f9d21154c	884	fp_copy(b, &x);
wolfSSL	0:d92f9d21154c	885
wolfSSL	0:d92f9d21154c	886	/* we need y = \|a\| */
wolfSSL	0:d92f9d21154c	887	fp_abs(a, &y);
wolfSSL	0:d92f9d21154c	888
wolfSSL	0:d92f9d21154c	889	/* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
wolfSSL	0:d92f9d21154c	890	fp_copy(&x, &u);
wolfSSL	0:d92f9d21154c	891	fp_copy(&y, &v);
wolfSSL	0:d92f9d21154c	892	fp_set (&D, 1);
wolfSSL	0:d92f9d21154c	893
wolfSSL	0:d92f9d21154c	894	top:
wolfSSL	0:d92f9d21154c	895	/* 4. while u is even do */
wolfSSL	0:d92f9d21154c	896	while (fp_iseven (&u) == FP_YES) {
wolfSSL	0:d92f9d21154c	897	/* 4.1 u = u/2 */
wolfSSL	0:d92f9d21154c	898	fp_div_2 (&u, &u);
wolfSSL	0:d92f9d21154c	899
wolfSSL	0:d92f9d21154c	900	/* 4.2 if B is odd then */
wolfSSL	0:d92f9d21154c	901	if (fp_isodd (&B) == FP_YES) {
wolfSSL	0:d92f9d21154c	902	fp_sub (&B, &x, &B);
wolfSSL	0:d92f9d21154c	903	}
wolfSSL	0:d92f9d21154c	904	/* B = B/2 */
wolfSSL	0:d92f9d21154c	905	fp_div_2 (&B, &B);
wolfSSL	0:d92f9d21154c	906	}
wolfSSL	0:d92f9d21154c	907
wolfSSL	0:d92f9d21154c	908	/* 5. while v is even do */
wolfSSL	0:d92f9d21154c	909	while (fp_iseven (&v) == FP_YES) {
wolfSSL	0:d92f9d21154c	910	/* 5.1 v = v/2 */
wolfSSL	0:d92f9d21154c	911	fp_div_2 (&v, &v);
wolfSSL	0:d92f9d21154c	912
wolfSSL	0:d92f9d21154c	913	/* 5.2 if D is odd then */
wolfSSL	0:d92f9d21154c	914	if (fp_isodd (&D) == FP_YES) {
wolfSSL	0:d92f9d21154c	915	/* D = (D-x)/2 */
wolfSSL	0:d92f9d21154c	916	fp_sub (&D, &x, &D);
wolfSSL	0:d92f9d21154c	917	}
wolfSSL	0:d92f9d21154c	918	/* D = D/2 */
wolfSSL	0:d92f9d21154c	919	fp_div_2 (&D, &D);
wolfSSL	0:d92f9d21154c	920	}
wolfSSL	0:d92f9d21154c	921
wolfSSL	0:d92f9d21154c	922	/* 6. if u >= v then */
wolfSSL	0:d92f9d21154c	923	if (fp_cmp (&u, &v) != FP_LT) {
wolfSSL	0:d92f9d21154c	924	/* u = u - v, B = B - D */
wolfSSL	0:d92f9d21154c	925	fp_sub (&u, &v, &u);
wolfSSL	0:d92f9d21154c	926	fp_sub (&B, &D, &B);
wolfSSL	0:d92f9d21154c	927	} else {
wolfSSL	0:d92f9d21154c	928	/* v - v - u, D = D - B */
wolfSSL	0:d92f9d21154c	929	fp_sub (&v, &u, &v);
wolfSSL	0:d92f9d21154c	930	fp_sub (&D, &B, &D);
wolfSSL	0:d92f9d21154c	931	}
wolfSSL	0:d92f9d21154c	932
wolfSSL	0:d92f9d21154c	933	/* if not zero goto step 4 */
wolfSSL	0:d92f9d21154c	934	if (fp_iszero (&u) == FP_NO) {
wolfSSL	0:d92f9d21154c	935	if (++loop_check > 1024) /* bad input */
wolfSSL	0:d92f9d21154c	936	return FP_VAL;
wolfSSL	0:d92f9d21154c	937	goto top;
wolfSSL	0:d92f9d21154c	938	}
wolfSSL	0:d92f9d21154c	939
wolfSSL	0:d92f9d21154c	940	/* now a = C, b = D, gcd == gv /
wolfSSL	0:d92f9d21154c	941
wolfSSL	0:d92f9d21154c	942	/* if v != 1 then there is no inverse */
wolfSSL	0:d92f9d21154c	943	if (fp_cmp_d (&v, 1) != FP_EQ) {
wolfSSL	0:d92f9d21154c	944	return FP_VAL;
wolfSSL	0:d92f9d21154c	945	}
wolfSSL	0:d92f9d21154c	946
wolfSSL	0:d92f9d21154c	947	/* b is now the inverse */
wolfSSL	0:d92f9d21154c	948	neg = a->sign;
wolfSSL	0:d92f9d21154c	949	while (D.sign == FP_NEG) {
wolfSSL	0:d92f9d21154c	950	fp_add (&D, b, &D);
wolfSSL	0:d92f9d21154c	951	}
wolfSSL	0:d92f9d21154c	952	fp_copy (&D, c);
wolfSSL	0:d92f9d21154c	953	c->sign = neg;
wolfSSL	0:d92f9d21154c	954	return FP_OKAY;
wolfSSL	0:d92f9d21154c	955	}
wolfSSL	0:d92f9d21154c	956
wolfSSL	0:d92f9d21154c	957	/* d = a * b (mod c) */
wolfSSL	0:d92f9d21154c	958	int fp_mulmod(fp_int a, fp_int b, fp_int c, fp_int d)
wolfSSL	0:d92f9d21154c	959	{
wolfSSL	0:d92f9d21154c	960	fp_int tmp;
wolfSSL	0:d92f9d21154c	961	fp_init(&tmp);
wolfSSL	0:d92f9d21154c	962	fp_mul(a, b, &tmp);
wolfSSL	0:d92f9d21154c	963	return fp_mod(&tmp, c, d);
wolfSSL	0:d92f9d21154c	964	}
wolfSSL	0:d92f9d21154c	965
wolfSSL	0:d92f9d21154c	966	#ifdef TFM_TIMING_RESISTANT
wolfSSL	0:d92f9d21154c	967
wolfSSL	0:d92f9d21154c	968	/* timing resistant montgomery ladder based exptmod
wolfSSL	0:d92f9d21154c	969
wolfSSL	0:d92f9d21154c	970	Based on work by Marc Joye, Sung-Ming Yen, "The Montgomery Powering Ladder", Cryptographic Hardware and Embedded Systems, CHES 2002
wolfSSL	0:d92f9d21154c	971	*/
wolfSSL	0:d92f9d21154c	972	static int _fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
wolfSSL	0:d92f9d21154c	973	{
wolfSSL	0:d92f9d21154c	974	fp_int R[2];
wolfSSL	0:d92f9d21154c	975	fp_digit buf, mp;
wolfSSL	0:d92f9d21154c	976	int err, bitcnt, digidx, y;
wolfSSL	0:d92f9d21154c	977
wolfSSL	0:d92f9d21154c	978	/* now setup montgomery */
wolfSSL	0:d92f9d21154c	979	if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
wolfSSL	0:d92f9d21154c	980	return err;
wolfSSL	0:d92f9d21154c	981	}
wolfSSL	0:d92f9d21154c	982
wolfSSL	0:d92f9d21154c	983	fp_init(&R[0]);
wolfSSL	0:d92f9d21154c	984	fp_init(&R[1]);
wolfSSL	0:d92f9d21154c	985
wolfSSL	0:d92f9d21154c	986	/* now we need R mod m */
wolfSSL	0:d92f9d21154c	987	fp_montgomery_calc_normalization (&R[0], P);
wolfSSL	0:d92f9d21154c	988
wolfSSL	0:d92f9d21154c	989	/* now set R[0][1] to G * R mod m */
wolfSSL	0:d92f9d21154c	990	if (fp_cmp_mag(P, G) != FP_GT) {
wolfSSL	0:d92f9d21154c	991	/* G > P so we reduce it first */
wolfSSL	0:d92f9d21154c	992	fp_mod(G, P, &R[1]);
wolfSSL	0:d92f9d21154c	993	} else {
wolfSSL	0:d92f9d21154c	994	fp_copy(G, &R[1]);
wolfSSL	0:d92f9d21154c	995	}
wolfSSL	0:d92f9d21154c	996	fp_mulmod (&R[1], &R[0], P, &R[1]);
wolfSSL	0:d92f9d21154c	997
wolfSSL	0:d92f9d21154c	998	/* for j = t-1 downto 0 do
wolfSSL	0:d92f9d21154c	999	r_!k = R0*R1; r_k = r_k^2
wolfSSL	0:d92f9d21154c	1000	*/
wolfSSL	0:d92f9d21154c	1001
wolfSSL	0:d92f9d21154c	1002	/* set initial mode and bit cnt */
wolfSSL	0:d92f9d21154c	1003	bitcnt = 1;
wolfSSL	0:d92f9d21154c	1004	buf = 0;
wolfSSL	0:d92f9d21154c	1005	digidx = X->used - 1;
wolfSSL	0:d92f9d21154c	1006
wolfSSL	0:d92f9d21154c	1007	for (;;) {
wolfSSL	0:d92f9d21154c	1008	/* grab next digit as required */
wolfSSL	0:d92f9d21154c	1009	if (--bitcnt == 0) {
wolfSSL	0:d92f9d21154c	1010	/* if digidx == -1 we are out of digits so break */
wolfSSL	0:d92f9d21154c	1011	if (digidx == -1) {
wolfSSL	0:d92f9d21154c	1012	break;
wolfSSL	0:d92f9d21154c	1013	}
wolfSSL	0:d92f9d21154c	1014	/* read next digit and reset bitcnt */
wolfSSL	0:d92f9d21154c	1015	buf = X->dp[digidx--];
wolfSSL	0:d92f9d21154c	1016	bitcnt = (int)DIGIT_BIT;
wolfSSL	0:d92f9d21154c	1017	}
wolfSSL	0:d92f9d21154c	1018
wolfSSL	0:d92f9d21154c	1019	/* grab the next msb from the exponent */
wolfSSL	0:d92f9d21154c	1020	y = (int)(buf >> (DIGIT_BIT - 1)) & 1;
wolfSSL	0:d92f9d21154c	1021	buf <<= (fp_digit)1;
wolfSSL	0:d92f9d21154c	1022
wolfSSL	0:d92f9d21154c	1023	/* do ops */
wolfSSL	0:d92f9d21154c	1024	fp_mul(&R[0], &R[1], &R[y^1]); fp_montgomery_reduce(&R[y^1], P, mp);
wolfSSL	0:d92f9d21154c	1025	fp_sqr(&R[y], &R[y]); fp_montgomery_reduce(&R[y], P, mp);
wolfSSL	0:d92f9d21154c	1026	}
wolfSSL	0:d92f9d21154c	1027
wolfSSL	0:d92f9d21154c	1028	fp_montgomery_reduce(&R[0], P, mp);
wolfSSL	0:d92f9d21154c	1029	fp_copy(&R[0], Y);
wolfSSL	0:d92f9d21154c	1030	return FP_OKAY;
wolfSSL	0:d92f9d21154c	1031	}
wolfSSL	0:d92f9d21154c	1032
wolfSSL	0:d92f9d21154c	1033	#else
wolfSSL	0:d92f9d21154c	1034
wolfSSL	0:d92f9d21154c	1035	/* y = g**x (mod b)
wolfSSL	0:d92f9d21154c	1036	* Some restrictions... x must be positive and < b
wolfSSL	0:d92f9d21154c	1037	*/
wolfSSL	0:d92f9d21154c	1038	static int _fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
wolfSSL	0:d92f9d21154c	1039	{
wolfSSL	0:d92f9d21154c	1040	fp_int M[64], res;
wolfSSL	0:d92f9d21154c	1041	fp_digit buf, mp;
wolfSSL	0:d92f9d21154c	1042	int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
wolfSSL	0:d92f9d21154c	1043
wolfSSL	0:d92f9d21154c	1044	/* find window size */
wolfSSL	0:d92f9d21154c	1045	x = fp_count_bits (X);
wolfSSL	0:d92f9d21154c	1046	if (x <= 21) {
wolfSSL	0:d92f9d21154c	1047	winsize = 1;
wolfSSL	0:d92f9d21154c	1048	} else if (x <= 36) {
wolfSSL	0:d92f9d21154c	1049	winsize = 3;
wolfSSL	0:d92f9d21154c	1050	} else if (x <= 140) {
wolfSSL	0:d92f9d21154c	1051	winsize = 4;
wolfSSL	0:d92f9d21154c	1052	} else if (x <= 450) {
wolfSSL	0:d92f9d21154c	1053	winsize = 5;
wolfSSL	0:d92f9d21154c	1054	} else {
wolfSSL	0:d92f9d21154c	1055	winsize = 6;
wolfSSL	0:d92f9d21154c	1056	}
wolfSSL	0:d92f9d21154c	1057
wolfSSL	0:d92f9d21154c	1058	/* init M array */
wolfSSL	0:d92f9d21154c	1059	XMEMSET(M, 0, sizeof(M));
wolfSSL	0:d92f9d21154c	1060
wolfSSL	0:d92f9d21154c	1061	/* now setup montgomery */
wolfSSL	0:d92f9d21154c	1062	if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
wolfSSL	0:d92f9d21154c	1063	return err;
wolfSSL	0:d92f9d21154c	1064	}
wolfSSL	0:d92f9d21154c	1065
wolfSSL	0:d92f9d21154c	1066	/* setup result */
wolfSSL	0:d92f9d21154c	1067	fp_init(&res);
wolfSSL	0:d92f9d21154c	1068
wolfSSL	0:d92f9d21154c	1069	/* create M table
wolfSSL	0:d92f9d21154c	1070	*
wolfSSL	0:d92f9d21154c	1071	* The M table contains powers of the input base, e.g. M[x] = G^x mod P
wolfSSL	0:d92f9d21154c	1072	*
wolfSSL	0:d92f9d21154c	1073	* The first half of the table is not computed though accept for M[0] and M[1]
wolfSSL	0:d92f9d21154c	1074	*/
wolfSSL	0:d92f9d21154c	1075
wolfSSL	0:d92f9d21154c	1076	/* now we need R mod m */
wolfSSL	0:d92f9d21154c	1077	fp_montgomery_calc_normalization (&res, P);
wolfSSL	0:d92f9d21154c	1078
wolfSSL	0:d92f9d21154c	1079	/* now set M[1] to G * R mod m */
wolfSSL	0:d92f9d21154c	1080	if (fp_cmp_mag(P, G) != FP_GT) {
wolfSSL	0:d92f9d21154c	1081	/* G > P so we reduce it first */
wolfSSL	0:d92f9d21154c	1082	fp_mod(G, P, &M[1]);
wolfSSL	0:d92f9d21154c	1083	} else {
wolfSSL	0:d92f9d21154c	1084	fp_copy(G, &M[1]);
wolfSSL	0:d92f9d21154c	1085	}
wolfSSL	0:d92f9d21154c	1086	fp_mulmod (&M[1], &res, P, &M[1]);
wolfSSL	0:d92f9d21154c	1087
wolfSSL	0:d92f9d21154c	1088	/* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */
wolfSSL	0:d92f9d21154c	1089	fp_copy (&M[1], &M[1 << (winsize - 1)]);
wolfSSL	0:d92f9d21154c	1090	for (x = 0; x < (winsize - 1); x++) {
wolfSSL	0:d92f9d21154c	1091	fp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)]);
wolfSSL	0:d92f9d21154c	1092	fp_montgomery_reduce (&M[1 << (winsize - 1)], P, mp);
wolfSSL	0:d92f9d21154c	1093	}
wolfSSL	0:d92f9d21154c	1094
wolfSSL	0:d92f9d21154c	1095	/* create upper table */
wolfSSL	0:d92f9d21154c	1096	for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
wolfSSL	0:d92f9d21154c	1097	fp_mul(&M[x - 1], &M[1], &M[x]);
wolfSSL	0:d92f9d21154c	1098	fp_montgomery_reduce(&M[x], P, mp);
wolfSSL	0:d92f9d21154c	1099	}
wolfSSL	0:d92f9d21154c	1100
wolfSSL	0:d92f9d21154c	1101	/* set initial mode and bit cnt */
wolfSSL	0:d92f9d21154c	1102	mode = 0;
wolfSSL	0:d92f9d21154c	1103	bitcnt = 1;
wolfSSL	0:d92f9d21154c	1104	buf = 0;
wolfSSL	0:d92f9d21154c	1105	digidx = X->used - 1;
wolfSSL	0:d92f9d21154c	1106	bitcpy = 0;
wolfSSL	0:d92f9d21154c	1107	bitbuf = 0;
wolfSSL	0:d92f9d21154c	1108
wolfSSL	0:d92f9d21154c	1109	for (;;) {
wolfSSL	0:d92f9d21154c	1110	/* grab next digit as required */
wolfSSL	0:d92f9d21154c	1111	if (--bitcnt == 0) {
wolfSSL	0:d92f9d21154c	1112	/* if digidx == -1 we are out of digits so break */
wolfSSL	0:d92f9d21154c	1113	if (digidx == -1) {
wolfSSL	0:d92f9d21154c	1114	break;
wolfSSL	0:d92f9d21154c	1115	}
wolfSSL	0:d92f9d21154c	1116	/* read next digit and reset bitcnt */
wolfSSL	0:d92f9d21154c	1117	buf = X->dp[digidx--];
wolfSSL	0:d92f9d21154c	1118	bitcnt = (int)DIGIT_BIT;
wolfSSL	0:d92f9d21154c	1119	}
wolfSSL	0:d92f9d21154c	1120
wolfSSL	0:d92f9d21154c	1121	/* grab the next msb from the exponent */
wolfSSL	0:d92f9d21154c	1122	y = (int)(buf >> (DIGIT_BIT - 1)) & 1;
wolfSSL	0:d92f9d21154c	1123	buf <<= (fp_digit)1;
wolfSSL	0:d92f9d21154c	1124
wolfSSL	0:d92f9d21154c	1125	/* if the bit is zero and mode == 0 then we ignore it
wolfSSL	0:d92f9d21154c	1126	* These represent the leading zero bits before the first 1 bit
wolfSSL	0:d92f9d21154c	1127	* in the exponent. Technically this opt is not required but it
wolfSSL	0:d92f9d21154c	1128	* does lower the # of trivial squaring/reductions used
wolfSSL	0:d92f9d21154c	1129	*/
wolfSSL	0:d92f9d21154c	1130	if (mode == 0 && y == 0) {
wolfSSL	0:d92f9d21154c	1131	continue;
wolfSSL	0:d92f9d21154c	1132	}
wolfSSL	0:d92f9d21154c	1133
wolfSSL	0:d92f9d21154c	1134	/* if the bit is zero and mode == 1 then we square */
wolfSSL	0:d92f9d21154c	1135	if (mode == 1 && y == 0) {
wolfSSL	0:d92f9d21154c	1136	fp_sqr(&res, &res);
wolfSSL	0:d92f9d21154c	1137	fp_montgomery_reduce(&res, P, mp);
wolfSSL	0:d92f9d21154c	1138	continue;
wolfSSL	0:d92f9d21154c	1139	}
wolfSSL	0:d92f9d21154c	1140
wolfSSL	0:d92f9d21154c	1141	/* else we add it to the window */
wolfSSL	0:d92f9d21154c	1142	bitbuf \|= (y << (winsize - ++bitcpy));
wolfSSL	0:d92f9d21154c	1143	mode = 2;
wolfSSL	0:d92f9d21154c	1144
wolfSSL	0:d92f9d21154c	1145	if (bitcpy == winsize) {
wolfSSL	0:d92f9d21154c	1146	/* ok window is filled so square as required and multiply */
wolfSSL	0:d92f9d21154c	1147	/* square first */
wolfSSL	0:d92f9d21154c	1148	for (x = 0; x < winsize; x++) {
wolfSSL	0:d92f9d21154c	1149	fp_sqr(&res, &res);
wolfSSL	0:d92f9d21154c	1150	fp_montgomery_reduce(&res, P, mp);
wolfSSL	0:d92f9d21154c	1151	}
wolfSSL	0:d92f9d21154c	1152
wolfSSL	0:d92f9d21154c	1153	/* then multiply */
wolfSSL	0:d92f9d21154c	1154	fp_mul(&res, &M[bitbuf], &res);
wolfSSL	0:d92f9d21154c	1155	fp_montgomery_reduce(&res, P, mp);
wolfSSL	0:d92f9d21154c	1156
wolfSSL	0:d92f9d21154c	1157	/* empty window and reset */
wolfSSL	0:d92f9d21154c	1158	bitcpy = 0;
wolfSSL	0:d92f9d21154c	1159	bitbuf = 0;
wolfSSL	0:d92f9d21154c	1160	mode = 1;
wolfSSL	0:d92f9d21154c	1161	}
wolfSSL	0:d92f9d21154c	1162	}
wolfSSL	0:d92f9d21154c	1163
wolfSSL	0:d92f9d21154c	1164	/* if bits remain then square/multiply */
wolfSSL	0:d92f9d21154c	1165	if (mode == 2 && bitcpy > 0) {
wolfSSL	0:d92f9d21154c	1166	/* square then multiply if the bit is set */
wolfSSL	0:d92f9d21154c	1167	for (x = 0; x < bitcpy; x++) {
wolfSSL	0:d92f9d21154c	1168	fp_sqr(&res, &res);
wolfSSL	0:d92f9d21154c	1169	fp_montgomery_reduce(&res, P, mp);
wolfSSL	0:d92f9d21154c	1170
wolfSSL	0:d92f9d21154c	1171	/* get next bit of the window */
wolfSSL	0:d92f9d21154c	1172	bitbuf <<= 1;
wolfSSL	0:d92f9d21154c	1173	if ((bitbuf & (1 << winsize)) != 0) {
wolfSSL	0:d92f9d21154c	1174	/* then multiply */
wolfSSL	0:d92f9d21154c	1175	fp_mul(&res, &M[1], &res);
wolfSSL	0:d92f9d21154c	1176	fp_montgomery_reduce(&res, P, mp);
wolfSSL	0:d92f9d21154c	1177	}
wolfSSL	0:d92f9d21154c	1178	}
wolfSSL	0:d92f9d21154c	1179	}
wolfSSL	0:d92f9d21154c	1180
wolfSSL	0:d92f9d21154c	1181	/* fixup result if Montgomery reduction is used
wolfSSL	0:d92f9d21154c	1182	* recall that any value in a Montgomery system is
wolfSSL	0:d92f9d21154c	1183	* actually multiplied by R mod n. So we have
wolfSSL	0:d92f9d21154c	1184	* to reduce one more time to cancel out the factor
wolfSSL	0:d92f9d21154c	1185	* of R.
wolfSSL	0:d92f9d21154c	1186	*/
wolfSSL	0:d92f9d21154c	1187	fp_montgomery_reduce(&res, P, mp);
wolfSSL	0:d92f9d21154c	1188
wolfSSL	0:d92f9d21154c	1189	/* swap res with Y */
wolfSSL	0:d92f9d21154c	1190	fp_copy (&res, Y);
wolfSSL	0:d92f9d21154c	1191	return FP_OKAY;
wolfSSL	0:d92f9d21154c	1192	}
wolfSSL	0:d92f9d21154c	1193
wolfSSL	0:d92f9d21154c	1194	#endif
wolfSSL	0:d92f9d21154c	1195
wolfSSL	0:d92f9d21154c	1196	int fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
wolfSSL	0:d92f9d21154c	1197	{
wolfSSL	0:d92f9d21154c	1198	/* prevent overflows */
wolfSSL	0:d92f9d21154c	1199	if (P->used > (FP_SIZE/2)) {
wolfSSL	0:d92f9d21154c	1200	return FP_VAL;
wolfSSL	0:d92f9d21154c	1201	}
wolfSSL	0:d92f9d21154c	1202
wolfSSL	0:d92f9d21154c	1203	if (X->sign == FP_NEG) {
wolfSSL	0:d92f9d21154c	1204	#ifndef POSITIVE_EXP_ONLY /* reduce stack if assume no negatives */
wolfSSL	0:d92f9d21154c	1205	int err;
wolfSSL	0:d92f9d21154c	1206	fp_int tmp;
wolfSSL	0:d92f9d21154c	1207
wolfSSL	0:d92f9d21154c	1208	/* yes, copy G and invmod it */
wolfSSL	0:d92f9d21154c	1209	fp_copy(G, &tmp);
wolfSSL	0:d92f9d21154c	1210	if ((err = fp_invmod(&tmp, P, &tmp)) != FP_OKAY) {
wolfSSL	0:d92f9d21154c	1211	return err;
wolfSSL	0:d92f9d21154c	1212	}
wolfSSL	0:d92f9d21154c	1213	X->sign = FP_ZPOS;
wolfSSL	0:d92f9d21154c	1214	err = _fp_exptmod(&tmp, X, P, Y);
wolfSSL	0:d92f9d21154c	1215	if (X != Y) {
wolfSSL	0:d92f9d21154c	1216	X->sign = FP_NEG;
wolfSSL	0:d92f9d21154c	1217	}
wolfSSL	0:d92f9d21154c	1218	return err;
wolfSSL	0:d92f9d21154c	1219	#else
wolfSSL	0:d92f9d21154c	1220	return FP_VAL;
wolfSSL	0:d92f9d21154c	1221	#endif
wolfSSL	0:d92f9d21154c	1222	}
wolfSSL	0:d92f9d21154c	1223	else {
wolfSSL	0:d92f9d21154c	1224	/* Positive exponent so just exptmod */
wolfSSL	0:d92f9d21154c	1225	return _fp_exptmod(G, X, P, Y);
wolfSSL	0:d92f9d21154c	1226	}
wolfSSL	0:d92f9d21154c	1227	}
wolfSSL	0:d92f9d21154c	1228
wolfSSL	0:d92f9d21154c	1229	/* computes a = 2*b /
wolfSSL	0:d92f9d21154c	1230	void fp_2expt(fp_int *a, int b)
wolfSSL	0:d92f9d21154c	1231	{
wolfSSL	0:d92f9d21154c	1232	int z;
wolfSSL	0:d92f9d21154c	1233
wolfSSL	0:d92f9d21154c	1234	/* zero a as per default */
wolfSSL	0:d92f9d21154c	1235	fp_zero (a);
wolfSSL	0:d92f9d21154c	1236
wolfSSL	0:d92f9d21154c	1237	if (b < 0) {
wolfSSL	0:d92f9d21154c	1238	return;
wolfSSL	0:d92f9d21154c	1239	}
wolfSSL	0:d92f9d21154c	1240
wolfSSL	0:d92f9d21154c	1241	z = b / DIGIT_BIT;
wolfSSL	0:d92f9d21154c	1242	if (z >= FP_SIZE) {
wolfSSL	0:d92f9d21154c	1243	return;
wolfSSL	0:d92f9d21154c	1244	}
wolfSSL	0:d92f9d21154c	1245
wolfSSL	0:d92f9d21154c	1246	/* set the used count of where the bit will go */
wolfSSL	0:d92f9d21154c	1247	a->used = z + 1;
wolfSSL	0:d92f9d21154c	1248
wolfSSL	0:d92f9d21154c	1249	/* put the single bit in its place */
wolfSSL	0:d92f9d21154c	1250	a->dp[z] = ((fp_digit)1) << (b % DIGIT_BIT);
wolfSSL	0:d92f9d21154c	1251	}
wolfSSL	0:d92f9d21154c	1252
wolfSSL	0:d92f9d21154c	1253	/* b = aa /
wolfSSL	0:d92f9d21154c	1254	void fp_sqr(fp_int A, fp_int B)
wolfSSL	0:d92f9d21154c	1255	{
wolfSSL	0:d92f9d21154c	1256	int y = A->used;
wolfSSL	0:d92f9d21154c	1257
wolfSSL	0:d92f9d21154c	1258	/* call generic if we're out of range */
wolfSSL	0:d92f9d21154c	1259	if (y + y > FP_SIZE) {
wolfSSL	0:d92f9d21154c	1260	fp_sqr_comba(A, B);
wolfSSL	0:d92f9d21154c	1261	return ;
wolfSSL	0:d92f9d21154c	1262	}
wolfSSL	0:d92f9d21154c	1263
wolfSSL	0:d92f9d21154c	1264	#if defined(TFM_SQR3)
wolfSSL	0:d92f9d21154c	1265	if (y <= 3) {
wolfSSL	0:d92f9d21154c	1266	fp_sqr_comba3(A,B);
wolfSSL	0:d92f9d21154c	1267	return;
wolfSSL	0:d92f9d21154c	1268	}
wolfSSL	0:d92f9d21154c	1269	#endif
wolfSSL	0:d92f9d21154c	1270	#if defined(TFM_SQR4)
wolfSSL	0:d92f9d21154c	1271	if (y == 4) {
wolfSSL	0:d92f9d21154c	1272	fp_sqr_comba4(A,B);
wolfSSL	0:d92f9d21154c	1273	return;
wolfSSL	0:d92f9d21154c	1274	}
wolfSSL	0:d92f9d21154c	1275	#endif
wolfSSL	0:d92f9d21154c	1276	#if defined(TFM_SQR6)
wolfSSL	0:d92f9d21154c	1277	if (y <= 6) {
wolfSSL	0:d92f9d21154c	1278	fp_sqr_comba6(A,B);
wolfSSL	0:d92f9d21154c	1279	return;
wolfSSL	0:d92f9d21154c	1280	}
wolfSSL	0:d92f9d21154c	1281	#endif
wolfSSL	0:d92f9d21154c	1282	#if defined(TFM_SQR7)
wolfSSL	0:d92f9d21154c	1283	if (y == 7) {
wolfSSL	0:d92f9d21154c	1284	fp_sqr_comba7(A,B);
wolfSSL	0:d92f9d21154c	1285	return;
wolfSSL	0:d92f9d21154c	1286	}
wolfSSL	0:d92f9d21154c	1287	#endif
wolfSSL	0:d92f9d21154c	1288	#if defined(TFM_SQR8)
wolfSSL	0:d92f9d21154c	1289	if (y == 8) {
wolfSSL	0:d92f9d21154c	1290	fp_sqr_comba8(A,B);
wolfSSL	0:d92f9d21154c	1291	return;
wolfSSL	0:d92f9d21154c	1292	}
wolfSSL	0:d92f9d21154c	1293	#endif
wolfSSL	0:d92f9d21154c	1294	#if defined(TFM_SQR9)
wolfSSL	0:d92f9d21154c	1295	if (y == 9) {
wolfSSL	0:d92f9d21154c	1296	fp_sqr_comba9(A,B);
wolfSSL	0:d92f9d21154c	1297	return;
wolfSSL	0:d92f9d21154c	1298	}
wolfSSL	0:d92f9d21154c	1299	#endif
wolfSSL	0:d92f9d21154c	1300	#if defined(TFM_SQR12)
wolfSSL	0:d92f9d21154c	1301	if (y <= 12) {
wolfSSL	0:d92f9d21154c	1302	fp_sqr_comba12(A,B);
wolfSSL	0:d92f9d21154c	1303	return;
wolfSSL	0:d92f9d21154c	1304	}
wolfSSL	0:d92f9d21154c	1305	#endif
wolfSSL	0:d92f9d21154c	1306	#if defined(TFM_SQR17)
wolfSSL	0:d92f9d21154c	1307	if (y <= 17) {
wolfSSL	0:d92f9d21154c	1308	fp_sqr_comba17(A,B);
wolfSSL	0:d92f9d21154c	1309	return;
wolfSSL	0:d92f9d21154c	1310	}
wolfSSL	0:d92f9d21154c	1311	#endif
wolfSSL	0:d92f9d21154c	1312	#if defined(TFM_SMALL_SET)
wolfSSL	0:d92f9d21154c	1313	if (y <= 16) {
wolfSSL	0:d92f9d21154c	1314	fp_sqr_comba_small(A,B);
wolfSSL	0:d92f9d21154c	1315	return;
wolfSSL	0:d92f9d21154c	1316	}
wolfSSL	0:d92f9d21154c	1317	#endif
wolfSSL	0:d92f9d21154c	1318	#if defined(TFM_SQR20)
wolfSSL	0:d92f9d21154c	1319	if (y <= 20) {
wolfSSL	0:d92f9d21154c	1320	fp_sqr_comba20(A,B);
wolfSSL	0:d92f9d21154c	1321	return;
wolfSSL	0:d92f9d21154c	1322	}
wolfSSL	0:d92f9d21154c	1323	#endif
wolfSSL	0:d92f9d21154c	1324	#if defined(TFM_SQR24)
wolfSSL	0:d92f9d21154c	1325	if (y <= 24) {
wolfSSL	0:d92f9d21154c	1326	fp_sqr_comba24(A,B);
wolfSSL	0:d92f9d21154c	1327	return;
wolfSSL	0:d92f9d21154c	1328	}
wolfSSL	0:d92f9d21154c	1329	#endif
wolfSSL	0:d92f9d21154c	1330	#if defined(TFM_SQR28)
wolfSSL	0:d92f9d21154c	1331	if (y <= 28) {
wolfSSL	0:d92f9d21154c	1332	fp_sqr_comba28(A,B);
wolfSSL	0:d92f9d21154c	1333	return;
wolfSSL	0:d92f9d21154c	1334	}
wolfSSL	0:d92f9d21154c	1335	#endif
wolfSSL	0:d92f9d21154c	1336	#if defined(TFM_SQR32)
wolfSSL	0:d92f9d21154c	1337	if (y <= 32) {
wolfSSL	0:d92f9d21154c	1338	fp_sqr_comba32(A,B);
wolfSSL	0:d92f9d21154c	1339	return;
wolfSSL	0:d92f9d21154c	1340	}
wolfSSL	0:d92f9d21154c	1341	#endif
wolfSSL	0:d92f9d21154c	1342	#if defined(TFM_SQR48)
wolfSSL	0:d92f9d21154c	1343	if (y <= 48) {
wolfSSL	0:d92f9d21154c	1344	fp_sqr_comba48(A,B);
wolfSSL	0:d92f9d21154c	1345	return;
wolfSSL	0:d92f9d21154c	1346	}
wolfSSL	0:d92f9d21154c	1347	#endif
wolfSSL	0:d92f9d21154c	1348	#if defined(TFM_SQR64)
wolfSSL	0:d92f9d21154c	1349	if (y <= 64) {
wolfSSL	0:d92f9d21154c	1350	fp_sqr_comba64(A,B);
wolfSSL	0:d92f9d21154c	1351	return;
wolfSSL	0:d92f9d21154c	1352	}
wolfSSL	0:d92f9d21154c	1353	#endif
wolfSSL	0:d92f9d21154c	1354	fp_sqr_comba(A, B);
wolfSSL	0:d92f9d21154c	1355	}
wolfSSL	0:d92f9d21154c	1356
wolfSSL	0:d92f9d21154c	1357	/* generic comba squarer */
wolfSSL	0:d92f9d21154c	1358	void fp_sqr_comba(fp_int A, fp_int B)
wolfSSL	0:d92f9d21154c	1359	{
wolfSSL	0:d92f9d21154c	1360	int pa, ix, iz;
wolfSSL	0:d92f9d21154c	1361	fp_digit c0, c1, c2;
wolfSSL	0:d92f9d21154c	1362	fp_int tmp, *dst;
wolfSSL	0:d92f9d21154c	1363	#ifdef TFM_ISO
wolfSSL	0:d92f9d21154c	1364	fp_word tt;
wolfSSL	0:d92f9d21154c	1365	#endif
wolfSSL	0:d92f9d21154c	1366
wolfSSL	0:d92f9d21154c	1367	/* get size of output and trim */
wolfSSL	0:d92f9d21154c	1368	pa = A->used + A->used;
wolfSSL	0:d92f9d21154c	1369	if (pa >= FP_SIZE) {
wolfSSL	0:d92f9d21154c	1370	pa = FP_SIZE-1;
wolfSSL	0:d92f9d21154c	1371	}
wolfSSL	0:d92f9d21154c	1372
wolfSSL	0:d92f9d21154c	1373	/* number of output digits to produce */
wolfSSL	0:d92f9d21154c	1374	COMBA_START;
wolfSSL	0:d92f9d21154c	1375	COMBA_CLEAR;
wolfSSL	0:d92f9d21154c	1376
wolfSSL	0:d92f9d21154c	1377	if (A == B) {
wolfSSL	0:d92f9d21154c	1378	fp_init(&tmp);
wolfSSL	0:d92f9d21154c	1379	dst = &tmp;
wolfSSL	0:d92f9d21154c	1380	} else {
wolfSSL	0:d92f9d21154c	1381	fp_zero(B);
wolfSSL	0:d92f9d21154c	1382	dst = B;
wolfSSL	0:d92f9d21154c	1383	}
wolfSSL	0:d92f9d21154c	1384
wolfSSL	0:d92f9d21154c	1385	for (ix = 0; ix < pa; ix++) {
wolfSSL	0:d92f9d21154c	1386	int tx, ty, iy;
wolfSSL	0:d92f9d21154c	1387	fp_digit tmpy, tmpx;
wolfSSL	0:d92f9d21154c	1388
wolfSSL	0:d92f9d21154c	1389	/* get offsets into the two bignums */
wolfSSL	0:d92f9d21154c	1390	ty = MIN(A->used-1, ix);
wolfSSL	0:d92f9d21154c	1391	tx = ix - ty;
wolfSSL	0:d92f9d21154c	1392
wolfSSL	0:d92f9d21154c	1393	/* setup temp aliases */
wolfSSL	0:d92f9d21154c	1394	tmpx = A->dp + tx;
wolfSSL	0:d92f9d21154c	1395	tmpy = A->dp + ty;
wolfSSL	0:d92f9d21154c	1396
wolfSSL	0:d92f9d21154c	1397	/* this is the number of times the loop will iterrate,
wolfSSL	0:d92f9d21154c	1398	while (tx++ < a->used && ty-- >= 0) { ... }
wolfSSL	0:d92f9d21154c	1399	*/
wolfSSL	0:d92f9d21154c	1400	iy = MIN(A->used-tx, ty+1);
wolfSSL	0:d92f9d21154c	1401
wolfSSL	0:d92f9d21154c	1402	/* now for squaring tx can never equal ty
wolfSSL	0:d92f9d21154c	1403	* we halve the distance since they approach
wolfSSL	0:d92f9d21154c	1404	* at a rate of 2x and we have to round because
wolfSSL	0:d92f9d21154c	1405	* odd cases need to be executed
wolfSSL	0:d92f9d21154c	1406	*/
wolfSSL	0:d92f9d21154c	1407	iy = MIN(iy, (ty-tx+1)>>1);
wolfSSL	0:d92f9d21154c	1408
wolfSSL	0:d92f9d21154c	1409	/* forward carries */
wolfSSL	0:d92f9d21154c	1410	COMBA_FORWARD;
wolfSSL	0:d92f9d21154c	1411
wolfSSL	0:d92f9d21154c	1412	/* execute loop */
wolfSSL	0:d92f9d21154c	1413	for (iz = 0; iz < iy; iz++) {
wolfSSL	0:d92f9d21154c	1414	SQRADD2(tmpx++, tmpy--);
wolfSSL	0:d92f9d21154c	1415	}
wolfSSL	0:d92f9d21154c	1416
wolfSSL	0:d92f9d21154c	1417	/* even columns have the square term in them */
wolfSSL	0:d92f9d21154c	1418	if ((ix&1) == 0) {
wolfSSL	0:d92f9d21154c	1419	/* TAO change COMBA_ADD back to SQRADD */
wolfSSL	0:d92f9d21154c	1420	SQRADD(A->dp[ix>>1], A->dp[ix>>1]);
wolfSSL	0:d92f9d21154c	1421	}
wolfSSL	0:d92f9d21154c	1422
wolfSSL	0:d92f9d21154c	1423	/* store it */
wolfSSL	0:d92f9d21154c	1424	COMBA_STORE(dst->dp[ix]);
wolfSSL	0:d92f9d21154c	1425	}
wolfSSL	0:d92f9d21154c	1426
wolfSSL	0:d92f9d21154c	1427	COMBA_FINI;
wolfSSL	0:d92f9d21154c	1428
wolfSSL	0:d92f9d21154c	1429	/* setup dest */
wolfSSL	0:d92f9d21154c	1430	dst->used = pa;
wolfSSL	0:d92f9d21154c	1431	fp_clamp (dst);
wolfSSL	0:d92f9d21154c	1432	if (dst != B) {
wolfSSL	0:d92f9d21154c	1433	fp_copy(dst, B);
wolfSSL	0:d92f9d21154c	1434	}
wolfSSL	0:d92f9d21154c	1435	}
wolfSSL	0:d92f9d21154c	1436
wolfSSL	0:d92f9d21154c	1437	int fp_cmp(fp_int a, fp_int b)
wolfSSL	0:d92f9d21154c	1438	{
wolfSSL	0:d92f9d21154c	1439	if (a->sign == FP_NEG && b->sign == FP_ZPOS) {
wolfSSL	0:d92f9d21154c	1440	return FP_LT;
wolfSSL	0:d92f9d21154c	1441	} else if (a->sign == FP_ZPOS && b->sign == FP_NEG) {
wolfSSL	0:d92f9d21154c	1442	return FP_GT;
wolfSSL	0:d92f9d21154c	1443	} else {
wolfSSL	0:d92f9d21154c	1444	/* compare digits */
wolfSSL	0:d92f9d21154c	1445	if (a->sign == FP_NEG) {
wolfSSL	0:d92f9d21154c	1446	/* if negative compare opposite direction */
wolfSSL	0:d92f9d21154c	1447	return fp_cmp_mag(b, a);
wolfSSL	0:d92f9d21154c	1448	} else {
wolfSSL	0:d92f9d21154c	1449	return fp_cmp_mag(a, b);
wolfSSL	0:d92f9d21154c	1450	}
wolfSSL	0:d92f9d21154c	1451	}
wolfSSL	0:d92f9d21154c	1452	}
wolfSSL	0:d92f9d21154c	1453
wolfSSL	0:d92f9d21154c	1454	/* compare against a single digit */
wolfSSL	0:d92f9d21154c	1455	int fp_cmp_d(fp_int *a, fp_digit b)
wolfSSL	0:d92f9d21154c	1456	{
wolfSSL	0:d92f9d21154c	1457	/* compare based on sign */
wolfSSL	0:d92f9d21154c	1458	if ((b && a->used == 0) \|\| a->sign == FP_NEG) {
wolfSSL	0:d92f9d21154c	1459	return FP_LT;
wolfSSL	0:d92f9d21154c	1460	}
wolfSSL	0:d92f9d21154c	1461
wolfSSL	0:d92f9d21154c	1462	/* compare based on magnitude */
wolfSSL	0:d92f9d21154c	1463	if (a->used > 1) {
wolfSSL	0:d92f9d21154c	1464	return FP_GT;
wolfSSL	0:d92f9d21154c	1465	}
wolfSSL	0:d92f9d21154c	1466
wolfSSL	0:d92f9d21154c	1467	/* compare the only digit of a to b */
wolfSSL	0:d92f9d21154c	1468	if (a->dp[0] > b) {
wolfSSL	0:d92f9d21154c	1469	return FP_GT;
wolfSSL	0:d92f9d21154c	1470	} else if (a->dp[0] < b) {
wolfSSL	0:d92f9d21154c	1471	return FP_LT;
wolfSSL	0:d92f9d21154c	1472	} else {
wolfSSL	0:d92f9d21154c	1473	return FP_EQ;
wolfSSL	0:d92f9d21154c	1474	}
wolfSSL	0:d92f9d21154c	1475
wolfSSL	0:d92f9d21154c	1476	}
wolfSSL	0:d92f9d21154c	1477
wolfSSL	0:d92f9d21154c	1478	int fp_cmp_mag(fp_int a, fp_int b)
wolfSSL	0:d92f9d21154c	1479	{
wolfSSL	0:d92f9d21154c	1480	int x;
wolfSSL	0:d92f9d21154c	1481
wolfSSL	0:d92f9d21154c	1482	if (a->used > b->used) {
wolfSSL	0:d92f9d21154c	1483	return FP_GT;
wolfSSL	0:d92f9d21154c	1484	} else if (a->used < b->used) {
wolfSSL	0:d92f9d21154c	1485	return FP_LT;
wolfSSL	0:d92f9d21154c	1486	} else {
wolfSSL	0:d92f9d21154c	1487	for (x = a->used - 1; x >= 0; x--) {
wolfSSL	0:d92f9d21154c	1488	if (a->dp[x] > b->dp[x]) {
wolfSSL	0:d92f9d21154c	1489	return FP_GT;
wolfSSL	0:d92f9d21154c	1490	} else if (a->dp[x] < b->dp[x]) {
wolfSSL	0:d92f9d21154c	1491	return FP_LT;
wolfSSL	0:d92f9d21154c	1492	}
wolfSSL	0:d92f9d21154c	1493	}
wolfSSL	0:d92f9d21154c	1494	}
wolfSSL	0:d92f9d21154c	1495	return FP_EQ;
wolfSSL	0:d92f9d21154c	1496	}
wolfSSL	0:d92f9d21154c	1497
wolfSSL	0:d92f9d21154c	1498	/* setups the montgomery reduction */
wolfSSL	0:d92f9d21154c	1499	int fp_montgomery_setup(fp_int a, fp_digit rho)
wolfSSL	0:d92f9d21154c	1500	{
wolfSSL	0:d92f9d21154c	1501	fp_digit x, b;
wolfSSL	0:d92f9d21154c	1502
wolfSSL	0:d92f9d21154c	1503	/* fast inversion mod 2**k
wolfSSL	0:d92f9d21154c	1504	*
wolfSSL	0:d92f9d21154c	1505	* Based on the fact that
wolfSSL	0:d92f9d21154c	1506	*
wolfSSL	0:d92f9d21154c	1507	* XA = 1 (mod 2n) => (X(2-XA)) A = 1 (mod 22n)
wolfSSL	0:d92f9d21154c	1508	* => 2XA - XXA*A = 1
wolfSSL	0:d92f9d21154c	1509	* => 2*(1) - (1) = 1
wolfSSL	0:d92f9d21154c	1510	*/
wolfSSL	0:d92f9d21154c	1511	b = a->dp[0];
wolfSSL	0:d92f9d21154c	1512
wolfSSL	0:d92f9d21154c	1513	if ((b & 1) == 0) {
wolfSSL	0:d92f9d21154c	1514	return FP_VAL;
wolfSSL	0:d92f9d21154c	1515	}
wolfSSL	0:d92f9d21154c	1516
wolfSSL	0:d92f9d21154c	1517	x = (((b + 2) & 4) << 1) + b; /* here xa==1 mod 24 /
wolfSSL	0:d92f9d21154c	1518	x = 2 - b x; /* here xa==1 mod 28 /
wolfSSL	0:d92f9d21154c	1519	x = 2 - b x; /* here xa==1 mod 216 /
wolfSSL	0:d92f9d21154c	1520	x = 2 - b x; /* here xa==1 mod 232 /
wolfSSL	0:d92f9d21154c	1521	#ifdef FP_64BIT
wolfSSL	0:d92f9d21154c	1522	x = 2 - b x; /* here xa==1 mod 264 /
wolfSSL	0:d92f9d21154c	1523	#endif
wolfSSL	0:d92f9d21154c	1524
wolfSSL	0:d92f9d21154c	1525	/* rho = -1/m mod b */
wolfSSL	0:d92f9d21154c	1526	*rho = (fp_digit) (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));
wolfSSL	0:d92f9d21154c	1527
wolfSSL	0:d92f9d21154c	1528	return FP_OKAY;
wolfSSL	0:d92f9d21154c	1529	}
wolfSSL	0:d92f9d21154c	1530
wolfSSL	0:d92f9d21154c	1531	/* computes a = B**n mod b without division or multiplication useful for
wolfSSL	0:d92f9d21154c	1532	* normalizing numbers in a Montgomery system.
wolfSSL	0:d92f9d21154c	1533	*/
wolfSSL	0:d92f9d21154c	1534	void fp_montgomery_calc_normalization(fp_int a, fp_int b)
wolfSSL	0:d92f9d21154c	1535	{
wolfSSL	0:d92f9d21154c	1536	int x, bits;
wolfSSL	0:d92f9d21154c	1537
wolfSSL	0:d92f9d21154c	1538	/* how many bits of last digit does b use */
wolfSSL	0:d92f9d21154c	1539	bits = fp_count_bits (b) % DIGIT_BIT;
wolfSSL	0:d92f9d21154c	1540	if (!bits) bits = DIGIT_BIT;
wolfSSL	0:d92f9d21154c	1541
wolfSSL	0:d92f9d21154c	1542	/* compute A = B^(n-1) * 2^(bits-1) */
wolfSSL	0:d92f9d21154c	1543	if (b->used > 1) {
wolfSSL	0:d92f9d21154c	1544	fp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1);
wolfSSL	0:d92f9d21154c	1545	} else {
wolfSSL	0:d92f9d21154c	1546	fp_set(a, 1);
wolfSSL	0:d92f9d21154c	1547	bits = 1;
wolfSSL	0:d92f9d21154c	1548	}
wolfSSL	0:d92f9d21154c	1549
wolfSSL	0:d92f9d21154c	1550	/* now compute C = A * B mod b */
wolfSSL	0:d92f9d21154c	1551	for (x = bits - 1; x < (int)DIGIT_BIT; x++) {
wolfSSL	0:d92f9d21154c	1552	fp_mul_2 (a, a);
wolfSSL	0:d92f9d21154c	1553	if (fp_cmp_mag (a, b) != FP_LT) {
wolfSSL	0:d92f9d21154c	1554	s_fp_sub (a, b, a);
wolfSSL	0:d92f9d21154c	1555	}
wolfSSL	0:d92f9d21154c	1556	}
wolfSSL	0:d92f9d21154c	1557	}
wolfSSL	0:d92f9d21154c	1558
wolfSSL	0:d92f9d21154c	1559
wolfSSL	0:d92f9d21154c	1560	#ifdef TFM_SMALL_MONT_SET
wolfSSL	0:d92f9d21154c	1561	#include "fp_mont_small.i"
wolfSSL	0:d92f9d21154c	1562	#endif
wolfSSL	0:d92f9d21154c	1563
wolfSSL	0:d92f9d21154c	1564	#ifdef HAVE_INTEL_MULX
wolfSSL	0:d92f9d21154c	1565	static inline void innermul8_mulx(fp_digit c_mulx, fp_digit cy_mulx, fp_digit *tmpm, fp_digit mu)
wolfSSL	0:d92f9d21154c	1566	{
wolfSSL	0:d92f9d21154c	1567	fp_digit _c0, _c1, _c2, _c3, _c4, _c5, _c6, _c7, cy ;
wolfSSL	0:d92f9d21154c	1568
wolfSSL	0:d92f9d21154c	1569	cy = *cy_mulx ;
wolfSSL	0:d92f9d21154c	1570	_c0=c_mulx[0]; _c1=c_mulx[1]; _c2=c_mulx[2]; _c3=c_mulx[3]; _c4=c_mulx[4]; _c5=c_mulx[5]; _c6=c_mulx[6]; _c7=c_mulx[7];
wolfSSL	0:d92f9d21154c	1571	INNERMUL8_MULX ;
wolfSSL	0:d92f9d21154c	1572	c_mulx[0]=_c0; c_mulx[1]=_c1; c_mulx[2]=_c2; c_mulx[3]=_c3; c_mulx[4]=_c4; c_mulx[5]=_c5; c_mulx[6]=_c6; c_mulx[7]=_c7;
wolfSSL	0:d92f9d21154c	1573	*cy_mulx = cy ;
wolfSSL	0:d92f9d21154c	1574	}
wolfSSL	0:d92f9d21154c	1575
wolfSSL	0:d92f9d21154c	1576	/* computes x/R == x (mod N) via Montgomery Reduction */
wolfSSL	0:d92f9d21154c	1577	static void fp_montgomery_reduce_mulx(fp_int a, fp_int m, fp_digit mp)
wolfSSL	0:d92f9d21154c	1578	{
wolfSSL	0:d92f9d21154c	1579	fp_digit c[FP_SIZE], _c, tmpm, mu = 0;
wolfSSL	0:d92f9d21154c	1580	int oldused, x, y, pa;
wolfSSL	0:d92f9d21154c	1581
wolfSSL	0:d92f9d21154c	1582	/* bail if too large */
wolfSSL	0:d92f9d21154c	1583	if (m->used > (FP_SIZE/2)) {
wolfSSL	0:d92f9d21154c	1584	(void)mu; /* shut up compiler */
wolfSSL	0:d92f9d21154c	1585	return;
wolfSSL	0:d92f9d21154c	1586	}
wolfSSL	0:d92f9d21154c	1587
wolfSSL	0:d92f9d21154c	1588	#ifdef TFM_SMALL_MONT_SET
wolfSSL	0:d92f9d21154c	1589	if (m->used <= 16) {
wolfSSL	0:d92f9d21154c	1590	fp_montgomery_reduce_small(a, m, mp);
wolfSSL	0:d92f9d21154c	1591	return;
wolfSSL	0:d92f9d21154c	1592	}
wolfSSL	0:d92f9d21154c	1593	#endif
wolfSSL	0:d92f9d21154c	1594
wolfSSL	0:d92f9d21154c	1595
wolfSSL	0:d92f9d21154c	1596	/* now zero the buff */
wolfSSL	0:d92f9d21154c	1597	XMEMSET(c, 0, sizeof c);
wolfSSL	0:d92f9d21154c	1598	pa = m->used;
wolfSSL	0:d92f9d21154c	1599
wolfSSL	0:d92f9d21154c	1600	/* copy the input */
wolfSSL	0:d92f9d21154c	1601	oldused = a->used;
wolfSSL	0:d92f9d21154c	1602	for (x = 0; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	1603	c[x] = a->dp[x];
wolfSSL	0:d92f9d21154c	1604	}
wolfSSL	0:d92f9d21154c	1605	MONT_START;
wolfSSL	0:d92f9d21154c	1606
wolfSSL	0:d92f9d21154c	1607	for (x = 0; x < pa; x++) {
wolfSSL	0:d92f9d21154c	1608	fp_digit cy = 0;
wolfSSL	0:d92f9d21154c	1609	/* get Mu for this round */
wolfSSL	0:d92f9d21154c	1610	LOOP_START;
wolfSSL	0:d92f9d21154c	1611	_c = c + x;
wolfSSL	0:d92f9d21154c	1612	tmpm = m->dp;
wolfSSL	0:d92f9d21154c	1613	y = 0;
wolfSSL	0:d92f9d21154c	1614	for (; y < (pa & ~7); y += 8) {
wolfSSL	0:d92f9d21154c	1615	innermul8_mulx(_c, &cy, tmpm, mu) ;
wolfSSL	0:d92f9d21154c	1616	_c += 8;
wolfSSL	0:d92f9d21154c	1617	tmpm += 8;
wolfSSL	0:d92f9d21154c	1618	}
wolfSSL	0:d92f9d21154c	1619	for (; y < pa; y++) {
wolfSSL	0:d92f9d21154c	1620	INNERMUL;
wolfSSL	0:d92f9d21154c	1621	++_c;
wolfSSL	0:d92f9d21154c	1622	}
wolfSSL	0:d92f9d21154c	1623	LOOP_END;
wolfSSL	0:d92f9d21154c	1624	while (cy) {
wolfSSL	0:d92f9d21154c	1625	PROPCARRY;
wolfSSL	0:d92f9d21154c	1626	++_c;
wolfSSL	0:d92f9d21154c	1627	}
wolfSSL	0:d92f9d21154c	1628	}
wolfSSL	0:d92f9d21154c	1629
wolfSSL	0:d92f9d21154c	1630	/* now copy out */
wolfSSL	0:d92f9d21154c	1631	_c = c + pa;
wolfSSL	0:d92f9d21154c	1632	tmpm = a->dp;
wolfSSL	0:d92f9d21154c	1633	for (x = 0; x < pa+1; x++) {
wolfSSL	0:d92f9d21154c	1634	tmpm++ = _c++;
wolfSSL	0:d92f9d21154c	1635	}
wolfSSL	0:d92f9d21154c	1636
wolfSSL	0:d92f9d21154c	1637	for (; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	1638	*tmpm++ = 0;
wolfSSL	0:d92f9d21154c	1639	}
wolfSSL	0:d92f9d21154c	1640
wolfSSL	0:d92f9d21154c	1641	MONT_FINI;
wolfSSL	0:d92f9d21154c	1642
wolfSSL	0:d92f9d21154c	1643	a->used = pa+1;
wolfSSL	0:d92f9d21154c	1644	fp_clamp(a);
wolfSSL	0:d92f9d21154c	1645
wolfSSL	0:d92f9d21154c	1646	/* if A >= m then A = A - m */
wolfSSL	0:d92f9d21154c	1647	if (fp_cmp_mag (a, m) != FP_LT) {
wolfSSL	0:d92f9d21154c	1648	s_fp_sub (a, m, a);
wolfSSL	0:d92f9d21154c	1649	}
wolfSSL	0:d92f9d21154c	1650	}
wolfSSL	0:d92f9d21154c	1651	#endif
wolfSSL	0:d92f9d21154c	1652
wolfSSL	0:d92f9d21154c	1653	/* computes x/R == x (mod N) via Montgomery Reduction */
wolfSSL	0:d92f9d21154c	1654	void fp_montgomery_reduce(fp_int a, fp_int m, fp_digit mp)
wolfSSL	0:d92f9d21154c	1655	{
wolfSSL	0:d92f9d21154c	1656	fp_digit c[FP_SIZE], _c, tmpm, mu = 0;
wolfSSL	0:d92f9d21154c	1657	int oldused, x, y, pa;
wolfSSL	0:d92f9d21154c	1658
wolfSSL	0:d92f9d21154c	1659	IF_HAVE_INTEL_MULX(fp_montgomery_reduce_mulx(a, m, mp), return) ;
wolfSSL	0:d92f9d21154c	1660
wolfSSL	0:d92f9d21154c	1661	/* bail if too large */
wolfSSL	0:d92f9d21154c	1662	if (m->used > (FP_SIZE/2)) {
wolfSSL	0:d92f9d21154c	1663	(void)mu; /* shut up compiler */
wolfSSL	0:d92f9d21154c	1664	return;
wolfSSL	0:d92f9d21154c	1665	}
wolfSSL	0:d92f9d21154c	1666
wolfSSL	0:d92f9d21154c	1667	#ifdef TFM_SMALL_MONT_SET
wolfSSL	0:d92f9d21154c	1668	if (m->used <= 16) {
wolfSSL	0:d92f9d21154c	1669	fp_montgomery_reduce_small(a, m, mp);
wolfSSL	0:d92f9d21154c	1670	return;
wolfSSL	0:d92f9d21154c	1671	}
wolfSSL	0:d92f9d21154c	1672	#endif
wolfSSL	0:d92f9d21154c	1673
wolfSSL	0:d92f9d21154c	1674
wolfSSL	0:d92f9d21154c	1675	/* now zero the buff */
wolfSSL	0:d92f9d21154c	1676	XMEMSET(c, 0, sizeof c);
wolfSSL	0:d92f9d21154c	1677	pa = m->used;
wolfSSL	0:d92f9d21154c	1678
wolfSSL	0:d92f9d21154c	1679	/* copy the input */
wolfSSL	0:d92f9d21154c	1680	oldused = a->used;
wolfSSL	0:d92f9d21154c	1681	for (x = 0; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	1682	c[x] = a->dp[x];
wolfSSL	0:d92f9d21154c	1683	}
wolfSSL	0:d92f9d21154c	1684	MONT_START;
wolfSSL	0:d92f9d21154c	1685
wolfSSL	0:d92f9d21154c	1686	for (x = 0; x < pa; x++) {
wolfSSL	0:d92f9d21154c	1687	fp_digit cy = 0;
wolfSSL	0:d92f9d21154c	1688	/* get Mu for this round */
wolfSSL	0:d92f9d21154c	1689	LOOP_START;
wolfSSL	0:d92f9d21154c	1690	_c = c + x;
wolfSSL	0:d92f9d21154c	1691	tmpm = m->dp;
wolfSSL	0:d92f9d21154c	1692	y = 0;
wolfSSL	0:d92f9d21154c	1693	#if (defined(TFM_SSE2) \|\| defined(TFM_X86_64))
wolfSSL	0:d92f9d21154c	1694	for (; y < (pa & ~7); y += 8) {
wolfSSL	0:d92f9d21154c	1695	INNERMUL8 ;
wolfSSL	0:d92f9d21154c	1696	_c += 8;
wolfSSL	0:d92f9d21154c	1697	tmpm += 8;
wolfSSL	0:d92f9d21154c	1698	}
wolfSSL	0:d92f9d21154c	1699	#endif
wolfSSL	0:d92f9d21154c	1700	for (; y < pa; y++) {
wolfSSL	0:d92f9d21154c	1701	INNERMUL;
wolfSSL	0:d92f9d21154c	1702	++_c;
wolfSSL	0:d92f9d21154c	1703	}
wolfSSL	0:d92f9d21154c	1704	LOOP_END;
wolfSSL	0:d92f9d21154c	1705	while (cy) {
wolfSSL	0:d92f9d21154c	1706	PROPCARRY;
wolfSSL	0:d92f9d21154c	1707	++_c;
wolfSSL	0:d92f9d21154c	1708	}
wolfSSL	0:d92f9d21154c	1709	}
wolfSSL	0:d92f9d21154c	1710
wolfSSL	0:d92f9d21154c	1711	/* now copy out */
wolfSSL	0:d92f9d21154c	1712	_c = c + pa;
wolfSSL	0:d92f9d21154c	1713	tmpm = a->dp;
wolfSSL	0:d92f9d21154c	1714	for (x = 0; x < pa+1; x++) {
wolfSSL	0:d92f9d21154c	1715	tmpm++ = _c++;
wolfSSL	0:d92f9d21154c	1716	}
wolfSSL	0:d92f9d21154c	1717
wolfSSL	0:d92f9d21154c	1718	for (; x < oldused; x++) {
wolfSSL	0:d92f9d21154c	1719	*tmpm++ = 0;
wolfSSL	0:d92f9d21154c	1720	}
wolfSSL	0:d92f9d21154c	1721
wolfSSL	0:d92f9d21154c	1722	MONT_FINI;
wolfSSL	0:d92f9d21154c	1723
wolfSSL	0:d92f9d21154c	1724	a->used = pa+1;
wolfSSL	0:d92f9d21154c	1725	fp_clamp(a);
wolfSSL	0:d92f9d21154c	1726
wolfSSL	0:d92f9d21154c	1727	/* if A >= m then A = A - m */
wolfSSL	0:d92f9d21154c	1728	if (fp_cmp_mag (a, m) != FP_LT) {
wolfSSL	0:d92f9d21154c	1729	s_fp_sub (a, m, a);
wolfSSL	0:d92f9d21154c	1730	}
wolfSSL	0:d92f9d21154c	1731	}
wolfSSL	0:d92f9d21154c	1732
wolfSSL	0:d92f9d21154c	1733	void fp_read_unsigned_bin(fp_int a, unsigned char b, int c)
wolfSSL	0:d92f9d21154c	1734	{
wolfSSL	0:d92f9d21154c	1735	/* zero the int */
wolfSSL	0:d92f9d21154c	1736	fp_zero (a);
wolfSSL	0:d92f9d21154c	1737
wolfSSL	0:d92f9d21154c	1738	/* If we know the endianness of this architecture, and we're using
wolfSSL	0:d92f9d21154c	1739	32-bit fp_digits, we can optimize this */
wolfSSL	0:d92f9d21154c	1740	#if (defined(LITTLE_ENDIAN_ORDER) \|\| defined(BIG_ENDIAN_ORDER)) && defined(FP_32BIT)
wolfSSL	0:d92f9d21154c	1741	/* But not for both simultaneously */
wolfSSL	0:d92f9d21154c	1742	#if defined(LITTLE_ENDIAN_ORDER) && defined(BIG_ENDIAN_ORDER)
wolfSSL	0:d92f9d21154c	1743	#error Both LITTLE_ENDIAN_ORDER and BIG_ENDIAN_ORDER defined.
wolfSSL	0:d92f9d21154c	1744	#endif
wolfSSL	0:d92f9d21154c	1745	{
wolfSSL	0:d92f9d21154c	1746	unsigned char pd = (unsigned char )a->dp;
wolfSSL	0:d92f9d21154c	1747
wolfSSL	0:d92f9d21154c	1748	if ((unsigned)c > (FP_SIZE * sizeof(fp_digit))) {
wolfSSL	0:d92f9d21154c	1749	int excess = c - (FP_SIZE * sizeof(fp_digit));
wolfSSL	0:d92f9d21154c	1750	c -= excess;
wolfSSL	0:d92f9d21154c	1751	b += excess;
wolfSSL	0:d92f9d21154c	1752	}
wolfSSL	0:d92f9d21154c	1753	a->used = (c + sizeof(fp_digit) - 1)/sizeof(fp_digit);
wolfSSL	0:d92f9d21154c	1754	/* read the bytes in */
wolfSSL	0:d92f9d21154c	1755	#ifdef BIG_ENDIAN_ORDER
wolfSSL	0:d92f9d21154c	1756	{
wolfSSL	0:d92f9d21154c	1757	/* Use Duff's device to unroll the loop. */
wolfSSL	0:d92f9d21154c	1758	int idx = (c - 1) & ~3;
wolfSSL	0:d92f9d21154c	1759	switch (c % 4) {
wolfSSL	0:d92f9d21154c	1760	case 0: do { pd[idx+0] = *b++;
wolfSSL	0:d92f9d21154c	1761	case 3: pd[idx+1] = *b++;
wolfSSL	0:d92f9d21154c	1762	case 2: pd[idx+2] = *b++;
wolfSSL	0:d92f9d21154c	1763	case 1: pd[idx+3] = *b++;
wolfSSL	0:d92f9d21154c	1764	idx -= 4;
wolfSSL	0:d92f9d21154c	1765	} while ((c -= 4) > 0);
wolfSSL	0:d92f9d21154c	1766	}
wolfSSL	0:d92f9d21154c	1767	}
wolfSSL	0:d92f9d21154c	1768	#else
wolfSSL	0:d92f9d21154c	1769	for (c -= 1; c >= 0; c -= 1) {
wolfSSL	0:d92f9d21154c	1770	pd[c] = *b++;
wolfSSL	0:d92f9d21154c	1771	}
wolfSSL	0:d92f9d21154c	1772	#endif
wolfSSL	0:d92f9d21154c	1773	}
wolfSSL	0:d92f9d21154c	1774	#else
wolfSSL	0:d92f9d21154c	1775	/* read the bytes in */
wolfSSL	0:d92f9d21154c	1776	for (; c > 0; c--) {
wolfSSL	0:d92f9d21154c	1777	fp_mul_2d (a, 8, a);
wolfSSL	0:d92f9d21154c	1778	a->dp[0] \|= *b++;
wolfSSL	0:d92f9d21154c	1779	a->used += 1;
wolfSSL	0:d92f9d21154c	1780	}
wolfSSL	0:d92f9d21154c	1781	#endif
wolfSSL	0:d92f9d21154c	1782	fp_clamp (a);
wolfSSL	0:d92f9d21154c	1783	}
wolfSSL	0:d92f9d21154c	1784
wolfSSL	0:d92f9d21154c	1785	void fp_to_unsigned_bin(fp_int a, unsigned char b)
wolfSSL	0:d92f9d21154c	1786	{
wolfSSL	0:d92f9d21154c	1787	int x;
wolfSSL	0:d92f9d21154c	1788	fp_int t;
wolfSSL	0:d92f9d21154c	1789
wolfSSL	0:d92f9d21154c	1790	fp_init_copy(&t, a);
wolfSSL	0:d92f9d21154c	1791
wolfSSL	0:d92f9d21154c	1792	x = 0;
wolfSSL	0:d92f9d21154c	1793	while (fp_iszero (&t) == FP_NO) {
wolfSSL	0:d92f9d21154c	1794	b[x++] = (unsigned char) (t.dp[0] & 255);
wolfSSL	0:d92f9d21154c	1795	fp_div_2d (&t, 8, &t, NULL);
wolfSSL	0:d92f9d21154c	1796	}
wolfSSL	0:d92f9d21154c	1797	fp_reverse (b, x);
wolfSSL	0:d92f9d21154c	1798	}
wolfSSL	0:d92f9d21154c	1799
wolfSSL	0:d92f9d21154c	1800	int fp_unsigned_bin_size(fp_int *a)
wolfSSL	0:d92f9d21154c	1801	{
wolfSSL	0:d92f9d21154c	1802	int size = fp_count_bits (a);
wolfSSL	0:d92f9d21154c	1803	return (size / 8 + ((size & 7) != 0 ? 1 : 0));
wolfSSL	0:d92f9d21154c	1804	}
wolfSSL	0:d92f9d21154c	1805
wolfSSL	0:d92f9d21154c	1806	void fp_set(fp_int *a, fp_digit b)
wolfSSL	0:d92f9d21154c	1807	{
wolfSSL	0:d92f9d21154c	1808	fp_zero(a);
wolfSSL	0:d92f9d21154c	1809	a->dp[0] = b;
wolfSSL	0:d92f9d21154c	1810	a->used = a->dp[0] ? 1 : 0;
wolfSSL	0:d92f9d21154c	1811	}
wolfSSL	0:d92f9d21154c	1812
wolfSSL	0:d92f9d21154c	1813	int fp_count_bits (fp_int * a)
wolfSSL	0:d92f9d21154c	1814	{
wolfSSL	0:d92f9d21154c	1815	int r;
wolfSSL	0:d92f9d21154c	1816	fp_digit q;
wolfSSL	0:d92f9d21154c	1817
wolfSSL	0:d92f9d21154c	1818	/* shortcut */
wolfSSL	0:d92f9d21154c	1819	if (a->used == 0) {
wolfSSL	0:d92f9d21154c	1820	return 0;
wolfSSL	0:d92f9d21154c	1821	}
wolfSSL	0:d92f9d21154c	1822
wolfSSL	0:d92f9d21154c	1823	/* get number of digits and add that */
wolfSSL	0:d92f9d21154c	1824	r = (a->used - 1) * DIGIT_BIT;
wolfSSL	0:d92f9d21154c	1825
wolfSSL	0:d92f9d21154c	1826	/* take the last digit and count the bits in it */
wolfSSL	0:d92f9d21154c	1827	q = a->dp[a->used - 1];
wolfSSL	0:d92f9d21154c	1828	while (q > ((fp_digit) 0)) {
wolfSSL	0:d92f9d21154c	1829	++r;
wolfSSL	0:d92f9d21154c	1830	q >>= ((fp_digit) 1);
wolfSSL	0:d92f9d21154c	1831	}
wolfSSL	0:d92f9d21154c	1832	return r;
wolfSSL	0:d92f9d21154c	1833	}
wolfSSL	0:d92f9d21154c	1834
wolfSSL	0:d92f9d21154c	1835	int fp_leading_bit(fp_int *a)
wolfSSL	0:d92f9d21154c	1836	{
wolfSSL	0:d92f9d21154c	1837	int bit = 0;
wolfSSL	0:d92f9d21154c	1838
wolfSSL	0:d92f9d21154c	1839	if (a->used != 0) {
wolfSSL	0:d92f9d21154c	1840	fp_digit q = a->dp[a->used - 1];
wolfSSL	0:d92f9d21154c	1841	int qSz = sizeof(fp_digit);
wolfSSL	0:d92f9d21154c	1842
wolfSSL	0:d92f9d21154c	1843	while (qSz > 0) {
wolfSSL	0:d92f9d21154c	1844	if ((unsigned char)q != 0)
wolfSSL	0:d92f9d21154c	1845	bit = (q & 0x80) != 0;
wolfSSL	0:d92f9d21154c	1846	q >>= 8;
wolfSSL	0:d92f9d21154c	1847	qSz--;
wolfSSL	0:d92f9d21154c	1848	}
wolfSSL	0:d92f9d21154c	1849	}
wolfSSL	0:d92f9d21154c	1850
wolfSSL	0:d92f9d21154c	1851	return bit;
wolfSSL	0:d92f9d21154c	1852	}
wolfSSL	0:d92f9d21154c	1853
wolfSSL	0:d92f9d21154c	1854	void fp_lshd(fp_int *a, int x)
wolfSSL	0:d92f9d21154c	1855	{
wolfSSL	0:d92f9d21154c	1856	int y;
wolfSSL	0:d92f9d21154c	1857
wolfSSL	0:d92f9d21154c	1858	/* move up and truncate as required */
wolfSSL	0:d92f9d21154c	1859	y = MIN(a->used + x - 1, (int)(FP_SIZE-1));
wolfSSL	0:d92f9d21154c	1860
wolfSSL	0:d92f9d21154c	1861	/* store new size */
wolfSSL	0:d92f9d21154c	1862	a->used = y + 1;
wolfSSL	0:d92f9d21154c	1863
wolfSSL	0:d92f9d21154c	1864	/* move digits */
wolfSSL	0:d92f9d21154c	1865	for (; y >= x; y--) {
wolfSSL	0:d92f9d21154c	1866	a->dp[y] = a->dp[y-x];
wolfSSL	0:d92f9d21154c	1867	}
wolfSSL	0:d92f9d21154c	1868
wolfSSL	0:d92f9d21154c	1869	/* zero lower digits */
wolfSSL	0:d92f9d21154c	1870	for (; y >= 0; y--) {
wolfSSL	0:d92f9d21154c	1871	a->dp[y] = 0;
wolfSSL	0:d92f9d21154c	1872	}
wolfSSL	0:d92f9d21154c	1873
wolfSSL	0:d92f9d21154c	1874	/* clamp digits */
wolfSSL	0:d92f9d21154c	1875	fp_clamp(a);
wolfSSL	0:d92f9d21154c	1876	}
wolfSSL	0:d92f9d21154c	1877
wolfSSL	0:d92f9d21154c	1878
wolfSSL	0:d92f9d21154c	1879	/* right shift by bit count */
wolfSSL	0:d92f9d21154c	1880	void fp_rshb(fp_int *c, int x)
wolfSSL	0:d92f9d21154c	1881	{
wolfSSL	0:d92f9d21154c	1882	register fp_digit *tmpc, mask, shift;
wolfSSL	0:d92f9d21154c	1883	fp_digit r, rr;
wolfSSL	0:d92f9d21154c	1884	fp_digit D = x;
wolfSSL	0:d92f9d21154c	1885
wolfSSL	0:d92f9d21154c	1886	/* mask */
wolfSSL	0:d92f9d21154c	1887	mask = (((fp_digit)1) << D) - 1;
wolfSSL	0:d92f9d21154c	1888
wolfSSL	0:d92f9d21154c	1889	/* shift for lsb */
wolfSSL	0:d92f9d21154c	1890	shift = DIGIT_BIT - D;
wolfSSL	0:d92f9d21154c	1891
wolfSSL	0:d92f9d21154c	1892	/* alias */
wolfSSL	0:d92f9d21154c	1893	tmpc = c->dp + (c->used - 1);
wolfSSL	0:d92f9d21154c	1894
wolfSSL	0:d92f9d21154c	1895	/* carry */
wolfSSL	0:d92f9d21154c	1896	r = 0;
wolfSSL	0:d92f9d21154c	1897	for (x = c->used - 1; x >= 0; x--) {
wolfSSL	0:d92f9d21154c	1898	/* get the lower bits of this word in a temp */
wolfSSL	0:d92f9d21154c	1899	rr = *tmpc & mask;
wolfSSL	0:d92f9d21154c	1900
wolfSSL	0:d92f9d21154c	1901	/* shift the current word and mix in the carry bits from previous word */
wolfSSL	0:d92f9d21154c	1902	tmpc = (tmpc >> D) \| (r << shift);
wolfSSL	0:d92f9d21154c	1903	--tmpc;
wolfSSL	0:d92f9d21154c	1904
wolfSSL	0:d92f9d21154c	1905	/* set the carry to the carry bits of the current word found above */
wolfSSL	0:d92f9d21154c	1906	r = rr;
wolfSSL	0:d92f9d21154c	1907	}
wolfSSL	0:d92f9d21154c	1908	}
wolfSSL	0:d92f9d21154c	1909
wolfSSL	0:d92f9d21154c	1910
wolfSSL	0:d92f9d21154c	1911	void fp_rshd(fp_int *a, int x)
wolfSSL	0:d92f9d21154c	1912	{
wolfSSL	0:d92f9d21154c	1913	int y;
wolfSSL	0:d92f9d21154c	1914
wolfSSL	0:d92f9d21154c	1915	/* too many digits just zero and return */
wolfSSL	0:d92f9d21154c	1916	if (x >= a->used) {
wolfSSL	0:d92f9d21154c	1917	fp_zero(a);
wolfSSL	0:d92f9d21154c	1918	return;
wolfSSL	0:d92f9d21154c	1919	}
wolfSSL	0:d92f9d21154c	1920
wolfSSL	0:d92f9d21154c	1921	/* shift */
wolfSSL	0:d92f9d21154c	1922	for (y = 0; y < a->used - x; y++) {
wolfSSL	0:d92f9d21154c	1923	a->dp[y] = a->dp[y+x];
wolfSSL	0:d92f9d21154c	1924	}
wolfSSL	0:d92f9d21154c	1925
wolfSSL	0:d92f9d21154c	1926	/* zero rest */
wolfSSL	0:d92f9d21154c	1927	for (; y < a->used; y++) {
wolfSSL	0:d92f9d21154c	1928	a->dp[y] = 0;
wolfSSL	0:d92f9d21154c	1929	}
wolfSSL	0:d92f9d21154c	1930
wolfSSL	0:d92f9d21154c	1931	/* decrement count */
wolfSSL	0:d92f9d21154c	1932	a->used -= x;
wolfSSL	0:d92f9d21154c	1933	fp_clamp(a);
wolfSSL	0:d92f9d21154c	1934	}
wolfSSL	0:d92f9d21154c	1935
wolfSSL	0:d92f9d21154c	1936	/* reverse an array, used for radix code */
wolfSSL	0:d92f9d21154c	1937	void fp_reverse (unsigned char *s, int len)
wolfSSL	0:d92f9d21154c	1938	{
wolfSSL	0:d92f9d21154c	1939	int ix, iy;
wolfSSL	0:d92f9d21154c	1940	unsigned char t;
wolfSSL	0:d92f9d21154c	1941
wolfSSL	0:d92f9d21154c	1942	ix = 0;
wolfSSL	0:d92f9d21154c	1943	iy = len - 1;
wolfSSL	0:d92f9d21154c	1944	while (ix < iy) {
wolfSSL	0:d92f9d21154c	1945	t = s[ix];
wolfSSL	0:d92f9d21154c	1946	s[ix] = s[iy];
wolfSSL	0:d92f9d21154c	1947	s[iy] = t;
wolfSSL	0:d92f9d21154c	1948	++ix;
wolfSSL	0:d92f9d21154c	1949	--iy;
wolfSSL	0:d92f9d21154c	1950	}
wolfSSL	0:d92f9d21154c	1951	}
wolfSSL	0:d92f9d21154c	1952
wolfSSL	0:d92f9d21154c	1953
wolfSSL	0:d92f9d21154c	1954	/* c = a - b */
wolfSSL	0:d92f9d21154c	1955	void fp_sub_d(fp_int a, fp_digit b, fp_int c)
wolfSSL	0:d92f9d21154c	1956	{
wolfSSL	0:d92f9d21154c	1957	fp_int tmp;
wolfSSL	0:d92f9d21154c	1958	fp_init(&tmp);
wolfSSL	0:d92f9d21154c	1959	fp_set(&tmp, b);
wolfSSL	0:d92f9d21154c	1960	fp_sub(a, &tmp, c);
wolfSSL	0:d92f9d21154c	1961	}
wolfSSL	0:d92f9d21154c	1962
wolfSSL	0:d92f9d21154c	1963
wolfSSL	0:d92f9d21154c	1964	/* CyaSSL callers from normal lib */
wolfSSL	0:d92f9d21154c	1965
wolfSSL	0:d92f9d21154c	1966	/* init a new mp_int */
wolfSSL	0:d92f9d21154c	1967	int mp_init (mp_int * a)
wolfSSL	0:d92f9d21154c	1968	{
wolfSSL	0:d92f9d21154c	1969	if (a)
wolfSSL	0:d92f9d21154c	1970	fp_init(a);
wolfSSL	0:d92f9d21154c	1971	return MP_OKAY;
wolfSSL	0:d92f9d21154c	1972	}
wolfSSL	0:d92f9d21154c	1973
wolfSSL	0:d92f9d21154c	1974	#ifdef ALT_ECC_SIZE
wolfSSL	0:d92f9d21154c	1975	void fp_init(fp_int *a)
wolfSSL	0:d92f9d21154c	1976	{
wolfSSL	0:d92f9d21154c	1977	a->size = FP_SIZE;
wolfSSL	0:d92f9d21154c	1978	fp_zero(a);
wolfSSL	0:d92f9d21154c	1979	}
wolfSSL	0:d92f9d21154c	1980
wolfSSL	0:d92f9d21154c	1981	void fp_zero(fp_int *a)
wolfSSL	0:d92f9d21154c	1982	{
wolfSSL	0:d92f9d21154c	1983	a->used = 0;
wolfSSL	0:d92f9d21154c	1984	a->sign = FP_ZPOS;
wolfSSL	0:d92f9d21154c	1985	XMEMSET(a->dp, 0, a->size * sizeof(fp_digit));
wolfSSL	0:d92f9d21154c	1986	}
wolfSSL	0:d92f9d21154c	1987	#endif
wolfSSL	0:d92f9d21154c	1988
wolfSSL	0:d92f9d21154c	1989
wolfSSL	0:d92f9d21154c	1990	/* clear one (frees) */
wolfSSL	0:d92f9d21154c	1991	void mp_clear (mp_int * a)
wolfSSL	0:d92f9d21154c	1992	{
wolfSSL	0:d92f9d21154c	1993	fp_zero(a);
wolfSSL	0:d92f9d21154c	1994	}
wolfSSL	0:d92f9d21154c	1995
wolfSSL	0:d92f9d21154c	1996	/* handle up to 6 inits */
wolfSSL	0:d92f9d21154c	1997	int mp_init_multi(mp_int* a, mp_int* b, mp_int* c, mp_int* d, mp_int* e, mp_int* f)
wolfSSL	0:d92f9d21154c	1998	{
wolfSSL	0:d92f9d21154c	1999	if (a)
wolfSSL	0:d92f9d21154c	2000	fp_init(a);
wolfSSL	0:d92f9d21154c	2001	if (b)
wolfSSL	0:d92f9d21154c	2002	fp_init(b);
wolfSSL	0:d92f9d21154c	2003	if (c)
wolfSSL	0:d92f9d21154c	2004	fp_init(c);
wolfSSL	0:d92f9d21154c	2005	if (d)
wolfSSL	0:d92f9d21154c	2006	fp_init(d);
wolfSSL	0:d92f9d21154c	2007	if (e)
wolfSSL	0:d92f9d21154c	2008	fp_init(e);
wolfSSL	0:d92f9d21154c	2009	if (f)
wolfSSL	0:d92f9d21154c	2010	fp_init(f);
wolfSSL	0:d92f9d21154c	2011
wolfSSL	0:d92f9d21154c	2012	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2013	}
wolfSSL	0:d92f9d21154c	2014
wolfSSL	0:d92f9d21154c	2015	/* high level addition (handles signs) */
wolfSSL	0:d92f9d21154c	2016	int mp_add (mp_int * a, mp_int * b, mp_int * c)
wolfSSL	0:d92f9d21154c	2017	{
wolfSSL	0:d92f9d21154c	2018	fp_add(a, b, c);
wolfSSL	0:d92f9d21154c	2019	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2020	}
wolfSSL	0:d92f9d21154c	2021
wolfSSL	0:d92f9d21154c	2022	/* high level subtraction (handles signs) */
wolfSSL	0:d92f9d21154c	2023	int mp_sub (mp_int * a, mp_int * b, mp_int * c)
wolfSSL	0:d92f9d21154c	2024	{
wolfSSL	0:d92f9d21154c	2025	fp_sub(a, b, c);
wolfSSL	0:d92f9d21154c	2026	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2027	}
wolfSSL	0:d92f9d21154c	2028
wolfSSL	0:d92f9d21154c	2029	/* high level multiplication (handles sign) */
wolfSSL	0:d92f9d21154c	2030	int mp_mul (mp_int * a, mp_int * b, mp_int * c)
wolfSSL	0:d92f9d21154c	2031	{
wolfSSL	0:d92f9d21154c	2032	fp_mul(a, b, c);
wolfSSL	0:d92f9d21154c	2033	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2034	}
wolfSSL	0:d92f9d21154c	2035
wolfSSL	0:d92f9d21154c	2036	/* d = a * b (mod c) */
wolfSSL	0:d92f9d21154c	2037	int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
wolfSSL	0:d92f9d21154c	2038	{
wolfSSL	0:d92f9d21154c	2039	return fp_mulmod(a, b, c, d);
wolfSSL	0:d92f9d21154c	2040	}
wolfSSL	0:d92f9d21154c	2041
wolfSSL	0:d92f9d21154c	2042	/* c = a mod b, 0 <= c < b */
wolfSSL	0:d92f9d21154c	2043	int mp_mod (mp_int * a, mp_int * b, mp_int * c)
wolfSSL	0:d92f9d21154c	2044	{
wolfSSL	0:d92f9d21154c	2045	return fp_mod (a, b, c);
wolfSSL	0:d92f9d21154c	2046	}
wolfSSL	0:d92f9d21154c	2047
wolfSSL	0:d92f9d21154c	2048	/* hac 14.61, pp608 */
wolfSSL	0:d92f9d21154c	2049	int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
wolfSSL	0:d92f9d21154c	2050	{
wolfSSL	0:d92f9d21154c	2051	return fp_invmod(a, b, c);
wolfSSL	0:d92f9d21154c	2052	}
wolfSSL	0:d92f9d21154c	2053
wolfSSL	0:d92f9d21154c	2054	/* this is a shell function that calls either the normal or Montgomery
wolfSSL	0:d92f9d21154c	2055	* exptmod functions. Originally the call to the montgomery code was
wolfSSL	0:d92f9d21154c	2056	* embedded in the normal function but that wasted alot of stack space
wolfSSL	0:d92f9d21154c	2057	* for nothing (since 99% of the time the Montgomery code would be called)
wolfSSL	0:d92f9d21154c	2058	*/
wolfSSL	0:d92f9d21154c	2059	int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
wolfSSL	0:d92f9d21154c	2060	{
wolfSSL	0:d92f9d21154c	2061	return fp_exptmod(G, X, P, Y);
wolfSSL	0:d92f9d21154c	2062	}
wolfSSL	0:d92f9d21154c	2063
wolfSSL	0:d92f9d21154c	2064	/* compare two ints (signed)*/
wolfSSL	0:d92f9d21154c	2065	int mp_cmp (mp_int * a, mp_int * b)
wolfSSL	0:d92f9d21154c	2066	{
wolfSSL	0:d92f9d21154c	2067	return fp_cmp(a, b);
wolfSSL	0:d92f9d21154c	2068	}
wolfSSL	0:d92f9d21154c	2069
wolfSSL	0:d92f9d21154c	2070	/* compare a digit */
wolfSSL	0:d92f9d21154c	2071	int mp_cmp_d(mp_int * a, mp_digit b)
wolfSSL	0:d92f9d21154c	2072	{
wolfSSL	0:d92f9d21154c	2073	return fp_cmp_d(a, b);
wolfSSL	0:d92f9d21154c	2074	}
wolfSSL	0:d92f9d21154c	2075
wolfSSL	0:d92f9d21154c	2076	/* get the size for an unsigned equivalent */
wolfSSL	0:d92f9d21154c	2077	int mp_unsigned_bin_size (mp_int * a)
wolfSSL	0:d92f9d21154c	2078	{
wolfSSL	0:d92f9d21154c	2079	return fp_unsigned_bin_size(a);
wolfSSL	0:d92f9d21154c	2080	}
wolfSSL	0:d92f9d21154c	2081
wolfSSL	0:d92f9d21154c	2082	/* store in unsigned [big endian] format */
wolfSSL	0:d92f9d21154c	2083	int mp_to_unsigned_bin (mp_int * a, unsigned char *b)
wolfSSL	0:d92f9d21154c	2084	{
wolfSSL	0:d92f9d21154c	2085	fp_to_unsigned_bin(a,b);
wolfSSL	0:d92f9d21154c	2086	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2087	}
wolfSSL	0:d92f9d21154c	2088
wolfSSL	0:d92f9d21154c	2089	/* reads a unsigned char array, assumes the msb is stored first [big endian] */
wolfSSL	0:d92f9d21154c	2090	int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
wolfSSL	0:d92f9d21154c	2091	{
wolfSSL	0:d92f9d21154c	2092	fp_read_unsigned_bin(a, (unsigned char *)b, c);
wolfSSL	0:d92f9d21154c	2093	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2094	}
wolfSSL	0:d92f9d21154c	2095
wolfSSL	0:d92f9d21154c	2096
wolfSSL	0:d92f9d21154c	2097	int mp_sub_d(fp_int a, fp_digit b, fp_int c)
wolfSSL	0:d92f9d21154c	2098	{
wolfSSL	0:d92f9d21154c	2099	fp_sub_d(a, b, c);
wolfSSL	0:d92f9d21154c	2100	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2101	}
wolfSSL	0:d92f9d21154c	2102
wolfSSL	0:d92f9d21154c	2103
wolfSSL	0:d92f9d21154c	2104	#ifdef ALT_ECC_SIZE
wolfSSL	0:d92f9d21154c	2105	void fp_copy(fp_int a, fp_int b)
wolfSSL	0:d92f9d21154c	2106	{
wolfSSL	0:d92f9d21154c	2107	if (a != b) {
wolfSSL	0:d92f9d21154c	2108	b->used = a->used;
wolfSSL	0:d92f9d21154c	2109	b->sign = a->sign;
wolfSSL	0:d92f9d21154c	2110	XMEMCPY(b->dp, a->dp, a->used * sizeof(fp_digit));
wolfSSL	0:d92f9d21154c	2111	}
wolfSSL	0:d92f9d21154c	2112	}
wolfSSL	0:d92f9d21154c	2113
wolfSSL	0:d92f9d21154c	2114	void fp_init_copy(fp_int a, fp_int b)
wolfSSL	0:d92f9d21154c	2115	{
wolfSSL	0:d92f9d21154c	2116	if (a != b) {
wolfSSL	0:d92f9d21154c	2117	fp_init(a);
wolfSSL	0:d92f9d21154c	2118	fp_copy(b, a);
wolfSSL	0:d92f9d21154c	2119	}
wolfSSL	0:d92f9d21154c	2120	}
wolfSSL	0:d92f9d21154c	2121	#endif
wolfSSL	0:d92f9d21154c	2122
wolfSSL	0:d92f9d21154c	2123	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2124	int mp_copy(fp_int* a, fp_int* b)
wolfSSL	0:d92f9d21154c	2125	{
wolfSSL	0:d92f9d21154c	2126	fp_copy(a, b);
wolfSSL	0:d92f9d21154c	2127	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2128	}
wolfSSL	0:d92f9d21154c	2129
wolfSSL	0:d92f9d21154c	2130
wolfSSL	0:d92f9d21154c	2131	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2132	int mp_isodd(mp_int* a)
wolfSSL	0:d92f9d21154c	2133	{
wolfSSL	0:d92f9d21154c	2134	return fp_isodd(a);
wolfSSL	0:d92f9d21154c	2135	}
wolfSSL	0:d92f9d21154c	2136
wolfSSL	0:d92f9d21154c	2137
wolfSSL	0:d92f9d21154c	2138	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2139	int mp_iszero(mp_int* a)
wolfSSL	0:d92f9d21154c	2140	{
wolfSSL	0:d92f9d21154c	2141	return fp_iszero(a);
wolfSSL	0:d92f9d21154c	2142	}
wolfSSL	0:d92f9d21154c	2143
wolfSSL	0:d92f9d21154c	2144
wolfSSL	0:d92f9d21154c	2145	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2146	int mp_count_bits (mp_int* a)
wolfSSL	0:d92f9d21154c	2147	{
wolfSSL	0:d92f9d21154c	2148	return fp_count_bits(a);
wolfSSL	0:d92f9d21154c	2149	}
wolfSSL	0:d92f9d21154c	2150
wolfSSL	0:d92f9d21154c	2151
wolfSSL	0:d92f9d21154c	2152	int mp_leading_bit (mp_int* a)
wolfSSL	0:d92f9d21154c	2153	{
wolfSSL	0:d92f9d21154c	2154	return fp_leading_bit(a);
wolfSSL	0:d92f9d21154c	2155	}
wolfSSL	0:d92f9d21154c	2156
wolfSSL	0:d92f9d21154c	2157
wolfSSL	0:d92f9d21154c	2158	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2159	void mp_rshb (mp_int* a, int x)
wolfSSL	0:d92f9d21154c	2160	{
wolfSSL	0:d92f9d21154c	2161	fp_rshb(a, x);
wolfSSL	0:d92f9d21154c	2162	}
wolfSSL	0:d92f9d21154c	2163
wolfSSL	0:d92f9d21154c	2164
wolfSSL	0:d92f9d21154c	2165	/* fast math wrappers */
wolfSSL	0:d92f9d21154c	2166	int mp_set_int(fp_int *a, fp_digit b)
wolfSSL	0:d92f9d21154c	2167	{
wolfSSL	0:d92f9d21154c	2168	fp_set(a, b);
wolfSSL	0:d92f9d21154c	2169	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2170	}
wolfSSL	0:d92f9d21154c	2171
wolfSSL	0:d92f9d21154c	2172
wolfSSL	0:d92f9d21154c	2173	#if defined(WOLFSSL_KEY_GEN) \|\| defined (HAVE_ECC)
wolfSSL	0:d92f9d21154c	2174
wolfSSL	0:d92f9d21154c	2175	/* c = a * a (mod b) */
wolfSSL	0:d92f9d21154c	2176	int fp_sqrmod(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	2177	{
wolfSSL	0:d92f9d21154c	2178	fp_int tmp;
wolfSSL	0:d92f9d21154c	2179	fp_init(&tmp);
wolfSSL	0:d92f9d21154c	2180	fp_sqr(a, &tmp);
wolfSSL	0:d92f9d21154c	2181	return fp_mod(&tmp, b, c);
wolfSSL	0:d92f9d21154c	2182	}
wolfSSL	0:d92f9d21154c	2183
wolfSSL	0:d92f9d21154c	2184	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2185	int mp_sqrmod(mp_int a, mp_int b, mp_int *c)
wolfSSL	0:d92f9d21154c	2186	{
wolfSSL	0:d92f9d21154c	2187	return fp_sqrmod(a, b, c);
wolfSSL	0:d92f9d21154c	2188	}
wolfSSL	0:d92f9d21154c	2189
wolfSSL	0:d92f9d21154c	2190	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2191	int mp_montgomery_calc_normalization(mp_int a, mp_int b)
wolfSSL	0:d92f9d21154c	2192	{
wolfSSL	0:d92f9d21154c	2193	fp_montgomery_calc_normalization(a, b);
wolfSSL	0:d92f9d21154c	2194	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2195	}
wolfSSL	0:d92f9d21154c	2196
wolfSSL	0:d92f9d21154c	2197	#endif /* WOLFSSL_KEYGEN \|\| HAVE_ECC */
wolfSSL	0:d92f9d21154c	2198
wolfSSL	0:d92f9d21154c	2199
wolfSSL	0:d92f9d21154c	2200	#if defined(WOLFSSL_KEY_GEN) \|\| defined(HAVE_COMP_KEY)
wolfSSL	0:d92f9d21154c	2201
wolfSSL	0:d92f9d21154c	2202	static const int lnz[16] = {
wolfSSL	0:d92f9d21154c	2203	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
wolfSSL	0:d92f9d21154c	2204	};
wolfSSL	0:d92f9d21154c	2205
wolfSSL	0:d92f9d21154c	2206	/* Counts the number of lsbs which are zero before the first zero bit */
wolfSSL	0:d92f9d21154c	2207	int fp_cnt_lsb(fp_int *a)
wolfSSL	0:d92f9d21154c	2208	{
wolfSSL	0:d92f9d21154c	2209	int x;
wolfSSL	0:d92f9d21154c	2210	fp_digit q, qq;
wolfSSL	0:d92f9d21154c	2211
wolfSSL	0:d92f9d21154c	2212	/* easy out */
wolfSSL	0:d92f9d21154c	2213	if (fp_iszero(a) == 1) {
wolfSSL	0:d92f9d21154c	2214	return 0;
wolfSSL	0:d92f9d21154c	2215	}
wolfSSL	0:d92f9d21154c	2216
wolfSSL	0:d92f9d21154c	2217	/* scan lower digits until non-zero */
wolfSSL	0:d92f9d21154c	2218	for (x = 0; x < a->used && a->dp[x] == 0; x++);
wolfSSL	0:d92f9d21154c	2219	q = a->dp[x];
wolfSSL	0:d92f9d21154c	2220	x *= DIGIT_BIT;
wolfSSL	0:d92f9d21154c	2221
wolfSSL	0:d92f9d21154c	2222	/* now scan this digit until a 1 is found */
wolfSSL	0:d92f9d21154c	2223	if ((q & 1) == 0) {
wolfSSL	0:d92f9d21154c	2224	do {
wolfSSL	0:d92f9d21154c	2225	qq = q & 15;
wolfSSL	0:d92f9d21154c	2226	x += lnz[qq];
wolfSSL	0:d92f9d21154c	2227	q >>= 4;
wolfSSL	0:d92f9d21154c	2228	} while (qq == 0);
wolfSSL	0:d92f9d21154c	2229	}
wolfSSL	0:d92f9d21154c	2230	return x;
wolfSSL	0:d92f9d21154c	2231	}
wolfSSL	0:d92f9d21154c	2232
wolfSSL	0:d92f9d21154c	2233
wolfSSL	0:d92f9d21154c	2234
wolfSSL	0:d92f9d21154c	2235
wolfSSL	0:d92f9d21154c	2236	static int s_is_power_of_two(fp_digit b, int *p)
wolfSSL	0:d92f9d21154c	2237	{
wolfSSL	0:d92f9d21154c	2238	int x;
wolfSSL	0:d92f9d21154c	2239
wolfSSL	0:d92f9d21154c	2240	/* fast return if no power of two */
wolfSSL	0:d92f9d21154c	2241	if ((b==0) \|\| (b & (b-1))) {
wolfSSL	0:d92f9d21154c	2242	return 0;
wolfSSL	0:d92f9d21154c	2243	}
wolfSSL	0:d92f9d21154c	2244
wolfSSL	0:d92f9d21154c	2245	for (x = 0; x < DIGIT_BIT; x++) {
wolfSSL	0:d92f9d21154c	2246	if (b == (((fp_digit)1)<<x)) {
wolfSSL	0:d92f9d21154c	2247	*p = x;
wolfSSL	0:d92f9d21154c	2248	return 1;
wolfSSL	0:d92f9d21154c	2249	}
wolfSSL	0:d92f9d21154c	2250	}
wolfSSL	0:d92f9d21154c	2251	return 0;
wolfSSL	0:d92f9d21154c	2252	}
wolfSSL	0:d92f9d21154c	2253
wolfSSL	0:d92f9d21154c	2254	/* a/b => cb + d == a */
wolfSSL	0:d92f9d21154c	2255	static int fp_div_d(fp_int a, fp_digit b, fp_int c, fp_digit *d)
wolfSSL	0:d92f9d21154c	2256	{
wolfSSL	0:d92f9d21154c	2257	fp_int q;
wolfSSL	0:d92f9d21154c	2258	fp_word w;
wolfSSL	0:d92f9d21154c	2259	fp_digit t;
wolfSSL	0:d92f9d21154c	2260	int ix;
wolfSSL	0:d92f9d21154c	2261
wolfSSL	0:d92f9d21154c	2262	/* cannot divide by zero */
wolfSSL	0:d92f9d21154c	2263	if (b == 0) {
wolfSSL	0:d92f9d21154c	2264	return FP_VAL;
wolfSSL	0:d92f9d21154c	2265	}
wolfSSL	0:d92f9d21154c	2266
wolfSSL	0:d92f9d21154c	2267	/* quick outs */
wolfSSL	0:d92f9d21154c	2268	if (b == 1 \|\| fp_iszero(a) == 1) {
wolfSSL	0:d92f9d21154c	2269	if (d != NULL) {
wolfSSL	0:d92f9d21154c	2270	*d = 0;
wolfSSL	0:d92f9d21154c	2271	}
wolfSSL	0:d92f9d21154c	2272	if (c != NULL) {
wolfSSL	0:d92f9d21154c	2273	fp_copy(a, c);
wolfSSL	0:d92f9d21154c	2274	}
wolfSSL	0:d92f9d21154c	2275	return FP_OKAY;
wolfSSL	0:d92f9d21154c	2276	}
wolfSSL	0:d92f9d21154c	2277
wolfSSL	0:d92f9d21154c	2278	/* power of two ? */
wolfSSL	0:d92f9d21154c	2279	if (s_is_power_of_two(b, &ix) == 1) {
wolfSSL	0:d92f9d21154c	2280	if (d != NULL) {
wolfSSL	0:d92f9d21154c	2281	*d = a->dp[0] & ((((fp_digit)1)<<ix) - 1);
wolfSSL	0:d92f9d21154c	2282	}
wolfSSL	0:d92f9d21154c	2283	if (c != NULL) {
wolfSSL	0:d92f9d21154c	2284	fp_div_2d(a, ix, c, NULL);
wolfSSL	0:d92f9d21154c	2285	}
wolfSSL	0:d92f9d21154c	2286	return FP_OKAY;
wolfSSL	0:d92f9d21154c	2287	}
wolfSSL	0:d92f9d21154c	2288
wolfSSL	0:d92f9d21154c	2289	/* no easy answer [c'est la vie]. Just division */
wolfSSL	0:d92f9d21154c	2290	fp_init(&q);
wolfSSL	0:d92f9d21154c	2291
wolfSSL	0:d92f9d21154c	2292	q.used = a->used;
wolfSSL	0:d92f9d21154c	2293	q.sign = a->sign;
wolfSSL	0:d92f9d21154c	2294	w = 0;
wolfSSL	0:d92f9d21154c	2295	for (ix = a->used - 1; ix >= 0; ix--) {
wolfSSL	0:d92f9d21154c	2296	w = (w << ((fp_word)DIGIT_BIT)) \| ((fp_word)a->dp[ix]);
wolfSSL	0:d92f9d21154c	2297
wolfSSL	0:d92f9d21154c	2298	if (w >= b) {
wolfSSL	0:d92f9d21154c	2299	t = (fp_digit)(w / b);
wolfSSL	0:d92f9d21154c	2300	w -= ((fp_word)t) * ((fp_word)b);
wolfSSL	0:d92f9d21154c	2301	} else {
wolfSSL	0:d92f9d21154c	2302	t = 0;
wolfSSL	0:d92f9d21154c	2303	}
wolfSSL	0:d92f9d21154c	2304	q.dp[ix] = (fp_digit)t;
wolfSSL	0:d92f9d21154c	2305	}
wolfSSL	0:d92f9d21154c	2306
wolfSSL	0:d92f9d21154c	2307	if (d != NULL) {
wolfSSL	0:d92f9d21154c	2308	*d = (fp_digit)w;
wolfSSL	0:d92f9d21154c	2309	}
wolfSSL	0:d92f9d21154c	2310
wolfSSL	0:d92f9d21154c	2311	if (c != NULL) {
wolfSSL	0:d92f9d21154c	2312	fp_clamp(&q);
wolfSSL	0:d92f9d21154c	2313	fp_copy(&q, c);
wolfSSL	0:d92f9d21154c	2314	}
wolfSSL	0:d92f9d21154c	2315
wolfSSL	0:d92f9d21154c	2316	return FP_OKAY;
wolfSSL	0:d92f9d21154c	2317	}
wolfSSL	0:d92f9d21154c	2318
wolfSSL	0:d92f9d21154c	2319
wolfSSL	0:d92f9d21154c	2320	/* c = a mod b, 0 <= c < b */
wolfSSL	0:d92f9d21154c	2321	static int fp_mod_d(fp_int a, fp_digit b, fp_digit c)
wolfSSL	0:d92f9d21154c	2322	{
wolfSSL	0:d92f9d21154c	2323	return fp_div_d(a, b, NULL, c);
wolfSSL	0:d92f9d21154c	2324	}
wolfSSL	0:d92f9d21154c	2325
wolfSSL	0:d92f9d21154c	2326	int mp_mod_d(fp_int a, fp_digit b, fp_digit c)
wolfSSL	0:d92f9d21154c	2327	{
wolfSSL	0:d92f9d21154c	2328	return fp_mod_d(a, b, c);
wolfSSL	0:d92f9d21154c	2329	}
wolfSSL	0:d92f9d21154c	2330
wolfSSL	0:d92f9d21154c	2331	#endif /* defined(WOLFSSL_KEY_GEN) \|\| defined(HAVE_COMP_KEY) */
wolfSSL	0:d92f9d21154c	2332
wolfSSL	0:d92f9d21154c	2333	#ifdef WOLFSSL_KEY_GEN
wolfSSL	0:d92f9d21154c	2334
wolfSSL	0:d92f9d21154c	2335	void fp_gcd(fp_int a, fp_int b, fp_int *c);
wolfSSL	0:d92f9d21154c	2336	void fp_lcm(fp_int a, fp_int b, fp_int *c);
wolfSSL	0:d92f9d21154c	2337	int fp_isprime(fp_int *a);
wolfSSL	0:d92f9d21154c	2338
wolfSSL	0:d92f9d21154c	2339	int mp_gcd(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	2340	{
wolfSSL	0:d92f9d21154c	2341	fp_gcd(a, b, c);
wolfSSL	0:d92f9d21154c	2342	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2343	}
wolfSSL	0:d92f9d21154c	2344
wolfSSL	0:d92f9d21154c	2345
wolfSSL	0:d92f9d21154c	2346	int mp_lcm(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	2347	{
wolfSSL	0:d92f9d21154c	2348	fp_lcm(a, b, c);
wolfSSL	0:d92f9d21154c	2349	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2350	}
wolfSSL	0:d92f9d21154c	2351
wolfSSL	0:d92f9d21154c	2352
wolfSSL	0:d92f9d21154c	2353	int mp_prime_is_prime(mp_int* a, int t, int* result)
wolfSSL	0:d92f9d21154c	2354	{
wolfSSL	0:d92f9d21154c	2355	(void)t;
wolfSSL	0:d92f9d21154c	2356	*result = fp_isprime(a);
wolfSSL	0:d92f9d21154c	2357	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2358	}
wolfSSL	0:d92f9d21154c	2359
wolfSSL	0:d92f9d21154c	2360	/* Miller-Rabin test of "a" to the base of "b" as described in
wolfSSL	0:d92f9d21154c	2361	* HAC pp. 139 Algorithm 4.24
wolfSSL	0:d92f9d21154c	2362	*
wolfSSL	0:d92f9d21154c	2363	* Sets result to 0 if definitely composite or 1 if probably prime.
wolfSSL	0:d92f9d21154c	2364	* Randomly the chance of error is no more than 1/4 and often
wolfSSL	0:d92f9d21154c	2365	* very much lower.
wolfSSL	0:d92f9d21154c	2366	*/
wolfSSL	0:d92f9d21154c	2367	static void fp_prime_miller_rabin (fp_int * a, fp_int * b, int *result)
wolfSSL	0:d92f9d21154c	2368	{
wolfSSL	0:d92f9d21154c	2369	fp_int n1, y, r;
wolfSSL	0:d92f9d21154c	2370	int s, j;
wolfSSL	0:d92f9d21154c	2371
wolfSSL	0:d92f9d21154c	2372	/* default */
wolfSSL	0:d92f9d21154c	2373	*result = FP_NO;
wolfSSL	0:d92f9d21154c	2374
wolfSSL	0:d92f9d21154c	2375	/* ensure b > 1 */
wolfSSL	0:d92f9d21154c	2376	if (fp_cmp_d(b, 1) != FP_GT) {
wolfSSL	0:d92f9d21154c	2377	return;
wolfSSL	0:d92f9d21154c	2378	}
wolfSSL	0:d92f9d21154c	2379
wolfSSL	0:d92f9d21154c	2380	/* get n1 = a - 1 */
wolfSSL	0:d92f9d21154c	2381	fp_init_copy(&n1, a);
wolfSSL	0:d92f9d21154c	2382	fp_sub_d(&n1, 1, &n1);
wolfSSL	0:d92f9d21154c	2383
wolfSSL	0:d92f9d21154c	2384	/* set 2*s r = n1 */
wolfSSL	0:d92f9d21154c	2385	fp_init_copy(&r, &n1);
wolfSSL	0:d92f9d21154c	2386
wolfSSL	0:d92f9d21154c	2387	/* count the number of least significant bits
wolfSSL	0:d92f9d21154c	2388	* which are zero
wolfSSL	0:d92f9d21154c	2389	*/
wolfSSL	0:d92f9d21154c	2390	s = fp_cnt_lsb(&r);
wolfSSL	0:d92f9d21154c	2391
wolfSSL	0:d92f9d21154c	2392	/* now divide n - 1 by 2*s /
wolfSSL	0:d92f9d21154c	2393	fp_div_2d (&r, s, &r, NULL);
wolfSSL	0:d92f9d21154c	2394
wolfSSL	0:d92f9d21154c	2395	/* compute y = b*r mod a /
wolfSSL	0:d92f9d21154c	2396	fp_init(&y);
wolfSSL	0:d92f9d21154c	2397	fp_exptmod(b, &r, a, &y);
wolfSSL	0:d92f9d21154c	2398
wolfSSL	0:d92f9d21154c	2399	/* if y != 1 and y != n1 do */
wolfSSL	0:d92f9d21154c	2400	if (fp_cmp_d (&y, 1) != FP_EQ && fp_cmp (&y, &n1) != FP_EQ) {
wolfSSL	0:d92f9d21154c	2401	j = 1;
wolfSSL	0:d92f9d21154c	2402	/* while j <= s-1 and y != n1 */
wolfSSL	0:d92f9d21154c	2403	while ((j <= (s - 1)) && fp_cmp (&y, &n1) != FP_EQ) {
wolfSSL	0:d92f9d21154c	2404	fp_sqrmod (&y, a, &y);
wolfSSL	0:d92f9d21154c	2405
wolfSSL	0:d92f9d21154c	2406	/* if y == 1 then composite */
wolfSSL	0:d92f9d21154c	2407	if (fp_cmp_d (&y, 1) == FP_EQ) {
wolfSSL	0:d92f9d21154c	2408	return;
wolfSSL	0:d92f9d21154c	2409	}
wolfSSL	0:d92f9d21154c	2410	++j;
wolfSSL	0:d92f9d21154c	2411	}
wolfSSL	0:d92f9d21154c	2412
wolfSSL	0:d92f9d21154c	2413	/* if y != n1 then composite */
wolfSSL	0:d92f9d21154c	2414	if (fp_cmp (&y, &n1) != FP_EQ) {
wolfSSL	0:d92f9d21154c	2415	return;
wolfSSL	0:d92f9d21154c	2416	}
wolfSSL	0:d92f9d21154c	2417	}
wolfSSL	0:d92f9d21154c	2418
wolfSSL	0:d92f9d21154c	2419	/* probably prime now */
wolfSSL	0:d92f9d21154c	2420	*result = FP_YES;
wolfSSL	0:d92f9d21154c	2421	}
wolfSSL	0:d92f9d21154c	2422
wolfSSL	0:d92f9d21154c	2423
wolfSSL	0:d92f9d21154c	2424	/* a few primes */
wolfSSL	0:d92f9d21154c	2425	static const fp_digit primes[256] = {
wolfSSL	0:d92f9d21154c	2426	0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
wolfSSL	0:d92f9d21154c	2427	0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
wolfSSL	0:d92f9d21154c	2428	0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
wolfSSL	0:d92f9d21154c	2429	0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 0x0083,
wolfSSL	0:d92f9d21154c	2430	0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
wolfSSL	0:d92f9d21154c	2431	0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
wolfSSL	0:d92f9d21154c	2432	0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
wolfSSL	0:d92f9d21154c	2433	0x010D, 0x010F, 0x0115, 0x0119, 0x011B, 0x0125, 0x0133, 0x0137,
wolfSSL	0:d92f9d21154c	2434
wolfSSL	0:d92f9d21154c	2435	0x0139, 0x013D, 0x014B, 0x0151, 0x015B, 0x015D, 0x0161, 0x0167,
wolfSSL	0:d92f9d21154c	2436	0x016F, 0x0175, 0x017B, 0x017F, 0x0185, 0x018D, 0x0191, 0x0199,
wolfSSL	0:d92f9d21154c	2437	0x01A3, 0x01A5, 0x01AF, 0x01B1, 0x01B7, 0x01BB, 0x01C1, 0x01C9,
wolfSSL	0:d92f9d21154c	2438	0x01CD, 0x01CF, 0x01D3, 0x01DF, 0x01E7, 0x01EB, 0x01F3, 0x01F7,
wolfSSL	0:d92f9d21154c	2439	0x01FD, 0x0209, 0x020B, 0x021D, 0x0223, 0x022D, 0x0233, 0x0239,
wolfSSL	0:d92f9d21154c	2440	0x023B, 0x0241, 0x024B, 0x0251, 0x0257, 0x0259, 0x025F, 0x0265,
wolfSSL	0:d92f9d21154c	2441	0x0269, 0x026B, 0x0277, 0x0281, 0x0283, 0x0287, 0x028D, 0x0293,
wolfSSL	0:d92f9d21154c	2442	0x0295, 0x02A1, 0x02A5, 0x02AB, 0x02B3, 0x02BD, 0x02C5, 0x02CF,
wolfSSL	0:d92f9d21154c	2443
wolfSSL	0:d92f9d21154c	2444	0x02D7, 0x02DD, 0x02E3, 0x02E7, 0x02EF, 0x02F5, 0x02F9, 0x0301,
wolfSSL	0:d92f9d21154c	2445	0x0305, 0x0313, 0x031D, 0x0329, 0x032B, 0x0335, 0x0337, 0x033B,
wolfSSL	0:d92f9d21154c	2446	0x033D, 0x0347, 0x0355, 0x0359, 0x035B, 0x035F, 0x036D, 0x0371,
wolfSSL	0:d92f9d21154c	2447	0x0373, 0x0377, 0x038B, 0x038F, 0x0397, 0x03A1, 0x03A9, 0x03AD,
wolfSSL	0:d92f9d21154c	2448	0x03B3, 0x03B9, 0x03C7, 0x03CB, 0x03D1, 0x03D7, 0x03DF, 0x03E5,
wolfSSL	0:d92f9d21154c	2449	0x03F1, 0x03F5, 0x03FB, 0x03FD, 0x0407, 0x0409, 0x040F, 0x0419,
wolfSSL	0:d92f9d21154c	2450	0x041B, 0x0425, 0x0427, 0x042D, 0x043F, 0x0443, 0x0445, 0x0449,
wolfSSL	0:d92f9d21154c	2451	0x044F, 0x0455, 0x045D, 0x0463, 0x0469, 0x047F, 0x0481, 0x048B,
wolfSSL	0:d92f9d21154c	2452
wolfSSL	0:d92f9d21154c	2453	0x0493, 0x049D, 0x04A3, 0x04A9, 0x04B1, 0x04BD, 0x04C1, 0x04C7,
wolfSSL	0:d92f9d21154c	2454	0x04CD, 0x04CF, 0x04D5, 0x04E1, 0x04EB, 0x04FD, 0x04FF, 0x0503,
wolfSSL	0:d92f9d21154c	2455	0x0509, 0x050B, 0x0511, 0x0515, 0x0517, 0x051B, 0x0527, 0x0529,
wolfSSL	0:d92f9d21154c	2456	0x052F, 0x0551, 0x0557, 0x055D, 0x0565, 0x0577, 0x0581, 0x058F,
wolfSSL	0:d92f9d21154c	2457	0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
wolfSSL	0:d92f9d21154c	2458	0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
wolfSSL	0:d92f9d21154c	2459	0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
wolfSSL	0:d92f9d21154c	2460	0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
wolfSSL	0:d92f9d21154c	2461	};
wolfSSL	0:d92f9d21154c	2462
wolfSSL	0:d92f9d21154c	2463	int fp_isprime(fp_int *a)
wolfSSL	0:d92f9d21154c	2464	{
wolfSSL	0:d92f9d21154c	2465	fp_int b;
wolfSSL	0:d92f9d21154c	2466	fp_digit d = 0;
wolfSSL	0:d92f9d21154c	2467	int r, res;
wolfSSL	0:d92f9d21154c	2468
wolfSSL	0:d92f9d21154c	2469	/* do trial division */
wolfSSL	0:d92f9d21154c	2470	for (r = 0; r < 256; r++) {
wolfSSL	0:d92f9d21154c	2471	fp_mod_d(a, primes[r], &d);
wolfSSL	0:d92f9d21154c	2472	if (d == 0) {
wolfSSL	0:d92f9d21154c	2473	return FP_NO;
wolfSSL	0:d92f9d21154c	2474	}
wolfSSL	0:d92f9d21154c	2475	}
wolfSSL	0:d92f9d21154c	2476
wolfSSL	0:d92f9d21154c	2477	/* now do 8 miller rabins */
wolfSSL	0:d92f9d21154c	2478	fp_init(&b);
wolfSSL	0:d92f9d21154c	2479	for (r = 0; r < 8; r++) {
wolfSSL	0:d92f9d21154c	2480	fp_set(&b, primes[r]);
wolfSSL	0:d92f9d21154c	2481	fp_prime_miller_rabin(a, &b, &res);
wolfSSL	0:d92f9d21154c	2482	if (res == FP_NO) {
wolfSSL	0:d92f9d21154c	2483	return FP_NO;
wolfSSL	0:d92f9d21154c	2484	}
wolfSSL	0:d92f9d21154c	2485	}
wolfSSL	0:d92f9d21154c	2486	return FP_YES;
wolfSSL	0:d92f9d21154c	2487	}
wolfSSL	0:d92f9d21154c	2488
wolfSSL	0:d92f9d21154c	2489
wolfSSL	0:d92f9d21154c	2490	/* c = [a, b] */
wolfSSL	0:d92f9d21154c	2491	void fp_lcm(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	2492	{
wolfSSL	0:d92f9d21154c	2493	fp_int t1, t2;
wolfSSL	0:d92f9d21154c	2494
wolfSSL	0:d92f9d21154c	2495	fp_init(&t1);
wolfSSL	0:d92f9d21154c	2496	fp_init(&t2);
wolfSSL	0:d92f9d21154c	2497	fp_gcd(a, b, &t1);
wolfSSL	0:d92f9d21154c	2498	if (fp_cmp_mag(a, b) == FP_GT) {
wolfSSL	0:d92f9d21154c	2499	fp_div(a, &t1, &t2, NULL);
wolfSSL	0:d92f9d21154c	2500	fp_mul(b, &t2, c);
wolfSSL	0:d92f9d21154c	2501	} else {
wolfSSL	0:d92f9d21154c	2502	fp_div(b, &t1, &t2, NULL);
wolfSSL	0:d92f9d21154c	2503	fp_mul(a, &t2, c);
wolfSSL	0:d92f9d21154c	2504	}
wolfSSL	0:d92f9d21154c	2505	}
wolfSSL	0:d92f9d21154c	2506
wolfSSL	0:d92f9d21154c	2507
wolfSSL	0:d92f9d21154c	2508
wolfSSL	0:d92f9d21154c	2509	/* c = (a, b) */
wolfSSL	0:d92f9d21154c	2510	void fp_gcd(fp_int a, fp_int b, fp_int *c)
wolfSSL	0:d92f9d21154c	2511	{
wolfSSL	0:d92f9d21154c	2512	fp_int u, v, r;
wolfSSL	0:d92f9d21154c	2513
wolfSSL	0:d92f9d21154c	2514	/* either zero than gcd is the largest */
wolfSSL	0:d92f9d21154c	2515	if (fp_iszero (a) == 1 && fp_iszero (b) == 0) {
wolfSSL	0:d92f9d21154c	2516	fp_abs (b, c);
wolfSSL	0:d92f9d21154c	2517	return;
wolfSSL	0:d92f9d21154c	2518	}
wolfSSL	0:d92f9d21154c	2519	if (fp_iszero (a) == 0 && fp_iszero (b) == 1) {
wolfSSL	0:d92f9d21154c	2520	fp_abs (a, c);
wolfSSL	0:d92f9d21154c	2521	return;
wolfSSL	0:d92f9d21154c	2522	}
wolfSSL	0:d92f9d21154c	2523
wolfSSL	0:d92f9d21154c	2524	/* optimized. At this point if a == 0 then
wolfSSL	0:d92f9d21154c	2525	* b must equal zero too
wolfSSL	0:d92f9d21154c	2526	*/
wolfSSL	0:d92f9d21154c	2527	if (fp_iszero (a) == 1) {
wolfSSL	0:d92f9d21154c	2528	fp_zero(c);
wolfSSL	0:d92f9d21154c	2529	return;
wolfSSL	0:d92f9d21154c	2530	}
wolfSSL	0:d92f9d21154c	2531
wolfSSL	0:d92f9d21154c	2532	/* sort inputs */
wolfSSL	0:d92f9d21154c	2533	if (fp_cmp_mag(a, b) != FP_LT) {
wolfSSL	0:d92f9d21154c	2534	fp_init_copy(&u, a);
wolfSSL	0:d92f9d21154c	2535	fp_init_copy(&v, b);
wolfSSL	0:d92f9d21154c	2536	} else {
wolfSSL	0:d92f9d21154c	2537	fp_init_copy(&u, b);
wolfSSL	0:d92f9d21154c	2538	fp_init_copy(&v, a);
wolfSSL	0:d92f9d21154c	2539	}
wolfSSL	0:d92f9d21154c	2540
wolfSSL	0:d92f9d21154c	2541	fp_init(&r);
wolfSSL	0:d92f9d21154c	2542	while (fp_iszero(&v) == FP_NO) {
wolfSSL	0:d92f9d21154c	2543	fp_mod(&u, &v, &r);
wolfSSL	0:d92f9d21154c	2544	fp_copy(&v, &u);
wolfSSL	0:d92f9d21154c	2545	fp_copy(&r, &v);
wolfSSL	0:d92f9d21154c	2546	}
wolfSSL	0:d92f9d21154c	2547	fp_copy(&u, c);
wolfSSL	0:d92f9d21154c	2548	}
wolfSSL	0:d92f9d21154c	2549
wolfSSL	0:d92f9d21154c	2550	#endif /* WOLFSSL_KEY_GEN */
wolfSSL	0:d92f9d21154c	2551
wolfSSL	0:d92f9d21154c	2552
wolfSSL	0:d92f9d21154c	2553	#if defined(HAVE_ECC) \|\| !defined(NO_PWDBASED)
wolfSSL	0:d92f9d21154c	2554	/* c = a + b */
wolfSSL	0:d92f9d21154c	2555	void fp_add_d(fp_int a, fp_digit b, fp_int c)
wolfSSL	0:d92f9d21154c	2556	{
wolfSSL	0:d92f9d21154c	2557	fp_int tmp;
wolfSSL	0:d92f9d21154c	2558	fp_init(&tmp);
wolfSSL	0:d92f9d21154c	2559	fp_set(&tmp, b);
wolfSSL	0:d92f9d21154c	2560	fp_add(a,&tmp,c);
wolfSSL	0:d92f9d21154c	2561	}
wolfSSL	0:d92f9d21154c	2562
wolfSSL	0:d92f9d21154c	2563	/* external compatibility */
wolfSSL	0:d92f9d21154c	2564	int mp_add_d(fp_int a, fp_digit b, fp_int c)
wolfSSL	0:d92f9d21154c	2565	{
wolfSSL	0:d92f9d21154c	2566	fp_add_d(a, b, c);
wolfSSL	0:d92f9d21154c	2567	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2568	}
wolfSSL	0:d92f9d21154c	2569
wolfSSL	0:d92f9d21154c	2570	#endif /* HAVE_ECC \|\| !NO_PWDBASED */
wolfSSL	0:d92f9d21154c	2571
wolfSSL	0:d92f9d21154c	2572
wolfSSL	0:d92f9d21154c	2573	#ifdef HAVE_ECC
wolfSSL	0:d92f9d21154c	2574
wolfSSL	0:d92f9d21154c	2575	/* chars used in radix conversions */
wolfSSL	0:d92f9d21154c	2576	static const char *fp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
wolfSSL	0:d92f9d21154c	2577
wolfSSL	0:d92f9d21154c	2578	static int fp_read_radix(fp_int a, const char str, int radix)
wolfSSL	0:d92f9d21154c	2579	{
wolfSSL	0:d92f9d21154c	2580	int y, neg;
wolfSSL	0:d92f9d21154c	2581	char ch;
wolfSSL	0:d92f9d21154c	2582
wolfSSL	0:d92f9d21154c	2583	/* make sure the radix is ok */
wolfSSL	0:d92f9d21154c	2584	if (radix < 2 \|\| radix > 64) {
wolfSSL	0:d92f9d21154c	2585	return FP_VAL;
wolfSSL	0:d92f9d21154c	2586	}
wolfSSL	0:d92f9d21154c	2587
wolfSSL	0:d92f9d21154c	2588	/* if the leading digit is a
wolfSSL	0:d92f9d21154c	2589	* minus set the sign to negative.
wolfSSL	0:d92f9d21154c	2590	*/
wolfSSL	0:d92f9d21154c	2591	if (*str == '-') {
wolfSSL	0:d92f9d21154c	2592	++str;
wolfSSL	0:d92f9d21154c	2593	neg = FP_NEG;
wolfSSL	0:d92f9d21154c	2594	} else {
wolfSSL	0:d92f9d21154c	2595	neg = FP_ZPOS;
wolfSSL	0:d92f9d21154c	2596	}
wolfSSL	0:d92f9d21154c	2597
wolfSSL	0:d92f9d21154c	2598	/* set the integer to the default of zero */
wolfSSL	0:d92f9d21154c	2599	fp_zero (a);
wolfSSL	0:d92f9d21154c	2600
wolfSSL	0:d92f9d21154c	2601	/* process each digit of the string */
wolfSSL	0:d92f9d21154c	2602	while (*str) {
wolfSSL	0:d92f9d21154c	2603	/* if the radix < 36 the conversion is case insensitive
wolfSSL	0:d92f9d21154c	2604	* this allows numbers like 1AB and 1ab to represent the same value
wolfSSL	0:d92f9d21154c	2605	* [e.g. in hex]
wolfSSL	0:d92f9d21154c	2606	*/
wolfSSL	0:d92f9d21154c	2607	ch = (char) ((radix < 36) ? XTOUPPER((unsigned char)str) : str);
wolfSSL	0:d92f9d21154c	2608	for (y = 0; y < 64; y++) {
wolfSSL	0:d92f9d21154c	2609	if (ch == fp_s_rmap[y]) {
wolfSSL	0:d92f9d21154c	2610	break;
wolfSSL	0:d92f9d21154c	2611	}
wolfSSL	0:d92f9d21154c	2612	}
wolfSSL	0:d92f9d21154c	2613
wolfSSL	0:d92f9d21154c	2614	/* if the char was found in the map
wolfSSL	0:d92f9d21154c	2615	* and is less than the given radix add it
wolfSSL	0:d92f9d21154c	2616	* to the number, otherwise exit the loop.
wolfSSL	0:d92f9d21154c	2617	*/
wolfSSL	0:d92f9d21154c	2618	if (y < radix) {
wolfSSL	0:d92f9d21154c	2619	fp_mul_d (a, (fp_digit) radix, a);
wolfSSL	0:d92f9d21154c	2620	fp_add_d (a, (fp_digit) y, a);
wolfSSL	0:d92f9d21154c	2621	} else {
wolfSSL	0:d92f9d21154c	2622	break;
wolfSSL	0:d92f9d21154c	2623	}
wolfSSL	0:d92f9d21154c	2624	++str;
wolfSSL	0:d92f9d21154c	2625	}
wolfSSL	0:d92f9d21154c	2626
wolfSSL	0:d92f9d21154c	2627	/* set the sign only if a != 0 */
wolfSSL	0:d92f9d21154c	2628	if (fp_iszero(a) != FP_YES) {
wolfSSL	0:d92f9d21154c	2629	a->sign = neg;
wolfSSL	0:d92f9d21154c	2630	}
wolfSSL	0:d92f9d21154c	2631	return FP_OKAY;
wolfSSL	0:d92f9d21154c	2632	}
wolfSSL	0:d92f9d21154c	2633
wolfSSL	0:d92f9d21154c	2634	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2635	int mp_read_radix(mp_int a, const char str, int radix)
wolfSSL	0:d92f9d21154c	2636	{
wolfSSL	0:d92f9d21154c	2637	return fp_read_radix(a, str, radix);
wolfSSL	0:d92f9d21154c	2638	}
wolfSSL	0:d92f9d21154c	2639
wolfSSL	0:d92f9d21154c	2640	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2641	void mp_set(fp_int *a, fp_digit b)
wolfSSL	0:d92f9d21154c	2642	{
wolfSSL	0:d92f9d21154c	2643	fp_set(a,b);
wolfSSL	0:d92f9d21154c	2644	}
wolfSSL	0:d92f9d21154c	2645
wolfSSL	0:d92f9d21154c	2646	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2647	int mp_sqr(fp_int A, fp_int B)
wolfSSL	0:d92f9d21154c	2648	{
wolfSSL	0:d92f9d21154c	2649	fp_sqr(A, B);
wolfSSL	0:d92f9d21154c	2650	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2651	}
wolfSSL	0:d92f9d21154c	2652
wolfSSL	0:d92f9d21154c	2653	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2654	int mp_montgomery_reduce(fp_int a, fp_int m, fp_digit mp)
wolfSSL	0:d92f9d21154c	2655	{
wolfSSL	0:d92f9d21154c	2656	fp_montgomery_reduce(a, m, mp);
wolfSSL	0:d92f9d21154c	2657	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2658	}
wolfSSL	0:d92f9d21154c	2659
wolfSSL	0:d92f9d21154c	2660
wolfSSL	0:d92f9d21154c	2661	/* fast math conversion */
wolfSSL	0:d92f9d21154c	2662	int mp_montgomery_setup(fp_int a, fp_digit rho)
wolfSSL	0:d92f9d21154c	2663	{
wolfSSL	0:d92f9d21154c	2664	return fp_montgomery_setup(a, rho);
wolfSSL	0:d92f9d21154c	2665	}
wolfSSL	0:d92f9d21154c	2666
wolfSSL	0:d92f9d21154c	2667	int mp_div_2(fp_int * a, fp_int * b)
wolfSSL	0:d92f9d21154c	2668	{
wolfSSL	0:d92f9d21154c	2669	fp_div_2(a, b);
wolfSSL	0:d92f9d21154c	2670	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2671	}
wolfSSL	0:d92f9d21154c	2672
wolfSSL	0:d92f9d21154c	2673
wolfSSL	0:d92f9d21154c	2674	int mp_init_copy(fp_int * a, fp_int * b)
wolfSSL	0:d92f9d21154c	2675	{
wolfSSL	0:d92f9d21154c	2676	fp_init_copy(a, b);
wolfSSL	0:d92f9d21154c	2677	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2678	}
wolfSSL	0:d92f9d21154c	2679
wolfSSL	0:d92f9d21154c	2680
wolfSSL	0:d92f9d21154c	2681	#ifdef HAVE_COMP_KEY
wolfSSL	0:d92f9d21154c	2682
wolfSSL	0:d92f9d21154c	2683	int mp_cnt_lsb(fp_int* a)
wolfSSL	0:d92f9d21154c	2684	{
wolfSSL	0:d92f9d21154c	2685	fp_cnt_lsb(a);
wolfSSL	0:d92f9d21154c	2686	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2687	}
wolfSSL	0:d92f9d21154c	2688
wolfSSL	0:d92f9d21154c	2689	int mp_div_2d(fp_int* a, int b, fp_int* c, fp_int* d)
wolfSSL	0:d92f9d21154c	2690	{
wolfSSL	0:d92f9d21154c	2691	fp_div_2d(a, b, c, d);
wolfSSL	0:d92f9d21154c	2692	return MP_OKAY;
wolfSSL	0:d92f9d21154c	2693	}
wolfSSL	0:d92f9d21154c	2694
wolfSSL	0:d92f9d21154c	2695	#endif /* HAVE_COMP_KEY */
wolfSSL	0:d92f9d21154c	2696
wolfSSL	0:d92f9d21154c	2697
wolfSSL	0:d92f9d21154c	2698	#endif /* HAVE_ECC */
wolfSSL	0:d92f9d21154c	2699
wolfSSL	0:d92f9d21154c	2700	#endif /* USE_FAST_MATH */
wolfSSL	0:d92f9d21154c	2701
wolfSSL	0:d92f9d21154c	2702

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	26 Jun 2015
Imports:	673
Forks:	0
Commits:	18
Dependents:	29
Dependencies:	0
Followers:	21

wolfcrypt/src/tfm.c@0:d92f9d21154c, 2015-06-26 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning