NewbieOubie2017 commented 6 years ago

I edited the code to get it to run with python3 but it still is not completely debugged... this is what I get when it runs: * Public Key Generation *** the private key (in base 10 format): 75263518707598184987916378021939673586055614731957507592904438851787542395619

the uncompressed public key (starts with '04' & is not the public address): 04 0.0 0.0

* Signature Generation *** r = 0.0 s = 0.0

* Signature Verification ***>> Traceback (most recent call last): File "CreateEllipticCurvesPart5TheMagicSigningAndVerifyingdebugged.py", line 63, in xu2, yu2 = EccMultiply(xPublicKey,yPublicKey,(r*w)%N) File "CreateEllipticCurvesPart5TheMagicSigningAndVerifyingdebugged.py", line 39, in EccMultiply if Scalar == 0 or Scalar >= N: raise Exception("Invalid Scalar/Private Key") Exception: Invalid Scalar/Private Key

Basically I just put in parentheses in the print commands. Here is the new code.

Python 2.7.6 - Super simple Elliptic Curve Presentation. No imported libraries, wrappers, nothing. # For educational purposes only

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

Pcurve = 2256 - 232 - 29 - 28 - 27 - 26 - 2*4 -1 # The proven prime N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field Acurve = 0; Bcurve = 7 # This defines the curve. y^2 = x^3 + Acurve x + Bcurve Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240 Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424 GPoint = (Gx,Gy) # This is our generator point. Tillions of dif ones possible

Individual Transaction/Personal Information

privKey = 75263518707598184987916378021939673586055614731957507592904438851787542395619 #replace with any private key RandNum = 28695618543805844332113829720373285210420739438570883203839696518176414791234 #replace with a truly random number HashOfThingToSign = 86032112319101611046176971828093669637772856272773459297323797145286374828050 # the hash of your message/transaction

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-lmratio, high-lowratio lm, low, hm, high = nm, new, lm, low return lm % n

def ECadd(xp,yp,xq,yq): # Not true addition, invented for EC. It adds Point-P with Point-Q. m = ((yq-yp) modinv(xq-xp,Pcurve)) % Pcurve xr = (mm-xp-xq) % Pcurve yr = (m*(xp-xr)-yp) % Pcurve return (xr,yr)

def ECdouble(xp,yp): # EC point doubling, invented for EC. It doubles Point-P. LamNumer = 3xpxp+Acurve LamDenom = 2yp Lam = (LamNumer modinv(LamDenom,Pcurve)) % Pcurve xr = (LamLam-2xp) % Pcurve yr = (Lam*(xp-xr)-yp) % Pcurve return (xr,yr)

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

print() print( "* Public Key Generation ***") xPublicKey, yPublicKey = EccMultiply(Gx,Gy,privKey) print( "the private key (in base 10 format):"); print(privKey); print() print("the uncompressed public key (starts with '04' & is not the public address):"); print("04", xPublicKey, yPublicKey)

print(); print("* Signature Generation ***") xRandSignPoint, yRandSignPoint = EccMultiply(Gx,Gy,RandNum) r = xRandSignPoint % N print("r =", r) s = ((HashOfThingToSign + rprivKey)(modinv(RandNum,N))) % N; print("s =", s)

print(); print("* Signature Verification ***>>") w = modinv(s,N) xu1, yu1 = EccMultiply(Gx,Gy,(HashOfThingToSign w)%N) xu2, yu2 = EccMultiply(xPublicKey,yPublicKey,(rw)%N) x,y = ECadd(xu1,yu1,xu2,yu2) print(r==x); print()

molet01 commented 5 years ago

ratio = high/low must be an integer division, change it into ratio = high // low

ricky-andre commented 5 years ago

This version worked for me:

Pcurve = 2256 - 232 - 29 - 28 - 27 - 26 - 2*4 -1 # The proven prime Acurve = 0; Bcurve = 7 # These two defines the elliptic curve. y^2 = x^3 + Acurve x + Bcurve Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240 Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424 GPoint = (Gx,Gy) # Generator Point N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field privKey = 75263518707598184987916378021939673586055614731957507592904438851787542395619

RandNum = 28695618543805844332113829720373285210420739438570883203839696518176414791234 #replace with a truly random number HashOfThingToSign = 86032112319101611046176971828093669637772856272773459297323797145286374828050 # the hash of your message/transaction

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

def ECAdd(a,b): # Point addition, invented for EC. LambdaAdd = ((b[1] - a[1]) modinv(b[0] - a[0],Pcurve)) % Pcurve x = (LambdaAdd LambdaAdd - a[0] - b[0]) % Pcurve y = (LambdaAdd * (a[0] - x) - a[1]) % Pcurve return (x,y)

def ECDouble(a): # Point Doubling, also invented for EC. LamdaDouble = ((3 a[0] a[0] + Acurve) modinv((2 a[1]), Pcurve)) % Pcurve x = (LamdaDouble LamdaDouble - 2 a[0]) % Pcurve y = (LamdaDouble * (a[0] - x) - a[1]) % Pcurve return (x,y)

def ECMultiply(GenPoint,privKeyHex): #Double & add. Not true multiplication if privKeyHex == 0 or privKeyHex >= N: raise Exception("Invalid Private Key") privKeyBin = str(bin(privKeyHex))[2:] Q=GenPoint for i in range (1, len(privKeyBin)): Q=ECDouble(Q); if privKeyBin[i] == "1": Q=ECAdd(Q,GenPoint); return (Q)

PublicKey = ECMultiply(GPoint,privKey) print("Private Key:") print (privKey) print("\nPublic Key public key (uncompressed):") print ("04", PublicKey) print("\nPublic Key (compressed):") if (PublicKey[1] % 2 == 1): # If the Y coordinate of the Public Key is odd. print("03"+str(hex(PublicKey[0])[2:]).zfill(64)) else: # If the Y coordinate is even. print("02"+str(hex(PublicKey[0])[2:]).zfill(64))

print("\n Signature Generation ") xRandSignPoint, yRandSignPoint = ECMultiply(GPoint,RandNum) r = xRandSignPoint % N print("r =", r) s = ((HashOfThingToSign + rprivKey)(modinv(RandNum,N))) % N print("s =", s)

print("\n*** Signature Verification ****>>") w = modinv(s,N) x, y = ECAdd(ECMultiply(GPoint,(HashOfThingToSign w) % N), ECMultiply(PublicKey,(rw) % N)) print(r==x);

ricky-andre commented 5 years ago

You can also find the code here: https://github.com/roheat/PublicKeyGeneration/

... even though you have to fix the following:

as explained above ratio = high//low (double back slash)
when printing the compressed version, the hex string needs to be cutted with [2:] (and NOT [2:-1])

and of course the print statements need to be modified.

NewbieOubie2017 commented 5 years ago

Okay I made those changes and hopefully submitted it correctly.

gtmadureira commented 3 years ago

CODE FOR PYTHON 3.6.13 OR HIGHER (UPDATED) :

https://github.com/gtmadureira/bitcoin_address-generator/tree/main/app_python/ecc_tests/secp256k1

NewbieOubie2017 commented 3 years ago

Thank you so very much Gustave! It works nicely once the indent at line 66 and 67 is adjusted.

From: Gustavo Madureira @.> Sent: Monday, April 12, 2021 10:42 PM To: wobine/blackboard101 @.> Cc: William Milmoe @.>; Author @.> Subject: Re: [wobine/blackboard101] python3 debugging code (#14)

https://github.com/gtmadureira/bitcoin_address-generator/blob/main/app_python/privkey_to_pubkey/secp256k1.py

CODE FOR PYTHON 3.6.13 OR HIGHER :

Super simple Elliptic Curve Presentation.

For educational purposes only.

Works on Python 3.6.13 or higher.

Source: https://github.com/gtmadureira/bitcoin_address-generator/blob/main/app_python/privkey_to_pubkey/secp256k1.py

import random import array import hashlib import os import sys

Checking the type of Operating System.

if sys.platform == "linux" or sys.platform == "linux2" or sys.platform == "darwin": def clear(): os.system('clear') # On Linux/OS X System elif sys.platform == "win32": def clear(): os.system('cls') # On Windows System

clear()

Maximum length of password needed.

This can be changed to suit your password length.

MAX_LEN = 1024

Declare arrays of the character that we need in out password.

Represented as chars to enable easy string concatenation.

DIGITS = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

LOCASE_CHARACTERS = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

UPCASE_CHARACTERS = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'M', 'N', 'O', 'p', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

SYMBOLS = [' ', '!', '"', '#', '$', '%', '&', "'", '(', ')', '*', '+', ',', '-', '.', '/', ':', ';', '<', '=', '>', '?', '@', '[', '\', ']', '^', '_', '`', '{', '|', '}', '~']

Combines all the character arrays above to form one array.

COMBINED_LIST = DIGITS + UPCASE_CHARACTERS + LOCASE_CHARACTERS + SYMBOLS

Randomly select at least one character from each character set above.

rand_digit = random.choice(DIGITS) rand_upper = random.choice(UPCASE_CHARACTERS) rand_lower = random.choice(LOCASE_CHARACTERS) rand_symbol = random.choice(SYMBOLS)

Combine the character randomly selected above

at this stage, the password contains only 4 characters but

we want a 12-character password.

temp_pass = rand_digit + rand_upper + rand_lower + rand_symbol

Now that we are sure we have at least one character from each

set of characters, we fill the rest of

the password length by selecting randomly from the combined

list of character above.

for x in range(MAX_LEN - 4): temp_pass = temp_pass + random.choice(COMBINED_LIST)

    # Convert temporary password into array and shuffle to
    # prevent it from having a consistent pattern
    # where the beginning of the password is predictable.
    temp_pass_list = array.array('u', temp_pass)
    random.shuffle(temp_pass_list)

Traverse the temporary password array and append the chars

to form the password.

password = "" for x in temp_pass_list: password = password + x

Hashing password with SHA3-256 algorithm.

hash = hashlib.sha3_256() hash.update(password.encode())

privKeyStr = "0x"+hash.hexdigest() # Random Private Key at hex_string. privKey = int(privKeyStr, 16) # Random Private Key at hex_value.

secp256k1 domain parameters.

Pcurve = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F # The proven prime. Acurve = 0x0000000000000000000000000000000000000000000000000000000000000000 # These two defines the elliptic curve. y^2 = x^3 + int(Acurve) * x + int(Bcurve). Bcurve = 0x0000000000000000000000000000000000000000000000000000000000000007 Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 GPoint = (int(Gx),int(Gy)) # This is our generator point. N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field.

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

def ECAdd(a,b): # Point Addition, invented for EC. LambdaAdd = ((b[1] - a[1]) modinv(b[0] - a[0],int(Pcurve))) % int(Pcurve) x = (LambdaAdd LambdaAdd - a[0] - b[0]) % int(Pcurve) y = (LambdaAdd * (a[0] - x) - a[1]) % int(Pcurve) return (x,y)

def ECDouble(a): # Point Doubling, invented for EC. LamdaDouble = ((3 a[0] a[0] + int(Acurve)) modinv((2 a[1]), int(Pcurve))) % int(Pcurve) x = (LamdaDouble LamdaDouble - 2 a[0]) % int(Pcurve) y = (LamdaDouble * (a[0] - x) - a[1]) % int(Pcurve) return (x,y)

def ECMultiply(GenPoint,privKeyHex): # Doubling & Addition. Not true multiplication. if privKeyHex == 0 or privKeyHex >= N: raise Exception("Invalid Private Key") privKeyBin = str(bin(privKeyHex))[2:] Q=GenPoint for i in range (1, len(privKeyBin)): Q=ECDouble(Q); if privKeyBin[i] == "1": Q=ECAdd(Q,GenPoint); return (Q)

publicKey = ECMultiply(GPoint,privKey)

print() print("--------------------------------------------------------------------------------------------------------------------------------------------") print() print(" 'Random Password' currently set with '"+str(MAX_LEN)+"' characters:") print() print (" "+password[0:128]) print (" "+password[128:256]) print (" "+password[256:384]) print (" "+password[384:512]) print (" "+password[512:640]) print (" "+password[640:768]) print (" "+password[768:896]) print (" "+password[896:1024]) print() print("--------------------------------------------------------------------------------------------------------------------------------------------") print() print (" 'Private Key' derived from Hashed 'Random Password' (64 characters hexadecimal [0-9A-F], hashed by SHA3-256):") print() print (" "+str(hex(privKey)[2:]).zfill(32).upper()) print() print("--------------------------------------------------------------------------------------------------------------------------------------------") print() print (" 'Public Key' derived from 'Private Key' using 'secp256k1 elliptic curve' (uncompressed, 130 characters hexadecimal [0-9A-F])") print (" [prefix = '04'] + [32 bytes of X coordinate] + [32 bytes of Y coordinate]:") print() print (" "+"04"+str(hex(publicKey[0])[2:]).zfill(64).upper()+str(hex(publicKey[1])[2:]).zfill(64).upper()) print() print("--------------------------------------------------------------------------------------------------------------------------------------------") print() if publicKey[1] % 2 == 1: # If the Y coordinate of the Public Key is odd. prefix = "'03'" else: # If the Y coordinate of the Public Key is even. prefix = "'02'" print (" 'Public Key' derived from 'Private Key' using 'secp256k1 elliptic curve' (compressed, 66 characters hexadecimal [0-9A-F])") print (" [prefix = " + prefix + "] + [32 bytes of X coordinate]:") print() if publicKey[1] % 2 == 1: # If the Y coordinate of the Public Key is odd. print (" "+"03"+str(hex(publicKey[0])[2:]).zfill(64).upper()) else: # If the Y coordinate of the Public Key is even. print (" "+"02"+str(hex(publicKey[0])[2:]).zfill(64).upper()) print() print("--------------------------------------------------------------------------------------------------------------------------------------------") print()

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHubhttps://github.com/wobine/blackboard101/issues/14#issuecomment-818453813, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AH6VPTEYK5ZMCLP4ZPIBXEDTIPKTDANCNFSM4EFITDTQ.