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