1// Copyright (c) 2011 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 "crypto/rsa_private_key.h"
6
7#include <algorithm>
8#include <list>
9
10#include "base/logging.h"
11#include "base/memory/scoped_ptr.h"
12#include "base/strings/string_util.h"
13
14// This file manually encodes and decodes RSA private keys using PrivateKeyInfo
15// from PKCS #8 and RSAPrivateKey from PKCS #1. These structures are:
16//
17// PrivateKeyInfo ::= SEQUENCE {
18//   version Version,
19//   privateKeyAlgorithm PrivateKeyAlgorithmIdentifier,
20//   privateKey PrivateKey,
21//   attributes [0] IMPLICIT Attributes OPTIONAL
22// }
23//
24// RSAPrivateKey ::= SEQUENCE {
25//   version Version,
26//   modulus INTEGER,
27//   publicExponent INTEGER,
28//   privateExponent INTEGER,
29//   prime1 INTEGER,
30//   prime2 INTEGER,
31//   exponent1 INTEGER,
32//   exponent2 INTEGER,
33//   coefficient INTEGER
34// }
35
36namespace {
37// Helper for error handling during key import.
38#define READ_ASSERT(truth) \
39  if (!(truth)) { \
40    NOTREACHED(); \
41    return false; \
42  }
43}  // namespace
44
45namespace crypto {
46
47const uint8 PrivateKeyInfoCodec::kRsaAlgorithmIdentifier[] = {
48  0x30, 0x0D, 0x06, 0x09, 0x2A, 0x86, 0x48, 0x86, 0xF7, 0x0D, 0x01, 0x01, 0x01,
49  0x05, 0x00
50};
51
52PrivateKeyInfoCodec::PrivateKeyInfoCodec(bool big_endian)
53    : big_endian_(big_endian) {}
54
55PrivateKeyInfoCodec::~PrivateKeyInfoCodec() {}
56
57bool PrivateKeyInfoCodec::Export(std::vector<uint8>* output) {
58  std::list<uint8> content;
59
60  // Version (always zero)
61  uint8 version = 0;
62
63  PrependInteger(coefficient_, &content);
64  PrependInteger(exponent2_, &content);
65  PrependInteger(exponent1_, &content);
66  PrependInteger(prime2_, &content);
67  PrependInteger(prime1_, &content);
68  PrependInteger(private_exponent_, &content);
69  PrependInteger(public_exponent_, &content);
70  PrependInteger(modulus_, &content);
71  PrependInteger(&version, 1, &content);
72  PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content);
73  PrependTypeHeaderAndLength(kOctetStringTag, content.size(), &content);
74
75  // RSA algorithm OID
76  for (size_t i = sizeof(kRsaAlgorithmIdentifier); i > 0; --i)
77    content.push_front(kRsaAlgorithmIdentifier[i - 1]);
78
79  PrependInteger(&version, 1, &content);
80  PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content);
81
82  // Copy everying into the output.
83  output->reserve(content.size());
84  output->assign(content.begin(), content.end());
85
86  return true;
87}
88
89bool PrivateKeyInfoCodec::ExportPublicKeyInfo(std::vector<uint8>* output) {
90  // Create a sequence with the modulus (n) and public exponent (e).
91  std::vector<uint8> bit_string;
92  if (!ExportPublicKey(&bit_string))
93    return false;
94
95  // Add the sequence as the contents of a bit string.
96  std::list<uint8> content;
97  PrependBitString(&bit_string[0], static_cast<int>(bit_string.size()),
98                   &content);
99
100  // Add the RSA algorithm OID.
101  for (size_t i = sizeof(kRsaAlgorithmIdentifier); i > 0; --i)
102    content.push_front(kRsaAlgorithmIdentifier[i - 1]);
103
104  // Finally, wrap everything in a sequence.
105  PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content);
106
107  // Copy everything into the output.
108  output->reserve(content.size());
109  output->assign(content.begin(), content.end());
110
111  return true;
112}
113
114bool PrivateKeyInfoCodec::ExportPublicKey(std::vector<uint8>* output) {
115  // Create a sequence with the modulus (n) and public exponent (e).
116  std::list<uint8> content;
117  PrependInteger(&public_exponent_[0],
118                 static_cast<int>(public_exponent_.size()),
119                 &content);
120  PrependInteger(&modulus_[0],  static_cast<int>(modulus_.size()), &content);
121  PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content);
122
123  // Copy everything into the output.
124  output->reserve(content.size());
125  output->assign(content.begin(), content.end());
126
127  return true;
128}
129
130bool PrivateKeyInfoCodec::Import(const std::vector<uint8>& input) {
131  if (input.empty()) {
132    return false;
133  }
134
135  // Parse the private key info up to the public key values, ignoring
136  // the subsequent private key values.
137  uint8* src = const_cast<uint8*>(&input.front());
138  uint8* end = src + input.size();
139  if (!ReadSequence(&src, end) ||
140      !ReadVersion(&src, end) ||
141      !ReadAlgorithmIdentifier(&src, end) ||
142      !ReadTypeHeaderAndLength(&src, end, kOctetStringTag, NULL) ||
143      !ReadSequence(&src, end) ||
144      !ReadVersion(&src, end) ||
145      !ReadInteger(&src, end, &modulus_))
146    return false;
147
148  int mod_size = modulus_.size();
149  READ_ASSERT(mod_size % 2 == 0);
150  int primes_size = mod_size / 2;
151
152  if (!ReadIntegerWithExpectedSize(&src, end, 4, &public_exponent_) ||
153      !ReadIntegerWithExpectedSize(&src, end, mod_size, &private_exponent_) ||
154      !ReadIntegerWithExpectedSize(&src, end, primes_size, &prime1_) ||
155      !ReadIntegerWithExpectedSize(&src, end, primes_size, &prime2_) ||
156      !ReadIntegerWithExpectedSize(&src, end, primes_size, &exponent1_) ||
157      !ReadIntegerWithExpectedSize(&src, end, primes_size, &exponent2_) ||
158      !ReadIntegerWithExpectedSize(&src, end, primes_size, &coefficient_))
159    return false;
160
161  READ_ASSERT(src == end);
162
163
164  return true;
165}
166
167void PrivateKeyInfoCodec::PrependInteger(const std::vector<uint8>& in,
168                                         std::list<uint8>* out) {
169  uint8* ptr = const_cast<uint8*>(&in.front());
170  PrependIntegerImpl(ptr, in.size(), out, big_endian_);
171}
172
173// Helper to prepend an ASN.1 integer.
174void PrivateKeyInfoCodec::PrependInteger(uint8* val,
175                                         int num_bytes,
176                                         std::list<uint8>* data) {
177  PrependIntegerImpl(val, num_bytes, data, big_endian_);
178}
179
180void PrivateKeyInfoCodec::PrependIntegerImpl(uint8* val,
181                                             int num_bytes,
182                                             std::list<uint8>* data,
183                                             bool big_endian) {
184 // Reverse input if little-endian.
185 std::vector<uint8> tmp;
186 if (!big_endian) {
187   tmp.assign(val, val + num_bytes);
188   std::reverse(tmp.begin(), tmp.end());
189   val = &tmp.front();
190 }
191
192  // ASN.1 integers are unpadded byte arrays, so skip any null padding bytes
193  // from the most-significant end of the integer.
194  int start = 0;
195  while (start < (num_bytes - 1) && val[start] == 0x00) {
196    start++;
197    num_bytes--;
198  }
199  PrependBytes(val, start, num_bytes, data);
200
201  // ASN.1 integers are signed. To encode a positive integer whose sign bit
202  // (the most significant bit) would otherwise be set and make the number
203  // negative, ASN.1 requires a leading null byte to force the integer to be
204  // positive.
205  uint8 front = data->front();
206  if ((front & 0x80) != 0) {
207    data->push_front(0x00);
208    num_bytes++;
209  }
210
211  PrependTypeHeaderAndLength(kIntegerTag, num_bytes, data);
212}
213
214bool PrivateKeyInfoCodec::ReadInteger(uint8** pos,
215                                      uint8* end,
216                                      std::vector<uint8>* out) {
217  return ReadIntegerImpl(pos, end, out, big_endian_);
218}
219
220bool PrivateKeyInfoCodec::ReadIntegerWithExpectedSize(uint8** pos,
221                                                      uint8* end,
222                                                      size_t expected_size,
223                                                      std::vector<uint8>* out) {
224  std::vector<uint8> temp;
225  if (!ReadIntegerImpl(pos, end, &temp, true))  // Big-Endian
226    return false;
227
228  int pad = expected_size - temp.size();
229  int index = 0;
230  if (out->size() == expected_size + 1) {
231    READ_ASSERT(out->front() == 0x00);
232    pad++;
233    index++;
234  } else {
235    READ_ASSERT(out->size() <= expected_size);
236  }
237
238  out->insert(out->end(), pad, 0x00);
239  out->insert(out->end(), temp.begin(), temp.end());
240
241  // Reverse output if little-endian.
242  if (!big_endian_)
243    std::reverse(out->begin(), out->end());
244  return true;
245}
246
247bool PrivateKeyInfoCodec::ReadIntegerImpl(uint8** pos,
248                                          uint8* end,
249                                          std::vector<uint8>* out,
250                                          bool big_endian) {
251  uint32 length = 0;
252  if (!ReadTypeHeaderAndLength(pos, end, kIntegerTag, &length) || !length)
253    return false;
254
255  // The first byte can be zero to force positiveness. We can ignore this.
256  if (**pos == 0x00) {
257    ++(*pos);
258    --length;
259  }
260
261  if (length)
262    out->insert(out->end(), *pos, (*pos) + length);
263
264  (*pos) += length;
265
266  // Reverse output if little-endian.
267  if (!big_endian)
268    std::reverse(out->begin(), out->end());
269  return true;
270}
271
272void PrivateKeyInfoCodec::PrependBytes(uint8* val,
273                                       int start,
274                                       int num_bytes,
275                                       std::list<uint8>* data) {
276  while (num_bytes > 0) {
277    --num_bytes;
278    data->push_front(val[start + num_bytes]);
279  }
280}
281
282void PrivateKeyInfoCodec::PrependLength(size_t size, std::list<uint8>* data) {
283  // The high bit is used to indicate whether additional octets are needed to
284  // represent the length.
285  if (size < 0x80) {
286    data->push_front(static_cast<uint8>(size));
287  } else {
288    uint8 num_bytes = 0;
289    while (size > 0) {
290      data->push_front(static_cast<uint8>(size & 0xFF));
291      size >>= 8;
292      num_bytes++;
293    }
294    CHECK_LE(num_bytes, 4);
295    data->push_front(0x80 | num_bytes);
296  }
297}
298
299void PrivateKeyInfoCodec::PrependTypeHeaderAndLength(uint8 type,
300                                                     uint32 length,
301                                                     std::list<uint8>* output) {
302  PrependLength(length, output);
303  output->push_front(type);
304}
305
306void PrivateKeyInfoCodec::PrependBitString(uint8* val,
307                                           int num_bytes,
308                                           std::list<uint8>* output) {
309  // Start with the data.
310  PrependBytes(val, 0, num_bytes, output);
311  // Zero unused bits.
312  output->push_front(0);
313  // Add the length.
314  PrependLength(num_bytes + 1, output);
315  // Finally, add the bit string tag.
316  output->push_front((uint8) kBitStringTag);
317}
318
319bool PrivateKeyInfoCodec::ReadLength(uint8** pos, uint8* end, uint32* result) {
320  READ_ASSERT(*pos < end);
321  int length = 0;
322
323  // If the MSB is not set, the length is just the byte itself.
324  if (!(**pos & 0x80)) {
325    length = **pos;
326    (*pos)++;
327  } else {
328    // Otherwise, the lower 7 indicate the length of the length.
329    int length_of_length = **pos & 0x7F;
330    READ_ASSERT(length_of_length <= 4);
331    (*pos)++;
332    READ_ASSERT(*pos + length_of_length < end);
333
334    length = 0;
335    for (int i = 0; i < length_of_length; ++i) {
336      length <<= 8;
337      length |= **pos;
338      (*pos)++;
339    }
340  }
341
342  READ_ASSERT(*pos + length <= end);
343  if (result) *result = length;
344  return true;
345}
346
347bool PrivateKeyInfoCodec::ReadTypeHeaderAndLength(uint8** pos,
348                                                  uint8* end,
349                                                  uint8 expected_tag,
350                                                  uint32* length) {
351  READ_ASSERT(*pos < end);
352  READ_ASSERT(**pos == expected_tag);
353  (*pos)++;
354
355  return ReadLength(pos, end, length);
356}
357
358bool PrivateKeyInfoCodec::ReadSequence(uint8** pos, uint8* end) {
359  return ReadTypeHeaderAndLength(pos, end, kSequenceTag, NULL);
360}
361
362bool PrivateKeyInfoCodec::ReadAlgorithmIdentifier(uint8** pos, uint8* end) {
363  READ_ASSERT(*pos + sizeof(kRsaAlgorithmIdentifier) < end);
364  READ_ASSERT(memcmp(*pos, kRsaAlgorithmIdentifier,
365                     sizeof(kRsaAlgorithmIdentifier)) == 0);
366  (*pos) += sizeof(kRsaAlgorithmIdentifier);
367  return true;
368}
369
370bool PrivateKeyInfoCodec::ReadVersion(uint8** pos, uint8* end) {
371  uint32 length = 0;
372  if (!ReadTypeHeaderAndLength(pos, end, kIntegerTag, &length))
373    return false;
374
375  // The version should be zero.
376  for (uint32 i = 0; i < length; ++i) {
377    READ_ASSERT(**pos == 0x00);
378    (*pos)++;
379  }
380
381  return true;
382}
383
384}  // namespace crypto
385