Bitcoin get public key from private key

How to Generate a Bitcoin Address — Step by Step

Here is a bash script that does what is outlined below: https://bit.ly/2MIgeOD

Introduction

This is a hands-on, technical guide about the generation of Bitcoin addresses including private and public keys, and the cryptography involved.

Learn more and join people in 22 countries around the world in my course on how to Become a Bitcoin + Blockchain Programmer.

This guide will walk you through all the steps to generate a Bitcoin address using the command line on a Mac. Similar steps should be possible on other operating systems using similar cryptographic tools. Lines starting with $ denote terminal commands, which you can type and run (without the $ of course).

Dependencies

• brew — Installation: https://brew.sh/
• pip — Installation: sudo easy_install pip
• libressl — Installation: brew install libressl
• base58 — Installation: pip install base58

Note: To do the contained openssl cli commands, I installed libressl in order for some of the elliptic curve commands to work as the current version of openssl cli on mac has a bug.

Cryptography Primer

Public Key Cryptography

Or asymmetric cryptography, is a type of cryptography that uses key pairs, each of which is unique. The pair of keys includes a public key and a private key. This is the type of cryptography that Bitcoin uses to control funds. A public key can be generated from a private key, but not vice-versa (computationally too difficult). Also, something encrypted with a private key can be decrypted with the public key, and vice-versa, hence they are asymmetric.

• Encryption: When a user has a public key, a message can be encrypted using a public key, which can only be read by the person with the private key. This also works in reverse.
• Digital Signatures: A user can, with their private key and a hash of some data, use a digital signature algorithm such as ECDSA, to calculate a digital signature. Then, another user can use the algorithm to verify that signature using the public key and the hash of the same data. If it passes, this proves a user did in fact submit a specific message, which has not been tampered with.
• Digital Fingerprint: Is a way to represent an arbitrarily large data set by computing the hash of it to generate a fingerprint of a standard size. This fingerprint would be so difficult to replicate without the same exact data, which can be assumed to have not been tampered with.

Private keys are what prove you can send Bitcoin that has been sent to you. It is like the password to your bank account. If you lose it or someone else gets a hold of it, you’re toast.

Public keys help people know how to send you Bitcoin.

Creating a Bitcoin Address

Private Key Generation

Private keys can be any 256 bit (32 byte) value from 0x1 to 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140 .¹

The total possible number of private keys is therefore 2²⁵⁶ or 1.16 x 10⁷⁷. Imagine the total number of atoms in your body, then imagine that each of those atoms is an earth. The total number of atoms on all of those earths is about 7 x 10⁷⁷.² There is virtually no chance that your random private key will ever be generated randomly or found by someone else.

A common (but not the most secure) way of creating a private key is to start with a seed, such as a group of words or passphrases picked at random. This seed is then passed through the SHA256 algorithm, which will always conveniently generate a 256 bit value. This is possible because every computer character is represented by an integer value (see ASCII and Unicode).

Note: SHA256 is a one-way, deterministic function meaning that it is easy to compute in one direction, but you cannot reverse it. In order to find a specific output, you have to try all the possible inputs until you get the desired output (brute forcing) and it will always produce the same output given the same input, respectively.

The seed can be used to generate the same private key if the same hashing algorithm is used in the future, so it is only necessary to save the seed.

This private key is in hexadecimal or base 16. Every 2 digits represents 8 bits or 1 byte. So, with 64 characters, there are 256 bits total.

Public Key Generation

Public keys are generated from the private keys in Bitcoin using elliptic curve ( secp256k1 ) multiplication using the formula K = k * G , where K is the public key, k is the private key, and G is a constant called the Generator Point⁴, which for secp256k1 is equal to:

It doesn’t seem to be known how this point was chosen by they designers of the curve. Also, this algorithm is a one-way algorithm, or a “trap door” function so that a private key cannot be derived from the public key. It is important to note that elliptic curve multiplication is not the same as scalar multiplication, though it does share similar properties.

To do this in the terminal from our private key earlier,

This public key contains a prefix 0x04 and the x and y coordinates on the elliptic curve secp256k1 , respectively.

Compressed Public Key

Most wallets and nodes implement compressed public key as a default format because it is half as big as an uncompressed key, saving blockchain space. To convert from an uncompressed public key to a compressed public key, you can omit the y value because the y value can be solved for using the equation of the elliptic curve: y² = x³ + 7. Since the equation solves for y², the right side of the equation could be either positive or negative. So, 0x02 is prepended for positive y values, and 0x03 is prepended for negative ones. If the last binary digit of the y coordinate is 0, then the number is even, which corresponds to positive. If it is 1, then it is negative. The compressed version of the public key becomes:

The prefix is 0x02 because the y coordinate ends in 0xa4 , which is even, therefore positive.

Address Generation

There are multiple Bitcoin address types, currently P2SH or pay-to-script hash is the default for most wallets. P2PKH was the predecessor and stands for Pay to Public Key Hash. Scripts give you more functionality, which is one reason why they are more popular. We’ll first generate a P2PKH original format address, followed by the now standard P2SH .

The public key from the previous output is hashed first using sha256 and then hashed using ripemd160 . This shortens the number of output bytes and ensures that in case there is some unforeseen relationship between elliptic curve and sha256, another unrelated hash function would significantly increase the difficulty of reversing the operation:

Note that since the input is a string, the xxd -r -p will convert the hex string into binary and then output it in hexdump style (ascii), which is what the openssl hashing functions expect as input.

Now that we have hashed the public key, we now perform base58check encoding. Base58check allows the hash to be displayed in a more compact way (using more letters of the alphabet) while avoiding characters that could be confused with each other such as 0 and O where a typo could result in your losing your funds. A checksum is applied to make sure the address was transmitted correctly without any data corruption such as mistyping the address.

Bitcoin P2PKH addresses begin with the version byte value 0x00 denoting the address type and end with a 4 byte checksum. First we prepend the version byte (prefix) to our public key hash and calculate and append the checksum before we encode it using base58 :

Note: -c denotes a checksum is to be applied. The checksum is calculated as checksum = SHA256(SHA256(prefix+data)) and only the first 4 bytes of the hash are appended to the end of the data.

The resulting value is a P2PKH address that can be used to receive Bitcoin: 16JrGhLx5bcBSA34kew9V6Mufa4aXhFe9X

Pay-to-Script Hash

The new default address type is a pay-to-script-hash, where instead of paying to a pubKey hash, it is a script hash. Bitcoin has a scripting language, you can read more about it here. Basically it allows for things like multiple signature requirements to send Bitcoin or a time delay before you are allowed to send funds, etc. A commonly used script is a P2WPKH (Pay to Witness Public Key Hash): OP_0 0x14

where the PubKey Hash is the RIPEMD160 of the SHA256 of the public key, as before, and 0x14 is the number of bytes in the PubKey Hash. So, to turn this script into an address, you simply apply BASE58CHECK to the RIPEMD160 of the SHA256 of the script OP_0 0x14

except you prepend 0x05 to the script hash instead of 0x00 to denote the address type is a P2SH address.

If you like the article, check out my course on how to Become a Bitcoin + Blockchain Programmer.

Источник

Bitcoin in a nutshell — Cryptography

Одна из причин, почему Bitcoin продолжает привлекать столько внимания — это его исключительная «математичность». Сатоши Накамото удалось создать систему, которая способна функционировать при полном отсутствии доверия между ее участниками. Все взаимодействия основаны на строгой математике, никакого человеческого фактора — вот в чем была революционность идеи, а не в одноранговой сети, как многие думают. Поэтому первую главу я решил посвятить именно математическим основам Bitcoin.

Ниже я постараюсь объяснить вам самые базовые вещи — эллиптические кривые, ECC, приватные / публичные ключи и так далее. По возможности я буду иллюстрировать свои слова примерами кода, преимущественно на Python 2.7, если что-то непонятно — спрашивайте в комментариях.

Table of content

Introduction

Как я уже сказал выше, криптография — это фундаментальная часть Bitcoin. Без нее вообще бы ничего не заработало, поэтому начинать нужно именно отсюда.

В Bitcoin используется так называемая криптография на эллиптических кривых (Elliptic curve cryptography, ECC). Она основана на некоторой особой функции — эллиптической кривой (не путать с эллипсом). Что это за функция и чем она так примечательна я расскажу дальше.

Elliptic curve

Эллипти́ческая крива́я над полем — неособая кубическая кривая на проективной плоскости над (алгебраическим замыканием поля ), задаваемая уравнением 3-й степени с коэффициентами из поля и «точкой на бесконечности» — Wikipedia

Если на пальцах, то эллиптическая кривая — это внешне довольно простая функция, как правило, записываемая в виде так называемой формы Вейерштрасса:

В зависимости от значений параметров и , график данной функции может выглядеть по разному:

Скрипт для отрисовки графика на Python:

Если верить вики, то впервые эта функция засветилась еще в трудах Диофанта, а позже, в 17 веке, ей заинтересовался сам Ньютон. Его исследования во многом привели к формулам сложения точек на эллиптической кривой, с которыми мы сейчас познакомимся. Здесь и в дальнейшем мы будем рассматривать некоторую эллиптическую кривую .

Пусть есть две точки . Их суммой называется точка , которая в простейшем случае определяется следующим образом: проведем прямую через и — она пересечет кривую в единственной точке, назовем ее . Поменяв координату точки на противоположную по знаку, мы получим точку , которую и будем называть суммой и , то есть .

Считаю необходимым отметить, что мы именно вводим такую операцию сложения — если вы будете складывать точки в привычном понимании, то есть складывая соответствующие координаты, то получите совсем другую точку , которая, скорее всего, не имеет ничего общего с или и вообще не лежит на кривой .

Самые сообразительные уже задались вопросом — а что будет, если например провести прямую через две точки, имеющие координаты вида и , то есть прямая, проходящая через них, будет параллельна оси ординат (третий кадр на картинке ниже).

Несложно увидеть, что в этом случае отсутствует третье пересечение с кривой , которое мы называли . Для того, чтобы избежать этого казуса, введем так называемую точку в бесконечности (point of infinity), обозначаемую обычно или просто , как на картинке. И будем говорить, что в случае отсутствия пересечения .

Особый интерес для нас представляет случай, когда мы хотим сложить точку саму с собой (2 кадр, точка ). В этом случае просто проведем касательную к точке и отразим полученную точку пересечения относительно .

Теперь, легким движением руки, можно ввести операцию умножения точки на какое-то число. В результате получим новую точку , то есть раз. С картинкой все должно стать вообще понятно:

Elliptic curve over a finite field

В ECC используется точно такая же кривая, только рассматриваемая над некоторым конечным полем — простое число. То есть

Все названные свойства (сложение, умножение, точка в бесконечности) для такой функции остаются в силе, хотя, если попробовать нарисовать данную функцию, то напоминать привычную эллиптическую кривую она будет лишь отдаленно (в лучшем случае). А понятие «касательной к функции в точке» вообще теряет всякий смысл, но это ничего страшного. Вот пример функции для :

А вот для , тут вообще почти хаотичный набор точек. Единственное, что все еще напоминает о происхождении этого графика, так это симметрия относительно оси .

P. S. Если вам интересно, как в случае с кривой над конечным полем вычислить координаты точки , зная координаты и — можете полистать «An Introduction to Bitcoin, Elliptic Curves and the Mathematics of ECDSA» by N. Mistry, там все подробно расписано, достаточно знать математику на уровне 8 класса.

P.P.S. На случай, если мои примеры не удовлетворили ваш пытливый ум, вот сайт для рисования кривых всех сортов, поэкспериментируйте.

SECP256k1

Возвращаясь к Bitcoin, в нем используется кривая SECP256k1. Она имеет вид и рассматривается над полем , где — очень большое простое число, а именно .

Так же для SECP256k1 определена так называемая base point, она же generator point — это просто точка, как правило, обозначаемая , лежащая на данной кривой. Она нужна для создания публичного ключа, о котором будет рассказано ниже.

Простой пример: используя Python, проверим, принадлежит ли точка кривой SECP256k1

Digital signature

Электро́нная по́дпись (ЭП), Электро́нная цифровая по́дпись (ЭЦП) — реквизит электронного документа, полученный в результате криптографического преобразования информации с использованием закрытого ключа подписи и позволяющий проверить отсутствие искажения информации в электронном документе с момента формирования подписи (целостность), принадлежность подписи владельцу сертификата ключа подписи (авторство), а в случае успешной проверки подтвердить факт подписания электронного документа (неотказуемость) — Wikipedia

Общая идея такая: Алиса хочет перевести 1 BTC Бобу. Для этого она создает сообщение типа:

Потом Алиса берет свой приватный ключ (пока что можете считать, что это число, известное только Алисе), хэш сообщения и функцию вида . На выходе она получает подпись своего сообщения — в случае ECDSA это будет пара целых чисел, для других алгоритмов подпись может выглядеть по другому. После этого она рассылает всем участникам сети исходное сообщение, подпись и свой публичный ключ.

В результате, каждый Вася при желании сможет взять эту троицу, функцию вида и проверить, действительно ли владелец приватного ключа подписывал это сообщение или нет. А если внутри сети все знают, что принадлежит Алисе, то можно понять, отправила эти деньги она или же кто-то пытается сделать это от ее имени.

Более того, предположим, что нашелся человек, вставший между Алисой и остальной сетью. Пусть он перехватил сообщение Алисы и что-то в нем изменил, буквально 1 бит из миллиарда. Но даже в этом случае проверка подписи на валидность покажет, что сообщение было изменено.

Это очень важная фича для Bitcoin, потому как сеть распределенная. Мы не можем заранее знать, к кому попадет наша транзакция с требованием перевести 1000 BTC. Но изменить ее (например указать свой адрес с качестве получателя) он не сможет, потому как транзакция подписана вашим приватным ключом, и остальные участники сети сразу поймут, что здесь что-то не так.

AHTUNG! В действительности процесс довольно сильно отличается от вышеописанного. Здесь я просто на пальцах показал, что из себя представляет электронно-цифровая подпись и зачем она нужна. Реальный алгоритм описан в главе «Bitcoin in a nutshell — Transactions».

Private key

Приватный ключ — это довольно общий термин и в различных алгоритмах электронной подписи могут использоваться различные типы приватных ключей.

Как вы уже могли заметить, в Bitcoin используется алгоритм ECDSA — в его случае приватный ключ — это некоторое натуральное 256 битное число, то есть самое обычное целое число от до . Технически, даже число 123456 будет являться корректным приватным ключом, но очень скоро вы узнаете, что ваши монеты «принадлежат» вам ровно до того момента, как у злоумышленника окажется ваш приватный ключ, а значения типа 123456 очень легко перебираются.

Важно отметить, на сегодняшний день перебрать все ключи невозможно в силу того, что — это фантастически большое число.

Постараемся его представить: согласно этой статье, на всей Земле немногим меньше песчинок. Воспользуемся тем, что , то есть песчинок. А всего адресов у нас , примерно .

Значит, мы можем взять весь песок на Земле, превратить каждую песчинку в новую Землю, в получившейся куче планет каждую песчинку на каждой планете снова превратить в новую Землю, и суммарное число песчинок все равно будет на порядки меньше числа возможных приватных ключей.

По этой же причине большинство Bitcoin клиентов при создании приватного ключа просто берут 256 случайных бит — вероятность коллизии крайне мала.

Python

Python, ECDSA

Bitcoin-cli

Public key

Пусть — наш приватный ключ, — base point, тогда публичный ключ . То есть, фактически, публичный ключ — это некоторая точка, лежащая на кривой SECP256k1.

Два важных нюанса. Во-первых, несложно видеть, что операция получения публичного ключа определена однозначно, то есть конкретному приватному ключу всегда соответствует один единственный публичный ключ. Во-вторых, обратная операция является вычислительно трудной и, в общем случае, получить приватный ключ из публичного можно только полным перебором первого.

Ниже вы узнаете, что точно такая же связь существует между публичным ключом и адресом, только там все дело в необратимости хэш-функций.

Python, ECDSA

C++, libbitcoin

Для компиляции и запуска используем (предварительно установив libbitcoin):

Вы можете видеть, что форматы публичных ключей в первом и втором примере отличаются (как минимум длиной), об этом я подробнее расскажу ниже.

Formats & address

Base58Check encoding

Эта кодировка будет встречаться нам постоянно на протяжении всей книги, поэтому стоит понимать, как она работает и зачем она вообще нужна.

Ее суть в том, чтобы максимально кратко записать последовательность байт в удобочитаемом формате и при этом сделать вероятность возможных опечаток еще меньше. Я думаю вы сами понимаете, что в случае Bitcoin безопасность лишней не бывает. Один неправильный символ и деньги уйдут на адрес, ключей к которому скорее всего никто никогда не найдет. Вот комментарий к этой кодировке из в base58.h:

Краткость записи проще всего реализовать, используя довольно распространенную кодировку Base64, то есть используя систему счисления с основанием 64, где для записи используются цифры 0,1. 9 , буквы a-z и A-Z — это дает 62 символа, оставшиеся два могут быть чем угодно, в зависимости от реализации.

Первое отличие Base58Check в том, что убраны символы 0,O,l,I на случай, если кто-нибудь решит их перепутать. Получается 58 символов, можете проверить

Второе отличие — это тот самый check. В конец строки снова добавляется checksum — первые 4 байта SHA256(SHA256(str)) . Ну и еще нужно добавить в начало столько единиц, сколько ведущих нулей было до кодировки в base58, это уже дело техники.

Private key formats

Самый очевидный способ хранить приватный ключ — это записать 256 бит в виде кучи нулей и единиц. Но, наверное, любой технически грамотный человек понимает, что будет сильно проще представить ту же самую последовательность в виде 32 байт, где каждому байту соответствует два символа в шестнадцатиричной записи. Напомню, что в этом случае используются цифры 0,1. 9 и буквы A,B,C,D,E,F . Этот формат я использовал в примерах выше, для красоты его еще иногда разделяют пробелами.

Другой более прогрессивный формат — WIF (Wallet Import Format). Строится он довольно просто:

1. Берем приватный ключ, например 0C28FCA386C7A227600B2FE50B7CAE11EC86D3BF1FBE471BE89827E19D72AA1D
2. Записываем его в Base58Check с префиксом 0x80 . Все.

Public key formats

На всякий случай напомню, что публичный ключ — это просто точка на прямой SECP256k1. Первый и самый распространенный вариант его записи — uncompressed формат, по 32 байта для X и Y координат. Чтобы не возникало путаницы, используется префикс 0x04 и того 65 байт.

Однако, как можно догадаться из названия, это не самый оптимальный способ хранить публичный ключ.

Вы удивитесь, но второй формат называется compressed. Суть его в следующем: публичный ключ — это точка на кривой, то есть пара чисел удовлетворяющая уравнению . А значит можно записать только Х координату и если нам понадобится Y координата — просто решаем уравнение. Тем самым мы уменьшаем размер публичного ключа почти на 50%!

Единственный нюанс — если точка лежит на кривой, то для ее Х координаты очевидно существует два решения такого уравнения (посмотрите на графики выше, если сомневаетесь). Обычно мы бы просто сохранили знак для Y координаты, но когда речь идет о функции над конечным полем, то нужно воспользоваться следующим свойством: если для Х координаты существуют решения уравнения, то одна из точек будет иметь четную Y координату, а вторая — нечетную (опять же, можете сами в этом убедиться).

В первом случае используется префикс 0x02 , во втором — 0x03 . Вот иллюстрация процесса:

Address

Как уже было сказано, адрес получается из публичного ключа однозначным образом. Более того, провести обратную операцию невозможно, так как используются криптографически стойкие хэш функции — RIPEMD160 и SHA256. Вот алгоритм перевода публичного ключа в адрес:

1. Возьмем приватный ключ, например 45b0c38fa54766354cf3409d38b873255dfa9ed3407a542ba48eb9cab9dfca67
2. Получим из него публичный ключ в uncompressed формате, в данном случае это 04162ebcd38c90b56fbdb4b0390695afb471c944a6003cb334bbf030a89c42b584f089012beb4842483692bdff9fcab8676fed42c47bffb081001209079bbcb8db .
3. Считаем RIPEMD160(SHA256(public_key)) , получается 5879DB1D96FC29B2A6BDC593E67EDD2C5876F64C
4. Переводим результат в Base58Check с префиксом 0x00 — 17JdJpDyu3tB5GD3jwZP784W5KbRdfb84X . Это и есть адрес.

Sign & verify

Не думаю, что вам нужно обязательно знать технические подробности того, как именно ECDSA подписывает и проверяет сообщения, все равно вы везде будете пользоваться готовыми библиотеками. Главное, чтобы у вас было общее понимание того зачем это нужно, но если вам все таки интересно — полистайте Layman’s Guide to Elliptic Curve Digital Signatures, там внизу есть красивая визуализация всего процесса, можете сами попробовать.

У меня на этом все, следующая глава: Bitcoin in a nutshell — Transaction.

Источник