use std::sync::atomic;
use std::{fmt, ops, ptr, str};
use cryptoxide::curve25519::*;
use generic_array::GenericArray;
use zeroize::{Zeroize, Zeroizing};
use crate::arithmetic::traits::*;
use crate::cryptographic_primitives::hashing::Digest;
use crate::BigInt;
use super::traits::{ECPoint, ECScalar};
use crate::elliptic::curves::{Curve, DeserializationError, NotOnCurve, PointCoords};
lazy_static::lazy_static! {
static ref GROUP_ORDER: BigInt = Ed25519Scalar {
purpose: "intermediate group_order",
fe: SK(Fe::from_bytes(&[
237, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16,
])).into()
}.to_bigint();
static ref ZERO: Ed25519Point = Ed25519Point {
purpose: "zero",
ge: ge_scalarmult_base(&[
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0,
]),
};
static ref GENERATOR: Ed25519Point = Ed25519Point {
purpose: "generator",
ge: ge_scalarmult_base(&[
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0,
]),
};
static ref BASE_POINT2: Ed25519Point = {
let bytes = GENERATOR.serialize_compressed();
let hashed = sha2::Sha256::digest(bytes.as_ref());
let hashed_twice = sha2::Sha256::digest(&hashed);
let p = Ed25519Point::deserialize(&hashed_twice).unwrap();
let eight = Ed25519Scalar::from_bigint(&BigInt::from(8));
Ed25519Point {
purpose: "base_point2",
ge: p.scalar_mul(&eight).ge,
}
};
}
const FE_ZERO: Fe = Fe([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
const TWO_TIMES_SECRET_KEY_SIZE: usize = 64;
pub type PK = GeP3;
#[derive(Clone)]
pub struct SK(pub Fe);
impl Zeroize for SK {
fn zeroize(&mut self) {
self.0 .0.zeroize()
}
}
impl ops::Deref for SK {
type Target = Fe;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl ops::DerefMut for SK {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum Ed25519 {}
#[derive(Clone)]
pub struct Ed25519Scalar {
#[allow(dead_code)]
purpose: &'static str,
fe: Zeroizing<SK>,
}
#[derive(Clone, Copy)]
pub struct Ed25519Point {
#[allow(dead_code)]
purpose: &'static str,
ge: PK,
}
pub type GE = Ed25519Point;
pub type FE = Ed25519Scalar;
impl Curve for Ed25519 {
type Point = GE;
type Scalar = FE;
const CURVE_NAME: &'static str = "ed25519";
}
impl ECScalar for Ed25519Scalar {
type Underlying = SK;
type ScalarLength = typenum::U32;
fn random() -> Ed25519Scalar {
let rnd_bn = BigInt::sample_below(Self::group_order());
let rnd_bn_mul_8 = BigInt::mod_mul(&rnd_bn, &BigInt::from(8), Self::group_order());
Ed25519Scalar {
purpose: "random",
fe: Self::from_bigint(&rnd_bn_mul_8).fe,
}
}
fn zero() -> Ed25519Scalar {
Ed25519Scalar {
purpose: "zero",
fe: SK(FE_ZERO).into(),
}
}
fn is_zero(&self) -> bool {
self.fe.0 == FE_ZERO
}
fn from_bigint(n: &BigInt) -> Ed25519Scalar {
let mut v = BigInt::to_bytes(n);
if v.len() > TWO_TIMES_SECRET_KEY_SIZE {
v = v[0..TWO_TIMES_SECRET_KEY_SIZE].to_vec();
}
let mut template = vec![0; TWO_TIMES_SECRET_KEY_SIZE - v.len()];
template.extend_from_slice(&v);
v = template;
v.reverse();
sc_reduce(&mut v[..]);
Ed25519Scalar {
purpose: "from_bigint",
fe: SK(Fe::from_bytes(&v[..])).into(),
}
}
fn to_bigint(&self) -> BigInt {
let mut t = self.fe.to_bytes().to_vec();
t.reverse();
BigInt::from_bytes(&t)
}
fn serialize(&self) -> GenericArray<u8, Self::ScalarLength> {
GenericArray::from(self.fe.to_bytes())
}
fn deserialize(bytes: &[u8]) -> Result<Self, DeserializationError> {
if bytes.len() != 32 {
return Err(DeserializationError);
}
Ok(Ed25519Scalar {
purpose: "deserialize",
fe: SK(Fe::from_bytes(bytes)).into(),
})
}
fn add(&self, other: &Self) -> Ed25519Scalar {
Ed25519Scalar {
purpose: "add",
fe: Self::from_bigint(&BigInt::mod_add(
&self.to_bigint(),
&other.to_bigint(),
Self::group_order(),
))
.fe,
}
}
fn mul(&self, other: &Self) -> Ed25519Scalar {
Ed25519Scalar {
purpose: "mul",
fe: Self::from_bigint(&BigInt::mod_mul(
&self.to_bigint(),
&other.to_bigint(),
Self::group_order(),
))
.fe,
}
}
fn sub(&self, other: &Self) -> Ed25519Scalar {
Ed25519Scalar {
purpose: "sub",
fe: Self::from_bigint(&BigInt::mod_sub(
&self.to_bigint(),
&other.to_bigint(),
Self::group_order(),
))
.fe,
}
}
fn neg(&self) -> Self {
Ed25519Scalar {
purpose: "neg",
fe: Self::from_bigint(&BigInt::mod_sub(
&Self::zero().to_bigint(),
&self.to_bigint(),
Self::group_order(),
))
.fe,
}
}
fn invert(&self) -> Option<Ed25519Scalar> {
if self.is_zero() {
None
} else {
Some(Ed25519Scalar {
purpose: "invert",
fe: Self::from_bigint(&BigInt::mod_inv(&self.to_bigint(), Self::group_order())?).fe,
})
}
}
fn group_order() -> &'static BigInt {
&GROUP_ORDER
}
fn underlying_ref(&self) -> &Self::Underlying {
&self.fe
}
fn underlying_mut(&mut self) -> &mut Self::Underlying {
&mut self.fe
}
fn from_underlying(fe: Self::Underlying) -> Ed25519Scalar {
Ed25519Scalar {
purpose: "from_underlying",
fe: fe.into(),
}
}
}
impl fmt::Debug for Ed25519Scalar {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(
f,
"Point {{ purpose: {:?}, bytes: {:?} }}",
self.purpose,
self.fe.to_bytes()
)
}
}
impl PartialEq for Ed25519Scalar {
fn eq(&self, other: &Ed25519Scalar) -> bool {
self.fe.0 == other.fe.0
}
}
impl fmt::Debug for Ed25519Point {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(
f,
"Point {{ purpose: {:?}, bytes: {:?} }}",
self.purpose,
self.ge.to_bytes()
)
}
}
impl PartialEq for Ed25519Point {
fn eq(&self, other: &Ed25519Point) -> bool {
self.ge.to_bytes() == other.ge.to_bytes()
}
}
impl Zeroize for Ed25519Point {
fn zeroize(&mut self) {
unsafe { ptr::write_volatile(&mut self.ge, GENERATOR.ge) };
atomic::compiler_fence(atomic::Ordering::SeqCst);
}
}
impl ECPoint for Ed25519Point {
type Underlying = PK;
type Scalar = Ed25519Scalar;
type CompressedPointLength = typenum::U32;
type UncompressedPointLength = typenum::U32;
fn zero() -> Ed25519Point {
*ZERO
}
fn is_zero(&self) -> bool {
self == &*ZERO
}
fn generator() -> &'static Ed25519Point {
&GENERATOR
}
fn base_point2() -> &'static Ed25519Point {
&BASE_POINT2
}
fn from_coords(x: &BigInt, y: &BigInt) -> Result<Ed25519Point, NotOnCurve> {
let is_odd = x.is_odd();
let expected_x = xrecover(y, is_odd);
if &expected_x != x {
return Err(NotOnCurve);
}
let y_bytes = y.to_bytes();
let mut padded = match y_bytes.len() {
n if n > 32 => return Err(NotOnCurve),
32 => y_bytes,
_ => {
let mut padding = vec![0; 32 - y_bytes.len()];
padding.extend_from_slice(&y_bytes);
padding
}
};
padded.reverse();
padded[31] |= (is_odd as u8) << 7;
Self::deserialize(&padded).map_err(|_e| NotOnCurve)
}
fn x_coord(&self) -> Option<BigInt> {
self.coords().map(|c| c.x)
}
fn y_coord(&self) -> Option<BigInt> {
let mut bytes = self.ge.to_bytes();
bytes[31] &= 0b01111111;
bytes.reverse();
Some(BigInt::from_bytes(&bytes))
}
fn coords(&self) -> Option<PointCoords> {
let mut bytes = self.ge.to_bytes();
let is_odd = (bytes[31] >> 7) == 1;
bytes[31] &= 0b01111111;
bytes.reverse();
let y = BigInt::from_bytes(&bytes);
let x = xrecover(&y, is_odd);
Some(PointCoords { x, y })
}
fn serialize_compressed(&self) -> GenericArray<u8, Self::CompressedPointLength> {
GenericArray::from(self.ge.to_bytes())
}
fn serialize_uncompressed(&self) -> GenericArray<u8, Self::UncompressedPointLength> {
GenericArray::from(self.ge.to_bytes())
}
fn deserialize(bytes: &[u8]) -> Result<Ed25519Point, DeserializationError> {
let bytes_vec = bytes.to_vec();
let mut bytes_array_32 = [0u8; 32];
let byte_len = bytes_vec.len();
match byte_len {
0..=32 => {
let mut template = vec![0; 32 - byte_len];
template.extend_from_slice(bytes);
let bytes_vec = template;
let bytes_slice = &bytes_vec[0..32];
bytes_array_32.copy_from_slice(bytes_slice);
let ge_from_bytes = PK::from_bytes_negate_vartime(&bytes_array_32);
match ge_from_bytes {
Some(_x) => {
let ge_bytes = ge_from_bytes.unwrap().to_bytes();
let ge_from_bytes = PK::from_bytes_negate_vartime(&ge_bytes[..]);
match ge_from_bytes {
Some(y) => Ok(Ed25519Point {
purpose: "deserialize",
ge: y,
}),
None => Err(DeserializationError),
}
}
None => Err(DeserializationError),
}
}
_ => {
let bytes_slice = &bytes_vec[0..32];
bytes_array_32.copy_from_slice(bytes_slice);
let ge_from_bytes = PK::from_bytes_negate_vartime(bytes);
match ge_from_bytes {
Some(_x) => {
let ge_bytes = ge_from_bytes.unwrap().to_bytes();
let ge_from_bytes = PK::from_bytes_negate_vartime(&ge_bytes[..]);
match ge_from_bytes {
Some(y) => Ok(Ed25519Point {
purpose: "random",
ge: y,
}),
None => Err(DeserializationError),
}
}
None => Err(DeserializationError),
}
}
}
}
fn scalar_mul(&self, fe: &Self::Scalar) -> Ed25519Point {
let vec_0 = [
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0,
];
let p2_point = GeP2::double_scalarmult_vartime(&fe.fe.to_bytes()[..], self.ge, &vec_0[..]);
let mut p2_bytes = p2_point.to_bytes();
p2_bytes[31] ^= 1 << 7;
let ge = GeP3::from_bytes_negate_vartime(&p2_bytes[..]).unwrap();
Ed25519Point {
purpose: "scalar_mul",
ge,
}
}
fn add_point(&self, other: &Self) -> Ed25519Point {
let pkpk = self.ge + other.ge.to_cached();
let mut pk_p2_bytes = pkpk.to_p2().to_bytes();
pk_p2_bytes[31] ^= 1 << 7;
Ed25519Point {
purpose: "add",
ge: PK::from_bytes_negate_vartime(&pk_p2_bytes).unwrap(),
}
}
fn sub_point(&self, other: &Self) -> Ed25519Point {
let pkpk = self.ge - other.ge.to_cached();
let mut pk_p2_bytes = pkpk.to_p2().to_bytes();
pk_p2_bytes[31] ^= 1 << 7;
Ed25519Point {
purpose: "sub",
ge: PK::from_bytes_negate_vartime(&pk_p2_bytes).unwrap(),
}
}
fn neg_point(&self) -> Self {
ZERO.sub_point(self)
}
fn underlying_ref(&self) -> &Self::Underlying {
&self.ge
}
fn underlying_mut(&mut self) -> &mut Self::Underlying {
&mut self.ge
}
fn from_underlying(ge: Self::Underlying) -> Ed25519Point {
Ed25519Point {
purpose: "from_underlying",
ge,
}
}
}
#[allow(clippy::many_single_char_names)]
fn xrecover(y_coor: &BigInt, is_odd: bool) -> BigInt {
let q = BigInt::from(2u32).pow(255u32) - BigInt::from(19u32);
let one = BigInt::one();
let d_n = -BigInt::from(121_665i32);
let d_d = expmod(&BigInt::from(121_666), &(q.clone() - BigInt::from(2)), &q);
let d_bn = d_n * d_d;
let y_sqr = y_coor * y_coor;
let u = y_sqr.clone() - one.clone();
let v = y_sqr * d_bn + one;
let v_inv = expmod(&v, &(q.clone() - BigInt::from(2)), &q);
let x_sqr = u * v_inv;
let q_plus_3_div_8 = (q.clone() + BigInt::from(3i32)) / BigInt::from(8i32);
let mut x = expmod(&x_sqr, &q_plus_3_div_8, &q);
if BigInt::mod_sub(&(x.clone() * x.clone()), &x_sqr, &q) != BigInt::zero() {
let q_minus_1_div_4 = (q.clone() - BigInt::from(1i32)) / BigInt::from(4i32);
let i = expmod(&BigInt::from(2i32), &q_minus_1_div_4, &q);
x = BigInt::mod_mul(&x, &i, &q);
}
if x.is_odd() != is_odd {
q - x
} else {
x
}
}
fn expmod(b: &BigInt, e: &BigInt, m: &BigInt) -> BigInt {
let one = BigInt::one();
if e.clone() == BigInt::zero() {
return one;
};
let t_temp = expmod(b, &(e.clone() / BigInt::from(2u32)), m);
let mut t = BigInt::mod_pow(&t_temp, &BigInt::from(2u32), m);
if BigInt::modulus(e, &BigInt::from(2)) != BigInt::zero() {
t = BigInt::mod_mul(&t, b, m);
}
t
}
#[cfg(test)]
mod tests {
use crate::arithmetic::traits::Converter;
use crate::elliptic::curves::{Ed25519, Point, Scalar};
use crate::BigInt;
#[test]
fn test_vectors_coordinates() {
#[rustfmt::skip]
let dalek = [
([26, 213, 37, 143, 96, 45, 86, 201, 178, 167, 37, 149, 96, 199, 44, 105, 92, 220, 214, 253, 49, 226, 164, 192, 254, 83, 110, 205, 211, 54, 105, 33], [88, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102]),
([14, 206, 67, 40, 78, 161, 197, 131, 95, 164, 215, 21, 69, 142, 13, 8, 172, 231, 51, 24, 125, 59, 4, 61, 108, 4, 90, 159, 76, 56, 171, 54], [201, 163, 248, 106, 174, 70, 95, 14, 86, 81, 56, 100, 81, 15, 57, 151, 86, 31, 162, 201, 232, 94, 162, 29, 194, 41, 35, 9, 243, 205, 96, 34]),
([112, 248, 201, 196, 87, 166, 58, 73, 71, 21, 206, 147, 193, 158, 115, 26, 249, 32, 53, 122, 184, 212, 37, 131, 70, 241, 207, 86, 219, 168, 61, 32], [47, 17, 50, 202, 97, 171, 56, 223, 240, 15, 47, 234, 50, 40, 242, 76, 108, 113, 213, 128, 133, 184, 14, 71, 225, 149, 21, 203, 39, 232, 208, 71]),
([200, 132, 165, 8, 188, 253, 135, 59, 153, 139, 105, 128, 123, 198, 58, 235, 147, 207, 78, 248, 92, 45, 134, 66, 182, 113, 215, 151, 95, 225, 66, 103], [180, 185, 55, 252, 169, 91, 47, 30, 147, 228, 30, 98, 252, 60, 120, 129, 143, 243, 138, 102, 9, 111, 173, 110, 121, 115, 229, 201, 0, 6, 211, 33]),
([248, 249, 40, 108, 109, 89, 178, 89, 116, 35, 191, 231, 51, 141, 87, 9, 145, 156, 36, 8, 21, 43, 226, 184, 238, 58, 229, 39, 6, 134, 164, 35], [235, 39, 103, 193, 55, 171, 122, 216, 39, 156, 7, 142, 255, 17, 106, 176, 120, 110, 173, 58, 46, 15, 152, 159, 114, 195, 127, 130, 242, 150, 150, 112]),
([38, 79, 126, 151, 246, 64, 221, 79, 252, 82, 120, 249, 144, 49, 3, 230, 125, 86, 57, 11, 29, 86, 130, 133, 249, 26, 66, 23, 105, 108, 207, 57], [105, 210, 6, 58, 79, 57, 45, 249, 56, 64, 140, 76, 231, 5, 18, 180, 120, 139, 248, 192, 236, 147, 222, 122, 107, 206, 44, 225, 14, 169, 52, 68]),
([11, 164, 60, 176, 15, 122, 81, 241, 120, 214, 217, 106, 253, 70, 232, 184, 168, 121, 29, 135, 249, 144, 242, 156, 19, 41, 248, 11, 32, 100, 250, 5], [38, 9, 218, 23, 175, 149, 214, 251, 106, 25, 13, 110, 94, 18, 241, 153, 76, 170, 168, 111, 121, 134, 244, 114, 40, 0, 38, 249, 234, 158, 25, 61]),
([135, 221, 207, 240, 91, 73, 162, 93, 64, 122, 35, 38, 164, 122, 131, 138, 183, 139, 210, 26, 191, 234, 2, 36, 8, 95, 123, 169, 177, 190, 157, 55], [252, 134, 75, 8, 238, 231, 160, 253, 33, 69, 9, 52, 193, 97, 50, 35, 252, 155, 85, 72, 83, 153, 247, 99, 208, 153, 206, 1, 224, 159, 235, 40]),
([86, 165, 194, 12, 221, 188, 184, 32, 109, 87, 97, 181, 251, 120, 181, 212, 73, 84, 144, 38, 193, 203, 233, 230, 191, 236, 29, 78, 237, 7, 126, 94], [199, 246, 108, 86, 49, 32, 20, 14, 168, 217, 39, 193, 154, 61, 27, 125, 14, 38, 211, 129, 170, 235, 245, 107, 121, 2, 241, 81, 92, 117, 85, 15]),
([10, 52, 205, 130, 60, 51, 9, 84, 210, 97, 57, 48, 155, 253, 239, 33, 38, 212, 112, 250, 238, 249, 49, 51, 115, 132, 208, 179, 129, 191, 236, 46], [232, 147, 139, 0, 100, 247, 156, 184, 116, 224, 230, 73, 72, 77, 77, 72, 182, 25, 161, 64, 183, 217, 50, 65, 124, 130, 55, 161, 45, 220, 210, 84]),
([104, 43, 74, 91, 213, 199, 81, 145, 29, 225, 42, 75, 196, 71, 241, 188, 122, 179, 203, 200, 182, 124, 172, 144, 5, 253, 243, 249, 82, 58, 17, 107], [61, 193, 39, 243, 89, 67, 149, 144, 197, 150, 121, 245, 244, 149, 101, 41, 6, 156, 81, 5, 24, 218, 184, 46, 121, 126, 105, 89, 113, 1, 235, 26]),
([247, 23, 19, 189, 251, 188, 210, 236, 69, 179, 21, 49, 233, 175, 130, 132, 61, 40, 198, 252, 17, 245, 65, 181, 139, 211, 18, 118, 82, 231, 26, 60], [78, 54, 17, 7, 162, 21, 32, 81, 196, 42, 195, 98, 139, 94, 127, 166, 15, 249, 69, 133, 108, 17, 134, 183, 126, 229, 215, 249, 195, 145, 28, 5]),
([234, 214, 222, 41, 58, 0, 185, 2, 89, 203, 38, 196, 186, 153, 177, 151, 47, 142, 0, 146, 38, 79, 82, 235, 71, 27, 137, 139, 36, 192, 19, 125], [213, 32, 91, 128, 166, 128, 32, 149, 195, 233, 159, 142, 135, 158, 30, 158, 122, 199, 204, 117, 108, 165, 241, 145, 26, 168, 1, 44, 171, 118, 169, 89]),
([222, 201, 177, 49, 16, 22, 170, 53, 20, 106, 212, 181, 52, 130, 113, 210, 74, 93, 154, 31, 83, 38, 60, 229, 142, 141, 51, 127, 255, 169, 213, 23], [137, 175, 246, 164, 100, 213, 16, 224, 29, 173, 239, 68, 189, 218, 131, 172, 122, 168, 240, 28, 7, 249, 195, 67, 108, 63, 183, 211, 135, 34, 2, 115]),
([138, 75, 231, 56, 188, 218, 194, 176, 133, 225, 74, 254, 45, 68, 132, 203, 32, 107, 45, 191, 17, 156, 215, 190, 211, 62, 95, 191, 104, 188, 168, 7], [1, 137, 40, 34, 106, 120, 170, 41, 3, 200, 116, 149, 3, 62, 220, 189, 7, 19, 168, 162, 32, 45, 179, 24, 112, 66, 253, 122, 196, 215, 73, 114]),
];
let mut p = Point::<Ed25519>::generator().to_point();
for (mut x, mut y) in dalek {
x.reverse();
y.reverse();
let x_big = BigInt::from_bytes(&x);
let y_big = BigInt::from_bytes(&y);
let coordinates = p.coords().unwrap();
assert_eq!(coordinates.y, y_big);
assert_eq!(coordinates.x, x_big);
p = p * Scalar::from(2u16);
}
}
}