Elliptic Curve arithmetic (add, multiply)

[Marcos Portnoi]

It seems addition and multiplication using Elliptic Curve points is not working (type G).

Here is a sample code:

import charm.toolbox.ecgroup
import charm.schemes.pksig.pksig_ecdsa
import charm.toolbox.eccurve


group = charm.toolbox.ecgroup.ECGroup(charm.toolbox.eccurve.secp256k1)
# Alice
ecdsa_alice = charm.schemes.pksig.pksig_ecdsa.ECDSA(group)
alice_public_key, alice_secret_key = ecdsa_alice.keygen(0)
print("Alice ECDSA public key: ", alice_public_key)
print("Alice ECDSA private key: ", alice_secret_key)


# Bob
ecdsa_bob = charm.schemes.pksig.pksig_ecdsa.ECDSA(group)
bob_public_key, bob_secret_key = ecdsa_bob.keygen(0)
print("Bob ECDSA public key: ", bob_public_key)
print("Bob ECDSA private key: ", bob_secret_key)


# Add?
print("Alice y point: ", alice_public_key['y'])
print("Bob y point: ", bob_public_key['y'])
# Not working. It is just appending tuples.
#print("Adding Alice and Bob public keys: ", group.coordinates(alice_public_key['y']) + group.coordinates(bob_public_key['y']))
# The following line yields: elliptic_curve.Error: adding the a group element G to ZR is undefined.
#print("Adding Alice and Bob public keys: ", alice_public_key['y'] + bob_public_key['y'])
# The following line yields: elliptic_curve.Error: elements are not of the same type.
print("Multiplying Alice private with Bob public: ", alice_secret_key * bob_public_key['y']

Checking the source code that generates the module elliptic_curve.pyd (ecmodule.c), it seems that the overload for "add" (ECE_add) only works with BIGNUMs, not (x,y) points (the function uses BN_mod_add, instead of EC_POINT_add from OpenSSL).

Any suggestions? I do need the add operation for elliptic curve points...

[Marcos Portnoi]

I was mistaken.

I studied ecmodule.c a bit more, and indeed EC_POINT_add is present, although in the overloading of multiplication (and EC_POINT_MUL in the overloading of exponentiation). That's when I remembered reading somewhere in the Charm documentation that Charm was designed such that crypto equations could be written in one form irregardless of the underlying group. I.e., g**x and x*a in Zr integer group are written exactly as g**x and x*a in EC groups, although they are in fact operated as x*G and x + a in EC groups. In this way, equations would not have to be rewritten if one chooses to change the underlying groups.

In fact, I rewrote the sample code and the operations do run in EC groups as point addition and escalar-point multiplication. The rewritten sample code:

group = charm.toolbox.ecgroup.ECGroup(charm.toolbox.eccurve.secp256k1)
# Alice
ecdsa_alice = charm.schemes.pksig.pksig_ecdsa.ECDSA(group)
alice_public_key, alice_secret_key = ecdsa_alice.keygen(0)
print("Alice ECDSA public key: ", alice_public_key)

print("Alice ECDSA secret key: ", alice_secret_key)

# Bob
ecdsa_bob = charm.schemes.pksig.pksig_ecdsa.ECDSA(group)
bob_public_key, bob_secret_key = ecdsa_bob.keygen(0)
print("Bob ECDSA public key: ", bob_public_key)

print("Bob ECDSA secret key: ", bob_secret_key)

# Add?
print("Alice y point: ", alice_public_key['y'])
print("Bob y point: ", bob_public_key['y'])

# Note that Charm overloads operators such that operations under Zr (integer) fields are written the same way as those under EC groups.
# I.e., g**x is written as is under Zr or G, but under G, it really means x*G. Likewise, a*b is written the same, but means a + b under EC groups.
# Therefore, the multiplication below is an "add" for EC points.
print("Adding Alice and Bob public keys: ", alice_public_key['y'] * bob_public_key['y'])


# Now the power here is a multiplication for EC group. Note the order; the base must come first, obviously, but it becomes the right-hand-side of the
# EC multiplication: alice_secret_key * bob_public_key
print("Multiplying Alice secret and Bob public key: ", bob_public_key['y'] ** alice_secret_key)

I have tested a few Python EC implementations and OpenSSL wrappers (pyelliptic, pyopenssl, cryptography, pycrypto), and indeed Charm has the most straightforward way of allowing for EC arithmetic: use ec_elements and just perform exponentiation and multiplication as though in Zr groups.