How to earn one ether by writing a simple program - Ethereum Riddle

Hello Steemit community!

My name is Jake Lin (Chinese Name: 林永坚), I am new to Steemit. I am a Chinese and living in Melbourne, Australia. I am a dad of two awesome kids 👦🏻 & 👶🏻. I am a Mobile Developer, I code Swift and Kotlin for living and fun. I like to share and open source. I spoke at conferences like YOW! Connected, /dev/world and GMTC. I open source some popular projects like IBAnimatable, Swift Weather and SaveTheDot. More stars 🌟 than EOS project 🤣. Now I spend most of my spare time (after kids bedtime) on coding smart contracts using Solidity and DAaps using React. OK, that's me. In short: A dad can code 😁

Ethereum Riddle

In the lunisolar Chinese calendar, the fifteenth day of the first month (15th of January) is the Lantern Festival. During the Lantern Festival, people go out at night to carry paper lanterns and solve riddles on the lanterns. Someone posted a crypto riddle for Lantern Festival this year as below:

Disclaimer: I don't have any relationship with the person posted this riddle.

The Riddle is in Chinese, we can use Google Translate app to translates it into something like:

OK, let's translate it properly.

There is an Ethereum private key 0x1c2bbd4fd5627db7a2cd3d2c16737826335bdcf2333ff2c212bcd222223265ff, but it has been changed two and only two hexadecimal numbers. If we can correct those two hex, we can generate the target address 0x7858121D26cE162011C97F0fd38c8CfB0859796c and transfer the ether out of this account.

Terms

Before we move on to the fun part - coding, let's go through some terms we will use in the code.

Wallet

Ethereum Wallet stores some information like the private key and the public key to allow the user access the fund. Wallet just stores the information, it doesn't store the cryptos like bitcoin or ether. It is similar to when we have the account number and password for our saving account, then we can access our money. But the money is not physically stored on our debit card.

Private key

Ethereum private key is a number between 1 to 2^256-1. e.g. 0x1c2bbd4fd5627db7a2cd3d2c16737826335bdcf2333ff2c212bcd222223265ff We use it with public key for encryption and decryption. We will talk about the public key in the next section. It's like the password for your saving account. Anyone has your private key, they can access the fund. We should never disclose our private key to anyone else.

Public key

A public key is a byte array of size 64. It can be generated from a private key. For example, we can generate the public key 0xd04c1579c26007f1f7e08ed056dc38007977fa8a8f89cc1ed46c47ad64d25faf207778e9cfffc4b8a6afe389793619858f3457ce35a775f0361b195e5564830f from the private key as mentioned above. But we can't revert the private key from the public key. The public key is like the saving account number, we can share it with the others.

Cryptography

Why do we have the private key and public key? Let's have a look how cryptography works. Cryptography is a method of storing and transmitting data in a particular form so that only those for whom it is intended can read and process it. Think about a store: Alice wants to pass some message to Bob but doesn't want the other read it without permission.

Symmetric cryptography

One way is to use symmetric cryptography.

In this method, Alice uses her private key to encrypt the clear text to ciphertext. Then transmit the ciphertext over the Internet to Bob. Then Bob uses Alice's private key to decrypt the ciphertext back to the clear text. Although some others on the Internet receive the ciphertext, they still can't read the clear text unless they obtain Alice's private key. But Alice has to share her private key to the public. There is a security issue for her when transmitting the private key over the Internet. That's why we have asymmetric cryptography.

Asymmetric cryptography

Asymmetric cryptography is similar to symmetric cryptography but it uses a pair of keys: a private key and a public key.

In this case, Alice uses her private to encrypt. But Bob uses Alice's public key to decrypt instead of the private key. Then Alice doesn't need to worry about leaking her private key.

Asymmetric cryptography is broadly used in the Internet and crypto ecosystem. There are two main use cases: encryption and digital signature.

Encryption

We can use asymmetric cryptography method for encryption. Because Alice can share her public key to anyone. Bob can encrypt the message using Alice's public key and publish on the Internet, anyone can receive the ciphertext but only Alice can decrypt it back to clear text with her private key.

Digital signature

Another popular case is to use asymmetric cryptography for digital signature. Alice can encrypt her digital signature to ciphertext and transmit both the ciphertext and the signature (in clear text) to Bob. Bob can decrypt the ciphertext back to clear text by using Alice's public key, then compare the clear text with the transmitted signature. If they are the same, it means the ciphertext was signed by Alice because only Alice can sign it with her private key.

Address

An Ethereum address is a 40 character hex string. e.g. 0x7858121D26cE162011C97F0fd38c8CfB0859796c. The address is generated by a public key. But we can't revert it back the public key. We can use it for receiving ethers. It's similar to the nickname of the account number because as you have seen above, the public key (account number) is way longer than the address.

OK, enough boring glossary, let's move on to the fun part - coding 😉

Coding time - the fun part

The requirements

Before start coding, let's figure out what should we do. As we mentioned before, there is no way to revert the private key from an address or a public key. We need to do it the opposite way. We can swap two hex in the provided private key 0x1c2bbd4fd5627db7a2cd3d2c16737826335bdcf2333ff2c212bcd222223265ff and use the swapped private key to generate the address. Then compare the generated address with the target address 0x7858121D26cE162011C97F0fd38c8CfB0859796c. If they match. It means we have found the correct private key 🎉 , hooray.

That requires two steps:

1. Swap two hex with the original private key each time.
2. Generate the address from a private key.

How to generate the address from a private key

Let's start with the easy one - generating the address from a private key. We can implement it in any programming language. The code below is written in JavaScript.

const EC = require('elliptic').ec
const BN = require('bn.js')
const ec = new EC('secp256k1')
const G = ec.g; // Generator point
const keccak256 = require('js-sha3').keccak256

// Refer to https://etherworld.co/2017/11/17/understanding-the-concept-of-private-key-public-key-and-address-in-ethereum-blockchain
/// Get public key from private key. `privateKey` is private key in buffer
const getPublickKeyFromPrivateKey = (privateKey) => {
    if (!(privateKey instanceof Buffer)) {
        throw new TypeError('param privateKey must be of Buffer type');
    }
    
    const pk = new BN(privateKey) // private key as big number
    const publicPoint = G.mul(pk) // EC multiplication to determine public point 
    const x = publicPoint().toBuffer() //32 bit x co-ordinate of public point 
    const y = publicPoint().toBuffer() //32 bit y co-ordinate of public point 
    
    const publicKey = Buffer.concat([x,y])
    return publicKey
}

/// Get address from public key. `publicKey` is public key in buffer
const getAddressFromPublicKey = (publicKey) => {
    if (!(publicKey instanceof Buffer)) {
        throw new TypeError('param privateKey must be of Buffer type');
    }
    
    const hash = keccak256(publicKey)
    const address = Buffer.from(hash, 'hex').slice(-20)
    return address
}

/// Get address from private key. `privateKey` is private key in buffer
const getAddressFromPrivateKey = (privateKey) => {
    if (!(privateKey instanceof Buffer)) {
        throw new TypeError('param privateKey must be of Buffer type');
    }

    const publicKey = getPublickKeyFromPrivateKey(privateKey)
    const address = getAddressFromPublicKey(publicKey)
    return address
}

To generate the address from a private key, we can find the technical details in The "Yellow Paper": Ethereum's formal specification. Firstly, we need to get the public key from the provided private key. As we can see in getPublickKeyFromPrivateKey method, we use Elliptic Curve Cryptography to generate the x and y co-ordinate of the public point, then concat them together to be 64 bytes long public key like 0xd04c1579c26007f1f7e08ed056dc38007977fa8a8f89cc1ed46c47ad64d25faf207778e9cfffc4b8a6afe389793619858f3457ce35a775f0361b195e5564830f

The last step is to derive the Ethereum address from the public key. As described in the "Yellow Paper", Ethereum uses the Keccak-256 hash function instead of SHA-3. As seen in getAddressFromPublicKey, we use keccak256 method to hash the public key and take the last 20 bytes (40 hex characters long) as the address.

That's it. It's very straightforward if we don't go forward with the technical details. If you are interested in those details, please go ahead to check out the "Yellow Paper".

How to swap two hex with the original private key

As described in the riddle, two hex of the provided private key has been replaced. We can try to swap two hex each time, and then generate the address and match it with the target address.

To achieve that, we introduce two sticks (blue and red). Each one has the hex number from 0 to f. Firstly, we place the first blue stick to the first hex of the original private key. And then we place the second red stick to the second hex as below:

The first two hex has been swapped to 002bbd4fd5627db7a2cd3d2c16737826335bdcf2333ff2c212bcd222223265ff. Now we use it to generate the address and compare. If we are not lucky enough to match the target address. Then we move the red stick up one hex like:

We repeat the generation and compression steps until the red stick hits f. We need to move the red stick toward the right to the third hex of the original private key like:

Then we keep doing the generation and compression steps by moving the red stick up and right until we hit the last hex of the original private key with f like:

In the case, it means the first hex of the private key must not be 0, We need to move the first blue stick one up to 1 and move the second red stick back to the second hex like:

Then we keep doing the compression and moving the red up and right (only one move a time).

After we move the first blue stick to f in the first hex and we are still not lucky enough, we need to move the blue stick to the second hex and reset to 0 then move the red stick to third hex as well like:

We repeat the steps - moving one at a time and comparing with the target address - again and again. We eventually will find out the target address. Here is the code:

const findPrivateKeyForAddress = (privateKeyStr, addressStr) => {
    if (typeof privateKeyStr !== 'string') {
        throw new TypeError('param privateKeyStr must be of String');
    } else if (typeof addressStr !== 'string') {
        throw new TypeError('param addressStr must be of String');
    }

    const hexStr = '0123456789abcdef'

    const targetAddress = Buffer.from(addressStr, 'hex')

    const privateKeyLength = privateKeyStr.length
    
    // Place the first blue stick from first to the second last of the hex
    for (let i = 0; i < privateKeyLength - 1; i++) {
        // Swap the first blue stick with a new hex (from `0` to `f`)
        for (const c1 of hexStr) {
            // Place the second red stick from one right of the placed blue stick the last of the hex
            for (let j = i + 1; j < privateKeyLength ; j++) {
                // Swap the second red stick with a new hex (from `0` to `f`)
                for (const c2 of hexStr) {
                    const privateKeyInChars = privateKeyStr.split('')
                    privateKeyInChars[i] = c1
                    privateKeyInChars[j] = c2
                    
                    // Generate the Ethereum address from the swapped private key
                    const privateKey = Buffer.from(privateKeyInChars.join(''), 'hex')
                    const address = getAddressFromPrivateKey(privateKey)
                    // Compare the generated address with the target address
                    if (address.equals(targetAddress)) {
                        // Bingo, we found it.
                        console.log('💥💥💥 PRIVATE KEY FOUND 💥💥💥')
                        return privateKey.toString('hex')
                    }
                }

            }
        }
    }
}

There are four for loops in the code, the first loop is used for moving the first blue stick from first to the second last of the hex ➡️. The second loop is used for moving the first blue stick with a new hex (from 0 to f) ⬆️. The third loop is used for moving the second red stick from one right of the placed blue stick the last of the hex ➡️. The fourth loop is used for moving the second red stick with a new hex (from 0 to f)⬆️. Each time we generate the Ethereum address from the swapped private key and then compare it with the target address. Return the private key when they are matched.

All the code can be found on GitHub | ethereum-riddle

Transferring the fund out

The last and most important step is to transfer out the fund as the reward. We can import the private key in any Ethereum compatible wallet like MetaMask.

Then We can transfer out the fund like

Unfortunately, when I saw this riddle, the fund had been transferred out. As a reward, I transferred myself 0.00008888 Ether 😁, we can find the transaction on etherscan.io

Thanks 👐

Thanks for your time, I hope you enjoy it. You can find me on:

• GitHub: https://github.com/JakeLin
• Dribble: https://dribbble.com/Jake_Lin
• Twitter: https://twitter.com/Jake_Lin
• WeChat: jakelinau
• Steemit: https://steemit.com/@jakelin

Small donation will be appreciated

• BTC: 3DxxE5Y8QMVLfeKzQgJ3nh4f6mxbaPVVUJ
• ETH: 0x48D9F0AD5BF1024821362871E04AF456Ad264F14