Profanity: Clarifications

Hi all! I have been asked several times about how Authors derived private key from public and started searching for information on this attack and found a very interesting discussion with its creators - I have compiled everything in this article, I hope no one has any questions! I found this dialogue very enlightening - here is the original link to the discussion but for your convenience I will bring it down without cuts and keeping the Author's punctuation and spelling! 

• Check out before reading: github.com/johguse/profanity/issues/61 ❕

Question:

How does one decrement a public key? (In the efficient manner section, it mentions “Repeatedly decrement them until they reach the seed public key.”)

Assuming, I have two private keys A and A’, where A’ is a single increment from A (e.g: A is [u8]: […, 0] and A’ is [u8]: […, 1]).

PublicKey(A) and PublicKey(A’) would be vastly different, right? How do I apply a decrement to PublicKey(A’) to get PublicKey(A)?

From what I understand from the blogpost:

Profanity does:

1. Generate a random seed N from set of 2**32 (problem here, small set)

2. Generate private key from seed N

3. Apply some deterministic function on generated private key to generate 2 million other private keys

4. Generate public keys for 2 million other private keys

5. Check addresses from public keys for vanity match

6. If no match, increment each of the 2 million private keys by 1

7. Repeat steps 3-5

To break, you want to find seed N, since you can compute the exact private/public keypair in the same time it took to generate (e.g using Profanity itself).

The efficient manner would require:

Pre-generation:

1. I can collect the public keys of all 2**32 (seed) * 2 million (deterministic) combinations ahead of time, with fairly little compute

Then:

1. I get the public key from the vanity address that has a transaction

2. I apply some deterministic function to get 2 million other public keys (I assume to match with the 2 million derived private keys; ignoring how this works for now)

3. I decrement these public keys over and over until one matches with one that I generated during Pre-generation (telling me the origin seed needed to re-compute the private key)

The part I don’t get is (3)—how can I decrement the public key to produce a match when two private keys (A and A') produce vastly different public keys.

Answer from Anton Bukov (1inch team):

Subtracting point G. Need to build table of 4b public keys, expansion to 2m keys was done by:

privateKey + (task_id << 192)

So on reverse process we did:

publicKey - (task_id << 192)*G