Ristretto compression process with a different basepoint.

[CPerezz]

Due to some issues I've had implementing Ristretto for another curve, I came to the repo to reproduce the behavior that I was experiencing and check it against this implementation by looking and playing with the ristretto.rs implementation.

How to reproduce the issue:

If I'm not wrong, as it is mentioned on the Decaf paper, and for Ristretto also, for a point, to be a valid Ristretto representation, "inside the 4coset where it lives" it has to be the only point that satisfies:

xy is non-negative, y is non-negative and x is non-zero. It also has to be a point that really exists on the curve so it satisfies the TwEds equation.

So, following this, I generated a point in the curve from a random x-coordinate by doing:

sage: l = 2^255 - 19
sage: d = -121665*inverse_mod(121666,l) %l
sage: y = 23
sage: y_sq = 23^2
sage: num = (1 - y_sq) % l 
sage: den = ((-1 + (d * y_sq)) %l)
sage: (num * inverse_mod(den, l)) % l
55215569697847802580944521799634926744318876158473612612445508315832021807620
sage: legendre_symbol(55215569697847802580944521799634926744318876158473612612445508315832021807620, l)
1

After performing the mod_sqrt, I multiplied the point by 8, doing:

#[test]
    fn test_basepoint() {
        let point = EdwardsPoint {
            X: FieldElement51([881010941142167, 1648694857529964, 470497918313193, 1327361769579760, 108032109768103]),
            Y: FieldElement51([23, 0, 0, 0, 0]),
            Z: FieldElement51::one(),
            T: FieldElement51([2248853136787876, 1891184704225212, 1814252866462463, 1255923122426260, 232938710981134])
        };

        println!("{:?}", point * Scalar::from(8u8)); // Same as using mul_by_cofactor(), I didn't remember to use the function at that moment. 
        let rp = RistrettoPoint(point);
        println!("{:?}", rp);

The result of the first print wasn't the identity, so it is a basepoint.
On the same test, I declared the resulting point as a RistrettoPoint and printed it since the Debug implementation prints the 4-coset related to the point.

From the 4 resulting points, I picked the one that satisfies the requirements mentioned above:

EdwardsPoint{
            X: FieldElement51([1756888093834848, 906380849653581, 1682251382230390, 1123942104594140, 1633797476279613]),
            Y: FieldElement51([1048006478132596, 1809720267245864, 892987767224016, 1812612240710576, 1078332328750236]),
            Z: FieldElement51([2251799813685233, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247]),
            T: FieldElement51([11786707589469, 1442460437840140, 1750187788891136, 1731706951350700, 1320044969760709])
        }

So at this point, we have a Twisted Edwards point, that is a basepoint since it has order L and is the valid RistrettoPoint representation inside of it's 4-coset since it satisfies the requirements mentioned above.

Issue

The issue appears when I execute:

#[test]
    fn de_compress_ristretto_basepoint() {
        let a = RistrettoPoint(EdwardsPoint{
            X: FieldElement51([1756888093834848, 906380849653581, 1682251382230390, 1123942104594140, 1633797476279613]),
            Y: FieldElement51([1048006478132596, 1809720267245864, 892987767224016, 1812612240710576, 1078332328750236]),
            Z: FieldElement51([2251799813685233, 2251799813685247, 2251799813685247, 2251799813685247, 2251799813685247]),
            T: FieldElement51([11786707589469, 1442460437840140, 1750187788891136, 1731706951350700, 1320044969760709])
        });
        let ac = a.compress();
        println!("{:?}", ac);
        let bcd = ac.decompress().unwrap();
        println!("{:?}", bcd);

        assert!(bcd == a);
    }

I added a println! statement just before the third compression step is executed (the inv_sqrt) that prints also the Choice that the operation returns. So it looks like:

//code...
let u1 = &(Z + &Y) * &(Z - &Y);
        let u2 = &X * &Y;
        println!("{:?}", (&u1 * &u2.square()).invsqrt());
        // Ignore return value since this is always square
        let (_, invsqrt) = (&u1 * &u2.square()).invsqrt();
// more code...

This are the outputs:

(Choice(0), FieldElement51([1018880721970498, 1040618323875924, 103342261851949, 1162127339646060, 770807009422663]))
CompressedRistretto: [252, 54, 194, 109, 205, 36, 66, 205, 229, 60, 191, 78, 74, 40, 34, 27, 161, 89, 1, 105, 10, 130, 160, 238, 107, 241, 10, 95, 244, 98, 175, 81]

So, it differs from the comment :

curve25519-dalek/src/ristretto.rs

Line 442 in cf03d39

// Ignore return value since this is always square

since we see that the result of the inv_sqrt() is not QR.

When the decompress() function is called, it returns a None and debugging the possible Choice results that can make the function fail I got:

Is the encode canonical? Choice(1)
s is neg?? 0

Is QR? 0    t is neg?? 1

Is this the expected behavior? Since it seems not due to the comments on the code and the statements that appear on:

• https://ristretto.group/formulas/encoding.html
• https://www.shiftleft.org/papers/decaf/decaf.pdf

I'm sorry if any assumption has been done incorrectly from my side or there's any conceptual error.

[3for]

I'm afraid the point you selected is not of order L? I've tested it and the assertion failed:

       let B = &EdwardsPoint {
            X: FieldElement51([881010941142167, 1648694857529964, 470497918313193, 1327361769579760, 108032109768103]),
            Y: FieldElement51([23, 0, 0, 0, 0]),
            Z: FieldElement51::one(),
            T: FieldElement51([2248853136787876, 1891184704225212, 1814252866462463, 1255923122426260, 232938710981134])
        };
        let should_be_id = B * &constants::BASEPOINT_ORDER;
        assert!(should_be_id.is_identity()); //Assertion failed here.

[CPerezz]

Hmmm.

It's right, the assertion shouldn't fail if it has order L. But I just tried this:

#[test]
    fn test_basepoint() {
        let point = EdwardsPoint {
            X: FieldElement51([881010941142167, 1648694857529964, 470497918313193, 1327361769579760, 108032109768103]),
            Y: FieldElement51([23, 0, 0, 0, 0]),
            Z: FieldElement51::one(),
            T: FieldElement51([2248853136787876, 1891184704225212, 1814252866462463, 1255923122426260, 232938710981134])
        };

        for i in 2..9 {
            let prod = &point * Scalar::from(i as u8);
            println!("{:?}", prod);
            assert!(prod != point);
            assert!(prod != EdwardsPoint::identity());
        };
    }

And it gave:

EdwardsPoint{
        X: FieldElement51([2152709433700862, 787155387387536, 250946600707227, 1470587149806751, 895489635055459]),
        Y: FieldElement51([961769779245714, 433349089872565, 575949965381556, 1310192225334422, 1575935055707276]),
        Z: FieldElement51([915998316997126, 336913110701451, 1343263620694248, 956837101456645, 2205050022615226]),
        T: FieldElement51([1892167310855571, 480631477984419, 1267872046560364, 124701787610033, 774821103260559])
}
EdwardsPoint{
        X: FieldElement51([404869813198543, 1491254651008611, 418008587326969, 133139870363596, 1305390955700225]),
        Y: FieldElement51([1427313885616576, 537191807754612, 1578668142731512, 1947935944094378, 1268852237660661]),
        Z: FieldElement51([2040728201848343, 392764441789775, 1608391131286780, 1762711276407932, 136477068064088]),
        T: FieldElement51([941734027117810, 671327388371284, 2099694974469118, 234469470682163, 1934831910681094])
}
EdwardsPoint{
        X: FieldElement51([1896035297497097, 1743689470791360, 988456596616466, 1285807289616174, 2015900744539391]),
        Y: FieldElement51([1481920216740675, 2154676273224399, 1509163695480085, 1213947287641258, 2074240132205130]),
        Z: FieldElement51([1855659908170929, 2123428861706343, 1197267677866277, 2155914088827479, 1658798892482794]),
        T: FieldElement51([1326775144488937, 1486779794314489, 860639310097851, 841396527101285, 667699861339669])
}
EdwardsPoint{
        X: FieldElement51([1110029952049657, 19969579232259, 984422659309499, 2047213867387800, 1962279606375864]),
        Y: FieldElement51([2240981728810622, 933580972968833, 755548968026578, 342220754267201, 2181344316306528]),
        Z: FieldElement51([206615459658714, 1207448359626836, 808376986808578, 666026825211383, 1780074006366576]),
        T: FieldElement51([2205120838439766, 1566833817953906, 263191271293934, 180813146290624, 1226508393471145])
}
EdwardsPoint{
        X: FieldElement51([1153968438678275, 254674371772579, 2016325181518160, 801449942972012, 9125175935066]),
        Y: FieldElement51([1987214753527066, 328520007810167, 1618871123700517, 320661106480792, 834999454539154]),
        Z: FieldElement51([1194172371942159, 1648347752117148, 3393107786346, 1693952092363892, 992926284591399]),
        T: FieldElement51([1541125073843858, 407990198633445, 756193587993344, 546007641940339, 1695201718954464])
}
EdwardsPoint{
        X: FieldElement51([1600434450430348, 1004825595102601, 1804504955252825, 1127816418964145, 1989425368752568]),
        Y: FieldElement51([2022569847951572, 1521473367453485, 1495794221231788, 112531152171504, 333482115048988]),
        Z: FieldElement51([2050626403807188, 936474195227100, 1303719201009426, 2034043474735693, 1231032037223398]),
        T: FieldElement51([1775875172671156, 1740966589757778, 1485687851361387, 1750270822750640, 1419954961292896])
}
EdwardsPoint{
        X: FieldElement51([902528018681584, 973688110499528, 1567648399543900, 216900523692753, 1037033738221762]),
        Y: FieldElement51([2176263945733873, 2001721889710795, 458627600718992, 453839575512736, 211960333421035]),
        Z: FieldElement51([363634961663146, 1457366270738878, 2223076046576883, 2145452785916722, 556743245786847]),
        T: FieldElement51([687743818003226, 255784778175023, 1918647329948927, 1495928598800383, 786557996093163])
}
test ristretto::test::test_basepoint ... ok

Identity isn't printed anywhere, and the assertions didn't fail.

So as far as I understand, this discards the point of having order: 2, 4, 8, 2L, 4L or 8L right?

If I'm missing something, excuse me I'm not a cryptographer or anything similar ahaha.

[hdevalence]

Hi all, I'm going to be on vacation until the middle of next week but I can check into this when I get back.

[3for]

@hdevalence Have a nice vocation!

I use the transformation above and translate the edwards point (u,v)=(777614515006863064380223997674220849595901915306045448346376123656982013079,23) to the corresponding montgomery point (x,y)=(31579660701086235115519359547823974869073632181538335647124795638521762629062, 9132590012203147150454691378506969525775439784381435392762152234963404418091):

sage: v=23
sage: u= 881010941142167+1648694857529964*2^51+470497918313193*2^102+13273617695
....: 79760*2^153+108032109768103*2^204
sage: u==27776145150068630643802239976742208495959019153060454483463761236569820
....: 13079
True
sage: l=2^255-19
sage: mod((1+v)/(1-v),l)
31579660701086235115519359547823974869073632181538335647124795638521762629062
sage: x=mod((1+v)/(1-v),l)
sage: y=mod(sqrt(x^3+486662*x^2+x),l)
sage: y
9132590012203147150454691378506969525775439784381435392762152234963404418091
sage: x
31579660701086235115519359547823974869073632181538335647124795638521762629062

sage: E= EllipticCurve(GF(2^255-19) ,[ 0,486662,0,1,0]);
sage: E
Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949
sage: P=E(x,y) //(x,y) point
sage: P
(31579660701086235115519359547823974869073632181538335647124795638521762629062 : 9132590012203147150454691378506969525775439784381435392762152234963404418091 : 1)
sage: P.order()
57896044618658097711785492504343953926856930875039260848015607506283634007912
sage: E.cardinality()
57896044618658097711785492504343953926856930875039260848015607506283634007912
sage: factor(E.cardinality())
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989
sage: P.order()==E.cardinality()
True
sage: Q=E(x,l-y) //(x,-y) point
sage: Q.order()==E.cardinality()
True
sage: P*P.order()
(0 : 1 : 0)
sage: Q*Q.order()
(0 : 1 : 0)

By translating the point @CPerezz selected to montgomery format, and use the sage script above, it seemed that the point do have the right order and can be act as a basepoint.

And I retest it with magma script ( just paste it in http://magma.maths.usyd.edu.au/calc/ ), the same results hold.

clear;
E := EllipticCurve([GF(2^255-19) | 0,486662,0,1,0]);
Order(E);
FactoredOrder(E);
P:=E![31579660701086235115519359547823974869073632181538335647124795638521762629062,9132590012203147150454691378506969525775439784381435392762152234963404418091,1];
FactoredOrder(P);
IsOrder(P, Order(E));
Order(E)*P;
Q:=E![31579660701086235115519359547823974869073632181538335647124795638521762629062,48763454606454950561330801125836984400859552548438846626966639768993160401858,1];
FactoredOrder(Q);
IsOrder(Q, Order(E));

magma result:

57896044618658097711785492504343953926856930875039260848015607506283634007912
[ <2, 3>, <72370055773322622139731865630429942408571163593799076060019509382854\
54250989, 1> ]
[ <7237005577332262213973186563042994240857116359379907606001950938285454250989\
, 1>, <2, 3> ]
true
(0 : 1 : 0)
[ <7237005577332262213973186563042994240857116359379907606001950938285454250989\
, 1>, <2, 3> ]
true

Anything wrong?

[3for]

Oh, I confused myselft. The point @CPerezz selected is of order 8L instead of L。

        let B = &EdwardsPoint {
            X: FieldElement51([881010941142167, 1648694857529964, 470497918313193, 1327361769579760, 108032109768103]),
            Y: FieldElement51([23, 0, 0, 0, 0]),
            Z: FieldElement51::one(),
            T: FieldElement51([2248853136787876, 1891184704225212, 1814252866462463, 1255923122426260, 232938710981134])
        };
        let should_be_id = B * &constants::BASEPOINT_ORDER;
        let b_id = should_be_id.mul_by_pow_2(3);
        assert!(b_id.is_identity()); //Assertion SUCCEED.

[CPerezz]

@3for is right.

Sorry for the confusion.
Then the decompression failure is due to the point order? Something like the 8L order points are "carried to 0" due to the Kernel of the isogeny that transports the point from the Ristretto domain to the starting curve one?

I close the issue btw, thanks for the quick responses @3for @hdevalence :)