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