ECC

ECC#

The ECC class implements the Elliptic Curve Cryptography (ECC) algorithm, which is based on the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP).

class ECC#

Creates a new ECC instance.

Parameters:

curve_name (str) – The name of the elliptic curve to use. Default is ‘P-256’, also known as ‘sep256r1’. Options are currently limited to [‘Curve25519’, ‘P-256’, ‘secp256k1’].

Note

The implementation of ECC in this module is based primarily on the following two resources:

Check References for the entire list.

Attention

For Montgomery curves (like Curve25519), the signature scheme has not been implemented yet and hence, the sign and verify functions do not yield any result. Use the ECC cryptosystem accordingly.

Introduction#

Elliptic Curve Cryptography (ECC) is a family of public-key cryptosystems based on the mathematics of elliptic curves. It provides higher security with smaller key sizes compared to other public-key cryptosystems, like RSA, making it more efficient. ECC is widely used in secure communications, including for SSL/TLS certificates, cryptocurrency wallets, and digital signatures. The security of ECC is based on the difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP).

Mathematical Details#

ECC Key Generation#

The ECC key generation process involves the following steps:

  1. Choose an elliptic curve: Select an elliptic curve defined by the equation:

\begin{gather*} y^2 = x^3 + ax + b \qquad \text{(for Weierstrass curves)}\\ By^2 = x(x-1)(x-A) \qquad \text{(for Montgomery curves)} \end{gather*}

where \(a, b, A\) and \(B\) are constants specific to the chosen curve.

  1. Select a base point: A base point \(G\) is selected on the curve, which is used to generate other points on the curve.

  2. Choose a private key: The private key \(b\) is a randomly selected integer.

  3. Compute the public key: The public key \(B\) is computed by multiplying the base point \(G\) by the private key \(b\):

\[B = b \cdot G\]

The public key is the point \(B\) on the elliptic curve, and the private key is the integer \(b\).

ECC Encryption/Decryption Process#

  • Encryption: To encrypt a message \(m\), we first encode it onto a point \(M\) on the curve, by either bruteforcing the next quadratic residue directly from the message integer [for Montgomery curves], or starting after a padding of 128 bits (1 left shifted by 128), as described in the reference [for Weierstrass curves]. We then generate a random integer \(k\) in the range \([1, (n-1)]\). The ciphertext is computed using the public key \(B\) as follows:

\begin{gather*} C_1 = k \cdot G\\ C_2 = m + k \cdot B \end{gather*}

The ciphertext is the pair \((C_1, C_2)\).

  • Decryption: To decrypt the ciphertext \((C_1, C_2)\), the private key \(b\) is used to compute:

\[m = C_2 - b \cdot C_1\]

Note

For both encryption and decryption, if Montgomery curves are used, we operate only with the X-coordinate of message point to compute \(C_2\), and finally take mod with the curve prime \(p\), returning \(1\) for Y-coordinate.

ECC Signature/Verification Process#

  • Signature: The hash of the plaintext message, \(m_h\), is signed using the private key \(b\) as follows:

\begin{gather*} r = (k \cdot G)_x \mod n\\ s = k^{-1} \cdot (m_h + r \cdot b) \mod n \end{gather*}

The signature is the pair \((r, s)\).

  • Verification: To verify a signature \((r, s)\) for a message \(m\) with hash \(m_h\), is verified using public key \(B\) as follows:

\begin{gather*} v_1 = s^{-1} * m_h \mod n\\ v_2 = s^{-1} * r \mod n\\ P = (v_1 \cdot G + v_2 \cdot B)\\ \end{gather*}

The result of the verification is given by:

\[r \stackrel{?}{=} P_x \mod n\]

Usage#

# Example usage of ECC to encrypt, decrypt, sign, and verify a message
from cryptosystems import ECC
cipher = ECC()
public_key, private_key = cipher.generate_keys()  # Generate ECC keys
ciphertext = cipher.encrypt("Hello World", public_key)
print(ciphertext)  # (123456, 654321)
plaintext = cipher.decrypt(ciphertext, private_key, "str")
print(plaintext)  # 'Hello World'
signature, message_hash = cipher.sign("Hello World", private_key)
print(signature, message_hash, sep=", ") # (123456, 654321), b'\x12\x34\x56\x78\x90'
verification = cipher.verify(signature, message_hash, public_key)
print(verification)  # True

Methods#

generate_keypair() → tuple#

Generates a new ECC key pair, in the form \((B, b)\), where \(B\) is the public key and \(b\) is the private key.

Returns:

A tuple containing the public key and private key.

Return type:

tuple

encrypt(plaintext: int | str | bytes, public_key: tuple) → tuple#

Encrypts the given plaintext using the ECC algorithm and returns the ciphertext.

Parameters:

  • plaintext (int | str | bytes) – The plaintext message to be encrypted.

  • public_key (tuple) – The public key used for encryption, in the form \(B = (x, y)\).

Returns:

The encrypted ciphertext.

Return type:

tuple

decrypt(ciphertext: tuple, private_key: int, return_type: str)#

Decrypts the given ciphertext using the ECC algorithm and returns the deciphered plaintext.

Parameters:

  • ciphertext (tuple) – The ciphertext message to be decrypted, in the form \(C = (C_1, C_2)\).

  • private_key (int) – The private key used for decryption, in the form \(b\).

  • return_type (str) – The type in which plaintext is to be returned. It should be either ‘int’, ‘str’, or ‘bytes’. Default is ‘int’

Returns:

The decrypted plaintext.

Return type:

int | str | bytes

sign(message: int | str | bytes, private_key: int) → tuple#

Signs the given message using the ECC algorithm and returns the signature and SHA256 hash.

Parameters:

  • message (int | str | bytes) – The plaintext message to be signed.

  • private_key (int) – The private key used for signature, the form \(b\).

Returns:

The tuple of signature for the message, in the form \((r, s)\), and the SHA256 hash (bytes) of the message.

Return type:

tuple

verify(signature: tuple, message_hash: bytes, public_key: tuple) → bool#

Verifies the given signature using the ECC algorithm and returns True or False.

Parameters:

  • signature (tuple) – The signature to be verified, in the form \((r, s)\).

  • message_hash (bytes) – The SHA256 hash for the message.

  • public_key (tuple) – The public key used for verification, in the form \(B\).

Returns:

True or False, the result of whether the signature is valid.

Return type:

bool

get_params() → tuple#

Returns the parameters of the curve with which the object was instantiated.

Returns:

The tuple of curve parameters, in the form \(((p, a, b),\: G=(G_x, G_y),\: n,\: \text{curve_name})\), where curve_name is “Weierstrass”, “Montgomery”, etc.

Return type:

tuple

References#