CyaSSL - A library for setting up Secure Socket Layer (SSL…

MultiTech » Code » CyaSSL

A library for setting up Secure Socket Layer (SSL) connections and verifying remote hosts using certificates. Contains only the source files for mbed platform implementation of the library.

Dependents: HTTPClient-SSL HTTPClient-SSL HTTPClient-SSL HTTPClient-SSL

ctaocrypt/src/tfm.c@6:cf58d49e1a86, 2015-03-23 (annotated)

Committer:: Mike Fiore
Date:: Mon Mar 23 16:51:07 2015 -0500
Revision:: 6:cf58d49e1a86
Parent:: 0:b86d15c6ba29

fix whitespace in sha512.c

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	27 Mar 2015
Imports:	27
Forks:	0
Commits:	7
Dependents:	4
Dependencies:	0
Followers:	87

ctaocrypt/src/tfm.c@6:cf58d49e1a86, 2015-03-23 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning