Closed CPerezz closed 5 years ago
@Bounce23 provided the values: a = -1
, d = -86649
related to the isomorphic twist solution.
As far as we've seen, with the implementation of sqrt_ratio_i
and the refactor of inv_sqrt
functions done on 9c00824 and 73ee720 and the refactor done then of compression/decompression functions done in 2f395a71, allowed us to pass:
bad_encoding_test
, see: https://ristretto.group/test_vectors/ristretto255.htmlidentity_point_encoding/decoding
.We are still unable to pass the good_encoding_tests
since the RISTRETTO_BASEPOINT_COMPRESSED
variable cannot be decompressed (which might mean that we need to find our own Basepoint).
@Bounce23 found the following parameters for an isomorphic twist that should work:
sage: d = 86649
sage: a = -1
sage: b = d/a
sage: b = 4*b
sage: c = 2-b
sage: c
346598
This ones, will provide the same Sub-group order, and also satisfy:
b
between the 3 curve types (Tw Edwards, Montgomery, Jacobian).We are still able to use a basepoint encoding for our curve, to fit with the ristretto scalar field. This is the one shown here:
sage: def findBasepoint(prime, A):
....: F = GF(prime)
....: E = EllipticCurve(F, [0, A, 0, 1, 0])
....:
....: for uInt in range(1, 1e3):
....: u = F(uInt)
....: v2 = u^3 + A*u^2 + u
....: if not v2.is_square():
....: continue
....: v = v2.sqrt()
....: point = E(u, v)
....: pointOrder = point.order()
....: if pointOrder > 8 and pointOrder.is_prime():
....: Q=u^3 + A*u^2 + u
....: return u, Q, sqrt(Q), point
....:
sage: res = findBasepoint(x, 346598)
sage: res
(17,
100171752,
1014685013428497365422144808165958100622560545891891747637198454693655077041,
(17 : 1014685013428497365422144808165958100622560545891891747637198454693655077041 : 1))
The difference is that we make use of an Edwards Y, without the need to specify the 'unique' basepoint stemming from (u-1)/(u+1), as this is for thee 25519 Montgomery fast scalar multiplication. Whereas ours is Edwards points encoded as field elements. The chosen Y value for a base point passes all the tests.
Furthering the above comment: the base point for twisted Edwards, Y = 100171752, is not chosen arbitrarily; and is in line with the safe curves criteria as shown here, which is found in the code at line 422 here. This is set such that the curve maintains rigidity and to allow y(P) as a ladder coordinate.
This is closed since we take part of this on #82
Since the curve that Sean provided in:
Provides values for the Twisted Edwards form that aren't suitable for a Ristretto protocol implementation we have two options:
Find an isomorphic twist that allows us to mantain the same orders for the Finite Field and also the Sub group, and at the same time, gives
a & d
values that are suitable for a Ristretto implementation.Choice a diferent curve. This will force us to:
It seems that @Bounce23 found an isomorphic twist that can do the job. We will update here the discussions.