Home | History | Annotate | Download | only in libmincrypt 
      1 /* rsa.c
      2 **
      3 ** Copyright 2008, The Android Open Source Project
      4 **
      5 ** Redistribution and use in source and binary forms, with or without
      6 ** modification, are permitted provided that the following conditions are met:
      7 **     * Redistributions of source code must retain the above copyright
      8 **       notice, this list of conditions and the following disclaimer.
      9 **     * Redistributions in binary form must reproduce the above copyright
     10 **       notice, this list of conditions and the following disclaimer in the
     11 **       documentation and/or other materials provided with the distribution.
     12 **     * Neither the name of Google Inc. nor the names of its contributors may
     13 **       be used to endorse or promote products derived from this software
     14 **       without specific prior written permission.
     15 **
     16 ** THIS SOFTWARE IS PROVIDED BY Google Inc. ``AS IS'' AND ANY EXPRESS OR
     17 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
     18 ** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
     19 ** EVENT SHALL Google Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     20 ** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     21 ** PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
     22 ** OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
     23 ** WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
     24 ** OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
     25 ** ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     26 */
     27 
     28 #include "mincrypt/rsa.h"
     29 #include "mincrypt/sha.h"
     30 
     31 /* a[] -= mod */
     32 static void subM(const RSAPublicKey *key, uint32_t *a) {
     33     int64_t A = 0;
     34     int i;
     35     for (i = 0; i < key->len; ++i) {
     36         A += (uint64_t)a[i] - key->n[i];
     37         a[i] = (uint32_t)A;
     38         A >>= 32;
     39     }
     40 }
     41 
     42 /* return a[] >= mod */
     43 static int geM(const RSAPublicKey *key, const uint32_t *a) {
     44     int i;
     45     for (i = key->len; i;) {
     46         --i;
     47         if (a[i] < key->n[i]) return 0;
     48         if (a[i] > key->n[i]) return 1;
     49     }
     50     return 1;  /* equal */
     51 }
     52 
     53 /* montgomery c[] += a * b[] / R % mod */
     54 static void montMulAdd(const RSAPublicKey *key,
     55                        uint32_t* c,
     56                        const uint32_t a,
     57                        const uint32_t* b) {
     58     uint64_t A = (uint64_t)a * b[0] + c[0];
     59     uint32_t d0 = (uint32_t)A * key->n0inv;
     60     uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
     61     int i;
     62 
     63     for (i = 1; i < key->len; ++i) {
     64         A = (A >> 32) + (uint64_t)a * b[i] + c[i];
     65         B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
     66         c[i - 1] = (uint32_t)B;
     67     }
     68 
     69     A = (A >> 32) + (B >> 32);
     70 
     71     c[i - 1] = (uint32_t)A;
     72 
     73     if (A >> 32) {
     74         subM(key, c);
     75     }
     76 }
     77 
     78 /* montgomery c[] = a[] * b[] / R % mod */
     79 static void montMul(const RSAPublicKey *key,
     80                     uint32_t* c,
     81                     const uint32_t* a,
     82                     const uint32_t* b) {
     83     int i;
     84     for (i = 0; i < key->len; ++i) {
     85         c[i] = 0;
     86     }
     87     for (i = 0; i < key->len; ++i) {
     88         montMulAdd(key, c, a[i], b);
     89     }
     90 }
     91 
     92 /* In-place public exponentiation.
     93 ** Input and output big-endian byte array in inout.
     94 */
     95 static void modpow3(const RSAPublicKey *key,
     96                     uint8_t* inout) {
     97     uint32_t a[RSANUMWORDS];
     98     uint32_t aR[RSANUMWORDS];
     99     uint32_t aaR[RSANUMWORDS];
    100     uint32_t *aaa = aR;  /* Re-use location. */
    101     int i;
    102 
    103     /* Convert from big endian byte array to little endian word array. */
    104     for (i = 0; i < key->len; ++i) {
    105         uint32_t tmp =
    106             (inout[((key->len - 1 - i) * 4) + 0] << 24) |
    107             (inout[((key->len - 1 - i) * 4) + 1] << 16) |
    108             (inout[((key->len - 1 - i) * 4) + 2] << 8) |
    109             (inout[((key->len - 1 - i) * 4) + 3] << 0);
    110         a[i] = tmp;
    111     }
    112 
    113     montMul(key, aR, a, key->rr);  /* aR = a * RR / R mod M   */
    114     montMul(key, aaR, aR, aR);     /* aaR = aR * aR / R mod M */
    115     montMul(key, aaa, aaR, a);     /* aaa = aaR * a / R mod M */
    116 
    117     /* Make sure aaa < mod; aaa is at most 1x mod too large. */
    118     if (geM(key, aaa)) {
    119         subM(key, aaa);
    120     }
    121 
    122     /* Convert to bigendian byte array */
    123     for (i = key->len - 1; i >= 0; --i) {
    124         uint32_t tmp = aaa[i];
    125         *inout++ = tmp >> 24;
    126         *inout++ = tmp >> 16;
    127         *inout++ = tmp >> 8;
    128         *inout++ = tmp >> 0;
    129     }
    130 }
    131 
    132 /* Expected PKCS1.5 signature padding bytes, for a keytool RSA signature.
    133 ** Has the 0-length optional parameter encoded in the ASN1 (as opposed to the
    134 ** other flavor which omits the optional parameter entirely). This code does not
    135 ** accept signatures without the optional parameter.
    136 */
    137 static const uint8_t padding[RSANUMBYTES - SHA_DIGEST_SIZE] = {
    138     0x00,0x01,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    139     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    140     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    141     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    142     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    143     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    144     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    145     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    146     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    147     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    148     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    149     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    150     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    151     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    152     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    153     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
    154     0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,
    155     0x30,0x21,0x30,0x09,0x06,0x05,0x2b,0x0e,0x03,0x02,0x1a,0x05,0x00,
    156     0x04,0x14
    157 };
    158 
    159 /* Verify a 2048 bit RSA PKCS1.5 signature against an expected SHA-1 hash.
    160 ** Returns 0 on failure, 1 on success.
    161 */
    162 int RSA_verify(const RSAPublicKey *key,
    163                const uint8_t *signature,
    164                const int len,
    165                const uint8_t *sha) {
    166     uint8_t buf[RSANUMBYTES];
    167     int i;
    168 
    169     if (key->len != RSANUMWORDS) {
    170         return 0;  /* Wrong key passed in. */
    171     }
    172 
    173     if (len != sizeof(buf)) {
    174         return 0;  /* Wrong input length. */
    175     }
    176 
    177     for (i = 0; i < len; ++i) {
    178         buf[i] = signature[i];
    179     }
    180 
    181     modpow3(key, buf);
    182 
    183     /* Check pkcs1.5 padding bytes. */
    184     for (i = 0; i < (int) sizeof(padding); ++i) {
    185         if (buf[i] != padding[i]) {
    186             return 0;
    187         }
    188     }
    189 
    190     /* Check sha digest matches. */
    191     for (; i < len; ++i) {
    192         if (buf[i] != *sha++) {
    193             return 0;
    194         }
    195     }
    196 
    197     return 1;
    198 }
    199