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
subM(const RSAPublicKey * key,uint32_t * a)33 static 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
geM(const RSAPublicKey * key,const uint32_t * a)45 static 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
montMulAdd(const RSAPublicKey * key,uint32_t * c,const uint32_t a,const uint32_t * b)57 static 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
montMul(const RSAPublicKey * key,uint32_t * c,const uint32_t * a,const uint32_t * b)82 static 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.
modpow(const RSAPublicKey * key,uint8_t * inout)97 static 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 /*
151 static 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.
190 static 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 /*
197 static 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.
235 static 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.
RSA_verify(const RSAPublicKey * key,const uint8_t * signature,const int len,const uint8_t * hash,const int hash_len)249 int 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