135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker/* rsa_e_3.c
235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**
335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** Copyright 2008, The Android Open Source Project
435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**
535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** Redistribution and use in source and binary forms, with or without
635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** modification, are permitted provided that the following conditions are met:
735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**     * Redistributions of source code must retain the above copyright
835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**       notice, this list of conditions and the following disclaimer.
935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**     * Redistributions in binary form must reproduce the above copyright
1035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**       notice, this list of conditions and the following disclaimer in the
1135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**       documentation and/or other materials provided with the distribution.
1235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**     * Neither the name of Google Inc. nor the names of its contributors may
1335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**       be used to endorse or promote products derived from this software
1435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**       without specific prior written permission.
1535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker**
1635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** THIS SOFTWARE IS PROVIDED BY Google Inc. ``AS IS'' AND ANY EXPRESS OR
1735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
1835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
1935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** EVENT SHALL Google Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
2135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
2235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
2335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
2435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
2535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker*/
2735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
2835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker#include "mincrypt/rsa.h"
2935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker#include "mincrypt/sha.h"
3035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
3135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker/* a[] -= mod */
3235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongkerstatic void subM(const RSAPublicKey *key, uint32_t *a) {
3335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    int64_t A = 0;
3435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    int i;
3535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = 0; i < key->len; ++i) {
3635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        A += (uint64_t)a[i] - key->n[i];
3735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        a[i] = (uint32_t)A;
3835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        A >>= 32;
3935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
4035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker}
4135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
4235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker/* return a[] >= mod */
4335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongkerstatic int geM(const RSAPublicKey *key, const uint32_t *a) {
4435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    int i;
4535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = key->len; i;) {
4635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        --i;
4735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        if (a[i] < key->n[i]) return 0;
4835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        if (a[i] > key->n[i]) return 1;
4935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
5035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    return 1;  /* equal */
5135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker}
5235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
5335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker/* montgomery c[] += a * b[] / R % mod */
5435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongkerstatic void montMulAdd(const RSAPublicKey *key,
5535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                       uint32_t* c,
5635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                       const uint32_t a,
5735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                       const uint32_t* b) {
5835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    uint64_t A = (uint64_t)a * b[0] + c[0];
5935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    uint32_t d0 = (uint32_t)A * key->n0inv;
6035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
6135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    int i;
6235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
6335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = 1; i < key->len; ++i) {
6435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        A = (A >> 32) + (uint64_t)a * b[i] + c[i];
6535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
6635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        c[i - 1] = (uint32_t)B;
6735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
6835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
6935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    A = (A >> 32) + (B >> 32);
7035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
7135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    c[i - 1] = (uint32_t)A;
7235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
7335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    if (A >> 32) {
7435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        subM(key, c);
7535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
7635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker}
7735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
7835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker/* montgomery c[] = a[] * b[] / R % mod */
7935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongkerstatic void montMul(const RSAPublicKey *key,
8035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                    uint32_t* c,
8135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                    const uint32_t* a,
8235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                    const uint32_t* b) {
8335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    int i;
8435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = 0; i < key->len; ++i) {
8535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        c[i] = 0;
8635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
8735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = 0; i < key->len; ++i) {
8835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        montMulAdd(key, c, a[i], b);
8935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
9035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker}
9135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
9235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker/* In-place public exponentiation.
9335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** Input and output big-endian byte array in inout.
9435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker*/
9535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongkerstatic void modpow3(const RSAPublicKey *key,
9635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                    uint8_t* inout) {
9735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    uint32_t a[RSANUMWORDS];
9835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    uint32_t aR[RSANUMWORDS];
9935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    uint32_t aaR[RSANUMWORDS];
10035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    uint32_t *aaa = aR;  /* Re-use location. */
10135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    int i;
10235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
10335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    /* Convert from big endian byte array to little endian word array. */
10435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = 0; i < key->len; ++i) {
10535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        uint32_t tmp =
10635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker            (inout[((key->len - 1 - i) * 4) + 0] << 24) |
10735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker            (inout[((key->len - 1 - i) * 4) + 1] << 16) |
10835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker            (inout[((key->len - 1 - i) * 4) + 2] << 8) |
10935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker            (inout[((key->len - 1 - i) * 4) + 3] << 0);
11035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        a[i] = tmp;
11135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
11235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
11335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    montMul(key, aR, a, key->rr);  /* aR = a * RR / R mod M   */
11435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    montMul(key, aaR, aR, aR);     /* aaR = aR * aR / R mod M */
11535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    montMul(key, aaa, aaR, a);     /* aaa = aaR * a / R mod M */
11635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
11735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    /* Make sure aaa < mod; aaa is at most 1x mod too large. */
11835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    if (geM(key, aaa)) {
11935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        subM(key, aaa);
12035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
12135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
12235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    /* Convert to bigendian byte array */
12335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = key->len - 1; i >= 0; --i) {
12435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        uint32_t tmp = aaa[i];
12535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        *inout++ = tmp >> 24;
12635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        *inout++ = tmp >> 16;
12735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        *inout++ = tmp >> 8;
12835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        *inout++ = tmp >> 0;
12935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
13035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker}
13135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
13235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker/* Expected PKCS1.5 signature padding bytes, for a keytool RSA signature.
13335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** Has the 0-length optional parameter encoded in the ASN1 (as opposed to the
13435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** other flavor which omits the optional parameter entirely). This code does not
13535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** accept signatures without the optional parameter.
13635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker*/
13735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongkerstatic const uint8_t padding[RSANUMBYTES - SHA_DIGEST_SIZE] = {
13835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0x00,0x01,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
13935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
14935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
15035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
15135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
15235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
15335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
15435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,
15535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0x30,0x21,0x30,0x09,0x06,0x05,0x2b,0x0e,0x03,0x02,0x1a,0x05,0x00,
15635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    0x04,0x14
15735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker};
15835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
15935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker/* Verify a 2048 bit RSA e=3 PKCS1.5 signature against an expected SHA-1 hash.
16035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker** Returns 0 on failure, 1 on success.
16135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker*/
16235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongkerint RSA_e_3_verify(const RSAPublicKey *key,
16335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                   const uint8_t *signature,
16435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                   const int len,
16535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker                   const uint8_t *sha) {
16635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    uint8_t buf[RSANUMBYTES];
16735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    int i;
16835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
16935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    if (key->len != RSANUMWORDS) {
17035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        return 0;  /* Wrong key passed in. */
17135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
17235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
17335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    if (len != sizeof(buf)) {
17435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        return 0;  /* Wrong input length. */
17535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
17635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
17735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker  if (key->exponent != 3) {
17835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker      return 0;  // Wrong exponent.
17935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker  }
18035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
18135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = 0; i < len; ++i) {
18235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        buf[i] = signature[i];
18335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
18435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
18535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    modpow3(key, buf);
18635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
18735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    /* Check pkcs1.5 padding bytes. */
18835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (i = 0; i < (int) sizeof(padding); ++i) {
18935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        if (buf[i] != padding[i]) {
19035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker            return 0;
19135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        }
19235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
19335d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
19435d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    /* Check sha digest matches. */
19535d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    for (; i < len; ++i) {
19635d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        if (buf[i] != *sha++) {
19735d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker            return 0;
19835d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker        }
19935d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    }
20035d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker
20135d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker    return 1;
20235d9ad5ae72de846967b91aed97060f0e8558661Doug Zongker}
203