1 // Copyright (c) 2013 The Chromium 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 #include "chrome/browser/devtools/adb/android_rsa.h" 6 7 #include "base/base64.h" 8 #include "base/memory/scoped_ptr.h" 9 #include "chrome/browser/prefs/pref_service_syncable.h" 10 #include "chrome/browser/profiles/profile.h" 11 #include "chrome/common/pref_names.h" 12 #include "crypto/rsa_private_key.h" 13 #include "crypto/signature_creator.h" 14 #include "net/cert/asn1_util.h" 15 16 namespace { 17 18 const size_t kRSANumWords = 64; 19 const size_t kBigIntSize = 1024; 20 21 static const char kDummyRSAPublicKey[] = 22 "MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA6OSJ64q+ZLg7VV2ojEPh5TRbYjwbT" 23 "TifSPeFIV45CHnbTWYiiIn41wrozpYizNsMWZUBjdah1N78WVhbyDrnr0bDgFp+gXjfVppa3I" 24 "gjiohEcemK3omXi3GDMK8ERhriLUKfQS842SXtQ8I+KoZtpCkGM//0h7+P+Rhm0WwdipIRMhR" 25 "8haNAeyDiiCvqJcvevv2T52vqKtS3aWz+GjaTJJLVWydEpz9WdvWeLfFVhe2ZnqwwZNa30Qoj" 26 "fsnvjaMwK2MU7uYfRBPuvLyK5QESWBpArNDd6ULl8Y+NU6kwNOVDc87OASCVEM1gw2IMi2mo2" 27 "WO5ywp0UWRiGZCkK+wOFQIDAQAB"; 28 29 typedef struct RSAPublicKey { 30 int len; // Length of n[] in number of uint32 31 uint32 n0inv; // -1 / n[0] mod 2^32 32 uint32 n[kRSANumWords]; // modulus as little endian array 33 uint32 rr[kRSANumWords]; // R^2 as little endian array 34 int exponent; // 3 or 65537 35 } RSAPublicKey; 36 37 // http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm 38 // a * x + b * y = gcd(a, b) = d 39 void ExtendedEuclid(uint64 a, uint64 b, uint64 *x, uint64 *y, uint64 *d) { 40 uint64 x1 = 0, x2 = 1, y1 = 1, y2 = 0; 41 42 while (b > 0) { 43 uint64 q = a / b; 44 uint64 r = a % b; 45 *x = x2 - q * x1; 46 *y = y2 - q * y1; 47 a = b; 48 b = r; 49 x2 = x1; 50 x1 = *x; 51 y2 = y1; 52 y1 = *y; 53 } 54 55 *d = a; 56 *x = x2; 57 *y = y2; 58 } 59 60 uint32 ModInverse(uint64 a, uint64 m) 61 { 62 uint64 d, x, y; 63 ExtendedEuclid(a, m, &x, &y, &d); 64 if (d == 1) 65 return static_cast<uint32>(x); 66 return 0; 67 } 68 69 uint32* BnNew() { 70 uint32* result = new uint32[kBigIntSize]; 71 memset(result, 0, kBigIntSize * sizeof(uint32)); 72 return result; 73 } 74 75 void BnFree(uint32* a) { 76 delete[] a; 77 } 78 79 void BnPrint(const std::string& title, uint32_t* a) { 80 int i = kBigIntSize - 1; 81 fprintf(stderr, "%s: ", title.c_str()); 82 while (!a[i]) --i; 83 for (; i >= 0; --i) 84 fprintf(stderr, "%08x", a[i]); 85 fprintf(stderr, "\n"); 86 } 87 88 uint32* BnCopy(uint32* a) { 89 uint32* result = new uint32[kBigIntSize]; 90 memcpy(result, a, kBigIntSize * sizeof(uint32)); 91 return result; 92 } 93 94 void BnAdd(uint32* a, uint32* b) { 95 uint64 carry_over = 0; 96 for (size_t i = 0; i < kBigIntSize; ++i) { 97 carry_over += static_cast<uint64>(a[i]) + b[i]; 98 a[i] = carry_over & kuint32max; 99 carry_over >>= 32; 100 } 101 } 102 103 uint32* BnMul(uint32* a, uint32 b) { 104 uint32* result = BnNew(); 105 uint64 carry_over = 0; 106 for (size_t i = 0; i < kBigIntSize; ++i) { 107 carry_over += static_cast<uint64>(a[i]) * b; 108 result[i] = carry_over & kuint32max; 109 carry_over >>= 32; 110 } 111 return result; 112 } 113 114 void BnSub(uint32* a, uint32* b) { 115 int carry_over = 0; 116 for (size_t i = 0; i < kBigIntSize; ++i) { 117 int64 sub = static_cast<int64>(a[i]) - b[i] - carry_over; 118 carry_over = 0; 119 if (sub < 0) { 120 carry_over = 1; 121 sub += GG_LONGLONG(0x100000000); 122 } 123 a[i] = static_cast<uint32>(sub); 124 } 125 } 126 127 void BnLeftShift(uint32* a, int offset) { 128 for (int i = kBigIntSize - offset - 1; i >= 0; --i) 129 a[i + offset] = a[i]; 130 for (int i = 0; i < offset; ++i) 131 a[i] = 0; 132 } 133 134 int BnCompare(uint32* a, uint32* b) { 135 for (int i = kBigIntSize - 1; i >= 0; --i) { 136 if (a[i] > b[i]) 137 return 1; 138 if (a[i] < b[i]) 139 return -1; 140 } 141 return 0; 142 } 143 144 uint64 BnGuess(uint32* a, uint32* b, uint64 from, uint64 to) { 145 if (from + 1 >= to) 146 return from; 147 148 uint64 guess = (from + to) / 2; 149 uint32* t = BnMul(b, static_cast<uint32>(guess)); 150 int result = BnCompare(a, t); 151 BnFree(t); 152 if (result > 0) 153 return BnGuess(a, b, guess, to); 154 if (result < 0) 155 return BnGuess(a, b, from, guess); 156 return guess; 157 } 158 159 void BnDiv(uint32* a, uint32* b, uint32** pq, uint32** pr) { 160 if (BnCompare(a, b) < 0) { 161 if (pq) 162 *pq = BnNew(); 163 if (pr) 164 *pr = BnCopy(a); 165 return; 166 } 167 168 int oa = kBigIntSize - 1; 169 int ob = kBigIntSize - 1; 170 for (; oa > 0 && !a[oa]; --oa) {} 171 for (; ob > 0 && !b[ob]; --ob) {} 172 uint32* q = BnNew(); 173 uint32* ca = BnCopy(a); 174 175 int digit = a[oa] < b[ob] ? oa - ob - 1 : oa - ob; 176 177 for (; digit >= 0; --digit) { 178 uint32* shifted_b = BnCopy(b); 179 BnLeftShift(shifted_b, digit); 180 uint32 value = static_cast<uint32>( 181 BnGuess(ca, shifted_b, 0, static_cast<uint64>(kuint32max) + 1)); 182 q[digit] = value; 183 uint32* t = BnMul(shifted_b, value); 184 BnSub(ca, t); 185 BnFree(t); 186 BnFree(shifted_b); 187 } 188 189 if (pq) 190 *pq = q; 191 else 192 BnFree(q); 193 if (pr) 194 *pr = ca; 195 else 196 BnFree(ca); 197 } 198 199 } // namespace 200 201 crypto::RSAPrivateKey* AndroidRSAPrivateKey(Profile* profile) { 202 std::string encoded_key = 203 profile->GetPrefs()->GetString(prefs::kDevToolsAdbKey); 204 std::string decoded_key; 205 scoped_ptr<crypto::RSAPrivateKey> key; 206 if (!encoded_key.empty() && base::Base64Decode(encoded_key, &decoded_key)) { 207 std::vector<uint8> key_info(decoded_key.begin(), decoded_key.end()); 208 key.reset(crypto::RSAPrivateKey::CreateFromPrivateKeyInfo(key_info)); 209 } 210 if (!key) { 211 key.reset(crypto::RSAPrivateKey::Create(2048)); 212 std::vector<uint8> key_info; 213 if (!key || !key->ExportPrivateKey(&key_info)) 214 return NULL; 215 216 std::string key_string(key_info.begin(), key_info.end()); 217 if (base::Base64Encode(key_string, &encoded_key)) { 218 profile->GetPrefs()->SetString(prefs::kDevToolsAdbKey, 219 encoded_key); 220 } 221 } 222 return key.release(); 223 } 224 225 std::string AndroidRSAPublicKey(crypto::RSAPrivateKey* key) { 226 std::vector<uint8> public_key; 227 if (!key) 228 return kDummyRSAPublicKey; 229 230 key->ExportPublicKey(&public_key); 231 std::string asn1(public_key.begin(), public_key.end()); 232 233 base::StringPiece pk; 234 if (!net::asn1::ExtractSubjectPublicKeyFromSPKI(asn1, &pk)) 235 return kDummyRSAPublicKey; 236 237 // Skip 10 byte asn1 prefix to the modulus. 238 std::vector<uint8> pk_data(pk.data() + 10, pk.data() + pk.length()); 239 uint32* n = BnNew(); 240 for (size_t i = 0; i < kRSANumWords; ++i) { 241 uint32 t = pk_data[4 * i]; 242 t = t << 8; 243 t += pk_data[4 * i + 1]; 244 t = t << 8; 245 t += pk_data[4 * i + 2]; 246 t = t << 8; 247 t += pk_data[4 * i + 3]; 248 n[kRSANumWords - i - 1] = t; 249 } 250 uint64 n0 = n[0]; 251 252 RSAPublicKey pkey; 253 pkey.len = kRSANumWords; 254 pkey.exponent = 65537; // Fixed public exponent 255 pkey.n0inv = 0 - ModInverse(n0, GG_LONGLONG(0x100000000)); 256 if (pkey.n0inv == 0) 257 return kDummyRSAPublicKey; 258 259 uint32* r = BnNew(); 260 r[kRSANumWords * 2] = 1; 261 262 uint32* rr; 263 BnDiv(r, n, NULL, &rr); 264 265 for (size_t i = 0; i < kRSANumWords; ++i) { 266 pkey.n[i] = n[i]; 267 pkey.rr[i] = rr[i]; 268 } 269 270 BnFree(n); 271 BnFree(r); 272 BnFree(rr); 273 274 std::string output; 275 std::string input(reinterpret_cast<char*>(&pkey), sizeof(pkey)); 276 base::Base64Encode(input, &output); 277 return output; 278 } 279 280 std::string AndroidRSASign(crypto::RSAPrivateKey* key, 281 const std::string& body) { 282 std::vector<uint8> digest(body.begin(), body.end()); 283 std::vector<uint8> result; 284 if (!crypto::SignatureCreator::Sign(key, vector_as_array(&digest), 285 digest.size(), &result)) { 286 return std::string(); 287 } 288 return std::string(result.begin(), result.end()); 289 } 290
