wolfSSL-TLS13-Beta - wolfSSL 3.11.1 for TLS1.3 beta

Users » wolfSSL » Code » wolfSSL-TLS13-Beta

wolfSSL 3.11.1 for TLS1.3 beta

wolfcrypt/src/tfm.c@13:80fb167dafdf, 2017-05-30 (annotated)

Committer:: wolfSSL
Date:: Tue May 30 06:16:19 2017 +0000
Revision:: 13:80fb167dafdf
Parent:: 11:cee25a834751

wolfSSL 3.11.1: TLS1.3 Beta

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	30 May 2017
Imports:	0
Forks:	0
Commits:	14
Dependents:	0
Dependencies:	0
Followers:	1

This repository is Public (Unlisted).

wolfcrypt/src/tfm.c@13:80fb167dafdf, 2017-05-30 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning