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
PrivateKeyInfoCodec(bool big_endian)52 PrivateKeyInfoCodec::PrivateKeyInfoCodec(bool big_endian)
53 : big_endian_(big_endian) {}
54
~PrivateKeyInfoCodec()55 PrivateKeyInfoCodec::~PrivateKeyInfoCodec() {}
56
Export(std::vector<uint8> * output)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
ExportPublicKeyInfo(std::vector<uint8> * output)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
ExportPublicKey(std::vector<uint8> * output)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
Import(const std::vector<uint8> & input)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
PrependInteger(const std::vector<uint8> & in,std::list<uint8> * out)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.
PrependInteger(uint8 * val,int num_bytes,std::list<uint8> * data)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
PrependIntegerImpl(uint8 * val,int num_bytes,std::list<uint8> * data,bool big_endian)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
ReadInteger(uint8 ** pos,uint8 * end,std::vector<uint8> * out)214 bool PrivateKeyInfoCodec::ReadInteger(uint8** pos,
215 uint8* end,
216 std::vector<uint8>* out) {
217 return ReadIntegerImpl(pos, end, out, big_endian_);
218 }
219
ReadIntegerWithExpectedSize(uint8 ** pos,uint8 * end,size_t expected_size,std::vector<uint8> * out)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
ReadIntegerImpl(uint8 ** pos,uint8 * end,std::vector<uint8> * out,bool big_endian)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
PrependBytes(uint8 * val,int start,int num_bytes,std::list<uint8> * data)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
PrependLength(size_t size,std::list<uint8> * data)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
PrependTypeHeaderAndLength(uint8 type,uint32 length,std::list<uint8> * output)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
PrependBitString(uint8 * val,int num_bytes,std::list<uint8> * output)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
ReadLength(uint8 ** pos,uint8 * end,uint32 * result)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
ReadTypeHeaderAndLength(uint8 ** pos,uint8 * end,uint8 expected_tag,uint32 * length)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
ReadSequence(uint8 ** pos,uint8 * end)358 bool PrivateKeyInfoCodec::ReadSequence(uint8** pos, uint8* end) {
359 return ReadTypeHeaderAndLength(pos, end, kSequenceTag, NULL);
360 }
361
ReadAlgorithmIdentifier(uint8 ** pos,uint8 * end)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
ReadVersion(uint8 ** pos,uint8 * end)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