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 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 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 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 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. 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. 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
