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
16namespace {
17
18const size_t kRSANumWords = 64;
19const size_t kBigIntSize = 1024;
20
21static 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
29typedef 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
39void 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
60uint32 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
69uint32* BnNew() {
70  uint32* result = new uint32[kBigIntSize];
71  memset(result, 0, kBigIntSize * sizeof(uint32));
72  return result;
73}
74
75void BnFree(uint32* a) {
76  delete[] a;
77}
78
79uint32* BnCopy(uint32* a) {
80  uint32* result = new uint32[kBigIntSize];
81  memcpy(result, a, kBigIntSize * sizeof(uint32));
82  return result;
83}
84
85uint32* 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;
91    carry_over >>= 32;
92  }
93  return result;
94}
95
96void BnSub(uint32* a, uint32* b) {
97  int carry_over = 0;
98  for (size_t i = 0; i < kBigIntSize; ++i) {
99    int64 sub = static_cast<int64>(a[i]) - b[i] - carry_over;
100    carry_over = 0;
101    if (sub < 0) {
102      carry_over = 1;
103      sub += GG_LONGLONG(0x100000000);
104    }
105    a[i] = static_cast<uint32>(sub);
106  }
107}
108
109void 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)
113    a[i] = 0;
114}
115
116int BnCompare(uint32* a, uint32* b) {
117  for (int i = kBigIntSize - 1; i >= 0; --i) {
118    if (a[i] > b[i])
119      return 1;
120    if (a[i] < b[i])
121      return -1;
122  }
123  return 0;
124}
125
126uint64 BnGuess(uint32* a, uint32* b, uint64 from, uint64 to) {
127  if (from + 1 >= to)
128    return from;
129
130  uint64 guess = (from + to) / 2;
131  uint32* t = BnMul(b, static_cast<uint32>(guess));
132  int result = BnCompare(a, t);
133  BnFree(t);
134  if (result > 0)
135    return BnGuess(a, b, guess, to);
136  if (result < 0)
137    return BnGuess(a, b, from, guess);
138  return guess;
139}
140
141void BnDiv(uint32* a, uint32* b, uint32** pq, uint32** pr) {
142  if (BnCompare(a, b) < 0) {
143    if (pq)
144      *pq = BnNew();
145    if (pr)
146      *pr = BnCopy(a);
147    return;
148  }
149
150  int oa = kBigIntSize - 1;
151  int ob = kBigIntSize - 1;
152  for (; oa > 0 && !a[oa]; --oa) {}
153  for (; ob > 0 && !b[ob]; --ob) {}
154  uint32* q = BnNew();
155  uint32* ca = BnCopy(a);
156
157  int digit = a[oa] < b[ob] ? oa - ob - 1 : oa - ob;
158
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));
164    q[digit] = value;
165    uint32* t = BnMul(shifted_b, value);
166    BnSub(ca, t);
167    BnFree(t);
168    BnFree(shifted_b);
169  }
170
171  if (pq)
172    *pq = q;
173  else
174    BnFree(q);
175  if (pr)
176    *pr = ca;
177  else
178    BnFree(ca);
179}
180
181}  // namespace
182
183crypto::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));
191  }
192  if (!key) {
193    key.reset(crypto::RSAPrivateKey::Create(2048));
194    std::vector<uint8> key_info;
195    if (!key || !key->ExportPrivateKey(&key_info))
196      return NULL;
197
198    std::string key_string(key_info.begin(), key_info.end());
199    base::Base64Encode(key_string, &encoded_key);
200    profile->GetPrefs()->SetString(prefs::kDevToolsAdbKey,
201                                   encoded_key);
202  }
203  return key.release();
204}
205
206std::string AndroidRSAPublicKey(crypto::RSAPrivateKey* key) {
207  std::vector<uint8> public_key;
208  if (!key)
209    return kDummyRSAPublicKey;
210
211  key->ExportPublicKey(&public_key);
212  std::string asn1(public_key.begin(), public_key.end());
213
214  base::StringPiece pk;
215  if (!net::asn1::ExtractSubjectPublicKeyFromSPKI(asn1, &pk))
216    return kDummyRSAPublicKey;
217
218  // Skip 10 byte asn1 prefix to the modulus.
219  std::vector<uint8> pk_data(pk.data() + 10, pk.data() + pk.length());
220  uint32* n = BnNew();
221  for (size_t i = 0; i < kRSANumWords; ++i) {
222    uint32 t = pk_data[4 * i];
223    t = t << 8;
224    t += pk_data[4 * i + 1];
225    t = t << 8;
226    t += pk_data[4 * i + 2];
227    t = t << 8;
228    t += pk_data[4 * i + 3];
229    n[kRSANumWords - i - 1] = t;
230  }
231  uint64 n0 = n[0];
232
233  RSAPublicKey pkey;
234  pkey.len = kRSANumWords;
235  pkey.exponent = 65537; // Fixed public exponent
236  pkey.n0inv = 0 - ModInverse(n0, GG_LONGLONG(0x100000000));
237  if (pkey.n0inv == 0)
238    return kDummyRSAPublicKey;
239
240  uint32* r = BnNew();
241  r[kRSANumWords * 2] = 1;
242
243  uint32* rr;
244  BnDiv(r, n, NULL, &rr);
245
246  for (size_t i = 0; i < kRSANumWords; ++i) {
247    pkey.n[i] = n[i];
248    pkey.rr[i] = rr[i];
249  }
250
251  BnFree(n);
252  BnFree(r);
253  BnFree(rr);
254
255  std::string output;
256  std::string input(reinterpret_cast<char*>(&pkey), sizeof(pkey));
257  base::Base64Encode(input, &output);
258  return output;
259}
260
261std::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();
268  }
269  return std::string(result.begin(), result.end());
270}
271