wolfSSL | Mbed

Users » sPymbed » Code » wolfSSL

wolfcrypt/src/tfm.c@4:1b0d80432c79, 2016-04-28 (annotated)

Committer:: wolfSSL
Date:: Thu Apr 28 00:57:21 2016 +0000
Revision:: 4:1b0d80432c79

wolfSSL 3.9.0

Who changed what in which revision?

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

Repository toolbox

Repository details

Type:	Library
Created:	19 Nov 2019
Imports:	7
Forks:	0
Commits:	18
Dependents:	1
Dependencies:	0
Followers:	1

Important changes to repositories hosted on mbed.com

wolfcrypt/src/tfm.c@4:1b0d80432c79, 2016-04-28 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Important changes to repositories hosted on mbed.com

wolfcrypt/src/tfm.c@4:1b0d80432c79, 2016-04-28 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning