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 <stddef.h> 8 #include <stdint.h> 9 10 #include <algorithm> 11 12 #include "base/logging.h" 13 #include "base/memory/scoped_ptr.h" 14 #include "base/strings/string_util.h" 15 16 // This file manually encodes and decodes RSA private keys using PrivateKeyInfo 17 // from PKCS #8 and RSAPrivateKey from PKCS #1. These structures are: 18 // 19 // PrivateKeyInfo ::= SEQUENCE { 20 // version Version, 21 // privateKeyAlgorithm PrivateKeyAlgorithmIdentifier, 22 // privateKey PrivateKey, 23 // attributes [0] IMPLICIT Attributes OPTIONAL 24 // } 25 // 26 // RSAPrivateKey ::= SEQUENCE { 27 // version Version, 28 // modulus INTEGER, 29 // publicExponent INTEGER, 30 // privateExponent INTEGER, 31 // prime1 INTEGER, 32 // prime2 INTEGER, 33 // exponent1 INTEGER, 34 // exponent2 INTEGER, 35 // coefficient INTEGER 36 // } 37 38 namespace { 39 // Helper for error handling during key import. 40 #define READ_ASSERT(truth) \ 41 if (!(truth)) { \ 42 NOTREACHED(); \ 43 return false; \ 44 } 45 } // namespace 46 47 namespace crypto { 48 49 const uint8_t PrivateKeyInfoCodec::kRsaAlgorithmIdentifier[] = { 50 0x30, 0x0D, 0x06, 0x09, 0x2A, 0x86, 0x48, 0x86, 51 0xF7, 0x0D, 0x01, 0x01, 0x01, 0x05, 0x00}; 52 53 PrivateKeyInfoCodec::PrivateKeyInfoCodec(bool big_endian) 54 : big_endian_(big_endian) {} 55 56 PrivateKeyInfoCodec::~PrivateKeyInfoCodec() {} 57 58 bool PrivateKeyInfoCodec::Export(std::vector<uint8_t>* output) { 59 std::list<uint8_t> content; 60 61 // Version (always zero) 62 uint8_t version = 0; 63 64 PrependInteger(coefficient_, &content); 65 PrependInteger(exponent2_, &content); 66 PrependInteger(exponent1_, &content); 67 PrependInteger(prime2_, &content); 68 PrependInteger(prime1_, &content); 69 PrependInteger(private_exponent_, &content); 70 PrependInteger(public_exponent_, &content); 71 PrependInteger(modulus_, &content); 72 PrependInteger(&version, 1, &content); 73 PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content); 74 PrependTypeHeaderAndLength(kOctetStringTag, content.size(), &content); 75 76 // RSA algorithm OID 77 for (size_t i = sizeof(kRsaAlgorithmIdentifier); i > 0; --i) 78 content.push_front(kRsaAlgorithmIdentifier[i - 1]); 79 80 PrependInteger(&version, 1, &content); 81 PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content); 82 83 // Copy everying into the output. 84 output->reserve(content.size()); 85 output->assign(content.begin(), content.end()); 86 87 return true; 88 } 89 90 bool PrivateKeyInfoCodec::ExportPublicKeyInfo(std::vector<uint8_t>* output) { 91 // Create a sequence with the modulus (n) and public exponent (e). 92 std::vector<uint8_t> 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_t> 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 output->assign(content.begin(), content.end()); 111 112 return true; 113 } 114 115 bool PrivateKeyInfoCodec::ExportPublicKey(std::vector<uint8_t>* output) { 116 // Create a sequence with the modulus (n) and public exponent (e). 117 std::list<uint8_t> content; 118 PrependInteger(&public_exponent_[0], 119 static_cast<int>(public_exponent_.size()), 120 &content); 121 PrependInteger(&modulus_[0], static_cast<int>(modulus_.size()), &content); 122 PrependTypeHeaderAndLength(kSequenceTag, content.size(), &content); 123 124 // Copy everything into the output. 125 output->reserve(content.size()); 126 output->assign(content.begin(), content.end()); 127 128 return true; 129 } 130 131 bool PrivateKeyInfoCodec::Import(const std::vector<uint8_t>& input) { 132 if (input.empty()) { 133 return false; 134 } 135 136 // Parse the private key info up to the public key values, ignoring 137 // the subsequent private key values. 138 uint8_t* src = const_cast<uint8_t*>(&input.front()); 139 uint8_t* end = src + input.size(); 140 if (!ReadSequence(&src, end) || 141 !ReadVersion(&src, end) || 142 !ReadAlgorithmIdentifier(&src, end) || 143 !ReadTypeHeaderAndLength(&src, end, kOctetStringTag, NULL) || 144 !ReadSequence(&src, end) || 145 !ReadVersion(&src, end) || 146 !ReadInteger(&src, end, &modulus_)) 147 return false; 148 149 int mod_size = modulus_.size(); 150 READ_ASSERT(mod_size % 2 == 0); 151 int primes_size = mod_size / 2; 152 153 if (!ReadIntegerWithExpectedSize(&src, end, 4, &public_exponent_) || 154 !ReadIntegerWithExpectedSize(&src, end, mod_size, &private_exponent_) || 155 !ReadIntegerWithExpectedSize(&src, end, primes_size, &prime1_) || 156 !ReadIntegerWithExpectedSize(&src, end, primes_size, &prime2_) || 157 !ReadIntegerWithExpectedSize(&src, end, primes_size, &exponent1_) || 158 !ReadIntegerWithExpectedSize(&src, end, primes_size, &exponent2_) || 159 !ReadIntegerWithExpectedSize(&src, end, primes_size, &coefficient_)) 160 return false; 161 162 READ_ASSERT(src == end); 163 164 165 return true; 166 } 167 168 void PrivateKeyInfoCodec::PrependInteger(const std::vector<uint8_t>& in, 169 std::list<uint8_t>* out) { 170 uint8_t* ptr = const_cast<uint8_t*>(&in.front()); 171 PrependIntegerImpl(ptr, in.size(), out, big_endian_); 172 } 173 174 // Helper to prepend an ASN.1 integer. 175 void PrivateKeyInfoCodec::PrependInteger(uint8_t* val, 176 int num_bytes, 177 std::list<uint8_t>* data) { 178 PrependIntegerImpl(val, num_bytes, data, big_endian_); 179 } 180 181 void PrivateKeyInfoCodec::PrependIntegerImpl(uint8_t* val, 182 int num_bytes, 183 std::list<uint8_t>* data, 184 bool big_endian) { 185 // Reverse input if little-endian. 186 std::vector<uint8_t> tmp; 187 if (!big_endian) { 188 tmp.assign(val, val + num_bytes); 189 std::reverse(tmp.begin(), tmp.end()); 190 val = &tmp.front(); 191 } 192 193 // ASN.1 integers are unpadded byte arrays, so skip any null padding bytes 194 // from the most-significant end of the integer. 195 int start = 0; 196 while (start < (num_bytes - 1) && val[start] == 0x00) { 197 start++; 198 num_bytes--; 199 } 200 PrependBytes(val, start, num_bytes, data); 201 202 // ASN.1 integers are signed. To encode a positive integer whose sign bit 203 // (the most significant bit) would otherwise be set and make the number 204 // negative, ASN.1 requires a leading null byte to force the integer to be 205 // positive. 206 uint8_t front = data->front(); 207 if ((front & 0x80) != 0) { 208 data->push_front(0x00); 209 num_bytes++; 210 } 211 212 PrependTypeHeaderAndLength(kIntegerTag, num_bytes, data); 213 } 214 215 bool PrivateKeyInfoCodec::ReadInteger(uint8_t** pos, 216 uint8_t* end, 217 std::vector<uint8_t>* out) { 218 return ReadIntegerImpl(pos, end, out, big_endian_); 219 } 220 221 bool PrivateKeyInfoCodec::ReadIntegerWithExpectedSize( 222 uint8_t** pos, 223 uint8_t* end, 224 size_t expected_size, 225 std::vector<uint8_t>* out) { 226 std::vector<uint8_t> temp; 227 if (!ReadIntegerImpl(pos, end, &temp, true)) // Big-Endian 228 return false; 229 230 int pad = expected_size - temp.size(); 231 int index = 0; 232 if (out->size() == expected_size + 1) { 233 READ_ASSERT(out->front() == 0x00); 234 pad++; 235 index++; 236 } else { 237 READ_ASSERT(out->size() <= expected_size); 238 } 239 240 out->insert(out->end(), pad, 0x00); 241 out->insert(out->end(), temp.begin(), temp.end()); 242 243 // Reverse output if little-endian. 244 if (!big_endian_) 245 std::reverse(out->begin(), out->end()); 246 return true; 247 } 248 249 bool PrivateKeyInfoCodec::ReadIntegerImpl(uint8_t** pos, 250 uint8_t* end, 251 std::vector<uint8_t>* out, 252 bool big_endian) { 253 uint32_t length = 0; 254 if (!ReadTypeHeaderAndLength(pos, end, kIntegerTag, &length) || !length) 255 return false; 256 257 // The first byte can be zero to force positiveness. We can ignore this. 258 if (**pos == 0x00) { 259 ++(*pos); 260 --length; 261 } 262 263 if (length) 264 out->insert(out->end(), *pos, (*pos) + length); 265 266 (*pos) += length; 267 268 // Reverse output if little-endian. 269 if (!big_endian) 270 std::reverse(out->begin(), out->end()); 271 return true; 272 } 273 274 void PrivateKeyInfoCodec::PrependBytes(uint8_t* val, 275 int start, 276 int num_bytes, 277 std::list<uint8_t>* data) { 278 while (num_bytes > 0) { 279 --num_bytes; 280 data->push_front(val[start + num_bytes]); 281 } 282 } 283 284 void PrivateKeyInfoCodec::PrependLength(size_t size, std::list<uint8_t>* data) { 285 // The high bit is used to indicate whether additional octets are needed to 286 // represent the length. 287 if (size < 0x80) { 288 data->push_front(static_cast<uint8_t>(size)); 289 } else { 290 uint8_t num_bytes = 0; 291 while (size > 0) { 292 data->push_front(static_cast<uint8_t>(size & 0xFF)); 293 size >>= 8; 294 num_bytes++; 295 } 296 CHECK_LE(num_bytes, 4); 297 data->push_front(0x80 | num_bytes); 298 } 299 } 300 301 void PrivateKeyInfoCodec::PrependTypeHeaderAndLength( 302 uint8_t type, 303 uint32_t length, 304 std::list<uint8_t>* output) { 305 PrependLength(length, output); 306 output->push_front(type); 307 } 308 309 void PrivateKeyInfoCodec::PrependBitString(uint8_t* val, 310 int num_bytes, 311 std::list<uint8_t>* output) { 312 // Start with the data. 313 PrependBytes(val, 0, num_bytes, output); 314 // Zero unused bits. 315 output->push_front(0); 316 // Add the length. 317 PrependLength(num_bytes + 1, output); 318 // Finally, add the bit string tag. 319 output->push_front((uint8_t)kBitStringTag); 320 } 321 322 bool PrivateKeyInfoCodec::ReadLength(uint8_t** pos, 323 uint8_t* end, 324 uint32_t* result) { 325 READ_ASSERT(*pos < end); 326 int length = 0; 327 328 // If the MSB is not set, the length is just the byte itself. 329 if (!(**pos & 0x80)) { 330 length = **pos; 331 (*pos)++; 332 } else { 333 // Otherwise, the lower 7 indicate the length of the length. 334 int length_of_length = **pos & 0x7F; 335 READ_ASSERT(length_of_length <= 4); 336 (*pos)++; 337 READ_ASSERT(*pos + length_of_length < end); 338 339 length = 0; 340 for (int i = 0; i < length_of_length; ++i) { 341 length <<= 8; 342 length |= **pos; 343 (*pos)++; 344 } 345 } 346 347 READ_ASSERT(*pos + length <= end); 348 if (result) *result = length; 349 return true; 350 } 351 352 bool PrivateKeyInfoCodec::ReadTypeHeaderAndLength(uint8_t** pos, 353 uint8_t* end, 354 uint8_t expected_tag, 355 uint32_t* length) { 356 READ_ASSERT(*pos < end); 357 READ_ASSERT(**pos == expected_tag); 358 (*pos)++; 359 360 return ReadLength(pos, end, length); 361 } 362 363 bool PrivateKeyInfoCodec::ReadSequence(uint8_t** pos, uint8_t* end) { 364 return ReadTypeHeaderAndLength(pos, end, kSequenceTag, NULL); 365 } 366 367 bool PrivateKeyInfoCodec::ReadAlgorithmIdentifier(uint8_t** pos, uint8_t* end) { 368 READ_ASSERT(*pos + sizeof(kRsaAlgorithmIdentifier) < end); 369 READ_ASSERT(memcmp(*pos, kRsaAlgorithmIdentifier, 370 sizeof(kRsaAlgorithmIdentifier)) == 0); 371 (*pos) += sizeof(kRsaAlgorithmIdentifier); 372 return true; 373 } 374 375 bool PrivateKeyInfoCodec::ReadVersion(uint8_t** pos, uint8_t* end) { 376 uint32_t length = 0; 377 if (!ReadTypeHeaderAndLength(pos, end, kIntegerTag, &length)) 378 return false; 379 380 // The version should be zero. 381 for (uint32_t i = 0; i < length; ++i) { 382 READ_ASSERT(**pos == 0x00); 383 (*pos)++; 384 } 385 386 return true; 387 } 388 389 } // namespace crypto 390
