bn.c

   1 // Copyright 2007,2008  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 static 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 static void bn_copy(u8 *d, u8 *a, u32 n)
  28 {
  29         memcpy(d, a, n);
  30 }
  31
  32 static 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 void bn_sub_raw(u8 *a, u8 *N, 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 = N[i] + c;
  55                 c = (a[i] < dig);
  56                 a[i] -= dig;
  57         }
  58 }
  59
  60 static void bn_add(u8 *d, u8 *a, u8 *b, u8 *N, u32 n)
  61 {
  62         u32 i;
  63         u32 dig;
  64         u8 c;
  65
  66         c = 0;
  67         for (i = n - 1; i < n; i--) {
  68                 dig = a[i] + b[i] + c;
  69                 c = (dig >= 0x100);
  70                 d[i] = dig;
  71         }
  72
  73         if (c)
  74                 bn_sub_raw(d, N, n);
  75
  76         if (bn_compare(d, N, n) >= 0)
  77                 bn_sub_raw(d, N, n);
  78 }
  79
  80 static void bn_mul(u8 *d, u8 *a, u8 *b, u8 *N, u32 n)
  81 {
  82         u32 i;
  83         u8 mask;
  84
  85         bn_zero(d, n);
  86
  87         for (i = 0; i < n; i++)
  88                 for (mask = 0x80; mask != 0; mask >>= 1) {
  89                         bn_add(d, d, d, N, n);
  90                         if ((a[i] & mask) != 0)
  91                                 bn_add(d, d, b, N, n);
  92                 }
  93 }
  94
  95 void bn_exp(u8 *d, u8 *a, u8 *N, u32 n, u8 *e, u32 en)
  96 {
  97         u8 t[512];
  98         u32 i;
  99         u8 mask;
 100
 101         bn_zero(d, n);
 102         d[n-1] = 1;
 103         for (i = 0; i < en; i++)
 104                 for (mask = 0x80; mask != 0; mask >>= 1) {
 105                         bn_mul(t, d, d, N, n);
 106                         if ((e[i] & mask) != 0)
 107                                 bn_mul(d, t, a, N, n);
 108                         else
 109                                 bn_copy(d, t, n);
 110                 }
 111 }
 112
 113 // only for prime N -- stupid but lazy, see if I care
 114 static void bn_inv(u8 *d, u8 *a, u8 *N, u32 n)
 115 {
 116         u8 t[512], s[512];
 117
 118         bn_copy(t, N, n);
 119         bn_zero(s, n);
 120         s[n-1] = 2;
 121         bn_sub_raw(t, s, n);
 122         bn_exp(d, a, N, n, t, n);
 123 }