Nyberg-Rueppel Signature Scheme

ecnr.py

import hashlib
import secrets

# Elliptic Curve Parameters (placeholders for educational purposes)
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F  # Field prime
a = 0
b = 7
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # Order of G

# Base point G (using Bitcoin's secp256k1 parameters for illustration)
G_x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
G_y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
G = (G_x, G_y)

# Elliptic Curve Operations
def inverse_mod(k, p):
    """Compute the modular inverse of k modulo p."""
    return pow(k, -1, p)

def point_add(P, Q):
    """Add two points P and Q on the elliptic curve."""
    if P == (None, None):
        return Q
    if Q == (None, None):
        return P
    if P == Q:
        return point_double(P)
    if P[0] == Q[0] and (P[1] + Q[1]) % p == 0:
        return (None, None)

    lam = ((Q[1] - P[1]) * inverse_mod(Q[0] - P[0], p)) % p
    x_r = (lam * lam - P[0] - Q[0]) % p
    y_r = (lam * (P[0] - x_r) - P[1]) % p
    return (x_r, y_r)

def point_double(P):
    """Double a point P on the elliptic curve."""
    if P == (None, None):
        return (None, None)

    lam = ((3 * P[0] * P[0] + a) * inverse_mod(2 * P[1], p)) % p
    x_r = (lam * lam - 2 * P[0]) % p
    y_r = (lam * (P[0] - x_r) - P[1]) % p
    return (x_r, y_r)

def point_multiply(k, P):
    """Multiply a point P by an integer k."""
    N = P
    Q = (None, None)  # Point at infinity
    while k > 0:
        if k % 2 == 1:
            Q = point_add(Q, N)
        N = point_double(N)
        k = k // 2
    return Q

def point_subtract(P, Q):
    """Subtract point Q from point P on the elliptic curve."""
    Q_neg = (Q[0], (-Q[1]) % p)
    return point_add(P, Q_neg)

def hash_function(R_x, m):
    """Hash function for ECNR (e.g., SHA-256)."""
    data = R_x.to_bytes(32, 'big') + m
    h = hashlib.sha256(data).digest()
    return int.from_bytes(h, 'big') % n

# Key Generation
def key_generation():
    d = secrets.randbelow(n - 1) + 1  # Private key
    Q = point_multiply(d, G)          # Public key
    return d, Q

# Signing
def sign_message(m, d):
    k = secrets.randbelow(n - 1) + 1
    R = point_multiply(k, G)
    e = hash_function(R[0], m)
    s = (k + e * d) % n
    signature = (R[0], s)
    return signature

# Verification
def verify_signature(m, signature, Q):
    R_x, s = signature
    e = hash_function(R_x, m)
    sG = point_multiply(s, G)
    eQ = point_multiply(e, Q)
    R_prime = point_subtract(sG, eQ)
    return R_prime[0] == R_x

# Example Usage
def int_to_bytes(x: int) -> bytes:
    return x.to_bytes((x.bit_length() + 7) // 8, byteorder='big')

def bytes_to_int(x: bytes) -> int:
    return int.from_bytes(x, byteorder='big')

def main():
    # Message to be signed
    message = b"Hello, ECNR!"

    # Generate keys
    d, Q = key_generation()

    # Sign the message
    signature = sign_message(message, d)

    # Verify the signature
    is_valid = verify_signature(message, signature, Q)

    # Output results
    print(f"Message: {message}")
    print(f"Private Key (d): {hex(d)}")
    print(f"Public Key (Q): ({hex(Q[0])}, {hex(Q[1])})")
    print(f"Signature: (R_x={hex(signature[0])}, s={hex(signature[1])})")
    print(f"Signature valid: {is_valid}")

if __name__ == "__main__":
    main()

nrss.py

'''
Nyberg–Rueppel Signature Scheme

Message (m): 0x48656c6c6f2c2045434e5221
Public Key (y): 0x6e4f2ed113767ca19ad79e9c8026d627bba
Private Key (x): 0x3b97d04cfba60a868650cbb460675f90352
Signature (r, s): (0x3e0c8187d0f2597a327997077ff4532a5da, 0x31435117e9e8db998abc3bc15b6dc58535f)
Signature valid : True
'''
import random

# Parameters
p = 0x112e06dc10ba8b690ed6ce57b4f4d62510fb
q = 0x897036e085d45b4876b672bda7a6b12887d
alpha = 0x3

# Key generation
def key_generation():
    x = random.randint(1, q-1)  # Private key
    y = pow(alpha, x, p)  # Public key
    return (x, y)

# Signing
def sign_message(m, x):
    k = random.randint(1, q-1)
    r = (m * pow(alpha, k, p)) % p
    r_prime = r % q
    s = (-k - r_prime * x) % q
    return (r, s)

# Verification
def verify_signature(m, r, s, y):
    if s >= q:
        return False
    r_prime = r % q
    lhs = (pow(alpha, s, p) * pow(y, r_prime, p) * r) % p
    return lhs == m

def int_to_bytes(x: int) -> bytes:
    return x.to_bytes(32, byteorder='big')

def bytes_to_int(x: bytes) -> int:
    return int.from_bytes(x, byteorder='big')
    
# Example usage
message = bytes_to_int(b"Hello, World!")
x, y = key_generation()
r, s = sign_message(message, x)
is_valid = verify_signature(message, r, s, y)

print(f"Message (m): {hex(message)}")
print(f"Public Key (y): {hex(y)}")
print(f"Private Key (x): {hex(x)}")
print(f"Signature (r, s): ({hex(r)}, {hex(s)})")
print(f"Signature valid : {is_valid}")