# ===================================================================
#
# Copyright (c) 2016, Legrandin <helderijs@gmail.com>
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in
#    the documentation and/or other materials provided with the
#    distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
# COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.
# ===================================================================

__all__ = ['generate', 'construct', 'import_key',
           'RsaKey', 'oid']

import binascii
import struct

from Crypto import Random
from Crypto.IO import PKCS8, PEM
from Crypto.Util.py3compat import tobytes, bord, tostr
from Crypto.Util.asn1 import DerSequence

from Crypto.Math.Numbers import Integer
from Crypto.Math.Primality import (test_probable_prime,
                                   generate_probable_prime, COMPOSITE)

from Crypto.PublicKey import (_expand_subject_public_key_info,
                              _create_subject_public_key_info,
                              _extract_subject_public_key_info)


class RsaKey(object):
    r"""Class defining an actual RSA key.
    Do not instantiate directly.
    Use :func:`generate`, :func:`construct` or :func:`import_key` instead.

    :ivar n: RSA modulus
    :vartype n: integer

    :ivar e: RSA public exponent
    :vartype e: integer

    :ivar d: RSA private exponent
    :vartype d: integer

    :ivar p: First factor of the RSA modulus
    :vartype p: integer

    :ivar q: Second factor of the RSA modulus
    :vartype q: integer

    :ivar u: Chinese remainder component (:math:`p^{-1} \text{mod } q`)
    :vartype q: integer
    """

    def __init__(self, **kwargs):
        """Build an RSA key.

        :Keywords:
          n : integer
            The modulus.
          e : integer
            The public exponent.
          d : integer
            The private exponent. Only required for private keys.
          p : integer
            The first factor of the modulus. Only required for private keys.
          q : integer
            The second factor of the modulus. Only required for private keys.
          u : integer
            The CRT coefficient (inverse of p modulo q). Only required for
            privta keys.
        """

        input_set = set(kwargs.keys())
        public_set = set(('n', 'e'))
        private_set = public_set | set(('p', 'q', 'd', 'u'))
        if input_set not in (private_set, public_set):
            raise ValueError("Some RSA components are missing")
        for component, value in kwargs.items():
            setattr(self, "_" + component, value)

    @property
    def n(self):
        return int(self._n)

    @property
    def e(self):
        return int(self._e)

    @property
    def d(self):
        if not self.has_private():
            raise AttributeError("No private exponent available for public keys")
        return int(self._d)

    @property
    def p(self):
        if not self.has_private():
            raise AttributeError("No CRT component 'p' available for public keys")
        return int(self._p)

    @property
    def q(self):
        if not self.has_private():
            raise AttributeError("No CRT component 'q' available for public keys")
        return int(self._q)

    @property
    def u(self):
        if not self.has_private():
            raise AttributeError("No CRT component 'u' available for public keys")
        return int(self._u)

    def size_in_bits(self):
        """Size of the RSA modulus in bits"""
        return self._n.size_in_bits()

    def size_in_bytes(self):
        """The minimal amount of bytes that can hold the RSA modulus"""
        return (self._n.size_in_bits() - 1) // 8 + 1

    def _encrypt(self, plaintext):
        if not 0 < plaintext < self._n:
            raise ValueError("Plaintext too large")
        return int(pow(Integer(plaintext), self._e, self._n))

    def _decrypt(self, ciphertext):
        if not 0 < ciphertext < self._n:
            raise ValueError("Ciphertext too large")
        if not self.has_private():
            raise TypeError("This is not a private key")

        # Blinded RSA decryption (to prevent timing attacks):
        # Step 1: Generate random secret blinding factor r,
        # such that 0 < r < n-1
        r = Integer.random_range(min_inclusive=1, max_exclusive=self._n)
        # Step 2: Compute c' = c * r**e mod n
        cp = Integer(ciphertext) * pow(r, self._e, self._n) % self._n
        # Step 3: Compute m' = c'**d mod n       (ordinary RSA decryption)
        m1 = pow(cp, self._d % (self._p - 1), self._p)
        m2 = pow(cp, self._d % (self._q - 1), self._q)
        h = m2 - m1
        while h < 0:
            h += self._q
        h = (h * self._u) % self._q
        mp = h * self._p + m1
        # Step 4: Compute m = m**(r-1) mod n
        result = (r.inverse(self._n) * mp) % self._n
        # Verify no faults occured
        if ciphertext != pow(result, self._e, self._n):
            raise ValueError("Fault detected in RSA decryption")
        return result

    def has_private(self):
        """Whether this is an RSA private key"""

        return hasattr(self, "_d")

    def can_encrypt(self):  # legacy
        return True

    def can_sign(self):     # legacy
        return True

    def publickey(self):
        """A matching RSA public key.

        Returns:
            a new :class:`RsaKey` object
        """
        return RsaKey(n=self._n, e=self._e)

    def __eq__(self, other):
        if self.has_private() != other.has_private():
            return False
        if self.n != other.n or self.e != other.e:
            return False
        if not self.has_private():
            return True
        return (self.d == other.d and
                self.q == other.q and
                self.p == other.p and
                self.u == other.u)

    def __ne__(self, other):
        return not (self == other)

    def __getstate__(self):
        # RSA key is not pickable
        from pickle import PicklingError
        raise PicklingError

    def __repr__(self):
        if self.has_private():
            extra = ", d=%d, p=%d, q=%d, u=%d" % (int(self._d), int(self._p),
                                                  int(self._q), int(self._u))
        else:
            extra = ""
        return "RsaKey(n=%d, e=%d%s)" % (int(self._n), int(self._e), extra)

    def __str__(self):
        if self.has_private():
            key_type = "Private"
        else:
            key_type = "Public"
        return "%s RSA key at 0x%X" % (key_type, id(self))

    def export_key(self, format='PEM', passphrase=None, pkcs=1,
                   protection=None, randfunc=None):
        """Export this RSA key.

        Args:
          format (string):
            The format to use for wrapping the key:

            - *'PEM'*. (*Default*) Text encoding, done according to `RFC1421`_/`RFC1423`_.
            - *'DER'*. Binary encoding.
            - *'OpenSSH'*. Textual encoding, done according to OpenSSH specification.
              Only suitable for public keys (not private keys).

          passphrase (string):
            (*For private keys only*) The pass phrase used for protecting the output.

          pkcs (integer):
            (*For private keys only*) The ASN.1 structure to use for
            serializing the key. Note that even in case of PEM
            encoding, there is an inner ASN.1 DER structure.

            With ``pkcs=1`` (*default*), the private key is encoded in a
            simple `PKCS#1`_ structure (``RSAPrivateKey``).

            With ``pkcs=8``, the private key is encoded in a `PKCS#8`_ structure
            (``PrivateKeyInfo``).

            .. note::
                This parameter is ignored for a public key.
                For DER and PEM, an ASN.1 DER ``SubjectPublicKeyInfo``
                structure is always used.

          protection (string):
            (*For private keys only*)
            The encryption scheme to use for protecting the private key.

            If ``None`` (default), the behavior depends on :attr:`format`:

            - For *'DER'*, the *PBKDF2WithHMAC-SHA1AndDES-EDE3-CBC*
              scheme is used. The following operations are performed:

                1. A 16 byte Triple DES key is derived from the passphrase
                   using :func:`Crypto.Protocol.KDF.PBKDF2` with 8 bytes salt,
                   and 1 000 iterations of :mod:`Crypto.Hash.HMAC`.
                2. The private key is encrypted using CBC.
                3. The encrypted key is encoded according to PKCS#8.

            - For *'PEM'*, the obsolete PEM encryption scheme is used.
              It is based on MD5 for key derivation, and Triple DES for encryption.

            Specifying a value for :attr:`protection` is only meaningful for PKCS#8
            (that is, ``pkcs=8``) and only if a pass phrase is present too.

            The supported schemes for PKCS#8 are listed in the
            :mod:`Crypto.IO.PKCS8` module (see :attr:`wrap_algo` parameter).

          randfunc (callable):
            A function that provides random bytes. Only used for PEM encoding.
            The default is :func:`Crypto.Random.get_random_bytes`.

        Returns:
          byte string: the encoded key

        Raises:
          ValueError:when the format is unknown or when you try to encrypt a private
            key with *DER* format and PKCS#1.

        .. warning::
            If you don't provide a pass phrase, the private key will be
            exported in the clear!

        .. _RFC1421:    http://www.ietf.org/rfc/rfc1421.txt
        .. _RFC1423:    http://www.ietf.org/rfc/rfc1423.txt
        .. _`PKCS#1`:   http://www.ietf.org/rfc/rfc3447.txt
        .. _`PKCS#8`:   http://www.ietf.org/rfc/rfc5208.txt
        """

        if passphrase is not None:
            passphrase = tobytes(passphrase)

        if randfunc is None:
            randfunc = Random.get_random_bytes

        if format == 'OpenSSH':
            e_bytes, n_bytes = [x.to_bytes() for x in (self._e, self._n)]
            if bord(e_bytes[0]) & 0x80:
                e_bytes = b'\x00' + e_bytes
            if bord(n_bytes[0]) & 0x80:
                n_bytes = b'\x00' + n_bytes
            keyparts = [b'ssh-rsa', e_bytes, n_bytes]
            keystring = b''.join([struct.pack(">I", len(kp)) + kp for kp in keyparts])
            return b'ssh-rsa ' + binascii.b2a_base64(keystring)[:-1]

        # DER format is always used, even in case of PEM, which simply
        # encodes it into BASE64.
        if self.has_private():
            binary_key = DerSequence([0,
                                      self.n,
                                      self.e,
                                      self.d,
                                      self.p,
                                      self.q,
                                      self.d % (self.p-1),
                                      self.d % (self.q-1),
                                      Integer(self.q).inverse(self.p)
                                      ]).encode()
            if pkcs == 1:
                key_type = 'RSA PRIVATE KEY'
                if format == 'DER' and passphrase:
                    raise ValueError("PKCS#1 private key cannot be encrypted")
            else:  # PKCS#8
                if format == 'PEM' and protection is None:
                    key_type = 'PRIVATE KEY'
                    binary_key = PKCS8.wrap(binary_key, oid, None)
                else:
                    key_type = 'ENCRYPTED PRIVATE KEY'
                    if not protection:
                        protection = 'PBKDF2WithHMAC-SHA1AndDES-EDE3-CBC'