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   output->assign(content.begin(), content.end());
  85
  86   return true;
  87 }
  88
  89 bool 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
 114 bool 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
 130 bool 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
 167 void 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.
 174 void PrivateKeyInfoCodec::PrependInteger(uint8* val,
 175                                          int num_bytes,
 176                                          std::list<uint8>* data) {
 177   PrependIntegerImpl(val, num_bytes, data, big_endian_);
 178 }
 179
 180 void 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
 214 bool PrivateKeyInfoCodec::ReadInteger(uint8** pos,
 215                                       uint8* end,
 216                                       std::vector<uint8>* out) {
 217   return ReadIntegerImpl(pos, end, out, big_endian_);
 218 }
 219
 220 bool 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
 247 bool 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
 272 void 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
 282 void 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
 299 void PrivateKeyInfoCodec::PrependTypeHeaderAndLength(uint8 type,
 300                                                      uint32 length,
 301                                                      std::list<uint8>* output) {
 302   PrependLength(length, output);
 303   output->push_front(type);
 304 }
 305
 306 void 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
 319 bool 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
 347 bool 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
 358 bool PrivateKeyInfoCodec::ReadSequence(uint8** pos, uint8* end) {
 359   return ReadTypeHeaderAndLength(pos, end, kSequenceTag, NULL);
 360 }
 361
 362 bool 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
 370 bool 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