Home | History | Annotate | Download | only in crypto 
      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 
     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
    385