contrib/bearssl/src/rsa/rsa_i62_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 #if BR_INT128 || BR_UMUL128
  28
  29 #define U      (2 + ((BR_MAX_RSA_FACTOR + 30) / 31))
  30 #define TLEN   (4 * U)  /* TLEN is counted in 64-bit words */
  31
  32 /* see bearssl_rsa.h */
  33 uint32_t
  34 br_rsa_i62_private(unsigned char *x, const br_rsa_private_key *sk)
  35 {
  36         const unsigned char *p, *q;
  37         size_t plen, qlen;
  38         size_t fwlen;
  39         uint32_t p0i, q0i;
  40         size_t xlen, u;
  41         uint64_t tmp[TLEN];
  42         long z;
  43         uint32_t *mp, *mq, *s1, *s2, *t1, *t2, *t3;
  44         uint32_t r;
  45
  46         /*
  47          * Compute the actual lengths of p and q, in bytes.
  48          * These lengths are not considered secret (we cannot really hide
  49          * them anyway in constant-time code).
  50          */
  51         p = sk->p;
  52         plen = sk->plen;
  53         while (plen > 0 && *p == 0) {
  54                 p ++;
  55                 plen --;
  56         }
  57         q = sk->q;
  58         qlen = sk->qlen;
  59         while (qlen > 0 && *q == 0) {
  60                 q ++;
  61                 qlen --;
  62         }
  63
  64         /*
  65          * Compute the maximum factor length, in words.
  66          */
  67         z = (long)(plen > qlen ? plen : qlen) << 3;
  68         fwlen = 1;
  69         while (z > 0) {
  70                 z -= 31;
  71                 fwlen ++;
  72         }
  73
  74         /*
  75          * Convert size to 62-bit words.
  76          */
  77         fwlen = (fwlen + 1) >> 1;
  78
  79         /*
  80          * We need to fit at least 6 values in the stack buffer.
  81          */
  82         if (6 * fwlen > TLEN) {
  83                 return 0;
  84         }
  85
  86         /*
  87          * Compute signature length (in bytes).
  88          */
  89         xlen = (sk->n_bitlen + 7) >> 3;
  90
  91         /*
  92          * Decode q.
  93          */
  94         mq = (uint32_t *)tmp;
  95         br_i31_decode(mq, q, qlen);
  96
  97         /*
  98          * Decode p.
  99          */
 100         t1 = (uint32_t *)(tmp + fwlen);
 101         br_i31_decode(t1, p, plen);
 102
 103         /*
 104          * Compute the modulus (product of the two factors), to compare
 105          * it with the source value. We use br_i31_mulacc(), since it's
 106          * already used later on.
 107          */
 108         t2 = (uint32_t *)(tmp + 2 * fwlen);
 109         br_i31_zero(t2, mq[0]);
 110         br_i31_mulacc(t2, mq, t1);
 111
 112         /*
 113          * We encode the modulus into bytes, to perform the comparison
 114          * with bytes. We know that the product length, in bytes, is
 115          * exactly xlen.
 116          * The comparison actually computes the carry when subtracting
 117          * the modulus from the source value; that carry must be 1 for
 118          * a value in the correct range. We keep it in r, which is our
 119          * accumulator for the error code.
 120          */
 121         t3 = (uint32_t *)(tmp + 4 * fwlen);
 122         br_i31_encode(t3, xlen, t2);
 123         u = xlen;
 124         r = 0;
 125         while (u > 0) {
 126                 uint32_t wn, wx;
 127
 128                 u --;
 129                 wn = ((unsigned char *)t3)[u];
 130                 wx = x[u];
 131                 r = ((wx - (wn + r)) >> 8) & 1;
 132         }
 133
 134         /*
 135          * Move the decoded p to another temporary buffer.
 136          */
 137         mp = (uint32_t *)(tmp + 2 * fwlen);
 138         memmove(mp, t1, 2 * fwlen * sizeof *t1);
 139
 140         /*
 141          * Compute s2 = x^dq mod q.
 142          */
 143         q0i = br_i31_ninv31(mq[1]);
 144         s2 = (uint32_t *)(tmp + fwlen);
 145         br_i31_decode_reduce(s2, x, xlen, mq);
 146         r &= br_i62_modpow_opt(s2, sk->dq, sk->dqlen, mq, q0i,
 147                 tmp + 3 * fwlen, TLEN - 3 * fwlen);
 148
 149         /*
 150          * Compute s1 = x^dp mod p.
 151          */
 152         p0i = br_i31_ninv31(mp[1]);
 153         s1 = (uint32_t *)(tmp + 3 * fwlen);
 154         br_i31_decode_reduce(s1, x, xlen, mp);
 155         r &= br_i62_modpow_opt(s1, sk->dp, sk->dplen, mp, p0i,
 156                 tmp + 4 * fwlen, TLEN - 4 * fwlen);
 157
 158         /*
 159          * Compute:
 160          *   h = (s1 - s2)*(1/q) mod p
 161          * s1 is an integer modulo p, but s2 is modulo q. PKCS#1 is
 162          * unclear about whether p may be lower than q (some existing,
 163          * widely deployed implementations of RSA don't tolerate p < q),
 164          * but we want to support that occurrence, so we need to use the
 165          * reduction function.
 166          *
 167          * Since we use br_i31_decode_reduce() for iq (purportedly, the
 168          * inverse of q modulo p), we also tolerate improperly large
 169          * values for this parameter.
 170          */
 171         t1 = (uint32_t *)(tmp + 4 * fwlen);
 172         t2 = (uint32_t *)(tmp + 5 * fwlen);
 173         br_i31_reduce(t2, s2, mp);
 174         br_i31_add(s1, mp, br_i31_sub(s1, t2, 1));
 175         br_i31_to_monty(s1, mp);
 176         br_i31_decode_reduce(t1, sk->iq, sk->iqlen, mp);
 177         br_i31_montymul(t2, s1, t1, mp, p0i);
 178
 179         /*
 180          * h is now in t2. We compute the final result:
 181          *   s = s2 + q*h
 182          * All these operations are non-modular.
 183          *
 184          * We need mq, s2 and t2. We use the t3 buffer as destination.
 185          * The buffers mp, s1 and t1 are no longer needed, so we can
 186          * reuse them for t3. Moreover, the first step of the computation
 187          * is to copy s2 into t3, after which s2 is not needed. Right
 188          * now, mq is in slot 0, s2 is in slot 1, and t2 is in slot 5.
 189          * Therefore, we have ample room for t3 by simply using s2.
 190          */
 191         t3 = s2;
 192         br_i31_mulacc(t3, mq, t2);
 193
 194         /*
 195          * Encode the result. Since we already checked the value of xlen,
 196          * we can just use it right away.
 197          */
 198         br_i31_encode(x, xlen, t3);
 199
 200         /*
 201          * The only error conditions remaining at that point are invalid
 202          * values for p and q (even integers).
 203          */
 204         return p0i & q0i & r;
 205 }
 206
 207 /* see bearssl_rsa.h */
 208 br_rsa_private
 209 br_rsa_i62_private_get(void)
 210 {
 211         return &br_rsa_i62_private;
 212 }
 213
 214 #else
 215
 216 /* see bearssl_rsa.h */
 217 br_rsa_private
 218 br_rsa_i62_private_get(void)
 219 {
 220         return 0;
 221 }
 222
 223 #endif