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 "kirk_engine.h"
9
bn_print(char * name,u8 * a,u32 n)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
bn_zero(u8 * d,u32 n)22 static void bn_zero(u8 *d, u32 n)
23 {
24 memset(d, 0, n);
25 }
26
bn_copy(u8 * d,u8 * a,u32 n)27 void bn_copy(u8 *d, u8 *a, u32 n)
28 {
29 memcpy(d, a, n);
30 }
31
bn_compare(u8 * a,u8 * b,u32 n)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
bn_add_1(u8 * d,u8 * a,u8 * b,u32 n)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
bn_sub_1(u8 * d,u8 * a,u8 * b,u32 n)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
bn_reduce(u8 * d,u8 * N,u32 n)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
bn_add(u8 * d,u8 * a,u8 * b,u8 * N,u32 n)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
bn_sub(u8 * d,u8 * a,u8 * b,u8 * N,u32 n)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
bn_mon_muladd_dig(u8 * d,u8 * a,u8 b,u8 * N,u32 n)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
bn_mon_mul(u8 * d,u8 * a,u8 * b,u8 * N,u32 n)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
bn_to_mon(u8 * d,u8 * N,u32 n)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
bn_from_mon(u8 * d,u8 * N,u32 n)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
bn_mon_exp(u8 * d,u8 * a,u8 * N,u32 n,u8 * e,u32 en)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
bn_mon_inv(u8 * d,u8 * a,u8 * N,u32 n)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 }
201