rsa.c revision 0a862dcd637d3ed82861d39bb48a55ed10a796a6 
1/* rsa.c
2**
3** Copyright 2012, 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#include "mincrypt/sha256.h"
31
32// a[] -= mod
33static void subM(const RSAPublicKey* key,
34                 uint32_t* a) {
35    int64_t A = 0;
36    int i;
37    for (i = 0; i < key->len; ++i) {
38        A += (uint64_t)a[i] - key->n[i];
39        a[i] = (uint32_t)A;
40        A >>= 32;
41    }
42}
43
44// return a[] >= mod
45static int geM(const RSAPublicKey* key,
46               const uint32_t* a) {
47    int i;
48    for (i = key->len; i;) {
49        --i;
50        if (a[i] < key->n[i]) return 0;
51        if (a[i] > key->n[i]) return 1;
52    }
53    return 1;  // equal
54}
55
56// montgomery c[] += a * b[] / R % mod
57static void montMulAdd(const RSAPublicKey* key,
58                       uint32_t* c,
59                       const uint32_t a,
60                       const uint32_t* b) {
61    uint64_t A = (uint64_t)a * b[0] + c[0];
62    uint32_t d0 = (uint32_t)A * key->n0inv;
63    uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
64    int i;
65
66    for (i = 1; i < key->len; ++i) {
67        A = (A >> 32) + (uint64_t)a * b[i] + c[i];
68        B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
69        c[i - 1] = (uint32_t)B;
70    }
71
72    A = (A >> 32) + (B >> 32);
73
74    c[i - 1] = (uint32_t)A;
75
76    if (A >> 32) {
77        subM(key, c);
78    }
79}
80
81// montgomery c[] = a[] * b[] / R % mod
82static void montMul(const RSAPublicKey* key,
83                    uint32_t* c,
84                    const uint32_t* a,
85                    const uint32_t* b) {
86    int i;
87    for (i = 0; i < key->len; ++i) {
88        c[i] = 0;
89    }
90    for (i = 0; i < key->len; ++i) {
91        montMulAdd(key, c, a[i], b);
92    }
93}
94
95// In-place public exponentiation.
96// Input and output big-endian byte array in inout.
97static void modpow(const RSAPublicKey* key,
98                   uint8_t* inout) {
99    uint32_t a[RSANUMWORDS];
100    uint32_t aR[RSANUMWORDS];
101    uint32_t aaR[RSANUMWORDS];
102    uint32_t* aaa = 0;
103    int i;
104
105    // Convert from big endian byte array to little endian word array.
106    for (i = 0; i < key->len; ++i) {
107        uint32_t tmp =
108            (inout[((key->len - 1 - i) * 4) + 0] << 24) |
109            (inout[((key->len - 1 - i) * 4) + 1] << 16) |
110            (inout[((key->len - 1 - i) * 4) + 2] << 8) |
111            (inout[((key->len - 1 - i) * 4) + 3] << 0);
112        a[i] = tmp;
113    }
114
115    if (key->exponent == 65537) {
116        aaa = aaR;  // Re-use location.
117        montMul(key, aR, a, key->rr);  // aR = a * RR / R mod M
118        for (i = 0; i < 16; i += 2) {
119            montMul(key, aaR, aR, aR);  // aaR = aR * aR / R mod M
120            montMul(key, aR, aaR, aaR);  // aR = aaR * aaR / R mod M
121        }
122        montMul(key, aaa, aR, a);  // aaa = aR * a / R mod M
123    } else if (key->exponent == 3) {
124        aaa = aR;  // Re-use location.
125        montMul(key, aR, a, key->rr);  /* aR = a * RR / R mod M   */
126        montMul(key, aaR, aR, aR);     /* aaR = aR * aR / R mod M */
127        montMul(key, aaa, aaR, a);     /* aaa = aaR * a / R mod M */
128    }
129
130    // Make sure aaa < mod; aaa is at most 1x mod too large.
131    if (geM(key, aaa)) {
132        subM(key, aaa);
133    }
134
135    // Convert to bigendian byte array
136    for (i = key->len - 1; i >= 0; --i) {
137        uint32_t tmp = aaa[i];
138        *inout++ = tmp >> 24;
139        *inout++ = tmp >> 16;
140        *inout++ = tmp >> 8;
141        *inout++ = tmp >> 0;
142    }
143}
144
145// Expected PKCS1.5 signature padding bytes, for a keytool RSA signature.
146// Has the 0-length optional parameter encoded in the ASN1 (as opposed to the
147// other flavor which omits the optional parameter entirely). This code does not
148// accept signatures without the optional parameter.
149
150/*
151static const uint8_t sha_padding[RSANUMBYTES] = {
152    0x00, 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
153    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
154    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
155    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
156    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
157    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
158    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
159    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
160    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
161    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
162    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
163    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
164    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
165    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
166    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
167    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
168    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
169    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
170    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
171    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
172    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
173    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
174    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
175    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
176    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
177    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
178    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
179    0xff, 0xff, 0xff, 0xff, 0x00, 0x30, 0x21, 0x30,
180    0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a,
181    0x05, 0x00, 0x04, 0x14,
182
183    // 20 bytes of hash go here.
184    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
185};
186*/
187
188// SHA-1 of PKCS1.5 signature sha_padding for 2048 bit, as above.
189// At the location of the bytes of the hash all 00 are hashed.
190static const uint8_t kExpectedPadShaRsa2048[SHA_DIGEST_SIZE] = {
191    0xdc, 0xbd, 0xbe, 0x42, 0xd5, 0xf5, 0xa7, 0x2e,
192    0x6e, 0xfc, 0xf5, 0x5d, 0xaf, 0x9d, 0xea, 0x68,
193    0x7c, 0xfb, 0xf1, 0x67
194};
195
196/*
197static const uint8_t sha256_padding[RSANUMBYTES] = {
198    0x00, 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
199    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
200    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
201    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
202    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
203    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
204    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
205    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
206    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
207    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
208    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
209    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
210    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
211    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
212    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
213    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
214    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
215    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
216    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
217    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
218    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
219    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
220    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
221    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
222    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
223    0xff, 0xff, 0xff, 0xff, 0x00, 0x30, 0x31, 0x30,
224    0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65,
225    0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20,
226
227    // 32 bytes of hash go here.
228    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
229    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
230};
231*/
232
233// SHA-256 of PKCS1.5 signature sha256_padding for 2048 bit, as above.
234// At the location of the bytes of the hash all 00 are hashed.
235static const uint8_t kExpectedPadSha256Rsa2048[SHA256_DIGEST_SIZE] = {
236    0xab, 0x28, 0x8d, 0x8a, 0xd7, 0xd9, 0x59, 0x92,
237    0xba, 0xcc, 0xf8, 0x67, 0x20, 0xe1, 0x15, 0x2e,
238    0x39, 0x8d, 0x80, 0x36, 0xd6, 0x6f, 0xf0, 0xfd,
239    0x90, 0xe8, 0x7d, 0x8b, 0xe1, 0x7c, 0x87, 0x59,
240};
241
242// Verify a 2048-bit RSA PKCS1.5 signature against an expected hash.
243// Both e=3 and e=65537 are supported.  hash_len may be
244// SHA_DIGEST_SIZE (== 20) to indicate a SHA-1 hash, or
245// SHA256_DIGEST_SIZE (== 32) to indicate a SHA-256 hash.  No other
246// values are supported.
247//
248// Returns 1 on successful verification, 0 on failure.
249int RSA_verify(const RSAPublicKey *key,
250               const uint8_t *signature,
251               const int len,
252               const uint8_t *hash,
253               const int hash_len) {
254    uint8_t buf[RSANUMBYTES];
255    int i;
256    const uint8_t* padding_hash;
257
258    if (key->len != RSANUMWORDS) {
259        return 0;  // Wrong key passed in.
260    }
261
262    if (len != sizeof(buf)) {
263        return 0;  // Wrong input length.
264    }
265
266    if (hash_len != SHA_DIGEST_SIZE &&
267        hash_len != SHA256_DIGEST_SIZE) {
268        return 0;  // Unsupported hash.
269    }
270
271    if (key->exponent != 3 && key->exponent != 65537) {
272        return 0;  // Unsupported exponent.
273    }
274
275    for (i = 0; i < len; ++i) {  // Copy input to local workspace.
276        buf[i] = signature[i];
277    }
278
279    modpow(key, buf);  // In-place exponentiation.
280
281    // Xor sha portion, so it all becomes 00 iff equal.
282    for (i = len - hash_len; i < len; ++i) {
283        buf[i] ^= *hash++;
284    }
285
286    // Hash resulting buf, in-place.
287    switch (hash_len) {
288        case SHA_DIGEST_SIZE:
289            padding_hash = kExpectedPadShaRsa2048;
290            SHA_hash(buf, len, buf);
291            break;
292        case SHA256_DIGEST_SIZE:
293            padding_hash = kExpectedPadSha256Rsa2048;
294            SHA256_hash(buf, len, buf);
295            break;
296        default:
297            return 0;
298    }
299
300    // Compare against expected hash value.
301    for (i = 0; i < hash_len; ++i) {
302        if (buf[i] != padding_hash[i]) {
303            return 0;
304        }
305    }
306
307    return 1;  // All checked out OK.
308}
309