g0^i mod (q-1)
What is i in g0^i mod (q-1)
i is range.What is i in g0^i mod (q-1)
Topic: A Small Subgroup Attack bitcoin (Read 242 times)
g0^i mod (q-1)
What is i in g0^i mod (q-1)
i is range. What is i in g0^i mod (q-1)
thank you very much 
What is i in g0^i mod (q-1)
Like I said, i is an integer ranging from 0 through 18051648 - 1.
So the private keys are 1, g0, g0^2 mod (q-1), g0^3 mod (q-1), ... , g0^18051647 mod (q-1).
g0^i mod (q-1)
What is i in g0^i mod (q-1)
What is i in g0^i mod (q-1)
Could someone enlighten me on this subject because I can't figure out how these 18051648 addresses are generated.
Perhaps reading this paper will help:
https://www.researchgate.net/publication/362472418_Special_Subsets_of_Addresses_for_Blockchains_Using_the_secp256k1_Curve
Section 4 details the generation of addresses from the private keys g0^i mod (q-1), with g0 = 7^{p1*p2*p3}, and 0 <= i < 18051648.
Could someone enlighten me on this subject because I can't figure out how these 18051648 addresses are generated.
Thank you.
Subgroup Detection
Since private keys are elements of Zq∗
, a straight brute force attack to the Bitcoin system seems infeasible, as inverting the map
ϕ:Zq∗⟶,k⟶k⋅P
would imply solving an ECDLP instance.
However, there are few small subgroups H≤Zq∗
that may be inspected, for which an exhaustive computation of all the possible keys and corresponding addresses may be carried out. This way one may compute the inverse of the restricted map
ϕ|H:⟶G.
Since the keys are supposed to be uniformly distributed, there is no probabilistic argument suggesting their presence in specific small subgroups. However, assuming that this is the case, we need to choose a suitable subgroup. In this view, by considering the factorization of q−1
into prime integers
q−1=26×3×149×631×107361793816595537p1×174723607534414371449p2×341948486974166000522343609283189p3,,
it is not difficult to test that the maximal subgroup of moderate size (i.e. that can today be checked with an average computer) contains N elements, where
N=26×3×149×631=18051648.
Such a group may be easily produced by considering any primitive element t of Zq
, such as t=7, and considering the element g=tp1×p2×p3, which generates the subgroup
H=={gi∣∣1≤i≤18051648}.
Indeed, we summarize in the following theorem two well-known results.
Theorem 1. Let F
be a field. Then, any finite subgroup G≤F∗ is cyclic. Moreover, for every positive integer M dividing |G|, there is a unique subgroup H≤G such that |H|=M
.
Subgroup Inspection
The group H as previously defined has less than 20 millions elements; therefore, we were able to straightforwardly construct, in a few days, the BTC addresses originated by all private keys k∈H
and to check whether they have appeared in the BTC blockchain since its creation until 2018.
We recall that an address appears in the blockchain whenever it receives any amount of bitcoin. Note that the number of addresses in the BTC blockchain does not correspond to the number of actual BTC users, as modern wallets handle many different addresses for each user.
With this procedure, we found 4 BTC addresses, in which private keys belong to H:
1PSRcasBNEwPC2TWUB68wvQZHwXy4yqPQ3,
1B5USZh6fc2hvw2yW9YaVF75sJLcLQ4wCt,
1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm,
1JPbzbsAx1HyaDQoLMapWGoqf9pD5uha5m.
Two of them, (3) and (4), came from the trivial keys 1 and −1
, and they might have been generated on purpose, but the remaining two addresses appear to be legit. In particular, a blockchain inspection (Reference [21], 2018) suggests that one of them (2) has been used as temporary address for moving a small amount of bitcoins, while the other (1) has probably been used as a personal address, since its owner has stored some bitcoins there for 4 years.
To show that the private key of address (1) was really recovered, we used three of our addresses
A. 1FCuka8PYyfMULbZ7fWu5GWVYiU88KAU9W,
B. 1NChjA8s5cwPgjWZjD9uu12A5sNfoRHhbA,
C. 1695755gMv3fJxYVCDitMGaxGu7naSXYmv,
and we performed tiny transactions from each of them, as shown in Figure 3.
These operations may be easily verified through any blockchain explorer, such as Reference [21], by searching for their transaction IDs:
T1. 69ad7033376cea2bbea01e7ef76cc8d7bc028325e9179b2231ca1076468c1a1e,
T2. 1dd5c256a1acc81ea4808a405fd83586ea03d8b58e29a081ebf3d0d95e77bf63,
T3. b722c77dcdd13c3616bf0c4437f2eb63d96346f74f4eeb7a1e24c1a9711fc101.
Thank you.
Subgroup Detection
Since private keys are elements of Zq∗
, a straight brute force attack to the Bitcoin system seems infeasible, as inverting the map
ϕ:Zq∗⟶,k⟶k⋅P
would imply solving an ECDLP instance.
However, there are few small subgroups H≤Zq∗
that may be inspected, for which an exhaustive computation of all the possible keys and corresponding addresses may be carried out. This way one may compute the inverse of the restricted map
ϕ|H:⟶G.
Since the keys are supposed to be uniformly distributed, there is no probabilistic argument suggesting their presence in specific small subgroups. However, assuming that this is the case, we need to choose a suitable subgroup. In this view, by considering the factorization of q−1
into prime integers
q−1=26×3×149×631×107361793816595537p1×174723607534414371449p2×341948486974166000522343609283189p3,,
it is not difficult to test that the maximal subgroup of moderate size (i.e. that can today be checked with an average computer) contains N elements, where
N=26×3×149×631=18051648.
Such a group may be easily produced by considering any primitive element t of Zq
, such as t=7, and considering the element g=tp1×p2×p3, which generates the subgroup
H=
Indeed, we summarize in the following theorem two well-known results.
Theorem 1. Let F
be a field. Then, any finite subgroup G≤F∗ is cyclic. Moreover, for every positive integer M dividing |G|, there is a unique subgroup H≤G such that |H|=M
.
Subgroup Inspection
The group H as previously defined has less than 20 millions elements; therefore, we were able to straightforwardly construct, in a few days, the BTC addresses originated by all private keys k∈H
and to check whether they have appeared in the BTC blockchain since its creation until 2018.
We recall that an address appears in the blockchain whenever it receives any amount of bitcoin. Note that the number of addresses in the BTC blockchain does not correspond to the number of actual BTC users, as modern wallets handle many different addresses for each user.
With this procedure, we found 4 BTC addresses, in which private keys belong to H:
1PSRcasBNEwPC2TWUB68wvQZHwXy4yqPQ3,
1B5USZh6fc2hvw2yW9YaVF75sJLcLQ4wCt,
1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm,
1JPbzbsAx1HyaDQoLMapWGoqf9pD5uha5m.
Two of them, (3) and (4), came from the trivial keys 1 and −1
, and they might have been generated on purpose, but the remaining two addresses appear to be legit. In particular, a blockchain inspection (Reference [21], 2018) suggests that one of them (2) has been used as temporary address for moving a small amount of bitcoins, while the other (1) has probably been used as a personal address, since its owner has stored some bitcoins there for 4 years.
To show that the private key of address (1) was really recovered, we used three of our addresses
A. 1FCuka8PYyfMULbZ7fWu5GWVYiU88KAU9W,
B. 1NChjA8s5cwPgjWZjD9uu12A5sNfoRHhbA,
C. 1695755gMv3fJxYVCDitMGaxGu7naSXYmv,
and we performed tiny transactions from each of them, as shown in Figure 3.
These operations may be easily verified through any blockchain explorer, such as Reference [21], by searching for their transaction IDs:
T1. 69ad7033376cea2bbea01e7ef76cc8d7bc028325e9179b2231ca1076468c1a1e,
T2. 1dd5c256a1acc81ea4808a405fd83586ea03d8b58e29a081ebf3d0d95e77bf63,
T3. b722c77dcdd13c3616bf0c4437f2eb63d96346f74f4eeb7a1e24c1a9711fc101.
Jump to: