-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathHow-kangaroo-works?.txt.txt
159 lines (155 loc) · 5.51 KB
/
How-kangaroo-works?.txt.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
The Bitcoin Kangaroo algorithm, a specialized implementation of the Pollard's Kangaroo algorithm, is used for solving the discrete logarithm problem in elliptic curve cryptography (ECC). Specifically, it is used to find a private key
𝑘
k given a public key
𝑃
=
𝑘
⋅
𝐺
P=k⋅G, where
𝐺
G is the generator point on the secp256k1 curve used in Bitcoin. The algorithm is often applied to a restricted range, like in Bitcoin "puzzle challenges," to find the private key within a given range if it exists. Let's walk through the components and structure of the algorithm in detail.
1. Overview of Pollard’s Kangaroo Algorithm
Pollard’s Kangaroo algorithm, or the Pollard lambda method, is a "distinguished points" algorithm that is well-suited for solving the discrete logarithm problem on a cyclic group. The algorithm is designed to work with a target in a known interval, so you know the approximate range of the solution. It uses two parallel "walks" — one starting with the "tame" kangaroo and the other with the "wild" kangaroo — and tries to capture the target by having the paths of the two kangaroos intersect within this range.
2. Key Concepts and Terminology
Elliptic Curve Discrete Logarithm Problem (ECDLP): This is the problem of finding the integer
𝑘
k such that
𝑃
=
𝑘
⋅
𝐺
P=k⋅G on an elliptic curve, given
𝑃
P and
𝐺
G. The solution
𝑘
k is the private key.
Tame Kangaroo: A calculated point that starts at one end of the interval (typically closer to the known range).
Wild Kangaroo: Another calculated point that starts closer to the unknown value or randomly within the interval.
Distinguished Points: These are points with certain characteristics, usually chosen to simplify tracking, like having specific bits set to zero. They serve as markers to know when the kangaroos' paths cross.
3. Structure and Steps of the Bitcoin Kangaroo Algorithm
The algorithm involves multiple steps to ensure the tame and wild kangaroos will eventually "collide" and identify the unknown discrete logarithm. Here’s a breakdown of each component and step:
Step 1: Define the Interval
Determine the target interval
[
𝑎
,
𝑏
]
[a,b] where you suspect the private key
𝑘
k to lie.
This interval size affects the speed of the algorithm since it’s designed to efficiently explore smaller, known intervals.
Step 2: Initialize the Kangaroos
Tame Kangaroo: Set this kangaroo to start from a known point close to the beginning of the interval. Set
𝑋
0
X
0
to a point in the range, and its associated "distance" as
𝑑
0
d
0
.
Wild Kangaroo: This one starts closer to the target or at a random point in the interval. Set
𝑌
0
Y
0
to an unknown location in the range and assign it a distance
𝑑
0
d
0
.
Step 3: Define the Step Function
A step function is defined to control how each kangaroo hops along the curve. The step function ensures that both the tame and wild kangaroos hop across the interval deterministically.
Each hop is determined by a hash function on the current point, which creates a "pseudo-random" step within a predefined set of steps.
For a point
𝑅
R, the step function
𝑓
(
𝑅
)
f(R) determines how far the kangaroo should move. This keeps the walk non-linear and prevents predictable cycles.
Step 4: Compute Walks with Distinguished Points
The tame and wild kangaroos begin their walks across the interval by repeatedly applying the step function.
The algorithm tracks the distinguished points (points with a specific characteristic) reached by each kangaroo.
Each kangaroo moves to a new position
𝑃
𝑖
P
i
by calculating
𝑃
𝑖
=
𝑃
𝑖
−
1
+
𝑓
(
𝑃
𝑖
−
1
)
⋅
𝐺
P
i
=P
i−1
+f(P
i−1
)⋅G.
Both the tame and wild kangaroo walks continue until they reach the same distinguished point, implying they have intersected paths.
Step 5: Check for Collision and Calculate Private Key
When the tame and wild kangaroo meet at the same distinguished point, the algorithm can use their distance values to calculate the target private key.
The distance covered by each kangaroo gives the relationship:
𝑘
=
𝑑
tame
−
𝑑
wild
k=d
tame
−d
wild
Given the modulus of the curve’s order, this calculation reveals the private key.
Step 6: Validate the Solution
Once a potential
𝑘
k is found, it’s essential to validate that
𝑘
⋅
𝐺
=
𝑃
k⋅G=P to confirm the solution.
This validation ensures that the collision did indeed reveal the correct private key.
4. Optimizations and Practical Considerations
Distinguished Point Optimization: Use distinguished points with a specific bit pattern (e.g., the last few bits being zero) to reduce memory storage requirements and increase efficiency.
Memory Considerations: Storing every point in large intervals can be memory-intensive, so using specific markers (distinguished points) helps reduce storage needs.
Parallelization: For larger intervals, running multiple wild kangaroos in parallel can improve the chance of finding a collision faster, but it requires more computational resources.
Summary
The Bitcoin Kangaroo algorithm, with two synchronized kangaroo walks within a restricted interval, can efficiently find the discrete logarithm (private key) when it exists within that interval. By employing a combination of a step function, distinguished points, and collision detection, the algorithm narrows down the private key.