1*0957b409SSimon J. Gerraty /* 2*0957b409SSimon J. Gerraty * Copyright (c) 2016 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 #define U (1 + (BR_MAX_RSA_FACTOR >> 5)) 28*0957b409SSimon J. Gerraty 29*0957b409SSimon J. Gerraty /* see bearssl_rsa.h */ 30*0957b409SSimon J. Gerraty uint32_t 31*0957b409SSimon J. Gerraty br_rsa_i32_private(unsigned char *x, const br_rsa_private_key *sk) 32*0957b409SSimon J. Gerraty { 33*0957b409SSimon J. Gerraty const unsigned char *p, *q; 34*0957b409SSimon J. Gerraty size_t plen, qlen; 35*0957b409SSimon J. Gerraty uint32_t tmp[6 * U]; 36*0957b409SSimon J. Gerraty uint32_t *mp, *mq, *s1, *s2, *t1, *t2, *t3; 37*0957b409SSimon J. Gerraty uint32_t p0i, q0i; 38*0957b409SSimon J. Gerraty size_t xlen, u; 39*0957b409SSimon J. Gerraty uint32_t r; 40*0957b409SSimon J. Gerraty 41*0957b409SSimon J. Gerraty /* 42*0957b409SSimon J. Gerraty * All our temporary buffers are from the tmp[] array. 43*0957b409SSimon J. Gerraty * 44*0957b409SSimon J. Gerraty * The mp, mq, s1, s2, t1 and t2 buffers are large enough to 45*0957b409SSimon J. Gerraty * contain a RSA factor. The t3 buffer can contain a complete 46*0957b409SSimon J. Gerraty * RSA modulus. t3 shares its storage space with s2, s1 and t1, 47*0957b409SSimon J. Gerraty * in that order (this is important, see below). 48*0957b409SSimon J. Gerraty */ 49*0957b409SSimon J. Gerraty mq = tmp; 50*0957b409SSimon J. Gerraty mp = tmp + U; 51*0957b409SSimon J. Gerraty t2 = tmp + 2 * U; 52*0957b409SSimon J. Gerraty s2 = tmp + 3 * U; 53*0957b409SSimon J. Gerraty s1 = tmp + 4 * U; 54*0957b409SSimon J. Gerraty t1 = tmp + 5 * U; 55*0957b409SSimon J. Gerraty t3 = s2; 56*0957b409SSimon J. Gerraty 57*0957b409SSimon J. Gerraty /* 58*0957b409SSimon J. Gerraty * Compute the actual lengths (in bytes) of p and q, and check 59*0957b409SSimon J. Gerraty * that they fit within our stack buffers. 60*0957b409SSimon J. Gerraty */ 61*0957b409SSimon J. Gerraty p = sk->p; 62*0957b409SSimon J. Gerraty plen = sk->plen; 63*0957b409SSimon J. Gerraty while (plen > 0 && *p == 0) { 64*0957b409SSimon J. Gerraty p ++; 65*0957b409SSimon J. Gerraty plen --; 66*0957b409SSimon J. Gerraty } 67*0957b409SSimon J. Gerraty q = sk->q; 68*0957b409SSimon J. Gerraty qlen = sk->qlen; 69*0957b409SSimon J. Gerraty while (qlen > 0 && *q == 0) { 70*0957b409SSimon J. Gerraty q ++; 71*0957b409SSimon J. Gerraty qlen --; 72*0957b409SSimon J. Gerraty } 73*0957b409SSimon J. Gerraty if (plen > (BR_MAX_RSA_FACTOR >> 3) 74*0957b409SSimon J. Gerraty || qlen > (BR_MAX_RSA_FACTOR >> 3)) 75*0957b409SSimon J. Gerraty { 76*0957b409SSimon J. Gerraty return 0; 77*0957b409SSimon J. Gerraty } 78*0957b409SSimon J. Gerraty 79*0957b409SSimon J. Gerraty /* 80*0957b409SSimon J. Gerraty * Decode p and q. 81*0957b409SSimon J. Gerraty */ 82*0957b409SSimon J. Gerraty br_i32_decode(mp, p, plen); 83*0957b409SSimon J. Gerraty br_i32_decode(mq, q, qlen); 84*0957b409SSimon J. Gerraty 85*0957b409SSimon J. Gerraty /* 86*0957b409SSimon J. Gerraty * Recompute modulus, to compare with the source value. 87*0957b409SSimon J. Gerraty */ 88*0957b409SSimon J. Gerraty br_i32_zero(t2, mp[0]); 89*0957b409SSimon J. Gerraty br_i32_mulacc(t2, mp, mq); 90*0957b409SSimon J. Gerraty xlen = (sk->n_bitlen + 7) >> 3; 91*0957b409SSimon J. Gerraty br_i32_encode(t2 + 2 * U, xlen, t2); 92*0957b409SSimon J. Gerraty u = xlen; 93*0957b409SSimon J. Gerraty r = 0; 94*0957b409SSimon J. Gerraty while (u > 0) { 95*0957b409SSimon J. Gerraty uint32_t wn, wx; 96*0957b409SSimon J. Gerraty 97*0957b409SSimon J. Gerraty u --; 98*0957b409SSimon J. Gerraty wn = ((unsigned char *)(t2 + 2 * U))[u]; 99*0957b409SSimon J. Gerraty wx = x[u]; 100*0957b409SSimon J. Gerraty r = ((wx - (wn + r)) >> 8) & 1; 101*0957b409SSimon J. Gerraty } 102*0957b409SSimon J. Gerraty 103*0957b409SSimon J. Gerraty /* 104*0957b409SSimon J. Gerraty * Compute s1 = x^dp mod p. 105*0957b409SSimon J. Gerraty */ 106*0957b409SSimon J. Gerraty p0i = br_i32_ninv32(mp[1]); 107*0957b409SSimon J. Gerraty br_i32_decode_reduce(s1, x, xlen, mp); 108*0957b409SSimon J. Gerraty br_i32_modpow(s1, sk->dp, sk->dplen, mp, p0i, t1, t2); 109*0957b409SSimon J. Gerraty 110*0957b409SSimon J. Gerraty /* 111*0957b409SSimon J. Gerraty * Compute s2 = x^dq mod q. 112*0957b409SSimon J. Gerraty */ 113*0957b409SSimon J. Gerraty q0i = br_i32_ninv32(mq[1]); 114*0957b409SSimon J. Gerraty br_i32_decode_reduce(s2, x, xlen, mq); 115*0957b409SSimon J. Gerraty br_i32_modpow(s2, sk->dq, sk->dqlen, mq, q0i, t1, t2); 116*0957b409SSimon J. Gerraty 117*0957b409SSimon J. Gerraty /* 118*0957b409SSimon J. Gerraty * Compute: 119*0957b409SSimon J. Gerraty * h = (s1 - s2)*(1/q) mod p 120*0957b409SSimon J. Gerraty * s1 is an integer modulo p, but s2 is modulo q. PKCS#1 is 121*0957b409SSimon J. Gerraty * unclear about whether p may be lower than q (some existing, 122*0957b409SSimon J. Gerraty * widely deployed implementations of RSA don't tolerate p < q), 123*0957b409SSimon J. Gerraty * but we want to support that occurrence, so we need to use the 124*0957b409SSimon J. Gerraty * reduction function. 125*0957b409SSimon J. Gerraty * 126*0957b409SSimon J. Gerraty * Since we use br_i32_decode_reduce() for iq (purportedly, the 127*0957b409SSimon J. Gerraty * inverse of q modulo p), we also tolerate improperly large 128*0957b409SSimon J. Gerraty * values for this parameter. 129*0957b409SSimon J. Gerraty */ 130*0957b409SSimon J. Gerraty br_i32_reduce(t2, s2, mp); 131*0957b409SSimon J. Gerraty br_i32_add(s1, mp, br_i32_sub(s1, t2, 1)); 132*0957b409SSimon J. Gerraty br_i32_to_monty(s1, mp); 133*0957b409SSimon J. Gerraty br_i32_decode_reduce(t1, sk->iq, sk->iqlen, mp); 134*0957b409SSimon J. Gerraty br_i32_montymul(t2, s1, t1, mp, p0i); 135*0957b409SSimon J. Gerraty 136*0957b409SSimon J. Gerraty /* 137*0957b409SSimon J. Gerraty * h is now in t2. We compute the final result: 138*0957b409SSimon J. Gerraty * s = s2 + q*h 139*0957b409SSimon J. Gerraty * All these operations are non-modular. 140*0957b409SSimon J. Gerraty * 141*0957b409SSimon J. Gerraty * We need mq, s2 and t2. We use the t3 buffer as destination. 142*0957b409SSimon J. Gerraty * The buffers mp, s1 and t1 are no longer needed. Moreover, 143*0957b409SSimon J. Gerraty * the first step is to copy s2 into the destination buffer t3. 144*0957b409SSimon J. Gerraty * We thus arranged for t3 to actually share space with s2, and 145*0957b409SSimon J. Gerraty * to be followed by the space formerly used by s1 and t1. 146*0957b409SSimon J. Gerraty */ 147*0957b409SSimon J. Gerraty br_i32_mulacc(t3, mq, t2); 148*0957b409SSimon J. Gerraty 149*0957b409SSimon J. Gerraty /* 150*0957b409SSimon J. Gerraty * Encode the result. Since we already checked the value of xlen, 151*0957b409SSimon J. Gerraty * we can just use it right away. 152*0957b409SSimon J. Gerraty */ 153*0957b409SSimon J. Gerraty br_i32_encode(x, xlen, t3); 154*0957b409SSimon J. Gerraty 155*0957b409SSimon J. Gerraty /* 156*0957b409SSimon J. Gerraty * The only error conditions remaining at that point are invalid 157*0957b409SSimon J. Gerraty * values for p and q (even integers). 158*0957b409SSimon J. Gerraty */ 159*0957b409SSimon J. Gerraty return p0i & q0i & r; 160*0957b409SSimon J. Gerraty } 161