tessl/pypi-ecdsa

ECDSA cryptographic signature library (pure python)

—

Pending

Overview

Eval results

Files

Mathematical Functions & Low-Level Operations

Name: tessl/pypi-ecdsa
Author: tessl

Low-level mathematical functions for elliptic curve cryptography, number theory operations, and deterministic signature generation. These functions provide the mathematical foundation for higher-level cryptographic operations.

Capabilities

Number Theory Functions

Mathematical operations on integers including modular arithmetic, primality testing, and specialized elliptic curve mathematical operations.

def gcd(*a):
    """
    Greatest common divisor of multiple numbers.
    
    Parameters:
    - a: int, numbers to find GCD of
    
    Returns:
    int, greatest common divisor
    """

def lcm2(a, b):
    """
    Least common multiple of two numbers.
    
    Parameters:
    - a: int, first number
    - b: int, second number
    
    Returns:
    int, least common multiple
    """

def lcm(*a):
    """
    Least common multiple of multiple numbers.
    
    Parameters:
    - a: int, numbers to find LCM of
    
    Returns:
    int, least common multiple
    """

def jacobi(a, n):
    """
    Compute Jacobi symbol (a/n).
    
    Parameters:
    - a: int, numerator of Jacobi symbol
    - n: int, denominator (must be odd positive integer)
    
    Returns:
    int, Jacobi symbol value (-1, 0, or 1)
    
    Raises:
    JacobiError: if n is not odd positive integer
    """

def square_root_mod_prime(a, p):
    """
    Compute square root of a modulo prime p.
    
    Parameters:
    - a: int, number to find square root of
    - p: int, prime modulus
    
    Returns:
    int, square root of a mod p
    
    Raises:
    SquareRootError: if a is not a quadratic residue mod p
    """

def is_prime(n):
    """
    Test if number is prime using Miller-Rabin test.
    
    Parameters:
    - n: int, number to test
    
    Returns:
    bool, True if n is prime
    """

def next_prime(starting_value):
    """
    Find next prime number >= starting_value.
    
    Parameters:
    - starting_value: int, starting point for search
    
    Returns:
    int, next prime >= starting_value
    """

def factorization(n):
    """
    Prime factorization of integer.
    
    Parameters:
    - n: int, number to factorize
    
    Returns:
    list[int], list of prime factors
    """

Polynomial Operations

Functions for polynomial arithmetic over finite fields, used in elliptic curve operations.

def polynomial_reduce_mod(poly, polymod, p):
    """
    Reduce polynomial modulo another polynomial over GF(p).
    
    Parameters:
    - poly: list[int], polynomial coefficients
    - polymod: list[int], modulus polynomial coefficients
    - p: int, prime field characteristic
    
    Returns:
    list[int], reduced polynomial coefficients
    """

def polynomial_multiply_mod(m1, m2, polymod, p):
    """
    Multiply polynomials modulo another polynomial over GF(p).
    
    Parameters:
    - m1: list[int], first polynomial coefficients
    - m2: list[int], second polynomial coefficients
    - polymod: list[int], modulus polynomial coefficients
    - p: int, prime field characteristic
    
    Returns:
    list[int], product polynomial coefficients
    """

def polynomial_exp_mod(base, exponent, polymod, p):
    """
    Exponentiate polynomial modulo another polynomial over GF(p).
    
    Parameters:
    - base: list[int], base polynomial coefficients
    - exponent: int, exponent
    - polymod: list[int], modulus polynomial coefficients
    - p: int, prime field characteristic
    
    Returns:
    list[int], result polynomial coefficients
    """

RFC 6979 Deterministic Signature Functions

Functions for generating deterministic k values per RFC 6979, ensuring signature determinism while maintaining security.

def generate_k(order, secexp, hash_func, data, retry_gen=0, extra_entropy=b""):
    """
    Generate deterministic k value per RFC 6979.
    
    Parameters:
    - order: int, curve order
    - secexp: int, private key (secret exponent)
    - hash_func: callable, hash function to use
    - data: bytes, data being signed
    - retry_gen: int, retry counter for different k values
    - extra_entropy: bytes, additional entropy
    
    Returns:
    int, deterministic k value for signature
    """

def bits2int(data, qlen):
    """
    Convert bit string to integer per RFC 6979.
    
    Parameters:
    - data: bytes, input bit string
    - qlen: int, bit length of curve order
    
    Returns:
    int, converted integer
    """

def bits2octets(data, order):
    """
    Convert bit string to octet string per RFC 6979.
    
    Parameters:
    - data: bytes, input bit string
    - order: int, curve order
    
    Returns:
    bytes, converted octet string
    """

Low-level ECDSA Operations

Core elliptic curve digital signature algorithm implementation with basic mathematical operations.

class Signature:
    """ECDSA signature container with (r, s) values."""
    
    def __init__(self, r, s):
        """
        Create signature from r and s values.
        
        Parameters:
        - r: int, r component of signature
        - s: int, s component of signature
        """
    
    def recover_public_keys(self, hash, generator):
        """
        Recover possible public keys from signature and hash.
        
        Parameters:
        - hash: int, hash value that was signed
        - generator: Point, curve generator point
        
        Returns:
        list[Point], possible public key points
        """

class Public_key:
    """Low-level ECDSA public key for signature verification."""
    
    def __init__(self, generator, point, verify=True):
        """
        Create public key from generator and point.
        
        Parameters:
        - generator: Point, curve generator
        - point: Point, public key point
        - verify: bool, whether to verify point is on curve
        """
    
    def verifies(self, hash, signature):
        """
        Verify signature against hash.
        
        Parameters:
        - hash: int, hash value to verify
        - signature: Signature, signature to verify
        
        Returns:
        bool, True if signature is valid
        """

class Private_key:
    """Low-level ECDSA private key for signature creation."""
    
    def __init__(self, public_key, secret_multiplier):
        """
        Create private key from public key and secret.
        
        Parameters:
        - public_key: Public_key, corresponding public key
        - secret_multiplier: int, private key value
        """
    
    def sign(self, hash, k):
        """
        Sign hash with given k value.
        
        Parameters:
        - hash: int, hash to sign
        - k: int, random k value for signature
        
        Returns:
        Signature, ECDSA signature
        
        Raises:
        RSZeroError: if r or s component is zero
        """

def point_is_valid(generator, x, y):
    """
    Check if point (x, y) is valid on the curve.
    
    Parameters:
    - generator: Point, curve generator for curve parameters
    - x: int, x coordinate
    - y: int, y coordinate
    
    Returns:
    bool, True if point is on curve
    """

Utility Functions for Bit Operations

Low-level utilities for bit manipulation and length calculations.

def bit_length(x):
    """
    Get bit length of integer.
    
    Parameters:
    - x: int, number to measure
    
    Returns:
    int, number of bits needed to represent x
    """

def orderlen(order):
    """
    Calculate byte length needed to represent curve order.
    
    Parameters:
    - order: int, curve order
    
    Returns:
    int, number of bytes needed
    """

def entropy_to_bits(ent_256):
    """
    Convert entropy bytes to bit string.
    
    Parameters:
    - ent_256: bytes, entropy data
    
    Returns:
    str, bit string representation
    """

Exception Classes

class RSZeroError(RuntimeError):
    """Raised when ECDSA signature r or s component is zero."""

class InvalidPointError(RuntimeError):
    """Raised when elliptic curve point is invalid."""

class JacobiError(Exception):
    """Raised when Jacobi symbol computation fails."""

class SquareRootError(Exception):
    """Raised when square root modulo prime fails."""

class NegativeExponentError(Exception):
    """Raised when negative exponent is used inappropriately."""

Usage Examples

Deterministic Signature Generation

from ecdsa import SigningKey, NIST256p
from ecdsa.rfc6979 import generate_k
from ecdsa.numbertheory import square_root_mod_prime
import hashlib

# Generate key and message
sk = SigningKey.generate(curve=NIST256p)
message = b"Deterministic signature test"
digest = hashlib.sha256(message).digest()

# Generate deterministic k value
k = generate_k(
    order=sk.curve.order,
    secexp=sk.privkey.secret_multiplier,
    hash_func=hashlib.sha256,
    data=digest
)

print(f"Generated k: {k}")
print(f"k bit length: {k.bit_length()}")

# Sign using the deterministic k
signature = sk.sign_deterministic(message, hashfunc=hashlib.sha256)
print(f"Deterministic signature: {signature.hex()}")

# Verify the signature is deterministic (same every time)
signature2 = sk.sign_deterministic(message, hashfunc=hashlib.sha256)
print(f"Signatures match: {signature == signature2}")

Number Theory Operations

from ecdsa.numbertheory import gcd, lcm, jacobi, is_prime, next_prime

# Greatest common divisor and least common multiple
a, b, c = 48, 18, 24
print(f"GCD of {a}, {b}, {c}: {gcd(a, b, c)}")
print(f"LCM of {a}, {b}: {lcm(a, b)}")

# Jacobi symbol computation (for quadratic residues)
n = 97  # prime
for a in [2, 3, 5, 7]:
    j = jacobi(a, n)
    print(f"Jacobi({a}/{n}) = {j}")

# Primality testing
candidates = [97, 98, 99, 101]
for num in candidates:
    print(f"{num} is prime: {is_prime(num)}")

# Find next prime
start = 100
next_p = next_prime(start)
print(f"Next prime after {start}: {next_p}")

Low-level ECDSA Operations

from ecdsa import NIST256p
from ecdsa.ecdsa import Private_key, Public_key, Signature
from ecdsa.util import randrange
import hashlib

# Create low-level key pair
generator = NIST256p.generator
secret = randrange(generator.order())
public_point = secret * generator
public_key = Public_key(generator, public_point)
private_key = Private_key(public_key, secret)

# Sign a hash directly
message = b"Low-level signing test"
hash_value = int(hashlib.sha256(message).hexdigest(), 16)

# Generate random k and sign
k = randrange(generator.order())
signature = private_key.sign(hash_value, k)

print(f"Signature r: {signature.r}")
print(f"Signature s: {signature.s}")

# Verify signature
is_valid = public_key.verifies(hash_value, signature)
print(f"Signature valid: {is_valid}")

# Demonstrate public key recovery
possible_keys = signature.recover_public_keys(hash_value, generator)
print(f"Recovered {len(possible_keys)} possible public keys")
for i, key_point in enumerate(possible_keys):
    if key_point == public_point:
        print(f"Original public key found at index {i}")

Working with Elliptic Curve Mathematics

from ecdsa import NIST256p
from ecdsa.ellipticcurve import Point
from ecdsa.numbertheory import square_root_mod_prime

# Work with curve points
curve = NIST256p.curve
generator = NIST256p.generator

# Generate a random point by scalar multiplication
scalar = 12345
point = scalar * generator

print(f"Point coordinates: ({point.x()}, {point.y()})")
print(f"Point is on curve: {curve.contains_point(point.x(), point.y())}")

# Demonstrate point arithmetic
point2 = 67890 * generator
sum_point = point + point2
double_point = 2 * point

print(f"Point addition works: {sum_point.x()}")
print(f"Point doubling works: {double_point.x()}")

# Work with modular square roots (used in point decompression)
p = curve.p()
test_value = 12345
if jacobi(test_value, p) == 1:  # test_value is a quadratic residue
    sqrt_val = square_root_mod_prime(test_value, p)
    print(f"sqrt({test_value}) mod {p} = {sqrt_val}")
    print(f"Verification: {sqrt_val}^2 mod {p} = {(sqrt_val * sqrt_val) % p}")

Polynomial Operations for Advanced Cryptography

from ecdsa.numbertheory import polynomial_reduce_mod, polynomial_multiply_mod

# Work with polynomials over finite field GF(7)
p = 7

# Define polynomials as coefficient lists (constant term first)
poly1 = [1, 2, 3]      # 1 + 2x + 3x^2
poly2 = [4, 5]         # 4 + 5x
polymod = [1, 0, 1]    # 1 + x^2 (irreducible over GF(7))

# Multiply polynomials
product = polynomial_multiply_mod(poly1, poly2, polymod, p)
print(f"Polynomial product: {product}")

# Reduce polynomial
poly_large = [1, 2, 3, 4, 5]  # 1 + 2x + 3x^2 + 4x^3 + 5x^4
reduced = polynomial_reduce_mod(poly_large, polymod, p)
print(f"Reduced polynomial: {reduced}")

Install with Tessl CLI