Chromium Code Reviews| OLD | NEW |
|---|---|
| 1 /* Copyright (c) 2010 The Chromium OS Authors. All rights reserved. | 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 | 2 * Use of this source code is governed by a BSD-style license that can be |
| 3 * found in the LICENSE file. | 3 * found in the LICENSE file. |
| 4 */ | 4 */ |
| 5 | 5 |
| 6 /* Implementation of RSA signature verification which uses a pre-processed | 6 /* Implementation of RSA signature verification which uses a pre-processed |
| 7 * key for computation. The code extends Android's RSA verification code to | 7 * key for computation. The code extends Android's RSA verification code to |
| 8 * support multiple RSA key lengths and hash digest algorithms. | 8 * support multiple RSA key lengths and hash digest algorithms. |
| 9 */ | 9 */ |
| 10 | 10 |
| 11 #include "cryptolib.h" | 11 #include "cryptolib.h" |
| 12 #include "utility.h" | 12 #include "utility.h" |
| 13 | 13 |
| 14 /* a[] -= mod */ | 14 /* a[] -= mod */ |
| 15 static void subM(const RSAPublicKey *key, uint32_t *a) { | 15 static void subM(const RSAPublicKey *key, uint32_t *a) { |
| 16 int64_t A = 0; | 16 int64_t A = 0; |
| 17 int i; | 17 uint32_t i; |
| 18 for (i = 0; i < key->len; ++i) { | 18 for (i = 0; i < key->len; ++i) { |
| 19 A += (uint64_t)a[i] - key->n[i]; | 19 A += (uint64_t)a[i] - key->n[i]; |
| 20 a[i] = (uint32_t)A; | 20 a[i] = (uint32_t)A; |
| 21 A >>= 32; | 21 A >>= 32; |
| 22 } | 22 } |
| 23 } | 23 } |
| 24 | 24 |
| 25 /* return a[] >= mod */ | 25 /* return a[] >= mod */ |
| 26 static int geM(const RSAPublicKey *key, uint32_t *a) { | 26 static int geM(const RSAPublicKey *key, uint32_t *a) { |
| 27 int i; | 27 uint32_t i; |
| 28 for (i = key->len; i;) { | 28 for (i = key->len; i;) { |
| 29 --i; | 29 --i; |
| 30 if (a[i] < key->n[i]) return 0; | 30 if (a[i] < key->n[i]) return 0; |
| 31 if (a[i] > key->n[i]) return 1; | 31 if (a[i] > key->n[i]) return 1; |
| 32 } | 32 } |
| 33 return 1; /* equal */ | 33 return 1; /* equal */ |
| 34 } | 34 } |
| 35 | 35 |
| 36 /* montgomery c[] += a * b[] / R % mod */ | 36 /* montgomery c[] += a * b[] / R % mod */ |
| 37 static void montMulAdd(const RSAPublicKey *key, | 37 static void montMulAdd(const RSAPublicKey *key, |
| 38 uint32_t* c, | 38 uint32_t* c, |
| 39 const uint32_t a, | 39 const uint32_t a, |
| 40 const uint32_t* b) { | 40 const uint32_t* b) { |
| 41 uint64_t A = (uint64_t)a * b[0] + c[0]; | 41 uint64_t A = UINT64_MULT32(a, b[0]) + c[0]; |
| 42 uint32_t d0 = (uint32_t)A * key->n0inv; | 42 uint32_t d0 = (uint32_t)A * key->n0inv; |
| 43 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; | 43 uint64_t B = UINT64_MULT32(d0, key->n[0]) + (uint32_t)A; |
| 44 int i; | 44 uint32_t i; |
| 45 | 45 |
| 46 for (i = 1; i < key->len; ++i) { | 46 for (i = 1; i < key->len; ++i) { |
| 47 A = (A >> 32) + (uint64_t)a * b[i] + c[i]; | 47 A = (A >> 32) + UINT64_MULT32(a, b[i]) + c[i]; |
| 48 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; | 48 B = (B >> 32) + UINT64_MULT32(d0, key->n[i]) + (uint32_t)A; |
| 49 c[i - 1] = (uint32_t)B; | 49 c[i - 1] = (uint32_t)B; |
| 50 } | 50 } |
| 51 | 51 |
| 52 A = (A >> 32) + (B >> 32); | 52 A = (A >> 32) + (B >> 32); |
| 53 | 53 |
| 54 c[i - 1] = (uint32_t)A; | 54 c[i - 1] = (uint32_t)A; |
| 55 | 55 |
| 56 if (A >> 32) { | 56 if (A >> 32) { |
| 57 subM(key, c); | 57 subM(key, c); |
| 58 } | 58 } |
| 59 } | 59 } |
| 60 | 60 |
| 61 /* montgomery c[] = a[] * b[] / R % mod */ | 61 /* montgomery c[] = a[] * b[] / R % mod */ |
| 62 static void montMul(const RSAPublicKey *key, | 62 static void montMul(const RSAPublicKey *key, |
| 63 uint32_t* c, | 63 uint32_t* c, |
| 64 uint32_t* a, | 64 uint32_t* a, |
| 65 uint32_t* b) { | 65 uint32_t* b) { |
| 66 int i; | 66 uint32_t i; |
| 67 for (i = 0; i < key->len; ++i) { | 67 for (i = 0; i < key->len; ++i) { |
| 68 c[i] = 0; | 68 c[i] = 0; |
| 69 } | 69 } |
| 70 for (i = 0; i < key->len; ++i) { | 70 for (i = 0; i < key->len; ++i) { |
| 71 montMulAdd(key, c, a[i], b); | 71 montMulAdd(key, c, a[i], b); |
| 72 } | 72 } |
| 73 } | 73 } |
| 74 | 74 |
| 75 /* In-place public exponentiation. (65537} | 75 /* In-place public exponentiation. (65537} |
| 76 * Input and output big-endian byte array in inout. | 76 * Input and output big-endian byte array in inout. |
| 77 */ | 77 */ |
| 78 static void modpowF4(const RSAPublicKey *key, | 78 static void modpowF4(const RSAPublicKey *key, |
| 79 uint8_t* inout) { | 79 uint8_t* inout) { |
| 80 uint32_t* a = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); | 80 uint32_t* a = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); |
| 81 uint32_t* aR = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); | 81 uint32_t* aR = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); |
| 82 uint32_t* aaR = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); | 82 uint32_t* aaR = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); |
| 83 | 83 |
| 84 uint32_t* aaa = aaR; /* Re-use location. */ | 84 uint32_t* aaa = aaR; /* Re-use location. */ |
| 85 int i; | 85 int i; |
| 86 | 86 |
| 87 /* Convert from big endian byte array to little endian word array. */ | 87 /* Convert from big endian byte array to little endian word array. */ |
| 88 for (i = 0; i < key->len; ++i) { | 88 for (i = 0; i < (int)key->len; ++i) { |
|
gauravsh
2010/06/21 23:32:48
both i and key->len are uint32_t, so this cast see
Randall Spangler
2010/06/21 23:58:05
i is a (signed) int; key->len is a uint32_t. So M
| |
| 89 uint32_t tmp = | 89 uint32_t tmp = |
| 90 (inout[((key->len - 1 - i) * 4) + 0] << 24) | | 90 (inout[((key->len - 1 - i) * 4) + 0] << 24) | |
| 91 (inout[((key->len - 1 - i) * 4) + 1] << 16) | | 91 (inout[((key->len - 1 - i) * 4) + 1] << 16) | |
| 92 (inout[((key->len - 1 - i) * 4) + 2] << 8) | | 92 (inout[((key->len - 1 - i) * 4) + 2] << 8) | |
| 93 (inout[((key->len - 1 - i) * 4) + 3] << 0); | 93 (inout[((key->len - 1 - i) * 4) + 3] << 0); |
| 94 a[i] = tmp; | 94 a[i] = tmp; |
| 95 } | 95 } |
| 96 | 96 |
| 97 montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */ | 97 montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */ |
| 98 for (i = 0; i < 16; i+=2) { | 98 for (i = 0; i < 16; i+=2) { |
| 99 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ | 99 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ |
| 100 montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ | 100 montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ |
| 101 } | 101 } |
| 102 montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ | 102 montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ |
| 103 | 103 |
| 104 | 104 |
| 105 /* Make sure aaa < mod; aaa is at most 1x mod too large. */ | 105 /* Make sure aaa < mod; aaa is at most 1x mod too large. */ |
| 106 if (geM(key, aaa)) { | 106 if (geM(key, aaa)) { |
| 107 subM(key, aaa); | 107 subM(key, aaa); |
| 108 } | 108 } |
| 109 | 109 |
| 110 /* Convert to bigendian byte array */ | 110 /* Convert to bigendian byte array */ |
| 111 for (i = key->len - 1; i >= 0; --i) { | 111 for (i = (int)key->len - 1; i >= 0; --i) { |
|
gauravsh
2010/06/21 23:32:48
i and key->len are both uint32_t
| |
| 112 uint32_t tmp = aaa[i]; | 112 uint32_t tmp = aaa[i]; |
| 113 *inout++ = tmp >> 24; | 113 *inout++ = (uint8_t)(tmp >> 24); |
| 114 *inout++ = tmp >> 16; | 114 *inout++ = (uint8_t)(tmp >> 16); |
| 115 *inout++ = tmp >> 8; | 115 *inout++ = (uint8_t)(tmp >> 8); |
| 116 *inout++ = tmp >> 0; | 116 *inout++ = (uint8_t)(tmp >> 0); |
| 117 } | 117 } |
| 118 | 118 |
| 119 Free(a); | 119 Free(a); |
| 120 Free(aR); | 120 Free(aR); |
| 121 Free(aaR); | 121 Free(aaR); |
| 122 } | 122 } |
| 123 | 123 |
| 124 /* Verify a RSA PKCS1.5 signature against an expected hash. | 124 /* Verify a RSA PKCS1.5 signature against an expected hash. |
| 125 * Returns 0 on failure, 1 on success. | 125 * Returns 0 on failure, 1 on success. |
| 126 */ | 126 */ |
| 127 int RSAVerify(const RSAPublicKey *key, | 127 int RSAVerify(const RSAPublicKey *key, |
| 128 const uint8_t *sig, | 128 const uint8_t *sig, |
| 129 const int sig_len, | 129 const uint32_t sig_len, |
| 130 const uint8_t sig_type, | 130 const uint8_t sig_type, |
| 131 const uint8_t *hash) { | 131 const uint8_t *hash) { |
| 132 int i; | 132 int i; |
| 133 uint8_t* buf; | 133 uint8_t* buf; |
| 134 const uint8_t* padding; | 134 const uint8_t* padding; |
| 135 int success = 1; | 135 int success = 1; |
| 136 | 136 |
| 137 if (sig_len != (key->len * sizeof(uint32_t))) { | 137 if (sig_len != (key->len * sizeof(uint32_t))) { |
| 138 debug("Signature is of incorrect length!\n"); | 138 debug("Signature is of incorrect length!\n"); |
| 139 return 0; | 139 return 0; |
| (...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 178 buf[i]); | 178 buf[i]); |
| 179 #endif | 179 #endif |
| 180 success = 0; | 180 success = 0; |
| 181 } | 181 } |
| 182 } | 182 } |
| 183 | 183 |
| 184 Free(buf); | 184 Free(buf); |
| 185 | 185 |
| 186 return success; | 186 return success; |
| 187 } | 187 } |
| OLD | NEW |