Help implement lamport signature in Rust

I'm trying to implement a Lamport signature. The idea is to have a function generate_keys() that generates a 4096-bit private key. Then, it generates a public key by hashing the private key in 32-bit blocks, resulting in an 8192-bit public key. Next, a function sign takes a message and the private key and creates an 8192-bit signature from the private key. Finally, a function verify takes the signature, message, and public key. It attempts to reconstruct blocks of the public key by hashing the signature and comparing them. If the reconstruction matches, the message is valid. Below is my implementation. I'm still new to Rust, and I can't see any flaws in my logic, but it doesn't work. I'd love help figuring out where the issue is and if there's a better way to do things.

use crate::helpers::{bin_to_hex, hex_to_bin};
use num_bigint::BigUint;
use rand::{rngs::OsRng, CryptoRng, RngCore};
use sha256::digest;

enum Index {
    Zero = 0,
    One = 1,
}

struct PrivateKey {
    index: Index,
    data: [String; 8],
}

impl PrivateKey {
    fn index_zero() -> Self {
        let mut rng = OsRng;
        let mut data: [String; 8] = Default::default();

        for num in data.iter_mut() {
            for element in 0..4 {
                num.push_str(&bin_to_hex(
                    hex_to_bin(
                        digest(hex_to_bin(
                            format!("{:0256X}", generate_random_256_bit_number(&mut rng)).as_str(),
                        ))
                        .as_str(),
                    )
                    .as_str(),
                ))
            }
        }

        PrivateKey {
            index: Index::Zero,
            data,
        }
    }

    fn index_one() -> Self {
        let mut rng = OsRng;
        let mut data: [String; 8] = Default::default();

        for num in data.iter_mut() {
            for element in 0..4 {
                num.push_str(&bin_to_hex(
                    hex_to_bin(
                        digest(hex_to_bin(
                            format!("{:0256X}", generate_random_256_bit_number(&mut rng)).as_str(),
                        ))
                        .as_str(),
                    )
                    .as_str(),
                ))
            }
        }
        PrivateKey {
            index: Index::One,
            data,
        }
    }
}
fn generate_random_256_bit_number<R: RngCore + CryptoRng>(rng: &mut R) -> BigUint {
    let mut bytes = [0u8; 64];

    rng.fill_bytes(&mut bytes);
    BigUint::from_bytes_be(&bytes)
}
fn generate_private_key() -> String {
    let private_key: String = {
        let mut result = String::new();

        for element in PrivateKey::index_zero().data.iter() {
            result.push_str(&element.to_string());
        }
        for element in PrivateKey::index_one().data.iter() {
            result.push_str(&element.to_string());
        }

        result
    };

    private_key
}
fn generate_public_key() -> String {
    let mut public_key = String::new();
    let private_key_bin = hex_to_bin(&generate_private_key());

    let mut start_index = 0;
    let mut end_index = 31;

    for _ in 0..128 {
        //generate a public key hash
        public_key.push_str(digest(&private_key_bin[start_index..end_index + 1]).as_str());
        start_index += 32;
        end_index += 32;
    }

    public_key
}
fn generate_keys() -> (String, String) {
    (generate_private_key(), generate_public_key())
}

fn sign(secret_key: &str, message: &str) -> String {
    let mut signature = String::new();
    let hashed_message = digest(message);
    let mut secret_key_0 = String::new();
    let mut secret_key_1 = String::new();
    //error below
    let hashed_bin_representation = hex_to_bin(&hashed_message);

    for (index, c) in hex_to_bin(secret_key).chars().enumerate() {
        if index < 8192 {
            secret_key_0.push_str(&c.to_string());
        } else {
            secret_key_1.push_str(&c.to_string());
        }
    }

    let mut start_index = 0;
    let mut end_index = 31;

    let mut start_index2 = 0;
    let mut end_index2 = 31;

    for (_, b) in hashed_bin_representation.chars().enumerate() {
        if b == '1' {
            signature.push_str(&secret_key_1[start_index..end_index + 1]);
            start_index += 32;
            end_index += 32;
        } else if b == '0' {
            signature.push_str(&secret_key_0[start_index2..end_index2 + 1]);
            start_index2 += 32;
            end_index2 += 32;
        }
    }

    signature = bin_to_hex(&signature);

    signature
}

fn verify(signature: &str, message: &str, public_key: &str) -> bool {
    let hashed_message = digest(message);

    let hashed_message_bin = hex_to_bin(&hashed_message);

    let signature_bin = hex_to_bin(signature);

    let mut start_index = 0;
    let mut end_index = 31;

    let mut counts = 0;
    for (_, _) in hashed_message_bin.chars().enumerate() {
        if public_key.contains(&digest(&signature_bin[start_index..end_index + 1])) {
            counts += 1;
        }

        start_index += 32;
        end_index += 32;
    }

    dbg!(&counts);
    counts == 128
}

#[cfg(test)]
mod tests {

    use super::*;
    #[test]
    fn secret_key_is_512_bits() {
        let _private_key: String = generate_private_key();
    }
    #[test]
    fn generate_keys_works() {
        let keys = generate_keys();
        println!("Private Key is :{}", keys.0);
        println!("Public Key is :{}", keys.1);
    }
    #[test]
    fn hash_message_works() {
        sign(generate_keys().0.as_str(), "In code we trust");
    }

    #[test]
    fn pub_key() {
        generate_public_key();
    }
    #[test]
    fn verify_signature() {
        // Generate keys

        let (private_key, public_key) = generate_keys();
        println!("The public key is , {}", public_key.len());
        // Message and sign it
        let message = "Amsc";
        let signature = sign(&private_key, message);

        // Verify signature
        let _result = verify(&signature, message, &public_key);
    }
}
// assert_eq!(
//     private_key.len() * 4,
//     512,
//     "Private key is not 512 bits long"
// );

Here are the helper functions below:

pub fn bin_to_hex(binary: &str) -> String {
    let mut hex = String::new();
    let mut chunk = String::new();

    for (i, bit) in binary.chars().enumerate() {
        chunk.push(bit);

        // If we've accumulated 4 bits, convert them to hexadecimal
        if (i + 1) % 4 == 0 {
            let hex_digit = match u8::from_str_radix(&chunk, 2) {
                Ok(val) => val,
                Err(_) => {
                    eprintln!("Error: Invalid binary string.");
                    return String::from("Error: Invalid binary string.");
                }
            };

            // Convert the decimal value to a hexadecimal character
            let hex_char = match hex_digit {
                0..=9 => (hex_digit + b'0') as char,
                10..=15 => (hex_digit - 10 + b'A') as char,
                _ => panic!("Invalid hexadecimal digit"),
            };

            hex.push(hex_char);

            // Clear the chunk for the next set of bits
            chunk.clear();
        }
    }

    // If there are remaining bits, pad the last chunk and convert it to hexadecimal
    if !chunk.is_empty() {
        while chunk.len() < 4 {
            chunk.push('0');
        }

        let hex_digit = u8::from_str_radix(&chunk, 2).unwrap();

        let hex_char = match hex_digit {
            0..=9 => (hex_digit + b'0') as char,
            10..=15 => (hex_digit - 10 + b'A') as char,
            _ => panic!("Invalid hexadecimal digit"),
        };

        hex.push(hex_char);
    }

    hex
}
pub fn hex_to_bin(hex_string: &str) -> String {
    let mut result = String::new();
    for c in hex_string.chars() {
        let hex_digit = c.to_digit(16).expect("Invalid hexadecimal digit");
        let bin_str = format!("{:04b}", hex_digit);
        result.push_str(&bin_str);
    }
    result
}
pub fn string_to_binary(input: &str) -> String {
    input.chars().map(|c| format!("{:08b}", c as u8)).collect()
}


I haven't looked at your code in detail yet, but are you sure String is the data type you want for your keys etc? That seems to be extremely unlikely to be correct, as Strings aren't used to store random bytes but have to contain correct UTF-8. You likely want to be working with byte vectors (Vec<u8>) and byte slices ([u8])

1 Like