wolfSSL | Mbed

Users » sPymbed » Code » wolfSSL

wolfcrypt/src/tfm.c@16:048e5e270a58, 2019-11-19 (annotated)

Committer:: sPymbed
Date:: Tue Nov 19 14:32:16 2019 +0000
Revision:: 16:048e5e270a58
Parent:: 15:117db924cf7c

working ssl

Who changed what in which revision?

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

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@16:048e5e270a58, 2019-11-19 (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@16:048e5e270a58, 2019-11-19 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning