Mercurial > projects > hoofbaby

annotate deps/Platinum/ThirdParty/Neptune/ThirdParty/axTLS/crypto/bigint.c @ 0:3425707ddbf6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import (hopefully this mercurial stuff works...)
author fraserofthenight
date Mon, 06 Jul 2009 08:06:28 -0700
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
2 * Copyright (c) 2007, Cameron Rich
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
3 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
4 * All rights reserved.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
5 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
8 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
9 * * Redistributions of source code must retain the above copyright notice,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
10 * this list of conditions and the following disclaimer.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
11 * * Redistributions in binary form must reproduce the above copyright notice,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
12 * this list of conditions and the following disclaimer in the documentation
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
13 * and/or other materials provided with the distribution.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
14 * * Neither the name of the axTLS project nor the names of its contributors
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
15 * may be used to endorse or promote products derived from this software
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
16 * without specific prior written permission.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
17 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
25 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
26 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
27 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
29 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
30
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
31 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
32 * @defgroup bigint_api Big Integer API
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
33 * @brief The bigint implementation as used by the axTLS project.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
34 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
35 * The bigint library is for RSA encryption/decryption as well as signing.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
36 * This code tries to minimise use of malloc/free by maintaining a small
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
37 * cache. A bigint context may maintain state by being made "permanent".
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
38 * It be be later released with a bi_depermanent() and bi_free() call.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
39 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
40 * It supports the following reduction techniques:
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
41 * - Classical
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
42 * - Barrett
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
43 * - Montgomery
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
44 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
45 * It also implements the following:
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
46 * - Karatsuba multiplication
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
47 * - Squaring
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
48 * - Sliding window exponentiation
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
49 * - Chinese Remainder Theorem (implemented in rsa.c).
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
50 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
51 * All the algorithms used are pretty standard, and designed for different
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
52 * data bus sizes. Negative numbers are not dealt with at all, so a subtraction
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
53 * may need to be tested for negativity.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
54 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
55 * This library steals some ideas from Jef Poskanzer
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
56 * <http://cs.marlboro.edu/term/cs-fall02/algorithms/crypto/RSA/bigint>
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
57 * and GMP <http://www.swox.com/gmp>. It gets most of its implementation
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
58 * detail from "The Handbook of Applied Cryptography"
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
59 * <http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf>
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
60 * @{
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
61 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
62
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
63 #include <stdlib.h>
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
64 #include <limits.h>
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
65 #include <string.h>
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
66 #include <stdio.h>
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
67 #include <time.h>
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
68 #include "bigint.h"
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
69
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
70 #define V1 v->comps[v->size-1] /**< v1 for division */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
71 #define V2 v->comps[v->size-2] /**< v2 for division */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
72 #define U(j) tmp_u->comps[tmp_u->size-j-1] /**< uj for division */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
73 #define Q(j) quotient->comps[quotient->size-j-1] /**< qj for division */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
74
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
75 static bigint *bi_int_multiply(BI_CTX *ctx, bigint *bi, comp i);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
76 static bigint *bi_int_divide(BI_CTX *ctx, bigint *biR, comp denom);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
77 static bigint *alloc(BI_CTX *ctx, int size);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
78 static bigint *trim(bigint *bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
79 static void more_comps(bigint *bi, int n);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
80 #if defined(CONFIG_BIGINT_KARATSUBA) || defined(CONFIG_BIGINT_BARRETT) || \
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
81 defined(CONFIG_BIGINT_MONTGOMERY)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
82 static bigint *comp_right_shift(bigint *biR, int num_shifts);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
83 static bigint *comp_left_shift(bigint *biR, int num_shifts);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
84 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
85
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
86 #ifdef CONFIG_BIGINT_CHECK_ON
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
87 static void check(const bigint *bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
88 #else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
89 #define check(A) /**< disappears in normal production mode */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
90 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
91
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
92
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
93 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
94 * @brief Start a new bigint context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
95 * @return A bigint context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
96 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
97 BI_CTX *bi_initialize(void)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
98 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
99 /* calloc() sets everything to zero */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
100 BI_CTX *ctx = (BI_CTX *)calloc(1, sizeof(BI_CTX));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
101
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
102 /* the radix */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
103 ctx->bi_radix = alloc(ctx, 2);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
104 ctx->bi_radix->comps[0] = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
105 ctx->bi_radix->comps[1] = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
106 bi_permanent(ctx->bi_radix);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
107 return ctx;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
108 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
109
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
110 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
111 * @brief Close the bigint context and free any resources.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
112 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
113 * Free up any used memory - a check is done if all objects were not
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
114 * properly freed.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
115 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
116 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
117 void bi_terminate(BI_CTX *ctx)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
118 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
119 bi_depermanent(ctx->bi_radix);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
120 bi_free(ctx, ctx->bi_radix);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
121
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
122 if (ctx->active_count != 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
123 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
124 #ifdef CONFIG_SSL_FULL_MODE
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
125 printf("bi_terminate: there were %d un-freed bigints\n",
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
126 ctx->active_count);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
127 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
128 abort();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
129 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
130
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
131 bi_clear_cache(ctx);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
132 free(ctx);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
133 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
134
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
135 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
136 *@brief Clear the memory cache.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
137 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
138 void bi_clear_cache(BI_CTX *ctx)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
139 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
140 bigint *p, *pn;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
141
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
142 if (ctx->free_list == NULL)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
143 return;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
144
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
145 for (p = ctx->free_list; p != NULL; p = pn)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
146 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
147 pn = p->next;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
148 free(p->comps);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
149 free(p);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
150 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
151
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
152 ctx->free_count = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
153 ctx->free_list = NULL;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
154 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
155
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
156 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
157 * @brief Increment the number of references to this object.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
158 * It does not do a full copy.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
159 * @param bi [in] The bigint to copy.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
160 * @return A reference to the same bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
161 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
162 bigint *bi_copy(bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
163 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
164 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
165 if (bi->refs != PERMANENT)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
166 bi->refs++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
167 return bi;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
168 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
169
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
170 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
171 * @brief Simply make a bigint object "unfreeable" if bi_free() is called on it.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
172 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
173 * For this object to be freed, bi_depermanent() must be called.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
174 * @param bi [in] The bigint to be made permanent.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
175 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
176 void bi_permanent(bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
177 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
178 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
179 if (bi->refs != 1)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
180 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
181 #ifdef CONFIG_SSL_FULL_MODE
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
182 printf("bi_permanent: refs was not 1\n");
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
183 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
184 abort();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
185 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
186
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
187 bi->refs = PERMANENT;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
188 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
189
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
190 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
191 * @brief Take a permanent object and make it eligible for freedom.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
192 * @param bi [in] The bigint to be made back to temporary.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
193 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
194 void bi_depermanent(bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
195 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
196 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
197 if (bi->refs != PERMANENT)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
198 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
199 #ifdef CONFIG_SSL_FULL_MODE
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
200 printf("bi_depermanent: bigint was not permanent\n");
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
201 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
202 abort();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
203 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
204
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
205 bi->refs = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
206 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
207
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
208 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
209 * @brief Free a bigint object so it can be used again.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
210 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
211 * The memory itself it not actually freed, just tagged as being available
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
212 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
213 * @param bi [in] The bigint to be freed.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
214 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
215 void bi_free(BI_CTX *ctx, bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
216 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
217 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
218 if (bi->refs == PERMANENT)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
219 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
220 return;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
221 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
222
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
223 if (--bi->refs > 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
224 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
225 return;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
226 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
227
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
228 bi->next = ctx->free_list;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
229 ctx->free_list = bi;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
230 ctx->free_count++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
231
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
232 if (--ctx->active_count < 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
233 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
234 #ifdef CONFIG_SSL_FULL_MODE
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
235 printf("bi_free: active_count went negative "
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
236 "- double-freed bigint?\n");
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
237 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
238 abort();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
239 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
240 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
241
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
242 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
243 * @brief Convert an (unsigned) integer into a bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
244 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
245 * @param i [in] The (unsigned) integer to be converted.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
246 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
247 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
248 bigint *int_to_bi(BI_CTX *ctx, comp i)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
249 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
250 bigint *biR = alloc(ctx, 1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
251 biR->comps[0] = i;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
252 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
253 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
254
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
255 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
256 * @brief Do a full copy of the bigint object.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
257 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
258 * @param bi [in] The bigint object to be copied.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
259 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
260 bigint *bi_clone(BI_CTX *ctx, const bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
261 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
262 bigint *biR = alloc(ctx, bi->size);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
263 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
264 memcpy(biR->comps, bi->comps, bi->size*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
265 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
266 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
267
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
268 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
269 * @brief Perform an addition operation between two bigints.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
270 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
271 * @param bia [in] A bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
272 * @param bib [in] Another bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
273 * @return The result of the addition.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
274 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
275 bigint *bi_add(BI_CTX *ctx, bigint *bia, bigint *bib)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
276 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
277 int n;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
278 comp carry = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
279 comp *pa, *pb;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
280
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
281 check(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
282 check(bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
283
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
284 n = max(bia->size, bib->size);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
285 more_comps(bia, n+1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
286 more_comps(bib, n);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
287 pa = bia->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
288 pb = bib->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
289
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
290 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
291 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
292 comp sl, rl, cy1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
293 sl = *pa + *pb++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
294 rl = sl + carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
295 cy1 = sl < *pa;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
296 carry = cy1 | (rl < sl);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
297 *pa++ = rl;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
298 } while (--n != 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
299
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
300 *pa = carry; /* do overflow */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
301 bi_free(ctx, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
302 return trim(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
303 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
304
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
305 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
306 * @brief Perform a subtraction operation between two bigints.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
307 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
308 * @param bia [in] A bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
309 * @param bib [in] Another bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
310 * @param is_negative [out] If defined, indicates that the result was negative.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
311 * is_negative may be null.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
312 * @return The result of the subtraction. The result is always positive.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
313 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
314 bigint *bi_subtract(BI_CTX *ctx,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
315 bigint *bia, bigint *bib, int *is_negative)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
316 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
317 int n = bia->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
318 comp *pa, *pb, carry = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
319
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
320 check(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
321 check(bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
322
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
323 more_comps(bib, n);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
324 pa = bia->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
325 pb = bib->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
326
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
327 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
328 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
329 comp sl, rl, cy1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
330 sl = *pa - *pb++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
331 rl = sl - carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
332 cy1 = sl > *pa;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
333 carry = cy1 | (rl > sl);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
334 *pa++ = rl;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
335 } while (--n != 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
336
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
337 if (is_negative) /* indicate a negative result */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
338 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
339 *is_negative = carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
340 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
341
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
342 bi_free(ctx, trim(bib)); /* put bib back to the way it was */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
343 return trim(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
344 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
345
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
346 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
347 * Perform a multiply between a bigint an an (unsigned) integer
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
348 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
349 static bigint *bi_int_multiply(BI_CTX *ctx, bigint *bia, comp b)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
350 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
351 int j = 0, n = bia->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
352 bigint *biR = alloc(ctx, n + 1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
353 comp carry = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
354 comp *r = biR->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
355 comp *a = bia->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
356
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
357 check(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
358
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
359 /* clear things to start with */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
360 memset(r, 0, ((n+1)*COMP_BYTE_SIZE));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
361
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
362 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
363 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
364 long_comp tmp = *r + (long_comp)a[j]*b + carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
365 *r++ = (comp)tmp; /* downsize */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
366 carry = (comp)(tmp >> COMP_BIT_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
367 } while (++j < n);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
368
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
369 *r = carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
370 bi_free(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
371 return trim(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
372 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
373
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
374 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
375 * @brief Does both division and modulo calculations.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
376 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
377 * Used extensively when doing classical reduction.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
378 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
379 * @param u [in] A bigint which is the numerator.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
380 * @param v [in] Either the denominator or the modulus depending on the mode.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
381 * @param is_mod [n] Determines if this is a normal division (0) or a reduction
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
382 * (1).
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
383 * @return The result of the division/reduction.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
384 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
385 bigint *bi_divide(BI_CTX *ctx, bigint *u, bigint *v, int is_mod)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
386 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
387 int n = v->size, m = u->size-n;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
388 int j = 0, orig_u_size = u->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
389 uint8_t mod_offset = ctx->mod_offset;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
390 comp d;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
391 bigint *quotient, *tmp_u;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
392 comp q_dash;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
393
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
394 check(u);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
395 check(v);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
396
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
397 /* if doing reduction and we are < mod, then return mod */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
398 if (is_mod && bi_compare(v, u) > 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
399 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
400 bi_free(ctx, v);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
401 return u;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
402 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
403
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
404 quotient = alloc(ctx, m+1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
405 tmp_u = alloc(ctx, n+1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
406 v = trim(v); /* make sure we have no leading 0's */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
407 d = (comp)((long_comp)COMP_RADIX/(V1+1));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
408
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
409 /* clear things to start with */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
410 memset(quotient->comps, 0, ((quotient->size)*COMP_BYTE_SIZE));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
411
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
412 /* normalise */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
413 if (d > 1)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
414 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
415 u = bi_int_multiply(ctx, u, d);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
416
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
417 if (is_mod)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
418 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
419 v = ctx->bi_normalised_mod[mod_offset];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
420 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
421 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
422 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
423 v = bi_int_multiply(ctx, v, d);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
424 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
425 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
426
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
427 if (orig_u_size == u->size) /* new digit position u0 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
428 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
429 more_comps(u, orig_u_size + 1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
430 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
431
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
432 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
433 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
434 /* get a temporary short version of u */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
435 memcpy(tmp_u->comps, &u->comps[u->size-n-1-j], (n+1)*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
436
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
437 /* calculate q' */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
438 if (U(0) == V1)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
439 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
440 q_dash = COMP_RADIX-1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
441 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
442 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
443 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
444 q_dash = (comp)(((long_comp)U(0)*COMP_RADIX + U(1))/V1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
445 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
446
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
447 if (v->size > 1 && V2)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
448 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
449 /* we are implementing the following:
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
450 if (V2*q_dash > (((U(0)*COMP_RADIX + U(1) -
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
451 q_dash*V1)*COMP_RADIX) + U(2))) ... */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
452 comp inner = (comp)((long_comp)COMP_RADIX*U(0) + U(1) -
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
453 (long_comp)q_dash*V1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
454 if ((long_comp)V2*q_dash > (long_comp)inner*COMP_RADIX + U(2))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
455 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
456 q_dash--;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
457 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
458 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
459
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
460 /* multiply and subtract */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
461 if (q_dash)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
462 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
463 int is_negative;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
464 tmp_u = bi_subtract(ctx, tmp_u,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
465 bi_int_multiply(ctx, bi_copy(v), q_dash), &is_negative);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
466 more_comps(tmp_u, n+1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
467
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
468 Q(j) = q_dash;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
469
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
470 /* add back */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
471 if (is_negative)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
472 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
473 Q(j)--;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
474 tmp_u = bi_add(ctx, tmp_u, bi_copy(v));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
475
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
476 /* lop off the carry */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
477 tmp_u->size--;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
478 v->size--;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
479 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
480 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
481 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
482 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
483 Q(j) = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
484 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
485
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
486 /* copy back to u */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
487 memcpy(&u->comps[u->size-n-1-j], tmp_u->comps, (n+1)*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
488 } while (++j <= m);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
489
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
490 bi_free(ctx, tmp_u);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
491 bi_free(ctx, v);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
492
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
493 if (is_mod) /* get the remainder */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
494 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
495 bi_free(ctx, quotient);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
496 return bi_int_divide(ctx, trim(u), d);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
497 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
498 else /* get the quotient */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
499 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
500 bi_free(ctx, u);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
501 return trim(quotient);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
502 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
503 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
504
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
505 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
506 * Perform an integer divide on a bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
507 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
508 static bigint *bi_int_divide(BI_CTX *ctx, bigint *biR, comp denom)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
509 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
510 int i = biR->size - 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
511 (void)ctx; /* unused */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
512 long_comp r = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
513
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
514 check(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
515
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
516 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
517 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
518 r = (r<<COMP_BIT_SIZE) + biR->comps[i];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
519 biR->comps[i] = (comp)(r / denom);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
520 r %= denom;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
521 } while (--i >= 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
522
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
523 return trim(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
524 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
525
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
526 #ifdef CONFIG_BIGINT_MONTGOMERY
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
527 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
528 * There is a need for the value of integer N' such that B^-1(B-1)-N^-1N'=1,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
529 * where B^-1(B-1) mod N=1. Actually, only the least significant part of
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
530 * N' is needed, hence the definition N0'=N' mod b. We reproduce below the
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
531 * simple algorithm from an article by Dusse and Kaliski to efficiently
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
532 * find N0' from N0 and b */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
533 static comp modular_inverse(bigint *bim)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
534 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
535 int i;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
536 comp t = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
537 comp two_2_i_minus_1 = 2; /* 2^(i-1) */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
538 long_comp two_2_i = 4; /* 2^i */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
539 comp N = bim->comps[0];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
540
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
541 for (i = 2; i <= COMP_BIT_SIZE; i++)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
542 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
543 if ((long_comp)N*t%two_2_i >= two_2_i_minus_1)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
544 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
545 t += two_2_i_minus_1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
546 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
547
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
548 two_2_i_minus_1 <<= 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
549 two_2_i <<= 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
550 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
551
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
552 return (comp)(COMP_RADIX-t);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
553 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
554 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
555
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
556 #if defined(CONFIG_BIGINT_KARATSUBA) || defined(CONFIG_BIGINT_BARRETT) || \
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
557 defined(CONFIG_BIGINT_MONTGOMERY)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
558 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
559 * Take each component and shift down (in terms of components)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
560 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
561 static bigint *comp_right_shift(bigint *biR, int num_shifts)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
562 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
563 int i = biR->size-num_shifts;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
564 comp *x = biR->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
565 comp *y = &biR->comps[num_shifts];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
566
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
567 check(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
568
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
569 if (i <= 0) /* have we completely right shifted? */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
570 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
571 biR->comps[0] = 0; /* return 0 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
572 biR->size = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
573 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
574 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
575
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
576 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
577 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
578 *x++ = *y++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
579 } while (--i > 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
580
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
581 biR->size -= num_shifts;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
582 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
583 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
584
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
585 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
586 * Take each component and shift it up (in terms of components)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
587 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
588 static bigint *comp_left_shift(bigint *biR, int num_shifts)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
589 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
590 int i = biR->size-1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
591 comp *x, *y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
592
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
593 check(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
594
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
595 if (num_shifts <= 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
596 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
597 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
598 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
599
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
600 more_comps(biR, biR->size + num_shifts);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
601
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
602 x = &biR->comps[i+num_shifts];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
603 y = &biR->comps[i];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
604
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
605 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
606 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
607 *x-- = *y--;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
608 } while (i--);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
609
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
610 memset(biR->comps, 0, num_shifts*COMP_BYTE_SIZE); /* zero LS comps */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
611 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
612 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
613 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
614
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
615 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
616 * @brief Allow a binary sequence to be imported as a bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
617 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
618 * @param data [in] The data to be converted.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
619 * @param size [in] The number of bytes of data.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
620 * @return A bigint representing this data.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
621 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
622 bigint *bi_import(BI_CTX *ctx, const uint8_t *data, int size)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
623 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
624 bigint *biR = alloc(ctx, (size+COMP_BYTE_SIZE-1)/COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
625 int i, j = 0, offset = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
626
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
627 memset(biR->comps, 0, biR->size*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
628
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
629 for (i = size-1; i >= 0; i--)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
630 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
631 biR->comps[offset] += data[i] << (j*8);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
632
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
633 if (++j == COMP_BYTE_SIZE)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
634 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
635 j = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
636 offset ++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
637 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
638 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
639
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
640 return trim(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
641 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
642
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
643 #ifdef CONFIG_SSL_FULL_MODE
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
644 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
645 * @brief The testharness uses this code to import text hex-streams and
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
646 * convert them into bigints.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
647 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
648 * @param data [in] A string consisting of hex characters. The characters must
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
649 * be in upper case.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
650 * @return A bigint representing this data.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
651 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
652 bigint *bi_str_import(BI_CTX *ctx, const char *data)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
653 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
654 int size = strlen(data);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
655 bigint *biR = alloc(ctx, (size+COMP_NUM_NIBBLES-1)/COMP_NUM_NIBBLES);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
656 int i, j = 0, offset = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
657 memset(biR->comps, 0, biR->size*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
658
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
659 for (i = size-1; i >= 0; i--)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
660 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
661 int num = (data[i] <= '9') ? (data[i] - '0') : (data[i] - 'A' + 10);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
662 biR->comps[offset] += num << (j*4);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
663
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
664 if (++j == COMP_NUM_NIBBLES)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
665 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
666 j = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
667 offset ++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
668 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
669 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
670
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
671 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
672 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
673
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
674 void bi_print(const char *label, bigint *x)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
675 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
676 int i, j;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
677
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
678 if (x == NULL)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
679 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
680 printf("%s: (null)\n", label);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
681 return;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
682 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
683
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
684 printf("%s: (size %d)\n", label, x->size);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
685 for (i = x->size-1; i >= 0; i--)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
686 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
687 for (j = COMP_NUM_NIBBLES-1; j >= 0; j--)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
688 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
689 comp mask = 0x0f << (j*4);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
690 comp num = (x->comps[i] & mask) >> (j*4);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
691 putc((num <= 9) ? (num + '0') : (num + 'A' - 10), stdout);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
692 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
693 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
694
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
695 printf("\n");
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
696 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
697 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
698
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
699 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
700 * @brief Take a bigint and convert it into a byte sequence.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
701 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
702 * This is useful after a decrypt operation.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
703 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
704 * @param x [in] The bigint to be converted.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
705 * @param data [out] The converted data as a byte stream.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
706 * @param size [in] The maximum size of the byte stream. Unused bytes will be
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
707 * zeroed.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
708 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
709 void bi_export(BI_CTX *ctx, bigint *x, uint8_t *data, int size)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
710 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
711 int i, j, k = size-1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
712
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
713 check(x);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
714 memset(data, 0, size); /* ensure all leading 0's are cleared */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
715
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
716 for (i = 0; i < x->size; i++)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
717 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
718 for (j = 0; j < COMP_BYTE_SIZE; j++)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
719 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
720 comp mask = 0xff << (j*8);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
721 int num = (x->comps[i] & mask) >> (j*8);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
722 data[k--] = num;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
723
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
724 if (k < 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
725 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
726 break;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
727 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
728 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
729 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
730
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
731 bi_free(ctx, x);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
732 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
733
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
734 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
735 * @brief Pre-calculate some of the expensive steps in reduction.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
736 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
737 * This function should only be called once (normally when a session starts).
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
738 * When the session is over, bi_free_mod() should be called. bi_mod_power()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
739 * relies on this function being called.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
740 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
741 * @param bim [in] The bigint modulus that will be used.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
742 * @param mod_offset [in] There are three moduluii that can be stored - the
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
743 * standard modulus, and its two primes p and q. This offset refers to which
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
744 * modulus we are referring to.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
745 * @see bi_free_mod(), bi_mod_power().
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
746 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
747 void bi_set_mod(BI_CTX *ctx, bigint *bim, int mod_offset)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
748 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
749 int k = bim->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
750 comp d = (comp)((long_comp)COMP_RADIX/(bim->comps[k-1]+1));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
751 #ifdef CONFIG_BIGINT_MONTGOMERY
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
752 bigint *R, *R2;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
753 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
754
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
755 ctx->bi_mod[mod_offset] = bim;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
756 bi_permanent(ctx->bi_mod[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
757 ctx->bi_normalised_mod[mod_offset] = bi_int_multiply(ctx, bim, d);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
758 bi_permanent(ctx->bi_normalised_mod[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
759
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
760 #if defined(CONFIG_BIGINT_MONTGOMERY)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
761 /* set montgomery variables */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
762 R = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k-1); /* R */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
763 R2 = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k*2-1); /* R^2 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
764 ctx->bi_RR_mod_m[mod_offset] = bi_mod(ctx, R2); /* R^2 mod m */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
765 ctx->bi_R_mod_m[mod_offset] = bi_mod(ctx, R); /* R mod m */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
766
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
767 bi_permanent(ctx->bi_RR_mod_m[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
768 bi_permanent(ctx->bi_R_mod_m[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
769
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
770 ctx->N0_dash[mod_offset] = modular_inverse(ctx->bi_mod[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
771
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
772 #elif defined (CONFIG_BIGINT_BARRETT)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
773 ctx->bi_mu[mod_offset] =
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
774 bi_divide(ctx, comp_left_shift(
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
775 bi_clone(ctx, ctx->bi_radix), k*2-1), ctx->bi_mod[mod_offset], 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
776 bi_permanent(ctx->bi_mu[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
777 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
778 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
779
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
780 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
781 * @brief Used when cleaning various bigints at the end of a session.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
782 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
783 * @param mod_offset [in] The offset to use.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
784 * @see bi_set_mod().
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
785 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
786 void bi_free_mod(BI_CTX *ctx, int mod_offset)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
787 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
788 bi_depermanent(ctx->bi_mod[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
789 bi_free(ctx, ctx->bi_mod[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
790 #if defined (CONFIG_BIGINT_MONTGOMERY)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
791 bi_depermanent(ctx->bi_RR_mod_m[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
792 bi_depermanent(ctx->bi_R_mod_m[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
793 bi_free(ctx, ctx->bi_RR_mod_m[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
794 bi_free(ctx, ctx->bi_R_mod_m[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
795 #elif defined(CONFIG_BIGINT_BARRETT)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
796 bi_depermanent(ctx->bi_mu[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
797 bi_free(ctx, ctx->bi_mu[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
798 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
799 bi_depermanent(ctx->bi_normalised_mod[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
800 bi_free(ctx, ctx->bi_normalised_mod[mod_offset]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
801 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
802
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
803 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
804 * Perform a standard multiplication between two bigints.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
805 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
806 static bigint *regular_multiply(BI_CTX *ctx, bigint *bia, bigint *bib)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
807 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
808 int i, j, i_plus_j;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
809 int n = bia->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
810 int t = bib->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
811 bigint *biR = alloc(ctx, n + t);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
812 comp *sr = biR->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
813 comp *sa = bia->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
814 comp *sb = bib->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
815
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
816 check(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
817 check(bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
818
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
819 /* clear things to start with */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
820 memset(biR->comps, 0, ((n+t)*COMP_BYTE_SIZE));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
821 i = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
822
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
823 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
824 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
825 comp carry = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
826 comp b = *sb++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
827 i_plus_j = i;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
828 j = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
829
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
830 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
831 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
832 long_comp tmp = sr[i_plus_j] + (long_comp)sa[j]*b + carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
833 sr[i_plus_j++] = (comp)tmp; /* downsize */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
834 carry = (comp)(tmp >> COMP_BIT_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
835 } while (++j < n);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
836
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
837 sr[i_plus_j] = carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
838 } while (++i < t);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
839
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
840 bi_free(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
841 bi_free(ctx, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
842 return trim(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
843 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
844
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
845 #ifdef CONFIG_BIGINT_KARATSUBA
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
846 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
847 * Karatsuba improves on regular multiplication due to only 3 multiplications
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
848 * being done instead of 4. The additional additions/subtractions are O(N)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
849 * rather than O(N^2) and so for big numbers it saves on a few operations
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
850 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
851 static bigint *karatsuba(BI_CTX *ctx, bigint *bia, bigint *bib, int is_square)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
852 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
853 bigint *x0, *x1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
854 bigint *p0, *p1, *p2;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
855 int m;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
856
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
857 if (is_square)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
858 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
859 m = (bia->size + 1)/2;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
860 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
861 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
862 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
863 m = (max(bia->size, bib->size) + 1)/2;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
864 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
865
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
866 x0 = bi_clone(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
867 x0->size = m;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
868 x1 = bi_clone(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
869 comp_right_shift(x1, m);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
870 bi_free(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
871
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
872 /* work out the 3 partial products */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
873 if (is_square)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
874 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
875 p0 = bi_square(ctx, bi_copy(x0));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
876 p2 = bi_square(ctx, bi_copy(x1));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
877 p1 = bi_square(ctx, bi_add(ctx, x0, x1));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
878 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
879 else /* normal multiply */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
880 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
881 bigint *y0, *y1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
882 y0 = bi_clone(ctx, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
883 y0->size = m;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
884 y1 = bi_clone(ctx, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
885 comp_right_shift(y1, m);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
886 bi_free(ctx, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
887
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
888 p0 = bi_multiply(ctx, bi_copy(x0), bi_copy(y0));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
889 p2 = bi_multiply(ctx, bi_copy(x1), bi_copy(y1));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
890 p1 = bi_multiply(ctx, bi_add(ctx, x0, x1), bi_add(ctx, y0, y1));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
891 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
892
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
893 p1 = bi_subtract(ctx,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
894 bi_subtract(ctx, p1, bi_copy(p2), NULL), bi_copy(p0), NULL);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
895
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
896 comp_left_shift(p1, m);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
897 comp_left_shift(p2, 2*m);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
898 return bi_add(ctx, p1, bi_add(ctx, p0, p2));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
899 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
900 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
901
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
902 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
903 * @brief Perform a multiplication operation between two bigints.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
904 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
905 * @param bia [in] A bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
906 * @param bib [in] Another bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
907 * @return The result of the multiplication.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
908 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
909 bigint *bi_multiply(BI_CTX *ctx, bigint *bia, bigint *bib)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
910 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
911 check(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
912 check(bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
913
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
914 #ifdef CONFIG_BIGINT_KARATSUBA
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
915 if (min(bia->size, bib->size) < MUL_KARATSUBA_THRESH)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
916 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
917 return regular_multiply(ctx, bia, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
918 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
919
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
920 return karatsuba(ctx, bia, bib, 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
921 #else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
922 return regular_multiply(ctx, bia, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
923 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
924 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
925
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
926 #ifdef CONFIG_BIGINT_SQUARE
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
927 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
928 * Perform the actual square operion. It takes into account overflow.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
929 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
930 static bigint *regular_square(BI_CTX *ctx, bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
931 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
932 int t = bi->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
933 int i = 0, j;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
934 bigint *biR = alloc(ctx, t*2);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
935 comp *w = biR->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
936 comp *x = bi->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
937 comp carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
938
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
939 memset(w, 0, biR->size*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
940
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
941 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
942 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
943 long_comp tmp = w[2*i] + (long_comp)x[i]*x[i];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
944 comp u = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
945 w[2*i] = (comp)tmp;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
946 carry = (comp)(tmp >> COMP_BIT_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
947
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
948 for (j = i+1; j < t; j++)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
949 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
950 long_comp xx = (long_comp)x[i]*x[j];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
951 long_comp xx2 = 2*xx;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
952 long_comp blob = (long_comp)w[i+j]+carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
953
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
954 if (u) /* previous overflow */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
955 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
956 blob += COMP_RADIX;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
957 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
958
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
959
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
960 u = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
961 tmp = xx2 + blob;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
962
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
963 /* check for overflow */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
964 if ((COMP_MAX-xx) < xx || (COMP_MAX-xx2) < blob)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
965 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
966 u = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
967 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
968
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
969 w[i+j] = (comp)tmp;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
970 carry = (comp)(tmp >> COMP_BIT_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
971 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
972
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
973 w[i+t] += carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
974
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
975 if (u)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
976 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
977 w[i+t+1] = 1; /* add carry */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
978 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
979 } while (++i < t);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
980
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
981 bi_free(ctx, bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
982 return trim(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
983 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
984
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
985 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
986 * @brief Perform a square operation on a bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
987 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
988 * @param bia [in] A bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
989 * @return The result of the multiplication.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
990 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
991 bigint *bi_square(BI_CTX *ctx, bigint *bia)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
992 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
993 check(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
994
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
995 #ifdef CONFIG_BIGINT_KARATSUBA
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
996 if (bia->size < SQU_KARATSUBA_THRESH)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
997 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
998 return regular_square(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
999 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1000
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1001 return karatsuba(ctx, bia, NULL, 1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1002 #else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1003 return regular_square(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1004 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1005 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1006 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1007
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1008 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1009 * @brief Compare two bigints.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1010 * @param bia [in] A bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1011 * @param bib [in] Another bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1012 * @return -1 if smaller, 1 if larger and 0 if equal.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1013 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1014 int bi_compare(bigint *bia, bigint *bib)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1015 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1016 int r, i;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1017
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1018 check(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1019 check(bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1020
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1021 if (bia->size > bib->size)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1022 r = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1023 else if (bia->size < bib->size)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1024 r = -1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1025 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1026 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1027 comp *a = bia->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1028 comp *b = bib->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1029
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1030 /* Same number of components. Compare starting from the high end
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1031 * and working down. */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1032 r = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1033 i = bia->size - 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1034
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1035 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1036 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1037 if (a[i] > b[i])
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1038 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1039 r = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1040 break;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1041 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1042 else if (a[i] < b[i])
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1043 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1044 r = -1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1045 break;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1046 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1047 } while (--i >= 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1048 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1049
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1050 return r;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1051 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1052
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1053 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1054 * Allocate and zero more components. Does not consume bi.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1055 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1056 static void more_comps(bigint *bi, int n)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1057 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1058 if (n > bi->max_comps)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1059 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1060 bi->max_comps = max(bi->max_comps * 2, n);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1061 bi->comps = (comp*)realloc(bi->comps, bi->max_comps * COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1062 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1063
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1064 if (n > bi->size)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1065 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1066 memset(&bi->comps[bi->size], 0, (n-bi->size)*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1067 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1068
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1069 bi->size = n;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1070 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1071
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1072 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1073 * Make a new empty bigint. It may just use an old one if one is available.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1074 * Otherwise get one off the heap.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1075 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1076 static bigint *alloc(BI_CTX *ctx, int size)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1077 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1078 bigint *biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1079
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1080 /* Can we recycle an old bigint? */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1081 if (ctx->free_list != NULL)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1082 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1083 biR = ctx->free_list;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1084 ctx->free_list = biR->next;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1085 ctx->free_count--;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1086
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1087 if (biR->refs != 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1088 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1089 #ifdef CONFIG_SSL_FULL_MODE
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1090 printf("alloc: refs was not 0\n");
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1091 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1092 abort(); /* create a stack trace from a core dump */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1093 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1094
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1095 more_comps(biR, size);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1096 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1097 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1098 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1099 /* No free bigints available - create a new one. */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1100 biR = (bigint *)malloc(sizeof(bigint));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1101 biR->comps = (comp*)malloc(size * COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1102 biR->max_comps = size; /* give some space to spare */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1103 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1104
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1105 biR->size = size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1106 biR->refs = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1107 biR->next = NULL;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1108 ctx->active_count++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1109 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1110 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1111
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1112 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1113 * Work out the highest '1' bit in an exponent. Used when doing sliding-window
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1114 * exponentiation.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1115 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1116 static int find_max_exp_index(bigint *biexp)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1117 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1118 int i = COMP_BIT_SIZE-1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1119 comp shift = COMP_RADIX/2;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1120 comp test = biexp->comps[biexp->size-1]; /* assume no leading zeroes */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1121
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1122 check(biexp);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1123
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1124 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1125 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1126 if (test & shift)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1127 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1128 return i+(biexp->size-1)*COMP_BIT_SIZE;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1129 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1130
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1131 shift >>= 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1132 } while (--i != 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1133
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1134 return -1; /* error - must have been a leading 0 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1135 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1136
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1137 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1138 * Is a particular bit is an exponent 1 or 0? Used when doing sliding-window
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1139 * exponentiation.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1140 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1141 static int exp_bit_is_one(bigint *biexp, int offset)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1142 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1143 comp test = biexp->comps[offset / COMP_BIT_SIZE];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1144 int num_shifts = offset % COMP_BIT_SIZE;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1145 comp shift = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1146 int i;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1147
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1148 check(biexp);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1149
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1150 for (i = 0; i < num_shifts; i++)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1151 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1152 shift <<= 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1153 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1154
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1155 return test & shift;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1156 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1157
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1158 #ifdef CONFIG_BIGINT_CHECK_ON
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1159 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1160 * Perform a sanity check on bi.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1161 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1162 static void check(const bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1163 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1164 if (bi->refs <= 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1165 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1166 printf("check: zero or negative refs in bigint\n");
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1167 abort();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1168 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1169
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1170 if (bi->next != NULL)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1171 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1172 printf("check: attempt to use a bigint from "
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1173 "the free list\n");
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1174 abort();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1175 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1176 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1177 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1178
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1179 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1180 * Delete any leading 0's (and allow for 0).
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1181 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1182 static bigint *trim(bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1183 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1184 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1185
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1186 while (bi->comps[bi->size-1] == 0 && bi->size > 1)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1187 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1188 bi->size--;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1189 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1190
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1191 return bi;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1192 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1193
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1194 #if defined(CONFIG_BIGINT_MONTGOMERY)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1195 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1196 * @brief Perform a single montgomery reduction.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1197 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1198 * @param bixy [in] A bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1199 * @return The result of the montgomery reduction.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1200 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1201 bigint *bi_mont(BI_CTX *ctx, bigint *bixy)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1202 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1203 int i = 0, n;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1204 uint8_t mod_offset = ctx->mod_offset;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1205 bigint *bim = ctx->bi_mod[mod_offset];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1206 comp mod_inv = ctx->N0_dash[mod_offset];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1207
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1208 check(bixy);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1209
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1210 if (ctx->use_classical) /* just use classical instead */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1211 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1212 return bi_mod(ctx, bixy);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1213 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1214
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1215 n = bim->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1216
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1217 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1218 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1219 bixy = bi_add(ctx, bixy, comp_left_shift(
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1220 bi_int_multiply(ctx, bim, bixy->comps[i]*mod_inv), i));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1221 } while (++i < n);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1222
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1223 comp_right_shift(bixy, n);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1224
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1225 if (bi_compare(bixy, bim) >= 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1226 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1227 bixy = bi_subtract(ctx, bixy, bim, NULL);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1228 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1229
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1230 return bixy;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1231 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1232
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1233 #elif defined(CONFIG_BIGINT_BARRETT)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1234 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1235 * Stomp on the most significant components to give the illusion of a "mod base
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1236 * radix" operation
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1237 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1238 static bigint *comp_mod(bigint *bi, int mod)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1239 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1240 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1241
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1242 if (bi->size > mod)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1243 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1244 bi->size = mod;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1245 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1246
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1247 return bi;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1248 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1249
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1250 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1251 * Barrett reduction has no need for some parts of the product, so ignore bits
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1252 * of the multiply. This routine gives Barrett its big performance
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1253 * improvements over Classical/Montgomery reduction methods.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1254 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1255 static bigint *partial_multiply(BI_CTX *ctx, bigint *bia, bigint *bib,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1256 int inner_partial, int outer_partial)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1257 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1258 int i = 0, j, n = bia->size, t = bib->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1259 bigint *biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1260 comp carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1261 comp *sr, *sa, *sb;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1262
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1263 check(bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1264 check(bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1265
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1266 biR = alloc(ctx, n + t);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1267 sa = bia->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1268 sb = bib->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1269 sr = biR->comps;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1270
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1271 if (inner_partial)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1272 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1273 memset(sr, 0, inner_partial*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1274 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1275 else /* outer partial */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1276 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1277 if (n < outer_partial || t < outer_partial) /* should we bother? */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1278 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1279 bi_free(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1280 bi_free(ctx, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1281 biR->comps[0] = 0; /* return 0 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1282 biR->size = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1283 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1284 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1285
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1286 memset(&sr[outer_partial], 0, (n+t-outer_partial)*COMP_BYTE_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1287 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1288
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1289 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1290 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1291 comp *a = sa;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1292 comp b = *sb++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1293 long_comp tmp;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1294 int i_plus_j = i;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1295 carry = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1296 j = n;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1297
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1298 if (outer_partial && i_plus_j < outer_partial)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1299 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1300 i_plus_j = outer_partial;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1301 a = &sa[outer_partial-i];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1302 j = n-(outer_partial-i);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1303 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1304
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1305 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1306 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1307 if (inner_partial && i_plus_j >= inner_partial)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1308 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1309 break;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1310 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1311
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1312 tmp = sr[i_plus_j] + ((long_comp)*a++)*b + carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1313 sr[i_plus_j++] = (comp)tmp; /* downsize */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1314 carry = (comp)(tmp >> COMP_BIT_SIZE);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1315 } while (--j != 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1316
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1317 sr[i_plus_j] = carry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1318 } while (++i < t);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1319
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1320 bi_free(ctx, bia);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1321 bi_free(ctx, bib);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1322 return trim(biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1323 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1324
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1325 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1326 * @brief Perform a single Barrett reduction.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1327 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1328 * @param bi [in] A bigint.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1329 * @return The result of the Barrett reduction.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1330 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1331 bigint *bi_barrett(BI_CTX *ctx, bigint *bi)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1332 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1333 bigint *q1, *q2, *q3, *r1, *r2, *r;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1334 uint8_t mod_offset = ctx->mod_offset;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1335 bigint *bim = ctx->bi_mod[mod_offset];
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1336 int k = bim->size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1337
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1338 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1339 check(bim);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1340
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1341 /* use Classical method instead - Barrett cannot help here */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1342 if (bi->size > k*2)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1343 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1344 return bi_mod(ctx, bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1345 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1346
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1347 q1 = comp_right_shift(bi_clone(ctx, bi), k-1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1348
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1349 /* do outer partial multiply */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1350 q2 = partial_multiply(ctx, q1, ctx->bi_mu[mod_offset], 0, k-1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1351 q3 = comp_right_shift(q2, k+1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1352 r1 = comp_mod(bi, k+1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1353
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1354 /* do inner partial multiply */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1355 r2 = comp_mod(partial_multiply(ctx, q3, bim, k+1, 0), k+1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1356 r = bi_subtract(ctx, r1, r2, NULL);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1357
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1358 /* if (r >= m) r = r - m; */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1359 if (bi_compare(r, bim) >= 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1360 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1361 r = bi_subtract(ctx, r, bim, NULL);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1362 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1363
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1364 return r;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1365 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1366 #endif /* CONFIG_BIGINT_BARRETT */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1367
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1368 #ifdef CONFIG_BIGINT_SLIDING_WINDOW
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1369 /*
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1370 * Work out g1, g3, g5, g7... etc for the sliding-window algorithm
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1371 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1372 static void precompute_slide_window(BI_CTX *ctx, int window, bigint *g1)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1373 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1374 int k = 1, i;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1375 bigint *g2;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1376
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1377 for (i = 0; i < window-1; i++) /* compute 2^(window-1) */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1378 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1379 k <<= 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1380 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1381
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1382 ctx->g = (bigint **)malloc(k*sizeof(bigint *));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1383 ctx->g[0] = bi_clone(ctx, g1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1384 bi_permanent(ctx->g[0]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1385 g2 = bi_residue(ctx, bi_square(ctx, ctx->g[0])); /* g^2 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1386
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1387 for (i = 1; i < k; i++)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1388 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1389 ctx->g[i] = bi_residue(ctx, bi_multiply(ctx, ctx->g[i-1], bi_copy(g2)));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1390 bi_permanent(ctx->g[i]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1391 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1392
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1393 bi_free(ctx, g2);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1394 ctx->window = k;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1395 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1396 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1397
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1398 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1399 * @brief Perform a modular exponentiation.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1400 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1401 * This function requires bi_set_mod() to have been called previously. This is
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1402 * one of the optimisations used for performance.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1403 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1404 * @param bi [in] The bigint on which to perform the mod power operation.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1405 * @param biexp [in] The bigint exponent.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1406 * @return The result of the mod exponentiation operation
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1407 * @see bi_set_mod().
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1408 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1409 bigint *bi_mod_power(BI_CTX *ctx, bigint *bi, bigint *biexp)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1410 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1411 int i = find_max_exp_index(biexp), j, window_size = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1412 bigint *biR = int_to_bi(ctx, 1);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1413
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1414 #if defined(CONFIG_BIGINT_MONTGOMERY)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1415 uint8_t mod_offset = ctx->mod_offset;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1416 if (!ctx->use_classical)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1417 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1418 /* preconvert */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1419 bi = bi_mont(ctx,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1420 bi_multiply(ctx, bi, ctx->bi_RR_mod_m[mod_offset])); /* x' */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1421 bi_free(ctx, biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1422 biR = ctx->bi_R_mod_m[mod_offset]; /* A */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1423 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1424 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1425
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1426 check(bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1427 check(biexp);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1428
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1429 #ifdef CONFIG_BIGINT_SLIDING_WINDOW
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1430 for (j = i; j > 32; j /= 5) /* work out an optimum size */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1431 window_size++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1432
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1433 /* work out the slide constants */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1434 precompute_slide_window(ctx, window_size, bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1435 #else /* just one constant */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1436 ctx->g = (bigint **)malloc(sizeof(bigint *));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1437 ctx->g[0] = bi_clone(ctx, bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1438 ctx->window = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1439 bi_permanent(ctx->g[0]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1440 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1441
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1442 /* if sliding-window is off, then only one bit will be done at a time and
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1443 * will reduce to standard left-to-right exponentiation */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1444 do
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1445 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1446 if (exp_bit_is_one(biexp, i))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1447 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1448 int l = i-window_size+1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1449 int part_exp = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1450
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1451 if (l < 0) /* LSB of exponent will always be 1 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1452 l = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1453 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1454 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1455 while (exp_bit_is_one(biexp, l) == 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1456 l++; /* go back up */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1457 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1458
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1459 /* build up the section of the exponent */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1460 for (j = i; j >= l; j--)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1461 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1462 biR = bi_residue(ctx, bi_square(ctx, biR));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1463 if (exp_bit_is_one(biexp, j))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1464 part_exp++;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1465
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1466 if (j != l)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1467 part_exp <<= 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1468 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1469
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1470 part_exp = (part_exp-1)/2; /* adjust for array */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1471 biR = bi_residue(ctx, bi_multiply(ctx, biR, ctx->g[part_exp]));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1472 i = l-1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1473 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1474 else /* square it */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1475 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1476 biR = bi_residue(ctx, bi_square(ctx, biR));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1477 i--;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1478 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1479 } while (i >= 0);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1480
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1481 /* cleanup */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1482 for (i = 0; i < ctx->window; i++)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1483 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1484 bi_depermanent(ctx->g[i]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1485 bi_free(ctx, ctx->g[i]);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1486 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1487
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1488 free(ctx->g);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1489 bi_free(ctx, bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1490 bi_free(ctx, biexp);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1491 #if defined CONFIG_BIGINT_MONTGOMERY
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1492 return ctx->use_classical ? biR : bi_mont(ctx, biR); /* convert back */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1493 #else /* CONFIG_BIGINT_CLASSICAL or CONFIG_BIGINT_BARRETT */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1494 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1495 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1496 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1497
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1498 #ifdef CONFIG_SSL_CERT_VERIFICATION
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1499 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1500 * @brief Perform a modular exponentiation using a temporary modulus.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1501 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1502 * We need this function to check the signatures of certificates. The modulus
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1503 * of this function is temporary as it's just used for authentication.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1504 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1505 * @param bi [in] The bigint to perform the exp/mod.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1506 * @param bim [in] The temporary modulus.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1507 * @param biexp [in] The bigint exponent.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1508 * @return The result of the mod exponentiation operation
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1509 * @see bi_set_mod().
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1510 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1511 bigint *bi_mod_power2(BI_CTX *ctx, bigint *bi, bigint *bim, bigint *biexp)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1512 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1513 bigint *biR, *tmp_biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1514
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1515 /* Set up a temporary bigint context and transfer what we need between
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1516 * them. We need to do this since we want to keep the original modulus
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1517 * which is already in this context. This operation is only called when
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1518 * doing peer verification, and so is not expensive :-) */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1519 BI_CTX *tmp_ctx = bi_initialize();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1520 bi_set_mod(tmp_ctx, bi_clone(tmp_ctx, bim), BIGINT_M_OFFSET);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1521 tmp_biR = bi_mod_power(tmp_ctx,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1522 bi_clone(tmp_ctx, bi),
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1523 bi_clone(tmp_ctx, biexp));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1524 biR = bi_clone(ctx, tmp_biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1525 bi_free(tmp_ctx, tmp_biR);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1526 bi_free_mod(tmp_ctx, BIGINT_M_OFFSET);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1527 bi_terminate(tmp_ctx);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1528
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1529 bi_free(ctx, bi);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1530 bi_free(ctx, bim);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1531 bi_free(ctx, biexp);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1532 return biR;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1533 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1534 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1535
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1536 #ifdef CONFIG_BIGINT_CRT
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1537 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1538 * @brief Use the Chinese Remainder Theorem to quickly perform RSA decrypts.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1539 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1540 * @param ctx [in] The bigint session context.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1541 * @param bi [in] The bigint to perform the exp/mod.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1542 * @param dP [in] CRT's dP bigint
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1543 * @param dQ [in] CRT's dQ bigint
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1544 * @param p [in] CRT's p bigint
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1545 * @param q [in] CRT's q bigint
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1546 * @param qInv [in] CRT's qInv bigint
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1547 * @return The result of the CRT operation
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1548 */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1549 bigint *bi_crt(BI_CTX *ctx, bigint *bi,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1550 bigint *dP, bigint *dQ,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1551 bigint *p, bigint *q, bigint *qInv)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1552 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1553 bigint *m1, *m2, *h;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1554
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1555 /* Montgomery has a condition the 0 < x, y < m and these products violate
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1556 * that condition. So disable Montgomery when using CRT */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1557 #if defined(CONFIG_BIGINT_MONTGOMERY)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1558 ctx->use_classical = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1559 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1560 ctx->mod_offset = BIGINT_P_OFFSET;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1561 m1 = bi_mod_power(ctx, bi_copy(bi), dP);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1562
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1563 ctx->mod_offset = BIGINT_Q_OFFSET;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1564 m2 = bi_mod_power(ctx, bi, dQ);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1565
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1566 h = bi_subtract(ctx, bi_add(ctx, m1, p), bi_copy(m2), NULL);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1567 h = bi_multiply(ctx, h, qInv);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1568 ctx->mod_offset = BIGINT_P_OFFSET;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1569 h = bi_residue(ctx, h);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1570 #if defined(CONFIG_BIGINT_MONTGOMERY)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1571 ctx->use_classical = 0; /* reset for any further operation */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1572 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1573 return bi_add(ctx, m2, bi_multiply(ctx, q, h));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1574 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1575 #endif
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1576 /** @} */