blob: 9061b3ae3058c3274298eb95390cf5df374b1637 [file] [log] [blame]
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -08001/* rsa.c
2**
Doug Zongker35d9ad52012-07-25 12:08:33 -07003** Copyright 2012, The Android Open Source Project
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -08004**
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**
Doug Zongker35d9ad52012-07-25 12:08:33 -070016** THIS SOFTWARE IS PROVIDED BY Google Inc. ``AS IS'' AND ANY EXPRESS OR
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080017** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
Doug Zongker35d9ad52012-07-25 12:08:33 -070018** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080019** EVENT SHALL Google Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
Doug Zongker35d9ad52012-07-25 12:08:33 -070021** 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
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080024** 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"
Doug Zongker0a862dc2013-04-10 15:08:28 -070029#include "mincrypt/sha.h"
30#include "mincrypt/sha256.h"
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080031
Doug Zongker0a862dc2013-04-10 15:08:28 -070032// 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}
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080043
Doug Zongker0a862dc2013-04-10 15:08:28 -070044// 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}
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080055
Doug Zongker0a862dc2013-04-10 15:08:28 -070056// 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.
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -0800249int RSA_verify(const RSAPublicKey *key,
250 const uint8_t *signature,
251 const int len,
Doug Zongker8e5b63d2013-04-10 09:22:02 -0700252 const uint8_t *hash,
253 const int hash_len) {
Doug Zongker0a862dc2013-04-10 15:08:28 -0700254 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);
Doug Zongker35d9ad52012-07-25 12:08:33 -0700291 break;
Doug Zongker0a862dc2013-04-10 15:08:28 -0700292 case SHA256_DIGEST_SIZE:
293 padding_hash = kExpectedPadSha256Rsa2048;
294 SHA256_hash(buf, len, buf);
Doug Zongker35d9ad52012-07-25 12:08:33 -0700295 break;
296 default:
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -0800297 return 0;
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -0800298 }
Doug Zongker0a862dc2013-04-10 15:08:28 -0700299
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.
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -0800308}