Merging split keys - addition and multiplication of two elliptic curves \ stacker news ~bitcoin

Hello dear hackerplebs,

i' ve posted my issue on bitcoin.stackexchange, i need a quick solution and i want to pay for it.

post the solution down here for the bounty and on the following link - or i will:

https://bitcoin.stackexchange.com/questions/119676/vanity-address-merging-split-keys-addition-and-multiplication-of-two-elliptic

Here is the issue:

i try to refactor js code for merging split keys to get a privKey for a vanity address. For better read/understanding, for updated packages (bitcoinjs-lib) and maybe integrations into wallets. Here is the code i want to refactoring https://github.com/sashmaaan/VanityAddressMerger/blob/master/src/sashmaaan.vmerge.js

given: vanityAddress, privkey, partialPrivkey

There are 6 cases/mathematical operations i've identified to get the right privatekey, and it should return 18 combined-privatekeys, but i get 23 then i try to find the one with the right derived address that is the same as the vanityAddress.

So i think there must be something wrong with the constants n or lambda1 and lambda2, or negatiation of the bigints.

The previous code uses a old version of bitcoinjs with deprecated functions ECKey so i tried to use ECPair but i am not shure if its used right in the code below:

import * as bitcoin from "bitcoinjs-lib";
import { ECPairFactory } from 'ecpair';
import * as ecc from 'tiny-secp256k1';

const ECPair = ECPairFactory(ecc);
import bigInt from "big-integer";
const orderBigInt = bigInt('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141', 16);
const n = bigInt("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16);

const lambdaKey = bigInt('5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72', 16)
/* const lambdaKeyBuffer =  Buffer.from(lambdaBigInt, 'hex');
const lambdaKey = ECPair.fromPrivateKey(lambdaKeyBuffer); */
const lambda2Key = bigInt('ac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce', 16)
/* const lambdaKeyBuffer2 = Buffer.from(lambdaBigInt2, 'hex');
const lambda2Key = ECPair.fromPrivateKey(lambdaKeyBuffer2);
 */

function mergeKeys(addr, privKey, partialPrivKey) {
    if (privKey === partialPrivKey) {
        throw new Error('Own private key and partial private key are the same');
    }

    if (!privKey || !partialPrivKey) {
        throw new Error('One of the private keys is null');
    }

    const ownKeyPair = ECPair.fromWIF(privKey);
    const partialKeyPair = ECPair.fromWIF(partialPrivKey);
    const ownKey = bigInt(ownKeyPair.privateKey.toString('hex'), 16);
    const partPrivKey = bigInt(partialKeyPair.privateKey.toString('hex'), 16);

    const keyPairs = [ownKey, partPrivKey];
    function negateKey(key) {
        return n.subtract(key).mod(n);
    }

    // Try merging private keys both ways (addition and multiplication)
    for (const keyPair2 of keyPairs) {
        for (const keyPair1 of keyPairs) {
            // No sym, no endo
            const mergedPrivateKey1 = keyPair1.add(keyPair2).mod(n);
            const privateKeyHex1 = mergedPrivateKey1.toString(16).padStart(64, '0');
            const privateKeyBuffer1 = Buffer.from(privateKeyHex1, 'hex');
            const mergedKeyPair1 = ECPair.fromPrivateKey(privateKeyBuffer1, { network: bitcoin.networks.bitcoin });
            console.log(mergedKeyPair1.toWIF(), 1)

            // No sym, endo 1
            const mergedPrivateKey2 = keyPair1.multiply(lambdaKey).mod(n).add(keyPair2).mod(n);
            const privateKeyHex2 = mergedPrivateKey2.toString(16).padStart(64, '0');
            const privateKeyBuffer2 = Buffer.from(privateKeyHex2, 'hex');
            const mergedKeyPair2 = ECPair.fromPrivateKey(privateKeyBuffer2, { network: bitcoin.networks.bitcoin });
            console.log(mergedKeyPair2.toWIF(), 2)

            // No sym, endo 2
            const mergedPrivateKey3 = keyPair1.multiply(lambda2Key).mod(n).add(keyPair2).mod(n);
            const privateKeyHex3 = mergedPrivateKey3.toString(16).padStart(64, '0');
            const privateKeyBuffer3 = Buffer.from(privateKeyHex3, 'hex');
            const mergedKeyPair3 = ECPair.fromPrivateKey(privateKeyBuffer3, { network: bitcoin.networks.bitcoin });
            console.log(mergedKeyPair3.toWIF(), 3)

            // Symmetric, no endo
            let mergedPrivateKey4 = negateKey(keyPair1).negate().add(keyPair2).mod(n)
            mergedPrivateKey4 = negateKey(mergedPrivateKey4)
            //mergedPrivateKey4 = negate(mergedPrivateKey4)
            const privateKeyHex4 = mergedPrivateKey4.toString(16).padStart(64, '0');
            const privateKeyBuffer4 = Buffer.from(privateKeyHex4, 'hex');
            const mergedKeyPair4 = ECPair.fromPrivateKey(privateKeyBuffer4, { network: bitcoin.networks.bitcoin });
            console.log(mergedKeyPair4.toWIF(), 4)

            // Symmetric, endo 1
            const mergedPrivateKey5 = keyPair1.multiply(lambdaKey).mod(n).negate().add(orderBigInt).add(keyPair2).mod(n);
            const privateKeyHex5 = mergedPrivateKey5.toString(16).padStart(64, '0');
            const privateKeyBuffer5 = Buffer.from(privateKeyHex5, 'hex');
            const mergedKeyPair5 = ECPair.fromPrivateKey(privateKeyBuffer5, { network: bitcoin.networks.bitcoin });
            console.log(mergedKeyPair5.toWIF(), 5)

            // Symmetric, endo 2
            const mergedPrivateKey6 = keyPair1.multiply(lambda2Key).mod(n).negate().add(orderBigInt).add(keyPair2).mod(n);
            const privateKeyHex6 = mergedPrivateKey6.toString(16).padStart(64, '0');
            const privateKeyBuffer6 = Buffer.from(privateKeyHex6, 'hex');
            const mergedKeyPair6 = ECPair.fromPrivateKey(privateKeyBuffer6, { network: bitcoin.networks.bitcoin });
            console.log(mergedKeyPair6.toWIF(), 6)

            // Generate addresses for each merged key pair
            const address1 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair1);
            const address2 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair2);
            const address3 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair3);
            const address4 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair4);
            const address5 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair5);
            const address6 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair6);

            // Check if any of the addresses match the target address
            if (addr === address1) return mergedKeyPair1.toWIF();
            if (addr === address2) return mergedKeyPair2.toWIF();
            if (addr === address3) return mergedKeyPair3.toWIF();
            if (addr === address4) return mergedKeyPair4.toWIF();
            if (addr === address5) return mergedKeyPair5.toWIF();
            if (addr === address6) return mergedKeyPair6.toWIF();
        }
    }

    //throw new Error('Failed to find a valid merged private key.');
}

function getAddressFromKeyType(keyType, keyPair) {
    switch (keyType) {
        case "1":
            const addr = bitcoin.payments.p2pkh({ pubkey: keyPair.publicKey, network: bitcoin.networks.bitcoin }).address;
            return addr
        case "3":
            return bitcoin.payments.p2sh({ redeem: bitcoin.payments.p2wpkh({ pubkey: keyPair.publicKey }), network: bitcoin.networks.bitcoin }).address;
        case "b":
        case "B":
            return bitcoin.payments.p2wpkh({ pubkey: keyPair.publicKey, network: bitcoin.networks.bitcoin }).address;
        default:
            return null;
    }
}

const addr = '1btcxcVyqf8jfkscQmYPBGRurZQG8PMtb';
const privKey = 'KzNCSsMnhf34GBt91tSbgDAC2YKt6cuX2XDiRzZtC487koBUHh5N';
const partialPrivKey = 'Kyc35db3dauFrVLSDYWgmrqAQCEcPf1Xnkv9QbGWYboE3FkV7rMv';

//expected private key: L53BPaiJWm3wJ4APYRzHo6sTUTYc76YY7Kx6ScyTBRkrYJ1My3S4
// mergeKeys(addr, privKey, partialPrivKey);
try {
    const mergedPrivateKey = mergeKeys(addr, privKey, partialPrivKey);
    console.log('Merged Private Key (WIF Compressed):', mergedPrivateKey);
} catch (error) {
    console.error('Error:', error.message, error)
}

Have Fun by catching the bounty!

150,000 sats bounty

0 sats \ 0 replies \ @cyphrRabbit OP 1 Oct 2023

After long conversations with chatGPT i found the problem...

It was the Symmetric no endo operation. the negotiation was doubled and if i made it once the key was invalid because it was not in the valid range It has to check if the privkey is valid:

  function isValidPrivateKey(key) {
        return key > 0 && key < n;
    }

...

 // Symmetric, no endo  
            let mergedPrivateKey4 = negateKey(keyPair1).add(keyPair2).mod(n);
            let mergedKeyPair4;
            if (isValidPrivateKey(mergedPrivateKey4)) {
                const privateKeyHex4 = mergedPrivateKey4.toString(16).padStart(64, '0');
                const privateKeyBuffer4 = Buffer.from(privateKeyHex4, 'hex');
                mergedKeyPair4 = ECPair.fromPrivateKey(privateKeyBuffer4, { network: bitcoin.networks.bitcoin });
                const address4 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair4);
                if (addr === address4) return mergedKeyPair4.toWIF();
            }

i added the validation for each case. Now it works fine, feel free to test and review!

Here is the whole code: (uncomment the testing)

import * as bitcoin from "bitcoinjs-lib";
import { ECPairFactory } from 'ecpair';
import * as ecc from 'tiny-secp256k1';

const ECPair = ECPairFactory(ecc);
import bigInt from "big-integer";
const orderBigInt = bigInt('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141', 16);
const n = bigInt("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16);

const lambdaKey = bigInt('5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72', 16)
const lambda2Key = bigInt('ac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce', 16)

function negateKey(key) {
    return n.minus(key).mod(n);
}

function getAddressFromKeyType(keyType, keyPair) {
    switch (keyType) {
        case "1":
            const addr = bitcoin.payments.p2pkh({ pubkey: keyPair.publicKey, network: bitcoin.networks.bitcoin }).address;
            return addr
        case "3":
            return bitcoin.payments.p2sh({ redeem: bitcoin.payments.p2wpkh({ pubkey: keyPair.publicKey }), network: bitcoin.networks.bitcoin }).address;
        case "b":
        case "B":
            return bitcoin.payments.p2wpkh({ pubkey: keyPair.publicKey, network: bitcoin.networks.bitcoin }).address;
        default:
            return null;
    }
}

function mergeKeys(addr, privKey, partialPrivKey) {
    if (privKey === partialPrivKey) {
        throw new Error('Own private key and partial private key are the same');
    }

    if (!privKey || !partialPrivKey) {
        throw new Error('One of the private keys is null');
    }

    const ownKeyPair = ECPair.fromWIF(privKey);
    const partialKeyPair = ECPair.fromWIF(partialPrivKey);
    const ownKey = bigInt(ownKeyPair.privateKey.toString('hex'), 16);
    const partPrivKey = bigInt(partialKeyPair.privateKey.toString('hex'), 16);

    const keyPairs = [ownKey, partPrivKey];

    function isValidPrivateKey(key) {
        return key > 0 && key < n;
    }
    
    // Try merging private keys both ways (addition and multiplication)
    for (const keyPair2 of keyPairs) {
        for (const keyPair1 of keyPairs) {
            // No sym, no endo
            const mergedPrivateKey1 = keyPair1.add(keyPair2).mod(n);
            let mergedKeyPair1;
            if (isValidPrivateKey(mergedPrivateKey1)) {
                const privateKeyHex1 = mergedPrivateKey1.toString(16).padStart(64, '0');
                const privateKeyBuffer1 = Buffer.from(privateKeyHex1, 'hex');
                mergedKeyPair1 = ECPair.fromPrivateKey(privateKeyBuffer1, { network: bitcoin.networks.bitcoin });
                const address1 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair1);
                if (addr === address1) return mergedKeyPair1.toWIF();
            }
            // No sym, endo 1
            const mergedPrivateKey2 = keyPair1.multiply(lambdaKey).mod(n).add(keyPair2).mod(n);
            let mergedKeyPair2;
            if (isValidPrivateKey(mergedPrivateKey2)) {
                const privateKeyHex2 = mergedPrivateKey2.toString(16).padStart(64, '0');
                const privateKeyBuffer2 = Buffer.from(privateKeyHex2, 'hex');
                mergedKeyPair2 = ECPair.fromPrivateKey(privateKeyBuffer2, { network: bitcoin.networks.bitcoin });
                const address2 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair2);
                if (addr === address2) return mergedKeyPair2.toWIF();
            }
            // No sym, endo 2
            const mergedPrivateKey3 = keyPair1.multiply(lambda2Key).mod(n).add(keyPair2).mod(n);
            let mergedKeyPair3;
            if (isValidPrivateKey(mergedPrivateKey3)) {
                const privateKeyHex3 = mergedPrivateKey3.toString(16).padStart(64, '0');
                const privateKeyBuffer3 = Buffer.from(privateKeyHex3, 'hex');
                mergedKeyPair3 = ECPair.fromPrivateKey(privateKeyBuffer3, { network: bitcoin.networks.bitcoin });
                const address3 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair3);
                if (addr === address3) return mergedKeyPair3.toWIF();
            }

            // Symmetric, no endo  
            let mergedPrivateKey4 = negateKey(keyPair1).add(keyPair2).mod(n);
            let mergedKeyPair4;
            if (isValidPrivateKey(mergedPrivateKey4)) {
                const privateKeyHex4 = mergedPrivateKey4.toString(16).padStart(64, '0');
                const privateKeyBuffer4 = Buffer.from(privateKeyHex4, 'hex');
                mergedKeyPair4 = ECPair.fromPrivateKey(privateKeyBuffer4, { network: bitcoin.networks.bitcoin });
                const address4 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair4);
                if (addr === address4) return mergedKeyPair4.toWIF();
            }

            // Symmetric, endo 1
            const mergedPrivateKey5 = keyPair1.multiply(lambdaKey).mod(n).negate().add(orderBigInt).add(keyPair2).mod(n);
            let mergedKeyPair5;
            if (isValidPrivateKey(mergedPrivateKey5)) {
                const privateKeyHex5 = mergedPrivateKey5.toString(16).padStart(64, '0');
                const privateKeyBuffer5 = Buffer.from(privateKeyHex5, 'hex');
                mergedKeyPair5 = ECPair.fromPrivateKey(privateKeyBuffer5, { network: bitcoin.networks.bitcoin });
                const address5 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair5);
                if (addr === address5) return mergedKeyPair5.toWIF();
            }
            // Symmetric, endo 2
            const mergedPrivateKey6 = keyPair1.multiply(lambda2Key).mod(n).negate().add(orderBigInt).add(keyPair2).mod(n);
            let mergedKeyPair6;
            if (isValidPrivateKey(mergedPrivateKey5)) {
                const privateKeyHex6 = mergedPrivateKey6.toString(16).padStart(64, '0');
                const privateKeyBuffer6 = Buffer.from(privateKeyHex6, 'hex');
                mergedKeyPair6 = ECPair.fromPrivateKey(privateKeyBuffer6, { network: bitcoin.networks.bitcoin });
                const address6 = getAddressFromKeyType(addr.charAt(0), mergedKeyPair6);
                if (addr === address6) return mergedKeyPair6.toWIF();
            }
            

        }
    }

    throw new Error('Failed to find a valid merged private key.');
}


 // For testing

const vanity_address = '1btcxcVyqf8jfkscQmYPBGRurZQG8PMtb';
const privKeyorg = 'KzNCSsMnhf34GBt91tSbgDAC2YKt6cuX2XDiRzZtC487koBUHh5N';
const partialPrivKeyorg = 'Kyc35db3dauFrVLSDYWgmrqAQCEcPf1Xnkv9QbGWYboE3FkV7rMv';

//expected private key: L53BPaiJWm3wJ4APYRzHo6sTUTYc76YY7Kx6ScyTBRkrYJ1My3S4
// mergeKeys(vanity_address, privKeyorg, partialPrivKeyorg);
try {
    const mergedPrivateKey = mergeKeys(vanity_address, privKeyorg, partialPrivKeyorg);
    console.log('Merged Private Key (WIF Compressed):', mergedPrivateKey);
} catch (error) {
    console.error('Error:', error.message, error)
}