crypto/rsa_private_key.cc

   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
  36 namespace {
  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
  45 namespace crypto {
  46
  47 const uint8 PrivateKeyInfoCodec::kRsaAlgorithmIdentifier[] = {
  48   0x30, 0x0D, 0x06, 0x09, 0x2A, 0x86, 0x48, 0x86, 0xF7, 0x0D, 0x01, 0x01, 0x01,
  49   0x05, 0x00
  50 };
  51
  52 PrivateKeyInfoCodec::PrivateKeyInfoCodec(bool big_endian)
  53     : big_endian_(big_endian) {}
  54
  55 PrivateKeyInfoCodec::~PrivateKeyInfoCodec() {}
  56
  57 bool 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
  90 bool 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
 116 bool 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
 133 bool 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
 170 void 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.
 177 void PrivateKeyInfoCodec::PrependInteger(uint8* val,
 178                                          int num_bytes,
 179                                          std::list<uint8>* data) {
 180   PrependIntegerImpl(val, num_bytes, data, big_endian_);
 181 }
 182
 183 void 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
 217 bool PrivateKeyInfoCodec::ReadInteger(uint8** pos,
 218                                       uint8* end,
 219                                       std::vector<uint8>* out) {
 220   return ReadIntegerImpl(pos, end, out, big_endian_);
 221 }
 222
 223 bool 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
 253 bool 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
 278 void 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
 288 void 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
 305 void PrivateKeyInfoCodec::PrependTypeHeaderAndLength(uint8 type,
 306                                                      uint32 length,
 307                                                      std::list<uint8>* output) {
 308   PrependLength(length, output);
 309   output->push_front(type);
 310 }
 311
 312 void 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
 325 bool 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
 353 bool 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
 364 bool PrivateKeyInfoCodec::ReadSequence(uint8** pos, uint8* end) {
 365   return ReadTypeHeaderAndLength(pos, end, kSequenceTag, NULL);
 366 }
 367
 368 bool 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
 376 bool 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