Donatien Garnier / MiniTLS-GPL

A super trimmed down TLS stack, GPL licensed

Dependents:   MiniTLS-HTTPS-Example

MiniTLS - A super trimmed down TLS/SSL Library for embedded devices Author: Donatien Garnier Copyright (C) 2013-2014 AppNearMe Ltd

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

math/exptmod/fp_exptmod.c@4:cbaf466d717d, 2014-06-10 (annotated)

Committer:
MiniTLS
Date:
Tue Jun 10 14:23:09 2014 +0000
Revision:
4:cbaf466d717d
Parent:
0:35aa5be3b78d 
Fixes for mbed

Who changed what in which revision?

UserRevisionLine numberNew contents of line
MiniTLS 0:35aa5be3b78d 1 /* TomsFastMath, a fast ISO C bignum library.
MiniTLS 0:35aa5be3b78d 2 *
MiniTLS 0:35aa5be3b78d 3 * This project is meant to fill in where LibTomMath
MiniTLS 0:35aa5be3b78d 4 * falls short. That is speed ;-)
MiniTLS 0:35aa5be3b78d 5 *
MiniTLS 0:35aa5be3b78d 6 * This project is public domain and free for all purposes.
MiniTLS 0:35aa5be3b78d 7 *
MiniTLS 0:35aa5be3b78d 8 * Tom St Denis, tomstdenis@gmail.com
MiniTLS 0:35aa5be3b78d 9 */
MiniTLS 0:35aa5be3b78d 10 #include <tfm.h>
MiniTLS 0:35aa5be3b78d 11
MiniTLS 0:35aa5be3b78d 12 #ifdef TFM_TIMING_RESISTANT
MiniTLS 0:35aa5be3b78d 13
MiniTLS 0:35aa5be3b78d 14 /* timing resistant montgomery ladder based exptmod
MiniTLS 0:35aa5be3b78d 15
MiniTLS 0:35aa5be3b78d 16 Based on work by Marc Joye, Sung-Ming Yen, "The Montgomery Powering Ladder", Cryptographic Hardware and Embedded Systems, CHES 2002
MiniTLS 0:35aa5be3b78d 17 */
MiniTLS 0:35aa5be3b78d 18 static int _fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
MiniTLS 0:35aa5be3b78d 19 {
MiniTLS 0:35aa5be3b78d 20 fp_int R[2];
MiniTLS 0:35aa5be3b78d 21 fp_digit buf, mp;
MiniTLS 0:35aa5be3b78d 22 int err, bitcnt, digidx, y;
MiniTLS 0:35aa5be3b78d 23
MiniTLS 0:35aa5be3b78d 24 /* now setup montgomery */
MiniTLS 0:35aa5be3b78d 25 if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
MiniTLS 0:35aa5be3b78d 26 return err;
MiniTLS 0:35aa5be3b78d 27 }
MiniTLS 0:35aa5be3b78d 28
MiniTLS 0:35aa5be3b78d 29 fp_init(&R[0]);
MiniTLS 0:35aa5be3b78d 30 fp_init(&R[1]);
MiniTLS 0:35aa5be3b78d 31
MiniTLS 0:35aa5be3b78d 32 /* now we need R mod m */
MiniTLS 0:35aa5be3b78d 33 fp_montgomery_calc_normalization (&R[0], P);
MiniTLS 0:35aa5be3b78d 34
MiniTLS 0:35aa5be3b78d 35 /* now set R[0][1] to G * R mod m */
MiniTLS 0:35aa5be3b78d 36 if (fp_cmp_mag(P, G) != FP_GT) {
MiniTLS 0:35aa5be3b78d 37 /* G > P so we reduce it first */
MiniTLS 0:35aa5be3b78d 38 fp_mod(G, P, &R[1]);
MiniTLS 0:35aa5be3b78d 39 } else {
MiniTLS 0:35aa5be3b78d 40 fp_copy(G, &R[1]);
MiniTLS 0:35aa5be3b78d 41 }
MiniTLS 0:35aa5be3b78d 42 fp_mulmod (&R[1], &R[0], P, &R[1]);
MiniTLS 0:35aa5be3b78d 43
MiniTLS 0:35aa5be3b78d 44 /* for j = t-1 downto 0 do
MiniTLS 0:35aa5be3b78d 45 r_!k = R0*R1; r_k = r_k^2
MiniTLS 0:35aa5be3b78d 46 */
MiniTLS 0:35aa5be3b78d 47
MiniTLS 0:35aa5be3b78d 48 /* set initial mode and bit cnt */
MiniTLS 0:35aa5be3b78d 49 bitcnt = 1;
MiniTLS 0:35aa5be3b78d 50 buf = 0;
MiniTLS 0:35aa5be3b78d 51 digidx = X->used - 1;
MiniTLS 0:35aa5be3b78d 52
MiniTLS 0:35aa5be3b78d 53 for (;;) {
MiniTLS 0:35aa5be3b78d 54 /* grab next digit as required */
MiniTLS 0:35aa5be3b78d 55 if (--bitcnt == 0) {
MiniTLS 0:35aa5be3b78d 56 /* if digidx == -1 we are out of digits so break */
MiniTLS 0:35aa5be3b78d 57 if (digidx == -1) {
MiniTLS 0:35aa5be3b78d 58 break;
MiniTLS 0:35aa5be3b78d 59 }
MiniTLS 0:35aa5be3b78d 60 /* read next digit and reset bitcnt */
MiniTLS 0:35aa5be3b78d 61 buf = X->dp[digidx--];
MiniTLS 0:35aa5be3b78d 62 bitcnt = (int)DIGIT_BIT;
MiniTLS 0:35aa5be3b78d 63 }
MiniTLS 0:35aa5be3b78d 64
MiniTLS 0:35aa5be3b78d 65 /* grab the next msb from the exponent */
MiniTLS 0:35aa5be3b78d 66 y = (fp_digit)(buf >> (DIGIT_BIT - 1)) & 1;
MiniTLS 0:35aa5be3b78d 67 buf <<= (fp_digit)1;
MiniTLS 0:35aa5be3b78d 68
MiniTLS 0:35aa5be3b78d 69 /* do ops */
MiniTLS 0:35aa5be3b78d 70 fp_mul(&R[0], &R[1], &R[y^1]); fp_montgomery_reduce(&R[y^1], P, mp);
MiniTLS 0:35aa5be3b78d 71 fp_sqr(&R[y], &R[y]); fp_montgomery_reduce(&R[y], P, mp);
MiniTLS 0:35aa5be3b78d 72 }
MiniTLS 0:35aa5be3b78d 73
MiniTLS 0:35aa5be3b78d 74 fp_montgomery_reduce(&R[0], P, mp);
MiniTLS 0:35aa5be3b78d 75 fp_copy(&R[0], Y);
MiniTLS 0:35aa5be3b78d 76 return FP_OKAY;
MiniTLS 0:35aa5be3b78d 77 }
MiniTLS 0:35aa5be3b78d 78
MiniTLS 0:35aa5be3b78d 79 #else
MiniTLS 0:35aa5be3b78d 80
MiniTLS 0:35aa5be3b78d 81 /* y = g**x (mod b)
MiniTLS 0:35aa5be3b78d 82 * Some restrictions... x must be positive and < b
MiniTLS 0:35aa5be3b78d 83 */
MiniTLS 0:35aa5be3b78d 84 static int _fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
MiniTLS 0:35aa5be3b78d 85 {
MiniTLS 0:35aa5be3b78d 86 fp_int M[64], res;
MiniTLS 0:35aa5be3b78d 87 fp_digit buf, mp;
MiniTLS 0:35aa5be3b78d 88 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
MiniTLS 0:35aa5be3b78d 89
MiniTLS 0:35aa5be3b78d 90 /* find window size */
MiniTLS 0:35aa5be3b78d 91 x = fp_count_bits (X);
MiniTLS 0:35aa5be3b78d 92 if (x <= 21) {
MiniTLS 0:35aa5be3b78d 93 winsize = 1;
MiniTLS 0:35aa5be3b78d 94 } else if (x <= 36) {
MiniTLS 0:35aa5be3b78d 95 winsize = 3;
MiniTLS 0:35aa5be3b78d 96 } else if (x <= 140) {
MiniTLS 0:35aa5be3b78d 97 winsize = 4;
MiniTLS 0:35aa5be3b78d 98 } else if (x <= 450) {
MiniTLS 0:35aa5be3b78d 99 winsize = 5;
MiniTLS 0:35aa5be3b78d 100 } else {
MiniTLS 0:35aa5be3b78d 101 winsize = 6;
MiniTLS 0:35aa5be3b78d 102 }
MiniTLS 0:35aa5be3b78d 103
MiniTLS 0:35aa5be3b78d 104 /* init M array */
MiniTLS 0:35aa5be3b78d 105 memset(M, 0, sizeof(M));
MiniTLS 0:35aa5be3b78d 106
MiniTLS 0:35aa5be3b78d 107 /* now setup montgomery */
MiniTLS 0:35aa5be3b78d 108 if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
MiniTLS 0:35aa5be3b78d 109 return err;
MiniTLS 0:35aa5be3b78d 110 }
MiniTLS 0:35aa5be3b78d 111
MiniTLS 0:35aa5be3b78d 112 /* setup result */
MiniTLS 0:35aa5be3b78d 113 fp_init(&res);
MiniTLS 0:35aa5be3b78d 114
MiniTLS 0:35aa5be3b78d 115 /* create M table
MiniTLS 0:35aa5be3b78d 116 *
MiniTLS 0:35aa5be3b78d 117 * The M table contains powers of the input base, e.g. M[x] = G^x mod P
MiniTLS 0:35aa5be3b78d 118 *
MiniTLS 0:35aa5be3b78d 119 * The first half of the table is not computed though accept for M[0] and M[1]
MiniTLS 0:35aa5be3b78d 120 */
MiniTLS 0:35aa5be3b78d 121
MiniTLS 0:35aa5be3b78d 122 /* now we need R mod m */
MiniTLS 0:35aa5be3b78d 123 fp_montgomery_calc_normalization (&res, P);
MiniTLS 0:35aa5be3b78d 124
MiniTLS 0:35aa5be3b78d 125 /* now set M[1] to G * R mod m */
MiniTLS 0:35aa5be3b78d 126 if (fp_cmp_mag(P, G) != FP_GT) {
MiniTLS 0:35aa5be3b78d 127 /* G > P so we reduce it first */
MiniTLS 0:35aa5be3b78d 128 fp_mod(G, P, &M[1]);
MiniTLS 0:35aa5be3b78d 129 } else {
MiniTLS 0:35aa5be3b78d 130 fp_copy(G, &M[1]);
MiniTLS 0:35aa5be3b78d 131 }
MiniTLS 0:35aa5be3b78d 132 fp_mulmod (&M[1], &res, P, &M[1]);
MiniTLS 0:35aa5be3b78d 133
MiniTLS 0:35aa5be3b78d 134 /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */
MiniTLS 0:35aa5be3b78d 135 fp_copy (&M[1], &M[1 << (winsize - 1)]);
MiniTLS 0:35aa5be3b78d 136 for (x = 0; x < (winsize - 1); x++) {
MiniTLS 0:35aa5be3b78d 137 fp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)]);
MiniTLS 0:35aa5be3b78d 138 fp_montgomery_reduce (&M[1 << (winsize - 1)], P, mp);
MiniTLS 0:35aa5be3b78d 139 }
MiniTLS 0:35aa5be3b78d 140
MiniTLS 0:35aa5be3b78d 141 /* create upper table */
MiniTLS 0:35aa5be3b78d 142 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
MiniTLS 0:35aa5be3b78d 143 fp_mul(&M[x - 1], &M[1], &M[x]);
MiniTLS 0:35aa5be3b78d 144 fp_montgomery_reduce(&M[x], P, mp);
MiniTLS 0:35aa5be3b78d 145 }
MiniTLS 0:35aa5be3b78d 146
MiniTLS 0:35aa5be3b78d 147 /* set initial mode and bit cnt */
MiniTLS 0:35aa5be3b78d 148 mode = 0;
MiniTLS 0:35aa5be3b78d 149 bitcnt = 1;
MiniTLS 0:35aa5be3b78d 150 buf = 0;
MiniTLS 0:35aa5be3b78d 151 digidx = X->used - 1;
MiniTLS 0:35aa5be3b78d 152 bitcpy = 0;
MiniTLS 0:35aa5be3b78d 153 bitbuf = 0;
MiniTLS 0:35aa5be3b78d 154
MiniTLS 0:35aa5be3b78d 155 for (;;) {
MiniTLS 0:35aa5be3b78d 156 /* grab next digit as required */
MiniTLS 0:35aa5be3b78d 157 if (--bitcnt == 0) {
MiniTLS 0:35aa5be3b78d 158 /* if digidx == -1 we are out of digits so break */
MiniTLS 0:35aa5be3b78d 159 if (digidx == -1) {
MiniTLS 0:35aa5be3b78d 160 break;
MiniTLS 0:35aa5be3b78d 161 }
MiniTLS 0:35aa5be3b78d 162 /* read next digit and reset bitcnt */
MiniTLS 0:35aa5be3b78d 163 buf = X->dp[digidx--];
MiniTLS 0:35aa5be3b78d 164 bitcnt = (int)DIGIT_BIT;
MiniTLS 0:35aa5be3b78d 165 }
MiniTLS 0:35aa5be3b78d 166
MiniTLS 0:35aa5be3b78d 167 /* grab the next msb from the exponent */
MiniTLS 0:35aa5be3b78d 168 y = (fp_digit)(buf >> (DIGIT_BIT - 1)) & 1;
MiniTLS 0:35aa5be3b78d 169 buf <<= (fp_digit)1;
MiniTLS 0:35aa5be3b78d 170
MiniTLS 0:35aa5be3b78d 171 /* if the bit is zero and mode == 0 then we ignore it
MiniTLS 0:35aa5be3b78d 172 * These represent the leading zero bits before the first 1 bit
MiniTLS 0:35aa5be3b78d 173 * in the exponent. Technically this opt is not required but it
MiniTLS 0:35aa5be3b78d 174 * does lower the # of trivial squaring/reductions used
MiniTLS 0:35aa5be3b78d 175 */
MiniTLS 0:35aa5be3b78d 176 if (mode == 0 && y == 0) {
MiniTLS 0:35aa5be3b78d 177 continue;
MiniTLS 0:35aa5be3b78d 178 }
MiniTLS 0:35aa5be3b78d 179
MiniTLS 0:35aa5be3b78d 180 /* if the bit is zero and mode == 1 then we square */
MiniTLS 0:35aa5be3b78d 181 if (mode == 1 && y == 0) {
MiniTLS 0:35aa5be3b78d 182 fp_sqr(&res, &res);
MiniTLS 0:35aa5be3b78d 183 fp_montgomery_reduce(&res, P, mp);
MiniTLS 0:35aa5be3b78d 184 continue;
MiniTLS 0:35aa5be3b78d 185 }
MiniTLS 0:35aa5be3b78d 186
MiniTLS 0:35aa5be3b78d 187 /* else we add it to the window */
MiniTLS 0:35aa5be3b78d 188 bitbuf |= (y << (winsize - ++bitcpy));
MiniTLS 0:35aa5be3b78d 189 mode = 2;
MiniTLS 0:35aa5be3b78d 190
MiniTLS 0:35aa5be3b78d 191 if (bitcpy == winsize) {
MiniTLS 0:35aa5be3b78d 192 /* ok window is filled so square as required and multiply */
MiniTLS 0:35aa5be3b78d 193 /* square first */
MiniTLS 0:35aa5be3b78d 194 for (x = 0; x < winsize; x++) {
MiniTLS 0:35aa5be3b78d 195 fp_sqr(&res, &res);
MiniTLS 0:35aa5be3b78d 196 fp_montgomery_reduce(&res, P, mp);
MiniTLS 0:35aa5be3b78d 197 }
MiniTLS 0:35aa5be3b78d 198
MiniTLS 0:35aa5be3b78d 199 /* then multiply */
MiniTLS 0:35aa5be3b78d 200 fp_mul(&res, &M[bitbuf], &res);
MiniTLS 0:35aa5be3b78d 201 fp_montgomery_reduce(&res, P, mp);
MiniTLS 0:35aa5be3b78d 202
MiniTLS 0:35aa5be3b78d 203 /* empty window and reset */
MiniTLS 0:35aa5be3b78d 204 bitcpy = 0;
MiniTLS 0:35aa5be3b78d 205 bitbuf = 0;
MiniTLS 0:35aa5be3b78d 206 mode = 1;
MiniTLS 0:35aa5be3b78d 207 }
MiniTLS 0:35aa5be3b78d 208 }
MiniTLS 0:35aa5be3b78d 209
MiniTLS 0:35aa5be3b78d 210 /* if bits remain then square/multiply */
MiniTLS 0:35aa5be3b78d 211 if (mode == 2 && bitcpy > 0) {
MiniTLS 0:35aa5be3b78d 212 /* square then multiply if the bit is set */
MiniTLS 0:35aa5be3b78d 213 for (x = 0; x < bitcpy; x++) {
MiniTLS 0:35aa5be3b78d 214 fp_sqr(&res, &res);
MiniTLS 0:35aa5be3b78d 215 fp_montgomery_reduce(&res, P, mp);
MiniTLS 0:35aa5be3b78d 216
MiniTLS 0:35aa5be3b78d 217 /* get next bit of the window */
MiniTLS 0:35aa5be3b78d 218 bitbuf <<= 1;
MiniTLS 0:35aa5be3b78d 219 if ((bitbuf & (1 << winsize)) != 0) {
MiniTLS 0:35aa5be3b78d 220 /* then multiply */
MiniTLS 0:35aa5be3b78d 221 fp_mul(&res, &M[1], &res);
MiniTLS 0:35aa5be3b78d 222 fp_montgomery_reduce(&res, P, mp);
MiniTLS 0:35aa5be3b78d 223 }
MiniTLS 0:35aa5be3b78d 224 }
MiniTLS 0:35aa5be3b78d 225 }
MiniTLS 0:35aa5be3b78d 226
MiniTLS 0:35aa5be3b78d 227 /* fixup result if Montgomery reduction is used
MiniTLS 0:35aa5be3b78d 228 * recall that any value in a Montgomery system is
MiniTLS 0:35aa5be3b78d 229 * actually multiplied by R mod n. So we have
MiniTLS 0:35aa5be3b78d 230 * to reduce one more time to cancel out the factor
MiniTLS 0:35aa5be3b78d 231 * of R.
MiniTLS 0:35aa5be3b78d 232 */
MiniTLS 0:35aa5be3b78d 233 fp_montgomery_reduce(&res, P, mp);
MiniTLS 0:35aa5be3b78d 234
MiniTLS 0:35aa5be3b78d 235 /* swap res with Y */
MiniTLS 0:35aa5be3b78d 236 fp_copy (&res, Y);
MiniTLS 0:35aa5be3b78d 237 return FP_OKAY;
MiniTLS 0:35aa5be3b78d 238 }
MiniTLS 0:35aa5be3b78d 239
MiniTLS 0:35aa5be3b78d 240 #endif
MiniTLS 0:35aa5be3b78d 241
MiniTLS 0:35aa5be3b78d 242
MiniTLS 0:35aa5be3b78d 243 int fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
MiniTLS 0:35aa5be3b78d 244 {
MiniTLS 0:35aa5be3b78d 245 fp_int tmp;
MiniTLS 0:35aa5be3b78d 246 int err;
MiniTLS 0:35aa5be3b78d 247
MiniTLS 0:35aa5be3b78d 248 #ifdef TFM_CHECK
MiniTLS 0:35aa5be3b78d 249 /* prevent overflows */
MiniTLS 0:35aa5be3b78d 250 if (P->used > (FP_SIZE/2)) {
MiniTLS 0:35aa5be3b78d 251 return FP_VAL;
MiniTLS 0:35aa5be3b78d 252 }
MiniTLS 0:35aa5be3b78d 253 #endif
MiniTLS 0:35aa5be3b78d 254
MiniTLS 0:35aa5be3b78d 255 /* is X negative? */
MiniTLS 0:35aa5be3b78d 256 if (X->sign == FP_NEG) {
MiniTLS 0:35aa5be3b78d 257 /* yes, copy G and invmod it */
MiniTLS 0:35aa5be3b78d 258 fp_copy(G, &tmp);
MiniTLS 0:35aa5be3b78d 259 if ((err = fp_invmod(&tmp, P, &tmp)) != FP_OKAY) {
MiniTLS 0:35aa5be3b78d 260 return err;
MiniTLS 0:35aa5be3b78d 261 }
MiniTLS 0:35aa5be3b78d 262 X->sign = FP_ZPOS;
MiniTLS 0:35aa5be3b78d 263 err = _fp_exptmod(&tmp, X, P, Y);
MiniTLS 0:35aa5be3b78d 264 if (X != Y) {
MiniTLS 0:35aa5be3b78d 265 X->sign = FP_NEG;
MiniTLS 0:35aa5be3b78d 266 }
MiniTLS 0:35aa5be3b78d 267 return err;
MiniTLS 0:35aa5be3b78d 268 } else {
MiniTLS 0:35aa5be3b78d 269 /* Positive exponent so just exptmod */
MiniTLS 0:35aa5be3b78d 270 return _fp_exptmod(G, X, P, Y);
MiniTLS 0:35aa5be3b78d 271 }
MiniTLS 0:35aa5be3b78d 272 }
MiniTLS 0:35aa5be3b78d 273
MiniTLS 0:35aa5be3b78d 274 /* $Source: /cvs/libtom/tomsfastmath/src/exptmod/fp_exptmod.c,v $ */
MiniTLS 0:35aa5be3b78d 275 /* $Revision: 1.1 $ */
MiniTLS 0:35aa5be3b78d 276 /* $Date: 2006/12/31 21:25:53 $ */