Topic: OFF TOPIC (Read 1612 times)

# Super simple Elliptic Curve Presentation. No imported libraries, wrappers, nothing.
# For educational purposes only. Remember to use Python 2.7.6 or lower. You'll need to make changes for Python 3.

# Below are the public specs for Bitcoin's curve - the secp256k1

Pcurve = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 -1 # The proven prime
N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field
Acurve = 0; Bcurve = 7 # These two defines the elliptic curve. y^2 = x^3 + Acurve * x + Bcurve
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx,Gy) # This is our generator point. Trillions of dif ones possible

#Individual Transaction/Personal Information
privKey = 0xA0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E #replace with any private key

def modinv(a,n=Pcurve): #Extended Euclidean Algorithm/'division' in elliptic curves
    lm, hm = 1,0
    low, high = a%n,n
    while low > 1:
        ratio = high/low
        nm, new = hm-lm*ratio, high-low*ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % n

def ECadd(a,b): # Not true addition, invented for EC. Could have been called anything.
    LamAdd = ((b[1]-a[1]) * modinv(b[0]-a[0],Pcurve)) % Pcurve
    x = (LamAdd*LamAdd-a[0]-b[0]) % Pcurve
    y = (LamAdd*(a[0]-x)-a[1]) % Pcurve
    return (x,y)

def ECdouble(a): # This is called point doubling, also invented for EC.
    Lam = ((3*a[0]*a[0]+Acurve) * modinv((2*a[1]),Pcurve)) % Pcurve
    x = (Lam*Lam-2*a[0]) % Pcurve
    y = (Lam*(a[0]-x)-a[1]) % Pcurve
    return (x,y)

def EccMultiply(GenPoint,ScalarHex): #Double & add. Not true multiplication
    if ScalarHex == 0 or ScalarHex >= N: raise Exception("Invalid Scalar/Private Key")
    ScalarBin = str(bin(ScalarHex))[2:]
    Q=GenPoint
    for i in range (1, len(ScalarBin)): # This is invented EC multiplication.
        Q=ECdouble(Q); # print "DUB", Q[0]; print
        if ScalarBin[i] == "1":
            Q=ECadd(Q,GenPoint); # print "ADD", Q[0]; print
    return (Q)

print; print "******* Public Key Generation *********";
print
PublicKey = EccMultiply(GPoint,privKey)
print "the private key:";
print privKey; print
print "the uncompressed public key (not address):";
print PublicKey; print
print "the uncompressed public key (HEX):";
print "04" + "%064x" % PublicKey[0] + "%064x" % PublicKey[1];
print;
print "the official Public Key - compressed:";
if PublicKey[1] % 2 == 1: # If the Y value for the Public Key is odd.
    print "03"+str(hex(PublicKey[0])[2:-1]).zfill(64)
else: # Or else, if the Y value is even.
    print "02"+str(hex(PublicKey[0])[2:-1]).zfill(64)

import gmpy2

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0X483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx,Gy)
Z = Point(0,0) # zero-point, infinite in real x,y - plane

# return (g, x, y) a*x + b*y = gcd(x, y)
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def modinv(m, n = modulo):
    while m < 0:
        m += n
    g, x, _ = egcd(m, n)
    if g == 1:
        return x % n

    else: print (' no inverse exist')

def mul2(Pmul2, p = modulo):
    R = Point(0,0)
    #c = 3*Pmul2.x*Pmul2.x*modinv(2*Pmul2.y, p) % p
    c = 3*Pmul2.x*Pmul2.x*gmpy2.invert(2*Pmul2.y, p) % p
    R.x = (c*c-2*Pmul2.x) % p
    R.y = (c*(Pmul2.x - R.x)-Pmul2.y) % p
    return R

def add(Padd, Q, p = modulo):
    if Padd.x == Padd.y == 0: return Q
    if Q.x == Q.y == 0: return Padd
    if Padd == Q: return mul2(Q)
    R = Point()
    dx = (Q.x - Padd.x) % p
    dy = (Q.y - Padd.y) % p
    c = dy * gmpy2.invert(dx, p) % p     
    #c = dy * modinv(dx, p) % p
    R.x = (c*c - Padd.x - Q.x) % p
    R.y = (c*(Padd.x - R.x) - Padd.y) % p
    return R # 6 sub, 3 mul, 1 inv

def mulk(k, Pmulk, p = modulo):
    if k == 0: return Z
    if k == 1: return Pmulk
    if (k % 2 == 0): return mulk(k//2, mul2(Pmulk, p), p)
    return add(Pmulk, mulk((k-1)//2, mul2(Pmulk, p), p), p)

>>> PG.x, PG.y
(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
>>> P2=mul2(PG)
>>> int(P2.x), int(P2.y)
(89565891926547004231252920425935692360644145829622209833684329913297188986597, 12158399299693830322967808612713398636155367887041628176798871954788371653930)
>>> P3=add(P2,PG)
>>> int(P3.x), int(P3.y)
(112711660439710606056748659173929673102114977341539408544630613555209775888121, 25583027980570883691656905877401976406448868254816295069919888960541586679410)