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/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  for (std::list<uint8>::iterator i = content.begin(); i != content.end(); ++i)
85    output->push_back(*i);
86
87  return true;
88}
89
90bool PrivateKeyInfoCodec::ExportPublicKeyInfo(std::vector<uint8>* output) {
91  // Create a sequence with the modulus (n) and public exponent (e).
92  std::vector<uint8> bit_string;
93  if (!ExportPublicKey(&bit_string))
94    return false;
95
96  // Add the sequence as the contents of a bit string.
97  std::list<uint8> content;
98  PrependBitString(&bit_string[0], static_cast<int>(bit_string.size()),
99                   &content);
100
101  // Add the RSA algorithm OID.
102  for (size_t i = sizeof(kRsaAlgorithmIdentifier); i > 0; --i)
103    content.push_front(kRsaAlgorithmIdentifier[i - 1]);
104
105  // Finally, wrap everything in a sequence.
106  PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content);
107
108  // Copy everything into the output.
109  output->reserve(content.size());
110  for (std::list<uint8>::iterator i = content.begin(); i != content.end(); ++i)
111    output->push_back(*i);
112
113  return true;
114}
115
116bool PrivateKeyInfoCodec::ExportPublicKey(std::vector<uint8>* output) {
117  // Create a sequence with the modulus (n) and public exponent (e).
118  std::list<uint8> content;
119  PrependInteger(&public_exponent_[0],
120                 static_cast<int>(public_exponent_.size()),
121                 &content);
122  PrependInteger(&modulus_[0],  static_cast<int>(modulus_.size()), &content);
123  PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content);
124
125  // Copy everything into the output.
126  output->reserve(content.size());
127  for (std::list<uint8>::iterator i = content.begin(); i != content.end(); ++i)
128    output->push_back(*i);
129
130  return true;
131}
132
133bool PrivateKeyInfoCodec::Import(const std::vector<uint8>& input) {
134  if (input.empty()) {
135    return false;
136  }
137
138  // Parse the private key info up to the public key values, ignoring
139  // the subsequent private key values.
140  uint8* src = const_cast<uint8*>(&input.front());
141  uint8* end = src + input.size();
142  if (!ReadSequence(&src, end) ||
143      !ReadVersion(&src, end) ||
144      !ReadAlgorithmIdentifier(&src, end) ||
145      !ReadTypeHeaderAndLength(&src, end, kOctetStringTag, NULL) ||
146      !ReadSequence(&src, end) ||
147      !ReadVersion(&src, end) ||
148      !ReadInteger(&src, end, &modulus_))
149    return false;
150
151  int mod_size = modulus_.size();
152  READ_ASSERT(mod_size % 2 == 0);
153  int primes_size = mod_size / 2;
154
155  if (!ReadIntegerWithExpectedSize(&src, end, 4, &public_exponent_) ||
156      !ReadIntegerWithExpectedSize(&src, end, mod_size, &private_exponent_) ||
157      !ReadIntegerWithExpectedSize(&src, end, primes_size, &prime1_) ||
158      !ReadIntegerWithExpectedSize(&src, end, primes_size, &prime2_) ||
159      !ReadIntegerWithExpectedSize(&src, end, primes_size, &exponent1_) ||
160      !ReadIntegerWithExpectedSize(&src, end, primes_size, &exponent2_) ||
161      !ReadIntegerWithExpectedSize(&src, end, primes_size, &coefficient_))
162    return false;
163
164  READ_ASSERT(src == end);
165
166
167  return true;
168}
169
170void PrivateKeyInfoCodec::PrependInteger(const std::vector<uint8>& in,
171                                         std::list<uint8>* out) {
172  uint8* ptr = const_cast<uint8*>(&in.front());
173  PrependIntegerImpl(ptr, in.size(), out, big_endian_);
174}
175
176// Helper to prepend an ASN.1 integer.
177void PrivateKeyInfoCodec::PrependInteger(uint8* val,
178                                         int num_bytes,
179                                         std::list<uint8>* data) {
180  PrependIntegerImpl(val, num_bytes, data, big_endian_);
181}
182
183void PrivateKeyInfoCodec::PrependIntegerImpl(uint8* val,
184                                             int num_bytes,
185                                             std::list<uint8>* data,
186                                             bool big_endian) {
187 // Reverse input if little-endian.
188 std::vector<uint8> tmp;
189 if (!big_endian) {
190   tmp.assign(val, val + num_bytes);
191   reverse(tmp.begin(), tmp.end());
192   val = &tmp.front();
193 }
194
195  // ASN.1 integers are unpadded byte arrays, so skip any null padding bytes
196  // from the most-significant end of the integer.
197  int start = 0;
198  while (start < (num_bytes - 1) && val[start] == 0x00) {
199    start++;
200    num_bytes--;
201  }
202  PrependBytes(val, start, num_bytes, data);
203
204  // ASN.1 integers are signed. To encode a positive integer whose sign bit
205  // (the most significant bit) would otherwise be set and make the number
206  // negative, ASN.1 requires a leading null byte to force the integer to be
207  // positive.
208  uint8 front = data->front();
209  if ((front & 0x80) != 0) {
210    data->push_front(0x00);
211    num_bytes++;
212  }
213
214  PrependTypeHeaderAndLength(kIntegerTag, num_bytes, data);
215}
216
217bool PrivateKeyInfoCodec::ReadInteger(uint8** pos,
218                                      uint8* end,
219                                      std::vector<uint8>* out) {
220  return ReadIntegerImpl(pos, end, out, big_endian_);
221}
222
223bool PrivateKeyInfoCodec::ReadIntegerWithExpectedSize(uint8** pos,
224                                                      uint8* end,
225                                                      size_t expected_size,
226                                                      std::vector<uint8>* out) {
227  std::vector<uint8> temp;
228  if (!ReadIntegerImpl(pos, end, &temp, true))  // Big-Endian
229    return false;
230
231  int pad = expected_size - temp.size();
232  int index = 0;
233  if (out->size() == expected_size + 1) {
234    READ_ASSERT(out->front() == 0x00);
235    pad++;
236    index++;
237  } else {
238    READ_ASSERT(out->size() <= expected_size);
239  }
240
241  while (pad) {
242    out->push_back(0x00);
243    pad--;
244  }
245  out->insert(out->end(), temp.begin(), temp.end());
246
247  // Reverse output if little-endian.
248  if (!big_endian_)
249    reverse(out->begin(), out->end());
250  return true;
251}
252
253bool PrivateKeyInfoCodec::ReadIntegerImpl(uint8** pos,
254                                          uint8* end,
255                                          std::vector<uint8>* out,
256                                          bool big_endian) {
257  uint32 length = 0;
258  if (!ReadTypeHeaderAndLength(pos, end, kIntegerTag, &length) || !length)
259    return false;
260
261  // The first byte can be zero to force positiveness. We can ignore this.
262  if (**pos == 0x00) {
263    ++(*pos);
264    --length;
265  }
266
267  if (length)
268    out->insert(out->end(), *pos, (*pos) + length);
269
270  (*pos) += length;
271
272  // Reverse output if little-endian.
273  if (!big_endian)
274    reverse(out->begin(), out->end());
275  return true;
276}
277
278void PrivateKeyInfoCodec::PrependBytes(uint8* val,
279                                       int start,
280                                       int num_bytes,
281                                       std::list<uint8>* data) {
282  while (num_bytes > 0) {
283    --num_bytes;
284    data->push_front(val[start + num_bytes]);
285  }
286}
287
288void PrivateKeyInfoCodec::PrependLength(size_t size, std::list<uint8>* data) {
289  // The high bit is used to indicate whether additional octets are needed to
290  // represent the length.
291  if (size < 0x80) {
292    data->push_front(static_cast<uint8>(size));
293  } else {
294    uint8 num_bytes = 0;
295    while (size > 0) {
296      data->push_front(static_cast<uint8>(size & 0xFF));
297      size >>= 8;
298      num_bytes++;
299    }
300    CHECK_LE(num_bytes, 4);
301    data->push_front(0x80 | num_bytes);
302  }
303}
304
305void PrivateKeyInfoCodec::PrependTypeHeaderAndLength(uint8 type,
306                                                     uint32 length,
307                                                     std::list<uint8>* output) {
308  PrependLength(length, output);
309  output->push_front(type);
310}
311
312void PrivateKeyInfoCodec::PrependBitString(uint8* val,
313                                           int num_bytes,
314                                           std::list<uint8>* output) {
315  // Start with the data.
316  PrependBytes(val, 0, num_bytes, output);
317  // Zero unused bits.
318  output->push_front(0);
319  // Add the length.
320  PrependLength(num_bytes + 1, output);
321  // Finally, add the bit string tag.
322  output->push_front((uint8) kBitStringTag);
323}
324
325bool PrivateKeyInfoCodec::ReadLength(uint8** pos, uint8* end, uint32* result) {
326  READ_ASSERT(*pos < end);
327  int length = 0;
328
329  // If the MSB is not set, the length is just the byte itself.
330  if (!(**pos & 0x80)) {
331    length = **pos;
332    (*pos)++;
333  } else {
334    // Otherwise, the lower 7 indicate the length of the length.
335    int length_of_length = **pos & 0x7F;
336    READ_ASSERT(length_of_length <= 4);
337    (*pos)++;
338    READ_ASSERT(*pos + length_of_length < end);
339
340    length = 0;
341    for (int i = 0; i < length_of_length; ++i) {
342      length <<= 8;
343      length |= **pos;
344      (*pos)++;
345    }
346  }
347
348  READ_ASSERT(*pos + length <= end);
349  if (result) *result = length;
350  return true;
351}
352
353bool PrivateKeyInfoCodec::ReadTypeHeaderAndLength(uint8** pos,
354                                                  uint8* end,
355                                                  uint8 expected_tag,
356                                                  uint32* length) {
357  READ_ASSERT(*pos < end);
358  READ_ASSERT(**pos == expected_tag);
359  (*pos)++;
360
361  return ReadLength(pos, end, length);
362}
363
364bool PrivateKeyInfoCodec::ReadSequence(uint8** pos, uint8* end) {
365  return ReadTypeHeaderAndLength(pos, end, kSequenceTag, NULL);
366}
367
368bool PrivateKeyInfoCodec::ReadAlgorithmIdentifier(uint8** pos, uint8* end) {
369  READ_ASSERT(*pos + sizeof(kRsaAlgorithmIdentifier) < end);
370  READ_ASSERT(memcmp(*pos, kRsaAlgorithmIdentifier,
371                     sizeof(kRsaAlgorithmIdentifier)) == 0);
372  (*pos) += sizeof(kRsaAlgorithmIdentifier);
373  return true;
374}
375
376bool PrivateKeyInfoCodec::ReadVersion(uint8** pos, uint8* end) {
377  uint32 length = 0;
378  if (!ReadTypeHeaderAndLength(pos, end, kIntegerTag, &length))
379    return false;
380
381  // The version should be zero.
382  for (uint32 i = 0; i < length; ++i) {
383    READ_ASSERT(**pos == 0x00);
384    (*pos)++;
385  }
386
387  return true;
388}
389
390}  // namespace crypto
391