edwards2.rn

//  Copyright 2021 Google LLC.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

import math

class EdwardsCurve(self, <m>, d: typeof(m), gy: typeof(m)) {
  self.m = m  // Modulus
  self.d = d  // Edwards curve d parameter
  self.gy = gy
  self.gx = self.computeX(gy)

  // Verify (gx, gy) is on the curve: -x**2 + y**2 = 1 + dx**2y**2:
  func pointOnCurve(self, P) -> bool {
    x = P.x; y = P.y
    m = self.m; d = self.d
    return -x**2 + y**2 == 1 + d*x**2*y**2 mod m
  }

  // Return the positive X coordinate given Y.
  func computeX(self, y) {
    root = math.msqrt((y**2 - 1)/(self.d*y**2 + 1) mod self.m, self.m)
    return min(root, self.m - root)
  }
}

// A point on the curve.
class Point(self, <curve>: EdwardsCurve, x: typeof(curve.m), y: typeof(curve.m)) {
  self.curve = curve
  self.x = x
  self.y = y
  if !curve.pointOnCurve(self) {
    raise Status.InvalidArgument, "The point is not on the curve"
  }

  operator + (a: Point, b: Point) -> Point {
    curve = a.curve
    if curve != b.curve {
      raise Status.InvalidArgument, "Points are on different curves"
    }
    d = curve.d
    m = curve.m
    x = (a.x*b.y + a.y*b.x) / (<d>1 + d*a.x*a.y*b.x*b.y) mod m
    y = (a.x*b.x + a.y*b.y) / (<d>1 - d*a.x*a.y*b.x*b.y) mod m
    return Point(curve, x, y)
  }

  // Only scalar multiplication is defined for elliptic curve points.
  operator * (k: Uint, P: Point) {
    R: typeof(P) = Point(P.curve, <typeof(P.x)>0, <typeof(P.y)>1)
    M: typeof(P) = P  // M is 2**n*P
    f = k
    while f != <f>0 {
      if f & <f>1 != <f>0 {
        R += M
      }
      M += M
      f >>= 1
    }
    return R
  }
}

unittest edwardsTest {
  // Curve 25519 parameters.
  m = <u255>(2u256**255 - 19)
  d = -121665/121666 mod m
  // Curve 25519 generator's Y coordinate.
  gy = 4 / 5 mod m
  println "gy * 5 = ", gy * 5 mod m
  curve = EdwardsCurve(m, d, gy)
  G = Point(curve, curve.gx, curve.gy) // Generateor base point
  println "gx = ", G.x
  println "gy = ", G.y
  a = 5678u255  // Alice's private key
  A = a * G  // Alice's public key
  b = 1234u255  // Bob's private key
  B = b * G  // Bob's public key
  aliceSecret = a * B
  bobSecret = b * A
  println "Alice's secret = %x" % aliceSecret.x
  println "Bob's secret = %x" % bobSecret.x
  if aliceSecret.x != bobSecret.x {
    raise Exception.Internal, "Failed"
  }
  println "Passed"
}