crypto/bn/bn_mont2.c

   1 /*\r
   2  *\r
   3  *      bn_mont2.c\r
   4  *\r
   5  *      Montgomery Modular Arithmetic Functions.\r
   6  *\r
   7  *      Copyright (C) Lenka Fibikova 2000\r
   8  *\r
   9  *\r
  10  */\r
  11 \r
  12 \r
  13 #include <stdio.h>\r
  14 #include <stdlib.h>\r
  15 #include <assert.h>\r
  16 \r
  17 #include "bn.h"\r
  18 #include "bn_modfs.h"\r
  19 #include "bn_mont2.h"\r
  20 \r
  21 #define BN_mask_word(x, m) ((x->d[0]) & (m))\r
  22 \r
  23 BN_MONTGOMERY *BN_mont_new()\r
  24 {\r
  25         BN_MONTGOMERY *ret;\r
  26 \r
  27         ret=(BN_MONTGOMERY *)malloc(sizeof(BN_MONTGOMERY));\r
  28 \r
  29         if (ret == NULL) return NULL;\r
  30 \r
  31         if ((ret->p = BN_new()) == NULL)\r
  32         {\r
  33                 free(ret);\r
  34                 return NULL;\r
  35         }\r
  36 \r
  37         return ret;\r
  38 }\r
  39 \r
  40 \r
  41 void BN_mont_clear_free(BN_MONTGOMERY *mont)\r
  42 {\r
  43         if (mont == NULL) return;\r
  44 \r
  45         if (mont->p != NULL) BN_clear_free(mont->p);\r
  46 \r
  47         mont->p_num_bytes = 0;\r
  48         mont->R_num_bits = 0;\r
  49         mont->p_inv_b_neg = 0;\r
  50 }\r
  51 \r
  52 int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
  53 {\r
  54         assert(x != NULL);\r
  55 \r
  56         assert(mont != NULL);\r
  57         assert(mont->p != NULL);\r
  58 \r
  59         assert(ctx != NULL);\r
  60 \r
  61         if (!BN_lshift(x, x, mont->R_num_bits)) return 0;\r
  62         if (!BN_mod(x, x, mont->p, ctx)) return 0;\r
  63 \r
  64         return 1;\r
  65 }\r
  66 \r
  67 \r
  68 static BN_ULONG BN_mont_inv(BIGNUM *a, int e, BN_CTX *ctx)\r
  69 /* y = a^{-1} (mod 2^e) for an odd number a */\r
  70 {\r
  71         BN_ULONG y, exp, mask;\r
  72         BIGNUM *x, *xy, *x_sh;\r
  73         int i;\r
  74 \r
  75         assert(a != NULL && ctx != NULL);\r
  76         assert(e <= BN_BITS2);\r
  77         assert(BN_is_odd(a));\r
  78         assert(!BN_is_zero(a) && !a->neg);\r
  79 \r
  80 \r
  81         y = 1;\r
  82         exp = 2;\r
  83         mask = 3;\r
  84         if((x = BN_dup(a)) == NULL) return 0;\r
  85         if(!BN_mask_bits(x, e)) return 0;\r
  86 \r
  87         xy = ctx->bn[ctx->tos]; \r
  88         x_sh = ctx->bn[ctx->tos + 1]; \r
  89         ctx->tos += 2;\r
  90 \r
  91         if (BN_copy(xy, x) == NULL) goto err;\r
  92         if (!BN_lshift1(x_sh, x)) goto err;\r
  93 \r
  94 \r
  95         for (i = 2; i <= e; i++)\r
  96         {\r
  97                 if (exp < BN_mask_word(xy, mask))\r
  98                 {\r
  99                         y = y + exp;\r
 100                         if (!BN_add(xy, xy, x_sh)) goto err;\r
 101                 }\r
 102 \r
 103                 exp <<= 1;\r
 104                 if (!BN_lshift1(x_sh, x_sh)) goto err;\r
 105                 mask <<= 1;\r
 106                 mask++;\r
 107         }\r
 108 \r
 109 \r
 110 #ifdef TEST\r
 111         if (xy->d[0] != 1) goto err;\r
 112 #endif\r
 113 \r
 114         if (x != NULL) BN_clear_free(x);\r
 115         ctx->tos -= 2;\r
 116         return y;\r
 117 \r
 118 \r
 119 err:\r
 120         if (x != NULL) BN_clear_free(x);\r
 121         ctx->tos -= 2;\r
 122         return 0;\r
 123 \r
 124 }\r
 125 \r
 126 int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
 127 {\r
 128         assert(p != NULL && ctx != NULL);\r
 129         assert(mont != NULL);\r
 130         assert(mont->p != NULL);\r
 131         assert(!BN_is_zero(p) && !p->neg);\r
 132 \r
 133 \r
 134         mont->p_num_bytes = p->top;\r
 135         mont->R_num_bits = (mont->p_num_bytes) * BN_BITS2;\r
 136 \r
 137         if (BN_copy(mont->p, p) == NULL);\r
 138         \r
 139         mont->p_inv_b_neg =  BN_mont_inv(p, BN_BITS2, ctx);\r
 140         mont->p_inv_b_neg = 0 - mont->p_inv_b_neg;\r
 141 \r
 142         return 1;\r
 143 }\r
 144 \r
 145 static int BN_cpy_mul_word(BIGNUM *ret, BIGNUM *a, BN_ULONG w)\r
 146 /* ret = a * w */\r
 147 {\r
 148         if (BN_copy(ret, a) == NULL) return 0;\r
 149 \r
 150         if (!BN_mul_word(ret, w)) return 0;\r
 151 \r
 152         return 1;\r
 153 }\r
 154 \r
 155 \r
 156 int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
 157 /* yR^{-1} (mod p) */\r
 158 {\r
 159         int i;\r
 160         BIGNUM *up, *p;\r
 161         BN_ULONG u;\r
 162 \r
 163         assert(y != NULL && mont != NULL && ctx != NULL);\r
 164         assert(mont->p != NULL);\r
 165         assert(BN_cmp(y, mont->p) < 0);\r
 166         assert(!y->neg);\r
 167 \r
 168 \r
 169         if (BN_is_zero(y)) return 1;\r
 170 \r
 171         p = mont->p;\r
 172         up = ctx->bn[ctx->tos]; \r
 173         ctx->tos += 1;\r
 174 \r
 175 \r
 176         for (i = 0; i < mont->p_num_bytes; i++)\r
 177         {\r
 178                 u = (y->d[0]) * mont->p_inv_b_neg;                      /* u = y_0 * p' */\r
 179 \r
 180                 if (!BN_cpy_mul_word(up, p, u)) goto err;       /* up = u * p */\r
 181 \r
 182                 if (!BN_add(y, y, up)) goto err;                        \r
 183 #ifdef TEST\r
 184                 if (y->d[0]) goto err;\r
 185 #endif\r
 186                 if (!BN_rshift(y, y, BN_BITS2)) goto err;       /* y = (y + up)/b */\r
 187         }\r
 188 \r
 189 \r
 190         if (BN_cmp(y, mont->p) >= 0) \r
 191         {\r
 192                 if (!BN_sub(y, y, mont->p)) goto err;\r
 193         }\r
 194 \r
 195         ctx->tos -= 1;\r
 196         return 1;\r
 197 \r
 198 err:\r
 199         ctx->tos -= 1;\r
 200         return 0;\r
 201 \r
 202 }\r
 203 \r
 204 \r
 205 int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
 206 /* r = x * y mod p */\r
 207 /* r != x && r! = y !!! */\r
 208 {\r
 209         BIGNUM *xiy, *up;\r
 210         BN_ULONG u;\r
 211         int i;\r
 212         \r
 213 \r
 214         assert(r != x && r != y);\r
 215         assert(r != NULL && x != NULL  && y != NULL && mont != NULL && ctx != NULL);\r
 216         assert(mont->p != NULL);\r
 217         assert(BN_cmp(x, mont->p) < 0);\r
 218         assert(BN_cmp(y, mont->p) < 0);\r
 219         assert(!x->neg);\r
 220         assert(!y->neg);\r
 221 \r
 222         if (BN_is_zero(x) || BN_is_zero(y))\r
 223         {\r
 224                 if (!BN_zero(r)) return 0;\r
 225                 return 1;\r
 226         }\r
 227 \r
 228 \r
 229 \r
 230         xiy = ctx->bn[ctx->tos]; \r
 231         up = ctx->bn[ctx->tos + 1]; \r
 232         ctx->tos += 2;\r
 233 \r
 234         if (!BN_zero(r)) goto err;\r
 235 \r
 236         for (i = 0; i < x->top; i++)\r
 237         {\r
 238                 u = (r->d[0] + x->d[i] * y->d[0]) * mont->p_inv_b_neg;\r
 239 \r
 240                 if (!BN_cpy_mul_word(xiy, y, x->d[i])) goto err;\r
 241                 if (!BN_cpy_mul_word(up, mont->p, u)) goto err;\r
 242 \r
 243                 if (!BN_add(r, r, xiy)) goto err;\r
 244                 if (!BN_add(r, r, up)) goto err;\r
 245 \r
 246 #ifdef TEST\r
 247                 if (r->d[0]) goto err;\r
 248 #endif\r
 249                 if (!BN_rshift(r, r, BN_BITS2)) goto err; \r
 250         }\r
 251 \r
 252         for (i = x->top; i < mont->p_num_bytes; i++)\r
 253         {\r
 254                 u = (r->d[0]) * mont->p_inv_b_neg;\r
 255 \r
 256                 if (!BN_cpy_mul_word(up, mont->p, u)) goto err;\r
 257 \r
 258                 if (!BN_add(r, r, up)) goto err;\r
 259 \r
 260 #ifdef TEST\r
 261                 if (r->d[0]) goto err;\r
 262 #endif\r
 263                 if (!BN_rshift(r, r, BN_BITS2)) goto err; \r
 264         }\r
 265 \r
 266 \r
 267         if (BN_cmp(r, mont->p) >= 0) \r
 268         {\r
 269                 if (!BN_sub(r, r, mont->p)) goto err;\r
 270         }\r
 271 \r
 272 \r
 273         ctx->tos -= 2;\r
 274         return 1;\r
 275 \r
 276 err:\r
 277         ctx->tos -= 2;\r
 278         return 0;\r
 279 }\r
 280 \r
 281 int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)\r
 282 {\r
 283         assert(r != NULL && x != NULL  && y != NULL && mont != NULL);\r
 284         assert(mont->p != NULL);\r
 285         assert(BN_cmp(x, mont->p) < 0);\r
 286         assert(BN_cmp(y, mont->p) < 0);\r
 287         assert(!x->neg);\r
 288         assert(!y->neg);\r
 289 \r
 290         if (!BN_add(r, x, y)) return 0;\r
 291         if (BN_cmp(r, mont->p) >= 0) \r
 292         {\r
 293                 if (!BN_sub(r, r, mont->p)) return 0;\r
 294         }\r
 295 \r
 296         return 1;\r
 297 }\r
 298 \r
 299 \r
 300 int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)\r
 301 {\r
 302         assert(r != NULL && x != NULL  && y != NULL && mont != NULL);\r
 303         assert(mont->p != NULL);\r
 304         assert(BN_cmp(x, mont->p) < 0);\r
 305         assert(BN_cmp(y, mont->p) < 0);\r
 306         assert(!x->neg);\r
 307         assert(!y->neg);\r
 308 \r
 309         if (!BN_sub(r, x, y)) return 0;\r
 310         if (r->neg) \r
 311         {\r
 312                 if (!BN_add(r, r, mont->p)) return 0;\r
 313         }\r
 314 \r
 315         return 1;\r
 316 }\r
 317 \r
 318 int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont)\r
 319 {\r
 320         assert(r != NULL && x != NULL && mont != NULL);\r
 321         assert(mont->p != NULL);\r
 322         assert(BN_cmp(x, mont->p) < 0);\r
 323         assert(!x->neg);\r
 324 \r
 325         if (!BN_lshift1(r, x)) return 0;\r
 326 \r
 327         if (BN_cmp(r, mont->p) >= 0) \r
 328         {\r
 329                 if (!BN_sub(r, r, mont->p)) return 0;\r
 330         }\r
 331 \r
 332         return 1;\r
 333 }\r
 334 \r
 335 int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont)\r
 336 {\r
 337         int sh_nb;\r
 338 \r
 339         assert(r != NULL && x != NULL && mont != NULL);\r
 340         assert(mont->p != NULL);\r
 341         assert(BN_cmp(x, mont->p) < 0);\r
 342         assert(!x->neg);\r
 343         assert(n > 0);\r
 344 \r
 345         if (r != x)\r
 346         {\r
 347                 if (BN_copy(r, x) == NULL) return 0;\r
 348         }\r
 349 \r
 350         while (n)\r
 351         {\r
 352                 sh_nb = BN_num_bits(mont->p) - BN_num_bits(r);\r
 353                 if (sh_nb > n) sh_nb = n;\r
 354 \r
 355                 if (sh_nb)\r
 356                 {\r
 357                         if(!BN_lshift(r, r, sh_nb)) return 0;\r
 358                 }\r
 359                 else \r
 360                 {\r
 361                         sh_nb = 1;\r
 362                         if (!BN_lshift1(r, r)) return 0;\r
 363                 }\r
 364 \r
 365                 if (BN_cmp(r, mont->p) >= 0) \r
 366                 {\r
 367                         if (!BN_sub(r, r, mont->p)) return 0;\r
 368                 }\r
 369 \r
 370                 n -= sh_nb;\r
 371         }\r
 372 \r
 373         return 1;\r
 374 }\r