src/modp256r1.c

   1 /*
   2  * modp256r1.c -- modulo arithmetic for p256r1
   3  *
   4  * Copyright (C) 2011, 2013, 2014 Free Software Initiative of Japan
   5  * Author: NIIBE Yutaka <gniibe@fsij.org>
   6  *
   7  * This file is a part of Gnuk, a GnuPG USB Token implementation.
   8  *
   9  * Gnuk is free software: you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation, either version 3 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * Gnuk is distributed in the hope that it will be useful, but WITHOUT
  15  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  16  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  17  * License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  21  *
  22  */
  23
  24 /*
  25  * p256 =  2^256 - 2^224 + 2^192 + 2^96 - 1
  26  */
  27 #include <stdint.h>
  28 #include <string.h>
  29
  30 #include "bn.h"
  31 #include "modp256r1.h"
  32
  33 /*
  34 256      224      192      160      128       96       64       32        0
  35 2^256
  36   1 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  37 2^256 - 2^224
  38   0 ffffffff 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  39 2^256 - 2^224 + 2^192
  40   0 ffffffff 00000001 00000000 00000000 00000000 00000000 00000000 00000000
  41 2^256 - 2^224 + 2^192 + 2^96
  42   0 ffffffff 00000001 00000000 00000000 00000001 00000000 00000000 00000000
  43 2^256 - 2^224 + 2^192 + 2^96 - 1
  44   0 ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff
  45 */
  46 const bn256 p256r1 = { {0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
  47                         0x00000000, 0x00000000, 0x00000001, 0xffffffff} };
  48
  49 /**
  50  * @brief  X = (A + B) mod p256r1
  51  */
  52 void
  53 modp256r1_add (bn256 *X, const bn256 *A, const bn256 *B)
  54 {
  55   uint32_t carry;
  56   bn256 tmp[1];
  57
  58   carry = bn256_add (X, A, B);
  59   if (carry)
  60     bn256_sub (X, X, P256R1);
  61   else
  62     bn256_sub (tmp, X, P256R1);
  63 }
  64
  65 /**
  66  * @brief  X = (A - B) mod p256r1
  67  */
  68 void
  69 modp256r1_sub (bn256 *X, const bn256 *A, const bn256 *B)
  70 {
  71   uint32_t borrow;
  72   bn256 tmp[1];
  73
  74   borrow = bn256_sub (X, A, B);
  75   if (borrow)
  76     bn256_add (X, X, P256R1);
  77   else
  78     bn256_add (tmp, X, P256R1);
  79 }
  80
  81 /**
  82  * @brief  X = A mod p256r1
  83  */
  84 void
  85 modp256r1_reduce (bn256 *X, const bn512 *A)
  86 {
  87   bn256 tmp[1];
  88   uint32_t borrow;
  89
  90 #define S1 X
  91 #define S2 tmp
  92 #define S3 tmp
  93 #define S4 tmp
  94 #define S5 tmp
  95 #define S6 tmp
  96 #define S7 tmp
  97 #define S8 tmp
  98 #define S9 tmp
  99
 100   S1->word[7] = A->word[7];
 101   S1->word[6] = A->word[6];
 102   S1->word[5] = A->word[5];
 103   S1->word[4] = A->word[4];
 104   S1->word[3] = A->word[3];
 105   S1->word[2] = A->word[2];
 106   S1->word[1] = A->word[1];
 107   S1->word[0] = A->word[0];
 108   /* X = S1 */
 109
 110   S2->word[7] = A->word[15];
 111   S2->word[6] = A->word[14];
 112   S2->word[5] = A->word[13];
 113   S2->word[4] = A->word[12];
 114   S2->word[3] = A->word[11];
 115   S2->word[2] = S2->word[1] = S2->word[0] = 0;
 116   /* X += 2 * S2 */
 117   modp256r1_add (X, X, S2);
 118   modp256r1_add (X, X, S2);
 119
 120   S3->word[7] = 0;
 121   S3->word[6] = A->word[15];
 122   S3->word[5] = A->word[14];
 123   S3->word[4] = A->word[13];
 124   S3->word[3] = A->word[12];
 125   S3->word[2] = S3->word[1] = S3->word[0] = 0;
 126   /* X += 2 * S3 */
 127   modp256r1_add (X, X, S3);
 128   modp256r1_add (X, X, S3);
 129
 130   S4->word[7] = A->word[15];
 131   S4->word[6] = A->word[14];
 132   S4->word[5] = S4->word[4] = S4->word[3] = 0;
 133   S4->word[2] = A->word[10];
 134   S4->word[1] = A->word[9];
 135   S4->word[0] = A->word[8];
 136   /* X += S4 */
 137   modp256r1_add (X, X, S4);
 138
 139   S5->word[7] = A->word[8];
 140   S5->word[6] = A->word[13];
 141   S5->word[5] = A->word[15];
 142   S5->word[4] = A->word[14];
 143   S5->word[3] = A->word[13];
 144   S5->word[2] = A->word[11];
 145   S5->word[1] = A->word[10];
 146   S5->word[0] = A->word[9];
 147   /* X += S5 */
 148   modp256r1_add (X, X, S5);
 149
 150   S6->word[7] = A->word[10];
 151   S6->word[6] = A->word[8];
 152   S6->word[5] = S6->word[4] = S6->word[3] = 0;
 153   S6->word[2] = A->word[13];
 154   S6->word[1] = A->word[12];
 155   S6->word[0] = A->word[11];
 156   /* X -= S6 */
 157   modp256r1_sub (X, X, S6);
 158
 159   S7->word[7] = A->word[11];
 160   S7->word[6] = A->word[9];
 161   S7->word[5] = S7->word[4] = 0;
 162   S7->word[3] = A->word[15];
 163   S7->word[2] = A->word[14];
 164   S7->word[1] = A->word[13];
 165   S7->word[0] = A->word[12];
 166   /* X -= S7 */
 167   modp256r1_sub (X, X, S7);
 168
 169   S8->word[7] = A->word[12];
 170   S8->word[6] = 0;
 171   S8->word[5] = A->word[10];
 172   S8->word[4] = A->word[9];
 173   S8->word[3] = A->word[8];
 174   S8->word[2] = A->word[15];
 175   S8->word[1] = A->word[14];
 176   S8->word[0] = A->word[13];
 177   /* X -= S8 */
 178   modp256r1_sub (X, X, S8);
 179
 180   S9->word[7] = A->word[13];
 181   S9->word[6] = 0;
 182   S9->word[5] = A->word[11];
 183   S9->word[4] = A->word[10];
 184   S9->word[3] = A->word[9];
 185   S9->word[2] = 0;
 186   S9->word[1] = A->word[15];
 187   S9->word[0] = A->word[14];
 188   /* X -= S9 */
 189   modp256r1_sub (X, X, S9);
 190
 191   borrow = bn256_sub (tmp, X, P256R1);
 192   if (borrow)
 193     memcpy (tmp, X, sizeof (bn256));
 194   else
 195     memcpy (X, tmp, sizeof (bn256));
 196
 197 #undef S1
 198 #undef S2
 199 #undef S3
 200 #undef S4
 201 #undef S5
 202 #undef S6
 203 #undef S7
 204 #undef S8
 205 #undef S9
 206 }
 207
 208 /**
 209  * @brief  X = (A * B) mod p256r1
 210  */
 211 void
 212 modp256r1_mul (bn256 *X, const bn256 *A, const bn256 *B)
 213 {
 214   bn512 AB[1];
 215
 216   bn256_mul (AB, A, B);
 217   modp256r1_reduce (X, AB);
 218 }
 219
 220 /**
 221  * @brief  X = A * A mod p256r1
 222  */
 223 void
 224 modp256r1_sqr (bn256 *X, const bn256 *A)
 225 {
 226   bn512 AA[1];
 227
 228   bn256_sqr (AA, A);
 229   modp256r1_reduce (X, AA);
 230 }
 231
 232 /**
 233  * @brief  C = (1 / a)  mod p256r1
 234  *
 235  * Return -1 on error.
 236  * Return 0 on success.
 237  */
 238 #define MAX_N_BITS 256
 239
 240 int
 241 modp256r1_inv (bn256 *C, const bn256 *a)
 242 {
 243   bn256 u[1], v[1], tmp[1];
 244   bn256 A[1] = { { { 1, 0, 0, 0, 0, 0, 0, 0 } } };
 245   uint32_t carry;
 246   int n = MAX_N_BITS * 3;
 247
 248   if (bn256_is_zero (a))
 249     return -1;
 250
 251   memset (C, 0, sizeof (bn256));
 252   memcpy (u, a, sizeof (bn256));
 253   memcpy (v, P256R1, sizeof (bn256));
 254
 255   while (n--)
 256     {
 257       int c = (bn256_is_even (u) << 1) + bn256_is_even (v);
 258
 259       switch (c)
 260         {
 261         case 3:
 262           bn256_shift (u, u, -1);
 263           if (bn256_is_even (A))
 264             {
 265               bn256_add (tmp, A, P256R1);
 266               carry = 0;
 267             }
 268           else
 269             carry = bn256_add (A, A, P256R1);
 270
 271           bn256_shift (A, A, -1);
 272           A->word[7] |= carry * 0x80000000;
 273
 274           bn256_shift (v, v, -1);
 275           if (bn256_is_even (C))
 276             {
 277               bn256_add (tmp, C, P256R1);
 278               carry = 0;
 279             }
 280           else
 281             carry = bn256_add (C, C, P256R1);
 282
 283           bn256_shift (C, C, -1);
 284           C->word[7] |= carry * 0x80000000;
 285
 286           if (bn256_is_ge (tmp, tmp))
 287             {
 288               bn256_sub (tmp, tmp, tmp);
 289               modp256r1_sub (tmp, tmp, tmp);
 290             }
 291           else
 292             {
 293               bn256_sub (tmp, tmp, tmp);
 294               modp256r1_sub (tmp, tmp, A);
 295             }
 296           break;
 297
 298         case 1:
 299           bn256_shift (tmp, tmp, -1);
 300           if (bn256_is_even (tmp))
 301             {
 302               bn256_add (tmp, tmp, P256R1);
 303               carry = 0;
 304             }
 305           else
 306             carry = bn256_add (tmp, tmp, P256R1);
 307
 308           bn256_shift (tmp, tmp, -1);
 309           tmp->word[7] |= carry * 0x80000000;
 310
 311           bn256_shift (v, v, -1);
 312           if (bn256_is_even (C))
 313             {
 314               bn256_add (tmp, C, P256R1);
 315               carry = 0;
 316             }
 317           else
 318             carry = bn256_add (C, C, P256R1);
 319
 320           bn256_shift (C, C, -1);
 321           C->word[7] |= carry * 0x80000000;
 322
 323           if (bn256_is_ge (tmp, tmp))
 324             {
 325               bn256_sub (tmp, tmp, tmp);
 326               modp256r1_sub (tmp, tmp, tmp);
 327             }
 328           else
 329             {
 330               bn256_sub (tmp, tmp, tmp);
 331               modp256r1_sub (tmp, tmp, A);
 332             }
 333           break;
 334
 335         case 2:
 336           bn256_shift (u, u, -1);
 337           if (bn256_is_even (A))
 338             {
 339               bn256_add (tmp, A, P256R1);
 340               carry = 0;
 341             }
 342           else
 343             carry = bn256_add (A, A, P256R1);
 344
 345           bn256_shift (A, A, -1);
 346           A->word[7] |= carry * 0x80000000;
 347
 348           bn256_shift (tmp, tmp, -1);
 349           if (bn256_is_even (tmp))
 350             {
 351               bn256_add (tmp, tmp, P256R1);
 352               carry = 0;
 353             }
 354           else
 355             carry = bn256_add (tmp, tmp, P256R1);
 356
 357           bn256_shift (tmp, tmp, -1);
 358           tmp->word[7] |= carry * 0x80000000;
 359
 360           if (bn256_is_ge (tmp, tmp))
 361             {
 362               bn256_sub (tmp, tmp, tmp);
 363               modp256r1_sub (tmp, tmp, tmp);
 364             }
 365           else
 366             {
 367               bn256_sub (tmp, tmp, tmp);
 368               modp256r1_sub (tmp, tmp, A);
 369             }
 370           break;
 371
 372         case 0:
 373           bn256_shift (tmp, tmp, -1);
 374           if (bn256_is_even (tmp))
 375             {
 376               bn256_add (tmp, tmp, P256R1);
 377               carry = 0;
 378             }
 379           else
 380             carry = bn256_add (tmp, tmp, P256R1);
 381
 382           bn256_shift (tmp, tmp, -1);
 383           tmp->word[7] |= carry * 0x80000000;
 384
 385           bn256_shift (tmp, tmp, -1);
 386           if (bn256_is_even (tmp))
 387             {
 388               bn256_add (tmp, tmp, P256R1);
 389               carry = 0;
 390             }
 391           else
 392             carry = bn256_add (tmp, tmp, P256R1);
 393
 394           bn256_shift (tmp, tmp, -1);
 395           tmp->word[7] |= carry * 0x80000000;
 396
 397           if (bn256_is_ge (u, v))
 398             {
 399               bn256_sub (u, u, v);
 400               modp256r1_sub (A, A, C);
 401             }
 402           else
 403             {
 404               bn256_sub (v, v, u);
 405               modp256r1_sub (C, C, A);
 406             }
 407           break;
 408         }
 409     }
 410
 411   return 0;
 412 }
 413
 414 /**
 415  * @brief  X = (A << shift) mod p256r1
 416  * @note   shift < 32
 417  */
 418 void
 419 modp256r1_shift (bn256 *X, const bn256 *A, int shift)
 420 {
 421   uint32_t carry;
 422 #define borrow carry
 423   bn256 tmp[1];
 424
 425   carry = bn256_shift (X, A, shift);
 426   if (shift < 0)
 427     return;
 428
 429   memset (tmp, 0, sizeof (bn256));
 430   tmp->word[7] = carry;
 431   tmp->word[0] = carry;
 432   modp256r1_add (X, X, tmp);
 433
 434   tmp->word[7] = 0;
 435   tmp->word[0] = 0;
 436   tmp->word[6] = carry;
 437   tmp->word[3] = carry;
 438   modp256r1_sub (X, X, tmp);
 439
 440   borrow = bn256_sub (tmp, X, P256R1);
 441   if (borrow)
 442     memcpy (tmp, X, sizeof (bn256));
 443   else
 444     memcpy (X, tmp, sizeof (bn256));
 445 #undef borrow
 446 }