Connect with us

Cryptography

How does “recid” variable work in libspec256k1 library?

I’m trying to understand how does “recid” (Recovery ID) variable work in libspec256k1 library (with C language).

Published

on

The following content was written by StraightCedar on May 19, 2020, 05:04:26 PM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)


I’m trying to understand how does “recid” (Recovery ID) variable work in libspec256k1 library (with C language).
(https://github.com/bitcoin-core/secp256k1)
I’m sorry if my question was too primitive or inappropriate on this forum.
I would appreciate any advice on the correct sites, the correct forums or etc.

I’d like to understand the relationship between “recid” (Recovery ID) , recovered-public-key and verification, so I tried following steps with modifying “secp256k1_ecdsa_sign_recoverable” function in  main_impl.h.

Step1: Original signing operation. (no modification)
I use “secp256k1_ecdsa_sign_recoverable” function in main_impl.h to get recoverable signature.
In that function, “secp256k1_ecdsa_sig_sign” function is called and it returns “sign” and “recid”.

Step2: Recover public key with recid, and verify.
I wanted to get the recovered public-key using “recid”, which was given by “secp256k1_ecdsa_sig_sign function” in Step 1, and to verify the signed data.
I got the recovered public-key from “secp256k1_ecdsa_recover” function, and it returned the result “1 (recovery success)”.
Then “secp256k1_ecdsa_verify” function returned the result “1 (verification success)”.

Step3: Expect “verification failure” with wrong “recid”, but…
I tried the public-key recovery with wrong “recid”, and expected that verification failed.
“recid” range is 0 to 3, but actually in this experiment, the “recid” value output by the secp256k1_ecdsa_sig_sign function was 0 or 1.
So, if “recid” was 0, I intentionally changed it to 1, and if it was 0, changed to 1.
I got the recovered public-key from “secp256k1_ecdsa_recover” function with wrong “recid”, and it returned the result “1 (recovery success)”.
Then “secp256k1_ecdsa_verify” function returned the result “1 (verification success)”, even though used public-key was recovered with wrong “recid”.

Why verification succeeded with the public-key recovered with wrong “recid”?

The reason why I want to do something like Step3 is that I am strongly considering an experiment using a signature function of another library instead of secp256k1_ecdsa_sig_sign of libspec256k1 as a signature function.
The alternative signature function is designed only for ECDSA signatures, so it does not output “recid”.
Also, its implementation is completely hidden along with the private-key, and it is not possible to retrieve the value in the internal calculation process.
But I need “recid” to construct appropriate blockchain transaction data to send, so I considered Step3 sequence.

Sorry for the long sentence.
Thank you.

—————–
Following is overview of my code at each step.
(It’s a little simplified.)

Step1 original “secp256k1_ecdsa_sign_recoverable” basic process is
Code:
<… some processes …>
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing  function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow);  /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL);        /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */

Step2 modified “secp256k1_ecdsa_sign_recoverable” basic process is
Code:
<… some processes …>
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing  function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow);  /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL);        /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */
/*****************************************/
/**** Step2 Added: Recover public-key ****/
/*****************************************/
int res_pubkey_recover;
static secp256k1_pubkey pubkey_buf;
res_pubkey_recover = secp256k1_ecdsa_recover(ctx, &pubkey_buf, signature, msg32);
/* “&pubkey_buf” is output recovered public key. “signature” is input, which has “sign”s and “recid”. “msg32” is the hash created from original message data (given as a input argument of “secp256k1_ecdsa_sign_recoverable”) */
/*****************************************/
/**** Step2 Added: Verify signed data ****/
/*****************************************/
int res_sig_conv;
static secp256k1_ecdsa_signature normal_sig_buf;
/* Convert recoverable-signature-data into normal-type-signature-data to be used for verification function.
res_sig_conv = secp256k1_ecdsa_recoverable_signature_convert(ctx, &normal_sig_buf, signature);
/* “&normal_sig_buf” is output converted signature data. “res_sig_conv” is always 1. */
/* Verification */
int res_verify;
res_verify = secp256k1_ecdsa_verify(ctx, &normal_sig_buf, msg32, &pubkey_buf);
/* “res_verify = 1” is verification success. “res_verify = 0” is verification failure. */

Step3 modified “secp256k1_ecdsa_sign_recoverable” basic process is
Code:
<… some processes …>
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing  function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow);  /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL);        /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
/**************************************/
/**** Step3 Added: Use wrong recid ****/
/**************************************/
recid = (recid == 0 ? 1 : 0); /* Intentionally use wrong recid. */
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */
/*****************************************/
/**** Step2 Added: Recover public-key ****/
/*****************************************/
int res_pubkey_recover;
static secp256k1_pubkey pubkey_buf;
res_pubkey_recover = secp256k1_ecdsa_recover(ctx, &pubkey_buf, signature, msg32);
/* “&pubkey_buf” is output recovered public key. “signature” is input, which has “sign”s and “recid”. “msg32” is the hash created from original message data (given as a input argument of “secp256k1_ecdsa_sign_recoverable”) */
/*****************************************/
/**** Step2 Added: Verify signed data ****/
/*****************************************/
int res_sig_conv;
static secp256k1_ecdsa_signature normal_sig_buf;
/* Convert recoverable-signature-data into normal-type-signature-data to be used for verification function.
res_sig_conv = secp256k1_ecdsa_recoverable_signature_convert(ctx, &normal_sig_buf, signature);
/* “&normal_sig_buf” is output converted signature data. “res_sig_conv” is always 1. */
/* Verification */
int res_verify;
res_verify = secp256k1_ecdsa_verify(ctx, &normal_sig_buf, msg32, &pubkey_buf);
/* “res_verify = 1” is verification success. “res_verify = 0” is verification failure. */

The following content was written by arulbero on May 19, 2020, 07:06:14 PM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)


https://bitcoin.stackexchange.com/questions/38351/ecdsa-v-r-s-what-is-v


Quote
The (r, s) is the normal output of an ECDSA signature, where r is computed as the X coordinate of a point R, modulo the curve order n.

In Bitcoin, for message signatures, we use a trick called public key recovery. The fact is that if you have the full R point (not just its X coordinate) and s, and a message, you can compute for which public key this would be a valid signature. What this allows is to ‘verify’ a message with an address, without needing to know the full key (we just do public key recovery on the signature, and then hash the recovered key and compare it with the address).

However, this means we need the full R coordinates. There can be up to 4 different points with a given “X coordinate modulo n”. (2 because each X coordinate has two possible Y coordinates, and 2 because r+n may still be a valid X coordinate). That number between 0 and 3 we call the recovery id, or recid. Therefore, we return an extra byte, which also functions as a header byte, by using 27+recid (for uncompressed recovered pubkeys) or 31+recid (for compressed recovered pubkeys).

Strictly speaking the recid is not necessary, as we can just cycle through all the possible coordinate pairs and check if any of them match the signature. The recid just speeds up this verification.

@PeterWuille There can be up to 4 different points with a given “X coordinate modulo n”. (2 because each X coordinate has two possible Y coordinates, and 2 because r+n may still be a valid X coordinate). I understand the former (2 y values for each x, because of the symmetry)… But how does the latter work? ie r+n may still be a valid X coordinate??

X and Y coordinates are numbers modulo p, the field size, which is around 2^256 – 2^32 for secp256k1. The value r and s in the signature however are modulo n, the group order, which is around 2^256 – 2^128. When R.x is between n and p, r is reduced to R.x-n. Thus, if you have an r value below 2^128-2^32, there may be 2 valid R.x values corresponding to it. – Pieter Wuille

27 = lower X even Y. 28 = lower X odd Y. 29 = higher X even Y. 30 = higher X odd Y. Note that 29 and 30 are exceedingly rarely, and will in practice only ever be seen in specifically generated examples. There are only two possible X values if r is between 1 and (p mod n), which has a chance of about 0.000000000000000000000000000000000000373 % to happen randomly.


The following content was written by StraightCedar on June 01, 2020, 10:57:42 AM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)


Thanks to your kind instruction.

I still don’t understand, but result of various trials, I could get the correct “recid” from “sign r”, “sign s” and  “original public key”, in the following process,

Step 1. Make sign data by an ECDSA signing function.
  (It is not included in libsecp256k1. A third party provided one, so it is not arranged for Bit Coin and it doesn’t output “recid”.)
Step 2. Recover public-key from “sign r”, “sign s” and “recid = 0” with secp256k1_ecdsa_recover function.
Step 3. Compare the recovered public-key with original public-key.
Step 4. If they are matched, recid = 0. If not matched, recid = 1.
  (According to some articles for Ethereum, I assumed recid is 0 or 1.)

Then I made transaction data from above result and sent it to the Brock Chain (Ethereum) built on cloud for my test, but often error messages were sent back.
When I executed the verify function of libsecp256k1 for the transaction data going to send, I found that when the validation function returned an error, the Brock Chain also sent an error message back.
Strictly speaking, if sign-s is “higher than the group order divided by 2” (quoted from the commnet in libsecp256k1, secp256k1_scalar_is_high function), the Block Chain will sent an error message back.

So I added range check for sign-s with secp256k1_scalar_is_high function, and if it is “higher”, signing process will be retried until the “sign-s” will become “not higher”.

It works and the Brock Chain no longer returns errors.

From these results, I assumed as follows,
1. Comparation of public keys determine that it is “even Y” or “odd Y”.
2. Higher “sign-s” is not allowed for Etherium.
  (I don’t understant about it.
   Maybe, the “third party signing function” doesn’t avoid overflowed Rx, so it generates the “sign-s” values corresponding to recid = 2 or 3?)

In any case, apparently I found that it is possible to identify the “recid” from “sign-r”, “sign-s” and “original public key”.

Thank you again.

The following content was written by arulbero on June 01, 2020, 03:13:29 PM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)


2. Higher “sign-s” is not allowed for Etherium.
  (I don't understant about it.
   Maybe, the “third party signing function” doesn't avoid overflowed Rx, so it generates the “sign-s” values corresponding to recid = 2 or 3?)

For how it works the ECDSA, https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

if (r,s) is a correct signature, (r, N-s) is also a valid signature

BUT this fact has created issues (transaction malleability) therefor, from Bitcoin Core 0.11, only the lower value of s is allowed:

https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#low-s-values-in-signatures

Quote
Low S values in signatures

The value S in signatures must be between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive). If S is too high, simply replace it by S' = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 – S.

Signatures produced by the OpenSSL library are not guaranteed to be consistent with this constraint. Version 0.9.3 of the reference client provides an example for detection and correction.

The constraints on the value R are unchanged w.r.t. ECDSA, and values can be between 0x1 and 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140 (inclusive).

For what concerns Ethereum, the same choice was made:

https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.md

Quote
Allowing transactions with any s value with 0 < s < secp256k1n, as is currently the case, opens a transaction malleability concern, as one can take any transaction, flip the s value from s to secp256k1n - s, flip the v value (27 -> 28, 28 -> 27), and the resulting signature would still be valid. This is not a serious security flaw, especially since Ethereum uses addresses and not transaction hashes as the input to an ether value transfer or other transaction, but it nevertheless creates a UI inconvenience as an attacker can cause the transaction that gets confirmed in a block to have a different hash from the transaction that any user sends, interfering with user interfaces that use transaction hashes as tracking IDs. Preventing high s values removes this problem.

The issue is the same for Bitcoin and Ethereum, the solution is the same.

Strictly speaking, if sign-s is “higher than the group order divided by 2” (quoted from the commnet in libsecp256k1, secp256k1_scalar_is_high function), the Block Chain will sent an error message back.

So I added range check for sign-s with secp256k1_scalar_is_high function, and if it is “higher”, signing process will be retried until the “sign-s” will become “not higher”.

It works and the Brock Chain no longer returns errors.

It is enough this check:

if (s > N/2) then s = N – s

you don't need to retry from the start the entire process.


result of various trials, I could get the correct “recid” from “sign r”, “sign s” and  “original public key”, in the following process,

Step 1. Make sign data by an ECDSA signing function.
  (It is not included in libsecp256k1. A third party provided one, so it is not arranged for Bit Coin and it doesn't output “recid”.)
Step 2. Recover public-key from “sign r”, “sign s” and “recid = 0” with secp256k1_ecdsa_recover function.
Step 3. Compare the recovered public-key with original public-key.
Step 4. If they are matched, recid = 0. If not matched, recid = 1.
  (According to some articles for Ethereum, I assumed recid is 0 or 1.)



In any case, apparently I found that it is possible to identify the “recid” from “sign-r”, “sign-s” and “original public key”.

The recid value serves to speedup the verification, usually you generate it when you create the signature but you want to derive the recid from (r, s) instead.
For the notation –> https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

1) compute (u1 x G + u2 x Qa) = (x'_1, y'_1)            
2) if x'_1 = r  the recid value is 0 or 1 for sure
   a) if y'_1 is even, then recid = 0
   b) if y'_1 is odd, then recid = 1
3) if x'_1 = r+N the recid value is 2 or 3 for sure
   a) if y'_1 is even, then recid = 2
   b) if y'_1 is odd, then recid = 3
4) if x'_1 != r and x'_1 != r+N, then the signature is not verified

I still don't understand

If you want  more details, I'll use the notation  https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Note1)

choose random (or pseudorandom) k in [1,N-1] and compute k*G = (x1, y1)
then you get the first part of the signature r = x1 mod N

x1 is a number that lies in field Fp, x1 is less than p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = about  2^256 – 2^32

while r is less than N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 = about 2^256 – 2^128

note that N < P;  

if  N < x1 < P,  then r = x1 mod N -->  0 < r < 2^128 - 2^32

for example (x1 = N + 5)

N < N + 5 < P   --->     0 < 5 < 2^128 - 2^32

but the number x1 = 5 too has the same value mod N:

0  < 5  <  N , then x1 mod N  =  5, in this case x1 mod N = x1 = r


To sum up: the same value of 'r' could refer to 2 different points (x1, y1):

(r, y1) and (r+N, y1)  if   0 < r <2^128 - 2^32 (very rare case)

instead if r > 2^128 – 2^32  –> r+N > p there is only 1 possibility for (x1,y1):

(r, y1)


Moreover there are other 2 possibilities: for each x1, there are 2 points with the same x-coordinate and opposite y-values: y1 an n-y1 (for the symmetry).

When you derive the second part of the signature, s, you get 2 opposite values for (x1, y1) and (x1, N-y1):

s = k^-1 (z + rd) mod N

because s depends on k (and k*G = (x1, y1))

For the BIP 62 you have to choose the low value of s in Bitcoin, therefor s is determined by its value, not by your initial choice of k. You may have (x1, y1) or (x1, N-y1).


Note2)

when you perform the signature verification algorithm, starting from r, s^-1, Qa and the hash of the message (the transaction) you have to get the original x1 again:

u1 x G + u2 x Qa = (x'_1, y'_1)

you should get again the point (x1, y1), but there are actually 4 possibilities:

1) x'_1 = r  (0 < x1 < N, r = x1) and y is even             --> recid 0   –> verified
2) x'_1 = r  (0 < x1 < N, r = x1) and y is odd               --> recid 1   –> verified
3) x'_1 > r  (N < x1 < P,  r = x1 - N) and y is even       -->  recid 2  –> verified
4) x'_1 > r  (N < x1 < P,  r = x1 - N) and y is odd        -->  recid 3   –> verified

since you don't want to store the y1 value you got from k*G (the signature contains only r, almost always r = x-coordinate of k*G, and s), you want to know if the original y1 is even or odd  and if the original x1 is greater or less than N.

The following content was written by StraightCedar on July 09, 2020, 08:16:33 AM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)


Thanks to your kind instruction again, and I’m sorry for late reply.

According to your advice about the conversion “Higher sign-s” to “Lower sign-s”, I could calculate appropriate sign-s without retry, and it was able to be used for Ethereum communication.
I had a deeper understanding of it, so I could also optimize some process flows .

Thank you for your continued support.

Continue Reading
Click to comment

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Cryptography

Question on DER-encoding of signature pair (r, s)

I’ve been working through the byte-level details of bitcoin transactions and I need some help on DER-encoding.

Published

on

The following content was written by Peter R on June 15, 2014, 06:47:20 PM in the thread Question on DER-encoding of signature pair (r, s). All content is owned by the author of the bitcointalk.org post. (original)


I’ve been working through the byte-level details of bitcoin transactions and I need some help on DER-encoding.  

I understand how to (manually) sign a transaction to determine the signature pair (r, s), but I don’t understand how I take these two 256-bit numbers and pack them in the right order and with the proper padding for DER.  

For example, here are two inputs to a transaction that I would think should have equal-length signature scripts but they don’t.  The difference is circled in red (there are 33 bytes in the first component of the signature for INPUT 2 instead of 32).  




I found this excellent article on raw bitcoin transactions by Ken Shirriff.  Here’s a table Ken made to explain the byte-level packing:




Although this was extremely helpful, I think some things are not clear.  For instance:

   –  You can’t think of a signature as a curve point (x,y), right?  A signature is a pair of 256-bit numbers (r,s), not a point on secp256k1.  

   –  Did I mark-up the image correctly (r comes before s)?

   –  If I know r and s as 256-bit integers (big numbers), how exactly do I DER encode them?  


An aside: Besides DER being the standard format of OpenSSL, is there really any benefit to DER encoding?  It seems to me we could simply pack r and s and have all signatures exactly 64 bytes long.  


The following content was written by piotr_n on June 15, 2014, 07:04:35 PM in the thread Question on DER-encoding of signature pair (r, s). All content is owned by the author of the bitcointalk.org post. (original)


If the highest bit of the most significant byte is set, then you need to put 00 in front of it.

That is why fa gets 00 in front, but 46, 6f, and 15 do not

It comes from the protocol rule that the highest bit of the number means it is negative.
It’s a bit screwed up in there (because these numbers are never negative), but many things in bitcoin protocol are screwed up and it still somehow works Smiley

And yes, the most significant bytes come fist – but only here. Not in the hashes or scripts other places, where you have the opposite order.

The following content was written by Peter R on June 15, 2014, 07:14:50 PM in the thread Question on DER-encoding of signature pair (r, s). All content is owned by the author of the bitcointalk.org post. (original)


Awesome.  Thanks piotr_n.  I am assuming that I was correct and that r comes before s in the signature pair, too, right?

The following content was written by piotr_n on June 15, 2014, 07:18:24 PM in the thread Question on DER-encoding of signature pair (r, s). All content is owned by the author of the bitcointalk.org post. (original)


Awesome.  Thanks piotr_n.  I am assuming that I was correct and that r comes before s in the signature pair, too, right?
Yes, R comes before S.

Also there is a hash type byte at the end (SIGHASH_ALL in your case)
Be careful with this; if it would happen that there was more than one extra byte after S, hash type is always the last one of them (anything else you ignore)
There are transaction inside the chain with signatures screwed like this and if you don’t handle such cases properly you will loose time on investigating it.

The following content was written by DeathAndTaxes on June 15, 2014, 09:30:22 PM in the thread Question on DER-encoding of signature pair (r, s). All content is owned by the author of the bitcointalk.org post. (original)


As piotr_n pointed out the bitcoin expects the highest bit to be zero so if it isn't an extra zero byte is added.  This means that r & s will always be 32 or 33 bytes.  Don't quote me but I believe this is a bug in OpenSSL which was copied and now everyone has to keep the bug in the code to ensure it remains compatible.


Quote
You can't think of a signature as a curve point (x,y), right?  A signature is a pair of 256-bit numbers (r,s), not a point on secp256k1.
Correct. A point in computed in the creation of the signature (k x G) but it is not the signature itself.  r & s are not an x & y value. 

Quote
Did I mark-up the image correctly (r comes before s)?
Yes.

Quote
If I know r and s as 256-bit integers (big numbers), how exactly do I DER encode them?

You will also need to know the sighash.  Given r,s, and sighash they are arranged in the following order:


All elements are 1 byte except r & s which will be 32 or 33 bytes.  Also be sure to read up carefully on sighash because it is “moved” (for reasons that are beyond me).  Another Satoshi-ism I guess.

r_value = Convert r into a little endian byte array.  If the leading bit is not zero then prepend a zero value byte.
s_value = Convert s into a little endian byte array.  If the leading bit is not zero then prepend a zero value byte.
r_len = number of bytes for  r (always 20 or 21)
s_len = number of bytes for s (always 20 or 21)
sequence = always 0x30
integer = always 0x02
len_rs = r_len + s_len + 2 (two extra bytes for the two integer bytes)
len_sig = len_rs + 3 (three extra bytes for the len_rs byte, the sequence byte and the sighash byte

What follows next is whatever is needed to complete the script which is encumbering the outputs.  The PubKey then follows when redeeming Pay2PubKeyHash outputs but is not universally present in other output types (i.e. Pay2PubKey).  


Quote
An aside: Besides DER being the standard format of OpenSSL, is there really any benefit to DER encoding?  It seems to me we could simply pack r and s and have all signatures exactly 64 bytes long. 

Correct.  There is very little reason to use DER encoding other than satoshi did it that way.  A new version of the tx format could created which is more space efficient.  The major advantage of DER encoding is sharing information between incompatible systems.  It is excessively verbose to facilitate a data interchange.  Putting DER signature inside propreitary data makes no sense.  Knowing DER doesn't allow you to decode a Bitcoin tx, and if you can decode a Bitcoin tx you could just follow explicit rules to decode r,s, sighash, pubkeys, etc just like you need to follow explicit rules to decode the tx version, number of inputs, sequence, etc.




The following content was written by Peter R on June 16, 2014, 07:31:51 AM in the thread Question on DER-encoding of signature pair (r, s). All content is owned by the author of the bitcointalk.org post. (original)


Thanks Gerald.  Your explanation was perfectly clear. 

I’m starting to really appreciate the collaborative open-source development bitcoin promotes (which is new for me).  Instead of getting stuck and wasting a day spinning my wheels, I just post a question, move on to something else, and I when I check back often the problem is solved.  Hopefully lurkers read these posts and it answers some of their questions too.

The following content was written by amaclin on June 16, 2014, 08:15:39 AM in the thread Question on DER-encoding of signature pair (r, s). All content is owned by the author of the bitcointalk.org post. (original)


Quote
As piotr_n pointed out the bitcoin expects the highest bit to be zero so if it isn’t an extra zero byte is added.  This means that r & s will always be 32 or 33 bytes.

To be correct: R & S usually are 32 or 33 bytes. But can be smaller.
If highest bit of 256-bit integer is set we got 33 bytes ( probability is 1/2 )
If highest byte is greater than 0 and smaller than 128 we got 32 bytes ( probability 127/256 )
If highest byte is 0 – we should take R as 248-bit integer and repeat these steps

There are signatures in blockchain where the length of R or S is 29, 30, 31

The following content was written by deepceleron on June 18, 2014, 03:47:18 AM in the thread Question on DER-encoding of signature pair (r, s). All content is owned by the author of the bitcointalk.org post. (original)


The signature data is encoded using ASN.1 stream encoding. Although Bitcoin implementations just shove signature bytes where they should go, it would be more correct to actually use an ASN library to make the DER-encoded signatures. That way there would not be mystery undocumented bit-set data such as the tag identifier, which are not just arbitrary bytes, but define the encoding method of the following bytes.

I documented this a bit before, walking through each byte of a transaction with the DER docs in hand (although I didn’t make a pretty table):


Transaction data format version (uint32_t):
01000000

TXIN:
    TX_IN count (number of Transaction inputs, satoshi VarInt):
    01
    TXIN DATA:
    Previous txout hash:
    21eb234bbd61b7c3d31034762126a64ff046b074963bf359eaa0da0ab59203a0
    Previous txout index:
    01000000
    Script Length:
    8b
        Signature Length: (48h = 72 bytes)
        48
        ECDSA Signature (X.690 DER-encoded):
            ASN.1 tag identifier (20h = constructed + 10h = SEQUENCE and SEQUENCE OF):
            30
            DER length octet, definite short form (45h = 69 bytes) (Signature r+s length)
            45
            ASN.1[/url] tag identifier (02 = INTEGER):
            02
             Signature r length (DER length octet):
             20
             Signature r (unsigned binary int, big-endian):
             263325fcbd579f5a3d0c49aa96538d9562ee41dc690d50dcc5a0af4ba2b9efcf
            ASN.1[/url] tag identifier (02 = INTEGER):
            02
             Signature s length (DER length octet):
             21
             Signature s (first byte is 00 pad to protect MSB 1 unsigned int):
             00fd8d53c6be9b3f68c74eed559cca314e718df437b5c5c57668c5930e14140502
        Signature end byte (SIGHASH_ALL):
        01

    Key length:
    41
        Public Key prefix:
        04
        Public Key part x
        52eca3b9b42d8fac888f4e6a962197a386a8e1c423e852dfbc58466a8021110e
        Public Key part y
        c5f1588cec8b4ebfc4be8a4d920812a39303727a90d53e82a70adcd3f3d15f09
    Sequence Number:
    ffffffff

TXOUT:
    txout number:
    01
    Value in base units:
    a086010000000000
        Script Length (107 bytes):
        6b

        Script (if we were to run it):
        OP_PUSHDATA1 – The next byte contains the number of bytes to be pushed onto the stack:
        4c
        Bytes (68 = 104 bytes):
        68
        STACK DATA 104 bytes:
        4c554b452d4a522049532041205045444f5048494c4521204f682c20616e6420
        676f642069736e2774207265616c2c207375636b612e2053746f7020706f6c6c
        7574696e672074686520626c6f636b636861696e207769746820796f7572206e
        6f6e73656e73652e

Lock Time (cannot be included before this block):
00000000


Continue Reading

Cryptography

Using secp256k1 endomorphism

The existence of the endomorphism is a roughly 20% speedup in a plain multi-exp due to halving the number of doublings.

Published

on

The following content was written by Jean_Luc on July 02, 2020, 08:24:44 PM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


The existence of the endomorphism is a roughly 20% speedup in a plain multi-exp due to halving the number of doublings. What it does is gives many algorithms which could be batched across multiple point the efficiency they’d have at twice the number of pubkeys.  It’s a pretty big speedup and AFAIK at an equivalent level of optimization it makes secp256k1 the fastest to verify of any widely deployed curve. So the motivation there is pretty clear, I think.

Could you give more info on this because I don’t see how to have efficient decomposition k.P= (k1+k2.lambda).P using such lambda.
Thanks

The following content was written by gmaxwell on July 02, 2020, 08:44:10 PM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


Could you give more info on this because I don’t see how to have efficient decomposition k.P= (k1+k2.lambda).P using such lambda.

Sure!

You rewrite   k*P as  k1*P + k2*lambda*P  —  lambda*P is trivial to compute, since its {beta * P.x, P.y} and k1 and k2 are 128-bit numbers instead of 256. Then this sum of products can be computed efficiently using Strauss’ algorithm (also called Shamir Trick) or similar.

Here is an implementation that splits k into k1 and k2 for secp256k1: https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_impl.h#L268  with a couple scalar operations.

The endomorphism optimization in libsecp256k1 is (currently) disabled by default (and can be enabled via a configure option) because it’s potentially covered by a patent that expires pretty soon. (I think history suggests that the patent is actually invalid, but the benefit isn’t great enough to worry about it).

The implementation in libsecp256k1 is a little more complicated than described above due to some common and some novel optimizations in its version of Strauss’ algorithm.  It uses WNAF so it pre-computes a small table of P times odd numbers using an efficient addition ladder. It then performs all the additions over an alternative isomorphic curve so that it’s able to treat the precomputed P multiplies as affine points without needing an inverse to reproject them.  As a result the application of beta is done on demand late in the algorithm rather than needing to compute two tables.

The following content was written by Jean_Luc on July 03, 2020, 07:52:19 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


@gmaxwell
Many thanks Wink
I discovered this book “Guide to Elliptic Curve Cryptography” which is great Wink

The following content was written by Jean_Luc on July 03, 2020, 11:44:30 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


I implemented the algorithm 3.74 of the above book and I found different results:
At iteration #70/#71, I well found the same constants a1 and a2 that are mentioned in the comment of the code.
but b1 and b2 are different and strangely b2=a1 in the comment Huh
I would expect b1 = -1839468DB3DC795B42AD17D3CA5C15137 and b2 = 4A5AC2BF7B5F37F9F1DB10D7A2A9C981.
I didn’t check yet g1 and g1 constants.

Code:
* “Guide to Elliptic Curve Cryptography” (Hankerson, Menezes, Vanstone) gives an algorithm
 * (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1
 * and k2 have a small size.
 * It relies on constants a1, b1, a2, b2. These constants for the value of lambda above are:
 *
 * – a1 =      {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
 * – b1 =     -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3}
 * – a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8}
 * – b2 =      {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}


Code:
s0=1
t0=0
r0=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

s1=0
t1=1
r1=5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72

s2=1
t2=E
r2=5D4F819BEEB6D5E108DABF867C8D2F0842474284DC46CD122CA9B187ECB08EB


s70=FCE9B1DD4EB7DD2718A2906787061B2
t70=4A5AC2BF7B5F37F9F1DB10D7A2A9C981
r70=114CA50F7A8E2F3F657C1108D9D44CFD8   (>sqrt(n))

s71=4A5AC2BF7B5F37F9F1DB10D7A2A9C981
t71=1839468DB3DC795B42AD17D3CA5C15137
r71=3086D221A7D46BCDE86C90E49284EB15  (


The following content was written by j2002ba2 on July 03, 2020, 01:53:22 PM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


@Jean_Luc Your code for EEA seems incorrect. Here are the correct values:
Code:
s70=FCE9B1DD4EB7DD2718A2906787061B2
t70=-3086D221A7D46BCDE86C90E49284EB15
r70=114CA50F7A8E2F3F657C1108D9D44CFD8   (>=sqrt(n))

s71=-4A5AC2BF7B5F37F9F1DB10D7A2A9C981
t71=E4437ED6010E88286F547FA90ABFE4C3
r71=3086D221A7D46BCDE86C90E49284EB15  (
s72=1839468DB3DC795B42AD17D3CA5C15137
t72=-4A5D84C4FAD1D149815130F31C84462E4
r72=2228364F61BCD8F0CDA23C16C0AC386F

Code:
(a1, b1) = (r71, -t71) = (3086D221A7D46BCDE86C90E49284EB15, -E4437ED6010E88286F547FA90ABFE4C3)
(a2, b2) = (r70, -t70) = (114CA50F7A8E2F3F657C1108D9D44CFD8, 3086D221A7D46BCDE86C90E49284EB15)
r70^2 + t70^2 = 13477B4472B4233ECA232A74B45B8E7F37640C02AF64BF4EEAEE3ABED3D0695F9
r72^2 + t72^2 = 159EC1A05B158DF471EAE76C8FA0CDA199E5599D41EC1E5915FBD403A750EC1B31

The following content was written by Jean_Luc on July 04, 2020, 07:11:58 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


Jean_Luc, hi. Then you include endomorfism to yout project – vanitysearch and kangaroo ?

VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry.

Quote
Now we need a rule to define a unique representative for each equivalence class {P,−P}. A simple rule in this case is: treat they-coordinate of P as an integer 0≤yP< qand let the unique representative be (xP,min{yP,q−yP}). The pseudorandomwalk is then defined using the unique equivalence class representative.
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf

But symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance.

The following content was written by arulbero on July 04, 2020, 07:41:11 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)



But symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance.

I did some tests with symmetry (python for cpu), with num_jumps = 32 you can get 1.6 / 1.7.sqrt(N) steps (instead of 2.08.sqrt(N)) if the DP is 12 or lower.

With longer paths you have to increase the number of the jumps, and that decreases the performance.

The following content was written by COBRAS on July 04, 2020, 10:58:13 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


Jean_Luc, hi. Then you include endomorfism to yout project – vanitysearch and kangaroo ?

VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I’m note sure it is possible to define equivalence classes for endomorphism as for symmetry.

Maybe 128 byte keys is more good I think. 256 byte is harde to fined !!! Implement please endomorphism in Kangaroo Bro ?

The following content was written by gmaxwell on July 06, 2020, 01:30:05 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


I’m note sure it is possible to define equivalence classes for endomorphism as for symmetry.
All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back)

The following content was written by Jean_Luc on July 06, 2020, 05:44:23 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back

Yes I know, but I don’t see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles.
If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk.
Any idea would be welcome Wink

The following content was written by arulbero on July 06, 2020, 06:09:17 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back

Yes I know, but I don’t see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles.
If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk.
Any idea would be welcome Wink


Each step (each jump) must depend on the last bits of x^3 mod p.  But you have no advantage in the search in [-(a+b)/2,(a+b)/2] interval, you have a speedup only in the union of 3 intervals:  [-(a+b)/2,(a+b)/2] U [-lambda*(a+b)/2,lambda*(a+b)/2] U [-lambda^2*(a+b)/2,lambda^2*(a+b)/2]

The following content was written by Jean_Luc on July 06, 2020, 06:57:50 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


Yes and the overlap between these ranges will be very small unless you search on very large range.
I’m wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution.
Of course computing a modexp is expensive but just for try…

Code:
0^((P-1)/3): 0
 1^((P-1)/3): 1
 2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
 3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
 4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
 5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
 6^((P-1)/3): 1
 7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
 8^((P-1)/3): 1
 9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
10^((P-1)/3): 1
11^((P-1)/3): 1
12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
13^((P-1)/3): 1
14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
17^((P-1)/3): 1
18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
19^((P-1)/3): 1
20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

The following content was written by gmaxwell on July 06, 2020, 07:31:08 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


Each step (each jump) must depend on the last bits of x^3 mod p.  But you have no advantage in the search in [-(a+b)/2,(a+b)/2] interval, you have a speedup only in the union of 3 intervals:  [-(a+b)/2,(a+b)/2] U [-lambda*(a+b)/2,lambda*(a+b)/2] U [-lambda^2*(a+b)/2,lambda^2*(a+b)/2]
Right.  I don’t know a way to use the endomorphism to get a speedup over a single compact interval– and I somewhat doubt that it’s possible.  If it were, then I think in the application of endomorphism to the multiexp it would be possible to recursively apply the endomorphism to decompose to smaller and smaller scalars, but it isn’t.

The speedup over the set of three intervals is still potentially interesting:  e.g. imagine you have an elgammal encryption where the decryption leaves with with a point you need to take the discrete log. And you can arrange that the DL is in some small enough range that this isn’t unrealistic, and could potentially support the sparse ranges.

This shows up in things like electronic voting or in confidential transactions. (In CT I avoided the need to solve a DL in the receiver by sneaking an encryption of it into a sidechannel in the range proofs)…. or just for DL challenge bragging rights.


The following content was written by COBRAS on July 06, 2020, 09:00:21 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


Yes and the overlap between these ranges will be very small unless you search on very large range.
I’m wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution.
Of course computing a modexp is expensive but just for try…

Code:
0^((P-1)/3): 0
 1^((P-1)/3): 1
 2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
 3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
 4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
 5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
 6^((P-1)/3): 1
 7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
 8^((P-1)/3): 1
 9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
10^((P-1)/3): 1
11^((P-1)/3): 1
12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
13^((P-1)/3): 1
14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
17^((P-1)/3): 1
18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
19^((P-1)/3): 1
20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

Good Day everybody.

128 bytes is big range i think, if endomorphism can solve so ranges it will be supper. But if no method for solve 128-256 bytes, I think all solutions will hard work with something another then puzzle addresses.

The following content was written by Jean_Luc on July 06, 2020, 09:47:53 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller Wink

The following content was written by COBRAS on July 06, 2020, 10:32:55 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)


A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller Wink


Yes, but with endomorphism needed only 128 bytes for solve 256 and only 64 for solve 128 !!!  Wink

p.s. and as i know endomorphism +0.7 fester !!!

Continue Reading

Cryptography

Encrypting messages question

It isn’t the same with signing/verifying that you prove you own the address.

Published

on


The only theing you need to encrypt a message is its text and a public key. What’s the point?? I can encrypt a message from satoshi’s public key then. What will I achieve? I can get the public key of an address right?

It isn’t the same with signing/verifying that you prove you own the address.

The following content was written by ranochigo on July 09, 2020, 01:29:21 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


ECDSA allows you to encrypt a message such that with a public key, you’ll be able to send it to everyone and only the person that has the correct private key pair would be able to decrypt and read the message. This is useful if you’re sending someone sensitive information and you don’t want anyone to eavesdrop on it while only the correct recipient could decipher the message.

When Electrum asks for the public key, it’s asking for the ECDSA public key and not the public key hash.

It operates similarly to PGP.

The following content was written by BlackHatCoiner on July 09, 2020, 01:39:59 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


Oh… I now got it… Only the person with the public key’s private key can decrypt it. No one else.

Code:
QklFMQIPIyVDBdGqsSS9ZEivHPstRUmp0aUKEwnGrpFsBNm/VaYCPzUoblM2EKVhwVLpaZ25upZjhCbV3R0rPm88Jvh5sbOJBwxM1Ib4iD5Bfac5SYDLxTKf5droxbs7lbWFj9DbB/7C/KZiq6nNiD1iGE0vTTlMmPhB+r4nXPEzo/zV3A==

I encrypted this to my personal address’ public key: 02ce99b57451cd90aef6bd8028df82bd7fbbfea93b40f4da45d13a4b401ae367f0

So, right now I can only know what’s there Smiley Grin

Thanks @ranochigo. Does this way of encryption have a name? Like SHA256 (for hash)

The following content was written by BrewMaster on July 09, 2020, 03:13:17 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


Does this way of encryption have a name?

Elliptic Curve Integrated Encryption System or ECIES for short. it is defined in the Standard For Efficient Cryptography 1 section 3.8 and i believe that is the algorithm that Electrum uses too.
here is a wikipedia link: https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme

The following content was written by BlackHatCoiner on July 11, 2020, 11:22:44 AM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


About electrum:

Can I somehow insert the address itself and not the whole public key? It asks me the public key and it is a small procedure to get the public key from an address.

The following content was written by ranochigo on July 11, 2020, 11:51:41 AM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


About electrum:

Can I somehow insert the address itself and not the whole public key? It asks me the public key and it is a small procedure to get the public key from an address.
Its not. You can’t get a public key from an address as an address is a hash of the public key. Since the hash is a one way function, you can’t get the ECDSA public key from an address.

The main trick that people tend to use is to obtain the public key from a transaction that spends UTXOs from that specific address since the script would reveal its public key.

The following content was written by khaled0111 on July 11, 2020, 04:28:42 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


What do you mean by inserting an address and what for?
If you mean to import it into Electrum then yes, it’s possible. But it will only create a watching-only wallet that can be used to monitor the addresse’s history/activity.
Using a watching-only wallet, you will not be able to sign or encrypt messages if this is what you want to achieve.

The following content was written by BlackHatCoiner on July 11, 2020, 04:40:00 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


What do you mean by inserting an address and what for?
If you mean to import it into Electrum then yes, it’s possible. But it will only create a watching-only wallet that can be used to monitor the addresse’s history/activity.
Using a watching-only wallet, you will not be able to sign or encrypt messages if this is what you want to achieve.


No, I mean that one:


Instead of writing the public key, to write the address.

The following content was written by khaled0111 on July 11, 2020, 05:04:26 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


^^ no, it won’t work. As you can see, you need the public key not the address to encrypt a message.
You will have to ask the one you want to send the encrypted message to to give you his public key or do what ranochigo suggested since there is no other way to retrieve a public key from an address.

The following content was written by BlackHatCoiner on July 11, 2020, 05:09:07 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


Right now, the encryption thing goes like that:

1) I ask a guy to give me his public key.
2) I encrypt a message
3) I send him the encrypted message.

Since only if he owns the address, he can decrypt the message, why can’t we simply skip the step 1?

The following content was written by khaled0111 on July 11, 2020, 05:57:03 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


You can’t skip the first step. How are you going to encrypt the message then!
In asymetric encryption, a key pair is needed. a public key known to everyone used to encrypt the message and a corresponding private key known by only the one who generated it and the only one supposed to decrypt the message.
Asymetric encryption solves the main problem with symetric encryption (where one key is used for both encryption and decryption) which is how to safely share the key without being intercepted by a malicious party.

The following content was written by HCP on July 11, 2020, 10:16:41 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


1) I ask a guy to give me his public key.

Since only if he owns the address, he can decrypt the message, why can’t we simply skip the step 1?

Because, as the others have mentioned, there is simply no way to get the public key from an address… (ignoring that you could go trawling through the blockchain for transactions where that address was used to provide an input, and get the public key from the transaction data).

Private Key -> ONE WAY hash elliptic curve multiplication -> Public Key -> ONE WAY hash -> Address

You can only go from left to right… you can’t go the other way. If the person you’re attempting to send the message to doesn’t provide the public key, there is no way to encrypt the message so only their private key can decrypt it.


EDITED for the sake of correctness.

The following content was written by mikeywith on July 11, 2020, 11:01:50 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


Right now, the encryption thing goes like that:

1) I ask a guy to give me his public key.
2) I encrypt a message
3) I send him the encrypted message.

Since only if he owns the address, he can decrypt the message, why can’t we simply skip the step 1?

For starters, you should forget about bitcoin address, imagine it doesn’t exist, think of it simply as a different representation of a public key, next you need to understand basic Public-key cryptography, the simplest way to look it is by imagining a scenario where you need to send your friend something as a gift, say it’s a gold coin, you are going to send it using a third-party which you don’t trust, that coin is so expensive and you are afraid that somebody will steal it, so you decide to put that coin in money/cash box and send the whole box to your friend, you can simply purchase a new box, send the key and the box together (a terrible idea) or send the lock and the key separately (a bad idea)or a better way would be asking your friend to buy the box and send it to you (unlocked) and of course, he will keep the keys.




So now you put that coin in the box, and then you lock it (notice that you don’t need the key to lock the box, but you need the key to unlock it) and then send it via an untrusted medium.





Your friend gets it and he uses the keys (since it’s his lock and only he has the keys – not even you have the keys) and bingo, the coin arrives safely.

The box = Your friend’s public key ( he can safely share it with others)
They keys = Private keys (He must not share it with others)
The coin = The encrypted message (The transporter knows there is something inside the box, but he doesn’t know what that is)

You can’t skip any part of those three.


Yes but I’m trying to say that if a person can decrypt the hash(private_key) (which is the public key), he can do it for the hash(hash(private_key)) too. (which is the address)


Well actually the address is more like hash(hash(hash(private_key))), you need to hash the public key twice first using sha256 and then ripemd160, but you are correct, your friend doesn’t need you to send him the public key nor the address, using his private key he knows what is the public key as well as the address, but YOU need HIS public key to encrypt a message which then he can decrypt using his private key.

The following content was written by BlackHatCoiner on July 12, 2020, 07:12:34 AM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


First of all, a thank you for making this post. It was really nice explanation.

Quote
your friend doesn’t need you to send him the public key nor the address, using his private key he knows what is the public key as well as the address, but YOU need HIS public key to encrypt a message which then he can decrypt using his private key

Both public key and address are texts that no one can do something to steal your coins.

Both public key and address begin from the same string (private key)

Both public key and address mean the same thing. (If you have the public key you can make the address)

I just don’t get why we can’t use the address as ”The Box”.

The following content was written by ranochigo on July 12, 2020, 08:24:18 AM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


Both public key and address are texts that no one can do something to steal your coins.
Correct.
Both public key and address begin from the same string (private key)
If you mean deriving both then yes. But it’s important to note that your address is derived from the public key and not the private key.
Both public key and address mean the same thing. (If you have the public key you can make the address)

I just don’t get why we can’t use the address as ”The Box”.
They don’t. Address is a public key hash.

For ECDSA signatures to work, they need the public key to be able to validate the signature or to decrypt the message (in the case of ECIES). The addresses are a totally new format that is created by one of the earlier Bitcoin contributors and is not a product of the development of ECDSA.

An address is useless in the encryption of the message since it is not an ECDSA public key. The main point is: You need the public key. Yes, you can derive the address from a public key but you can’t go the other way around. It’s just like you can use flour to bake a cake but you can’t use the cake to make flour; it’s irreversible.

The following content was written by o_e_l_e_o on July 12, 2020, 10:39:51 AM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


Private Key -> ONE WAY hash -> Public Key -> ONE WAY hash -> Address
I know you know and that you’ve just made a typo, but for the sake of other users reading this thread, private key to public key is via a one way elliptic curve multiplication, not a one way hash.

Yes but I’m trying to say that if a person can decrypt the hash(private_key) (which is the public key), he can do it for the hash(hash(private_key)) too. (which is the address)
As above. The public key is not a hash of the private key, and therefore the address is not a double hash of the private key. Incidentally, to calculate the address from the public key (where we do use hashing functions), we use two different functions – first SHA256, then RIPEMD160.

The following content was written by mikeywith on July 12, 2020, 03:47:41 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


Both public key and address mean the same thing. (If you have the public key you can make the address)

I just don’t get why we can’t use the address as ”The Box”.

Not sure how do I explain this, technically you can actually use bitcoin address to encrypt a message, but only in symmetric encryption fashion, what you need here is asymmetric encryption (Publick Key encryption), bitcoin address is ripemd-160 bit hash of the public key which is 256 bits, so in short, the address and the private key are in a different format and thus the encryption algorithm won’t work on the address, in the box example you would imagine the address as a very small box that can’t handle the coin nor the lock.

So if you now understand that the address in its simplest form can’t be used, you might still ask, well if the address is hash for the public key why can’t we encrypt it? first of all, just because you know the address, and you know it’s the hash of a public key, you simply can’t reconstruct the public key from the address.

also after reading this part again

Quote
The only thing you need to encrypt a message is its text and a public key. What’s the point?? I can encrypt a message from satoshi’s public key then. What will I achieve? I can get the public key of an address right?

It isn’t the same with signing/verifying that you prove you own the address.

It seems like you are confusing encryption to a signature, ECDSA is designed for signature and shouldn’t really be used for encryption anyway, there are far better options that were designed for the sole purpose of message encryption.

The following content was written by bob123 on July 12, 2020, 07:59:37 PM in the thread Encrypting messages question. All content is owned by the author of the bitcointalk.org post. (original)


Yes but I’m trying to say that if a person can decrypt the hash(private_key) (which is the public key), he can do it for the hash(hash(private_key)) too. (which is the address)

Hashing and encrypting is something completely different.
Hashing is a one-way function. Easy and fast to calculate the hash of an input, but practically impossible to calculate the input out of the hash.

An encryption on the other hand can be reversed by knowing the corresponding key. Since you were referring to asymmetric encryption, the necessary key here is the private key while the public key is used to encrypt the message.



Both public key and address are texts that no one can do something to steal your coins.

Correct.



Both public key and address begin from the same string (private key)

Correct.


Both public key and address mean the same thing. (If you have the public key you can make the address)

They do not “mean the same thing”.
On a technical level, addresses don’t exist. They are made for humans.

And yes, the address can be derived from the public key by using the corresponding hash function(s).



I just don’t get why we can’t use the address as ”The Box”.

Because messages are signed with a private key and verified by the public key.
Messages are encrypting with the public key and encrypted with the private key.

You can not use the address, because you can not get the public key out of the address. Only the other way around (public key -> address via one-way function).

Continue Reading

Trending