1/* rsa_e_f4.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 31// a[] -= mod 32static void subM(const RSAPublicKey* key, 33 uint32_t* a) { 34 int64_t A = 0; 35 int i; 36 for (i = 0; i < key->len; ++i) { 37 A += (uint64_t)a[i] - key->n[i]; 38 a[i] = (uint32_t)A; 39 A >>= 32; 40 } 41} 42 43// return a[] >= mod 44static int geM(const RSAPublicKey* key, 45 const uint32_t* a) { 46 int i; 47 for (i = key->len; i;) { 48 --i; 49 if (a[i] < key->n[i]) return 0; 50 if (a[i] > key->n[i]) return 1; 51 } 52 return 1; // equal 53} 54 55// montgomery c[] += a * b[] / R % mod 56static void montMulAdd(const RSAPublicKey* key, 57 uint32_t* c, 58 const uint32_t a, 59 const uint32_t* b) { 60 uint64_t A = (uint64_t)a * b[0] + c[0]; 61 uint32_t d0 = (uint32_t)A * key->n0inv; 62 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; 63 int i; 64 65 for (i = 1; i < key->len; ++i) { 66 A = (A >> 32) + (uint64_t)a * b[i] + c[i]; 67 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; 68 c[i - 1] = (uint32_t)B; 69 } 70 71 A = (A >> 32) + (B >> 32); 72 73 c[i - 1] = (uint32_t)A; 74 75 if (A >> 32) { 76 subM(key, c); 77 } 78} 79 80// montgomery c[] = a[] * b[] / R % mod 81static void montMul(const RSAPublicKey* key, 82 uint32_t* c, 83 const uint32_t* a, 84 const uint32_t* b) { 85 int i; 86 for (i = 0; i < key->len; ++i) { 87 c[i] = 0; 88 } 89 for (i = 0; i < key->len; ++i) { 90 montMulAdd(key, c, a[i], b); 91 } 92} 93 94// In-place public exponentiation. 95// Input and output big-endian byte array in inout. 96static void modpowF4(const RSAPublicKey* key, 97 uint8_t* inout) { 98 uint32_t a[RSANUMWORDS]; 99 uint32_t aR[RSANUMWORDS]; 100 uint32_t aaR[RSANUMWORDS]; 101 uint32_t* aaa = aaR; // Re-use location. 102 int i; 103 104 // Convert from big endian byte array to little endian word array. 105 for (i = 0; i < key->len; ++i) { 106 uint32_t tmp = 107 (inout[((key->len - 1 - i) * 4) + 0] << 24) | 108 (inout[((key->len - 1 - i) * 4) + 1] << 16) | 109 (inout[((key->len - 1 - i) * 4) + 2] << 8) | 110 (inout[((key->len - 1 - i) * 4) + 3] << 0); 111 a[i] = tmp; 112 } 113 114 montMul(key, aR, a, key->rr); // aR = a * RR / R mod M 115 for (i = 0; i < 16; i += 2) { 116 montMul(key, aaR, aR, aR); // aaR = aR * aR / R mod M 117 montMul(key, aR, aaR, aaR); // aR = aaR * aaR / R mod M 118 } 119 montMul(key, aaa, aR, a); // aaa = aR * a / R mod M 120 121 // Make sure aaa < mod; aaa is at most 1x mod too large. 122 if (geM(key, aaa)) { 123 subM(key, aaa); 124 } 125 126 // Convert to bigendian byte array 127 for (i = key->len - 1; i >= 0; --i) { 128 uint32_t tmp = aaa[i]; 129 *inout++ = tmp >> 24; 130 *inout++ = tmp >> 16; 131 *inout++ = tmp >> 8; 132 *inout++ = tmp >> 0; 133 } 134} 135 136// Expected PKCS1.5 signature padding bytes, for a keytool RSA signature. 137// Has the 0-length optional parameter encoded in the ASN1 (as opposed to the 138// other flavor which omits the optional parameter entirely). This code does not 139// accept signatures without the optional parameter. 140/* 141static const uint8_t padding[RSANUMBYTES] = { 1420x00,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 143}; 144*/ 145 146// SHA-1 of PKCS1.5 signature padding for 2048 bit, as above. 147// At the location of the bytes of the hash all 00 are hashed. 148static const uint8_t kExpectedPadShaRsa2048[SHA_DIGEST_SIZE] = { 149 0xdc, 0xbd, 0xbe, 0x42, 0xd5, 0xf5, 0xa7, 0x2e, 0x6e, 0xfc, 150 0xf5, 0x5d, 0xaf, 0x9d, 0xea, 0x68, 0x7c, 0xfb, 0xf1, 0x67 151}; 152 153// Verify a 2048 bit RSA e=65537 PKCS1.5 signature against an expected 154// SHA-1 hash. Returns 0 on failure, 1 on success. 155int RSA_e_f4_verify(const RSAPublicKey* key, 156 const uint8_t* signature, 157 const int len, 158 const uint8_t* sha) { 159 uint8_t buf[RSANUMBYTES]; 160 int i; 161 162 if (key->len != RSANUMWORDS) { 163 return 0; // Wrong key passed in. 164 } 165 166 if (len != sizeof(buf)) { 167 return 0; // Wrong input length. 168 } 169 170 if (key->exponent != 65537) { 171 return 0; // Wrong exponent. 172 } 173 174 for (i = 0; i < len; ++i) { // Copy input to local workspace. 175 buf[i] = signature[i]; 176 } 177 178 modpowF4(key, buf); // In-place exponentiation. 179 180 // Xor sha portion, so it all becomes 00 iff equal. 181 for (i = len - SHA_DIGEST_SIZE; i < len; ++i) { 182 buf[i] ^= *sha++; 183 } 184 185 // Hash resulting buf, in-place. 186 SHA(buf, len, buf); 187 188 // Compare against expected hash value. 189 for (i = 0; i < SHA_DIGEST_SIZE; ++i) { 190 if (buf[i] != kExpectedPadShaRsa2048[i]) { 191 return 0; 192 } 193 } 194 195 return 1; // All checked out OK. 196} 197