_ Git - BearSSL/blob - 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;
  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          * Compute s2 = x^dq mod q.
  99          */
 100         q0i = br_i31_ninv31(mq[1]);
 101         s2 = (uint32_t *)(tmp + fwlen);
 102         br_i31_decode_reduce(s2, x, xlen, mq);
 103         r = br_i62_modpow_opt(s2, sk->dq, sk->dqlen, mq, q0i,
 104                 tmp + 2 * fwlen, TLEN - 2 * fwlen);
 105
 106         /*
 107          * Decode p.
 108          */
 109         mp = (uint32_t *)(tmp + 2 * fwlen);
 110         br_i31_decode(mp, p, plen);
 111
 112         /*
 113          * Compute s1 = x^dp mod p.
 114          */
 115         p0i = br_i31_ninv31(mp[1]);
 116         s1 = (uint32_t *)(tmp + 3 * fwlen);
 117         br_i31_decode_reduce(s1, x, xlen, mp);
 118         r &= br_i62_modpow_opt(s1, sk->dp, sk->dplen, mp, p0i,
 119                 tmp + 4 * fwlen, TLEN - 4 * fwlen);
 120
 121         /*
 122          * Compute:
 123          *   h = (s1 - s2)*(1/q) mod p
 124          * s1 is an integer modulo p, but s2 is modulo q. PKCS#1 is
 125          * unclear about whether p may be lower than q (some existing,
 126          * widely deployed implementations of RSA don't tolerate p < q),
 127          * but we want to support that occurrence, so we need to use the
 128          * reduction function.
 129          *
 130          * Since we use br_i31_decode_reduce() for iq (purportedly, the
 131          * inverse of q modulo p), we also tolerate improperly large
 132          * values for this parameter.
 133          */
 134         t1 = (uint32_t *)(tmp + 4 * fwlen);
 135         t2 = (uint32_t *)(tmp + 5 * fwlen);
 136         br_i31_reduce(t2, s2, mp);
 137         br_i31_add(s1, mp, br_i31_sub(s1, t2, 1));
 138         br_i31_to_monty(s1, mp);
 139         br_i31_decode_reduce(t1, sk->iq, sk->iqlen, mp);
 140         br_i31_montymul(t2, s1, t1, mp, p0i);
 141
 142         /*
 143          * h is now in t2. We compute the final result:
 144          *   s = s2 + q*h
 145          * All these operations are non-modular.
 146          *
 147          * We need mq, s2 and t2. We use the t3 buffer as destination.
 148          * The buffers mp, s1 and t1 are no longer needed, so we can
 149          * reuse them for t3. Moreover, the first step of the computation
 150          * is to copy s2 into t3, after which s2 is not needed. Right
 151          * now, mq is in slot 0, s2 is in slot 1, and t2 is in slot 5.
 152          * Therefore, we have ample room for t3 by simply using s2.
 153          */
 154         t3 = s2;
 155         br_i31_mulacc(t3, mq, t2);
 156
 157         /*
 158          * Encode the result. Since we already checked the value of xlen,
 159          * we can just use it right away.
 160          */
 161         br_i31_encode(x, xlen, t3);
 162
 163         /*
 164          * The only error conditions remaining at that point are invalid
 165          * values for p and q (even integers).
 166          */
 167         return p0i & q0i & r;
 168 }
 169
 170 /* see bearssl_rsa.h */
 171 br_rsa_private
 172 br_rsa_i62_private_get(void)
 173 {
 174         return &br_rsa_i62_private;
 175 }
 176
 177 #else
 178
 179 /* see bearssl_rsa.h */
 180 br_rsa_private
 181 br_rsa_i62_private_get(void)
 182 {
 183         return 0;
 184 }
 185
 186 #endif