Author: Tony Patti, Cryptographer | Reference Implementation v0.4.7 | May 2026
This REFERENCE IMPLEMENTATION IN RUST represents a significant evolution of the Hill Cipher, moving beyond simple matrix multiplication into a multi-layered Extended Affine Transformation. By operating over a large prime field e.g. GF(997727) and utilizing dimensions up to 2000x2000 (or even larger), the system uses multi-megabit keys to achieve a work factor that defies conventional brute-force paradigms. Why RUST? Because its Rayon crate makes it so easy for parallel calculations, on a 24-thread computer, "top" shows 23 threads engaged simultaneously on the matrix math.
| ➔ | If you want to download (the latest version of) this software, click here for the Rust program "Hill-GF-Extended.rs" |
The (original) Hill Cipher encryption is defined by the simple equation: C = M * P using mod 26 arithmetic,
in this extension, we add non-linearity, C = SP(M * INS(SUB(P)) + A) using Galois Field arithmetic, where:
The system integrates Probabilistic Injection (3 random bits inserted per 16 bits of plaintext) which means that re-encrypting one plaintext block will yield completely different ciphertext each time, without chaining. ensuring that even identical plaintext blocks produce unique ciphertext outcomes.
As an example: at a dimension of 2000, the probabilistic variance of a single block reaches 2^6000 unique ciphertext possibilities—a number so vast it dwarfs the number of atoms in the observable universe (~2^265). This ensures that even with identical plaintext, the "noise" injected into the system makes pattern recognition asymptotically impossible.
This web page provides the exact line-for-line source code required for a full reference implementation, with side-by-side explanatory text.
| (no command given) | |
|---|
| keygen command (Key Generation) 500x500 matrix containing 250,000 numbers at 20 bits each Optionally you can change the modulus via "--mod" for example "--mod 524289" to another 20-bit prime |
|
|---|
| keygen command (Key Generation) 1000x1000 matrix containing 1,000,000 numbers at 20 bits each |
|
|---|
| encrypt command | |
|---|
| decrypt command | |
|---|
| info command (details about a key file) |
|
|---|
| Full Source Code (Hill-GF-Extended.rs) | Architectural Documentation |
|---|---|
| /* * Hill-GF-Extended - Reference Implementation - version 0.4.7 * * * PURPOSE: * This program implements an "Extended Affine Hill Cipher" over a Prime Finite Field GF(P). * 1. INPUT SUBSTITUTION: Dual 8-bit S-Boxes transform input before matrix ops. * 2. PROBABILISTIC INJECTION: 3 random bits per element create asymptotic OTP variance. * 3. AFFINE TRANSFORMATION: Adds a random secret Offset vector after Matrix Multiplication. * 4. OUTPUT SUBSTITUTION: Numeric digits of the ciphertext are mapped to ASCII pools. * 5. CIPHERTEXT PERMUTATION: The order of digits within the homophonic strings is shuffled. * * * DIRECT COMMANDS: * --keygen Generates and saves a new key file with metadata. * --encrypt Encrypts a file using a specified key. * --decrypt Decrypts a ciphertext using a specified key. * --info Calculates and displays detailed entropy and work-factor stats. * --timing Displays timing for each phase of the key generation. * --help Displays this usage summary. * (will also display if you provide no commands) * * * PARAMETERS: * --dim <N> Dimension of the square matrix (Default: 20). * --mod <P> Prime modulus selectable from the range [524,289 ... 999,983] * This provides for 35,108 different primes. (Default: 997727). * --plain <name> Plaintext file path (Default: msg.txt). * --cipher <name> Ciphertext file path (Default: msg.enc). * --key <name> Key file path (Default: master.key). * * Author: Tony Patti, Cryptographer, May 2026 */ use rand::seq::SliceRandom; use rand::Rng; use rand::rngs::OsRng; use std::collections::{HashMap, HashSet}; use std::io::{self, Read, Write, BufRead, BufReader}; use std::fs::File; use std::time::Instant; use rayon::prelude::*; use std::env; const DEFAULT_MOD: u64 = 997727; const DEFAULT_DIM: usize = 500; const CHAR_POOL: &str = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; const NUM_CHARS_PER_DIGIT_MAPPING: usize = 5; const MAX_DIGITS_IN_MOD: usize = 6; struct KeyStore { modulus: u64, dim: usize, offset: Vec<u64>, digit_perm: Vec<usize>, mapping: HashMap<u8, Vec<char>>, sbox_left: [u8; 256], sbox_right: [u8; 256], encr_matrix: Vec<Vec<u64>>, decr_matrix: Vec<Vec<u64>>, } |
1. System Purpose & State
The implementation defines a 5-layer security protocol:
KeyStore holds the entire cryptographic state, including both encryption and decryption matrices to optimize runtime performance.
|
| // --- [Utility & Help] --- fn fmt_num(n: u64) -> String { let s = n.to_string(); s.as_bytes().rchunks(3).rev() .map(|chunk| std::str::from_utf8(chunk).unwrap()) .collect::<Vec<_>>().join(",") } | |
| fn print_help() { println!("Hill-GF-Extended Cryptosystem v0.4.6"); println!("Usage:"); println!(" --keygen [--dim N] [--mod P] [--key name] [--timing]"); println!(" --encrypt [--key name] [--plain name] [--cipher name] [--timing]"); println!(" --decrypt [--key name] [--plain name] [--cipher name] [--timing]"); println!(" --info [--key name]"); println!("\nDefaults: --dim 20 --mod 997727 --plain msg.txt --cipher msg.enc --key master.key"); } | 2. User Interface & Command-Line Interface (CLI) Logic The print_help() function serves as the primary interface for user guidance. It provides a standardized usage summary that outlines the available commands—--keygen, --encrypt, --decrypt, and --info—alongside their required and optional parameters. From an architectural standpoint, this utility is triggered during the initial argument-parsing phase in main(). If the program detects the --help flag or receives no operational commands, it executes this function to display the system's syntax and default configurations before terminating execution. This ensures that the user is fully aware of the environment variables, such as the default Modulus (997727) and Dimension (20), before attempting cryptographic operations. |
| fn calculate_entropy(ks: &KeyStore) { let mod_bits = (ks.modulus as f64).log2().ceil() as u64; let mod_choice_bits = 15; let matrix_bits = (ks.dim * ks.dim) as u64 * mod_bits; let offset_bits = (ks.dim as u64) * mod_bits; let sbox_total_bits = ((1..=256).map(|i| (i as f64).log2()).sum::<f64>() * 2.0) as u64; let digit_perm_bits = (1..=10).map(|i| (i as f64).log2()).sum::<f64>() as u64; let map_entropy_bits = (3..=52).map(|i| (i as f64).log2()).sum::<f64>() as u64; let random_injection_bits = (ks.dim * 3) as u64; let total_static_bits = mod_choice_bits + matrix_bits + offset_bits + sbox_total_bits + digit_perm_bits + map_entropy_bits; let log10_val = (random_injection_bits as f64) * 2.0f64.log10(); let exponent = log10_val.floor(); let mantissa = 10.0f64.powf(log10_val - exponent); println!("--- [Hill-GF-Extended System Info] ---"); println!("Modulus: {} (stored as {} bits)", fmt_num(ks.modulus), mod_bits); println!("Dimension: {} x {}", fmt_num(ks.dim as u64), fmt_num(ks.dim as u64)); println!("---------------------------------------"); println!("Modulus Selection Entropy (35,108 primes): {} bits", mod_choice_bits); println!("Input Byte Substitutions S-Box Entropy (x2): {} bits", fmt_num(sbox_total_bits)); println!("Encryption Matrix Entropy: {} bits", fmt_num(matrix_bits)); println!("Affine (offset) Vector Entropy: {} bits", fmt_num(offset_bits)); println!("Output Digit Permutation Entropy: {} bits", fmt_num(digit_perm_bits)); println!("Output Mapping Entropy: {} bits", fmt_num(map_entropy_bits)); println!("---------------------------------------"); println!("Total Static Key Material (Work Factor): {} bits", fmt_num(total_static_bits)); println!("Probabilistic Variance (Noise per Block): {} bits (3 bits x {})", fmt_num(random_injection_bits), fmt_num(ks.dim as u64)); println!("Total unique ciphertexts per plaintext block: 2^{} (~{:.2} x 10^{:.0})", fmt_num(random_injection_bits), mantissa, exponent); println!("---------------------------------------"); } |
3. Audit & Information Theory
The calculate_entropy function quantifies the system's security strength.
By calculating entropy for the matrices, S-Boxes, and digit mappings, the system provides a theoretical Work Factor for any given dimension. The Probabilistic Variance calculation highlights the number of possible ciphertexts per plaintext block. |
| // --- [File Parsers] --- fn parse_vec_u64(s: &str) -> Vec<u64> { s.replace(|c: char| !c.is_digit(10) && c != ',', "") .split(',') .filter_map(|v| v.trim().parse::<u64>().ok()) .collect() } fn parse_matrix(buffer: &str) -> Vec<Vec<u64>> { let mut rows = Vec::new(); let clean = buffer.trim_matches(|c| c == '[' || c == ']' || c == ' '); for row_str in clean.split("], [") { let r = parse_vec_u64(row_str); if !r.is_empty() { rows.push(r); } } rows } fn parse_key_file(path: &str) -> io::Result<KeyStore> { let file = File::open(path)?; let reader = BufReader::new(file); let (mut modulus, mut dim) = (0, 0); let (mut offset, mut digit_perm) = (Vec::new(), Vec::new()); let (mut sbox_l, mut sbox_r) = ([0u8; 256], [0u8; 256]); let (mut enc_m, mut dec_m) = (Vec::new(), Vec::new()); let mut mapping = HashMap::new(); let (mut current_sec, mut buffer) = (String::new(), String::new()); for line in reader.lines() { let l = line?; if l.is_empty() { continue; } if l.contains(':') && !l.starts_with(" ") && !l.starts_with("[") { current_sec = l.split(':').next().unwrap().trim().to_string(); buffer = l.splitn(2, ':').nth(1).unwrap().trim().to_string(); } else { buffer.push_str(&l); } match current_sec.as_str() { "Modulus" => modulus = buffer.parse().unwrap_or(0), "Dimension" => dim = buffer.parse().unwrap_or(0), "Offset Vector" => offset = parse_vec_u64(&buffer), "Digit Permutation" => digit_perm = parse_vec_u64(&buffer).into_iter().map(|v| v as usize).collect(), "S-Box Left" => { for (i, &v) in parse_vec_u64(&buffer).iter().enumerate().take(256) { sbox_l[i] = v as u8; } }, "S-Box Right" => { for (i, &v) in parse_vec_u64(&buffer).iter().enumerate().take(256) { sbox_r[i] = v as u8; } }, "Encryption Matrix" => if l.contains("]]") { enc_m = parse_matrix(&buffer); }, "Decryption Matrix" => if l.contains("]]") { dec_m = parse_matrix(&buffer); }, "Homophonic Mapping" => if buffer.contains('}') { let raw = buffer.trim_matches(|c| c == '{' || c == '}'); for part in raw.split("],") { let kv: Vec<&str> = part.splitn(2, ':').collect(); if kv.len() == 2 { let d = kv[0].trim().parse::<u8>().unwrap_or(0); let chars: Vec<char> = kv[1].chars().filter(|c| c.is_alphabetic()).collect(); mapping.insert(d, chars); } } }, _ => {} } } Ok(KeyStore { modulus, dim, offset, digit_perm, mapping, sbox_left: sbox_l, sbox_right: sbox_r, encr_matrix: enc_m, decr_matrix: dec_m }) } |
4. Data Ingestion & Parsing
The parse_key_file logic handles the complex task of rebuilding the KeyStore from a text-based format.
It uses a stateful buffer to accumulate multi-line matrix data. This ensures that even at extreme dimensions, the system can accurately ingest the Encryption and Decryption matrices alongside the S-Box and Homophonic Mapping data. |
| // --- [SPN & Galois Engines] --- fn apply_spn_forward(value: u64, mapping: &HashMap<u8, Vec<char>>, perm: &[usize]) -> String { let digits_raw = format!("{:06}", value); let s: Vec<char> = digits_raw.chars().map(|c| { let d = c.to_digit(10).unwrap() as u8; let pool = mapping.get(&d).expect("MapErr"); *pool.choose(&mut OsRng).expect("PoolErr") }).collect(); let mut p = vec![' '; 6]; for i in 0..6 { p[i] = s[perm[i]]; } p.into_iter().collect() } fn apply_spn_backward(token: &str, mapping: &HashMap<u8, Vec<char>>, perm: &[usize]) -> u64 { let t: Vec<char> = token.chars().collect(); let mut u = vec![' '; 6]; for i in 0..6 { u[perm[i]] = t[i]; } let mut res_digits = String::new(); for c in u.iter() { for d in 0..=9 { if let Some(pool) = mapping.get(&d) { if pool.contains(c) { res_digits.push_str(&d.to_string()); break; } } } } res_digits.parse().unwrap_or(0) } fn mod_inv(a: u64, m: u64) -> u64 { let mut a_i = a as i64; let mut m_i = m as i64; let (mut x, mut y, mut u, mut v) = (0, 1, 1, 0); while a_i != 0 { let q = m_i / a_i; let r = m_i % a_i; let m_new = x - u * q; let n_new = y - v * q; m_i = a_i; a_i = r; x = u; y = v; u = m_new; v = n_new; } ((x % m as i64) + m as i64) as u64 % m } fn mat_vec_mul_gf_parallel(matrix: &Vec<Vec<u64>>, vector: &Vec<u64>, modulus: u64) -> Vec<u64> { matrix.par_iter().map(|row| { let mut sum = 0u128; for (j, &val) in row.iter().enumerate() { sum = (sum + (val as u128 * vector[j] as u128)) % modulus as u128; } sum as u64 }).collect() } fn gauss_jordan_gf_parallel(matrix: Vec<Vec<u64>>, modulus: u64) -> Option<Vec<Vec<u64>>> { let n = matrix.len(); let mut augmented = vec![vec![0u64; 2 * n]; n]; for i in 0..n { for j in 0..n { augmented[i][j] = matrix[i][j]; } augmented[i][n + i] = 1; } for i in 0..n { let mut pivot = i; while pivot < n && augmented[pivot][i] == 0 { pivot += 1; } if pivot == n { return None; } augmented.swap(i, pivot); let inv = mod_inv(augmented[i][i], modulus); for j in 0..2 * n { augmented[i][j] = (augmented[i][j] as u128 * inv as u128 % modulus as u128) as u64; } let (before, rest) = augmented.split_at_mut(i); let (p_row_slice, after) = rest.split_at_mut(1); let p_row = &p_row_slice[0]; before.par_iter_mut().chain(after.par_iter_mut()).for_each(|row| { let factor = row[i]; if factor != 0 { for c in 0..2 * n { let term = (factor as u128 * p_row[c] as u128 % modulus as u128) as u64; row[c] = (row[c] + modulus - term) % modulus; } } }); } let mut inv_mat = vec![vec![0u64; n]; n]; for i in 0..n { for j in 0..n { inv_mat[i][j] = augmented[i][n + j]; } } Some(inv_mat) } |
5. Cryptographic Engines
This section contains the core mathematics:
|
| // --- [Main Entry] --- fn main() -> io::Result<()> { let args: Vec<String> = env::args().collect(); if args.len() < 2 || args.contains(&"--help".to_string()) { print_help(); return Ok(()); } let (mut run_keygen, mut run_encrypt, mut run_decrypt, mut run_info, mut show_timing) = (false, false, false, false, false); let (mut dim, mut modulus) = (DEFAULT_DIM, DEFAULT_MOD); let (mut p_file, mut c_file, mut k_file) = ("msg.txt".to_string(), "msg.enc".to_string(), "master.key".to_string()); let mut idx = 1; while idx < args.len() { match args[idx].as_str() { "--keygen" => run_keygen = true, "--encrypt" => run_encrypt = true, "--decrypt" => run_decrypt = true, "--info" => run_info = true, "--timing" => show_timing = true, "--dim" => { if let Some(v) = args.get(idx+1) { dim = v.parse().unwrap_or(DEFAULT_DIM); idx += 1; } }, "--mod" => { if let Some(v) = args.get(idx+1) { modulus = v.parse().unwrap_or(DEFAULT_MOD); idx += 1; } }, "--plain" => { if let Some(v) = args.get(idx+1) { p_file = v.clone(); idx += 1; } }, "--cipher" => { if let Some(v) = args.get(idx+1) { c_file = v.clone(); idx += 1; } }, "--key" => { if let Some(v) = args.get(idx+1) { k_file = v.clone(); idx += 1; } }, _ => {} } idx += 1; } if run_keygen { let total_start = Instant::now(); // --- PHASE 1: MATH --- let math_start = Instant::now(); let (e_mat, d_mat) = loop { let m = (0..dim).map(|_| (0..dim).map(|_| OsRng.gen_range(0..modulus)).collect::<Vec<u64>>()).collect::<Vec<Vec<u64>>>(); if let Some(inv) = gauss_jordan_gf_parallel(m.clone(), modulus) { break (m, inv); } }; let math_time = math_start.elapsed(); let mut s_l = [0u8; 256]; let mut s_r = [0u8; 256]; for j in 0..256 { s_l[j] = j as u8; s_r[j] = j as u8; } s_l.shuffle(&mut OsRng); s_r.shuffle(&mut OsRng); let off: Vec<u64> = (0..dim).map(|_| OsRng.gen_range(0..modulus)).collect(); let mut d_perm: Vec<usize> = (0..MAX_DIGITS_IN_MOD).collect(); d_perm.shuffle(&mut OsRng); let mut pool: Vec<char> = CHAR_POOL.chars().collect(); pool.shuffle(&mut OsRng); let mut used_chars = HashSet::new(); // --- PHASE 2: DISK I/O & FORMATTING --- let io_start = Instant::now(); let mut kf = File::create(&k_file)?; writeln!(kf, "Modulus: {}\nDimension: {}\nOffset Vector: {:?}\nDigit Permutation: {:?}\nS-Box Left: {:?}\nS-Box Right: {:?}\nEncryption Matrix: {:?}\nDecryption Matrix: {:?}", modulus, dim, off, d_perm, s_l, s_r, e_mat, d_mat)?; write!(kf, "Homophonic Mapping: {{")?; for d in 0..=9 { let mut selected = Vec::new(); while selected.len() < NUM_CHARS_PER_DIGIT_MAPPING && !pool.is_empty() { let c = pool.pop().unwrap(); if !used_chars.contains(&c) { selected.push(c); used_chars.insert(c); } } write!(kf, "{}: {:?}", d, selected)?; if d < 9 { write!(kf, ", ")?; } } writeln!(kf, "}}")?; let io_time = io_start.elapsed(); print!("Key generated: {}", k_file); if show_timing { println!("\n >> Math/Inversion: {:.2?}", math_time); println!(" >> Format/Disk IO: {:.2?}", io_time); println!(" >> Total Keygen : {:.2?}", total_start.elapsed()); } else { println!(""); } } |
6. Command Ingestion & Keygen
The main entry point parses arguments and handles the --keygen phase.
During key generation, the system separates Math and I/O operations to provide detailed timing telemetry. It generates random S-Boxes, Offset vectors, and uses the Gauss-Jordan engine to ensure the encryption matrix is invertible before writing the master.key file.
|
| if run_info { let ks = parse_key_file(&k_file)?; calculate_entropy(&ks); } if run_encrypt { let start = Instant::now(); let ks = parse_key_file(&k_file)?; let mut f = File::open(&p_file)?; let mut buf = Vec::new(); f.read_to_end(&mut buf)?; let mut c_out = Vec::new(); for chunk in buf.chunks(ks.dim * 2) { let mut data = chunk.to_vec(); data.resize(ks.dim * 2, 0); let p_v = (0..ks.dim).map(|k| { let (bl, br) = (ks.sbox_left[data[k*2] as usize] as u64, ks.sbox_right[data[k*2+1] as usize] as u64); let (r1, r2, r3) = (OsRng.gen_range(0..2) as u64, OsRng.gen_range(0..2) as u64, OsRng.gen_range(0..2) as u64); (r1 << 18) | (bl << 10) | (r2 << 9) | (br << 1) | r3 }).collect::<Vec<u64>>(); let c_v: Vec<u64> = mat_vec_mul_gf_parallel(&ks.encr_matrix, &p_v, ks.modulus).iter().enumerate().map(|(i, &v)| (v + ks.offset[i]) % ks.modulus).collect(); let tokens: Vec<String> = c_v.iter().map(|&v| apply_spn_forward(v, &ks.mapping, &ks.digit_perm)).collect(); c_out.push(format!("{}\n", tokens.join(" "))); } File::create(&c_file)?.write_all(c_out.concat().as_bytes())?; print!("Encrypted: {}", c_file); if show_timing { println!(" (Time: {:.2?})", start.elapsed()); } else { println!(""); } } if run_decrypt { let start = Instant::now(); let ks = parse_key_file(&k_file)?; let mut f = File::open(&c_file)?; let mut c_text = String::new(); f.read_to_string(&mut c_text)?; let mut recovered_bytes = Vec::new(); for line in c_text.lines() { let tokens: Vec<&str> = line.split_whitespace().collect(); if tokens.is_empty() { continue; } let c_v: Vec<u64> = tokens.iter().map(|t| apply_spn_backward(t, &ks.mapping, &ks.digit_perm)).collect(); let cp: Vec<u64> = c_v.iter().enumerate().map(|(i, &v)| (v + ks.modulus - ks.offset[i]) % ks.modulus).collect(); let p_v = mat_vec_mul_gf_parallel(&ks.decr_matrix, &cp, ks.modulus); for val in p_v { recovered_bytes.push(ks.sbox_left.iter().position(|&x| x == ((val >> 10) & 0xFF) as u8).unwrap() as u8); recovered_bytes.push(ks.sbox_right.iter().position(|&x| x == ((val >> 1) & 0xFF) as u8).unwrap() as u8); } } while recovered_bytes.last() == Some(&0) { recovered_bytes.pop(); } File::create(&p_file)?.write_all(&recovered_bytes)?; print!("Decrypted: {}", p_file); if show_timing { println!(" (Time: {:.2?})", start.elapsed()); } else { println!(""); } } Ok(()) } |
7. Runtime Execution Loops
The Encryption and Decryption loops implement the final transformation cycles:
|