bn.c

   1 // Copyright 2007,2008,2010  Segher Boessenkool  <segher@kernel.crashing.org>
   2 // Licensed under the terms of the GNU GPL, version 2
   3 // http://www.gnu.org/licenses/old-licenses/gpl-2.0.txt
   4
   5 #include <string.h>
   6 #include <stdio.h>
   7
   8 #include "tools.h"
   9
  10 void bn_print(char *name, u8 *a, u32 n)
  11 {
  12         u32 i;
  13
  14         printf("%s = ", name);
  15
  16         for (i = 0; i < n; i++)
  17                 printf("%02x", a[i]);
  18
  19         printf("\n");
  20 }
  21
  22 static void bn_zero(u8 *d, u32 n)
  23 {
  24         memset(d, 0, n);
  25 }
  26
  27 void bn_copy(u8 *d, u8 *a, u32 n)
  28 {
  29         memcpy(d, a, n);
  30 }
  31
  32 int bn_compare(u8 *a, u8 *b, u32 n)
  33 {
  34         u32 i;
  35
  36         for (i = 0; i < n; i++) {
  37                 if (a[i] < b[i])
  38                         return -1;
  39                 if (a[i] > b[i])
  40                         return 1;
  41         }
  42
  43         return 0;
  44 }
  45
  46 static u8 bn_add_1(u8 *d, u8 *a, u8 *b, u32 n)
  47 {
  48         u32 i;
  49         u32 dig;
  50         u8 c;
  51
  52         c = 0;
  53         for (i = n - 1; i < n; i--) {
  54                 dig = a[i] + b[i] + c;
  55                 c = dig >> 8;
  56                 d[i] = dig;
  57         }
  58
  59         return c;
  60 }
  61
  62 static u8 bn_sub_1(u8 *d, u8 *a, u8 *b, u32 n)
  63 {
  64         u32 i;
  65         u32 dig;
  66         u8 c;
  67
  68         c = 1;
  69         for (i = n - 1; i < n; i--) {
  70                 dig = a[i] + 255 - b[i] + c;
  71                 c = dig >> 8;
  72                 d[i] = dig;
  73         }
  74
  75         return 1 - c;
  76 }
  77
  78 void bn_reduce(u8 *d, u8 *N, u32 n)
  79 {
  80         if (bn_compare(d, N, n) >= 0)
  81                 bn_sub_1(d, d, N, n);
  82 }
  83
  84 void bn_add(u8 *d, u8 *a, u8 *b, u8 *N, u32 n)
  85 {
  86         if (bn_add_1(d, a, b, n))
  87                 bn_sub_1(d, d, N, n);
  88
  89         bn_reduce(d, N, n);
  90 }
  91
  92 void bn_sub(u8 *d, u8 *a, u8 *b, u8 *N, u32 n)
  93 {
  94         if (bn_sub_1(d, a, b, n))
  95                 bn_add_1(d, d, N, n);
  96 }
  97
  98 static const u8 inv256[0x80] = {
  99         0x01, 0xab, 0xcd, 0xb7, 0x39, 0xa3, 0xc5, 0xef,
 100         0xf1, 0x1b, 0x3d, 0xa7, 0x29, 0x13, 0x35, 0xdf,
 101         0xe1, 0x8b, 0xad, 0x97, 0x19, 0x83, 0xa5, 0xcf,
 102         0xd1, 0xfb, 0x1d, 0x87, 0x09, 0xf3, 0x15, 0xbf,
 103         0xc1, 0x6b, 0x8d, 0x77, 0xf9, 0x63, 0x85, 0xaf,
 104         0xb1, 0xdb, 0xfd, 0x67, 0xe9, 0xd3, 0xf5, 0x9f,
 105         0xa1, 0x4b, 0x6d, 0x57, 0xd9, 0x43, 0x65, 0x8f,
 106         0x91, 0xbb, 0xdd, 0x47, 0xc9, 0xb3, 0xd5, 0x7f,
 107         0x81, 0x2b, 0x4d, 0x37, 0xb9, 0x23, 0x45, 0x6f,
 108         0x71, 0x9b, 0xbd, 0x27, 0xa9, 0x93, 0xb5, 0x5f,
 109         0x61, 0x0b, 0x2d, 0x17, 0x99, 0x03, 0x25, 0x4f,
 110         0x51, 0x7b, 0x9d, 0x07, 0x89, 0x73, 0x95, 0x3f,
 111         0x41, 0xeb, 0x0d, 0xf7, 0x79, 0xe3, 0x05, 0x2f,
 112         0x31, 0x5b, 0x7d, 0xe7, 0x69, 0x53, 0x75, 0x1f,
 113         0x21, 0xcb, 0xed, 0xd7, 0x59, 0xc3, 0xe5, 0x0f,
 114         0x11, 0x3b, 0x5d, 0xc7, 0x49, 0x33, 0x55, 0xff,
 115 };
 116
 117 static void bn_mon_muladd_dig(u8 *d, u8 *a, u8 b, u8 *N, u32 n)
 118 {
 119         u32 dig;
 120         u32 i;
 121
 122         u8 z = -(d[n-1] + a[n-1]*b) * inv256[N[n-1]/2];
 123
 124         dig = d[n-1] + a[n-1]*b + N[n-1]*z;
 125         dig >>= 8;
 126
 127         for (i = n - 2; i < n; i--) {
 128                 dig += d[i] + a[i]*b + N[i]*z;
 129                 d[i+1] = dig;
 130                 dig >>= 8;
 131         }
 132
 133         d[0] = dig;
 134         dig >>= 8;
 135
 136         if (dig)
 137                 bn_sub_1(d, d, N, n);
 138
 139         bn_reduce(d, N, n);
 140 }
 141
 142 void bn_mon_mul(u8 *d, u8 *a, u8 *b, u8 *N, u32 n)
 143 {
 144         u8 t[512];
 145         u32 i;
 146
 147         bn_zero(t, n);
 148
 149         for (i = n - 1; i < n; i--)
 150                 bn_mon_muladd_dig(t, a, b[i], N, n);
 151
 152         bn_copy(d, t, n);
 153 }
 154
 155 void bn_to_mon(u8 *d, u8 *N, u32 n)
 156 {
 157         u32 i;
 158
 159         for (i = 0; i < 8*n; i++)
 160                 bn_add(d, d, d, N, n);
 161 }
 162
 163 void bn_from_mon(u8 *d, u8 *N, u32 n)
 164 {
 165         u8 t[512];
 166
 167         bn_zero(t, n);
 168         t[n-1] = 1;
 169         bn_mon_mul(d, d, t, N, n);
 170 }
 171
 172 static void bn_mon_exp(u8 *d, u8 *a, u8 *N, u32 n, u8 *e, u32 en)
 173 {
 174         u8 t[512];
 175         u32 i;
 176         u8 mask;
 177
 178         bn_zero(d, n);
 179         d[n-1] = 1;
 180         bn_to_mon(d, N, n);
 181
 182         for (i = 0; i < en; i++)
 183                 for (mask = 0x80; mask != 0; mask >>= 1) {
 184                         bn_mon_mul(t, d, d, N, n);
 185                         if ((e[i] & mask) != 0)
 186                                 bn_mon_mul(d, t, a, N, n);
 187                         else
 188                                 bn_copy(d, t, n);
 189                 }
 190 }
 191
 192 void bn_mon_inv(u8 *d, u8 *a, u8 *N, u32 n)
 193 {
 194         u8 t[512], s[512];
 195
 196         bn_zero(s, n);
 197         s[n-1] = 2;
 198         bn_sub_1(t, N, s, n);
 199         bn_mon_exp(d, a, N, n, t, n);
 200 }