keys.ha (9044B)
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 for (s[0] == 0) { 118 s = s[1..]; 119 }; 120 121 return countbits(s[0]) + 8 * (len(s) - 1); 122 }; 123 124 fn countbits(x: u8) size = { 125 let k: u32 = nequ32(x, 0); 126 let c: u32 = 0; 127 128 c = gtu32(x, 0x0f); 129 x = muxu32(c, x >> 4, x): u8; 130 k += c << 2; 131 132 c = gtu32(x, 0x03); 133 x = muxu32(c, x >> 2, x): u8; 134 k += c << 1; 135 136 k += gtu32(x, 0x01); 137 138 return k; 139 }; 140 141 @test fn countbits() void = { 142 assert(countbits(0xf0) == 8); 143 assert(countbits(0x70) == 7); 144 assert(countbits(0x30) == 6); 145 assert(countbits(0x10) == 5); 146 assert(countbits(0x08) == 4); 147 assert(countbits(0x04) == 3); 148 assert(countbits(0x03) == 2); 149 assert(countbits(0x01) == 1); 150 assert(countbits(0x00) == 0); 151 }; 152 153 // Returns the public key parameters, borrowed from given 'pubkey'. 154 export fn pubkey_params(pubkey: []u8) pubparams = { 155 let keybuf = pubkey; 156 return pubparams { 157 e = nextslice(&keybuf), 158 n = nextslice(&keybuf), 159 }; 160 }; 161 162 fn nextslice(key: *[]u8) []u8 = { 163 const l = endian::begetu16(key[..2]); 164 let s = key[2..2 + l]; 165 *key = key[2 + l..]; 166 return s; 167 }; 168 169 // Size required to store a private key of [[BITSZ]] length. 170 export def PRIVKEYSZ: size = 13 + (MAXFACTOR >> 3) * 5; 171 172 fn privkey_len(x: *privparams) size = 173 13z + len(x.p) + len(x.q) + len(x.dp) + len(x.dq) + len(x.iq); 174 175 // Initializes the private key 'privkey' using the values from 'x'. 'nbitlen' of 176 // 'x' may be omitted, if the modulus 'n' is passed. All other values of 'x' 177 // must be present. If 'x' is missing 'dp' and 'dq' use [[privkey_initd]]. 178 // 179 // In case of invalid parameters or if the key is too small, [[errors::invalid]] 180 // is returned. If the key does not fit 'privkey', [[errors::overflow]] is 181 // returned. On success the number of bytes written to 'privkey' is returned. 182 export fn privkey_init(privkey: []u8, x: privparams, n: []u8...) (size | error) = { 183 privkey_normalize(privkey, &x)?; 184 185 if (len(x.dp) == 0 || len(x.dq) == 0) { 186 return errors::invalid; 187 }; 188 189 let s = privkey_writehead(privkey, &x, n...)?; 190 let w = memio::fixed(privkey[s..]); 191 192 s += writeslice(&w, x.dp)!; 193 s += writeslice(&w, x.dq)!; 194 195 s += writeslice(&w, x.iq)!; 196 s += writeslice(&w, x.p)!; 197 s += writeslice(&w, x.q)!; 198 return s; 199 }; 200 201 // Trims key parameters and also does basic key checks. 202 fn privkey_normalize(privkey: []u8, x: *privparams) (void | error) = { 203 x.p = ltrim(x.p); 204 x.q = ltrim(x.q); 205 x.dp = ltrim(x.dp); 206 x.dq = ltrim(x.dq); 207 x.iq = ltrim(x.iq); 208 209 if (len(privkey) < privkey_len(x) 210 || len(x.p) > types::U16_MAX 211 || len(x.q) > types::U16_MAX 212 || len(x.dp) > types::U16_MAX 213 || len(x.dq) > types::U16_MAX 214 || len(x.iq) > types::U16_MAX) { 215 return errors::overflow; 216 }; 217 218 if (len(x.p) == 0 || len(x.q) == 0 || len(x.iq) == 0 219 || !isodd(x.p) || !isodd(x.q)) { 220 return errors::invalid; 221 }; 222 }; 223 224 fn isodd(x: []u8) bool = { 225 assert(len(x) > 0); 226 return x[len(x)-1] & 1 == 1; 227 }; 228 229 fn privkey_writehead( 230 privkey: []u8, 231 p: *privparams, 232 n: []u8... 233 ) (size | error) = { 234 assert(len(n) <= 1); 235 const nbitlen = if (len(n) == 1) bitlen(n[0]) else p.nbitlen; 236 if (nbitlen > types::U16_MAX) { 237 return errors::overflow; 238 }; 239 if (nbitlen < MINBITSZ) { 240 return errors::invalid; 241 }; 242 243 let w = memio::fixed(privkey); 244 let lenbuf: [2]u8 = [0...]; 245 endian::beputu16(lenbuf, nbitlen: u16); 246 return io::write(&w, lenbuf)!; 247 }; 248 249 // Initializes the private key 'privkey' using the values from 'x' and the 250 // secret exponent 'd'. 'dp' and 'dq' will be derived from 'p' and 'q' of 'x'. 251 // 'nbitlen' of 'x' may be omitted, if the modulus 'n' is passed. 'x' must 252 // provide 'iq'. 253 // 254 // In case of invalid parameters or if the key is too small, [[errors::invalid]] 255 // is returned. If the key does not fit 'privkey', [[errors::overflow]] is 256 // returned. On success the number of bytes written to 'privkey' is returend. 257 export fn privkey_initd( 258 privkey: []u8, 259 x: privparams, 260 d: []u8, 261 n: []u8... 262 ) (size | error) = { 263 privkey_normalize(privkey, &x)?; 264 265 let s = privkey_writehead(privkey, &x, n...)?; 266 267 // the order is important. The dmod operation uses the space for the 268 // remaining factors as buffer. 269 s += privkey_dmod(privkey[s..], d, x.p); 270 s += privkey_dmod(privkey[s..], d, x.q); 271 272 let w = memio::fixed(privkey[s..]); 273 s += writeslice(&w, x.iq)!; 274 s += writeslice(&w, x.p)!; 275 s += writeslice(&w, x.q)!; 276 277 // zero out tail in case the privkey_dmod operation left buffered values 278 bytes::zero(privkey[s..]); 279 return s; 280 }; 281 282 // Calculates 'x' = 'd' mod 'y' - 1 and stores 'x' into 'out' preceeding a 283 // u16 len. 'out' will also be used as a calculation buffer. 'y' must be odd. 284 fn privkey_dmod(out: []u8, d: []u8, y: []u8) size = { 285 const encwordlen = bigint::encodelen(y); 286 const enclen = encwordlen * size(bigint::word); 287 const xlen = len(y); 288 289 assert(len(out) >= 2 + xlen + 2 * enclen); 290 assert(isodd(y)); 291 292 let buf = out[2 + xlen..]; 293 // XXX: this may be only done once for both dp and dq 294 let by = (buf[..enclen]: *[*]bigint::word)[..encwordlen]; 295 bigint::encode(by, y); 296 bigint::decrodd(by); 297 298 let bx = (buf[enclen..2 * enclen]: *[*]bigint::word)[..encwordlen]; 299 bigint::encodereduce(bx, d, by); 300 301 out[0] = (xlen >> 8): u8; 302 out[1] = xlen: u8; 303 bigint::decode(out[2..2 + xlen], bx); 304 return 2 + xlen; 305 }; 306 307 // Returns the private key parameters borrowed from 'privkey'. 308 export fn privkey_params(privkey: []u8) privparams = { 309 let keybuf = privkey[2..]; 310 return privparams { 311 nbitlen = privkey_nbitlen(privkey), 312 dp = nextslice(&keybuf), 313 dq = nextslice(&keybuf), 314 iq = nextslice(&keybuf), 315 p = nextslice(&keybuf), 316 q = nextslice(&keybuf), 317 ... 318 }; 319 }; 320 321 // Returns the length of the modulus 'n'. 322 export fn privkey_nbitlen(privkey: []u8) size = { 323 return endian::begetu16(privkey[0..2]); 324 }; 325 326 // Returns the number of bytes that are required to store a value modulo 'n'. 327 export fn privkey_nsize(privkey: []u8) size = { 328 return (privkey_nbitlen(privkey) + 7) / 8; 329 };