contrib/bearssl/src/rsa/rsa_i32_priv.c

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