Scalar multiplication in elliptic curves in C

PrivateKey.c

//Full guide: https://leetarxiv.substack.com/p/hacking-dormant-bitcoin-wallets-c
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <gmp.h>
#include <secp256k1.h>
#include <openssl/sha.h>
#include <openssl/ripemd.h>

//Run: clear && gcc PrivateKey.c -lsecp256k1 -lcrypto -lgmp -o m.o && ./m.o
typedef struct elliptic_curve_point_struct *EllipticCurvePoint;
struct elliptic_curve_point_struct
{
	mpz_t x;
	mpz_t y;
	int infinity;	
};

EllipticCurvePoint CreatePoint()
{
	EllipticCurvePoint point = malloc(sizeof(struct elliptic_curve_point_struct));
	mpz_init(point->x);
	mpz_init(point->y);
	point->infinity = 0;
	return point;
}

void CopyPoint(EllipticCurvePoint source, EllipticCurvePoint destination)
{
	mpz_set(destination->x, source->x);
	mpz_set(destination->y, source->y);
	destination->infinity = source->infinity;
}

int TestPointEquality(EllipticCurvePoint a, EllipticCurvePoint b)
{
	if(a->infinity && b->infinity) return 1;
	if(a->infinity || b->infinity) return 0;
	return mpz_cmp(a->x, b->x) == 0 && mpz_cmp(a->y, b->y) == 0;	
}

int TestLSBParity(mpz_t y)
{
	return mpz_tstbit(y, 0); // Returns 1 if odd, 0 if even
}

void DestroyPoint(EllipticCurvePoint point)
{
	if(point)
	{
		mpz_clear(point->x);
		mpz_clear(point->y);
		free(point);
	}
}

bool AddCurvePoints(EllipticCurvePoint R, EllipticCurvePoint P, EllipticCurvePoint Q, mpz_t primeNumber)
{
	//Case 0: Handle Points at infinity
	if(P->infinity != 0){CopyPoint(Q,R);return true;}
	if(Q->infinity != 0){CopyPoint(P,R);return true;}
	
	//Case 1: Handle P->x == Q->x
	if(mpz_cmp(P->x, Q->x) == 0) 
	{
		//Case 1.1: X values similar but Y differ or 0
		if(mpz_cmp(P->y, Q->y) != 0 || mpz_cmp_ui(P->y, 0) == 0){R->infinity = 1;return true;}
		
		//Case 1.2: Point Doubling
		mpz_t s, num, den, den_inv, tmp;
		mpz_inits(s, num, den, den_inv, tmp, NULL);
		//num = x^2
		mpz_mul(num, P->x, P->x);
		//num = 3x^2   
		mpz_mul_ui(num, num, 3);       

		//den = 2y
		mpz_mul_ui(den, P->y, 2); 
		//Find denominator inverse     
		if(!mpz_invert(den_inv, den, primeNumber)){R->infinity = 1;mpz_clears(s, num, den, den_inv, tmp, NULL);return true;}

		//s = (3x^2)/(2y)
		mpz_mul(s, num, den_inv);     
		mpz_mod(s, s, primeNumber);

		//x3 = s^2 - 2x
		mpz_mul(tmp, s, s);
		mpz_sub(tmp, tmp, P->x);
		mpz_sub(tmp, tmp, Q->x);
		mpz_mod(R->x, tmp, primeNumber);

		//y3 = s*(x - x3) - y
		mpz_sub(tmp, P->x, R->x);
		mpz_mul(tmp, s, tmp);
		mpz_sub(tmp, tmp, P->y);
		mpz_mod(R->y, tmp, primeNumber);

		R->infinity = 0;

		mpz_clears(s, num, den, den_inv, tmp, NULL);
		return true;

	}
	//Case 2: Handle P != Q (Point Addition)
	else
	{
		mpz_t s, num, den, den_inv, tmp;
		mpz_inits(s, num, den, den_inv, tmp, NULL);
		
		//num = y2 - y1
		mpz_sub(num, Q->y, P->y);
		//den = x2 - x1   
		mpz_sub(den, Q->x, P->x); 
		//Find inverse of denominator mod p    
		if(!mpz_invert(den_inv, den, primeNumber)){R->infinity = 1;mpz_clears(s, num, den, den_inv, tmp, NULL);return true;}

		//s = (y2 - y1)/(x2 - x1) mod p
		mpz_mul(s, num, den_inv);mpz_mod(s, s, primeNumber);

		//x3 = s^2 - x1 - x2 mod p
		mpz_mul(tmp, s, s);mpz_sub(tmp, tmp, P->x);mpz_sub(tmp, tmp, Q->x);mpz_mod(R->x, tmp, primeNumber);

		//y3 = s*(x1 - x3) - y1
		mpz_sub(tmp, P->x, R->x);mpz_mul(tmp, s, tmp);mpz_sub(tmp, tmp, P->y);mpz_mod(R->y, tmp, primeNumber);
		R->infinity = 0;
		//Free memory
		mpz_clears(s, num, den, den_inv, tmp, NULL);
		return true;
	}
}
void PrintCompressedPublicKey(EllipticCurvePoint P)
{
	uint8_t buffer[32] = {0};
	size_t count = 0;
	mpz_export(buffer + (32 - (mpz_sizeinbase(P->x, 2) + 7) / 8), &count, 1, 1, 1, 0, P->x);
	
	int parity = TestLSBParity(P->y);
	printf("Compressed Public Key: %02X", parity ? 0x03 : 0x02);
	for(int i = 0; i < 32; i++) printf("%02X", buffer[i]);
	printf("\n");
}
void CurveScalarMultiplication(EllipticCurvePoint resultant, EllipticCurvePoint generator, mpz_t privateKey, mpz_t primeNumber)
{
	//Create pointAtInfinity, temp0
	EllipticCurvePoint pointAtInfinity = CreatePoint();
	pointAtInfinity->infinity = 1;  
	
	EllipticCurvePoint temp0 = CreatePoint();
	
	//Find no. of bits in private key
	size_t binaryLength = mpz_sizeinbase(privateKey, 2);
	
	//loop from MSB to LSB
	for(ssize_t i = binaryLength - 1; i >= 0; --i)
	{
		//temp0 = 2*pointAtInfinity
		AddCurvePoints(temp0, pointAtInfinity, pointAtInfinity, primeNumber);
		CopyPoint(temp0, pointAtInfinity);
		
		//Test the current bit's parity
		if(mpz_tstbit(privateKey, i) != 0)
		{
			//temp0 = pointAtInfinity + generator
			AddCurvePoints(temp0, pointAtInfinity, generator, primeNumber);
			CopyPoint(temp0, pointAtInfinity);	
		}	
	}
	//Save pointAtInfinity to the result variable
	CopyPoint(pointAtInfinity, resultant);
	
	//Free memory
	DestroyPoint(pointAtInfinity);
	DestroyPoint(temp0);
}

void TestECPoint()
{	
	//Curve properties
	char *primeNumberHexadecimal = "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F";	
	char *generatorXHexadecimal  = "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798";
	char *generatorYHexadecimal = "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8";

	mpz_t primeNumber, privateKey;
	
	//Set prime number in base 16
	mpz_init_set_str(primeNumber, primeNumberHexadecimal, 16);
	//Set private key in base 10
	mpz_init_set_str(privateKey, "5", 10);
	
	//Create Generator and Result points
	EllipticCurvePoint generator = CreatePoint();
	EllipticCurvePoint resultant = CreatePoint();
	
	//Set generator X and Y values and infinity = 0
	mpz_set_str(generator->x, generatorXHexadecimal, 16);
	mpz_set_str(generator->y, generatorYHexadecimal, 16);
	generator->infinity = 0;
	
	//Multiply Generator by private key modulo primeNumber.
	CurveScalarMultiplication(resultant, generator, privateKey, primeNumber);
	gmp_printf("Public Key X: %Zx\n", resultant->x);
	gmp_printf("Public Key Y: %Zx\n", resultant->y);
	PrintCompressedPublicKey(resultant);
	
	DestroyPoint(generator);
	DestroyPoint(resultant);
	mpz_clears(primeNumber, privateKey,NULL);
}

const char *BASE58_ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
void EncodeInBase58(size_t inputLength, uint8_t *input, size_t outputLength, char *output)
{
	uint8_t temp[32] = {0};memcpy(temp, input, inputLength);
	uint8_t result[64] = {0};int resultLength = 0;

	for(size_t i = 0; i < inputLength; i++)
	{
		int carry = temp[i];
		for(int j = 0; j < resultLength || carry; j++)
		{
			if(j == resultLength) resultLength++;
			carry += 256 * result[j];
			result[j] = carry % 58;
			carry /= 58;
		}
	}

	int leading_zeros = 0;
	for(size_t i = 0; i < inputLength && input[i] == 0; i++) {output[leading_zeros++] = '1';}
	for(int i = resultLength - 1; i >= 0; i--) {output[leading_zeros++] = BASE58_ALPHABET[result[i]];}
	output[leading_zeros] = '\0';
}
void PrintHexadecimalString(size_t stringLength, uint8_t *string)
{
	for(size_t i = 0; i < stringLength; i++)
	{
		printf("%02X", string[i]);
	}
	printf("\n");
}

//Assumes publicKeyString is 33 bytes
//Assumes generatedAddress is 64 bytes
void PublicKeyToBitcoinWalletAddress(uint8_t *publicKeyString, char *generatedAddress)
{
	uint8_t sha256Hash[32];
	SHA256(publicKeyString, 33, sha256Hash);

	uint8_t ripemd160Hash[20];
	RIPEMD160(sha256Hash, 32, ripemd160Hash);

	uint8_t versionedPayload[21];
	versionedPayload[0] = 0x00; // version byte for mainnet
	memcpy(versionedPayload + 1, ripemd160Hash, 20);

	uint8_t checksumInput[25];
	memcpy(checksumInput, versionedPayload, 21);
	
	uint8_t hash1[32], hash2[32];
	SHA256(checksumInput, 21, hash1);
	SHA256(hash1, 32, hash2);
	memcpy(checksumInput + 21, hash2, 4);

	EncodeInBase58(25, checksumInput, 64, generatedAddress);
}

int main()
{
	TestECPoint();
	//Initialize secpContext
	secp256k1_context *secpContext = secp256k1_context_create(SECP256K1_CONTEXT_SIGN);
	
	//Set upper bound and target wallet address
	uint32_t upperBound = 0;
	char *walletAddress = "19ZewH8Kk1PDbSNdJ97FP4EiCjTRaZMZQA";
	printf("%s\n", walletAddress);
	
	//Test different private keys	
	for(uint8_t privateKey = 1; privateKey <= upperBound; privateKey++)
	{
		uint8_t privateKeyString[32] = {0};
		privateKeyString[31] = privateKey;
		assert(secp256k1_ec_seckey_verify(secpContext, privateKeyString) != 0);
		printf("\nPrivate Key:\n");PrintHexadecimalString(32, privateKeyString);
		
		//Generate public key
		secp256k1_pubkey publicKey;
		size_t publicKeyLength = 33;
		uint8_t publicKeyString[33];
		
		assert(secp256k1_ec_pubkey_create(secpContext, &publicKey, privateKeyString) != 0);
		secp256k1_ec_pubkey_serialize(secpContext, publicKeyString, &publicKeyLength, &publicKey, SECP256K1_EC_COMPRESSED);
		printf("Public Key:\n");PrintHexadecimalString(33, publicKeyString);
		
		//Generate wallet address
		char generatedAddress[64];
		PublicKeyToBitcoinWalletAddress(publicKeyString, generatedAddress);
		printf("Generated Address:%s\n",generatedAddress);
		if(strcmp(generatedAddress, walletAddress) == 0)
		{
			printf("**MATCH FOUND: Private Key = %u\n", privateKey);
			break;
		}
	}
	
	//Destroy secpContext
	secp256k1_context_destroy(secpContext);
}