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