Algorithms

@dataclass(frozen=True)
class DigitalSignature:
    """ECDSA signature generation and verification.

    Attributes:
        private_key: The private scalar (integer).
        curve_name:  Name of the curve (e.g. ``"secp256k1"``).
    """

    private_key: int
    curve_name: str = "secp256k1"

    # ----- derived properties -----

    @property
    def _curve(self):
        return get_curve(self.curve_name)

    @property
    def _G(self) -> Point:
        return get_generator(self.curve_name)

    @property
    def public_key(self) -> Point:
        """Compute the public key: ``private_key * G``."""
        return self.private_key * self._G

    # ----- algorithm -----

    def sign(self, message_hash: int) -> tuple[int, int]:
        """Generate an ECDSA signature for a message hash.

        Algorithm:
            1. Choose random k ∈ [1, n-1]
            2. R = k·G,  r = R.x mod n
            3. s = (m + r·d) · k⁻¹ mod n   (d = private key, m = hash)

        .. warning::

           The nonce *k* must **never** be reused across different messages.
           Reusing *k* leaks the private key (as demonstrated in the
           2010 Sony PS3 ECDSA attack).

        Args:
            message_hash: Integer hash of the message (e.g. SHA-256).

        Returns:
            A tuple ``(r, s)`` representing the signature.
        """
        n = self._curve.n
        G = self._G
        r, s = 0, 0
        while r == 0 or s == 0:
            k = secrets.randbelow(n - 1) + 1
            R = k * G
            r = R.x % n
            s = ((message_hash + r * self.private_key) * pow(k, -1, n)) % n
        return r, s

    def verify(self, public_key: Point, message_hash: int, r: int, s: int) -> bool:
        """Verify an ECDSA signature.

        Algorithm:
            1. w  = s⁻¹ mod n
            2. u₁ = m·w mod n,  u₂ = r·w mod n
            3. R' = u₁·G + u₂·Q   (Q = public key)
            4. Accept iff R'.x mod n = r

        Args:
            public_key:   The signer's public key point.
            message_hash: Integer hash of the signed message.
            r:            First component of the signature.
            s:            Second component of the signature.

        Returns:
            ``True`` if the signature is valid, ``False`` otherwise.

        Raises:
            ValueError: If ``r`` or ``s`` are outside ``[1, n-1]``.
        """
        n = self._curve.n
        if not (1 <= r < n and 1 <= s < n):
            raise ValueError("r or s are not in the valid range [1, n-1].")

        G = self._G
        w = pow(s, -1, n)
        u1 = (message_hash * w) % n
        u2 = (r * w) % n
        R = u1 * G + u2 * public_key
        return R.x % n == r

    # ----- convenience wrappers -----

    def sign_message(
        self,
        message: bytes,
        hash_func: Callable[[bytes], Any] = hashlib.sha256,
    ) -> tuple[int, int]:
        """Hash a message and sign it.

        Args:
            message:   The raw message bytes to sign.
            hash_func: Hash constructor (default ``hashlib.sha256``).
                       Any callable that accepts ``bytes`` and returns an
                       object with a ``.hexdigest()`` method (e.g.
                       ``hashlib.sha384``, ``hashlib.sha512``,
                       ``hashlib.sha3_256``).

        Returns:
            A tuple ``(r, s)`` representing the ECDSA signature.
        """
        message_hash = int(hash_func(message).hexdigest(), 16)
        return self.sign(message_hash)

    def verify_message(
        self,
        public_key: Point,
        message: bytes,
        r: int,
        s: int,
        hash_func: Callable[[bytes], Any] = hashlib.sha256,
    ) -> tuple[int, int] | bool:
        """Hash a message and verify its ECDSA signature.

        Args:
            public_key: The signer's public key point.
            message:    The raw message bytes.
            r:          First component of the signature.
            s:          Second component of the signature.
            hash_func:  Hash constructor (default ``hashlib.sha256``).
                        Must match the one used in ``sign_message``.

        Returns:
            ``True`` if the signature is valid, ``False`` otherwise.
        """
        message_hash = int(hash_func(message).hexdigest(), 16)
        return self.verify(public_key, message_hash, r, s)

@dataclass(frozen=True)
class Koblitz:
    """Koblitz message encoding/decoding on an elliptic curve.

    Encoding algorithm:
        1. Convert the message string to an integer *m* using base-α
           positional encoding (α = alphabet_size).
        2. For j = 1, 2, ..., d-1 compute x = d·m + j (mod p).
        3. Test if x³ + ax + b is a quadratic residue mod p (see
           :func:`ecutils.utils.math.is_quadratic_residue`).
        4. If yes, compute y = √(x³ + ax + b) mod p and return
           ``(Point(x, y), j)``.

    With d = 100 the probability of failure per attempt is ≈ 1/2, so the
    overall failure probability after 99 attempts is ≈ 2⁻⁹⁹.

    Attributes:
        curve_name: Name of the curve (e.g. ``"secp521r1"``).
                    Larger curves can encode longer messages in a single point.
        alphabet_size: Character set size. 256 for ASCII, 65536 for Unicode.
    """

    curve_name: str = "secp521r1"
    alphabet_size: int = 256

    # ----- derived properties -----

    @property
    def _curve(self):
        return get_curve(self.curve_name)

    # ----- encode -----

    def encode(self, message: str) -> tuple[Point, int]:
        """Encode a text message into a point on the curve.

        The message is first converted to an integer, then Koblitz's
        method is used to find a valid curve point derived from that integer.

        Args:
            message: The text to encode (limited by curve size).

        Returns:
            A tuple ``(point, j)`` where ``j`` is needed for decoding.

        Raises:
            ValueError: If no valid point is found (extremely unlikely).
        """
        curve = self._curve
        alpha = self.alphabet_size

        # Convert string -> integer  (base-alpha encoding)
        m = sum(ord(ch) * (alpha**i) for i, ch in enumerate(message))

        # Koblitz: try x = d*m + j until y² = x³ + ax + b has a root
        d = 100
        for j in range(1, d):
            x = (d * m + j) % curve.p
            s = (pow(x, 3, curve.p) + curve.a * x + curve.b) % curve.p

            # Euler criterion + Tonelli-like shortcut for p ≡ 3 (mod 4)
            if s == pow(s, (curve.p + 1) // 2, curve.p):
                y = pow(s, (curve.p + 1) // 4, curve.p)
                pt = Point(x, y, curve)
                if pt.is_on_curve():
                    return pt, j

        raise ValueError("Failed to encode message to a valid point on the curve.")

    # ----- decode -----

    def decode(self, point: Point, j: int) -> str:
        """Decode a curve point back into the original text message.

        Args:
            point: The encoded point (as returned by :meth:`encode`).
            j:     The auxiliary value returned alongside the point.

        Returns:
            The original text message.
        """
        alpha = self.alphabet_size
        d = 100
        m = (point.x - j) // d

        chars: list[str] = []
        while m > 0:
            chars.append(chr(m % alpha))
            m //= alpha
        return "".join(chars)