eddsa: add support for point precomputation#262
Merged
tomato42 merged 1 commit intotlsfuzzer:masterfrom Oct 26, 2021
Merged
Conversation
tomato42
force-pushed
the
edwards-precompute
branch
from
cefa2ef to
43bb453
Compare
t184256
reviewed
Aug 18, 2021
Contributor
t184256
left a comment
t184256
left a comment
There was a problem hiding this comment.
Not a fan of some details, though you're unlikely to find them blocking either.
Comment on lines
+1342
to
+1367
| order = self.__order | ||
| assert order | ||
| precompute = [] | ||
| i = 1 | ||
| order *= 2 | ||
| coord_x, coord_y, coord_z, coord_t = self.__coords | ||
| prime = self.__curve.p() | ||
| doubler = PointEdwards( | ||
| self.__curve, coord_x, coord_y, coord_z, coord_t, order | ||
| ) | ||
| order *= 2 | ||
| coord_x, coord_y = doubler.x(), doubler.y() | ||
| coord_t = coord_x * coord_y % prime | ||
| precompute.append((coord_x, coord_y, coord_t)) | ||
|
|
||
| while i < order: | ||
| i *= 2 | ||
| doubler = doubler.double().scale() | ||
| coord_x, coord_y = doubler.x(), doubler.y() | ||
| coord_t = coord_x * coord_y % prime | ||
| precompute.append((coord_x, coord_y, coord_t)) | ||
|
|
||
| self.__precompute = precompute |
Contributor
There was a problem hiding this comment.
Here are two attempts to restructure the do-while awkwardness, with control flow
assert self.__order
precompute = []
prime = self.__curve.p()
doubler = PointEdwards(self.__curve, *self.__coords, self.__order * 2)
i = 1
while True:
doubler.scale()
coord_x, coord_y = doubler.x(), doubler.y()
coord_t = coord_x * coord_y % prime
precompute.append((coord_x, coord_y, coord_t))
if i >= self.__order * 4:
break
i *= 2
doubler = doubler.double()
self.__precompute = precompute
# assert self.__order * 8 < 2**len(precompute) < self.__order * 16and with extracting scale-yield-double to a separate generator
def double_gen(p):
while True:
yield p.scale()
p = p.double()
assert self.__order
prime = self.__curve.p()
p1 = PointEdwards(self.__curve, *self.__coords, self.__order * 2)
import itertools
self.__precompute = list(itertools.islice(
((p.x(), p.y(), p.x() * p.y() % prime) for p in double_gen(p1)),
bit_length(self.__order) + 3
))
# assert self.__order * 8 < 2**len(self.__precompute) < self.__order * 16
Member
Author
There was a problem hiding this comment.
yes, *self.__coords is nice syntactic sugar, unfortunately doesn't work on python2, but yeah, could be rewritten
tomato42
force-pushed
the
edwards-precompute
branch
from
43bb453 to
e48d851
Compare
tomato42
force-pushed
the
edwards-precompute
branch
from
e48d851 to
67b1688
Compare
t184256
approved these changes
Oct 25, 2021
Contributor
t184256
left a comment
t184256
left a comment
There was a problem hiding this comment.
r+ from me, I don't have any more good input
Member
Author
|
@t184256 thanks for the review! |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Significantly speed up all EdDSA operations by computing multiplication table of the generator point