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.

crypto/ltc/ltc_ecc_mulmod_timing.c@4:cbaf466d717d, 2014-06-10 (annotated)

Committer:
MiniTLS
Date:
Tue Jun 10 14:23:09 2014 +0000
Revision:
4:cbaf466d717d
Parent:
2:527a66d0a1a9 
Fixes for mbed

Who changed what in which revision?

UserRevisionLine numberNew contents of line
MiniTLS 2:527a66d0a1a9 1 /*
MiniTLS 2:527a66d0a1a9 2 MiniTLS - A super trimmed down TLS/SSL Library for embedded devices
MiniTLS 2:527a66d0a1a9 3 Author: Donatien Garnier
MiniTLS 2:527a66d0a1a9 4 Copyright (C) 2013-2014 AppNearMe Ltd
MiniTLS 2:527a66d0a1a9 5
MiniTLS 2:527a66d0a1a9 6 This program is free software; you can redistribute it and/or
MiniTLS 2:527a66d0a1a9 7 modify it under the terms of the GNU General Public License
MiniTLS 2:527a66d0a1a9 8 as published by the Free Software Foundation; either version 2
MiniTLS 2:527a66d0a1a9 9 of the License, or (at your option) any later version.
MiniTLS 2:527a66d0a1a9 10
MiniTLS 2:527a66d0a1a9 11 This program is distributed in the hope that it will be useful,
MiniTLS 2:527a66d0a1a9 12 but WITHOUT ANY WARRANTY; without even the implied warranty of
MiniTLS 2:527a66d0a1a9 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
MiniTLS 2:527a66d0a1a9 14 GNU General Public License for more details.
MiniTLS 2:527a66d0a1a9 15
MiniTLS 2:527a66d0a1a9 16 You should have received a copy of the GNU General Public License
MiniTLS 2:527a66d0a1a9 17 along with this program; if not, write to the Free Software
MiniTLS 2:527a66d0a1a9 18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
MiniTLS 2:527a66d0a1a9 19 *//* LibTomCrypt, modular cryptographic library -- Tom St Denis
MiniTLS 2:527a66d0a1a9 20 *
MiniTLS 2:527a66d0a1a9 21 * LibTomCrypt is a library that provides various cryptographic
MiniTLS 2:527a66d0a1a9 22 * algorithms in a highly modular and flexible manner.
MiniTLS 2:527a66d0a1a9 23 *
MiniTLS 2:527a66d0a1a9 24 * The library is free for all purposes without any express
MiniTLS 2:527a66d0a1a9 25 * guarantee it works.
MiniTLS 2:527a66d0a1a9 26 *
MiniTLS 2:527a66d0a1a9 27 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
MiniTLS 2:527a66d0a1a9 28 */
MiniTLS 2:527a66d0a1a9 29
MiniTLS 2:527a66d0a1a9 30 /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
MiniTLS 2:527a66d0a1a9 31 *
MiniTLS 2:527a66d0a1a9 32 * All curves taken from NIST recommendation paper of July 1999
MiniTLS 2:527a66d0a1a9 33 * Available at http://csrc.nist.gov/cryptval/dss.htm
MiniTLS 2:527a66d0a1a9 34 */
MiniTLS 2:527a66d0a1a9 35 #include "ltc.h"
MiniTLS 2:527a66d0a1a9 36
MiniTLS 2:527a66d0a1a9 37 /**
MiniTLS 2:527a66d0a1a9 38 @file ltc_ecc_mulmod_timing.c
MiniTLS 2:527a66d0a1a9 39 ECC Crypto, Tom St Denis
MiniTLS 2:527a66d0a1a9 40 */
MiniTLS 2:527a66d0a1a9 41
MiniTLS 2:527a66d0a1a9 42 #ifdef LTC_MECC
MiniTLS 2:527a66d0a1a9 43
MiniTLS 2:527a66d0a1a9 44 #ifdef LTC_ECC_TIMING_RESISTANT
MiniTLS 2:527a66d0a1a9 45
MiniTLS 2:527a66d0a1a9 46 /**
MiniTLS 2:527a66d0a1a9 47 Perform a point multiplication (timing resistant)
MiniTLS 2:527a66d0a1a9 48 @param k The scalar to multiply by
MiniTLS 2:527a66d0a1a9 49 @param G The base point
MiniTLS 2:527a66d0a1a9 50 @param R [out] Destination for kG
MiniTLS 2:527a66d0a1a9 51 @param modulus The modulus of the field the ECC curve is in
MiniTLS 2:527a66d0a1a9 52 @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
MiniTLS 2:527a66d0a1a9 53 @return MINITLS_OK on success
MiniTLS 2:527a66d0a1a9 54 */
MiniTLS 2:527a66d0a1a9 55 int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map)
MiniTLS 2:527a66d0a1a9 56 {
MiniTLS 2:527a66d0a1a9 57 ecc_point tG, M[3];
MiniTLS 2:527a66d0a1a9 58 int i, j, err;
MiniTLS 2:527a66d0a1a9 59 fp_int mu;
MiniTLS 2:527a66d0a1a9 60 fp_digit mp;
MiniTLS 2:527a66d0a1a9 61 unsigned long buf;
MiniTLS 2:527a66d0a1a9 62 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
MiniTLS 2:527a66d0a1a9 63
MiniTLS 2:527a66d0a1a9 64 LTC_ARGCHK(k != NULL);
MiniTLS 2:527a66d0a1a9 65 LTC_ARGCHK(G != NULL);
MiniTLS 2:527a66d0a1a9 66 LTC_ARGCHK(R != NULL);
MiniTLS 2:527a66d0a1a9 67 LTC_ARGCHK(modulus != NULL);
MiniTLS 2:527a66d0a1a9 68
MiniTLS 2:527a66d0a1a9 69 /* init montgomery reduction */
MiniTLS 2:527a66d0a1a9 70 if ((err = mp_montgomery_setup(modulus, &mp)) != MINITLS_OK) {
MiniTLS 2:527a66d0a1a9 71 return err;
MiniTLS 2:527a66d0a1a9 72 }
MiniTLS 2:527a66d0a1a9 73 /*if ((err =*/ mp_init(&mu);/*) != MINITLS_OK) {
MiniTLS 2:527a66d0a1a9 74 mp_montgomery_free(&mp);
MiniTLS 2:527a66d0a1a9 75 return err;
MiniTLS 2:527a66d0a1a9 76 }*/
MiniTLS 2:527a66d0a1a9 77 /*if ((err =*/ mp_montgomery_normalization(&mu, modulus);/*) != MINITLS_OK) {
MiniTLS 2:527a66d0a1a9 78 mp_clear(&mu);
MiniTLS 2:527a66d0a1a9 79 mp_montgomery_free(&mp);
MiniTLS 2:527a66d0a1a9 80 return err;
MiniTLS 2:527a66d0a1a9 81 }*/
MiniTLS 2:527a66d0a1a9 82
MiniTLS 2:527a66d0a1a9 83 /* alloc ram for window temps */
MiniTLS 2:527a66d0a1a9 84 for (i = 0; i < 3; i++) {
MiniTLS 2:527a66d0a1a9 85 if (mp_init_multi(&M[i].x, &M[i].y, &M[i].z, NULL) != MINITLS_OK)
MiniTLS 2:527a66d0a1a9 86 {
MiniTLS 2:527a66d0a1a9 87 for (j = 0; j < i; j++) {
MiniTLS 2:527a66d0a1a9 88 mp_clear_multi(&M[j].x, &M[j].y, &M[j].z, NULL);
MiniTLS 2:527a66d0a1a9 89 }
MiniTLS 2:527a66d0a1a9 90 mp_clear(&mu);
MiniTLS 2:527a66d0a1a9 91 mp_montgomery_free(&mp);
MiniTLS 2:527a66d0a1a9 92 return MINITLS_ERR_MEMORY;
MiniTLS 2:527a66d0a1a9 93 }
MiniTLS 2:527a66d0a1a9 94 }
MiniTLS 2:527a66d0a1a9 95
MiniTLS 2:527a66d0a1a9 96 /* make a copy of G incase R==G */
MiniTLS 2:527a66d0a1a9 97 if (mp_init_multi(&tG.x, &tG.y, &tG.z, NULL) != MINITLS_OK) { err = MINITLS_ERR_MEMORY; goto done; }
MiniTLS 2:527a66d0a1a9 98
MiniTLS 2:527a66d0a1a9 99 /* tG = G and convert to montgomery */
MiniTLS 2:527a66d0a1a9 100 if ((err = mp_mulmod(&G->x, &mu, modulus, &tG.x)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 101 if ((err = mp_mulmod(&G->y, &mu, modulus, &tG.y)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 102 if ((err = mp_mulmod(&G->z, &mu, modulus, &tG.z)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 103 mp_clear(&mu);
MiniTLS 2:527a66d0a1a9 104 //mu = NULL;
MiniTLS 2:527a66d0a1a9 105
MiniTLS 2:527a66d0a1a9 106 /* calc the M tab */
MiniTLS 2:527a66d0a1a9 107 /* M[0] == G */
MiniTLS 2:527a66d0a1a9 108 /*if ((err =*/ mp_copy(&tG.x, &M[0].x); /*) != MINITLS_OK) { goto done; }*/
MiniTLS 2:527a66d0a1a9 109 /*if ((err =*/ mp_copy(&tG.y, &M[0].y); /*) != MINITLS_OK) { goto done; }*/
MiniTLS 2:527a66d0a1a9 110 /*if ((err =*/ mp_copy(&tG.z, &M[0].z); /*) != MINITLS_OK) { goto done; }*/
MiniTLS 2:527a66d0a1a9 111 /* M[1] == 2G */
MiniTLS 2:527a66d0a1a9 112 if ((err = ltc_ecc_projective_dbl_point(&tG, &M[1], modulus, &mp)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 113
MiniTLS 2:527a66d0a1a9 114 /* setup sliding window */
MiniTLS 2:527a66d0a1a9 115 mode = 0;
MiniTLS 2:527a66d0a1a9 116 bitcnt = 1;
MiniTLS 2:527a66d0a1a9 117 buf = 0;
MiniTLS 2:527a66d0a1a9 118 digidx = mp_get_digit_count(k) - 1;
MiniTLS 2:527a66d0a1a9 119 bitcpy = bitbuf = 0;
MiniTLS 2:527a66d0a1a9 120 first = 1;
MiniTLS 2:527a66d0a1a9 121
MiniTLS 2:527a66d0a1a9 122 /* perform ops */
MiniTLS 2:527a66d0a1a9 123 for (;;) {
MiniTLS 2:527a66d0a1a9 124 /* grab next digit as required */
MiniTLS 2:527a66d0a1a9 125 if (--bitcnt == 0) {
MiniTLS 2:527a66d0a1a9 126 if (digidx == -1) {
MiniTLS 2:527a66d0a1a9 127 break;
MiniTLS 2:527a66d0a1a9 128 }
MiniTLS 2:527a66d0a1a9 129 buf = mp_get_digit(k, digidx);
MiniTLS 2:527a66d0a1a9 130 bitcnt = (int) MP_DIGIT_BIT;
MiniTLS 2:527a66d0a1a9 131 --digidx;
MiniTLS 2:527a66d0a1a9 132 }
MiniTLS 2:527a66d0a1a9 133
MiniTLS 2:527a66d0a1a9 134 /* grab the next msb from the ltiplicand */
MiniTLS 2:527a66d0a1a9 135 i = (buf >> (MP_DIGIT_BIT - 1)) & 1;
MiniTLS 2:527a66d0a1a9 136 buf <<= 1;
MiniTLS 2:527a66d0a1a9 137
MiniTLS 2:527a66d0a1a9 138 if (mode == 0 && i == 0) {
MiniTLS 2:527a66d0a1a9 139 /* dummy operations */
MiniTLS 2:527a66d0a1a9 140 if ((err = ltc_ecc_projective_add_point(&M[0], &M[1], &M[2], modulus, &mp)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 141 if ((err = ltc_ecc_projective_dbl_point(&M[1], &M[2], modulus, &mp)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 142 continue;
MiniTLS 2:527a66d0a1a9 143 }
MiniTLS 2:527a66d0a1a9 144
MiniTLS 2:527a66d0a1a9 145 if (mode == 0 && i == 1) {
MiniTLS 2:527a66d0a1a9 146 mode = 1;
MiniTLS 2:527a66d0a1a9 147 /* dummy operations */
MiniTLS 2:527a66d0a1a9 148 if ((err = ltc_ecc_projective_add_point(&M[0], &M[1], &M[2], modulus, &mp)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 149 if ((err = ltc_ecc_projective_dbl_point(&M[1], &M[2], modulus, &mp)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 150 continue;
MiniTLS 2:527a66d0a1a9 151 }
MiniTLS 2:527a66d0a1a9 152
MiniTLS 2:527a66d0a1a9 153 if ((err = ltc_ecc_projective_add_point(&M[0], &M[1], &M[i^1], modulus, &mp)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 154 if ((err = ltc_ecc_projective_dbl_point(&M[i], &M[i], modulus, &mp)) != MINITLS_OK) { goto done; }
MiniTLS 2:527a66d0a1a9 155 }
MiniTLS 2:527a66d0a1a9 156
MiniTLS 2:527a66d0a1a9 157 /* copy result out */
MiniTLS 2:527a66d0a1a9 158 /*if ((err =*/ mp_copy(&M[0].x, &R->x);/*) != MINITLS_OK) { goto done; }*/
MiniTLS 2:527a66d0a1a9 159 /*if ((err =*/ mp_copy(&M[0].y, &R->y);/*) != MINITLS_OK) { goto done; }*/
MiniTLS 2:527a66d0a1a9 160 /*if ((err =*/ mp_copy(&M[0].z, &R->z);/*) != MINITLS_OK) { goto done; }*/
MiniTLS 2:527a66d0a1a9 161
MiniTLS 2:527a66d0a1a9 162 /* map R back from projective space */
MiniTLS 2:527a66d0a1a9 163 if (map) {
MiniTLS 2:527a66d0a1a9 164 err = ltc_ecc_map(R, modulus, &mp);
MiniTLS 2:527a66d0a1a9 165 } else {
MiniTLS 2:527a66d0a1a9 166 err = MINITLS_OK;
MiniTLS 2:527a66d0a1a9 167 }
MiniTLS 2:527a66d0a1a9 168 done:
MiniTLS 2:527a66d0a1a9 169 //if (mu != NULL) {
MiniTLS 2:527a66d0a1a9 170 mp_clear(&mu);
MiniTLS 2:527a66d0a1a9 171 //}
MiniTLS 2:527a66d0a1a9 172 mp_montgomery_free(&mp);
MiniTLS 2:527a66d0a1a9 173 mp_clear_multi(&tG.x, &tG.y, &tG.z, NULL);
MiniTLS 2:527a66d0a1a9 174 for (i = 0; i < 3; i++) {
MiniTLS 2:527a66d0a1a9 175 mp_clear_multi(&M[i].x, &M[i].y, &M[i].z, NULL);
MiniTLS 2:527a66d0a1a9 176 }
MiniTLS 2:527a66d0a1a9 177 return err;
MiniTLS 2:527a66d0a1a9 178 }
MiniTLS 2:527a66d0a1a9 179
MiniTLS 2:527a66d0a1a9 180 #endif
MiniTLS 2:527a66d0a1a9 181 #endif
MiniTLS 2:527a66d0a1a9 182 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod_timing.c,v $ */
MiniTLS 2:527a66d0a1a9 183 /* $Revision: 1.13 $ */
MiniTLS 2:527a66d0a1a9 184 /* $Date: 2007/05/12 14:32:35 $ */
MiniTLS 2:527a66d0a1a9 185