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
|
"""
This module provides a `Point` class and a special `InfinityPoint` class for the point at infinity.
"""
from copy import copy
from typing import Mapping, TYPE_CHECKING
from public import public
from .context import ResultAction
from .coordinates import AffineCoordinateModel, CoordinateModel, EFDCoordinateModel
from .mod import Mod, Undefined
from .op import CodeOp
if TYPE_CHECKING:
from .curve import EllipticCurve
@public
class CoordinateMappingAction(ResultAction):
"""A mapping of a point from one coordinate system to another one, usually one is an affine one."""
model_from: CoordinateModel
model_to: CoordinateModel
point: "Point"
def __init__(self, model_from: CoordinateModel, model_to: CoordinateModel, point: "Point"):
super().__init__()
self.model_from = model_from
self.model_to = model_to
self.point = point
def __repr__(self):
return f"{self.__class__.__name__}(from={self.model_from}, to={self.model_to}, {self.point})"
@public
class Point(object):
"""A point with coordinates in a coordinate model."""
coordinate_model: CoordinateModel
coords: Mapping[str, Mod]
field: int
def __init__(self, model: CoordinateModel, **coords: Mod):
if not set(model.variables) == set(coords.keys()):
raise ValueError
self.coordinate_model = model
self.coords = coords
field = None
for value in self.coords.values():
if field is None:
field = value.n
else:
if field != value.n:
raise ValueError(f"Mismatched coordinate field of definition, {field} vs {value.n}.")
self.field = field if field is not None else 0
def __getattribute__(self, name):
# Do the magic such that point.X1 works!
if "coords" in super().__getattribute__("__dict__"):
coords = super().__getattribute__("coords")
if name in coords:
return coords[name]
return super().__getattribute__(name)
def to_affine(self) -> "Point":
"""Convert this point into the affine coordinate model, if possible."""
affine_model = AffineCoordinateModel(self.coordinate_model.curve_model)
with CoordinateMappingAction(self.coordinate_model, affine_model, self) as action:
if isinstance(self.coordinate_model, AffineCoordinateModel):
return action.exit(copy(self))
ops = []
for s in self.coordinate_model.satisfying:
try:
ops.append(CodeOp(s))
except Exception:
pass
result_variables = set(map(lambda x: x.result, ops))
if not result_variables.issuperset(affine_model.variables):
raise NotImplementedError
result = {}
locls = {**self.coords}
for op in ops:
try:
locls[op.result] = op(**locls)
except NameError as e:
if op.result in affine_model.variables:
raise e
else:
continue
if op.result in affine_model.variables:
result[op.result] = locls[op.result]
return action.exit(Point(affine_model, **result))
def to_model(self, coordinate_model: CoordinateModel, curve: "EllipticCurve") -> "Point":
"""Convert an affine point into a given coordinate model, if possible."""
if not isinstance(self.coordinate_model, AffineCoordinateModel):
raise ValueError
with CoordinateMappingAction(self.coordinate_model, coordinate_model, self) as action:
ops = []
for s in coordinate_model.satisfying:
try:
ops.append(CodeOp(s))
except Exception:
pass
locls = {**self.coords, **curve.parameters, "Z": Mod(1, curve.prime)}
for op in ops:
try:
locls[op.result] = op(**locls)
except Exception:
continue
result = {}
for var in coordinate_model.variables:
if var in locls: # Try this first.
result[var] = locls[var]
elif var == "X":
result[var] = self.coords["x"]
if isinstance(coordinate_model, EFDCoordinateModel) and coordinate_model.name == "inverted":
result[var] = result[var].inverse()
elif var == "Y":
result[var] = self.coords["y"]
if isinstance(coordinate_model, EFDCoordinateModel):
if coordinate_model.name == "inverted":
result[var] = result[var].inverse()
elif coordinate_model.name == "yz":
result[var] = result[var] * curve.parameters["r"]
elif coordinate_model.name == "yzsquared":
result[var] = result[var]**2 * curve.parameters["r"]
elif var.startswith("Z"):
result[var] = Mod(1, curve.prime)
elif var == "T":
result[var] = Mod(int(self.coords["x"] * self.coords["y"]), curve.prime)
else:
raise NotImplementedError
return action.exit(Point(coordinate_model, **result))
def equals_affine(self, other: "Point") -> bool:
"""Test whether this point is equal to `other` irrespective of the coordinate model (in the affine sense)."""
if not isinstance(other, Point) or isinstance(other, InfinityPoint):
return False
if self.coordinate_model.curve_model != other.coordinate_model.curve_model:
return False
return self.to_affine() == other.to_affine()
def equals_scaled(self, other: "Point") -> bool:
"""
Test whether this point is equal to `other` using the "z" scaling formula,
which maps the projective class to a single representative.
:param other: The point to compare
:raises ValueError: If the "z" formula is not available for the coordinate system.
:return: Whether the points are equal.
"""
if not isinstance(other, Point) or isinstance(other, InfinityPoint):
return False
if self.coordinate_model.curve_model != other.coordinate_model.curve_model:
return False
if "z" in self.coordinate_model.formulas:
formula = self.coordinate_model.formulas["z"]
self_mapped = formula(self.field, self)
other_mapped = formula(self.field, other)
return self_mapped == other_mapped
else:
raise ValueError("No scaling formula available.")
def equals(self, other: "Point") -> bool:
"""Test whether this point is equal to `other` irrespective of the coordinate model (in the affine sense)."""
return self.equals_affine(other)
def __bytes__(self):
res = b"\x04"
for k in sorted(self.coords.keys()):
res += bytes(self.coords[k])
return res
def __eq__(self, other):
if not isinstance(other, Point):
return False
if self.coordinate_model != other.coordinate_model:
return False
return self.coords == other.coords
def __hash__(self):
return hash((tuple(self.coords.keys()), tuple(self.coords.values()))) + 1
def __str__(self):
args = ", ".join([f"{key}={val}" for key, val in self.coords.items()])
return f"[{args}]"
def __repr__(self):
return f"Point([{str(self)}] in {self.coordinate_model})"
@public
class InfinityPoint(Point):
"""A point at infinity."""
def __init__(self, model: CoordinateModel):
coords = {key: Undefined() for key in model.variables}
super().__init__(model, **coords)
def to_affine(self) -> "InfinityPoint":
return InfinityPoint(AffineCoordinateModel(self.coordinate_model.curve_model))
def to_model(self, coordinate_model: CoordinateModel, curve: "EllipticCurve") -> "InfinityPoint":
return InfinityPoint(coordinate_model)
def equals_affine(self, other: "Point") -> bool:
return self == other
def equals_scaled(self, other: "Point") -> bool:
return self == other
def equals(self, other: "Point") -> bool:
return self == other
def __bytes__(self):
return b"\x00"
def __eq__(self, other):
if type(other) is not InfinityPoint:
return False
else:
return self.coordinate_model == other.coordinate_model
def __str__(self):
return "Infinity"
def __repr__(self):
return f"InfinityPoint({self.coordinate_model})"
|
