public key to mnemonic

[BlackHatCoiner]

I'm working on a project in which I need a way to convert an ECC public key to mnemonic. Until now, it wasn't a problem I was generating a random private key then I was getting the 260-bit public key, I cut the last 2 hex characters to achieve 256 bits and then I could get 24 words.

The problem comes when I'll have to convert those 24 words back to its original public key form so I can verify a message. I realized that I can't do that, because those 2 characters are missing from the public key. Is there any way to convert the whole public key to mnemonic? Or anything that would solve my problem?

[coinableS]

You shouldn't be converting public keys to a mnemonic.

[BlackHatCoiner]

You shouldn't be converting public keys to a mnemonic.

I shouldn't if we're talking about wallets. Hexadecimal to mnemonic can be normally implemented.

[o_e_l_e_o]

Until now, it wasn't a problem I was generating a random private key then I was getting the 260-bit public key, I cut the last 2 hex characters to achieve 256 bits and then I could get 24 words.

A public key is not 260 bits, and cutting two hex characters is equivalent to cutting 8 bits, not 4.

A full uncompressed public key is 520 bits long, which is 130 hex characters. This takes the form of the prefix byte 04 followed by two 256 bit numbers - the x coordinate and the y coordinate.

A compressed public key is 264 bits long which is 66 hex characters. You drop the 256 bit y coordinate, and change the prefix byte to either 02 or 03 depending on whether the y coordinate is even or odd.

If you use the compressed public key, then 24 words at 11 bits each works out at exactly 264 bits. You should therefore be able to fully encode the compressed public key in to a 24 word phrase, assuming you are using a word list of 2048 words.

I feel I have to mention that this is a non-standard use of a passphrase and obviously does not allow you to back up your wallet or spend any coins.

[j2002ba2]

Minimal number of bits for public key is 257: 256 bit x and 1 bit y (usually parity).

Compressed public key starts with 02 or 03, which is y parity. If you have a way of avoiding or guessing the y bit, then just use the x bits.

If this is not possible, then transform x to mnemonics, and then, if y is odd, let the last word be the next from the wordlist, modulo 256. Obviously this would break the checksum verification in half of the cases, but then you set the last word to be the previous-mod256 one, and if checksum matches, then you are good to go, knowing y is odd.

For example 020000000000000000000000000000000000000000000000000000000000000001 would be
"abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon diesel"
while 030000000000000000000000000000000000000000000000000000000000000001
"abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon diet"

By next-mod256 I mean if the last word is "cable", next-mod256 would be "abandon" (not "cactus").

[BlackHatCoiner]

A compressed public key is 264 bits long which is 66 hex characters. You drop the 256 bit y coordinate, and change the prefix byte to either 02 or 03 depending on whether the y coordinate is even or odd.

Why do I drop the 256 bit y coordinate? Let's take it from start, I have this public key:
03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4

Right now its length is 66, which means 264 bits. I want 256 to get the 24 words, so I'll have to get rid of 2 characters. Should I remove the first 2 which define if it's odd or even? Will I, then, be able to return from mnemonic to public key?

On my code I've removed the last 2 chars:
03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56

For some weird reason when I convert this to binary I get 258 bits. Shouldn't I get 256? (264 - 4*2 = 256)

[j2002ba2]

With my code 03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4 would become
"spring benefit animal dumb identify trip sudden pond snack giraffe amount razor crucial captain extra excite promote witness motion prefer enrich topple forward observe".

Drop (and remember) the starting 03, encode the rest, "increment" the last word (since y is odd).

Decoding would be: calculate the checksum, if it doesn't match "decrement" last word (and remember y is odd), if it still doesn't match - error, decode, prepend 02 (or 03 when odd), check if point is valid - otherwise error.

[pooya87]

You don't need to drop anything, in BIP39 definition you take 256 bits of entropy, append 8 bits of checksum and then encode the total 264 bits.
A compressed public key is 33 bytes or 264 bits already, you just have to modify the code to not compute the checksum and simply encode the entire 264 bits that you already have. If you think about this type of encoding (bits to words) you want your bit length to be divisible by 11 and 264 bits already is (264 = 11*24 + 0).
You are already doing something out of ordinary and you said you aren't creating a wallet so this modification shouldn't matter.

[BlackHatCoiner]

You don't need to drop anything, in BIP39 definition you take 256 bits of entropy, append 8 bits of checksum and then encode the total 264 bits.
A compressed public key is 33 bytes or 264 bits already, you just have to modify the code to not compute the checksum and simply encode the entire 264 bits that you already have. If you think about this type of encoding (bits to words) you want your bit length to be divisible by 11 and 264 bits already is (264 = 11*24 + 0).
You are already doing something out of ordinary and you said you aren't creating a wallet so this modification shouldn't matter.

I'm trying to encode the total 264 bits, but it seems that the library is doing it by default. If I try to do it with 264 it gives me error:

Code:

byte[] hextobyte = StringToByteArray(firstpublickey);
Mnemonic public_mnemonic = new Mnemonic(Wordlist.English, hextobyte);

What I don't understand is why a public key like: 03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4 is 258 bits and not 256 or 264 (= 4*66).

[pooya87]

I'm trying to encode the total 264 bits, but it seems that the library is doing it by default. If I try to do it with 264 it gives me error:

That is because the bitcoin libraries are designed for BIP39 not what you are trying to do, and in BIP39 the code expects the entropy length to be certain values that you can see in that error message otherwise if the length is something else it can not split it into the expected number of words (12, 24, etc.).
Here is reference implementation in GO rejecting entropies that aren't among the expected values: https://github.com/tyler-smith/go-bip39/blob/master/bip39.go#L302-L305

What I don't understand is why a public key like: 03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4 is 258 bits and not 256 or 264 (= 4*66).

It is probably because you are doing something wrong when converting hex to binary. There are 66 characters in the hex you posted that represent 33 bytes and 264 bits.
Here is the binary:

Code:

00000011 11010011 00100010 10100100 00100100 00100001 11110111 00001001 11010001 10110110 00100101 00111110 11001101 00001100 01000100 00100000 01011001 01010011 01000110 01000100 01010100 01000010 01110110 10101100 00111111 10010110 01000001 01010100 11100100 10110001 11001010 01010110 11110100 

You can check yours against this to see which part of it is wrong.

[o_e_l_e_o]

As pooya87 has pointed out, the reason it wants 256 bits of entropy is because with 24 word seed phrases we calculate a checksum of 8 bits and append it to the 256 bits of entropy, giving 264 bits in total. Each word represents 11 bits of data, and so 24 words gives 24*11 = 264 bits. Since you are doing something non-standard, you do not need to calculate a checksum, and so can just encode your 264 bit compressed public key directly in to words.

What I don't understand is why a public key like: 03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4 is 258 bits and not 256 or 264 (= 4*66).

I assume whatever you are using to it to binary is dropping the leading zeroes, of which there are 6, and so giving you 258 bits instead of 264.

Code:

03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4

Convert to binary

Code:

00000011 11010011 00100010 10100100 00100100 00100001 11110111 00001001 11010001 10110110 00100101 00111110 11001101 00001100 01000100 00100000 01011001 01010011 01000110 01000100 01010100 01000010 01110110 10101100 00111111 10010110 01000001 01010100 11100100 10110001 11001010 01010110 11110100

Arrange in to groups of 11 bits

Code:

00000011110 10011001000 10101001000 01001000010 00011111011 10000100111 01000110110 11000100101 00111110110 01101000011 00010001000 01000000101 10010101001 10100011001 00010001010 10001000010 01110110101 01100001111 11100101100 10000010101 01001110010 01011000111 00101001010 11011110100

Map each group of 11 bits to the corresponding word in the BIP39 wordlist

Code:

adult october poverty embark buyer lumber egg seven disagree half baby doll news permit bacon marriage issue giggle tortoise live exact flight citizen teach

[odolvlobo]

A compressed public key is 264 bits long which is 66 hex characters. You drop the 256 bit y coordinate, and change the prefix byte to either 02 or 03 depending on whether the y coordinate is even or odd.

Why do I drop the 256 bit y coordinate? Let's take it from start, I have this public key:
03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4

Right now its length is 66, which means 264 bits. I want 256 to get the 24 words, so I'll have to get rid of 2 characters. Should I remove the first 2 which define if it's odd or even? Will I, then, be able to return from mnemonic to public key?

On my code I've removed the last 2 chars:
03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56

For some weird reason when I convert this to binary I get 258 bits. Shouldn't I get 256? (264 - 4*2 = 256)

A simple solution is to pad the input with 0s. For BIP-39, you need a multiple of 32 bits, so you add 24 extra 0 bits to the end.

Encoding:

1. Public key: 03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4
2. Pad:     03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4000000
3. Encode: adult october poverty embark buyer lumber egg seven disagree half baby doll news permit bacon marriage issue giggle tortoise live exact flight citizen teach abandon abandon dinner


Decoding:

1. Mnemonic: adult october poverty embark buyer lumber egg seven disagree half baby doll news permit bacon marriage issue giggle tortoise live exact flight citizen teach abandon abandon dinner
2. Decode:    03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4000000
3. Drop padding: 03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4

This is where I found the technique: https://github.com/jambolo/bip39

[o_e_l_e_o]

-snip-

This is a more complex solution than the one I have already outlined above, and is a non-standard use of BIP39. The maximum allowable entropy for BIP39 is 256 bits. By padding a compressed public key with 6 additional zeroes, you are now using a 288 bit number. Your process also calculates and appends a non-standard 9 bit checksum, before encoding the whole thing in 27 words. The 27 words you end up with are identical to the 24 words I outlined in my process, but with 3 extra and unnecessary words appended to the end.

A 264 bit compressed public key encodes exactly in to 24 words. No need to overcomplicate things unless you really want a checksum for whatever reason.

[BlackHatCoiner]

A compressed public key is 264 bits long which is 66 hex characters. You drop the 256 bit y coordinate, and change the prefix byte to either 02 or 03 depending on whether the y coordinate is even or odd.

I have a little question about the prefix byte. When you say that y coordinate is even or odd you mean on what number the entire hex ends?
For example 02f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381 starts with 02 so it's even, but ends with 1 so it can't be even. How do I understand if a hex needs a 02 or a 03?

[o_e_l_e_o]

When you say that y coordinate is even or odd you mean on what number the entire hex ends?

Yes, but not the hex you have quoted.

The hex you have quoted - 02f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381 - is the compressed public key. It is the initial 02 byte followed by the x coordinate only. The y coordinate has been omitted because it can be calculated from knowledge of the x coordinate and the initial byte. The full uncompressed key is:

Code:

04f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f138195d1c7407dee48a9b4796494c1c23824e90614b7a84aea43242922a48699bd8e

This is made up of the following

Code:

Initial byte - 04 (which tells us the key is uncompressed)
x coordinate - f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381
y coordinate - 95d1c7407dee48a9b4796494c1c23824e90614b7a84aea43242922a48699bd8e

So to compress this, you drop the y coordinate, and since the y coordinate is even, turn in the initial 04 byte to 02.


For a slightly more technical answer, to calculate the y coordinate, you use the following equation:
y² (mod p) = (x³ + 7) (mod p)

Because you calculate y², then the solution for y can be either positive or negative. (Consider that both 3² and (-3)² both equal 9). Because of elliptic curve mathematics, and the limits we use when interpreting these numbers, we call one of these even and the other odd, and apply the necessary prefix accordingly.

[BlackHatCoiner]

Because of elliptic curve mathematics, and the limits we use when interpreting these numbers, we call one of these even and the other odd, and apply the necessary prefix accordingly.

But why do we call them even or odds based on their sign? Why don't we call them negatives or positives? Just like in maths. Also, if we calculate the equation we will get 2 results as you said. One positive (y) and one negative (-y). Which of those do we choose? Does the computer chooses it randomly?

For a slightly more technical answer, to calculate the y coordinate, you use the following equation:
y² (mod p) = (x³ + 7) (mod p)

What is p? I know that α mod β gives us the remainder of the division, but I haven't seen that again and I don't understand it.

[o_e_l_e_o]

Why don't we call them negatives or positives?

Because in finite fields there is no such thing as a negative or positive.

Does the computer chooses it randomly?

No. When you turn a private key in to a public key, you get exactly one point on the curve, which has exactly one x coordinate and one y coordinate. However, for every x coordinate, there are two possible y coordinates, so when you compress your public key down to just the x coordinate, you specific which y coordinate is the correct one.

What is p?

The field size, which for the secp256k1 curve bitcoin uses is 2²⁵⁶ – 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1.


Here is a very gross oversimplification, but used as an illustration. Consider some calculations which are being done modulo 11.

5² = 25 = 3
6² = 36 = 3

So 5 (odd) and 6 (even) are the square roots of 3, in our field of modulo 11. Note that it does not make sense to speak of positives or negatives here, since in our field of modulo 11, the following is also true:

-17 = -6 = 5 = 16 = 27
-16 = -5 = 6 = 17 = 28

[BlackHatCoiner]

Oh. Then that's a problem for me. On my project I generate a private key, then from the public key, I remove the prefix and convert the 64 char length string to mnemonic. Once I need that public key again I'll have to decode the mnemonic. The problem is that I won't know which prefix it should have. I guess that both of these public keys exist on the secp256k1 curve:

02f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381
03f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381

One solution is trying to match both of them every time and see which is the right one. Tell me if you have a better solution.

[o_e_l_e_o]

I guess that both of these public keys exist on the secp256k1 curve:

Yes.

Code:

02f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381

Decompresses to

Code:

04f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f138195d1c7407dee48a9b4796494c1c23824e90614b7a84aea43242922a48699bd8e

Which splits up as

Code:

04
x = f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381
y = 95d1c7407dee48a9b4796494c1c23824e90614b7a84aea43242922a48699bd8e

Code:

03f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381

Decompresses to

Code:

04f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f13816a2e38bf8211b7564b869b6b3e3dc7db16f9eb4857b515bcdbd6dd5a79663ea1

Which splits up as

Code:

04
x = f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381
y = 6a2e38bf8211b7564b869b6b3e3dc7db16f9eb4857b515bcdbd6dd5a79663ea1

As you can see, although the x coordinates are the same, the two y coordinates are completely different.

Tell me if you have a better solution.

I already gave you a perfect solution in this post above: https://bitcointalk.org/index.php?topic=5295107.msg55721191#msg55721191
A compressed public key, including the prefix byte, encodes exactly in to 24 words from the BIP39 list.

For example, let's use the first key you gave - 02f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381

Code:

02f9fd63b1121b8872d6184b39e97972cd636e76a0fa9c67a74b1b7156791f1381

Convert to binary (exactly 264 bits)

Code:

00000010 11111001 11111101 01100011 10110001 00010010 00011011 10001000 01110010 11010110 00011000 01001011 00111001 11101001 01111001 01110010 11001101 01100011 01101110 01110110 10100000 11111010 10011100 01100111 10100111 01001011 00011011 01110001 01010110 01111001 00011111 00010011 10000001

Arrange in to groups of 11 bits (exactly 24 groups of 11 bits)

Code:

00000010111 11001111111 01011000111 01100010001 00100001101 11000100001 11001011010 11000011000 01001011001 11001111010 01011110010 11100101100 11010110001 10110111001 11011010100 00011111010 10011100011 00111101001 11010010110 00110110111 00010101011 00111100100 01111100010 01110000001

Map each group of 11 bits to the corresponding word in the BIP39 wordlist

Code:

actual soup flight giraffe canvas service slender seek enroll soon furnace tortoise stomach rescue surround butter organ diamond spot dad betray develop labor ice

[BlackHatCoiner]

I already gave you a perfect solution in this post above: https://bitcointalk.org/index.php?topic=5295107.msg55721191#msg55721191
A compressed public key, including the prefix byte, encodes exactly in to 24 words from the BIP39 list.

I did it! Thanks. I probably hadn't done it right in the previous time, because I didn't understand the basics behind all these. Now that I have cleared up some things on my mind, I can carry it out.