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