Ed25519

Due Friday, 31 Oct. at 1440 ET.

Setup

Requirements

• To complete this assignment, you must:
  • Create a 82 directory in your 271rs repository.
  • This folder must be a Cargo package.

My responsibility

• I have adapted the official Python implementation to Python3 and added type hints.
• I provide, below, functions types for all functions used in my implementation.
• I provide a main.rs file which performance constant setup, shows an example of using a big number library, and checks validity using one of the test cases from the official Python implementation.

Your responsibility

• You will implement all functions of ed25519.py in Rust.
• You will ensure your code meets validity checks.
  • This will be as simple as cargo run provided you use the provided main.rs.

An Aside

• You will need to use cargo add to use external packages.
  • While you may use ix and your own SHA, this is not necessary or required.
• Besides using cargo add, you could also manually update the crates Cargo.toml file.
• I will also provide my Cargo.toml file.

Provided Files

Main

src/main.rs

use num::*;
use num_bigint::BigInt;
use num_traits::Euclid;

fn main() {
    // --- 1. Constant Setup  ---
    const B: usize = 256;
    
    // q: int = 2**255 - 19
    let q = BigInt::from(2).pow(255) - BigInt::from(19);

    // l: int = 2**252 + 27742317777372353535851937790883648493
    let l_suffix = BigInt::parse_bytes(b"27742317777372353535851937790883648493", 10).unwrap();
    let l = BigInt::from(2).pow(252) + l_suffix;

    // d: int = -121665 * inv(121666)
    let n_d = BigInt::from(-121665);
    let d_inv = inv(&BigInt::from(121666), &q);
    let d = (n_d * d_inv).rem_euclid(&q);

    // I: int = expmod(2,(q-1)//4,q)
    let exponent_i = (&q - BigInt::from(1)) / BigInt::from(4);
    let i_const = expmod(&BigInt::from(2), &exponent_i, &q);
    
    // By : int = 4 * inv(5)
    let by = (BigInt::from(4) * inv(&BigInt::from(5), &q)).rem_euclid(&q);
    
    // Bx : int = xrecover(By)
    let bx = xrecover(&by, &q, &d, &i_const);
    
    // B : List[int] = [Bx % q, By % q]
    let b_point: Vec<BigInt> = vec![bx.rem_euclid(&q), by.rem_euclid(&q)];

    // println!("Ed25519 Constant Initialization Complete.");
    
    // --- 2. Test Case ---
    // Line 2 of this file. https://ed25519.cr.yp.to/python/sign.input
    
    // Secret Key (32-bytes, all zeros)
    // 4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c
    let sk = vec![0x4c, 0xcd, 0x08, 0x9b, 0x28, 0xff, 0x96, 0xda, 0x9d, 0xb6, 0xc3, 0x46, 0xec, 0x11, 0x4e, 0x0f, 0x5b, 0x8a, 0x31, 0x9f, 0x35, 0xab, 0xa6, 0x24, 0xda, 0x8c, 0xf6, 0xed, 0x4f, 0xb8, 0xa6, 0xfb, 0x3d, 0x40, 0x17, 0xc3, 0xe8, 0x43, 0x89, 0x5a, 0x92, 0xb7, 0x0a, 0xa7, 0x4d, 0x1b, 0x7e, 0xbc, 0x9c, 0x98, 0x2c, 0xcf, 0x2e, 0xc4, 0x96, 0x8c, 0xc0, 0xcd, 0x55, 0xf1, 0x2a, 0xf4, 0x66, 0x0c];

    // Message
    // 72
    let m = 0x72;
    
    // 3. Generate Public Key
    let pk = publickey(&sk, B, &q, &d, &b_point);

    // 4. Create Signature
    let sig = signature(m, &sk, &pk, B, &q, &l, &d, &b_point);
    
    // 5. Verify Signature
    dbg!(checkvalid(&sig, m, &pk, B, &q, &d, &i_const, &b_point));
}

Cargo

Cargo.toml

[package]
name = "num"
version = "0.1.0"
edition = "2024"

[dependencies]
hex = "0.4.3"
num-bigint = "0.4.6"
num-integer = "0.1.46"
num-traits = "0.2.19"
sha2 = "0.10.9"

Lib

• In this case, I do not provide function bodies, but provide types, imports, and constants.

src/lib.rs

use num_bigint::BigInt;
use num_traits::{Zero, One, ToPrimitive, Euclid};
use num_integer::Integer;
use sha2::{Digest, Sha512};

// --- Global Helpers (No Dependencies) ---

// H(m: bytes) -> bytes
fn h(m: &[u8]) -> Vec<u8> {

// bit(h: bytes, i: int) -> int
fn bit(h_val: &[u8], i: usize) -> u8 {

// expmod(b:int,e:int,m:int) -> int
pub fn expmod(b_val: &BigInt, e: &BigInt, m: &BigInt) -> BigInt {

// inv(x:int, q: &BigInt) -> int
pub fn inv(x: &BigInt, q: &BigInt) -> BigInt {

// xrecover helper (nested for local use in setup and decode)
pub fn xrecover(y: &BigInt, q: &BigInt, d: &BigInt, i_const: &BigInt) -> BigInt {

// --- Core Functions (Require Constants) ---

fn edwards(p: &Vec<BigInt>, q_val: &Vec<BigInt>, q: &BigInt, d: &BigInt) -> Vec<BigInt> {

fn scalarmult(p: &Vec<BigInt>, e: &BigInt, q: &BigInt, d: &BigInt) -> Vec<BigInt> {

fn encodeint(y: &BigInt, b: usize) -> Vec<u8> {

fn encodepoint(p: &Vec<BigInt>, b: usize) -> Vec<u8> {

pub fn publickey(sk: &[u8], b: usize, q: &BigInt, d: &BigInt, b_point: &Vec<BigInt>) -> Vec<u8> {

fn hint(m: &[u8], b: usize) -> BigInt {

pub fn signature(m: &[u8], sk: &[u8], pk: &[u8], b: usize, q: &BigInt, l: &BigInt, d: &BigInt, b_point: &Vec<BigInt>) -> Vec<u8> {

fn isoncurve(p: &Vec<BigInt>, q: &BigInt, d: &BigInt) -> bool {

fn decodeint(s: &[u8], b: usize) -> BigInt {

fn decodepoint(s: &[u8], b: usize, q: &BigInt, d: &BigInt, i_const: &BigInt) -> Result<Point, &'static str> {

pub fn checkvalid(s: &[u8], m: &[u8], pk: &[u8], b: usize, q: &BigInt, d: &BigInt, i_const: &BigInt, b_point: &Vec<BigInt>) -> bool {