1 // Copyright 2008-2010 Google Inc. All Rights Reserved. 2 // Author: mschilder (at) google.com (Marius Schilder) 3 4 #include "rsa.h" 5 #include "sha.h" 6 7 // a[] -= mod 8 static void subM(RSAPublicKey key, 9 uint32_t* a) { 10 int64_t A = 0; 11 int i; 12 for (i = 0; i < key->len; ++i) { 13 A += (uint64_t)a[i] - key->n[i]; 14 a[i] = (uint32_t)A; 15 A >>= 32; 16 } 17 } 18 19 // return a[] >= mod 20 static int geM(RSAPublicKey key, 21 const uint32_t* a) { 22 int i; 23 for (i = key->len; i;) { 24 --i; 25 if (a[i] < key->n[i]) return 0; 26 if (a[i] > key->n[i]) return 1; 27 } 28 return 1; // equal 29 } 30 31 // montgomery c[] += a * b[] / R % mod 32 static void montMulAdd(RSAPublicKey key, 33 uint32_t* c, 34 const uint32_t a, 35 const uint32_t* b) { 36 uint64_t A = (uint64_t)a * b[0] + c[0]; 37 uint32_t d0 = (uint32_t)A * key->n0inv; 38 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; 39 int i; 40 41 for (i = 1; i < key->len; ++i) { 42 A = (A >> 32) + (uint64_t)a * b[i] + c[i]; 43 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; 44 c[i - 1] = (uint32_t)B; 45 } 46 47 A = (A >> 32) + (B >> 32); 48 49 c[i - 1] = (uint32_t)A; 50 51 if (A >> 32) { 52 subM(key, c); 53 } 54 } 55 56 // montgomery c[] = a[] * b[] / R % mod 57 static void montMul(RSAPublicKey key, 58 uint32_t* c, 59 const uint32_t* a, 60 const uint32_t* b) { 61 int i; 62 for (i = 0; i < key->len; ++i) { 63 c[i] = 0; 64 } 65 for (i = 0; i < key->len; ++i) { 66 montMulAdd(key, c, a[i], b); 67 } 68 } 69 70 // In-place public exponentiation. 71 // Input and output big-endian byte array in inout. 72 static void modpowF4(RSAPublicKey key, 73 uint8_t* inout) { 74 uint32_t a[RSANUMWORDS]; 75 uint32_t aR[RSANUMWORDS]; 76 uint32_t aaR[RSANUMWORDS]; 77 uint32_t* aaa = aaR; // Re-use location. 78 int i; 79 80 // Convert from big endian byte array to little endian word array. 81 for (i = 0; i < key->len; ++i) { 82 uint32_t tmp = 83 (inout[((key->len - 1 - i) * 4) + 0] << 24) | 84 (inout[((key->len - 1 - i) * 4) + 1] << 16) | 85 (inout[((key->len - 1 - i) * 4) + 2] << 8) | 86 (inout[((key->len - 1 - i) * 4) + 3] << 0); 87 a[i] = tmp; 88 } 89 90 montMul(key, aR, a, key->rr); // aR = a * RR / R mod M 91 for (i = 0; i < 16; i += 2) { 92 montMul(key, aaR, aR, aR); // aaR = aR * aR / R mod M 93 montMul(key, aR, aaR, aaR); // aR = aaR * aaR / R mod M 94 } 95 montMul(key, aaa, aR, a); // aaa = aR * a / R mod M 96 97 // Make sure aaa < mod; aaa is at most 1x mod too large. 98 if (geM(key, aaa)) { 99 subM(key, aaa); 100 } 101 102 // Convert to bigendian byte array 103 for (i = key->len - 1; i >= 0; --i) { 104 uint32_t tmp = aaa[i]; 105 *inout++ = tmp >> 24; 106 *inout++ = tmp >> 16; 107 *inout++ = tmp >> 8; 108 *inout++ = tmp >> 0; 109 } 110 } 111 112 // Expected PKCS1.5 signature padding bytes, for a keytool RSA signature. 113 // Has the 0-length optional parameter encoded in the ASN1 (as opposed to the 114 // other flavor which omits the optional parameter entirely). This code does not 115 // accept signatures without the optional parameter. 116 /* 117 static const uint8_t padding[RSANUMBYTES] = { 118 0x00,0x01,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2b,0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 119 }; 120 */ 121 122 // SHA-1 of PKCS1.5 signature padding for 2048 bit, as above. 123 // At the location of the bytes of the hash all 00 are hashed. 124 static const uint8_t kExpectedPadShaRsa2048[SHA_DIGEST_SIZE] = { 125 0xdc, 0xbd, 0xbe, 0x42, 0xd5, 0xf5, 0xa7, 0x2e, 0x6e, 0xfc, 126 0xf5, 0x5d, 0xaf, 0x9d, 0xea, 0x68, 0x7c, 0xfb, 0xf1, 0x67 127 }; 128 129 // Verify a 2048 bit RSA PKCS1.5 signature against an expected SHA-1 hash. 130 // Returns 0 on failure, 1 on success. 131 int RSA_verify(RSAPublicKey key, 132 const uint8_t* signature, 133 const int len, 134 const uint8_t* sha) { 135 uint8_t buf[RSANUMBYTES]; 136 int i; 137 138 if (key->len != RSANUMWORDS) { 139 return 0; // Wrong key passed in. 140 } 141 142 if (len != sizeof(buf)) { 143 return 0; // Wrong input length. 144 } 145 146 for (i = 0; i < len; ++i) { // Copy input to local workspace. 147 buf[i] = signature[i]; 148 } 149 150 modpowF4(key, buf); // In-place exponentiation. 151 152 // Xor sha portion, so it all becomes 00 iff equal. 153 for (i = len - SHA_DIGEST_SIZE; i < len; ++i) { 154 buf[i] ^= *sha++; 155 } 156 157 // Hash resulting buf, in-place. 158 SHA(buf, len, buf); 159 160 // Compare against expected hash value. 161 for (i = 0; i < SHA_DIGEST_SIZE; ++i) { 162 if (buf[i] != kExpectedPadShaRsa2048[i]) { 163 return 0; 164 } 165 } 166 167 return 1; // All checked out OK. 168 } 169