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