1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the alphavm library.
  3  
  4  // Licensed under the Apache License, Version 2.0 (the "License");
  5  // you may not use this file except in compliance with the License.
  6  // You may obtain a copy of the License at:
  7  
  8  // http://www.apache.org/licenses/LICENSE-2.0
  9  
 10  // Unless required by applicable law or agreed to in writing, software
 11  // distributed under the License is distributed on an "AS IS" BASIS,
 12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 13  // See the License for the specific language governing permissions and
 14  // limitations under the License.
 15  
 16  use super::*;
 17  
 18  impl<E: Environment> Elligator2<E> {
 19      /// Returns the encoded affine group element and sign, given a field element.
 20      pub fn encode(input: &Field<E>) -> Result<(Group<E>, bool)> {
 21          // Compute the encoding of the input field element.
 22          let (encoding, sign_high) = Self::encode_without_cofactor_clear(input)?;
 23  
 24          // Cofactor clear the twisted Edwards element (x, y).
 25          let group = encoding.mul_by_cofactor().to_affine();
 26          ensure!(group.is_on_curve(), "Elligator2 failed: element is not on curve");
 27          ensure!(group.is_in_correct_subgroup_assuming_on_curve(), "Elligator2 failed: element in incorrect subgroup");
 28  
 29          Ok((Group::new(group), sign_high))
 30      }
 31  
 32      /// Returns the encoded affine group element and sign, given a field element.
 33      pub(crate) fn encode_without_cofactor_clear(input: &Field<E>) -> Result<(Group<E>, bool)> {
 34          ensure!(
 35              Group::<E>::EDWARDS_D.legendre().is_qnr(),
 36              "D on the twisted Edwards curve must be a quadratic nonresidue"
 37          );
 38          ensure!(!input.is_zero(), "Inputs to Elligator2 must be nonzero (inverses will fail)");
 39  
 40          let one = Field::<E>::one();
 41  
 42          // Store the sign of the input, to be returned with the output.
 43          let sign_high = input > &input.neg();
 44  
 45          // Compute the mapping from Fq to E(Fq) as a Montgomery element (u, v).
 46          let (u, v) = {
 47              // Compute the coefficients for the Weierstrass form: y^2 == x^3 + A * x^2 + B * x.
 48              let (a, b) = match Group::<E>::MONTGOMERY_B.inverse() {
 49                  Ok(b_inverse) => (Group::MONTGOMERY_A * b_inverse, b_inverse.square()),
 50                  Err(_) => bail!("Montgomery B must be invertible in order to use Elligator2"),
 51              };
 52  
 53              // Let (u, r) = (D, input).
 54              let (u, r) = (Group::EDWARDS_D, input);
 55  
 56              // Let ur2 = u * r^2;
 57              let ur2 = u * r.square();
 58  
 59              // Ensure A^2 * ur^2 != B(1 + ur^2)^2.
 60              ensure!(a.square() * ur2 != b * (one + ur2).square(), "Elligator2 failed: A^2 * ur^2 == B(1 + ur^2)^2");
 61  
 62              // Let v = -A / (1 + ur^2).
 63              let v = -a * (one + ur2).inverse().map_err(|_| anyhow!("Elligator2 failed: (1 + ur^2) == 0"))?;
 64  
 65              // Ensure v is nonzero.
 66              ensure!(!v.is_zero(), "Elligator2 failed: v == 0");
 67  
 68              // Let e = legendre(v^3 + Av^2 + Bv).
 69              let v2 = v.square();
 70              let e = ((v2 * v) + (a * v2) + (b * v)).legendre();
 71  
 72              // Ensure e is nonzero.
 73              ensure!(!e.is_zero(), "Elligator2 failed: e == 0");
 74  
 75              // Let x = ev - ((1 - e) * A/2).
 76              let x = match e {
 77                  LegendreSymbol::Zero => -a * Field::<E>::half(),
 78                  LegendreSymbol::QuadraticResidue => v,
 79                  LegendreSymbol::QuadraticNonResidue => -v - a,
 80              };
 81  
 82              // Ensure x is nonzero.
 83              ensure!(!x.is_zero(), "Elligator2 failed: x == 0");
 84  
 85              // Let y = -e * sqrt(x^3 + Ax^2 + Bx).
 86              let x2 = x.square();
 87              let rhs = (x2 * x) + (a * x2) + (b * x);
 88              let value =
 89                  rhs.even_square_root().map_err(|_| anyhow!("Elligator2 failed: even_sqrt(x^3 + Ax^2 + Bx) failed"))?;
 90  
 91              let y = match e {
 92                  LegendreSymbol::Zero => Field::<E>::zero(),
 93                  LegendreSymbol::QuadraticResidue => -value,
 94                  LegendreSymbol::QuadraticNonResidue => value,
 95              };
 96  
 97              // Ensure y is nonzero.
 98              ensure!(!y.is_zero(), "Elligator2 failed: y == 0");
 99  
100              // Ensure (x, y) is a valid Weierstrass element on: y^2 == x^3 + A * x^2 + B * x.
101              ensure!(y.square() == rhs, "Elligator2 failed: y^2 != x^3 + A * x^2 + B * x");
102  
103              // Convert the Weierstrass element (x, y) to Montgomery element (u, v).
104              let u = x * Group::MONTGOMERY_B;
105              let v = y * Group::MONTGOMERY_B;
106  
107              // Ensure (u, v) is a valid Montgomery element on: B * v^2 == u^3 + A * u^2 + u
108              let u2 = u.square();
109              ensure!(
110                  Group::MONTGOMERY_B * v.square() == (u2 * u) + (Group::MONTGOMERY_A * u2) + u,
111                  "Elligator2 failed: B * v^2 != u^3 + A * u^2 + u"
112              );
113  
114              (u, v)
115          };
116  
117          // Convert the Montgomery element (u, v) to the twisted Edwards element (x, y).
118          let x = u * v.inverse().map_err(|_| anyhow!("Elligator2 failed: v == 0"))?;
119          let y = (u - one) * (u + one).inverse().map_err(|_| anyhow!("Elligator2 failed: (u + 1) == 0"))?;
120  
121          // Recover the point from the twisted Edwards element (x, y).
122          let point = Group::from_xy_coordinates_unchecked(x, y);
123          // Ensure the recovered point is on the curve.
124          ensure!(point.to_affine().is_on_curve(), "Elligator2 failed: point is not on the curve");
125          // Return the recovered point.
126          Ok((point, sign_high))
127      }
128  }