Symbolic type-3 pairing & group operations in SymPy/Sage

type3-symbolic.py

# Type-3 Pairing Implementation for Sage/SymPy
# Models G1, G2, GT groups and scalar field Fp with bilinear pairing

from sympy import symbols, simplify, Mod, Integer
from typing import Union, Optional
import random

class ScalarField:
    """Scalar field Fp for exponents/coefficients"""
    def __init__(self, value, p: Optional[int] = None):
        self.p = p or 2**256 - 2**32 - 977  # Default large prime
        if isinstance(value, int):
            self.value = value % self.p
        else:
            self.value = value  # Allow symbolic values
    
    def __repr__(self):
        return f"Fp({self.value})"
    
    def __add__(self, other):
        if isinstance(other, ScalarField):
            if isinstance(self.value, int) and isinstance(other.value, int):
                return ScalarField((self.value + other.value) % self.p, self.p)
            return ScalarField(simplify(self.value + other.value), self.p)
        return ScalarField(simplify(self.value + other), self.p)
    
    def __sub__(self, other):
        if isinstance(other, ScalarField):
            if isinstance(self.value, int) and isinstance(other.value, int):
                return ScalarField((self.value - other.value) % self.p, self.p)
            return ScalarField(simplify(self.value - other.value), self.p)
        return ScalarField(simplify(self.value - other), self.p)
    
    def __mul__(self, other):
        if isinstance(other, ScalarField):
            if isinstance(self.value, int) and isinstance(other.value, int):
                return ScalarField((self.value * other.value) % self.p, self.p)
            return ScalarField(simplify(self.value * other.value), self.p)
        return ScalarField(simplify(self.value * other), self.p)
    
    def __truediv__(self, other):
        """Field division (multiplication by modular inverse)"""
        if isinstance(other, ScalarField):
            if isinstance(self.value, int) and isinstance(other.value, int):
                # Compute modular inverse using extended Euclidean algorithm
                inv = pow(other.value, self.p - 2, self.p)  # Fermat's little theorem
                return ScalarField((self.value * inv) % self.p, self.p)
            return ScalarField(simplify(self.value / other.value), self.p)
        return ScalarField(simplify(self.value / other), self.p)
    
    def __pow__(self, exp):
        if isinstance(self.value, int) and isinstance(exp, int):
            return ScalarField(pow(self.value, exp, self.p), self.p)
        return ScalarField(self.value ** exp, self.p)
    
    def __neg__(self):
        """Additive inverse in field"""
        if isinstance(self.value, int):
            return ScalarField((-self.value) % self.p, self.p)
        return ScalarField(simplify(-self.value), self.p)
    
    def inverse(self):
        """Multiplicative inverse in field"""
        if isinstance(self.value, int):
            return ScalarField(pow(self.value, self.p - 2, self.p), self.p)
        return ScalarField(1 / self.value, self.p)

class GroupElement:
    """Base class for pairing group elements"""
    def __init__(self, value, group_name: str, generator_symbol: str = "g"):
        self.value = value
        self.group_name = group_name
        self.generator_symbol = generator_symbol
    
    def __repr__(self):
        if self.value == 0:
            return f"O_{self.group_name}"  # Identity element
        elif self.value == 1:
            return f"{self.generator_symbol}_{self.group_name}"
        else:
            return f"{self.generator_symbol}_{self.group_name}^({self.value})"
    
    def __add__(self, other):
        """Group addition (additive notation for elliptic curves)"""
        if not isinstance(other, type(self)) or other.group_name != self.group_name:
            raise TypeError(f"Cannot add {self.group_name} element to {type(other).__name__}")
        return type(self)(simplify(self.value + other.value))
    
    def __sub__(self, other):
        """Group subtraction"""
        if not isinstance(other, type(self)) or other.group_name != self.group_name:
            raise TypeError(f"Cannot subtract {type(other).__name__} from {self.group_name}")
        return type(self)(simplify(self.value - other.value))
    
    def __mul__(self, scalar):
        """Scalar multiplication"""
        if isinstance(scalar, ScalarField):
            return type(self)(simplify(self.value * scalar.value))
        return type(self)(simplify(self.value * scalar))
    
    def __rmul__(self, scalar):
        """Right scalar multiplication"""
        return self.__mul__(scalar)
    
    def __neg__(self):
        """Group negation"""
        return type(self)(simplify(-self.value))
    
    def __eq__(self, other):
        return (isinstance(other, type(self)) and 
                other.group_name == self.group_name and 
                simplify(self.value - other.value) == 0)
    
    def is_identity(self):
        """Check if element is the group identity"""
        return simplify(self.value) == 0
    
    def order(self, group_order=None):
        """Return the order of this element (if group_order provided)"""
        if group_order is None:
            return None
        # This would need more sophisticated implementation in practice
        return f"ord({self}) | {group_order}"

class G1Element(GroupElement):
    """Elements of G1 (typically on base field)"""
    def __init__(self, value):
        super().__init__(value, "1", "g")

class G2Element(GroupElement):
    """Elements of G2 (typically on extension field)"""
    def __init__(self, value):
        super().__init__(value, "2", "h")

class GTElement(GroupElement):
    """Elements of GT (target group, typically in extension field)"""
    def __init__(self, value):
        super().__init__(value, "T", "e")
    
    def __mul__(self, other):
        """GT multiplication (corresponds to addition in exponent)"""
        if isinstance(other, GTElement):
            return GTElement(simplify(self.value + other.value))  # Additive in exponent
        elif isinstance(other, ScalarField):
            return GTElement(simplify(self.value * other.value))
        return GTElement(simplify(self.value * other))
    
    def __truediv__(self, other):
        """GT division (corresponds to subtraction in exponent)"""
        if isinstance(other, GTElement):
            return GTElement(simplify(self.value - other.value))
        elif isinstance(other, ScalarField):
            return GTElement(simplify(self.value / other.value))
        return GTElement(simplify(self.value / other))
    
    def __pow__(self, exp):
        """Exponentiation in GT (scalar multiplication in exponent)"""
        if isinstance(exp, ScalarField):
            return GTElement(simplify(self.value * exp.value))
        return GTElement(simplify(self.value * exp))
    
    def inverse(self):
        """Multiplicative inverse in GT (negation in exponent)"""
        return GTElement(simplify(-self.value))

# Pairing function e: G1 × G2 → GT
def pairing(P: G1Element, Q: G2Element) -> GTElement:
    """
    Bilinear pairing e: G1 × G2 → GT
    Satisfies bilinearity: e(aP, bQ) = e(P, Q)^(ab)
    """
    if not isinstance(P, G1Element) or not isinstance(Q, G2Element):
        raise TypeError("Pairing requires G1Element and G2Element")
    
    # The pairing maps (g1^a, g2^b) -> e(g1,g2)^(ab)
    return GTElement(simplify(P.value * Q.value))

# Convenience constructors
def Fp(value, p=None):
    """Create scalar field element"""
    return ScalarField(value, p)

def G1(value=1):
    """Create G1 element (default is generator)"""
    return G1Element(value)

def G2(value=1):
    """Create G2 element (default is generator)"""
    return G2Element(value)

def GT(value=1):
    """Create GT element (default is generator)"""
    return GTElement(value)

# Example usage and testing
if __name__ == "__main__":
    # Create symbolic variables
    a, b, x, y, r, s = symbols('a b x y r s')
    
    print("=== Type-3 Pairing Groups ===")
    print("G1: Additive group (elliptic curve points)")
    print("G2: Additive group (elliptic curve points on extension)")  
    print("GT: Multiplicative group (extension field elements)")
    print("Fp: Scalar field for exponents\n")
    
    # Scalar field operations
    print("=== Scalar Field Fp ===")
    fp_a = Fp(a)
    fp_b = Fp(b)
    print(f"a = {fp_a}")
    print(f"b = {fp_b}")
    print(f"a + b = {fp_a + fp_b}")
    print(f"a * b = {fp_a * fp_b}")
    print(f"a^2 = {fp_a**2}")
    
    # G1 operations
    print(f"\n=== Group G1 ===")
    g1_gen = G1()  # Generator
    P = G1(x)      # Point P = g1^x
    Q_g1 = G1(y)   # Point Q = g1^y
    
    print(f"g1 (generator) = {g1_gen}")
    print(f"P = {P}")
    print(f"Q = {Q_g1}")
    print(f"P + Q = {P + Q_g1}")
    print(f"2*P = {2 * P}")
    print(f"a*P = {fp_a * P}")
    print(f"-P = {-P}")
    
    # G2 operations
    print(f"\n=== Group G2 ===")
    g2_gen = G2()  # Generator
    R = G2(r)      # Point R = g2^r  
    S = G2(s)      # Point S = g2^s
    
    print(f"g2 (generator) = {g2_gen}")
    print(f"R = {R}")
    print(f"S = {S}")
    print(f"R + S = {R + S}")
    print(f"b*R = {fp_b * R}")
    
    # This should fail - cannot mix G1 and G2
    print(f"\n=== Type Safety ===")
    try:
        invalid = P + R  # G1 + G2 should fail
        print("ERROR: This should not work!")
    except TypeError as e:
        print(f"✓ Correctly prevented G1 + G2: {e}")
    
    # GT operations  
    print(f"\n=== Target Group GT (Multiplicative Representation) ===")
    gt_gen = GT()
    T1 = GT(a)
    T2 = GT(b)
    
    print(f"e (GT generator) = {gt_gen}")
    print(f"T1 = {T1}")
    print(f"T2 = {T2}")
    print(f"T1 * T2 = {T1 * T2}")  # Multiplicative in GT
    print(f"T1 / T2 = {T1 / T2}")  # Division in GT (subtraction in exponent)
    print(f"T1^a = {T1**fp_a}")
    print(f"T1^(-1) = {T1.inverse()}")  # Multiplicative inverse
    
    # Field operations
    print(f"\n=== Field Operations ===")
    fp_x = Fp(7)
    fp_y = Fp(3) 
    print(f"7 + 3 = {fp_x + fp_y}")
    print(f"7 - 3 = {fp_x - fp_y}")
    print(f"7 * 3 = {fp_x * fp_y}")
    print(f"7 / 3 = {fp_x / fp_y}")
    print(f"7^(-1) = {fp_x.inverse()}")
    print(f"-7 = {-fp_x}")
    
    # Identity elements
    print(f"\n=== Identity Elements ===")
    id_g1 = G1(0)
    id_g2 = G2(0) 
    id_gt = GT(0)
    id_fp = Fp(0)
    
    print(f"G1 identity: {id_g1}")
    print(f"G2 identity: {id_g2}")
    print(f"GT identity: {id_gt}")
    print(f"Fp additive identity: {id_fp}")
    print(f"Fp multiplicative identity: {Fp(1)}")
    
    # Check identity properties
    print(f"P + O_1 = {P + id_g1}")
    print(f"T1 * e^0 = {T1 * id_gt}")  # Should equal T1
    
    # Pairing operations
    print(f"\n=== Bilinear Pairing e: G1 × G2 → GT ===")
    
    # Basic pairing
    e_PR = pairing(P, R)
    print(f"e(P, R) = e({P}, {R}) = {e_PR}")
    
    # Bilinearity: e(aP, bR) = e(P, R)^(ab)
    aP = fp_a * P
    bR = fp_b * R
    e_aP_bR = pairing(aP, bR)
    e_PR_ab = pairing(P, R) ** (fp_a * fp_b)
    
    print(f"\n=== Bilinearity Check ===")
    print(f"aP = {aP}")
    print(f"bR = {bR}")
    print(f"e(aP, bR) = {e_aP_bR}")
    print(f"e(P, R)^(ab) = {e_PR_ab}")
    print(f"Equal? {e_aP_bR == e_PR_ab}")
    
    # Common cryptographic operations
    print(f"\n=== Cryptographic Examples ===")
    
    # Key generation
    alpha, beta = symbols('alpha beta')
    sk_alpha = Fp(alpha)  # Secret key
    pk_alpha = sk_alpha * G1()  # Public key in G1
    
    print(f"Secret key: {sk_alpha}")
    print(f"Public key: {pk_alpha}")
    
    # Signature verification pattern: e(sig, g2) = e(msg_hash, pk)
    msg_hash = G1(symbols('H(m)'))  # Hash of message to G1
    signature = sk_alpha * msg_hash  # Signature
    
    e_sig_g2 = pairing(signature, G2())
    e_hash_pk = pairing(msg_hash, pk_alpha * G2())  # This won't work directly...
    
    print(f"Message hash: {msg_hash}")
    print(f"Signature: {signature}")
    print(f"e(sig, g2) = {e_sig_g2}")
    
    # For BLS signatures, we'd need pk in G2:
    pk_G2 = sk_alpha * G2()
    e_hash_pk_correct = pairing(msg_hash, pk_G2)
    print(f"Public key in G2: {pk_G2}")
    print(f"e(H(m), pk_G2) = {e_hash_pk_correct}")
    print(f"Signature valid? {e_sig_g2 == e_hash_pk_correct}")
    
    print(f"\n=== Advanced: Multi-scalar operations ===")
    # Multi-scalar multiplication
    scalars = [Fp(a), Fp(b), Fp(x)]
    g1_points = [G1(1), G1(2), G1(3)]
    
    # Compute a*G1(1) + b*G1(2) + x*G1(3)
    msm_result = sum([s * p for s, p in zip(scalars, g1_points)], G1(0))
    print(f"Multi-scalar mult: {scalars[0]}*{g1_points[0]} + {scalars[1]}*{g1_points[1]} + {scalars[2]}*{g1_points[2]}")
    print(f"Result: {msm_result}")

This was quickly spat out by Claude Sonnet 4, I'm keeping it here for reference.
It allows me to model symbolic operations on curve groups in Sage with the restraints that come from asymmetric bilinear pairings etc.