Debian Codegraph @

crypto/rsa/keys.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 use bytes;
5 use crypto::bigint;
6 use crypto::math::*;
7 use endian;
8 use errors;
9 use io;
10 use memio;
11 use types;
12
13 // The default bit size of RSA keys is 4096-bit. Used as base for buffer sizes.
14 export def BITSZ: size = 4096;
15
16 // The minimum bit size of RSA keys used only for validation during key init.
17 // The default value is 1024-bit.
18 export def MINBITSZ: size = 1024;
19
20 // RSA key parameters for initializing public keys with [[pubkey_init]].
21 export type pubparams = struct {
22 // Modulus in big-endian order
23 n: []u8,
24
25 // Public exponent in big-endian order
26 e: []u8,
27 };
28
29 // RSA key parameters for initializing private keys with [[privkey_init]]. If
30 // the private exponent d is available, [[privkey_initd]] may be used, which
31 // derives 'dp' and 'dq'. All big integer values are in big-endian order.
32 export type privparams = struct {
33 // Bit length of the modulus n. If unknown, the modulus can be provided
34 // to the init function, which derivces the length.
35 nbitlen: size,
36
37 // First prime factor.
38 p: []u8,
39
40 // Second prime factor
41 q: []u8,
42
43 // First exponent. dp = d mod (p - 1) where d is the private exponent.
44 // May be omitted on [[privkey_initd]].
45 dp: []u8,
46
47 // Second exponent. dq = d mod (q - 1) where d is the private exponent.
48 // May be omitted on [[privkey_initd]].
49 dq: []u8,
50
51 // Coefficient. iq = q^-1 mod p.
52 iq: []u8,
53 };
54
55 // Size required to store a public key of [[BITSZ]] length.
56 export def PUBKEYSZ: size = 5 + 2 * (BITSZ >> 3);
57
58 // Initializes a public key from given [[pubparams]] 'x'. The data format
59 // of 'pubkey' is subject to change and must not be used to serialize the key.
60 // [[PUBKEYSZ]] defines the required size to store a key of [[BITSZ]].
61 //
62 // If given key does not fit into 'pubkey' or is too small, [[errors::overflow]]
63 // is returned. Returns [[errors::invalid]], if given key parameters are
64 // invalid. Returns the number of bytes written to 'pubkey' on success.
65 export fn pubkey_init(pubkey: []u8, x: pubparams) (size | error) = {
66 let e = ltrim(x.e);
67 let n = ltrim(x.n);
68
69 if (len(pubkey) < pubkey_len(n, e) || len(n) > types::U16_MAX
70 || len(e) > types::U16_MAX) {
71 return errors::overflow;
72 };
73
74 // Very basic key checks that only catch obvious errors.
75 if ((len(e) == 1 && e[0] == 1) || len(e) > len(n)) {
76 return errors::invalid;
77 };
78 if (bitlen(n) < MINBITSZ) {
79 return errors::invalid;
80 };
81
82 let w = memio::fixed(pubkey);
83
84 let s = 0z;
85 s += writeslice(&w, e)!;
86 s += writeslice(&w, n)!;
87 return s;
88 };
89
90 // Returns the length of the modulus 'n' of given public key.
91 export fn pubkey_nbitlen(pubkey: []u8) size = {
92 let p = pubkey_params(pubkey);
93 return bitlen(p.n);
94 };
95
96 // Returns the length the public key would require in its encoded form.
97 fn pubkey_len(n: []u8, e: []u8) size = 1z + 2 + len(n) + 2 + len(e);
98
99 // Returns the slice without preceeding zeroes.
100 fn ltrim(s: []u8) []u8 = {
101 for (len(s) > 0 && s[0] == 0) {
102 s = s[1..];
103 };
104 return s;
105 };
106
107 fn writeslice(dest: io::handle, a: []u8) (size | io::error) = {
108 let lenbuf: [2]u8 = [0...];
109 endian::beputu16(lenbuf, len(a): u16);
110 let s = io::write(dest, lenbuf)?;
111 s += io::write(dest, a)?;
112 return s;
113 };
114
115 // Counts the bits for given slice 'n'.
116 fn bitlen(s: []u8) size = {
117 let i = 0z;
118 for (i < len(s) && s[i] == 0; i += 1) void;
119 return countbits(s[i]) + 8 * (len(s) - i - 1);
120 };
121
122 fn countbits(x: u8) size = {
123 let k: u32 = nequ32(x, 0);
124 let c: u32 = 0;
125
126 c = gtu32(x, 0x0f);
127 x = muxu32(c, x >> 4, x): u8;
128 k += c << 2;
129
130 c = gtu32(x, 0x03);
131 x = muxu32(c, x >> 2, x): u8;
132 k += c << 1;
133
134 k += gtu32(x, 0x01);
135
136 return k;
137 };
138
139 @test fn countbits() void = {
140 assert(countbits(0xf0) == 8);
141 assert(countbits(0x70) == 7);
142 assert(countbits(0x30) == 6);
143 assert(countbits(0x10) == 5);
144 assert(countbits(0x08) == 4);
145 assert(countbits(0x04) == 3);
146 assert(countbits(0x03) == 2);
147 assert(countbits(0x01) == 1);
148 assert(countbits(0x00) == 0);
149 };
150
151 // Returns the public key parameters, borrowed from given 'pubkey'.
152 export fn pubkey_params(pubkey: []u8) pubparams = {
153 let keybuf = pubkey;
154 return pubparams {
155 e = nextslice(&keybuf),
156 n = nextslice(&keybuf),
157 };
158 };
159
160 fn nextslice(key: *[]u8) []u8 = {
161 const l = endian::begetu16(key[..2]);
162 let s = key[2..2 + l];
163 *key = key[2 + l..];
164 return s;
165 };
166
167 // Size required to store a private key of [[BITSZ]] length.
168 export def PRIVKEYSZ: size = 13 + (MAXFACTOR >> 3) * 5;
169
170 fn privkey_len(x: *privparams) size =
171 13z + len(x.p) + len(x.q) + len(x.dp) + len(x.dq) + len(x.iq);
172
173 // Initializes the private key 'privkey' using the values from 'x'. 'nbitlen' of
174 // 'x' may be omitted, if the modulus 'n' is passed. All other values of 'x'
175 // must be present. If 'x' is missing 'dp' and 'dq' use [[privkey_initd]].
176 //
177 // In case of invalid parameters or if the key is too small, [[errors::invalid]]
178 // is returned. If the key does not fit 'privkey', [[errors::overflow]] is
179 // returned. On success the number of bytes written to 'privkey' is returned.
180 export fn privkey_init(privkey: []u8, x: privparams, n: []u8...) (size | error) = {
181 privkey_normalize(privkey, &x)?;
182
183 if (len(x.dp) == 0 || len(x.dq) == 0) {
184 return errors::invalid;
185 };
186
187 let s = privkey_writehead(privkey, &x, n...)?;
188 let w = memio::fixed(privkey[s..]);
189
190 s += writeslice(&w, x.dp)!;
191 s += writeslice(&w, x.dq)!;
192
193 s += writeslice(&w, x.iq)!;
194 s += writeslice(&w, x.p)!;
195 s += writeslice(&w, x.q)!;
196 return s;
197 };
198
199 // Trims key parameters and also does basic key checks.
200 fn privkey_normalize(privkey: []u8, x: *privparams) (void | error) = {
201 x.p = ltrim(x.p);
202 x.q = ltrim(x.q);
203 x.dp = ltrim(x.dp);
204 x.dq = ltrim(x.dq);
205 x.iq = ltrim(x.iq);
206
207 if (len(privkey) < privkey_len(x)
208 || len(x.p) > types::U16_MAX
209 || len(x.q) > types::U16_MAX
210 || len(x.dp) > types::U16_MAX
211 || len(x.dq) > types::U16_MAX
212 || len(x.iq) > types::U16_MAX) {
213 return errors::overflow;
214 };
215
216 if (len(x.p) == 0 || len(x.q) == 0 || len(x.iq) == 0
217 || !isodd(x.p) || !isodd(x.q)) {
218 return errors::invalid;
219 };
220 };
221
222 fn isodd(x: []u8) bool = {
223 assert(len(x) > 0);
224 return x[len(x)-1] & 1 == 1;
225 };
226
227 fn privkey_writehead(
228 privkey: []u8,
229 p: *privparams,
230 n: []u8...
231 ) (size | error) = {
232 assert(len(n) <= 1);
233 const nbitlen = if (len(n) == 1) bitlen(n[0]) else p.nbitlen;
234 if (nbitlen > types::U16_MAX) {
235 return errors::overflow;
236 };
237 if (nbitlen < MINBITSZ) {
238 return errors::invalid;
239 };
240
241 let w = memio::fixed(privkey);
242 let lenbuf: [2]u8 = [0...];
243 endian::beputu16(lenbuf, nbitlen: u16);
244 return io::write(&w, lenbuf)!;
245 };
246
247 // Initializes the private key 'privkey' using the values from 'x' and the
248 // secret exponent 'd'. 'dp' and 'dq' will be derived from 'p' and 'q' of 'x'.
249 // 'nbitlen' of 'x' may be omitted, if the modulus 'n' is passed. 'x' must
250 // provide 'iq'.
251 //
252 // In case of invalid parameters or if the key is too small, [[errors::invalid]]
253 // is returned. If the key does not fit 'privkey', [[errors::overflow]] is
254 // returned. On success the number of bytes written to 'privkey' is returend.
255 export fn privkey_initd(
256 privkey: []u8,
257 x: privparams,
258 d: []u8,
259 n: []u8...
260 ) (size | error) = {
261 privkey_normalize(privkey, &x)?;
262
263 let s = privkey_writehead(privkey, &x, n...)?;
264
265 // the order is important. The dmod operation uses the space for the
266 // remaining factors as buffer.
267 s += privkey_dmod(privkey[s..], d, x.p);
268 s += privkey_dmod(privkey[s..], d, x.q);
269
270 let w = memio::fixed(privkey[s..]);
271 s += writeslice(&w, x.iq)!;
272 s += writeslice(&w, x.p)!;
273 s += writeslice(&w, x.q)!;
274
275 // zero out tail in case the privkey_dmod operation left buffered values
276 bytes::zero(privkey[s..]);
277 return s;
278 };
279
280 // Calculates 'x' = 'd' mod 'y' - 1 and stores 'x' into 'out' preceeding a
281 // u16 len. 'out' will also be used as a calculation buffer. 'y' must be odd.
282 fn privkey_dmod(out: []u8, d: []u8, y: []u8) size = {
283 const encwordlen = bigint::encodelen(y);
284 const enclen = encwordlen * size(bigint::word);
285 const xlen = len(y);
286
287 assert(len(out) >= 2 + xlen + 2 * enclen);
288 assert(isodd(y));
289
290 let buf = out[2 + xlen..];
291 // XXX: this may be only done once for both dp and dq
292 let by = (buf[..enclen]: *[*]bigint::word)[..encwordlen];
293 bigint::encode(by, y);
294 bigint::decrodd(by);
295
296 let bx = (buf[enclen..2 * enclen]: *[*]bigint::word)[..encwordlen];
297 bigint::encodereduce(bx, d, by);
298
299 out[0] = (xlen >> 8): u8;
300 out[1] = xlen: u8;
301 bigint::decode(out[2..2 + xlen], bx);
302 return 2 + xlen;
303 };
304
305 // Returns the private key parameters borrowed from 'privkey'.
306 export fn privkey_params(privkey: []u8) privparams = {
307 let keybuf = privkey[2..];
308 return privparams {
309 nbitlen = privkey_nbitlen(privkey),
310 dp = nextslice(&keybuf),
311 dq = nextslice(&keybuf),
312 iq = nextslice(&keybuf),
313 p = nextslice(&keybuf),
314 q = nextslice(&keybuf),
315 ...
316 };
317 };
318
319 // Returns the length of the modulus 'n'.
320 export fn privkey_nbitlen(privkey: []u8) size = {
321 return endian::begetu16(privkey[0..2]);
322 };
323
324 // Returns the number of bytes that are required to store a value modulo 'n'.
325 export fn privkey_nsize(privkey: []u8) size = {
326 return (privkey_nbitlen(privkey) + 7) / 8;
327 };