#
#  Util/asn1.py : Minimal support for ASN.1 DER binary encoding.
#
# ===================================================================
# The contents of this file are dedicated to the public domain.  To
# the extent that dedication to the public domain is not available,
# everyone is granted a worldwide, perpetual, royalty-free,
# non-exclusive license to exercise all rights associated with the
# contents of this file for any purpose whatsoever.
# No rights are reserved.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
# ===================================================================

from __future__ import annotations

import struct
from collections.abc import Iterable, Iterator, Sequence
from typing import Any, Optional, TypeVar, Union, cast

from Crypto.Util.number import bytes_to_long, long_to_bytes

_DerObjectT = TypeVar("_DerObjectT", bound="DerObject")

DerSetElement = Union[bytes, int]

__all__ = [
    "ContextTag",
    "DerObject",
    "DerInteger",
    "DerBoolean",
    "DerOctetString",
    "DerNull",
    "DerSequence",
    "DerObjectId",
    "DerBitString",
    "DerSetOf",
]

# Useful references:
# - https://luca.ntop.org/Teaching/Appunti/asn1.html
# - https://letsencrypt.org/docs/a-warm-welcome-to-asn1-and-der/
# - https://www.zytrax.com/tech/survival/asn1.html
# - https://www.oss.com/asn1/resources/books-whitepapers-pubs/larmouth-asn1-book.pdf
# - https://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf
# - https://misc.daniel-marschall.de/asn.1/oid-converter/online.php


def _is_number(x, only_non_negative=False):
    test = 0
    try:
        test = x + test
    except TypeError:
        return False
    return not only_non_negative or x >= 0


class BytesIO_EOF:
    """This class differs from BytesIO in that a ValueError exception is
    raised whenever EOF is reached."""

    def __init__(self, initial_bytes: bytes) -> None:
        self._buffer = initial_bytes
        self._index = 0
        self._bookmark: Optional[int] = None

    def set_bookmark(self) -> None:
        self._bookmark = self._index

    def data_since_bookmark(self) -> bytes:
        assert self._bookmark is not None
        return self._buffer[self._bookmark : self._index]

    def remaining_data(self) -> int:
        return len(self._buffer) - self._index

    def read(self, length: int) -> bytes:
        new_index = self._index + length
        if new_index > len(self._buffer):
            raise ValueError(
                "Not enough data for DER decoding: expected %d bytes and found %d"
                % (new_index, len(self._buffer))
            )

        result = self._buffer[self._index : new_index]
        self._index = new_index
        return result

    def read_byte(self) -> int:
        return self.read(1)[0]


class ContextTag:
    """The type of a DER element with a context-specific tag ``[number]``,
    as returned by :meth:`DerSequence.item_types`.

    The tag can be IMPLICIT or EXPLICIT: the encoding does not tell them apart,
    nor the actual type of the element.
    Two objects are equal if they have the same number.

    Args:
      number (integer):
        The number of the tag (0 to 30).
    """

    def __init__(self, number: int) -> None:
        if not (isinstance(number, int) and 0 <= number < 0x1F):
            raise ValueError("Wrong DER tag number")
        self.number = number

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, ContextTag):
            return NotImplemented
        return self.number == other.number

    def __hash__(self) -> int:
        return hash((ContextTag, self.number))

    def __repr__(self) -> str:
        return "ContextTag(%d)" % self.number


class DerObject:
    """Base class for defining a single DER object.

    This class should never be directly instantiated.
    """

    def __init__(
        self,
        asn1Id: Optional[Union[int, bytes]] = None,
        payload: bytes = b"",
        implicit: Optional[Union[int, bytes]] = None,
        constructed: bool = False,
        explicit: Optional[Union[int, bytes]] = None,
    ) -> None:
        """Initialize the DER object according to a specific ASN.1 type.

        :Parameters:
          asn1Id : integer or byte
            The universal DER tag number for this object
            (e.g. 0x10 for a SEQUENCE).
            If None, the tag is not known yet.

          payload : byte string
            The initial payload of the object (that it,
            the content octets).
            If not specified, the payload is empty.

          implicit : integer or byte
            The IMPLICIT tag number (< 0x1F) to use for the encoded object.
            It overrides the universal tag *asn1Id*.
            It cannot be combined with the ``explicit`` parameter.
            By default, there is no IMPLICIT tag.

          constructed : bool
            True when the ASN.1 type is *constructed*.
            False when it is *primitive* (default).

          explicit : integer or byte
            The EXPLICIT tag number (< 0x1F) to use for the encoded object.
            It cannot be combined with the ``implicit`` parameter.
            By default, there is no EXPLICIT tag.
        """

        self._tag_octet: Optional[int]
        if asn1Id is None:
            # The tag octet will be read in with ``decode``
            self._tag_octet = None
            return
        asn1Id = self._convertTag(asn1Id)

        self.payload = payload

        # In a BER/DER identifier octet:
        # * bits 4-0 contain the tag value
        # * bit 5 is set if the type is 'constructed'
        #   and unset if 'primitive'
        # * bits 7-6 depend on the encoding class
        #
        # Class        | Bit 7, Bit 6
        # ----------------------------------
        # universal    |   0      0
        # application  |   0      1
        # context-spec |   1      0 (default for IMPLICIT/EXPLICIT)
        # private      |   1      1
        #

        constructed_bit = 0x20 if constructed else 0x00

        if None not in (explicit, implicit):
            raise ValueError("Explicit and implicit tags are mutually exclusive")

        if implicit is not None:
            # IMPLICIT tag overrides asn1Id
            self._tag_octet = 0x80 | constructed_bit | self._convertTag(implicit)
        elif explicit is not None:
            # 'constructed bit' is always asserted for an EXPLICIT tag
            self._tag_octet = 0x80 | 0x20 | self._convertTag(explicit)
            self._inner_tag_octet = constructed_bit | asn1Id
        else:
            # Neither IMPLICIT nor EXPLICIT
            self._tag_octet = constructed_bit | asn1Id

    def _convertTag(self, tag: Union[int, bytes]) -> int:
        """Check if *tag* is a real DER tag (5 bits).
        Convert it from a character to number if necessary.
        """
        if isinstance(tag, (bytes, bytearray)) and len(tag) == 1:
            tag = tag[0]
        # Ensure that tag is a low tag
        if not (isinstance(tag, int) and 0 <= tag < 0x1F):
            raise ValueError("Wrong DER tag")
        return tag

    @staticmethod
    def _definite_form(length: int) -> bytes:
        """Build length octets according to BER/DER
        definite form.
        """
        if length > 127:
            encoding = long_to_bytes(length)
            return bytes([len(encoding) + 128]) + encoding
        return bytes([length])

    def encode(self) -> bytes:
        """Return this DER element, fully encoded as a binary byte string."""

        # Concatenate identifier octets, length octets,
        # and contents octets

        output_payload = self.payload

        # In case of an EXTERNAL tag, first encode the inner
        # element.
        if hasattr(self, "_inner_tag_octet"):
            output_payload = (
                bytes([self._inner_tag_octet]) + self._definite_form(len(self.payload)) + self.payload
            )

        assert self._tag_octet is not None
        return bytes([self._tag_octet]) + self._definite_form(len(output_payload)) + output_payload

    def _decodeLen(self, s: BytesIO_EOF) -> int:
        """Decode DER length octets from a file."""

        length = s.read_byte()

        if length > 127:
            encoded_length = s.read(length & 0x7F)
            if encoded_length[0] == 0:
                raise ValueError("Invalid DER: length has leading zero")
            length = bytes_to_long(encoded_length)
            if length <= 127:
                raise ValueError("Invalid DER: length in long form but smaller than 128")

        return length

    def decode(self: _DerObjectT, der_encoded: bytes, strict: bool = False) -> _DerObjectT:
        """Decode a complete DER element, and re-initializes this
        object with it.

        Args:
          der_encoded (byte string): A complete DER element.

        Raises:
          ValueError: in case of parsing errors.
        """

        if not isinstance(der_encoded, bytes):
            raise ValueError("Input is not a byte string")

        s = BytesIO_EOF(der_encoded)
        self._decodeFromStream(s, strict)

        # There shouldn't be other bytes left
        if s.remaining_data() > 0:
            raise ValueError("Unexpected extra data after the DER structure")

        return self

    def _decodeFromStream(self, s: BytesIO_EOF, strict: bool) -> None:
        """Decode a complete DER element from a file."""

        idOctet = s.read_byte()
        if self._tag_octet is not None:
            if idOctet != self._tag_octet:
                raise ValueError("Unexpected DER tag")
        else:
            self._tag_octet = idOctet
        length = self._decodeLen(s)
        self.payload = s.read(length)

        # In case of an EXTERNAL tag, further decode the inner
        # element.
        if hasattr(self, "_inner_tag_octet"):
            p = BytesIO_EOF(self.payload)
            inner_octet = p.read_byte()
            if inner_octet != self._inner_tag_octet:
                raise ValueError("Unexpected internal DER tag")
            length = self._decodeLen(p)
            self.payload = p.read(length)

            # There shouldn't be other bytes left
            if p.remaining_data() > 0:
                raise ValueError("Unexpected extra data after the DER structure")


class DerInteger(DerObject):
    """Class to model a DER INTEGER.

    An example of encoding is::

      >>> from Crypto.Util.asn1 import DerInteger
      >>> from binascii import hexlify, unhexlify
      >>> int_der = DerInteger(9)
      >>> print hexlify(int_der.encode())

    which will show ``020109``, the DER encoding of 9.

    And for decoding::

      >>> s = unhexlify(b'020109')
      >>> try:
      >>>   int_der = DerInteger()
      >>>   int_der.decode(s)
      >>>   print int_der.value
      >>> except ValueError:
      >>>   print "Not a valid DER INTEGER"

    the output will be ``9``.

    :ivar value: The integer value
    :vartype value: integer
    """

    def __init__(
        self,
        value: int = 0,
        implicit: Optional[Union[int, bytes]] = None,
        explicit: Optional[Union[int, bytes]] = None,
    ) -> None:
        """Initialize the DER object as an INTEGER.

        :Parameters:
          value : integer
            The value of the integer.

          implicit : integer
            The IMPLICIT tag to use for the encoded object.
            It overrides the universal tag for INTEGER (2).
        """

        DerObject.__init__(self, 0x02, b"", implicit, False, explicit)
        self.value = value  # The integer value

    def encode(self) -> bytes:
        """Return the DER INTEGER, fully encoded as a
        binary string."""

        number = self.value
        self.payload = b""
        while True:
            self.payload = bytes([int(number & 255)]) + self.payload
            if 128 <= number <= 255:
                self.payload = bytes([0x00]) + self.payload
            if -128 <= number <= 255:
                break
            number >>= 8
        return DerObject.encode(self)

    def decode(self, der_encoded: bytes, strict: bool = False) -> DerInteger:
        """Decode a DER-encoded INTEGER, and re-initializes this
        object with it.

        Args:
          der_encoded (byte string): A complete INTEGER DER element.

        Raises:
          ValueError: in case of parsing errors.
        """

        return DerObject.decode(self, der_encoded, strict=strict)

    def _decodeFromStream(self, s: BytesIO_EOF, strict: bool) -> None:
        """Decode a complete DER INTEGER from a file."""

        # Fill up self.payload
        DerObject._decodeFromStream(self, s, strict)

        if strict:
            if len(self.payload) == 0:
                raise ValueError("Invalid encoding for DER INTEGER: empty payload")
            if len(self.payload) >= 2 and struct.unpack(">H", self.payload[:2])[0] < 0x80:
                raise ValueError("Invalid encoding for DER INTEGER: leading zero")

        # Derive self.value from self.payload
        self.value = 0
        bits = 1
        for i in self.payload:
            self.value *= 256
            self.value += i
            bits <<= 8
        if self.payload and self.payload[0] & 0x80:
            self.value -= bits


class DerBoolean(DerObject):
    """Class to model a DER-encoded BOOLEAN.

    An example of encoding is::

    >>> from Crypto.Util.asn1 import DerBoolean
    >>> bool_der = DerBoolean(True)
    >>> print(bool_der.encode().hex())

    which will show ``0101ff``, the DER encoding of True.

    And for decoding::

    >>> s = bytes.fromhex('0101ff')
    >>> try:
    >>>   bool_der = DerBoolean()
    >>>   bool_der.decode(s)
    >>>   print(bool_der.value)
    >>> except ValueError:
    >>>   print "Not a valid DER BOOLEAN"

    the output will be ``True``.

    :ivar value: The boolean value
    :vartype value: boolean
    """

    def __init__(
        self,
        value: bool = False,
        implicit: Optional[Union[int, bytes]] = None,
        explicit: Optional[Union[int, bytes]] = None,
    ) -> None:
        """Initialize the DER object as a BOOLEAN.

        Args:
          value (boolean):
            The value of the boolean. Default is False.

          implicit (integer or byte):
            The IMPLICIT tag number (< 0x1F) to use for the encoded object.
            It overrides the universal tag for BOOLEAN (1).
            It cannot be combined with the ``explicit`` parameter.
            By default, there is no IMPLICIT tag.

          explicit (integer or byte):
            The EXPLICIT tag number (< 0x1F) to use for the encoded object.
            It cannot be combined with the ``implicit`` parameter.
            By default, there is no EXPLICIT tag.
        """

        DerObject.__init__(self, 0x01, b"", implicit, False, explicit)
        self.value = value  # The boolean value

    def encode(self) -> bytes:
        """Return the DER BOOLEAN, fully encoded as a binary string."""

        self.payload = b"\xff" if self.value else b"\x00"
        return DerObject.encode(self)

    def decode(self, der_encoded: bytes, strict: bool = False) -> DerBoolean:
        """Decode a DER-encoded BOOLEAN, and re-initializes this object with it.

        Args:
            der_encoded (byte string): A DER-encoded BOOLEAN.

        Raises:
            ValueError: in case of parsing errors.
        """

        return DerObject.decode(self, der_encoded, strict)

    def _decodeFromStream(self, s, strict):
        """Decode a DER-encoded BOOLEAN from a file."""

        # Fill up self.payload
        DerObject._decodeFromStream(self, s, strict)

        if len(self.payload) != 1:
            raise ValueError("Invalid encoding for DER BOOLEAN: payload is not 1 byte")

        if self.payload[0] == 0:
            self.value = False
        elif self.payload[0] == 0xFF:
            self.value = True
        else:
            raise ValueError("Invalid payload for DER BOOLEAN")


class DerSequence(DerObject):
    """Class to model a DER SEQUENCE.

    This object behaves like a dynamic Python sequence.

    Sub-elements that are INTEGERs behave like Python integers.

    Any other sub-element is a binary string encoded as a complete DER
    sub-element (TLV).

    An example of encoding is:

      >>> from Crypto.Util.asn1 import DerSequence, DerInteger
      >>> from binascii import hexlify, unhexlify
      >>> obj_der = unhexlify('070102')
      >>> seq_der = DerSequence([4])
      >>> seq_der.append(9)
      >>> seq_der.append(obj_der.encode())
      >>> print hexlify(seq_der.encode())

    which will show ``3009020104020109070102``, the DER encoding of the
    sequence containing ``4``, ``9``, and the object with payload ``02``.

    For decoding:

      >>> s = unhexlify(b'3009020104020109070102')
      >>> try:
      >>>   seq_der = DerSequence()
      >>>   seq_der.decode(s)
      >>>   print len(seq_der)
      >>>   print seq_der[0]
      >>>   print seq_der[:]
      >>> except ValueError:
      >>>   print "Not a valid DER SEQUENCE"

    the output will be::

      3
      4
      [4, 9, b'\x07\x01\x02']

    """

    def __init__(
        self,
        startSeq: Optional[Sequence[Union[int, bytes, DerObject]]] = None,
        implicit: Optional[int] = None,
        explicit: Optional[int] = None,
    ) -> None:
        """Initialize the DER object as a SEQUENCE.

        :Parameters:
          startSeq : Python sequence
            A sequence whose element are either integers or
            other DER objects.

          implicit : integer or byte
            The IMPLICIT tag number (< 0x1F) to use for the encoded object.
            It overrides the universal tag for SEQUENCE (16).
            It cannot be combined with the ``explicit`` parameter.
            By default, there is no IMPLICIT tag.

          explicit : integer or byte
            The EXPLICIT tag number (< 0x1F) to use for the encoded object.
            It cannot be combined with the ``implicit`` parameter.
            By default, there is no EXPLICIT tag.
        """

        DerObject.__init__(self, 0x10, b"", implicit, True, explicit)
        self._seq: list[Any]
        if startSeq is None:
            self._seq = []
        else:
            self._seq = cast(list[Any], startSeq)

    # A few methods to make it behave like a python sequence

    def __delitem__(self, n: Union[int, slice]) -> None:
        del self._seq[n]

    def __getitem__(self, n: Union[int, slice]) -> Any:
        return self._seq[n]

    def __setitem__(self, key: int, value: Union[int, bytes, DerObject]) -> None:
        self._seq[key] = value

    def __len__(self) -> int:
        return len(self._seq)

    def __iadd__(self, item: Union[int, bytes, DerObject]) -> DerSequence:
        self._seq.append(item)
        return self

    def append(self, item: Union[int, bytes, DerObject]) -> DerSequence:
        self._seq.append(item)
        return self

    def insert(self, index: int, item: Union[int, bytes, DerObject]) -> DerSequence:
        self._seq.insert(index, item)
        return self

    def hasInts(self, only_non_negative: bool = True) -> int:
        """Return the number of items in this sequence that are
        integers.

        Args:
          only_non_negative (boolean):
            If ``True``, negative integers are not counted in.
        """

        items = [x for x in self._seq if _is_number(x, only_non_negative)]
        return len(items)

    def hasOnlyInts(self, only_non_negative: bool = True) -> bool:
        """Return ``True`` if all items in this sequence are integers
        or non-negative integers.

        This function returns False is the sequence is empty,
        or at least one member is not an integer.

        Args:
          only_non_negative (boolean):
            If ``True``, the presence of negative integers
            causes the method to return ``False``."""
        return bool(self._seq) and self.hasInts(only_non_negative) == len(self._seq)

    def item_types(self) -> list[Union[type[DerObject], ContextTag]]:
        """Return the type of each item in this sequence, from its tag.

        The type of an item is:

        * the class for the universal types of this module:
          :class:`DerBoolean`, :class:`DerInteger`, :class:`DerBitString`,
          :class:`DerOctetString`, :class:`DerNull`, :class:`DerObjectId`,
          :class:`DerSequence` and :class:`DerSetOf`;
        * a :class:`ContextTag` for an item with a context-specific tag
          (IMPLICIT or EXPLICIT), since the tag hides the actual type;
        * :class:`DerObject` for anything else.

        Use it to tell apart the items after a decoding, without decoding them:

        >>> from Crypto.Util.asn1 import DerSequence, DerInteger, DerOctetString, ContextTag
        >>> from binascii import unhexlify
        >>> seq_der = DerSequence().decode(unhexlify('30080201040401028100'))
        >>> seq_der.item_types() == [DerInteger, DerOctetString, ContextTag(1)]
        True
        """

        result: list[Union[type[DerObject], ContextTag]] = []
        for item in self._seq:
            if _is_number(item):
                tag_octet = 0x02
            elif isinstance(item, DerObject) and item._tag_octet is not None:
                tag_octet = item._tag_octet
            elif isinstance(item, (bytes, bytearray)) and len(item) > 0:
                tag_octet = item[0]
            else:
                raise ValueError("Item %r is not a DER element" % (item,))

            tag_class, number = tag_octet & 0xC0, tag_octet & 0x1F
            if tag_class == 0x00:
                result.append(_UNIVERSAL_TYPES.get(tag_octet, DerObject))
            elif tag_class == 0x80 and number != 0x1F:
                result.append(ContextTag(number))
            else:
                result.append(DerObject)
        return result

    def encode(self) -> bytes:
        """Return this DER SEQUENCE, fully encoded as a
        binary string.

        Raises:
          ValueError: if some elements in the sequence are neither integers
                      nor byte strings.
        """
        self.payload = b""
        for item in self._seq:
            if isinstance(item, bytes):
                self.payload += item
            elif _is_number(item):
                self.payload += DerInteger(item).encode()
            else:
                self.payload += item.encode()
        return DerObject.encode(self)

    def decode(
        self,
        der_encoded: bytes,
        strict: bool = False,
        nr_elements: Optional[Union[int, Iterable[int]]] = None,
        only_ints_expected: bool = False,
    ) -> DerSequence:
        """Decode a complete DER SEQUENCE, and re-initializes this
        object with it.

        Args:
          der_encoded (byte string):
            A complete SEQUENCE DER element.
          nr_elements (None or integer or list of integers):
            The number of members the SEQUENCE can have
          only_ints_expected (boolean):
            Whether the SEQUENCE is expected to contain only integers.
          strict (boolean):
            Whether decoding must check for strict DER compliancy.

        Raises:
          ValueError: in case of parsing errors.

        DER INTEGERs are decoded into Python integers. Any other DER
        element is not decoded. Its validity is not checked.
        """

        self._nr_elements = nr_elements
        result = DerObject.decode(self, der_encoded, strict=strict)

        if only_ints_expected and not self.hasOnlyInts():
            raise ValueError("Some members are not INTEGERs")

        return result

    def _decodeFromStream(self, s: BytesIO_EOF, strict: bool) -> None:
        """Decode a complete DER SEQUENCE from a file."""

        self._seq = []

        # Fill up self.payload
        DerObject._decodeFromStream(self, s, strict)

        # Add one item at a time to self.seq, by scanning self.payload
        p = BytesIO_EOF(self.payload)
        while p.remaining_data() > 0:
            p.set_bookmark()

            der = DerObject()
            der._decodeFromStream(p, strict)

            # Parse INTEGERs differently
            if der._tag_octet != 0x02:
                self._seq.append(p.data_since_bookmark())
            else:
                derInt = DerInteger()
                data = p.data_since_bookmark()
                derInt.decode(data, strict=strict)
                self._seq.append(derInt.value)

        ok = True
        if isinstance(self._nr_elements, int):
            ok = len(self._seq) == self._nr_elements
        elif self._nr_elements is not None:
            ok = len(self._seq) in self._nr_elements

        if not ok:
            raise ValueError("Unexpected number of members (%d) in the sequence" % len(self._seq))


class DerOctetString(DerObject):
    """Class to model a DER OCTET STRING.

    An example of encoding is:

    >>> from Crypto.Util.asn1 import DerOctetString
    >>> from binascii import hexlify, unhexlify
    >>> os_der = DerOctetString(b'\\xaa')
    >>> os_der.payload += b'\\xbb'
    >>> print hexlify(os_der.encode())

    which will show ``0402aabb``, the DER encoding for the byte string
    ``b'\\xAA\\xBB'``.

    For decoding:

    >>> s = unhexlify(b'0402aabb')
    >>> try:
    >>>   os_der = DerOctetString()
    >>>   os_der.decode(s)
    >>>   print hexlify(os_der.payload)
    >>> except ValueError:
    >>>   print "Not a valid DER OCTET STRING"

    the output will be ``aabb``.

    :ivar payload: The content of the string
    :vartype payload: byte string
    """

    def __init__(self, value: bytes = b"", implicit: Optional[Union[int, bytes]] = None) -> None:
        """Initialize the DER object as an OCTET STRING.

        :Parameters:
          value : byte string
            The initial payload of the object.
            If not specified, the payload is empty.

          implicit : integer
            The IMPLICIT tag to use for the encoded object.
            It overrides the universal tag for OCTET STRING (4).
        """
        DerObject.__init__(self, 0x04, value, implicit, False)


class DerNull(DerObject):
    """Class to model a DER NULL element."""

    def __init__(self) -> None:
        """Initialize the DER object as a NULL."""

        DerObject.__init__(self, 0x05, b"", None, False)


class DerObjectId(DerObject):
    """Class to model a DER OBJECT ID.

    An example of encoding is:

    >>> from Crypto.Util.asn1 import DerObjectId
    >>> from binascii import hexlify, unhexlify
    >>> oid_der = DerObjectId("1.2")
    >>> oid_der.value += ".840.113549.1.1.1"
    >>> print hexlify(oid_der.encode())

    which will show ``06092a864886f70d010101``, the DER encoding for the
    RSA Object Identifier ``1.2.840.113549.1.1.1``.

    For decoding:

    >>> s = unhexlify(b'06092a864886f70d010101')
    >>> try:
    >>>   oid_der = DerObjectId()
    >>>   oid_der.decode(s)
    >>>   print oid_der.value
    >>> except ValueError:
    >>>   print "Not a valid DER OBJECT ID"

    the output will be ``1.2.840.113549.1.1.1``.

    :ivar value: The Object ID (OID), a dot separated list of integers
    :vartype value: string
    """

    def __init__(
        self,
        value: str = "",
        implicit: Optional[Union[int, bytes]] = None,
        explicit: Optional[Union[int, bytes]] = None,
    ) -> None:
        """Initialize the DER object as an OBJECT ID.

        :Parameters:
          value : string
            The initial Object Identifier (e.g. "1.2.0.0.6.2").
          implicit : integer
            The IMPLICIT tag to use for the encoded object.
            It overrides the universal tag for OBJECT ID (6).
          explicit : integer
            The EXPLICIT tag to use for the encoded object.
        """
        DerObject.__init__(self, 0x06, b"", implicit, False, explicit)
        self.value = value

    def encode(self) -> bytes:
        """Return the DER OBJECT ID, fully encoded as a
        binary string."""

        comps = [int(x) for x in self.value.split(".")]

        if len(comps) < 2:
            raise ValueError("Not a valid Object Identifier string")
        if comps[0] > 2:
            raise ValueError("First component must be 0, 1 or 2")
        if comps[0] < 2 and comps[1] > 39:
            raise ValueError("Second component must be 39 at most")

        subcomps = [40 * comps[0] + comps[1]] + comps[2:]

        encoding = []
        for v in reversed(subcomps):
            encoding.append(v & 0x7F)
            v >>= 7
            while v:
                encoding.append((v & 0x7F) | 0x80)
                v >>= 7

        self.payload = b"".join([bytes([x]) for x in reversed(encoding)])
        return DerObject.encode(self)

    def decode(self, der_encoded: bytes, strict: bool = False) -> DerObjectId:
        """Decode a complete DER OBJECT ID, and re-initializes this
        object with it.

        Args:
            der_encoded (byte string):
                A complete DER OBJECT ID.
            strict (boolean):
                Whether decoding must check for strict DER compliancy.

        Raises:
            ValueError: in case of parsing errors.
        """

        return DerObject.decode(self, der_encoded, strict)

    def _decodeFromStream(self, s, strict):
        """Decode a complete DER OBJECT ID from a file."""

        # Fill up self.payload
        DerObject._decodeFromStream(self, s, strict)

        # Derive self.value from self.payload
        p = BytesIO_EOF(self.payload)

        # Each subidentifier is a base-128 big-endian number, where all octets
        # but the last have bit 8 set. As per X.690 8.19.2, the leading octet
        # cannot be 0x80 (padding) and that holds for BER too.
        subcomps = []
        v = 0
        in_subcomp = False
        while p.remaining_data():
            c = p.read_byte()
            if c == 0x80 and not in_subcomp:
                raise ValueError("Invalid OID: subidentifier with leading 0x80")
            v = (v << 7) + (c & 0x7F)
            in_subcomp = bool(c & 0x80)
            if not in_subcomp:
                subcomps.append(v)
                v = 0

        if in_subcomp:
            raise ValueError("Invalid OID: truncated subidentifier")

        if len(subcomps) == 0:
            raise ValueError("Empty payload")

        if subcomps[0] < 40:
            subcomps[:1] = [0, subcomps[0]]
        elif subcomps[0] < 80:
            subcomps[:1] = [1, subcomps[0] - 40]
        else:
            subcomps[:1] = [2, subcomps[0] - 80]

        self.value = ".".join([str(x) for x in subcomps])


class DerBitString(DerObject):
    """Class to model a DER BIT STRING.

    An example of encoding is:

    >>> from Crypto.Util.asn1 import DerBitString
    >>> bs_der = DerBitString(b'\\xAA')
    >>> bs_der.value += b'\\xBB'
    >>> print(bs_der.encode().hex())

    which will show ``030300aabb``, the DER encoding for the bit string
    ``b'\\xAA\\xBB'``.

    For decoding:

    >>> s = bytes.fromhex('030300aabb')
    >>> try:
    >>>   bs_der = DerBitString()
    >>>   bs_der.decode(s)
    >>>   print(bs_der.value.hex())
    >>> except ValueError:
    >>>   print "Not a valid DER BIT STRING"

    the output will be ``aabb``.

    :ivar value: The content of the string
    :vartype value: byte string
    """

    def __init__(
        self,
        value: Union[bytes, DerObject] = b"",
        implicit: Optional[Union[int, bytes]] = None,
        explicit: Optional[Union[int, bytes]] = None,
    ) -> None:
        """Initialize the DER object as a BIT STRING.

        :Parameters:
          value : byte string or DER object
            The initial, packed bit string.
            If not specified, the bit string is empty.
          implicit : integer
            The IMPLICIT tag to use for the encoded object.
            It overrides the universal tag for BIT STRING (3).
          explicit : integer
            The EXPLICIT tag to use for the encoded object.
        """
        DerObject.__init__(self, 0x03, b"", implicit, False, explicit)

        # The bitstring value (packed)
        self.value: bytes
        if isinstance(value, DerObject):
            self.value = value.encode()
        else:
            self.value = value

    def encode(self) -> bytes:
        """Return the DER BIT STRING, fully encoded as a
        byte string."""

        # Add padding count byte
        self.payload = b"\x00" + self.value
        return DerObject.encode(self)

    def decode(self, der_encoded: bytes, strict: bool = False) -> DerBitString:
        """Decode a complete DER BIT STRING, and re-initializes this
        object with it.

        Args:
            der_encoded (byte string): a complete DER BIT STRING.
            strict (boolean):
                Whether decoding must check for strict DER compliancy.

        Raises:
            ValueError: in case of parsing errors.
        """

        return DerObject.decode(self, der_encoded, strict)

    def _decodeFromStream(self, s, strict):
        """Decode a complete DER BIT STRING DER from a file."""

        # Fill-up self.payload
        DerObject._decodeFromStream(self, s, strict)

        if self.payload and self.payload[0] != 0:
            raise ValueError("Not a valid BIT STRING")

        # Fill-up self.value
        self.value = b""
        # Remove padding count byte
        if self.payload:
            self.value = self.payload[1:]


class DerSetOf(DerObject):
    """Class to model a DER SET OF.

    An example of encoding is:

    >>> from Crypto.Util.asn1 import DerBitString
    >>> from binascii import hexlify, unhexlify
    >>> so_der = DerSetOf([4,5])
    >>> so_der.add(6)
    >>> print hexlify(so_der.encode())

    which will show ``3109020104020105020106``, the DER encoding
    of a SET OF with items 4,5, and 6.

    For decoding:

    >>> s = unhexlify(b'3109020104020105020106')
    >>> try:
    >>>   so_der = DerSetOf()
    >>>   so_der.decode(s)
    >>>   print [x for x in so_der]
    >>> except ValueError:
    >>>   print "Not a valid DER SET OF"

    the output will be ``[4, 5, 6]``.
    """

    def __init__(
        self, startSet: Optional[Iterable[DerSetElement]] = None, implicit: Optional[Union[int, bytes]] = None
    ) -> None:
        """Initialize the DER object as a SET OF.

        :Parameters:
          startSet : container
            The initial set of integers or DER encoded objects.
          implicit : integer
            The IMPLICIT tag to use for the encoded object.
            It overrides the universal tag for SET OF (17).
        """
        DerObject.__init__(self, 0x11, b"", implicit, True)
        self._seq: list[Any] = []

        # All elements must be of the same type (and therefore have the
        # same leading octet)
        self._elemOctet: Optional[int] = None

        if startSet:
            for e in startSet:
                self.add(e)

    def __getitem__(self, n: int) -> DerSetElement:
        return self._seq[n]

    def __iter__(self) -> Iterator[DerSetElement]:
        return iter(self._seq)

    def __len__(self) -> int:
        return len(self._seq)

    def add(self, elem: DerSetElement) -> None:
        """Add an element to the set.

        Args:
            elem (byte string or integer):
              An element of the same type of objects already in the set.
              It can be an integer or a DER encoded object.
        """

        eo: Optional[int]
        if _is_number(elem):
            eo = 0x02
        elif isinstance(elem, DerObject):
            eo = self._tag_octet
        else:
            eo = cast(bytes, elem)[0]

        if self._elemOctet != eo:
            if self._elemOctet is not None:
                raise ValueError("New element does not belong to the set")
            self._elemOctet = eo

        if elem not in self._seq:
            self._seq.append(elem)

    def decode(self, der_encoded: bytes, strict: bool = False) -> DerSetOf:
        """Decode a complete SET OF DER element, and re-initializes this
        object with it.

        DER INTEGERs are decoded into Python integers. Any other DER
        element is left undecoded; its validity is not checked.

        Args:
            der_encoded (byte string): a complete DER BIT SET OF.
            strict (boolean):
                Whether decoding must check for strict DER compliancy.

        Raises:
            ValueError: in case of parsing errors.
        """

        return DerObject.decode(self, der_encoded, strict)

    def _decodeFromStream(self, s: BytesIO_EOF, strict: bool) -> None:
        """Decode a complete DER SET OF from a file."""

        self._seq = []

        # Fill up self.payload
        DerObject._decodeFromStream(self, s, strict)

        # Add one item at a time to self.seq, by scanning self.payload
        p = BytesIO_EOF(self.payload)
        setIdOctet: Optional[int] = -1
        while p.remaining_data() > 0:
            p.set_bookmark()

            der = DerObject()
            der._decodeFromStream(p, strict)

            # Verify that all members are of the same type
            if setIdOctet == -1:
                setIdOctet = der._tag_octet
            else:
                if setIdOctet != der._tag_octet:
                    raise ValueError("Not all elements are of the same DER type")

            # Parse INTEGERs differently
            if setIdOctet != 0x02:
                self._seq.append(p.data_since_bookmark())
            else:
                derInt = DerInteger()
                derInt.decode(p.data_since_bookmark(), strict)
                self._seq.append(derInt.value)
        # end

    def encode(self) -> bytes:
        """Return this SET OF DER element, fully encoded as a
        binary string.
        """

        # Elements in the set must be ordered in lexicographic order
        ordered = []
        for item in self._seq:
            if _is_number(item):
                bys = DerInteger(item).encode()
            elif isinstance(item, DerObject):
                bys = item.encode()
            else:
                bys = item
            ordered.append(bys)
        ordered.sort()
        self.payload = b"".join(ordered)
        return DerObject.encode(self)


# The classes for the universal types, by tag (identifier octet)
_UNIVERSAL_TYPES: dict[int, type[DerObject]] = {
    0x01: DerBoolean,
    0x02: DerInteger,
    0x03: DerBitString,
    0x04: DerOctetString,
    0x05: DerNull,
    0x06: DerObjectId,
    0x30: DerSequence,
    0x31: DerSetOf,
}