-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathmap.txt
240 lines (196 loc) · 9.82 KB
/
map.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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
{
title: The Map
description: Describes how to apply Elligator mathematically
}
The Elligator Map and Inverse Map
=================================
Elligator specifies two kinds of maps,
the “map” (or “direct map” for clarity)
and the “inverse map”.
The map is a function that takes a number <var>r</var> from an
elliptic curve’s finite field (which we call a
“field element”),
and produces a point
<var>P</var> = (<var>u</var>, <var>v</var>)
on that elliptic curve.
Note that the map is not quite injective:
<var>r</var> and −<var>r</var> map to the same point.
Numbers that are neither equal nor opposite do map to different points
though.
The _inverse_ map is a function that takes as input an elliptic curve
point <var>P</var> and outputs a field element <var>r</var>.
We also call that number the “representative” because it
represents a point on the curve.
Note that _only about half_ of the curve can be mapped back.
For any given point <var>P</var> that can be mapped,
applying the inverse map then the direct map will yield the original
point <var>P</var>.
For any representative <var>r</var> in the curve’s finite field,
applying the direct map then the inverse map will yield either the
original representative <var>r</var> or its opposite
−<var>r</var>.
Applicability
-------------
Elligator does not work on all elliptic curves,
and will not properly hide points on all curves where it does work.
The following conditions must hold:
- The finite field the curve is based on must have an odd
characteristic.
That is, it cannot be a binary field.
In practice most curves use large prime fields, which are all odd.
While extension fields and binary fields can sometimes be faster,
prime fields have a more compelling security story.
- The curve is expressible in the form
<var>v</var><sup>2</sup> = <var>u</var><sup>3</sup> + <var>A</var><var>u</var><sup>2</sup> + <var>B</var><var>u</var>,
such that
<var>A</var><var>B</var>(<var>A</var><sup>2</sup> − 4<var>B</var>) ≠ 0.
Note that this includes all Montgomery curves of the form
<var>v</var><sup>2</sup> = <var>u</var><sup>3</sup> + <var>A</var><var>u</var><sup>2</sup> + <var>u</var>
(except
<var>v</var><sup>2</sup> = <var>u</var><sup>3</sup> + <var>u</var>),
including Curve25519 and Curve448.
In practice, almost any curve with an odd field and a point of
order two can be written in this form.
- Additionally,
for Elligator to properly hide points on the curve as random noise,
The characteristic of its field must be very close to a power of two.
This is because we are ultimately transmitting bit strings over the
network,
whose range is always a power of two.
In practice, only Mersenne primes (2<sup><var>k</var></sup> − 1),
pseudo-Mersenne primes (2<sup><var>k</var></sup> − <var>c</var>),
and _some_ Solinas primes
(2<sup><var>k</var></sup> − 2<sup><var>l</var></sup> … − 1
where <var>k</var> − <var>l</var> ideally exceeds 128)
are adequate.
Overall, those conditions cover a wide range of curves,
including the very popular Curve25519 and Curve448.
One notable exception are short Weierstraß curves that
have a prime order and therefore lack a point of order two;
an example of a curve with a prime order is NIST P-256.
<aside>
Those already familiar with Elligator may realise that we are actually
talking about Elligator 2.
That’s because Elligator 1 is less widely applicable,
has no other compelling benefits,
and as a result has not caught on.
It is thus simpler to ignore it.
</aside>
Instantiation Parameters
------------------------
An Elligator instantiation works over a specific curve,
and has a couple parameters of its own.
Before actually defining the maps, we need to fix those parameters.
- The **finite field** GF(<var>q</var>) over which the curve operates.
Note that <var>q</var> is always the power of a prime.
That is, <var>q</var> = <var>p</var><sup><var>m</var></sup>,
for some prime <var>p</var> and some strictly positive integer
<var>m</var>.
Most of the time though,
we will be using a prime field,
where <var>q</var> = <var>p</var>.
Recall that <var>p</var> = 2 is not possible because
the field must have an odd characteristic.
Examples of finite fields include
GF(2<sup>255</sup> − 19),
used by Curve25519,
and
GF(2<sup>448</sup> − 2<sup>224</sup> − 1),
used by Curve448.
- The **elliptic curve**, defined by the equation
<var>v</var><sup>2</sup> = <var>u</var><sup>3</sup> + <var>A</var><var>u</var><sup>2</sup> + <var>B</var><var>u</var>.
Examples of elliptic curves include Curve25519
(<var>A</var> = 486662, <var>B</var> = 1) and
Curve448 (<var>A</var> = 156326, <var>B</var> = 1).
- The **non-square** <var>Z</var> in GF(<var>q</var>).
It can be any number in GF(<var>q</var>) that has no square root.
That is, there is no number <var>n</var> in GF(<var>q</var>) such that
<var>n</var><sup>2</sup> = <var>Z</var>.
We generally chose <var>Z</var> to minimise computations down the
line, like small numbers,
or numbers tailored to speed up specific implementations.
With GF(2<sup>255</sup> − 19),
those would be 2 and √−1 respectively.
With
GF(2<sup>448</sup> − 2<sup>224</sup> − 1),
−1 is best in all cases.
- The **set of non-negative field elements**.
A square <var>s</var> in GF(<var>q</var>) always has two square roots:
√<var>s</var> and −√<var>s</var>.
We need a way to determine which is the positive one for the direct
and inverse maps to be deterministic.
For prime fields GF(<var>p</var>) where
<var>p</var> ≡ 3 (mod 4),
we can pick
√<var>s</var> = <var>s</var><sup>(<var>p</var>+1)/4</sup>,
which is the unique square root that is also a square
(the _principal square root_).
For other fields,
we chose the set of non-negative field elements somewhat arbitrarily.
Common choices are the set
{0, 1, … (<var>q</var>−1)/2}
or the set of even numbers.
<aside>
For the implementation of square roots and checking whether a number has
a square root in GF(<var>q</var>),
refer to [I-D.draft-irtf-cfrg-hash-to-curve-16, appendix I](https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-16#appendix-I).
</aside>
The direct map
--------------
First, we need to define the `legendre()` function;
it computes the [Legendre symbol](https://en.wikipedia.org/wiki/Legendre_symbol)
of a field element <var>f</var>:
- `legendre`(<var>f</var>) = 0 if <var>f</var> is zero.
- `legendre`(<var>f</var>) = 1 if <var>f</var>
is a non-zero square.
- `legendre`(<var>f</var>) = −1 if <var>f</var> is not a
square.
This can be constructed using the square root checking functions needed
to find the chosen non-square <var>Z</var> above.
In a prime fields GF(<var>p</var>),
it can be defined as:
`legendre`(<var>f</var>) = <var>f</var><sup>(<var>p</var> − 1) / 2</sup>.
The map itself takes any non-zero field element <var>r</var> (the
representative),
and outputs a point
<var>P</var> = (<var>u</var>, <var>v</var>) on the curve
as follows:
- <var>w</var> = −<var>A</var> / (1 + <var>Z</var> <var>r</var><sup>2</sup>)
- <var>e</var> = `legendre`(<var>w</var><sup>3</sup> + <var>A</var> <var>w</var><sup>2</sup> + <var>B</var> <var>w</var>)
- <var>u</var> = <var>e</var> <var>w</var> − (1 − <var>e</var>) (<var>A</var> / 2)
- <var>v</var> = −<var>e</var> √(<var>u</var><sup>3</sup> + <var>A</var> <var>u</var><sup>2</sup> + <var>B</var> <var>u</var>)
- <var>P</var> = (<var>u</var>, <var>v</var>)
Zero is a special case,
which maps to the point (0, 0).
<aside>
The general case for zero gives us
<var>w</var> = −<var>A</var> and
<var>e</var> = `legendre`(<var>A</var><var>B</var>).
When <var>B</var> = 0 (all Montgomery curves) and
−<var>A</var> is not a square (Curve25519, Curve448),
this this means that <var>e</var> = −1 and
(<var>u</var>, <var>v</var>) = (0, 0).
As a consequence Curve25519 and Curve448 do not have to treat zero as a
special case.
</aside>
The inverse map
---------------
Unlike the direct map,
the inverse map does _not_ work for all points on the curve.
It only holds for points
<var>P</var> = (<var>u</var>, <var>v</var>) such that:
- <var>u</var> ≠ −A;
- −<var>Z</var><var>u</var>(<var>u</var> + <var>A</var>)
is a square;
- if <var>v</var> = 0,
then <var>u</var> = 0 as well.
Assuming those conditions hold, the representative <var>r</var> of
<var>P</var> = (<var>u</var>, <var>v</var>) is computed
as follows:
- <var>r</var> = √(−<var>u</var> / (<var>Z</var> (<var>u</var> + <var>A</var>)))
if <var>v</var> is non-negative,
- <var>r</var> = √(−(<var>u</var> + <var>A</var>) / (<var>Z</var> <var>u</var>))
if <var>v</var> is strictly negative.
Note:
if <var>P</var> = (0, 0) then
<var>r</var> = √(−0 / (<var>Z</var> (0 + <var>A</var>))) = 0.