1 /* 2 * Copyright (c) 2018 Thomas Pornin <pornin@bolet.org> 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining 5 * a copy of this software and associated documentation files (the 6 * "Software"), to deal in the Software without restriction, including 7 * without limitation the rights to use, copy, modify, merge, publish, 8 * distribute, sublicense, and/or sell copies of the Software, and to 9 * permit persons to whom the Software is furnished to do so, subject to 10 * the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be 13 * included in all copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 */ 24 25 #include "inner.h" 26 27 /* 28 * Recompute public exponent, based on factor p and reduced private 29 * exponent dp. 30 */ 31 static uint32_t 32 get_pubexp(const unsigned char *pbuf, size_t plen, 33 const unsigned char *dpbuf, size_t dplen) 34 { 35 /* 36 * dp is the inverse of e modulo p-1. If p = 3 mod 4, then 37 * p-1 = 2*((p-1)/2). Taken modulo 2, e is odd and has inverse 1; 38 * thus, dp must be odd. 39 * 40 * We compute the inverse of dp modulo (p-1)/2. This requires 41 * first reducing dp modulo (p-1)/2 (this can be done with a 42 * conditional subtract, no need to use the generic modular 43 * reduction function); then, we use moddiv. 44 */ 45 46 uint32_t tmp[6 * ((BR_MAX_RSA_FACTOR + 61) / 31)]; 47 uint32_t *p, *dp, *x; 48 size_t len; 49 uint32_t e; 50 51 /* 52 * Compute actual factor length (in bytes) and check that it fits 53 * under our size constraints. 54 */ 55 while (plen > 0 && *pbuf == 0) { 56 pbuf ++; 57 plen --; 58 } 59 if (plen == 0 || plen < 5 || plen > (BR_MAX_RSA_FACTOR / 8)) { 60 return 0; 61 } 62 63 /* 64 * Compute actual reduced exponent length (in bytes) and check that 65 * it is not longer than p. 66 */ 67 while (dplen > 0 && *dpbuf == 0) { 68 dpbuf ++; 69 dplen --; 70 } 71 if (dplen > plen || dplen == 0 72 || (dplen == plen && dpbuf[0] > pbuf[0])) 73 { 74 return 0; 75 } 76 77 /* 78 * Verify that p = 3 mod 4 and that dp is odd. 79 */ 80 if ((pbuf[plen - 1] & 3) != 3 || (dpbuf[dplen - 1] & 1) != 1) { 81 return 0; 82 } 83 84 /* 85 * Decode p and compute (p-1)/2. 86 */ 87 p = tmp; 88 br_i31_decode(p, pbuf, plen); 89 len = (p[0] + 63) >> 5; 90 br_i31_rshift(p, 1); 91 92 /* 93 * Decode dp and make sure its announced bit length matches that of 94 * p (we already know that the size of dp, in bits, does not exceed 95 * the size of p, so we just have to copy the header word). 96 */ 97 dp = p + len; 98 memset(dp, 0, len * sizeof *dp); 99 br_i31_decode(dp, dpbuf, dplen); 100 dp[0] = p[0]; 101 102 /* 103 * Subtract (p-1)/2 from dp if necessary. 104 */ 105 br_i31_sub(dp, p, NOT(br_i31_sub(dp, p, 0))); 106 107 /* 108 * If another subtraction is needed, then this means that the 109 * value was invalid. We don't care to leak information about 110 * invalid keys. 111 */ 112 if (br_i31_sub(dp, p, 0) == 0) { 113 return 0; 114 } 115 116 /* 117 * Invert dp modulo (p-1)/2. If the inversion fails, then the 118 * key value was invalid. 119 */ 120 x = dp + len; 121 br_i31_zero(x, p[0]); 122 x[1] = 1; 123 if (br_i31_moddiv(x, dp, p, br_i31_ninv31(p[1]), x + len) == 0) { 124 return 0; 125 } 126 127 /* 128 * We now have an inverse. We must set it to zero (error) if its 129 * length is greater than 32 bits and/or if it is an even integer. 130 * Take care that the bit_length function returns an encoded 131 * bit length. 132 */ 133 e = (uint32_t)x[1] | ((uint32_t)x[2] << 31); 134 e &= -LT(br_i31_bit_length(x + 1, len - 1), 34); 135 e &= -(e & 1); 136 return e; 137 } 138 139 /* see bearssl_rsa.h */ 140 uint32_t 141 br_rsa_i31_compute_pubexp(const br_rsa_private_key *sk) 142 { 143 /* 144 * Get the public exponent from both p and q. This is the right 145 * exponent if we get twice the same value. 146 */ 147 uint32_t ep, eq; 148 149 ep = get_pubexp(sk->p, sk->plen, sk->dp, sk->dplen); 150 eq = get_pubexp(sk->q, sk->qlen, sk->dq, sk->dqlen); 151 return ep & -EQ(ep, eq); 152 } 153