1 // Copyright 2014 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.
5 #include "chrome/browser/devtools/device/usb/android_rsa.h"
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"
18 const size_t kRSANumWords = 64;
19 const size_t kBigIntSize = 1024;
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";
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
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;
60 uint32 ModInverse(uint64 a, uint64 m)
63 ExtendedEuclid(a, m, &x, &y, &d);
65 return static_cast<uint32>(x);
70 uint32* result = new uint32[kBigIntSize];
71 memset(result, 0, kBigIntSize * sizeof(uint32));
75 void BnFree(uint32* a) {
79 uint32* BnCopy(uint32* a) {
80 uint32* result = new uint32[kBigIntSize];
81 memcpy(result, a, kBigIntSize * sizeof(uint32));
85 uint32* BnMul(uint32* a, uint32 b) {
86 uint32* result = BnNew();
87 uint64 carry_over = 0;
88 for (size_t i = 0; i < kBigIntSize; ++i) {
89 carry_over += static_cast<uint64>(a[i]) * b;
90 result[i] = carry_over & kuint32max;
96 void BnSub(uint32* a, uint32* b) {
98 for (size_t i = 0; i < kBigIntSize; ++i) {
99 int64 sub = static_cast<int64>(a[i]) - b[i] - carry_over;
103 sub += 0x100000000LL;
105 a[i] = static_cast<uint32>(sub);
109 void BnLeftShift(uint32* a, int offset) {
110 for (int i = kBigIntSize - offset - 1; i >= 0; --i)
111 a[i + offset] = a[i];
112 for (int i = 0; i < offset; ++i)
116 int BnCompare(uint32* a, uint32* b) {
117 for (int i = kBigIntSize - 1; i >= 0; --i) {
126 uint64 BnGuess(uint32* a, uint32* b, uint64 from, uint64 to) {
130 uint64 guess = (from + to) / 2;
131 uint32* t = BnMul(b, static_cast<uint32>(guess));
132 int result = BnCompare(a, t);
135 return BnGuess(a, b, guess, to);
137 return BnGuess(a, b, from, guess);
141 void BnDiv(uint32* a, uint32* b, uint32** pq, uint32** pr) {
142 if (BnCompare(a, b) < 0) {
150 int oa = kBigIntSize - 1;
151 int ob = kBigIntSize - 1;
152 for (; oa > 0 && !a[oa]; --oa) {}
153 for (; ob > 0 && !b[ob]; --ob) {}
155 uint32* ca = BnCopy(a);
157 int digit = a[oa] < b[ob] ? oa - ob - 1 : oa - ob;
159 for (; digit >= 0; --digit) {
160 uint32* shifted_b = BnCopy(b);
161 BnLeftShift(shifted_b, digit);
162 uint32 value = static_cast<uint32>(
163 BnGuess(ca, shifted_b, 0, static_cast<uint64>(kuint32max) + 1));
165 uint32* t = BnMul(shifted_b, value);
183 crypto::RSAPrivateKey* AndroidRSAPrivateKey(Profile* profile) {
184 std::string encoded_key =
185 profile->GetPrefs()->GetString(prefs::kDevToolsAdbKey);
186 std::string decoded_key;
187 scoped_ptr<crypto::RSAPrivateKey> key;
188 if (!encoded_key.empty() && base::Base64Decode(encoded_key, &decoded_key)) {
189 std::vector<uint8> key_info(decoded_key.begin(), decoded_key.end());
190 key.reset(crypto::RSAPrivateKey::CreateFromPrivateKeyInfo(key_info));
193 key.reset(crypto::RSAPrivateKey::Create(2048));
194 std::vector<uint8> key_info;
195 if (!key || !key->ExportPrivateKey(&key_info))
198 std::string key_string(key_info.begin(), key_info.end());
199 base::Base64Encode(key_string, &encoded_key);
200 profile->GetPrefs()->SetString(prefs::kDevToolsAdbKey,
203 return key.release();
206 std::string AndroidRSAPublicKey(crypto::RSAPrivateKey* key) {
207 std::vector<uint8> public_key;
209 return kDummyRSAPublicKey;
211 key->ExportPublicKey(&public_key);
212 std::string asn1(public_key.begin(), public_key.end());
214 base::StringPiece pk;
215 if (!net::asn1::ExtractSubjectPublicKeyFromSPKI(asn1, &pk))
216 return kDummyRSAPublicKey;
218 // Skip 10 byte asn1 prefix to the modulus.
219 std::vector<uint8> pk_data(pk.data() + 10, pk.data() + pk.length());
221 for (size_t i = 0; i < kRSANumWords; ++i) {
222 uint32 t = pk_data[4 * i];
224 t += pk_data[4 * i + 1];
226 t += pk_data[4 * i + 2];
228 t += pk_data[4 * i + 3];
229 n[kRSANumWords - i - 1] = t;
234 pkey.len = kRSANumWords;
235 pkey.exponent = 65537; // Fixed public exponent
236 pkey.n0inv = 0 - ModInverse(n0, 0x100000000LL);
238 return kDummyRSAPublicKey;
241 r[kRSANumWords * 2] = 1;
244 BnDiv(r, n, NULL, &rr);
246 for (size_t i = 0; i < kRSANumWords; ++i) {
256 std::string input(reinterpret_cast<char*>(&pkey), sizeof(pkey));
257 base::Base64Encode(input, &output);
261 std::string AndroidRSASign(crypto::RSAPrivateKey* key,
262 const std::string& body) {
263 std::vector<uint8> digest(body.begin(), body.end());
264 std::vector<uint8> result;
265 if (!crypto::SignatureCreator::Sign(key, vector_as_array(&digest),
266 digest.size(), &result)) {
267 return std::string();
269 return std::string(result.begin(), result.end());