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
|
#!/usr/bin/env python3
from argparse import ArgumentParser, RawTextHelpFormatter
import re
import sage.all
from sage.schemes.elliptic_curves.constructor import EllipticCurve
from pegasis import PEGASIS
from sage.rings.integer import Integer
description = """
Verifies the outptus of the action against previously collected values.
This is useful to verify that the values computed by pegasis are consistent during development.
"""
parser = ArgumentParser(prog="test_consistency.py", description=description, formatter_class=RawTextHelpFormatter)
parser.add_argument(
"--loglevel",
default="INFO",
help="Set loglevel to one of 'DEBUG', 'INFO' (default), 'WARNING', 'ERROR', 'CRITICAL'",
choices=("DEBUG", "INFO", "WARNING", "ERROR", "CRITICAL"),
)
parser.add_argument(
"--verify",
default=False,
metavar="file",
help="Select file containing test vectors",
)
parser.add_argument(
"--generate",
type=int,
default=0,
metavar="N",
help="Generate N test vectors",
)
parser.add_argument(
"--save",
default=False,
metavar="file",
help="Select file to save test vectors to",
)
parser.add_argument("-p", type=int, help="Prime size", choices=(500, 1000, 1500, 2000, 4000), default=500)
args = parser.parse_args()
EGA = PEGASIS(args.p)
def montgomery(A):
return EllipticCurve(EGA.Fp, [0, A, 0, 1, 0])
def generate(nvectors):
E = EGA.E_start
vectors = ["# Created with `consistency.py`. Verify with `consistency.py --verify <path to file>`"]
for _ in range(nvectors):
ideal = EGA.sample_ideal()
F = EGA.action(E, ideal)
# Unfortunately sage does not provide an easily parseable __repr__ class for ideals
# The following diy serialisation is a little bit brittle
#
# - .gens_two() will return two generators as elements of the underlying order
# - This order is defined inside the number field Q(sqrt(-p))
# - More precisely, this is defined in pegasis as
# self.K = NumberField(name="pi", polynomial = var('x')**2 + self.p)
# - Elements of K are a list [a, b] representing the element a + pi*b
# - We print a and b into the test_vectors file
vector = []
vector += [f"({x}, {y})" for (x, y) in [list(g) for g in ideal.gens_two()]]
vector += [f"{E.a2()}"]
vector += [f"{F.a2()}"]
vectors += [" ".join(vector)]
E = F
print(f"[{_+1}/{nvectors}] Generated vector")
return vectors
def verify(vectors):
nvectors = len(vectors)
success = 0
for nvector, vector in enumerate(vectors):
# re.match('([0-9]*)')
# python's re does not support repeating capture groups, must repeat manually
pattern = "^"
# First ideal generator (two coordinates)
pattern = r"^\(([-0-9]*),\s*([-0-9]*)\)"
# Second ideal generator (two coordinates)
pattern += r"\s*\(([-0-9]*),\s*([-0-9]*)\)"
# Starting Montgomery coefficient
pattern += r"\s*([-0-9]*)"
# Ending Montgomery coefficient
pattern += r"\s*([-0-9]*)"
pattern += "$"
matches = re.match(pattern, vector)
if matches is None:
print("Parsing error of test vector")
print(vector)
continue
# - Coefficients g11, g12 of the first generator of the ideal
# - Coefficients g21, g22 of the second generator of the ideal
# - A Montgomery coefficient of the starting curve
# - B Montgomery coefficient of the ending curve
g11, g12, g21, g22, A, B = matches.groups()
pi = EGA.order.gens()[1]
g1 = Integer(g11) + Integer(g12) * pi
g2 = Integer(g21) + Integer(g22) * pi
ideal = EGA.order * g1 + EGA.order * g2
A = EGA.Fp(A)
B = EGA.Fp(B)
E = montgomery(A)
F = EGA.action(E, ideal)
if F.a2() == B:
success += 1
print(f"{nvector+1}/{nvectors} (Succes rate: {success/(nvector+1)*100:.2f}) Success!")
else:
print(f"{nvector+1}/{nvectors} Failure!")
if args.generate and args.verify:
print("--generate and --verify are mutually exclusive")
exit(1)
if args.generate:
print("Generating test vectors")
if args.save:
print(f"Will save vectors to file '{args.save}'")
# Test that we can actually write before generating vectors
with open(args.save, "w") as file:
pass
else:
print("Will print test vectors to stdout redirect to file or copy-paste manually")
vectors = generate(args.generate)
if args.save:
with open(args.save, "w") as file:
vectors = [vector + "\n" for vector in vectors]
file.writelines(vectors)
else:
for vector in vectors:
print(vector)
if args.verify:
with open(args.verify, "r") as vectors_file:
vectors = vectors_file.readlines()
# Ignore comment lines
vectors = [vector for vector in vectors if not vector[0] == "#"]
verify(vectors)
|
