1<?php
2
3/**
4 * Pure-PHP PKCS#1 (v2.1) compliant implementation of RSA.
5 *
6 * PHP version 5
7 *
8 * Here's an example of how to encrypt and decrypt text with this library:
9 * <code>
10 * <?php
11 *    include 'vendor/autoload.php';
12 *
13 *    $rsa = new \phpseclib\Crypt\RSA();
14 *    extract($rsa->createKey());
15 *
16 *    $plaintext = 'terrafrost';
17 *
18 *    $rsa->loadKey($privatekey);
19 *    $ciphertext = $rsa->encrypt($plaintext);
20 *
21 *    $rsa->loadKey($publickey);
22 *    echo $rsa->decrypt($ciphertext);
23 * ?>
24 * </code>
25 *
26 * Here's an example of how to create signatures and verify signatures with this library:
27 * <code>
28 * <?php
29 *    include 'vendor/autoload.php';
30 *
31 *    $rsa = new \phpseclib\Crypt\RSA();
32 *    extract($rsa->createKey());
33 *
34 *    $plaintext = 'terrafrost';
35 *
36 *    $rsa->loadKey($privatekey);
37 *    $signature = $rsa->sign($plaintext);
38 *
39 *    $rsa->loadKey($publickey);
40 *    echo $rsa->verify($plaintext, $signature) ? 'verified' : 'unverified';
41 * ?>
42 * </code>
43 *
44 * @category  Crypt
45 * @package   RSA
46 * @author    Jim Wigginton <terrafrost@php.net>
47 * @copyright 2009 Jim Wigginton
48 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
49 * @link      http://phpseclib.sourceforge.net
50 */
51
52namespace phpseclib\Crypt;
53
54use phpseclib\Math\BigInteger;
55
56/**
57 * Pure-PHP PKCS#1 compliant implementation of RSA.
58 *
59 * @package RSA
60 * @author  Jim Wigginton <terrafrost@php.net>
61 * @access  public
62 */
63class RSA
64{
65    /**#@+
66     * @access public
67     * @see self::encrypt()
68     * @see self::decrypt()
69     */
70    /**
71     * Use {@link http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding Optimal Asymmetric Encryption Padding}
72     * (OAEP) for encryption / decryption.
73     *
74     * Uses sha1 by default.
75     *
76     * @see self::setHash()
77     * @see self::setMGFHash()
78     */
79    const ENCRYPTION_OAEP = 1;
80    /**
81     * Use PKCS#1 padding.
82     *
83     * Although self::ENCRYPTION_OAEP offers more security, including PKCS#1 padding is necessary for purposes of backwards
84     * compatibility with protocols (like SSH-1) written before OAEP's introduction.
85     */
86    const ENCRYPTION_PKCS1 = 2;
87    /**
88     * Do not use any padding
89     *
90     * Although this method is not recommended it can none-the-less sometimes be useful if you're trying to decrypt some legacy
91     * stuff, if you're trying to diagnose why an encrypted message isn't decrypting, etc.
92     */
93    const ENCRYPTION_NONE = 3;
94    /**#@-*/
95
96    /**#@+
97     * @access public
98     * @see self::sign()
99     * @see self::verify()
100     * @see self::setHash()
101    */
102    /**
103     * Use the Probabilistic Signature Scheme for signing
104     *
105     * Uses sha1 by default.
106     *
107     * @see self::setSaltLength()
108     * @see self::setMGFHash()
109     */
110    const SIGNATURE_PSS = 1;
111    /**
112     * Use the PKCS#1 scheme by default.
113     *
114     * Although self::SIGNATURE_PSS offers more security, including PKCS#1 signing is necessary for purposes of backwards
115     * compatibility with protocols (like SSH-2) written before PSS's introduction.
116     */
117    const SIGNATURE_PKCS1 = 2;
118    /**#@-*/
119
120    /**#@+
121     * @access private
122     * @see \phpseclib\Crypt\RSA::createKey()
123    */
124    /**
125     * ASN1 Integer
126     */
127    const ASN1_INTEGER = 2;
128    /**
129     * ASN1 Bit String
130     */
131    const ASN1_BITSTRING = 3;
132    /**
133     * ASN1 Octet String
134     */
135    const ASN1_OCTETSTRING = 4;
136    /**
137     * ASN1 Object Identifier
138     */
139    const ASN1_OBJECT = 6;
140    /**
141     * ASN1 Sequence (with the constucted bit set)
142     */
143    const ASN1_SEQUENCE = 48;
144    /**#@-*/
145
146    /**#@+
147     * @access private
148     * @see \phpseclib\Crypt\RSA::__construct()
149    */
150    /**
151     * To use the pure-PHP implementation
152     */
153    const MODE_INTERNAL = 1;
154    /**
155     * To use the OpenSSL library
156     *
157     * (if enabled; otherwise, the internal implementation will be used)
158     */
159    const MODE_OPENSSL = 2;
160    /**#@-*/
161
162    /**#@+
163     * @access public
164     * @see \phpseclib\Crypt\RSA::createKey()
165     * @see \phpseclib\Crypt\RSA::setPrivateKeyFormat()
166    */
167    /**
168     * PKCS#1 formatted private key
169     *
170     * Used by OpenSSH
171     */
172    const PRIVATE_FORMAT_PKCS1 = 0;
173    /**
174     * PuTTY formatted private key
175     */
176    const PRIVATE_FORMAT_PUTTY = 1;
177    /**
178     * XML formatted private key
179     */
180    const PRIVATE_FORMAT_XML = 2;
181    /**
182     * PKCS#8 formatted private key
183     */
184    const PRIVATE_FORMAT_PKCS8 = 8;
185    /**
186     * OpenSSH formatted private key
187     */
188    const PRIVATE_FORMAT_OPENSSH = 9;
189    /**#@-*/
190
191    /**#@+
192     * @access public
193     * @see \phpseclib\Crypt\RSA::createKey()
194     * @see \phpseclib\Crypt\RSA::setPublicKeyFormat()
195    */
196    /**
197     * Raw public key
198     *
199     * An array containing two \phpseclib\Math\BigInteger objects.
200     *
201     * The exponent can be indexed with any of the following:
202     *
203     * 0, e, exponent, publicExponent
204     *
205     * The modulus can be indexed with any of the following:
206     *
207     * 1, n, modulo, modulus
208     */
209    const PUBLIC_FORMAT_RAW = 3;
210    /**
211     * PKCS#1 formatted public key (raw)
212     *
213     * Used by File/X509.php
214     *
215     * Has the following header:
216     *
217     * -----BEGIN RSA PUBLIC KEY-----
218     *
219     * Analogous to ssh-keygen's pem format (as specified by -m)
220     */
221    const PUBLIC_FORMAT_PKCS1 = 4;
222    const PUBLIC_FORMAT_PKCS1_RAW = 4;
223    /**
224     * XML formatted public key
225     */
226    const PUBLIC_FORMAT_XML = 5;
227    /**
228     * OpenSSH formatted public key
229     *
230     * Place in $HOME/.ssh/authorized_keys
231     */
232    const PUBLIC_FORMAT_OPENSSH = 6;
233    /**
234     * PKCS#1 formatted public key (encapsulated)
235     *
236     * Used by PHP's openssl_public_encrypt() and openssl's rsautl (when -pubin is set)
237     *
238     * Has the following header:
239     *
240     * -----BEGIN PUBLIC KEY-----
241     *
242     * Analogous to ssh-keygen's pkcs8 format (as specified by -m). Although PKCS8
243     * is specific to private keys it's basically creating a DER-encoded wrapper
244     * for keys. This just extends that same concept to public keys (much like ssh-keygen)
245     */
246    const PUBLIC_FORMAT_PKCS8 = 7;
247    /**#@-*/
248
249    /**
250     * Precomputed Zero
251     *
252     * @var \phpseclib\Math\BigInteger
253     * @access private
254     */
255    var $zero;
256
257    /**
258     * Precomputed One
259     *
260     * @var \phpseclib\Math\BigInteger
261     * @access private
262     */
263    var $one;
264
265    /**
266     * Private Key Format
267     *
268     * @var int
269     * @access private
270     */
271    var $privateKeyFormat = self::PRIVATE_FORMAT_PKCS1;
272
273    /**
274     * Public Key Format
275     *
276     * @var int
277     * @access public
278     */
279    var $publicKeyFormat = self::PUBLIC_FORMAT_PKCS8;
280
281    /**
282     * Modulus (ie. n)
283     *
284     * @var \phpseclib\Math\BigInteger
285     * @access private
286     */
287    var $modulus;
288
289    /**
290     * Modulus length
291     *
292     * @var \phpseclib\Math\BigInteger
293     * @access private
294     */
295    var $k;
296
297    /**
298     * Exponent (ie. e or d)
299     *
300     * @var \phpseclib\Math\BigInteger
301     * @access private
302     */
303    var $exponent;
304
305    /**
306     * Primes for Chinese Remainder Theorem (ie. p and q)
307     *
308     * @var array
309     * @access private
310     */
311    var $primes;
312
313    /**
314     * Exponents for Chinese Remainder Theorem (ie. dP and dQ)
315     *
316     * @var array
317     * @access private
318     */
319    var $exponents;
320
321    /**
322     * Coefficients for Chinese Remainder Theorem (ie. qInv)
323     *
324     * @var array
325     * @access private
326     */
327    var $coefficients;
328
329    /**
330     * Hash name
331     *
332     * @var string
333     * @access private
334     */
335    var $hashName;
336
337    /**
338     * Hash function
339     *
340     * @var \phpseclib\Crypt\Hash
341     * @access private
342     */
343    var $hash;
344
345    /**
346     * Length of hash function output
347     *
348     * @var int
349     * @access private
350     */
351    var $hLen;
352
353    /**
354     * Length of salt
355     *
356     * @var int
357     * @access private
358     */
359    var $sLen;
360
361    /**
362     * Hash function for the Mask Generation Function
363     *
364     * @var \phpseclib\Crypt\Hash
365     * @access private
366     */
367    var $mgfHash;
368
369    /**
370     * Length of MGF hash function output
371     *
372     * @var int
373     * @access private
374     */
375    var $mgfHLen;
376
377    /**
378     * Encryption mode
379     *
380     * @var int
381     * @access private
382     */
383    var $encryptionMode = self::ENCRYPTION_OAEP;
384
385    /**
386     * Signature mode
387     *
388     * @var int
389     * @access private
390     */
391    var $signatureMode = self::SIGNATURE_PSS;
392
393    /**
394     * Public Exponent
395     *
396     * @var mixed
397     * @access private
398     */
399    var $publicExponent = false;
400
401    /**
402     * Password
403     *
404     * @var string
405     * @access private
406     */
407    var $password = false;
408
409    /**
410     * Components
411     *
412     * For use with parsing XML formatted keys.  PHP's XML Parser functions use utilized - instead of PHP's DOM functions -
413     * because PHP's XML Parser functions work on PHP4 whereas PHP's DOM functions - although surperior - don't.
414     *
415     * @see self::_start_element_handler()
416     * @var array
417     * @access private
418     */
419    var $components = array();
420
421    /**
422     * Current String
423     *
424     * For use with parsing XML formatted keys.
425     *
426     * @see self::_character_handler()
427     * @see self::_stop_element_handler()
428     * @var mixed
429     * @access private
430     */
431    var $current;
432
433    /**
434     * OpenSSL configuration file name.
435     *
436     * Set to null to use system configuration file.
437     * @see self::createKey()
438     * @var mixed
439     * @Access public
440     */
441    var $configFile;
442
443    /**
444     * Public key comment field.
445     *
446     * @var string
447     * @access private
448     */
449    var $comment = 'phpseclib-generated-key';
450
451    /**
452     * The constructor
453     *
454     * If you want to make use of the openssl extension, you'll need to set the mode manually, yourself.  The reason
455     * \phpseclib\Crypt\RSA doesn't do it is because OpenSSL doesn't fail gracefully.  openssl_pkey_new(), in particular, requires
456     * openssl.cnf be present somewhere and, unfortunately, the only real way to find out is too late.
457     *
458     * @return \phpseclib\Crypt\RSA
459     * @access public
460     */
461    function __construct()
462    {
463        $this->configFile = dirname(__FILE__) . '/../openssl.cnf';
464
465        if (!defined('CRYPT_RSA_MODE')) {
466            switch (true) {
467                // Math/BigInteger's openssl requirements are a little less stringent than Crypt/RSA's. in particular,
468                // Math/BigInteger doesn't require an openssl.cfg file whereas Crypt/RSA does. so if Math/BigInteger
469                // can't use OpenSSL it can be pretty trivially assumed, then, that Crypt/RSA can't either.
470                case defined('MATH_BIGINTEGER_OPENSSL_DISABLE'):
471                    define('CRYPT_RSA_MODE', self::MODE_INTERNAL);
472                    break;
473                case extension_loaded('openssl') && file_exists($this->configFile):
474                    // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
475                    $versions = array();
476
477                    // avoid generating errors (even with suppression) when phpinfo() is disabled (common in production systems)
478                    if (strpos(ini_get('disable_functions'), 'phpinfo') === false) {
479                        ob_start();
480                        @phpinfo();
481                        $content = ob_get_contents();
482                        ob_end_clean();
483
484                        preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
485
486                        if (!empty($matches[1])) {
487                            for ($i = 0; $i < count($matches[1]); $i++) {
488                                $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
489
490                                // Remove letter part in OpenSSL version
491                                if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
492                                    $versions[$matches[1][$i]] = $fullVersion;
493                                } else {
494                                    $versions[$matches[1][$i]] = $m[0];
495                                }
496                            }
497                        }
498                    }
499
500                    // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
501                    switch (true) {
502                        case !isset($versions['Header']):
503                        case !isset($versions['Library']):
504                        case $versions['Header'] == $versions['Library']:
505                        case version_compare($versions['Header'], '1.0.0') >= 0 && version_compare($versions['Library'], '1.0.0') >= 0:
506                            define('CRYPT_RSA_MODE', self::MODE_OPENSSL);
507                            break;
508                        default:
509                            define('CRYPT_RSA_MODE', self::MODE_INTERNAL);
510                            define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
511                    }
512                    break;
513                default:
514                    define('CRYPT_RSA_MODE', self::MODE_INTERNAL);
515            }
516        }
517
518        $this->zero = new BigInteger();
519        $this->one = new BigInteger(1);
520
521        $this->hash = new Hash('sha1');
522        $this->hLen = $this->hash->getLength();
523        $this->hashName = 'sha1';
524        $this->mgfHash = new Hash('sha1');
525        $this->mgfHLen = $this->mgfHash->getLength();
526    }
527
528    /**
529     * Create public / private key pair
530     *
531     * Returns an array with the following three elements:
532     *  - 'privatekey': The private key.
533     *  - 'publickey':  The public key.
534     *  - 'partialkey': A partially computed key (if the execution time exceeded $timeout).
535     *                  Will need to be passed back to \phpseclib\Crypt\RSA::createKey() as the third parameter for further processing.
536     *
537     * @access public
538     * @param int $bits
539     * @param int $timeout
540     * @param array $partial
541     */
542    function createKey($bits = 1024, $timeout = false, $partial = array())
543    {
544        if (!defined('CRYPT_RSA_EXPONENT')) {
545            // http://en.wikipedia.org/wiki/65537_%28number%29
546            define('CRYPT_RSA_EXPONENT', '65537');
547        }
548        // per <http://cseweb.ucsd.edu/~hovav/dist/survey.pdf#page=5>, this number ought not result in primes smaller
549        // than 256 bits. as a consequence if the key you're trying to create is 1024 bits and you've set CRYPT_RSA_SMALLEST_PRIME
550        // to 384 bits then you're going to get a 384 bit prime and a 640 bit prime (384 + 1024 % 384). at least if
551        // CRYPT_RSA_MODE is set to self::MODE_INTERNAL. if CRYPT_RSA_MODE is set to self::MODE_OPENSSL then
552        // CRYPT_RSA_SMALLEST_PRIME is ignored (ie. multi-prime RSA support is more intended as a way to speed up RSA key
553        // generation when there's a chance neither gmp nor OpenSSL are installed)
554        if (!defined('CRYPT_RSA_SMALLEST_PRIME')) {
555            define('CRYPT_RSA_SMALLEST_PRIME', 4096);
556        }
557
558        // OpenSSL uses 65537 as the exponent and requires RSA keys be 384 bits minimum
559        if (CRYPT_RSA_MODE == self::MODE_OPENSSL && $bits >= 384 && CRYPT_RSA_EXPONENT == 65537) {
560            $config = array();
561            if (isset($this->configFile)) {
562                $config['config'] = $this->configFile;
563            }
564            $rsa = openssl_pkey_new(array('private_key_bits' => $bits) + $config);
565            openssl_pkey_export($rsa, $privatekey, null, $config);
566            $publickey = openssl_pkey_get_details($rsa);
567            $publickey = $publickey['key'];
568
569            $privatekey = call_user_func_array(array($this, '_convertPrivateKey'), array_values($this->_parseKey($privatekey, self::PRIVATE_FORMAT_PKCS1)));
570            $publickey = call_user_func_array(array($this, '_convertPublicKey'), array_values($this->_parseKey($publickey, self::PUBLIC_FORMAT_PKCS1)));
571
572            // clear the buffer of error strings stemming from a minimalistic openssl.cnf
573            while (openssl_error_string() !== false) {
574            }
575
576            return array(
577                'privatekey' => $privatekey,
578                'publickey' => $publickey,
579                'partialkey' => false
580            );
581        }
582
583        static $e;
584        if (!isset($e)) {
585            $e = new BigInteger(CRYPT_RSA_EXPONENT);
586        }
587
588        extract($this->_generateMinMax($bits));
589        $absoluteMin = $min;
590        $temp = $bits >> 1; // divide by two to see how many bits P and Q would be
591        if ($temp > CRYPT_RSA_SMALLEST_PRIME) {
592            $num_primes = floor($bits / CRYPT_RSA_SMALLEST_PRIME);
593            $temp = CRYPT_RSA_SMALLEST_PRIME;
594        } else {
595            $num_primes = 2;
596        }
597        extract($this->_generateMinMax($temp + $bits % $temp));
598        $finalMax = $max;
599        extract($this->_generateMinMax($temp));
600
601        $generator = new BigInteger();
602
603        $n = $this->one->copy();
604        if (!empty($partial)) {
605            extract(unserialize($partial));
606        } else {
607            $exponents = $coefficients = $primes = array();
608            $lcm = array(
609                'top' => $this->one->copy(),
610                'bottom' => false
611            );
612        }
613
614        $start = time();
615        $i0 = count($primes) + 1;
616
617        do {
618            for ($i = $i0; $i <= $num_primes; $i++) {
619                if ($timeout !== false) {
620                    $timeout-= time() - $start;
621                    $start = time();
622                    if ($timeout <= 0) {
623                        return array(
624                            'privatekey' => '',
625                            'publickey'  => '',
626                            'partialkey' => serialize(array(
627                                'primes' => $primes,
628                                'coefficients' => $coefficients,
629                                'lcm' => $lcm,
630                                'exponents' => $exponents
631                            ))
632                        );
633                    }
634                }
635
636                if ($i == $num_primes) {
637                    list($min, $temp) = $absoluteMin->divide($n);
638                    if (!$temp->equals($this->zero)) {
639                        $min = $min->add($this->one); // ie. ceil()
640                    }
641                    $primes[$i] = $generator->randomPrime($min, $finalMax, $timeout);
642                } else {
643                    $primes[$i] = $generator->randomPrime($min, $max, $timeout);
644                }
645
646                if ($primes[$i] === false) { // if we've reached the timeout
647                    if (count($primes) > 1) {
648                        $partialkey = '';
649                    } else {
650                        array_pop($primes);
651                        $partialkey = serialize(array(
652                            'primes' => $primes,
653                            'coefficients' => $coefficients,
654                            'lcm' => $lcm,
655                            'exponents' => $exponents
656                        ));
657                    }
658
659                    return array(
660                        'privatekey' => '',
661                        'publickey'  => '',
662                        'partialkey' => $partialkey
663                    );
664                }
665
666                // the first coefficient is calculated differently from the rest
667                // ie. instead of being $primes[1]->modInverse($primes[2]), it's $primes[2]->modInverse($primes[1])
668                if ($i > 2) {
669                    $coefficients[$i] = $n->modInverse($primes[$i]);
670                }
671
672                $n = $n->multiply($primes[$i]);
673
674                $temp = $primes[$i]->subtract($this->one);
675
676                // textbook RSA implementations use Euler's totient function instead of the least common multiple.
677                // see http://en.wikipedia.org/wiki/Euler%27s_totient_function
678                $lcm['top'] = $lcm['top']->multiply($temp);
679                $lcm['bottom'] = $lcm['bottom'] === false ? $temp : $lcm['bottom']->gcd($temp);
680
681                $exponents[$i] = $e->modInverse($temp);
682            }
683
684            list($temp) = $lcm['top']->divide($lcm['bottom']);
685            $gcd = $temp->gcd($e);
686            $i0 = 1;
687        } while (!$gcd->equals($this->one));
688
689        $d = $e->modInverse($temp);
690
691        $coefficients[2] = $primes[2]->modInverse($primes[1]);
692
693        // from <http://tools.ietf.org/html/rfc3447#appendix-A.1.2>:
694        // RSAPrivateKey ::= SEQUENCE {
695        //     version           Version,
696        //     modulus           INTEGER,  -- n
697        //     publicExponent    INTEGER,  -- e
698        //     privateExponent   INTEGER,  -- d
699        //     prime1            INTEGER,  -- p
700        //     prime2            INTEGER,  -- q
701        //     exponent1         INTEGER,  -- d mod (p-1)
702        //     exponent2         INTEGER,  -- d mod (q-1)
703        //     coefficient       INTEGER,  -- (inverse of q) mod p
704        //     otherPrimeInfos   OtherPrimeInfos OPTIONAL
705        // }
706
707        return array(
708            'privatekey' => $this->_convertPrivateKey($n, $e, $d, $primes, $exponents, $coefficients),
709            'publickey'  => $this->_convertPublicKey($n, $e),
710            'partialkey' => false
711        );
712    }
713
714    /**
715     * Convert a private key to the appropriate format.
716     *
717     * @access private
718     * @see self::setPrivateKeyFormat()
719     * @param Math_BigInteger $n
720     * @param Math_BigInteger $e
721     * @param Math_BigInteger $d
722     * @param array<int,Math_BigInteger> $primes
723     * @param array<int,Math_BigInteger> $exponents
724     * @param array<int,Math_BigInteger> $coefficients
725     * @return string
726     */
727    function _convertPrivateKey($n, $e, $d, $primes, $exponents, $coefficients)
728    {
729        $signed = $this->privateKeyFormat != self::PRIVATE_FORMAT_XML;
730        $num_primes = count($primes);
731        $raw = array(
732            'version' => $num_primes == 2 ? chr(0) : chr(1), // two-prime vs. multi
733            'modulus' => $n->toBytes($signed),
734            'publicExponent' => $e->toBytes($signed),
735            'privateExponent' => $d->toBytes($signed),
736            'prime1' => $primes[1]->toBytes($signed),
737            'prime2' => $primes[2]->toBytes($signed),
738            'exponent1' => $exponents[1]->toBytes($signed),
739            'exponent2' => $exponents[2]->toBytes($signed),
740            'coefficient' => $coefficients[2]->toBytes($signed)
741        );
742
743        // if the format in question does not support multi-prime rsa and multi-prime rsa was used,
744        // call _convertPublicKey() instead.
745        switch ($this->privateKeyFormat) {
746            case self::PRIVATE_FORMAT_XML:
747                if ($num_primes != 2) {
748                    return false;
749                }
750                return "<RSAKeyValue>\r\n" .
751                       '  <Modulus>' . base64_encode($raw['modulus']) . "</Modulus>\r\n" .
752                       '  <Exponent>' . base64_encode($raw['publicExponent']) . "</Exponent>\r\n" .
753                       '  <P>' . base64_encode($raw['prime1']) . "</P>\r\n" .
754                       '  <Q>' . base64_encode($raw['prime2']) . "</Q>\r\n" .
755                       '  <DP>' . base64_encode($raw['exponent1']) . "</DP>\r\n" .
756                       '  <DQ>' . base64_encode($raw['exponent2']) . "</DQ>\r\n" .
757                       '  <InverseQ>' . base64_encode($raw['coefficient']) . "</InverseQ>\r\n" .
758                       '  <D>' . base64_encode($raw['privateExponent']) . "</D>\r\n" .
759                       '</RSAKeyValue>';
760                break;
761            case self::PRIVATE_FORMAT_PUTTY:
762                if ($num_primes != 2) {
763                    return false;
764                }
765                $key = "PuTTY-User-Key-File-2: ssh-rsa\r\nEncryption: ";
766                $encryption = (!empty($this->password) || is_string($this->password)) ? 'aes256-cbc' : 'none';
767                $key.= $encryption;
768                $key.= "\r\nComment: " . $this->comment . "\r\n";
769                $public = pack(
770                    'Na*Na*Na*',
771                    strlen('ssh-rsa'),
772                    'ssh-rsa',
773                    strlen($raw['publicExponent']),
774                    $raw['publicExponent'],
775                    strlen($raw['modulus']),
776                    $raw['modulus']
777                );
778                $source = pack(
779                    'Na*Na*Na*Na*',
780                    strlen('ssh-rsa'),
781                    'ssh-rsa',
782                    strlen($encryption),
783                    $encryption,
784                    strlen($this->comment),
785                    $this->comment,
786                    strlen($public),
787                    $public
788                );
789                $public = base64_encode($public);
790                $key.= "Public-Lines: " . ((strlen($public) + 63) >> 6) . "\r\n";
791                $key.= chunk_split($public, 64);
792                $private = pack(
793                    'Na*Na*Na*Na*',
794                    strlen($raw['privateExponent']),
795                    $raw['privateExponent'],
796                    strlen($raw['prime1']),
797                    $raw['prime1'],
798                    strlen($raw['prime2']),
799                    $raw['prime2'],
800                    strlen($raw['coefficient']),
801                    $raw['coefficient']
802                );
803                if (empty($this->password) && !is_string($this->password)) {
804                    $source.= pack('Na*', strlen($private), $private);
805                    $hashkey = 'putty-private-key-file-mac-key';
806                } else {
807                    $private.= Random::string(16 - (strlen($private) & 15));
808                    $source.= pack('Na*', strlen($private), $private);
809                    $sequence = 0;
810                    $symkey = '';
811                    while (strlen($symkey) < 32) {
812                        $temp = pack('Na*', $sequence++, $this->password);
813                        $symkey.= pack('H*', sha1($temp));
814                    }
815                    $symkey = substr($symkey, 0, 32);
816                    $crypto = new AES();
817
818                    $crypto->setKey($symkey);
819                    $crypto->disablePadding();
820                    $private = $crypto->encrypt($private);
821                    $hashkey = 'putty-private-key-file-mac-key' . $this->password;
822                }
823
824                $private = base64_encode($private);
825                $key.= 'Private-Lines: ' . ((strlen($private) + 63) >> 6) . "\r\n";
826                $key.= chunk_split($private, 64);
827                $hash = new Hash('sha1');
828                $hash->setKey(pack('H*', sha1($hashkey)));
829                $key.= 'Private-MAC: ' . bin2hex($hash->hash($source)) . "\r\n";
830
831                return $key;
832            case self::PRIVATE_FORMAT_OPENSSH:
833                if ($num_primes != 2) {
834                    return false;
835                }
836                $publicKey = pack('Na*Na*Na*', strlen('ssh-rsa'), 'ssh-rsa', strlen($raw['publicExponent']), $raw['publicExponent'], strlen($raw['modulus']), $raw['modulus']);
837                $privateKey = pack(
838                    'Na*Na*Na*Na*Na*Na*Na*',
839                    strlen('ssh-rsa'),
840                    'ssh-rsa',
841                    strlen($raw['modulus']),
842                    $raw['modulus'],
843                    strlen($raw['publicExponent']),
844                    $raw['publicExponent'],
845                    strlen($raw['privateExponent']),
846                    $raw['privateExponent'],
847                    strlen($raw['coefficient']),
848                    $raw['coefficient'],
849                    strlen($raw['prime1']),
850                    $raw['prime1'],
851                    strlen($raw['prime2']),
852                    $raw['prime2']
853                );
854                $checkint = Random::string(4);
855                $paddedKey = pack(
856                    'a*Na*',
857                    $checkint . $checkint . $privateKey,
858                    strlen($this->comment),
859                    $this->comment
860                );
861                $paddingLength = (7 * strlen($paddedKey)) % 8;
862                for ($i = 1; $i <= $paddingLength; $i++) {
863                    $paddedKey.= chr($i);
864                }
865                $key = pack(
866                    'Na*Na*Na*NNa*Na*',
867                    strlen('none'),
868                    'none',
869                    strlen('none'),
870                    'none',
871                    0,
872                    '',
873                    1,
874                    strlen($publicKey),
875                    $publicKey,
876                    strlen($paddedKey),
877                    $paddedKey
878                );
879                $key = "openssh-key-v1\0$key";
880
881                return "-----BEGIN OPENSSH PRIVATE KEY-----\r\n" .
882                       chunk_split(base64_encode($key), 70) .
883                       "-----END OPENSSH PRIVATE KEY-----";
884            default: // eg. self::PRIVATE_FORMAT_PKCS1
885                $components = array();
886                foreach ($raw as $name => $value) {
887                    $components[$name] = pack('Ca*a*', self::ASN1_INTEGER, $this->_encodeLength(strlen($value)), $value);
888                }
889
890                $RSAPrivateKey = implode('', $components);
891
892                if ($num_primes > 2) {
893                    $OtherPrimeInfos = '';
894                    for ($i = 3; $i <= $num_primes; $i++) {
895                        // OtherPrimeInfos ::= SEQUENCE SIZE(1..MAX) OF OtherPrimeInfo
896                        //
897                        // OtherPrimeInfo ::= SEQUENCE {
898                        //     prime             INTEGER,  -- ri
899                        //     exponent          INTEGER,  -- di
900                        //     coefficient       INTEGER   -- ti
901                        // }
902                        $OtherPrimeInfo = pack('Ca*a*', self::ASN1_INTEGER, $this->_encodeLength(strlen($primes[$i]->toBytes(true))), $primes[$i]->toBytes(true));
903                        $OtherPrimeInfo.= pack('Ca*a*', self::ASN1_INTEGER, $this->_encodeLength(strlen($exponents[$i]->toBytes(true))), $exponents[$i]->toBytes(true));
904                        $OtherPrimeInfo.= pack('Ca*a*', self::ASN1_INTEGER, $this->_encodeLength(strlen($coefficients[$i]->toBytes(true))), $coefficients[$i]->toBytes(true));
905                        $OtherPrimeInfos.= pack('Ca*a*', self::ASN1_SEQUENCE, $this->_encodeLength(strlen($OtherPrimeInfo)), $OtherPrimeInfo);
906                    }
907                    $RSAPrivateKey.= pack('Ca*a*', self::ASN1_SEQUENCE, $this->_encodeLength(strlen($OtherPrimeInfos)), $OtherPrimeInfos);
908                }
909
910                $RSAPrivateKey = pack('Ca*a*', self::ASN1_SEQUENCE, $this->_encodeLength(strlen($RSAPrivateKey)), $RSAPrivateKey);
911
912                if ($this->privateKeyFormat == self::PRIVATE_FORMAT_PKCS8) {
913                    $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
914                    $RSAPrivateKey = pack(
915                        'Ca*a*Ca*a*',
916                        self::ASN1_INTEGER,
917                        "\01\00",
918                        $rsaOID,
919                        4,
920                        $this->_encodeLength(strlen($RSAPrivateKey)),
921                        $RSAPrivateKey
922                    );
923                    $RSAPrivateKey = pack('Ca*a*', self::ASN1_SEQUENCE, $this->_encodeLength(strlen($RSAPrivateKey)), $RSAPrivateKey);
924                    if (!empty($this->password) || is_string($this->password)) {
925                        $salt = Random::string(8);
926                        $iterationCount = 2048;
927
928                        $crypto = new DES();
929                        $crypto->setPassword($this->password, 'pbkdf1', 'md5', $salt, $iterationCount);
930                        $RSAPrivateKey = $crypto->encrypt($RSAPrivateKey);
931
932                        $parameters = pack(
933                            'Ca*a*Ca*N',
934                            self::ASN1_OCTETSTRING,
935                            $this->_encodeLength(strlen($salt)),
936                            $salt,
937                            self::ASN1_INTEGER,
938                            $this->_encodeLength(4),
939                            $iterationCount
940                        );
941                        $pbeWithMD5AndDES_CBC = "\x2a\x86\x48\x86\xf7\x0d\x01\x05\x03";
942
943                        $encryptionAlgorithm = pack(
944                            'Ca*a*Ca*a*',
945                            self::ASN1_OBJECT,
946                            $this->_encodeLength(strlen($pbeWithMD5AndDES_CBC)),
947                            $pbeWithMD5AndDES_CBC,
948                            self::ASN1_SEQUENCE,
949                            $this->_encodeLength(strlen($parameters)),
950                            $parameters
951                        );
952
953                        $RSAPrivateKey = pack(
954                            'Ca*a*Ca*a*',
955                            self::ASN1_SEQUENCE,
956                            $this->_encodeLength(strlen($encryptionAlgorithm)),
957                            $encryptionAlgorithm,
958                            self::ASN1_OCTETSTRING,
959                            $this->_encodeLength(strlen($RSAPrivateKey)),
960                            $RSAPrivateKey
961                        );
962
963                        $RSAPrivateKey = pack('Ca*a*', self::ASN1_SEQUENCE, $this->_encodeLength(strlen($RSAPrivateKey)), $RSAPrivateKey);
964
965                        $RSAPrivateKey = "-----BEGIN ENCRYPTED PRIVATE KEY-----\r\n" .
966                                         chunk_split(base64_encode($RSAPrivateKey), 64) .
967                                         '-----END ENCRYPTED PRIVATE KEY-----';
968                    } else {
969                        $RSAPrivateKey = "-----BEGIN PRIVATE KEY-----\r\n" .
970                                         chunk_split(base64_encode($RSAPrivateKey), 64) .
971                                         '-----END PRIVATE KEY-----';
972                    }
973                    return $RSAPrivateKey;
974                }
975
976                if (!empty($this->password) || is_string($this->password)) {
977                    $iv = Random::string(8);
978                    $symkey = pack('H*', md5($this->password . $iv)); // symkey is short for symmetric key
979                    $symkey.= substr(pack('H*', md5($symkey . $this->password . $iv)), 0, 8);
980                    $des = new TripleDES();
981                    $des->setKey($symkey);
982                    $des->setIV($iv);
983                    $iv = strtoupper(bin2hex($iv));
984                    $RSAPrivateKey = "-----BEGIN RSA PRIVATE KEY-----\r\n" .
985                                     "Proc-Type: 4,ENCRYPTED\r\n" .
986                                     "DEK-Info: DES-EDE3-CBC,$iv\r\n" .
987                                     "\r\n" .
988                                     chunk_split(base64_encode($des->encrypt($RSAPrivateKey)), 64) .
989                                     '-----END RSA PRIVATE KEY-----';
990                } else {
991                    $RSAPrivateKey = "-----BEGIN RSA PRIVATE KEY-----\r\n" .
992                                     chunk_split(base64_encode($RSAPrivateKey), 64) .
993                                     '-----END RSA PRIVATE KEY-----';
994                }
995
996                return $RSAPrivateKey;
997        }
998    }
999
1000    /**
1001     * Convert a public key to the appropriate format
1002     *
1003     * @access private
1004     * @see self::setPublicKeyFormat()
1005     * @param Math_BigInteger $n
1006     * @param Math_BigInteger $e
1007     * @return string|array<string,Math_BigInteger>
1008     */
1009    function _convertPublicKey($n, $e)
1010    {
1011        $signed = $this->publicKeyFormat != self::PUBLIC_FORMAT_XML;
1012
1013        $modulus = $n->toBytes($signed);
1014        $publicExponent = $e->toBytes($signed);
1015
1016        switch ($this->publicKeyFormat) {
1017            case self::PUBLIC_FORMAT_RAW:
1018                return array('e' => $e->copy(), 'n' => $n->copy());
1019            case self::PUBLIC_FORMAT_XML:
1020                return "<RSAKeyValue>\r\n" .
1021                       '  <Modulus>' . base64_encode($modulus) . "</Modulus>\r\n" .
1022                       '  <Exponent>' . base64_encode($publicExponent) . "</Exponent>\r\n" .
1023                       '</RSAKeyValue>';
1024                break;
1025            case self::PUBLIC_FORMAT_OPENSSH:
1026                // from <http://tools.ietf.org/html/rfc4253#page-15>:
1027                // string    "ssh-rsa"
1028                // mpint     e
1029                // mpint     n
1030                $RSAPublicKey = pack('Na*Na*Na*', strlen('ssh-rsa'), 'ssh-rsa', strlen($publicExponent), $publicExponent, strlen($modulus), $modulus);
1031                $RSAPublicKey = 'ssh-rsa ' . base64_encode($RSAPublicKey) . ' ' . $this->comment;
1032
1033                return $RSAPublicKey;
1034            default: // eg. self::PUBLIC_FORMAT_PKCS1_RAW or self::PUBLIC_FORMAT_PKCS1
1035                // from <http://tools.ietf.org/html/rfc3447#appendix-A.1.1>:
1036                // RSAPublicKey ::= SEQUENCE {
1037                //     modulus           INTEGER,  -- n
1038                //     publicExponent    INTEGER   -- e
1039                // }
1040                $components = array(
1041                    'modulus' => pack('Ca*a*', self::ASN1_INTEGER, $this->_encodeLength(strlen($modulus)), $modulus),
1042                    'publicExponent' => pack('Ca*a*', self::ASN1_INTEGER, $this->_encodeLength(strlen($publicExponent)), $publicExponent)
1043                );
1044
1045                $RSAPublicKey = pack(
1046                    'Ca*a*a*',
1047                    self::ASN1_SEQUENCE,
1048                    $this->_encodeLength(strlen($components['modulus']) + strlen($components['publicExponent'])),
1049                    $components['modulus'],
1050                    $components['publicExponent']
1051                );
1052
1053                if ($this->publicKeyFormat == self::PUBLIC_FORMAT_PKCS1_RAW) {
1054                    $RSAPublicKey = "-----BEGIN RSA PUBLIC KEY-----\r\n" .
1055                                    chunk_split(base64_encode($RSAPublicKey), 64) .
1056                                    '-----END RSA PUBLIC KEY-----';
1057                } else {
1058                    // sequence(oid(1.2.840.113549.1.1.1), null)) = rsaEncryption.
1059                    $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
1060                    $RSAPublicKey = chr(0) . $RSAPublicKey;
1061                    $RSAPublicKey = chr(3) . $this->_encodeLength(strlen($RSAPublicKey)) . $RSAPublicKey;
1062
1063                    $RSAPublicKey = pack(
1064                        'Ca*a*',
1065                        self::ASN1_SEQUENCE,
1066                        $this->_encodeLength(strlen($rsaOID . $RSAPublicKey)),
1067                        $rsaOID . $RSAPublicKey
1068                    );
1069
1070                    $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
1071                                     chunk_split(base64_encode($RSAPublicKey), 64) .
1072                                     '-----END PUBLIC KEY-----';
1073                }
1074
1075                return $RSAPublicKey;
1076        }
1077    }
1078
1079    /**
1080     * Break a public or private key down into its constituant components
1081     *
1082     * @access private
1083     * @see self::_convertPublicKey()
1084     * @see self::_convertPrivateKey()
1085     * @param string|array $key
1086     * @param int $type
1087     * @return array|bool
1088     */
1089    function _parseKey($key, $type)
1090    {
1091        if ($type != self::PUBLIC_FORMAT_RAW && !is_string($key)) {
1092            return false;
1093        }
1094
1095        switch ($type) {
1096            case self::PUBLIC_FORMAT_RAW:
1097                if (!is_array($key)) {
1098                    return false;
1099                }
1100                $components = array();
1101                switch (true) {
1102                    case isset($key['e']):
1103                        $components['publicExponent'] = $key['e']->copy();
1104                        break;
1105                    case isset($key['exponent']):
1106                        $components['publicExponent'] = $key['exponent']->copy();
1107                        break;
1108                    case isset($key['publicExponent']):
1109                        $components['publicExponent'] = $key['publicExponent']->copy();
1110                        break;
1111                    case isset($key[0]):
1112                        $components['publicExponent'] = $key[0]->copy();
1113                }
1114                switch (true) {
1115                    case isset($key['n']):
1116                        $components['modulus'] = $key['n']->copy();
1117                        break;
1118                    case isset($key['modulo']):
1119                        $components['modulus'] = $key['modulo']->copy();
1120                        break;
1121                    case isset($key['modulus']):
1122                        $components['modulus'] = $key['modulus']->copy();
1123                        break;
1124                    case isset($key[1]):
1125                        $components['modulus'] = $key[1]->copy();
1126                }
1127                return isset($components['modulus']) && isset($components['publicExponent']) ? $components : false;
1128            case self::PRIVATE_FORMAT_PKCS1:
1129            case self::PRIVATE_FORMAT_PKCS8:
1130            case self::PUBLIC_FORMAT_PKCS1:
1131                /* Although PKCS#1 proposes a format that public and private keys can use, encrypting them is
1132                   "outside the scope" of PKCS#1.  PKCS#1 then refers you to PKCS#12 and PKCS#15 if you're wanting to
1133                   protect private keys, however, that's not what OpenSSL* does.  OpenSSL protects private keys by adding
1134                   two new "fields" to the key - DEK-Info and Proc-Type.  These fields are discussed here:
1135
1136                   http://tools.ietf.org/html/rfc1421#section-4.6.1.1
1137                   http://tools.ietf.org/html/rfc1421#section-4.6.1.3
1138
1139                   DES-EDE3-CBC as an algorithm, however, is not discussed anywhere, near as I can tell.
1140                   DES-CBC and DES-EDE are discussed in RFC1423, however, DES-EDE3-CBC isn't, nor is its key derivation
1141                   function.  As is, the definitive authority on this encoding scheme isn't the IETF but rather OpenSSL's
1142                   own implementation.  ie. the implementation *is* the standard and any bugs that may exist in that
1143                   implementation are part of the standard, as well.
1144
1145                   * OpenSSL is the de facto standard.  It's utilized by OpenSSH and other projects */
1146                if (preg_match('#DEK-Info: (.+),(.+)#', $key, $matches)) {
1147                    $iv = pack('H*', trim($matches[2]));
1148                    $symkey = pack('H*', md5($this->password . substr($iv, 0, 8))); // symkey is short for symmetric key
1149                    $symkey.= pack('H*', md5($symkey . $this->password . substr($iv, 0, 8)));
1150                    // remove the Proc-Type / DEK-Info sections as they're no longer needed
1151                    $key = preg_replace('#^(?:Proc-Type|DEK-Info): .*#m', '', $key);
1152                    $ciphertext = $this->_extractBER($key);
1153                    if ($ciphertext === false) {
1154                        $ciphertext = $key;
1155                    }
1156                    switch ($matches[1]) {
1157                        case 'AES-256-CBC':
1158                            $crypto = new AES();
1159                            break;
1160                        case 'AES-128-CBC':
1161                            $symkey = substr($symkey, 0, 16);
1162                            $crypto = new AES();
1163                            break;
1164                        case 'DES-EDE3-CFB':
1165                            $crypto = new TripleDES(Base::MODE_CFB);
1166                            break;
1167                        case 'DES-EDE3-CBC':
1168                            $symkey = substr($symkey, 0, 24);
1169                            $crypto = new TripleDES();
1170                            break;
1171                        case 'DES-CBC':
1172                            $crypto = new DES();
1173                            break;
1174                        default:
1175                            return false;
1176                    }
1177                    $crypto->setKey($symkey);
1178                    $crypto->setIV($iv);
1179                    $decoded = $crypto->decrypt($ciphertext);
1180                } else {
1181                    $decoded = $this->_extractBER($key);
1182                }
1183
1184                if ($decoded !== false) {
1185                    $key = $decoded;
1186                }
1187
1188                $components = array();
1189
1190                if (ord($this->_string_shift($key)) != self::ASN1_SEQUENCE) {
1191                    return false;
1192                }
1193                if ($this->_decodeLength($key) != strlen($key)) {
1194                    return false;
1195                }
1196
1197                $tag = ord($this->_string_shift($key));
1198                /* intended for keys for which OpenSSL's asn1parse returns the following:
1199
1200                    0:d=0  hl=4 l= 631 cons: SEQUENCE
1201                    4:d=1  hl=2 l=   1 prim:  INTEGER           :00
1202                    7:d=1  hl=2 l=  13 cons:  SEQUENCE
1203                    9:d=2  hl=2 l=   9 prim:   OBJECT            :rsaEncryption
1204                   20:d=2  hl=2 l=   0 prim:   NULL
1205                   22:d=1  hl=4 l= 609 prim:  OCTET STRING
1206
1207                   ie. PKCS8 keys*/
1208
1209                if ($tag == self::ASN1_INTEGER && substr($key, 0, 3) == "\x01\x00\x30") {
1210                    $this->_string_shift($key, 3);
1211                    $tag = self::ASN1_SEQUENCE;
1212                }
1213
1214                if ($tag == self::ASN1_SEQUENCE) {
1215                    $temp = $this->_string_shift($key, $this->_decodeLength($key));
1216                    if (ord($this->_string_shift($temp)) != self::ASN1_OBJECT) {
1217                        return false;
1218                    }
1219                    $length = $this->_decodeLength($temp);
1220                    switch ($this->_string_shift($temp, $length)) {
1221                        case "\x2a\x86\x48\x86\xf7\x0d\x01\x01\x01": // rsaEncryption
1222                        case "\x2A\x86\x48\x86\xF7\x0D\x01\x01\x0A": // rsaPSS
1223                            break;
1224                        case "\x2a\x86\x48\x86\xf7\x0d\x01\x05\x03": // pbeWithMD5AndDES-CBC
1225                            /*
1226                               PBEParameter ::= SEQUENCE {
1227                                   salt OCTET STRING (SIZE(8)),
1228                                   iterationCount INTEGER }
1229                            */
1230                            if (ord($this->_string_shift($temp)) != self::ASN1_SEQUENCE) {
1231                                return false;
1232                            }
1233                            if ($this->_decodeLength($temp) != strlen($temp)) {
1234                                return false;
1235                            }
1236                            $this->_string_shift($temp); // assume it's an octet string
1237                            $salt = $this->_string_shift($temp, $this->_decodeLength($temp));
1238                            if (ord($this->_string_shift($temp)) != self::ASN1_INTEGER) {
1239                                return false;
1240                            }
1241                            $this->_decodeLength($temp);
1242                            list(, $iterationCount) = unpack('N', str_pad($temp, 4, chr(0), STR_PAD_LEFT));
1243                            $this->_string_shift($key); // assume it's an octet string
1244                            $length = $this->_decodeLength($key);
1245                            if (strlen($key) != $length) {
1246                                return false;
1247                            }
1248
1249                            $crypto = new DES();
1250                            $crypto->setPassword($this->password, 'pbkdf1', 'md5', $salt, $iterationCount);
1251                            $key = $crypto->decrypt($key);
1252                            if ($key === false) {
1253                                return false;
1254                            }
1255                            return $this->_parseKey($key, self::PRIVATE_FORMAT_PKCS1);
1256                        default:
1257                            return false;
1258                    }
1259                    /* intended for keys for which OpenSSL's asn1parse returns the following:
1260
1261                        0:d=0  hl=4 l= 290 cons: SEQUENCE
1262                        4:d=1  hl=2 l=  13 cons:  SEQUENCE
1263                        6:d=2  hl=2 l=   9 prim:   OBJECT            :rsaEncryption
1264                       17:d=2  hl=2 l=   0 prim:   NULL
1265                       19:d=1  hl=4 l= 271 prim:  BIT STRING */
1266                    $tag = ord($this->_string_shift($key)); // skip over the BIT STRING / OCTET STRING tag
1267                    $this->_decodeLength($key); // skip over the BIT STRING / OCTET STRING length
1268                    // "The initial octet shall encode, as an unsigned binary integer wtih bit 1 as the least significant bit, the number of
1269                    //  unused bits in the final subsequent octet. The number shall be in the range zero to seven."
1270                    //  -- http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf (section 8.6.2.2)
1271                    if ($tag == self::ASN1_BITSTRING) {
1272                        $this->_string_shift($key);
1273                    }
1274                    if (ord($this->_string_shift($key)) != self::ASN1_SEQUENCE) {
1275                        return false;
1276                    }
1277                    if ($this->_decodeLength($key) != strlen($key)) {
1278                        return false;
1279                    }
1280                    $tag = ord($this->_string_shift($key));
1281                }
1282                if ($tag != self::ASN1_INTEGER) {
1283                    return false;
1284                }
1285
1286                $length = $this->_decodeLength($key);
1287                $temp = $this->_string_shift($key, $length);
1288                if (strlen($temp) != 1 || ord($temp) > 2) {
1289                    $components['modulus'] = new BigInteger($temp, 256);
1290                    $this->_string_shift($key); // skip over self::ASN1_INTEGER
1291                    $length = $this->_decodeLength($key);
1292                    $components[$type == self::PUBLIC_FORMAT_PKCS1 ? 'publicExponent' : 'privateExponent'] = new BigInteger($this->_string_shift($key, $length), 256);
1293
1294                    return $components;
1295                }
1296                if (ord($this->_string_shift($key)) != self::ASN1_INTEGER) {
1297                    return false;
1298                }
1299                $length = $this->_decodeLength($key);
1300                $components['modulus'] = new BigInteger($this->_string_shift($key, $length), 256);
1301                $this->_string_shift($key);
1302                $length = $this->_decodeLength($key);
1303                $components['publicExponent'] = new BigInteger($this->_string_shift($key, $length), 256);
1304                $this->_string_shift($key);
1305                $length = $this->_decodeLength($key);
1306                $components['privateExponent'] = new BigInteger($this->_string_shift($key, $length), 256);
1307                $this->_string_shift($key);
1308                $length = $this->_decodeLength($key);
1309                $components['primes'] = array(1 => new BigInteger($this->_string_shift($key, $length), 256));
1310                $this->_string_shift($key);
1311                $length = $this->_decodeLength($key);
1312                $components['primes'][] = new BigInteger($this->_string_shift($key, $length), 256);
1313                $this->_string_shift($key);
1314                $length = $this->_decodeLength($key);
1315                $components['exponents'] = array(1 => new BigInteger($this->_string_shift($key, $length), 256));
1316                $this->_string_shift($key);
1317                $length = $this->_decodeLength($key);
1318                $components['exponents'][] = new BigInteger($this->_string_shift($key, $length), 256);
1319                $this->_string_shift($key);
1320                $length = $this->_decodeLength($key);
1321                $components['coefficients'] = array(2 => new BigInteger($this->_string_shift($key, $length), 256));
1322
1323                if (!empty($key)) {
1324                    if (ord($this->_string_shift($key)) != self::ASN1_SEQUENCE) {
1325                        return false;
1326                    }
1327                    $this->_decodeLength($key);
1328                    while (!empty($key)) {
1329                        if (ord($this->_string_shift($key)) != self::ASN1_SEQUENCE) {
1330                            return false;
1331                        }
1332                        $this->_decodeLength($key);
1333                        $key = substr($key, 1);
1334                        $length = $this->_decodeLength($key);
1335                        $components['primes'][] = new BigInteger($this->_string_shift($key, $length), 256);
1336                        $this->_string_shift($key);
1337                        $length = $this->_decodeLength($key);
1338                        $components['exponents'][] = new BigInteger($this->_string_shift($key, $length), 256);
1339                        $this->_string_shift($key);
1340                        $length = $this->_decodeLength($key);
1341                        $components['coefficients'][] = new BigInteger($this->_string_shift($key, $length), 256);
1342                    }
1343                }
1344
1345                return $components;
1346            case self::PUBLIC_FORMAT_OPENSSH:
1347                $parts = explode(' ', $key, 3);
1348
1349                $key = isset($parts[1]) ? base64_decode($parts[1]) : false;
1350                if ($key === false) {
1351                    return false;
1352                }
1353
1354                $comment = isset($parts[2]) ? $parts[2] : false;
1355
1356                $cleanup = substr($key, 0, 11) == "\0\0\0\7ssh-rsa";
1357
1358                if (strlen($key) <= 4) {
1359                    return false;
1360                }
1361                extract(unpack('Nlength', $this->_string_shift($key, 4)));
1362                $publicExponent = new BigInteger($this->_string_shift($key, $length), -256);
1363                if (strlen($key) <= 4) {
1364                    return false;
1365                }
1366                extract(unpack('Nlength', $this->_string_shift($key, 4)));
1367                $modulus = new BigInteger($this->_string_shift($key, $length), -256);
1368
1369                if ($cleanup && strlen($key)) {
1370                    if (strlen($key) <= 4) {
1371                        return false;
1372                    }
1373                    extract(unpack('Nlength', $this->_string_shift($key, 4)));
1374                    $realModulus = new BigInteger($this->_string_shift($key, $length), -256);
1375                    return strlen($key) ? false : array(
1376                        'modulus' => $realModulus,
1377                        'publicExponent' => $modulus,
1378                        'comment' => $comment
1379                    );
1380                } else {
1381                    return strlen($key) ? false : array(
1382                        'modulus' => $modulus,
1383                        'publicExponent' => $publicExponent,
1384                        'comment' => $comment
1385                    );
1386                }
1387            // http://www.w3.org/TR/xmldsig-core/#sec-RSAKeyValue
1388            // http://en.wikipedia.org/wiki/XML_Signature
1389            case self::PRIVATE_FORMAT_XML:
1390            case self::PUBLIC_FORMAT_XML:
1391                $this->components = array();
1392
1393                $xml = xml_parser_create('UTF-8');
1394                xml_set_object($xml, $this);
1395                xml_set_element_handler($xml, '_start_element_handler', '_stop_element_handler');
1396                xml_set_character_data_handler($xml, '_data_handler');
1397                // add <xml></xml> to account for "dangling" tags like <BitStrength>...</BitStrength> that are sometimes added
1398                if (!xml_parse($xml, '<xml>' . $key . '</xml>')) {
1399                    xml_parser_free($xml);
1400                    unset($xml);
1401                    return false;
1402                }
1403
1404                xml_parser_free($xml);
1405                unset($xml);
1406
1407                return isset($this->components['modulus']) && isset($this->components['publicExponent']) ? $this->components : false;
1408            // from PuTTY's SSHPUBK.C
1409            case self::PRIVATE_FORMAT_PUTTY:
1410                $components = array();
1411                $key = preg_split('#\r\n|\r|\n#', $key);
1412                $type = trim(preg_replace('#PuTTY-User-Key-File-2: (.+)#', '$1', $key[0]));
1413                if ($type != 'ssh-rsa') {
1414                    return false;
1415                }
1416                $encryption = trim(preg_replace('#Encryption: (.+)#', '$1', $key[1]));
1417                $comment = trim(preg_replace('#Comment: (.+)#', '$1', $key[2]));
1418
1419                $publicLength = trim(preg_replace('#Public-Lines: (\d+)#', '$1', $key[3]));
1420                $public = base64_decode(implode('', array_map('trim', array_slice($key, 4, $publicLength))));
1421                $public = substr($public, 11);
1422                extract(unpack('Nlength', $this->_string_shift($public, 4)));
1423                $components['publicExponent'] = new BigInteger($this->_string_shift($public, $length), -256);
1424                extract(unpack('Nlength', $this->_string_shift($public, 4)));
1425                $components['modulus'] = new BigInteger($this->_string_shift($public, $length), -256);
1426
1427                $privateLength = trim(preg_replace('#Private-Lines: (\d+)#', '$1', $key[$publicLength + 4]));
1428                $private = base64_decode(implode('', array_map('trim', array_slice($key, $publicLength + 5, $privateLength))));
1429
1430                switch ($encryption) {
1431                    case 'aes256-cbc':
1432                        $symkey = '';
1433                        $sequence = 0;
1434                        while (strlen($symkey) < 32) {
1435                            $temp = pack('Na*', $sequence++, $this->password);
1436                            $symkey.= pack('H*', sha1($temp));
1437                        }
1438                        $symkey = substr($symkey, 0, 32);
1439                        $crypto = new AES();
1440                }
1441
1442                if ($encryption != 'none') {
1443                    $crypto->setKey($symkey);
1444                    $crypto->disablePadding();
1445                    $private = $crypto->decrypt($private);
1446                    if ($private === false) {
1447                        return false;
1448                    }
1449                }
1450
1451                extract(unpack('Nlength', $this->_string_shift($private, 4)));
1452                if (strlen($private) < $length) {
1453                    return false;
1454                }
1455                $components['privateExponent'] = new BigInteger($this->_string_shift($private, $length), -256);
1456                extract(unpack('Nlength', $this->_string_shift($private, 4)));
1457                if (strlen($private) < $length) {
1458                    return false;
1459                }
1460                $components['primes'] = array(1 => new BigInteger($this->_string_shift($private, $length), -256));
1461                extract(unpack('Nlength', $this->_string_shift($private, 4)));
1462                if (strlen($private) < $length) {
1463                    return false;
1464                }
1465                $components['primes'][] = new BigInteger($this->_string_shift($private, $length), -256);
1466
1467                $temp = $components['primes'][1]->subtract($this->one);
1468                $components['exponents'] = array(1 => $components['publicExponent']->modInverse($temp));
1469                $temp = $components['primes'][2]->subtract($this->one);
1470                $components['exponents'][] = $components['publicExponent']->modInverse($temp);
1471
1472                extract(unpack('Nlength', $this->_string_shift($private, 4)));
1473                if (strlen($private) < $length) {
1474                    return false;
1475                }
1476                $components['coefficients'] = array(2 => new BigInteger($this->_string_shift($private, $length), -256));
1477
1478                return $components;
1479            case self::PRIVATE_FORMAT_OPENSSH:
1480                $components = array();
1481                $decoded = $this->_extractBER($key);
1482                $magic = $this->_string_shift($decoded, 15);
1483                if ($magic !== "openssh-key-v1\0") {
1484                    return false;
1485                }
1486                $options = $this->_string_shift($decoded, 24);
1487                // \0\0\0\4none = ciphername
1488                // \0\0\0\4none = kdfname
1489                // \0\0\0\0 = kdfoptions
1490                // \0\0\0\1 = numkeys
1491                if ($options != "\0\0\0\4none\0\0\0\4none\0\0\0\0\0\0\0\1") {
1492                    return false;
1493                }
1494                extract(unpack('Nlength', $this->_string_shift($decoded, 4)));
1495                if (strlen($decoded) < $length) {
1496                    return false;
1497                }
1498                $publicKey = $this->_string_shift($decoded, $length);
1499                extract(unpack('Nlength', $this->_string_shift($decoded, 4)));
1500                if (strlen($decoded) < $length) {
1501                    return false;
1502                }
1503                $paddedKey = $this->_string_shift($decoded, $length);
1504
1505                if ($this->_string_shift($publicKey, 11) !== "\0\0\0\7ssh-rsa") {
1506                    return false;
1507                }
1508
1509                $checkint1 = $this->_string_shift($paddedKey, 4);
1510                $checkint2 = $this->_string_shift($paddedKey, 4);
1511                if (strlen($checkint1) != 4 || $checkint1 !== $checkint2) {
1512                    return false;
1513                }
1514
1515                if ($this->_string_shift($paddedKey, 11) !== "\0\0\0\7ssh-rsa") {
1516                    return false;
1517                }
1518
1519                $values = array(
1520                    &$components['modulus'],
1521                    &$components['publicExponent'],
1522                    &$components['privateExponent'],
1523                    &$components['coefficients'][2],
1524                    &$components['primes'][1],
1525                    &$components['primes'][2]
1526                );
1527
1528                foreach ($values as &$value) {
1529                    extract(unpack('Nlength', $this->_string_shift($paddedKey, 4)));
1530                    if (strlen($paddedKey) < $length) {
1531                        return false;
1532                    }
1533                    $value = new BigInteger($this->_string_shift($paddedKey, $length), -256);
1534                }
1535
1536                extract(unpack('Nlength', $this->_string_shift($paddedKey, 4)));
1537                if (strlen($paddedKey) < $length) {
1538                    return false;
1539                }
1540                $components['comment'] = $this->_string_shift($decoded, $length);
1541
1542                $temp = $components['primes'][1]->subtract($this->one);
1543                $components['exponents'] = array(1 => $components['publicExponent']->modInverse($temp));
1544                $temp = $components['primes'][2]->subtract($this->one);
1545                $components['exponents'][] = $components['publicExponent']->modInverse($temp);
1546
1547                return $components;
1548        }
1549
1550        return false;
1551    }
1552
1553    /**
1554     * Returns the key size
1555     *
1556     * More specifically, this returns the size of the modulo in bits.
1557     *
1558     * @access public
1559     * @return int
1560     */
1561    function getSize()
1562    {
1563        return !isset($this->modulus) ? 0 : strlen($this->modulus->toBits());
1564    }
1565
1566    /**
1567     * Start Element Handler
1568     *
1569     * Called by xml_set_element_handler()
1570     *
1571     * @access private
1572     * @param resource $parser
1573     * @param string $name
1574     * @param array $attribs
1575     */
1576    function _start_element_handler($parser, $name, $attribs)
1577    {
1578        //$name = strtoupper($name);
1579        switch ($name) {
1580            case 'MODULUS':
1581                $this->current = &$this->components['modulus'];
1582                break;
1583            case 'EXPONENT':
1584                $this->current = &$this->components['publicExponent'];
1585                break;
1586            case 'P':
1587                $this->current = &$this->components['primes'][1];
1588                break;
1589            case 'Q':
1590                $this->current = &$this->components['primes'][2];
1591                break;
1592            case 'DP':
1593                $this->current = &$this->components['exponents'][1];
1594                break;
1595            case 'DQ':
1596                $this->current = &$this->components['exponents'][2];
1597                break;
1598            case 'INVERSEQ':
1599                $this->current = &$this->components['coefficients'][2];
1600                break;
1601            case 'D':
1602                $this->current = &$this->components['privateExponent'];
1603        }
1604        $this->current = '';
1605    }
1606
1607    /**
1608     * Stop Element Handler
1609     *
1610     * Called by xml_set_element_handler()
1611     *
1612     * @access private
1613     * @param resource $parser
1614     * @param string $name
1615     */
1616    function _stop_element_handler($parser, $name)
1617    {
1618        if (isset($this->current)) {
1619            $this->current = new BigInteger(base64_decode($this->current), 256);
1620            unset($this->current);
1621        }
1622    }
1623
1624    /**
1625     * Data Handler
1626     *
1627     * Called by xml_set_character_data_handler()
1628     *
1629     * @access private
1630     * @param resource $parser
1631     * @param string $data
1632     */
1633    function _data_handler($parser, $data)
1634    {
1635        if (!isset($this->current) || is_object($this->current)) {
1636            return;
1637        }
1638        $this->current.= trim($data);
1639    }
1640
1641    /**
1642     * Loads a public or private key
1643     *
1644     * Returns true on success and false on failure (ie. an incorrect password was provided or the key was malformed)
1645     *
1646     * @access public
1647     * @param string|RSA|array $key
1648     * @param bool|int $type optional
1649     * @return bool
1650     */
1651    function loadKey($key, $type = false)
1652    {
1653        if ($key instanceof RSA) {
1654            $this->privateKeyFormat = $key->privateKeyFormat;
1655            $this->publicKeyFormat = $key->publicKeyFormat;
1656            $this->k = $key->k;
1657            $this->hLen = $key->hLen;
1658            $this->sLen = $key->sLen;
1659            $this->mgfHLen = $key->mgfHLen;
1660            $this->encryptionMode = $key->encryptionMode;
1661            $this->signatureMode = $key->signatureMode;
1662            $this->password = $key->password;
1663            $this->configFile = $key->configFile;
1664            $this->comment = $key->comment;
1665
1666            if (is_object($key->hash)) {
1667                $this->hash = new Hash($key->hash->getHash());
1668            }
1669            if (is_object($key->mgfHash)) {
1670                $this->mgfHash = new Hash($key->mgfHash->getHash());
1671            }
1672
1673            if (is_object($key->modulus)) {
1674                $this->modulus = $key->modulus->copy();
1675            }
1676            if (is_object($key->exponent)) {
1677                $this->exponent = $key->exponent->copy();
1678            }
1679            if (is_object($key->publicExponent)) {
1680                $this->publicExponent = $key->publicExponent->copy();
1681            }
1682
1683            $this->primes = array();
1684            $this->exponents = array();
1685            $this->coefficients = array();
1686
1687            foreach ($this->primes as $prime) {
1688                $this->primes[] = $prime->copy();
1689            }
1690            foreach ($this->exponents as $exponent) {
1691                $this->exponents[] = $exponent->copy();
1692            }
1693            foreach ($this->coefficients as $coefficient) {
1694                $this->coefficients[] = $coefficient->copy();
1695            }
1696
1697            return true;
1698        }
1699
1700        if ($type === false) {
1701            $types = array(
1702                self::PUBLIC_FORMAT_RAW,
1703                self::PRIVATE_FORMAT_PKCS1,
1704                self::PRIVATE_FORMAT_XML,
1705                self::PRIVATE_FORMAT_PUTTY,
1706                self::PUBLIC_FORMAT_OPENSSH,
1707                self::PRIVATE_FORMAT_OPENSSH
1708            );
1709            foreach ($types as $type) {
1710                $components = $this->_parseKey($key, $type);
1711                if ($components !== false) {
1712                    break;
1713                }
1714            }
1715        } else {
1716            $components = $this->_parseKey($key, $type);
1717        }
1718
1719        if ($components === false) {
1720            $this->comment = null;
1721            $this->modulus = null;
1722            $this->k = null;
1723            $this->exponent = null;
1724            $this->primes = null;
1725            $this->exponents = null;
1726            $this->coefficients = null;
1727            $this->publicExponent = null;
1728
1729            return false;
1730        }
1731
1732        if (isset($components['comment']) && $components['comment'] !== false) {
1733            $this->comment = $components['comment'];
1734        }
1735        $this->modulus = $components['modulus'];
1736        $this->k = strlen($this->modulus->toBytes());
1737        $this->exponent = isset($components['privateExponent']) ? $components['privateExponent'] : $components['publicExponent'];
1738        if (isset($components['primes'])) {
1739            $this->primes = $components['primes'];
1740            $this->exponents = $components['exponents'];
1741            $this->coefficients = $components['coefficients'];
1742            $this->publicExponent = $components['publicExponent'];
1743        } else {
1744            $this->primes = array();
1745            $this->exponents = array();
1746            $this->coefficients = array();
1747            $this->publicExponent = false;
1748        }
1749
1750        switch ($type) {
1751            case self::PUBLIC_FORMAT_OPENSSH:
1752            case self::PUBLIC_FORMAT_RAW:
1753                $this->setPublicKey();
1754                break;
1755            case self::PRIVATE_FORMAT_PKCS1:
1756                switch (true) {
1757                    case strpos($key, '-BEGIN PUBLIC KEY-') !== false:
1758                    case strpos($key, '-BEGIN RSA PUBLIC KEY-') !== false:
1759                        $this->setPublicKey();
1760                }
1761        }
1762
1763        return true;
1764    }
1765
1766    /**
1767     * Sets the password
1768     *
1769     * Private keys can be encrypted with a password.  To unset the password, pass in the empty string or false.
1770     * Or rather, pass in $password such that empty($password) && !is_string($password) is true.
1771     *
1772     * @see self::createKey()
1773     * @see self::loadKey()
1774     * @access public
1775     * @param string $password
1776     */
1777    function setPassword($password = false)
1778    {
1779        $this->password = $password;
1780    }
1781
1782    /**
1783     * Defines the public key
1784     *
1785     * Some private key formats define the public exponent and some don't.  Those that don't define it are problematic when
1786     * used in certain contexts.  For example, in SSH-2, RSA authentication works by sending the public key along with a
1787     * message signed by the private key to the server.  The SSH-2 server looks the public key up in an index of public keys
1788     * and if it's present then proceeds to verify the signature.  Problem is, if your private key doesn't include the public
1789     * exponent this won't work unless you manually add the public exponent. phpseclib tries to guess if the key being used
1790     * is the public key but in the event that it guesses incorrectly you might still want to explicitly set the key as being
1791     * public.
1792     *
1793     * Do note that when a new key is loaded the index will be cleared.
1794     *
1795     * Returns true on success, false on failure
1796     *
1797     * @see self::getPublicKey()
1798     * @access public
1799     * @param string $key optional
1800     * @param int $type optional
1801     * @return bool
1802     */
1803    function setPublicKey($key = false, $type = false)
1804    {
1805        // if a public key has already been loaded return false
1806        if (!empty($this->publicExponent)) {
1807            return false;
1808        }
1809
1810        if ($key === false && !empty($this->modulus)) {
1811            $this->publicExponent = $this->exponent;
1812            return true;
1813        }
1814
1815        if ($type === false) {
1816            $types = array(
1817                self::PUBLIC_FORMAT_RAW,
1818                self::PUBLIC_FORMAT_PKCS1,
1819                self::PUBLIC_FORMAT_XML,
1820                self::PUBLIC_FORMAT_OPENSSH
1821            );
1822            foreach ($types as $type) {
1823                $components = $this->_parseKey($key, $type);
1824                if ($components !== false) {
1825                    break;
1826                }
1827            }
1828        } else {
1829            $components = $this->_parseKey($key, $type);
1830        }
1831
1832        if ($components === false) {
1833            return false;
1834        }
1835
1836        if (empty($this->modulus) || !$this->modulus->equals($components['modulus'])) {
1837            $this->modulus = $components['modulus'];
1838            $this->exponent = $this->publicExponent = $components['publicExponent'];
1839            return true;
1840        }
1841
1842        $this->publicExponent = $components['publicExponent'];
1843
1844        return true;
1845    }
1846
1847    /**
1848     * Defines the private key
1849     *
1850     * If phpseclib guessed a private key was a public key and loaded it as such it might be desirable to force
1851     * phpseclib to treat the key as a private key. This function will do that.
1852     *
1853     * Do note that when a new key is loaded the index will be cleared.
1854     *
1855     * Returns true on success, false on failure
1856     *
1857     * @see self::getPublicKey()
1858     * @access public
1859     * @param string $key optional
1860     * @param int $type optional
1861     * @return bool
1862     */
1863    function setPrivateKey($key = false, $type = false)
1864    {
1865        if ($key === false && !empty($this->publicExponent)) {
1866            $this->publicExponent = false;
1867            return true;
1868        }
1869
1870        $rsa = new RSA();
1871        if (!$rsa->loadKey($key, $type)) {
1872            return false;
1873        }
1874        $rsa->publicExponent = false;
1875
1876        // don't overwrite the old key if the new key is invalid
1877        $this->loadKey($rsa);
1878        return true;
1879    }
1880
1881    /**
1882     * Returns the public key
1883     *
1884     * The public key is only returned under two circumstances - if the private key had the public key embedded within it
1885     * or if the public key was set via setPublicKey().  If the currently loaded key is supposed to be the public key this
1886     * function won't return it since this library, for the most part, doesn't distinguish between public and private keys.
1887     *
1888     * @see self::getPublicKey()
1889     * @access public
1890     * @param int $type optional
1891     */
1892    function getPublicKey($type = self::PUBLIC_FORMAT_PKCS8)
1893    {
1894        if (empty($this->modulus) || empty($this->publicExponent)) {
1895            return false;
1896        }
1897
1898        $oldFormat = $this->publicKeyFormat;
1899        $this->publicKeyFormat = $type;
1900        $temp = $this->_convertPublicKey($this->modulus, $this->publicExponent);
1901        $this->publicKeyFormat = $oldFormat;
1902        return $temp;
1903    }
1904
1905    /**
1906     * Returns the public key's fingerprint
1907     *
1908     * The public key's fingerprint is returned, which is equivalent to running `ssh-keygen -lf rsa.pub`. If there is
1909     * no public key currently loaded, false is returned.
1910     * Example output (md5): "c1:b1:30:29:d7:b8:de:6c:97:77:10:d7:46:41:63:87" (as specified by RFC 4716)
1911     *
1912     * @access public
1913     * @param string $algorithm The hashing algorithm to be used. Valid options are 'md5' and 'sha256'. False is returned
1914     * for invalid values.
1915     * @return mixed
1916     */
1917    function getPublicKeyFingerprint($algorithm = 'md5')
1918    {
1919        if (empty($this->modulus) || empty($this->publicExponent)) {
1920            return false;
1921        }
1922
1923        $modulus = $this->modulus->toBytes(true);
1924        $publicExponent = $this->publicExponent->toBytes(true);
1925
1926        $RSAPublicKey = pack('Na*Na*Na*', strlen('ssh-rsa'), 'ssh-rsa', strlen($publicExponent), $publicExponent, strlen($modulus), $modulus);
1927
1928        switch ($algorithm) {
1929            case 'sha256':
1930                $hash = new Hash('sha256');
1931                $base = base64_encode($hash->hash($RSAPublicKey));
1932                return substr($base, 0, strlen($base) - 1);
1933            case 'md5':
1934                return substr(chunk_split(md5($RSAPublicKey), 2, ':'), 0, -1);
1935            default:
1936                return false;
1937        }
1938    }
1939
1940    /**
1941     * Returns the private key
1942     *
1943     * The private key is only returned if the currently loaded key contains the constituent prime numbers.
1944     *
1945     * @see self::getPublicKey()
1946     * @access public
1947     * @param int $type optional
1948     * @return mixed
1949     */
1950    function getPrivateKey($type = self::PUBLIC_FORMAT_PKCS1)
1951    {
1952        if (empty($this->primes)) {
1953            return false;
1954        }
1955
1956        $oldFormat = $this->privateKeyFormat;
1957        $this->privateKeyFormat = $type;
1958        $temp = $this->_convertPrivateKey($this->modulus, $this->publicExponent, $this->exponent, $this->primes, $this->exponents, $this->coefficients);
1959        $this->privateKeyFormat = $oldFormat;
1960        return $temp;
1961    }
1962
1963    /**
1964     * Returns a minimalistic private key
1965     *
1966     * Returns the private key without the prime number constituants.  Structurally identical to a public key that
1967     * hasn't been set as the public key
1968     *
1969     * @see self::getPrivateKey()
1970     * @access private
1971     * @param int $mode optional
1972     */
1973    function _getPrivatePublicKey($mode = self::PUBLIC_FORMAT_PKCS8)
1974    {
1975        if (empty($this->modulus) || empty($this->exponent)) {
1976            return false;
1977        }
1978
1979        $oldFormat = $this->publicKeyFormat;
1980        $this->publicKeyFormat = $mode;
1981        $temp = $this->_convertPublicKey($this->modulus, $this->exponent);
1982        $this->publicKeyFormat = $oldFormat;
1983        return $temp;
1984    }
1985
1986    /**
1987     *  __toString() magic method
1988     *
1989     * @access public
1990     * @return string
1991     */
1992    function __toString()
1993    {
1994        $key = $this->getPrivateKey($this->privateKeyFormat);
1995        if ($key !== false) {
1996            return $key;
1997        }
1998        $key = $this->_getPrivatePublicKey($this->publicKeyFormat);
1999        return $key !== false ? $key : '';
2000    }
2001
2002    /**
2003     *  __clone() magic method
2004     *
2005     * @access public
2006     * @return Crypt_RSA
2007     */
2008    function __clone()
2009    {
2010        $key = new RSA();
2011        $key->loadKey($this);
2012        return $key;
2013    }
2014
2015    /**
2016     * Generates the smallest and largest numbers requiring $bits bits
2017     *
2018     * @access private
2019     * @param int $bits
2020     * @return array
2021     */
2022    function _generateMinMax($bits)
2023    {
2024        $bytes = $bits >> 3;
2025        $min = str_repeat(chr(0), $bytes);
2026        $max = str_repeat(chr(0xFF), $bytes);
2027        $msb = $bits & 7;
2028        if ($msb) {
2029            $min = chr(1 << ($msb - 1)) . $min;
2030            $max = chr((1 << $msb) - 1) . $max;
2031        } else {
2032            $min[0] = chr(0x80);
2033        }
2034
2035        return array(
2036            'min' => new BigInteger($min, 256),
2037            'max' => new BigInteger($max, 256)
2038        );
2039    }
2040
2041    /**
2042     * DER-decode the length
2043     *
2044     * DER supports lengths up to (2**8)**127, however, we'll only support lengths up to (2**8)**4.  See
2045     * {@link http://itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf#p=13 X.690 paragraph 8.1.3} for more information.
2046     *
2047     * @access private
2048     * @param string $string
2049     * @return int
2050     */
2051    function _decodeLength(&$string)
2052    {
2053        $length = ord($this->_string_shift($string));
2054        if ($length & 0x80) { // definite length, long form
2055            $length&= 0x7F;
2056            $temp = $this->_string_shift($string, $length);
2057            list(, $length) = unpack('N', substr(str_pad($temp, 4, chr(0), STR_PAD_LEFT), -4));
2058        }
2059        return $length;
2060    }
2061
2062    /**
2063     * DER-encode the length
2064     *
2065     * DER supports lengths up to (2**8)**127, however, we'll only support lengths up to (2**8)**4.  See
2066     * {@link http://itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf#p=13 X.690 paragraph 8.1.3} for more information.
2067     *
2068     * @access private
2069     * @param int $length
2070     * @return string
2071     */
2072    function _encodeLength($length)
2073    {
2074        if ($length <= 0x7F) {
2075            return chr($length);
2076        }
2077
2078        $temp = ltrim(pack('N', $length), chr(0));
2079        return pack('Ca*', 0x80 | strlen($temp), $temp);
2080    }
2081
2082    /**
2083     * String Shift
2084     *
2085     * Inspired by array_shift
2086     *
2087     * @param string $string
2088     * @param int $index
2089     * @return string
2090     * @access private
2091     */
2092    function _string_shift(&$string, $index = 1)
2093    {
2094        $substr = substr($string, 0, $index);
2095        $string = substr($string, $index);
2096        return $substr;
2097    }
2098
2099    /**
2100     * Determines the private key format
2101     *
2102     * @see self::createKey()
2103     * @access public
2104     * @param int $format
2105     */
2106    function setPrivateKeyFormat($format)
2107    {
2108        $this->privateKeyFormat = $format;
2109    }
2110
2111    /**
2112     * Determines the public key format
2113     *
2114     * @see self::createKey()
2115     * @access public
2116     * @param int $format
2117     */
2118    function setPublicKeyFormat($format)
2119    {
2120        $this->publicKeyFormat = $format;
2121    }
2122
2123    /**
2124     * Determines which hashing function should be used
2125     *
2126     * Used with signature production / verification and (if the encryption mode is self::ENCRYPTION_OAEP) encryption and
2127     * decryption.  If $hash isn't supported, sha1 is used.
2128     *
2129     * @access public
2130     * @param string $hash
2131     */
2132    function setHash($hash)
2133    {
2134        // \phpseclib\Crypt\Hash supports algorithms that PKCS#1 doesn't support.  md5-96 and sha1-96, for example.
2135        switch ($hash) {
2136            case 'md2':
2137            case 'md5':
2138            case 'sha1':
2139            case 'sha256':
2140            case 'sha384':
2141            case 'sha512':
2142                $this->hash = new Hash($hash);
2143                $this->hashName = $hash;
2144                break;
2145            default:
2146                $this->hash = new Hash('sha1');
2147                $this->hashName = 'sha1';
2148        }
2149        $this->hLen = $this->hash->getLength();
2150    }
2151
2152    /**
2153     * Determines which hashing function should be used for the mask generation function
2154     *
2155     * The mask generation function is used by self::ENCRYPTION_OAEP and self::SIGNATURE_PSS and although it's
2156     * best if Hash and MGFHash are set to the same thing this is not a requirement.
2157     *
2158     * @access public
2159     * @param string $hash
2160     */
2161    function setMGFHash($hash)
2162    {
2163        // \phpseclib\Crypt\Hash supports algorithms that PKCS#1 doesn't support.  md5-96 and sha1-96, for example.
2164        switch ($hash) {
2165            case 'md2':
2166            case 'md5':
2167            case 'sha1':
2168            case 'sha256':
2169            case 'sha384':
2170            case 'sha512':
2171                $this->mgfHash = new Hash($hash);
2172                break;
2173            default:
2174                $this->mgfHash = new Hash('sha1');
2175        }
2176        $this->mgfHLen = $this->mgfHash->getLength();
2177    }
2178
2179    /**
2180     * Determines the salt length
2181     *
2182     * To quote from {@link http://tools.ietf.org/html/rfc3447#page-38 RFC3447#page-38}:
2183     *
2184     *    Typical salt lengths in octets are hLen (the length of the output
2185     *    of the hash function Hash) and 0.
2186     *
2187     * @access public
2188     * @param int $sLen
2189     */
2190    function setSaltLength($sLen)
2191    {
2192        $this->sLen = $sLen;
2193    }
2194
2195    /**
2196     * Integer-to-Octet-String primitive
2197     *
2198     * See {@link http://tools.ietf.org/html/rfc3447#section-4.1 RFC3447#section-4.1}.
2199     *
2200     * @access private
2201     * @param \phpseclib\Math\BigInteger $x
2202     * @param int $xLen
2203     * @return string
2204     */
2205    function _i2osp($x, $xLen)
2206    {
2207        $x = $x->toBytes();
2208        if (strlen($x) > $xLen) {
2209            user_error('Integer too large');
2210            return false;
2211        }
2212        return str_pad($x, $xLen, chr(0), STR_PAD_LEFT);
2213    }
2214
2215    /**
2216     * Octet-String-to-Integer primitive
2217     *
2218     * See {@link http://tools.ietf.org/html/rfc3447#section-4.2 RFC3447#section-4.2}.
2219     *
2220     * @access private
2221     * @param int|string|resource $x
2222     * @return \phpseclib\Math\BigInteger
2223     */
2224    function _os2ip($x)
2225    {
2226        return new BigInteger($x, 256);
2227    }
2228
2229    /**
2230     * Exponentiate with or without Chinese Remainder Theorem
2231     *
2232     * See {@link http://tools.ietf.org/html/rfc3447#section-5.1.1 RFC3447#section-5.1.2}.
2233     *
2234     * @access private
2235     * @param \phpseclib\Math\BigInteger $x
2236     * @return \phpseclib\Math\BigInteger
2237     */
2238    function _exponentiate($x)
2239    {
2240        switch (true) {
2241            case empty($this->primes):
2242            case $this->primes[1]->equals($this->zero):
2243            case empty($this->coefficients):
2244            case $this->coefficients[2]->equals($this->zero):
2245            case empty($this->exponents):
2246            case $this->exponents[1]->equals($this->zero):
2247                return $x->modPow($this->exponent, $this->modulus);
2248        }
2249
2250        $num_primes = count($this->primes);
2251
2252        if (defined('CRYPT_RSA_DISABLE_BLINDING')) {
2253            $m_i = array(
2254                1 => $x->modPow($this->exponents[1], $this->primes[1]),
2255                2 => $x->modPow($this->exponents[2], $this->primes[2])
2256            );
2257            $h = $m_i[1]->subtract($m_i[2]);
2258            $h = $h->multiply($this->coefficients[2]);
2259            list(, $h) = $h->divide($this->primes[1]);
2260            $m = $m_i[2]->add($h->multiply($this->primes[2]));
2261
2262            $r = $this->primes[1];
2263            for ($i = 3; $i <= $num_primes; $i++) {
2264                $m_i = $x->modPow($this->exponents[$i], $this->primes[$i]);
2265
2266                $r = $r->multiply($this->primes[$i - 1]);
2267
2268                $h = $m_i->subtract($m);
2269                $h = $h->multiply($this->coefficients[$i]);
2270                list(, $h) = $h->divide($this->primes[$i]);
2271
2272                $m = $m->add($r->multiply($h));
2273            }
2274        } else {
2275            $smallest = $this->primes[1];
2276            for ($i = 2; $i <= $num_primes; $i++) {
2277                if ($smallest->compare($this->primes[$i]) > 0) {
2278                    $smallest = $this->primes[$i];
2279                }
2280            }
2281
2282            $one = new BigInteger(1);
2283
2284            $r = $one->random($one, $smallest->subtract($one));
2285
2286            $m_i = array(
2287                1 => $this->_blind($x, $r, 1),
2288                2 => $this->_blind($x, $r, 2)
2289            );
2290            $h = $m_i[1]->subtract($m_i[2]);
2291            $h = $h->multiply($this->coefficients[2]);
2292            list(, $h) = $h->divide($this->primes[1]);
2293            $m = $m_i[2]->add($h->multiply($this->primes[2]));
2294
2295            $r = $this->primes[1];
2296            for ($i = 3; $i <= $num_primes; $i++) {
2297                $m_i = $this->_blind($x, $r, $i);
2298
2299                $r = $r->multiply($this->primes[$i - 1]);
2300
2301                $h = $m_i->subtract($m);
2302                $h = $h->multiply($this->coefficients[$i]);
2303                list(, $h) = $h->divide($this->primes[$i]);
2304
2305                $m = $m->add($r->multiply($h));
2306            }
2307        }
2308
2309        return $m;
2310    }
2311
2312    /**
2313     * Performs RSA Blinding
2314     *
2315     * Protects against timing attacks by employing RSA Blinding.
2316     * Returns $x->modPow($this->exponents[$i], $this->primes[$i])
2317     *
2318     * @access private
2319     * @param \phpseclib\Math\BigInteger $x
2320     * @param \phpseclib\Math\BigInteger $r
2321     * @param int $i
2322     * @return \phpseclib\Math\BigInteger
2323     */
2324    function _blind($x, $r, $i)
2325    {
2326        $x = $x->multiply($r->modPow($this->publicExponent, $this->primes[$i]));
2327        $x = $x->modPow($this->exponents[$i], $this->primes[$i]);
2328
2329        $r = $r->modInverse($this->primes[$i]);
2330        $x = $x->multiply($r);
2331        list(, $x) = $x->divide($this->primes[$i]);
2332
2333        return $x;
2334    }
2335
2336    /**
2337     * Performs blinded RSA equality testing
2338     *
2339     * Protects against a particular type of timing attack described.
2340     *
2341     * See {@link http://codahale.com/a-lesson-in-timing-attacks/ A Lesson In Timing Attacks (or, Don't use MessageDigest.isEquals)}
2342     *
2343     * Thanks for the heads up singpolyma!
2344     *
2345     * @access private
2346     * @param string $x
2347     * @param string $y
2348     * @return bool
2349     */
2350    function _equals($x, $y)
2351    {
2352        if (function_exists('hash_equals')) {
2353            return hash_equals($x, $y);
2354        }
2355
2356        if (strlen($x) != strlen($y)) {
2357            return false;
2358        }
2359
2360        $result = "\0";
2361        $x^= $y;
2362        for ($i = 0; $i < strlen($x); $i++) {
2363            $result|= $x[$i];
2364        }
2365
2366        return $result === "\0";
2367    }
2368
2369    /**
2370     * RSAEP
2371     *
2372     * See {@link http://tools.ietf.org/html/rfc3447#section-5.1.1 RFC3447#section-5.1.1}.
2373     *
2374     * @access private
2375     * @param \phpseclib\Math\BigInteger $m
2376     * @return \phpseclib\Math\BigInteger
2377     */
2378    function _rsaep($m)
2379    {
2380        if ($m->compare($this->zero) < 0 || $m->compare($this->modulus) > 0) {
2381            user_error('Message representative out of range');
2382            return false;
2383        }
2384        return $this->_exponentiate($m);
2385    }
2386
2387    /**
2388     * RSADP
2389     *
2390     * See {@link http://tools.ietf.org/html/rfc3447#section-5.1.2 RFC3447#section-5.1.2}.
2391     *
2392     * @access private
2393     * @param \phpseclib\Math\BigInteger $c
2394     * @return \phpseclib\Math\BigInteger
2395     */
2396    function _rsadp($c)
2397    {
2398        if ($c->compare($this->zero) < 0 || $c->compare($this->modulus) > 0) {
2399            user_error('Ciphertext representative out of range');
2400            return false;
2401        }
2402        return $this->_exponentiate($c);
2403    }
2404
2405    /**
2406     * RSASP1
2407     *
2408     * See {@link http://tools.ietf.org/html/rfc3447#section-5.2.1 RFC3447#section-5.2.1}.
2409     *
2410     * @access private
2411     * @param \phpseclib\Math\BigInteger $m
2412     * @return \phpseclib\Math\BigInteger
2413     */
2414    function _rsasp1($m)
2415    {
2416        if ($m->compare($this->zero) < 0 || $m->compare($this->modulus) > 0) {
2417            user_error('Message representative out of range');
2418            return false;
2419        }
2420        return $this->_exponentiate($m);
2421    }
2422
2423    /**
2424     * RSAVP1
2425     *
2426     * See {@link http://tools.ietf.org/html/rfc3447#section-5.2.2 RFC3447#section-5.2.2}.
2427     *
2428     * @access private
2429     * @param \phpseclib\Math\BigInteger $s
2430     * @return \phpseclib\Math\BigInteger
2431     */
2432    function _rsavp1($s)
2433    {
2434        if ($s->compare($this->zero) < 0 || $s->compare($this->modulus) > 0) {
2435            user_error('Signature representative out of range');
2436            return false;
2437        }
2438        return $this->_exponentiate($s);
2439    }
2440
2441    /**
2442     * MGF1
2443     *
2444     * See {@link http://tools.ietf.org/html/rfc3447#appendix-B.2.1 RFC3447#appendix-B.2.1}.
2445     *
2446     * @access private
2447     * @param string $mgfSeed
2448     * @param int $maskLen
2449     * @return string
2450     */
2451    function _mgf1($mgfSeed, $maskLen)
2452    {
2453        // if $maskLen would yield strings larger than 4GB, PKCS#1 suggests a "Mask too long" error be output.
2454
2455        $t = '';
2456        $count = ceil($maskLen / $this->mgfHLen);
2457        for ($i = 0; $i < $count; $i++) {
2458            $c = pack('N', $i);
2459            $t.= $this->mgfHash->hash($mgfSeed . $c);
2460        }
2461
2462        return substr($t, 0, $maskLen);
2463    }
2464
2465    /**
2466     * RSAES-OAEP-ENCRYPT
2467     *
2468     * See {@link http://tools.ietf.org/html/rfc3447#section-7.1.1 RFC3447#section-7.1.1} and
2469     * {http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding OAES}.
2470     *
2471     * @access private
2472     * @param string $m
2473     * @param string $l
2474     * @return string
2475     */
2476    function _rsaes_oaep_encrypt($m, $l = '')
2477    {
2478        $mLen = strlen($m);
2479
2480        // Length checking
2481
2482        // if $l is larger than two million terrabytes and you're using sha1, PKCS#1 suggests a "Label too long" error
2483        // be output.
2484
2485        if ($mLen > $this->k - 2 * $this->hLen - 2) {
2486            user_error('Message too long');
2487            return false;
2488        }
2489
2490        // EME-OAEP encoding
2491
2492        $lHash = $this->hash->hash($l);
2493        $ps = str_repeat(chr(0), $this->k - $mLen - 2 * $this->hLen - 2);
2494        $db = $lHash . $ps . chr(1) . $m;
2495        $seed = Random::string($this->hLen);
2496        $dbMask = $this->_mgf1($seed, $this->k - $this->hLen - 1);
2497        $maskedDB = $db ^ $dbMask;
2498        $seedMask = $this->_mgf1($maskedDB, $this->hLen);
2499        $maskedSeed = $seed ^ $seedMask;
2500        $em = chr(0) . $maskedSeed . $maskedDB;
2501
2502        // RSA encryption
2503
2504        $m = $this->_os2ip($em);
2505        $c = $this->_rsaep($m);
2506        $c = $this->_i2osp($c, $this->k);
2507
2508        // Output the ciphertext C
2509
2510        return $c;
2511    }
2512
2513    /**
2514     * RSAES-OAEP-DECRYPT
2515     *
2516     * See {@link http://tools.ietf.org/html/rfc3447#section-7.1.2 RFC3447#section-7.1.2}.  The fact that the error
2517     * messages aren't distinguishable from one another hinders debugging, but, to quote from RFC3447#section-7.1.2:
2518     *
2519     *    Note.  Care must be taken to ensure that an opponent cannot
2520     *    distinguish the different error conditions in Step 3.g, whether by
2521     *    error message or timing, or, more generally, learn partial
2522     *    information about the encoded message EM.  Otherwise an opponent may
2523     *    be able to obtain useful information about the decryption of the
2524     *    ciphertext C, leading to a chosen-ciphertext attack such as the one
2525     *    observed by Manger [36].
2526     *
2527     * As for $l...  to quote from {@link http://tools.ietf.org/html/rfc3447#page-17 RFC3447#page-17}:
2528     *
2529     *    Both the encryption and the decryption operations of RSAES-OAEP take
2530     *    the value of a label L as input.  In this version of PKCS #1, L is
2531     *    the empty string; other uses of the label are outside the scope of
2532     *    this document.
2533     *
2534     * @access private
2535     * @param string $c
2536     * @param string $l
2537     * @return string
2538     */
2539    function _rsaes_oaep_decrypt($c, $l = '')
2540    {
2541        // Length checking
2542
2543        // if $l is larger than two million terrabytes and you're using sha1, PKCS#1 suggests a "Label too long" error
2544        // be output.
2545
2546        if (strlen($c) != $this->k || $this->k < 2 * $this->hLen + 2) {
2547            user_error('Decryption error');
2548            return false;
2549        }
2550
2551        // RSA decryption
2552
2553        $c = $this->_os2ip($c);
2554        $m = $this->_rsadp($c);
2555        if ($m === false) {
2556            user_error('Decryption error');
2557            return false;
2558        }
2559        $em = $this->_i2osp($m, $this->k);
2560
2561        // EME-OAEP decoding
2562
2563        $lHash = $this->hash->hash($l);
2564        $y = ord($em[0]);
2565        $maskedSeed = substr($em, 1, $this->hLen);
2566        $maskedDB = substr($em, $this->hLen + 1);
2567        $seedMask = $this->_mgf1($maskedDB, $this->hLen);
2568        $seed = $maskedSeed ^ $seedMask;
2569        $dbMask = $this->_mgf1($seed, $this->k - $this->hLen - 1);
2570        $db = $maskedDB ^ $dbMask;
2571        $lHash2 = substr($db, 0, $this->hLen);
2572        $m = substr($db, $this->hLen);
2573        $hashesMatch = $this->_equals($lHash, $lHash2);
2574        $leadingZeros = 1;
2575        $patternMatch = 0;
2576        $offset = 0;
2577        for ($i = 0; $i < strlen($m); $i++) {
2578            $patternMatch|= $leadingZeros & ($m[$i] === "\1");
2579            $leadingZeros&= $m[$i] === "\0";
2580            $offset+= $patternMatch ? 0 : 1;
2581        }
2582
2583        // we do & instead of && to avoid https://en.wikipedia.org/wiki/Short-circuit_evaluation
2584        // to protect against timing attacks
2585        if (!$hashesMatch & !$patternMatch) {
2586            user_error('Decryption error');
2587            return false;
2588        }
2589
2590        // Output the message M
2591
2592        return substr($m, $offset + 1);
2593    }
2594
2595    /**
2596     * Raw Encryption / Decryption
2597     *
2598     * Doesn't use padding and is not recommended.
2599     *
2600     * @access private
2601     * @param string $m
2602     * @return string
2603     */
2604    function _raw_encrypt($m)
2605    {
2606        $temp = $this->_os2ip($m);
2607        $temp = $this->_rsaep($temp);
2608        return  $this->_i2osp($temp, $this->k);
2609    }
2610
2611    /**
2612     * RSAES-PKCS1-V1_5-ENCRYPT
2613     *
2614     * See {@link http://tools.ietf.org/html/rfc3447#section-7.2.1 RFC3447#section-7.2.1}.
2615     *
2616     * @access private
2617     * @param string $m
2618     * @return string
2619     */
2620    function _rsaes_pkcs1_v1_5_encrypt($m)
2621    {
2622        $mLen = strlen($m);
2623
2624        // Length checking
2625
2626        if ($mLen > $this->k - 11) {
2627            user_error('Message too long');
2628            return false;
2629        }
2630
2631        // EME-PKCS1-v1_5 encoding
2632
2633        $psLen = $this->k - $mLen - 3;
2634        $ps = '';
2635        while (strlen($ps) != $psLen) {
2636            $temp = Random::string($psLen - strlen($ps));
2637            $temp = str_replace("\x00", '', $temp);
2638            $ps.= $temp;
2639        }
2640        $type = 2;
2641        // see the comments of _rsaes_pkcs1_v1_5_decrypt() to understand why this is being done
2642        if (defined('CRYPT_RSA_PKCS15_COMPAT') && (!isset($this->publicExponent) || $this->exponent !== $this->publicExponent)) {
2643            $type = 1;
2644            // "The padding string PS shall consist of k-3-||D|| octets. ... for block type 01, they shall have value FF"
2645            $ps = str_repeat("\xFF", $psLen);
2646        }
2647        $em = chr(0) . chr($type) . $ps . chr(0) . $m;
2648
2649        // RSA encryption
2650        $m = $this->_os2ip($em);
2651        $c = $this->_rsaep($m);
2652        $c = $this->_i2osp($c, $this->k);
2653
2654        // Output the ciphertext C
2655
2656        return $c;
2657    }
2658
2659    /**
2660     * RSAES-PKCS1-V1_5-DECRYPT
2661     *
2662     * See {@link http://tools.ietf.org/html/rfc3447#section-7.2.2 RFC3447#section-7.2.2}.
2663     *
2664     * For compatibility purposes, this function departs slightly from the description given in RFC3447.
2665     * The reason being that RFC2313#section-8.1 (PKCS#1 v1.5) states that ciphertext's encrypted by the
2666     * private key should have the second byte set to either 0 or 1 and that ciphertext's encrypted by the
2667     * public key should have the second byte set to 2.  In RFC3447 (PKCS#1 v2.1), the second byte is supposed
2668     * to be 2 regardless of which key is used.  For compatibility purposes, we'll just check to make sure the
2669     * second byte is 2 or less.  If it is, we'll accept the decrypted string as valid.
2670     *
2671     * As a consequence of this, a private key encrypted ciphertext produced with \phpseclib\Crypt\RSA may not decrypt
2672     * with a strictly PKCS#1 v1.5 compliant RSA implementation.  Public key encrypted ciphertext's should but
2673     * not private key encrypted ciphertext's.
2674     *
2675     * @access private
2676     * @param string $c
2677     * @return string
2678     */
2679    function _rsaes_pkcs1_v1_5_decrypt($c)
2680    {
2681        // Length checking
2682
2683        if (strlen($c) != $this->k) { // or if k < 11
2684            user_error('Decryption error');
2685            return false;
2686        }
2687
2688        // RSA decryption
2689
2690        $c = $this->_os2ip($c);
2691        $m = $this->_rsadp($c);
2692
2693        if ($m === false) {
2694            user_error('Decryption error');
2695            return false;
2696        }
2697        $em = $this->_i2osp($m, $this->k);
2698
2699        // EME-PKCS1-v1_5 decoding
2700
2701        if (ord($em[0]) != 0 || ord($em[1]) > 2) {
2702            user_error('Decryption error');
2703            return false;
2704        }
2705
2706        $ps = substr($em, 2, strpos($em, chr(0), 2) - 2);
2707        $m = substr($em, strlen($ps) + 3);
2708
2709        if (strlen($ps) < 8) {
2710            user_error('Decryption error');
2711            return false;
2712        }
2713
2714        // Output M
2715
2716        return $m;
2717    }
2718
2719    /**
2720     * EMSA-PSS-ENCODE
2721     *
2722     * See {@link http://tools.ietf.org/html/rfc3447#section-9.1.1 RFC3447#section-9.1.1}.
2723     *
2724     * @access private
2725     * @param string $m
2726     * @param int $emBits
2727     */
2728    function _emsa_pss_encode($m, $emBits)
2729    {
2730        // if $m is larger than two million terrabytes and you're using sha1, PKCS#1 suggests a "Label too long" error
2731        // be output.
2732
2733        $emLen = ($emBits + 1) >> 3; // ie. ceil($emBits / 8)
2734        $sLen = $this->sLen !== null ? $this->sLen : $this->hLen;
2735
2736        $mHash = $this->hash->hash($m);
2737        if ($emLen < $this->hLen + $sLen + 2) {
2738            user_error('Encoding error');
2739            return false;
2740        }
2741
2742        $salt = Random::string($sLen);
2743        $m2 = "\0\0\0\0\0\0\0\0" . $mHash . $salt;
2744        $h = $this->hash->hash($m2);
2745        $ps = str_repeat(chr(0), $emLen - $sLen - $this->hLen - 2);
2746        $db = $ps . chr(1) . $salt;
2747        $dbMask = $this->_mgf1($h, $emLen - $this->hLen - 1);
2748        $maskedDB = $db ^ $dbMask;
2749        $maskedDB[0] = ~chr(0xFF << ($emBits & 7)) & $maskedDB[0];
2750        $em = $maskedDB . $h . chr(0xBC);
2751
2752        return $em;
2753    }
2754
2755    /**
2756     * EMSA-PSS-VERIFY
2757     *
2758     * See {@link http://tools.ietf.org/html/rfc3447#section-9.1.2 RFC3447#section-9.1.2}.
2759     *
2760     * @access private
2761     * @param string $m
2762     * @param string $em
2763     * @param int $emBits
2764     * @return string
2765     */
2766    function _emsa_pss_verify($m, $em, $emBits)
2767    {
2768        // if $m is larger than two million terrabytes and you're using sha1, PKCS#1 suggests a "Label too long" error
2769        // be output.
2770
2771        $emLen = ($emBits + 7) >> 3; // ie. ceil($emBits / 8);
2772        $sLen = $this->sLen !== null ? $this->sLen : $this->hLen;
2773
2774        $mHash = $this->hash->hash($m);
2775        if ($emLen < $this->hLen + $sLen + 2) {
2776            return false;
2777        }
2778
2779        if ($em[strlen($em) - 1] != chr(0xBC)) {
2780            return false;
2781        }
2782
2783        $maskedDB = substr($em, 0, -$this->hLen - 1);
2784        $h = substr($em, -$this->hLen - 1, $this->hLen);
2785        $temp = chr(0xFF << ($emBits & 7));
2786        if ((~$maskedDB[0] & $temp) != $temp) {
2787            return false;
2788        }
2789        $dbMask = $this->_mgf1($h, $emLen - $this->hLen - 1);
2790        $db = $maskedDB ^ $dbMask;
2791        $db[0] = ~chr(0xFF << ($emBits & 7)) & $db[0];
2792        $temp = $emLen - $this->hLen - $sLen - 2;
2793        if (substr($db, 0, $temp) != str_repeat(chr(0), $temp) || ord($db[$temp]) != 1) {
2794            return false;
2795        }
2796        $salt = substr($db, $temp + 1); // should be $sLen long
2797        $m2 = "\0\0\0\0\0\0\0\0" . $mHash . $salt;
2798        $h2 = $this->hash->hash($m2);
2799        return $this->_equals($h, $h2);
2800    }
2801
2802    /**
2803     * RSASSA-PSS-SIGN
2804     *
2805     * See {@link http://tools.ietf.org/html/rfc3447#section-8.1.1 RFC3447#section-8.1.1}.
2806     *
2807     * @access private
2808     * @param string $m
2809     * @return string
2810     */
2811    function _rsassa_pss_sign($m)
2812    {
2813        // EMSA-PSS encoding
2814
2815        $em = $this->_emsa_pss_encode($m, 8 * $this->k - 1);
2816
2817        // RSA signature
2818
2819        $m = $this->_os2ip($em);
2820        $s = $this->_rsasp1($m);
2821        $s = $this->_i2osp($s, $this->k);
2822
2823        // Output the signature S
2824
2825        return $s;
2826    }
2827
2828    /**
2829     * RSASSA-PSS-VERIFY
2830     *
2831     * See {@link http://tools.ietf.org/html/rfc3447#section-8.1.2 RFC3447#section-8.1.2}.
2832     *
2833     * @access private
2834     * @param string $m
2835     * @param string $s
2836     * @return string
2837     */
2838    function _rsassa_pss_verify($m, $s)
2839    {
2840        // Length checking
2841
2842        if (strlen($s) != $this->k) {
2843            user_error('Invalid signature');
2844            return false;
2845        }
2846
2847        // RSA verification
2848
2849        $modBits = strlen($this->modulus->toBits());
2850
2851        $s2 = $this->_os2ip($s);
2852        $m2 = $this->_rsavp1($s2);
2853        if ($m2 === false) {
2854            user_error('Invalid signature');
2855            return false;
2856        }
2857        $em = $this->_i2osp($m2, $this->k);
2858        if ($em === false) {
2859            user_error('Invalid signature');
2860            return false;
2861        }
2862
2863        // EMSA-PSS verification
2864
2865        return $this->_emsa_pss_verify($m, $em, $modBits - 1);
2866    }
2867
2868    /**
2869     * EMSA-PKCS1-V1_5-ENCODE
2870     *
2871     * See {@link http://tools.ietf.org/html/rfc3447#section-9.2 RFC3447#section-9.2}.
2872     *
2873     * @access private
2874     * @param string $m
2875     * @param int $emLen
2876     * @return string
2877     */
2878    function _emsa_pkcs1_v1_5_encode($m, $emLen)
2879    {
2880        $h = $this->hash->hash($m);
2881        if ($h === false) {
2882            return false;
2883        }
2884
2885        // see http://tools.ietf.org/html/rfc3447#page-43
2886        switch ($this->hashName) {
2887            case 'md2':
2888                $t = pack('H*', '3020300c06082a864886f70d020205000410');
2889                break;
2890            case 'md5':
2891                $t = pack('H*', '3020300c06082a864886f70d020505000410');
2892                break;
2893            case 'sha1':
2894                $t = pack('H*', '3021300906052b0e03021a05000414');
2895                break;
2896            case 'sha256':
2897                $t = pack('H*', '3031300d060960864801650304020105000420');
2898                break;
2899            case 'sha384':
2900                $t = pack('H*', '3041300d060960864801650304020205000430');
2901                break;
2902            case 'sha512':
2903                $t = pack('H*', '3051300d060960864801650304020305000440');
2904        }
2905        $t.= $h;
2906        $tLen = strlen($t);
2907
2908        if ($emLen < $tLen + 11) {
2909            user_error('Intended encoded message length too short');
2910            return false;
2911        }
2912
2913        $ps = str_repeat(chr(0xFF), $emLen - $tLen - 3);
2914
2915        $em = "\0\1$ps\0$t";
2916
2917        return $em;
2918    }
2919
2920    /**
2921     * EMSA-PKCS1-V1_5-ENCODE (without NULL)
2922     *
2923     * Quoting https://tools.ietf.org/html/rfc8017#page-65,
2924     *
2925     * "The parameters field associated with id-sha1, id-sha224, id-sha256,
2926     *  id-sha384, id-sha512, id-sha512/224, and id-sha512/256 should
2927     *  generally be omitted, but if present, it shall have a value of type
2928     *  NULL"
2929     *
2930     * @access private
2931     * @param string $m
2932     * @param int $emLen
2933     * @return string
2934     */
2935    function _emsa_pkcs1_v1_5_encode_without_null($m, $emLen)
2936    {
2937        $h = $this->hash->hash($m);
2938        if ($h === false) {
2939            return false;
2940        }
2941
2942        switch ($this->hashName) {
2943            case 'sha1':
2944                $t = pack('H*', '301f300706052b0e03021a0414');
2945                break;
2946            case 'sha256':
2947                $t = pack('H*', '302f300b06096086480165030402010420');
2948                break;
2949            case 'sha384':
2950                $t = pack('H*', '303f300b06096086480165030402020430');
2951                break;
2952            case 'sha512':
2953                $t = pack('H*', '304f300b06096086480165030402030440');
2954                break;
2955            default:
2956                return false;
2957        }
2958        $t.= $h;
2959        $tLen = strlen($t);
2960
2961        if ($emLen < $tLen + 11) {
2962            user_error('Intended encoded message length too short');
2963            return false;
2964        }
2965
2966        $ps = str_repeat(chr(0xFF), $emLen - $tLen - 3);
2967
2968        $em = "\0\1$ps\0$t";
2969
2970        return $em;
2971    }
2972
2973    /**
2974     * RSASSA-PKCS1-V1_5-SIGN
2975     *
2976     * See {@link http://tools.ietf.org/html/rfc3447#section-8.2.1 RFC3447#section-8.2.1}.
2977     *
2978     * @access private
2979     * @param string $m
2980     * @return string
2981     */
2982    function _rsassa_pkcs1_v1_5_sign($m)
2983    {
2984        // EMSA-PKCS1-v1_5 encoding
2985
2986        $em = $this->_emsa_pkcs1_v1_5_encode($m, $this->k);
2987        if ($em === false) {
2988            user_error('RSA modulus too short');
2989            return false;
2990        }
2991
2992        // RSA signature
2993
2994        $m = $this->_os2ip($em);
2995        $s = $this->_rsasp1($m);
2996        $s = $this->_i2osp($s, $this->k);
2997
2998        // Output the signature S
2999
3000        return $s;
3001    }
3002
3003    /**
3004     * RSASSA-PKCS1-V1_5-VERIFY
3005     *
3006     * See {@link http://tools.ietf.org/html/rfc3447#section-8.2.2 RFC3447#section-8.2.2}.
3007     *
3008     * @access private
3009     * @param string $m
3010     * @param string $s
3011     * @return string
3012     */
3013    function _rsassa_pkcs1_v1_5_verify($m, $s)
3014    {
3015        // Length checking
3016
3017        if (strlen($s) != $this->k) {
3018            user_error('Invalid signature');
3019            return false;
3020        }
3021
3022        // RSA verification
3023
3024        $s = $this->_os2ip($s);
3025        $m2 = $this->_rsavp1($s);
3026        if ($m2 === false) {
3027            user_error('Invalid signature');
3028            return false;
3029        }
3030        $em = $this->_i2osp($m2, $this->k);
3031        if ($em === false) {
3032            user_error('Invalid signature');
3033            return false;
3034        }
3035
3036        // EMSA-PKCS1-v1_5 encoding
3037
3038        $em2 = $this->_emsa_pkcs1_v1_5_encode($m, $this->k);
3039        $em3 = $this->_emsa_pkcs1_v1_5_encode_without_null($m, $this->k);
3040
3041        if ($em2 === false && $em3 === false) {
3042            user_error('RSA modulus too short');
3043            return false;
3044        }
3045
3046        // Compare
3047
3048        return ($em2 !== false && $this->_equals($em, $em2)) ||
3049               ($em3 !== false && $this->_equals($em, $em3));
3050    }
3051
3052    /**
3053     * Set Encryption Mode
3054     *
3055     * Valid values include self::ENCRYPTION_OAEP and self::ENCRYPTION_PKCS1.
3056     *
3057     * @access public
3058     * @param int $mode
3059     */
3060    function setEncryptionMode($mode)
3061    {
3062        $this->encryptionMode = $mode;
3063    }
3064
3065    /**
3066     * Set Signature Mode
3067     *
3068     * Valid values include self::SIGNATURE_PSS and self::SIGNATURE_PKCS1
3069     *
3070     * @access public
3071     * @param int $mode
3072     */
3073    function setSignatureMode($mode)
3074    {
3075        $this->signatureMode = $mode;
3076    }
3077
3078    /**
3079     * Set public key comment.
3080     *
3081     * @access public
3082     * @param string $comment
3083     */
3084    function setComment($comment)
3085    {
3086        $this->comment = $comment;
3087    }
3088
3089    /**
3090     * Get public key comment.
3091     *
3092     * @access public
3093     * @return string
3094     */
3095    function getComment()
3096    {
3097        return $this->comment;
3098    }
3099
3100    /**
3101     * Encryption
3102     *
3103     * Both self::ENCRYPTION_OAEP and self::ENCRYPTION_PKCS1 both place limits on how long $plaintext can be.
3104     * If $plaintext exceeds those limits it will be broken up so that it does and the resultant ciphertext's will
3105     * be concatenated together.
3106     *
3107     * @see self::decrypt()
3108     * @access public
3109     * @param string $plaintext
3110     * @return string
3111     */
3112    function encrypt($plaintext)
3113    {
3114        switch ($this->encryptionMode) {
3115            case self::ENCRYPTION_NONE:
3116                $plaintext = str_split($plaintext, $this->k);
3117                $ciphertext = '';
3118                foreach ($plaintext as $m) {
3119                    $ciphertext.= $this->_raw_encrypt($m);
3120                }
3121                return $ciphertext;
3122            case self::ENCRYPTION_PKCS1:
3123                $length = $this->k - 11;
3124                if ($length <= 0) {
3125                    return false;
3126                }
3127
3128                $plaintext = str_split($plaintext, $length);
3129                $ciphertext = '';
3130                foreach ($plaintext as $m) {
3131                    $ciphertext.= $this->_rsaes_pkcs1_v1_5_encrypt($m);
3132                }
3133                return $ciphertext;
3134            //case self::ENCRYPTION_OAEP:
3135            default:
3136                $length = $this->k - 2 * $this->hLen - 2;
3137                if ($length <= 0) {
3138                    return false;
3139                }
3140
3141                $plaintext = str_split($plaintext, $length);
3142                $ciphertext = '';
3143                foreach ($plaintext as $m) {
3144                    $ciphertext.= $this->_rsaes_oaep_encrypt($m);
3145                }
3146                return $ciphertext;
3147        }
3148    }
3149
3150    /**
3151     * Decryption
3152     *
3153     * @see self::encrypt()
3154     * @access public
3155     * @param string $ciphertext
3156     * @return string
3157     */
3158    function decrypt($ciphertext)
3159    {
3160        if ($this->k <= 0) {
3161            return false;
3162        }
3163
3164        $ciphertext = str_split($ciphertext, $this->k);
3165        $ciphertext[count($ciphertext) - 1] = str_pad($ciphertext[count($ciphertext) - 1], $this->k, chr(0), STR_PAD_LEFT);
3166
3167        $plaintext = '';
3168
3169        switch ($this->encryptionMode) {
3170            case self::ENCRYPTION_NONE:
3171                $decrypt = '_raw_encrypt';
3172                break;
3173            case self::ENCRYPTION_PKCS1:
3174                $decrypt = '_rsaes_pkcs1_v1_5_decrypt';
3175                break;
3176            //case self::ENCRYPTION_OAEP:
3177            default:
3178                $decrypt = '_rsaes_oaep_decrypt';
3179        }
3180
3181        foreach ($ciphertext as $c) {
3182            $temp = $this->$decrypt($c);
3183            if ($temp === false) {
3184                return false;
3185            }
3186            $plaintext.= $temp;
3187        }
3188
3189        return $plaintext;
3190    }
3191
3192    /**
3193     * Create a signature
3194     *
3195     * @see self::verify()
3196     * @access public
3197     * @param string $message
3198     * @return string
3199     */
3200    function sign($message)
3201    {
3202        if (empty($this->modulus) || empty($this->exponent)) {
3203            return false;
3204        }
3205
3206        switch ($this->signatureMode) {
3207            case self::SIGNATURE_PKCS1:
3208                return $this->_rsassa_pkcs1_v1_5_sign($message);
3209            //case self::SIGNATURE_PSS:
3210            default:
3211                return $this->_rsassa_pss_sign($message);
3212        }
3213    }
3214
3215    /**
3216     * Verifies a signature
3217     *
3218     * @see self::sign()
3219     * @access public
3220     * @param string $message
3221     * @param string $signature
3222     * @return bool
3223     */
3224    function verify($message, $signature)
3225    {
3226        if (empty($this->modulus) || empty($this->exponent)) {
3227            return false;
3228        }
3229
3230        switch ($this->signatureMode) {
3231            case self::SIGNATURE_PKCS1:
3232                return $this->_rsassa_pkcs1_v1_5_verify($message, $signature);
3233            //case self::SIGNATURE_PSS:
3234            default:
3235                return $this->_rsassa_pss_verify($message, $signature);
3236        }
3237    }
3238
3239    /**
3240     * Extract raw BER from Base64 encoding
3241     *
3242     * @access private
3243     * @param string $str
3244     * @return string
3245     */
3246    function _extractBER($str)
3247    {
3248        /* X.509 certs are assumed to be base64 encoded but sometimes they'll have additional things in them
3249         * above and beyond the ceritificate.
3250         * ie. some may have the following preceding the -----BEGIN CERTIFICATE----- line:
3251         *
3252         * Bag Attributes
3253         *     localKeyID: 01 00 00 00
3254         * subject=/O=organization/OU=org unit/CN=common name
3255         * issuer=/O=organization/CN=common name
3256         */
3257        $temp = preg_replace('#.*?^-+[^-]+-+[\r\n ]*$#ms', '', $str, 1);
3258        // remove the -----BEGIN CERTIFICATE----- and -----END CERTIFICATE----- stuff
3259        $temp = preg_replace('#-+[^-]+-+#', '', $temp);
3260        // remove new lines
3261        $temp = str_replace(array("\r", "\n", ' '), '', $temp);
3262        $temp = preg_match('#^[a-zA-Z\d/+]*={0,2}$#', $temp) ? base64_decode($temp) : false;
3263        return $temp != false ? $temp : $str;
3264    }
3265}
3266