OLD | NEW |
---|---|
(Empty) | |
1 /* Copyright (c) 2010 The Chromium OS Authors. All rights reserved. | |
2 * Use of this source code is governed by a BSD-style license that can be | |
3 * found in the LICENSE file. | |
4 */ | |
5 | |
6 /* Implementation of RSA signature verification which uses a pre-processed | |
7 * key for computation. The code extends Android's RSA verification code to | |
8 * support multiple RSA key lengths and hash digest algorithms. | |
9 */ | |
10 | |
11 #include <stdio.h> | |
12 | |
13 #include "padding.h" | |
14 #include "rsa.h" | |
15 #include "utility.h" | |
16 | |
17 /* a[] -= mod */ | |
18 static void subM(const RSAPublicKey *key, uint32_t *a) { | |
19 int64_t A = 0; | |
20 int i; | |
21 for (i = 0; i < key->len; ++i) { | |
22 A += (uint64_t)a[i] - key->n[i]; | |
23 a[i] = (uint32_t)A; | |
24 A >>= 32; | |
25 } | |
26 } | |
27 | |
28 /* return a[] >= mod */ | |
29 static int geM(const RSAPublicKey *key, uint32_t *a) { | |
30 int i; | |
31 for (i = key->len; i;) { | |
32 --i; | |
33 if (a[i] < key->n[i]) return 0; | |
34 if (a[i] > key->n[i]) return 1; | |
35 } | |
36 return 1; /* equal */ | |
37 } | |
38 | |
39 /* montgomery c[] += a * b[] / R % mod */ | |
40 static void montMulAdd(const RSAPublicKey *key, | |
41 uint32_t* c, | |
42 const uint32_t a, | |
43 const uint32_t* b) { | |
44 uint64_t A = (uint64_t)a * b[0] + c[0]; | |
45 uint32_t d0 = (uint32_t)A * key->n0inv; | |
46 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; | |
47 int i; | |
48 | |
49 for (i = 1; i < key->len; ++i) { | |
50 A = (A >> 32) + (uint64_t)a * b[i] + c[i]; | |
51 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; | |
52 c[i - 1] = (uint32_t)B; | |
53 } | |
54 | |
55 A = (A >> 32) + (B >> 32); | |
56 | |
57 c[i - 1] = (uint32_t)A; | |
58 | |
59 if (A >> 32) { | |
60 subM(key, c); | |
61 } | |
62 } | |
63 | |
64 /* montgomery c[] = a[] * b[] / R % mod */ | |
65 static void montMul(const RSAPublicKey *key, | |
66 uint32_t* c, | |
67 uint32_t* a, | |
68 uint32_t* b) { | |
69 int i; | |
70 for (i = 0; i < key->len; ++i) { | |
71 c[i] = 0; | |
72 } | |
73 for (i = 0; i < key->len; ++i) { | |
74 montMulAdd(key, c, a[i], b); | |
75 } | |
76 } | |
77 | |
78 /* In-place public exponentiation. (65537} | |
79 * Input and output big-endian byte array in inout. | |
80 */ | |
81 static void modpowF4(const RSAPublicKey *key, | |
82 uint8_t* inout) { | |
83 uint32_t* a = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); | |
84 uint32_t* aR = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); | |
85 uint32_t* aaR = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); | |
86 | |
87 uint32_t* aaa = aaR; /* Re-use location. */ | |
88 int i; | |
89 | |
90 /* Convert from big endian byte array to little endian word array. */ | |
91 for (i = 0; i < key->len; ++i) { | |
92 uint32_t tmp = | |
93 (inout[((key->len - 1 - i) * 4) + 0] << 24) | | |
94 (inout[((key->len - 1 - i) * 4) + 1] << 16) | | |
95 (inout[((key->len - 1 - i) * 4) + 2] << 8) | | |
96 (inout[((key->len - 1 - i) * 4) + 3] << 0); | |
97 a[i] = tmp; | |
98 } | |
99 | |
100 montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */ | |
101 for (i = 0; i < 16; i+=2) { | |
102 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ | |
103 montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ | |
104 } | |
105 montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ | |
106 | |
107 | |
mschilder
2010/02/01 19:40:39
extra line?
gauravsh
2010/02/08 20:28:18
Fixed.
| |
108 /* Make sure aaa < mod; aaa is at most 1x mod too large. */ | |
109 if (geM(key, aaa)) { | |
110 subM(key, aaa); | |
111 } | |
112 | |
113 /* Convert to bigendian byte array */ | |
114 for (i = key->len - 1; i >= 0; --i) { | |
115 uint32_t tmp = aaa[i]; | |
116 *inout++ = tmp >> 24; | |
117 *inout++ = tmp >> 16; | |
118 *inout++ = tmp >> 8; | |
119 *inout++ = tmp >> 0; | |
120 } | |
121 | |
122 Free(a); | |
mschilder
2010/02/01 19:40:39
depending on how minimalist/crappy your allocator
gauravsh
2010/02/08 20:28:18
Done.
| |
123 Free(aR); | |
124 Free(aaR); | |
125 } | |
126 | |
127 /* Verify a RSA PKCS1.5 signature against an expected hash. | |
128 * Returns 0 on failure, 1 on success. | |
129 */ | |
130 int RSA_verify(const RSAPublicKey *key, | |
131 const uint8_t *sig, | |
132 const int sig_len, | |
133 const uint8_t sig_type, | |
134 const uint8_t *hash) { | |
135 int i; | |
136 uint8_t* buf; | |
137 const uint8_t* padding; | |
138 int success = 1; | |
139 | |
140 if (sig_len != (key->len * sizeof(uint32_t))) { | |
141 fprintf(stderr, "Signature is of incorrect length!\n"); | |
142 return 0; | |
143 } | |
144 | |
145 if (sig_type >= kNumAlgorithms) { | |
146 fprintf(stderr, "Invalid signature type!\n"); | |
147 return 0; | |
148 } | |
149 | |
150 if (key->len != siglen_map[sig_type]) { | |
151 fprintf(stderr, "Wrong key passed in!\n"); | |
152 return 0; | |
153 } | |
154 | |
155 buf = (uint8_t*) Malloc(sig_len); | |
156 Memcpy(buf, sig, sig_len); | |
157 | |
158 modpowF4(key, buf); | |
159 | |
160 /* Determine padding to use depending on the signature type. */ | |
161 padding = padding_map[sig_type]; | |
162 | |
163 /* Check pkcs1.5 padding bytes. */ | |
164 for (i = 0; i < padding_size_map[sig_type]; ++i) { | |
165 if (buf[i] != padding[i]) { | |
166 #ifndef NDEBUG | |
167 /* TODO(gauravsh): Replace with a macro call for logging. */ | |
168 fprintf(stderr, "Padding: Expecting = %02x Got = %02x\n", padding[i], | |
169 buf[i]); | |
170 #endif | |
171 success = 0; | |
172 } | |
173 } | |
174 | |
175 /* Check if digest matches. */ | |
176 for (; i < sig_len; ++i) { | |
177 if (buf[i] != *hash++) { | |
178 #ifndef NDEBUG | |
179 /* TODO(gauravsh): Replace with a macro call for logging. */ | |
180 fprintf(stderr, "Digest: Expecting = %02x Got = %02x\n", padding[i], | |
181 buf[i]); | |
182 #endif | |
183 success = 0; | |
184 } | |
185 } | |
186 | |
187 Free(buf); | |
188 | |
189 return success; | |
190 } | |
OLD | NEW |