rsa_e_3.c revision 35d9ad5ae72de846967b91aed97060f0e8558661 
1/* rsa_e_3.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 */
32static 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 */
43static 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 */
54static 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 */
79static 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*/
95static 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*/
137static 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 e=3 PKCS1.5 signature against an expected SHA-1 hash.
160** Returns 0 on failure, 1 on success.
161*/
162int RSA_e_3_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  if (key->exponent != 3) {
178      return 0;  // Wrong exponent.
179  }
180
181    for (i = 0; i < len; ++i) {
182        buf[i] = signature[i];
183    }
184
185    modpow3(key, buf);
186
187    /* Check pkcs1.5 padding bytes. */
188    for (i = 0; i < (int) sizeof(padding); ++i) {
189        if (buf[i] != padding[i]) {
190            return 0;
191        }
192    }
193
194    /* Check sha digest matches. */
195    for (; i < len; ++i) {
196        if (buf[i] != *sha++) {
197            return 0;
198        }
199    }
200
201    return 1;
202}
203