CyaSSL - Fork of CyaSSL for my specific settings

Users » d0773d » Code » CyaSSL

Fork of CyaSSL for my specific settings

ctaocrypt/src/tfm.c@4:28ac50e1d49c, 2015-03-03 (annotated)

Committer:: d0773d
Date:: Tue Mar 03 22:52:52 2015 +0000
Revision:: 4:28ac50e1d49c
Parent:: 0:1239e9b70ca2

CyaSSL example

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	03 Mar 2015
Imports:	2
Forks:	0
Commits:	5
Dependents:	1
Dependencies:	0
Followers:	2

ctaocrypt/src/tfm.c@4:28ac50e1d49c, 2015-03-03 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning