This is a fork of the mbed port of axTLS

Dependents:   TLS_axTLS-Example HTTPSClientExample

Overview

This library is a fork from the mbed port of axTLS. It attempts to :

  • reduce the usage of dynamic memory
  • verify certificates with key size up to 2048 bits
  • provide a simple interface

Encryption

This library uses either RC4 or AES for encryption.

Memory usage

During the establishment of a connection, about 10KB of memory is allocated dynamically (it depends on certificates). Once the connection is established, the memory consumption is relatively low. This means that your program must not use too much static memory or allocate memory before you establish a TLS connection.

Certificates

Certificates are the major source of problem and will often be the reason why your program will crash. Due to memory constraint, there are some limitations on certificates :

  • Each certificate must not be bigger than 2KB
  • TLS client can only handle a chain of up to three certificates (excluding the root certificate). This means that the server must not send more than three certificates.

Also, this library can only load certificates following these specifications :

  • encoded in binary DER format (PKCS1)
  • The public key must use RSA only

Once the connection is established, you should free all loaded certificates by calling CertificateManager::clear(). This will free a few kilobytes (it depends on your certificates). In addition, to enable certificate verification during the connection, this library has a "precomputed mode". This mode uses much less memory than a normal certificate verification.

Normal mode

You need to copy the root certificate in binary-DER format on the mbed. Then in your code, let's say that your root certificate is saved on the mbed as "root.der", assuming that you include CertificateManager.h and that you created a LocalFileSystem, you can load this certificate as this ;

Load root certificate

CertificateManager::add("/local/root.der");
CertificateManager::load();

Do not forget that this mode takes quite a lot of memory ( the memory peak is high while verifying certificates) and will only work if the key size is not bigger than 1024 bits (otherwise it will crash while verifying certificates).

Precomputed mode

In this mode, you need to save the entire chain of certificates (in binary-DER format) including the root certificate on the mbed. In practice, this means that you must first retrieve all certificates that the server sends during a connection and then find the right root certificate. In your code, you must call CertificateManager::add for each certificate and in the right order : from the server certificate to the root certificate. Here is how you shoud load certificates in this mode :

Loadcertificates in precomputed mode

CertificateManager::add("/local/server1.der");
CertificateManager::add("/local/server2.der");
CertificateManager::add("/local/server3.der");
CertificateManager::add("/local/root.der");
CertificateManager::load(true);

Using this mode, you should be able to verify certificates with key size up to 2048 bits.

How do I find these certificates ?

I posted an entry in my notebook detailing how to get certificates from a server. You should be able to get all certificates you need except the root certificate. Here is a way how to get the root certificate on windows :

  1. Open (double-click) the last certificate sent by the server
  2. Go to details panel and click on the entry called Issuer. The first line gives you the name of this certificate and the second line indicates the company who created this certificate
  3. Open firefox
  4. Go to options, advanced panel and click on View Certificates
  5. Go to Authorities panel
  6. Choose the certificate whose name match the issuer of the last certificate sent by the server
  7. Export this certificate to binary-DER format.

Connect to mbed.org !

Import programTLS_axTLS-Example

Establishing a connection to mbed.org using TLS

Committer:
feb11
Date:
Thu Sep 12 15:18:04 2013 +0000
Revision:
0:85fceccc1a7c
intial import

Who changed what in which revision?

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