As a hobby project (and to learn the language), I'm working on a crypto library in Rust. The following is a component thereof, which implements encryption with and the cracking of the Caesar cipher.
My primary interest is whether the code follows best practices, with a secondary concern regarding its efficiency. I'm not very used to Rust idioms, and there are a few places where I feel that the code is clunky, but can't see a better solution.
Note that:
- this being a hobby project, I aim to write most everything myself and avoid external libraries;
- as this is part of a larger (as yet unwritten) framework, I have generalised more than necessary for this component alone. If it seems over-engineered, that would be because it has been designed for easy implementation of other [poly]alphabetic ciphers, like a more general substitution cipher or the Vigenère cipher.
lib.rs
#![feature(const_option)]
pub mod alphabetic;
pub mod caesar;
pub mod frequency;
alphabetic.rs
///Provides various types for dealing with alphabetic ciphers, like
///the Caesar and Vigenère ciphers.
use std::{
cmp::{self, Ordering},
fmt::{self, Display},
ops::{Add, Sub},
};
pub const ALPHABET_SIZE: usize = 26;
#[derive(Copy, Clone, Debug)]
pub enum Case {
Upper,
Lower,
}
#[derive(Copy, Clone, Debug)]
///Contains a `value` (zero-indexed and guaranteed to be in the range 0-25) and
/// a `Case` specifying the case. The case is only used for display purposes,
/// and when cases are mixed in arithmetic operations, the output favours
///`Case::Upper` (so if one letter is uppercase, the result will also be
/// uppercase); this ensures that addition is at least commutative.
pub struct Letter {
pub value: u8,
pub case: Case,
}
impl Letter {
///Constructs a new `Letter` from its `u8` and `Case` components.
pub const fn new(value: u8, case: Case) -> Letter {
Letter {
value: (value) % ALPHABET_SIZE as u8,
case,
}
}
///Constructs a new `Letter`, accepting a negative alphabetical index
///(which will wrap around).
pub fn from_signed(value: i8, case: Case) -> Letter {
Letter {
//rem_euclid returns nonnegative integers so this cast is safe
value: value.rem_euclid(ALPHABET_SIZE as i8) as u8,
case,
}
}
///Returns the `Letter` corresponding to a given `char`, or `None` if
///the `char` is out of the alphabetical ASCII range.
pub const fn try_from_char(char_value: char) -> Option<Letter> {
let (start, case) = match char_value {
'A'..='Z' => ('A' as u32, Case::Upper),
'a'..='z' => ('a' as u32, Case::Lower),
_ => return None,
};
Some(Letter::new((char_value as u32 - start) as u8, case))
}
///Returns the `Letter` corresponding to a given byte, or `None` if the
///byte is out of the alphabetical ASCII range.
pub fn try_from_utf8(byte_value: u8) -> Option<Letter> {
let (start, case) = match byte_value {
0x41..=0x5A => (0x41, Case::Upper),
0x61..=0x7A => (0x61, Case::Lower),
_ => return None,
};
Some(Letter::new(byte_value - start, case))
}
///Returns the `char` corresponding to the alphabetical character specified
///by `self.value` and `self.case`. Returns `None` if this fails, but that
///could only happen if `self.value` where out of its correct range (0-25).
///Typically we can be sure that is not the case, so we can `unwrap` the
/// result, or use the `unsafe` `to_char_unchecked` if speed is
/// required.
pub fn try_to_char(&self) -> Option<char> {
char::from_u32(match self.case {
Case::Upper => self.value as u32 + 'A' as u32,
Case::Lower => self.value as u32 + 'a' as u32,
})
}
///# Safety
///This should be safe in all circumstances, since `from_u32_unchecked`
///could only fail if the value is out of ASCII range. So long as our
///range guarantee on `self.value` (0-25) is met, the corresponding `u32`
///will be in range.
pub unsafe fn to_char_unchecked(&self) -> char {
char::from_u32_unchecked(match self.case {
Case::Upper => self.value as u32 + 'A' as u32,
Case::Lower => self.value as u32 + 'a' as u32,
})
}
///Returns the (ASCII) byte corresponding to the character specified by
///`self.value` and `self.case`.
pub fn to_utf8(&self) -> u8 {
match self.case {
Case::Upper => self.value + 0x41,
Case::Lower => self.value + 0x61,
}
}
///Returns `Case::Lower` iff both inputs are lowercase, and `Case::Upper`
///otherwise. Used internally to decide which case to give the result of an
/// arithmetic operation on two `Letter`s.
fn combined_case(case1: Case, case2: Case) -> Case {
match (case1, case2) {
(Case::Lower, Case::Lower) => Case::Lower,
_ => Case::Upper,
}
}
}
///`Letters` add their values, wrapping around the alphabet if necessary.
impl Add<Letter> for Letter {
type Output = Self;
fn add(self, rhs: Self) -> Self {
Self::new(
self.value + rhs.value,
Letter::combined_case(self.case, rhs.case),
)
}
}
impl Add<i8> for Letter {
type Output = Self;
fn add(self, rhs: i8) -> Self {
Self::from_signed(self.value as i8 + rhs, self.case)
}
}
impl Sub<Letter> for Letter {
type Output = Self;
fn sub(self, rhs: Self) -> Self {
Self::from_signed(
self.value as i8 - rhs.value as i8,
Letter::combined_case(self.case, rhs.case),
)
}
}
impl Sub<i8> for Letter {
type Output = Self;
fn sub(self, rhs: i8) -> Self {
Self::from_signed(self.value as i8 - rhs, self.case)
}
}
impl PartialEq for Letter {
fn eq(&self, other: &Self) -> bool {
self.value == other.value
}
}
impl Eq for Letter {}
impl Ord for Letter {
fn cmp(&self, other: &Self) -> Ordering {
self.value.cmp(&other.value)
}
}
impl PartialOrd for Letter {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Display for Letter {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.try_to_char().ok_or(fmt::Error)?)
}
}
#[derive(Clone, Debug, PartialEq)]
///Newtype over a `Vec<Letter>`. Allows conversion to and from a UTF-8 string,
///and allows elementwise addition and other operations.
pub struct Alphabetic(Vec<Letter>);
impl Alphabetic {
pub fn new(vec: Vec<Letter>) -> Alphabetic {
Alphabetic(vec)
}
///Returns an `Alphabetic` from the given string, but returns `None` if the
/// string contains any non-alphabetic characters.
pub fn try_from_str(string: &str) -> Option<Alphabetic> {
let letters: Option<Vec<Letter>> = string.bytes().map(Letter::try_from_utf8).collect();
Some(Alphabetic::new(letters?))
}
///Returns an `Alphabetic` from the given string. Unlike `try_from_str`,
/// this function will simply ignore any characters which it cannot
/// convert, rather than returning `None`.
pub fn from_str_filtered(string: &str) -> Alphabetic {
Alphabetic::new(
string
.bytes()
.filter(|x| x.is_ascii_alphabetic())
.map(|x| Letter::try_from_utf8(x).unwrap())
.collect(),
)
}
///Applies `func` to each pair of values from `self` and `other`,
/// collecting the results into a new `Alphabetic`. If it reaches the
/// end of one of the strings, it will simply dump the remainder of the
/// longer string into the output; therefore, the output is always the
/// same length as the longer of the two strings.
pub fn pairwise_map(
&self,
other: &Self,
func: Box<dyn Fn(Letter, Letter) -> Letter>,
) -> Alphabetic {
let mut buf: Vec<Letter> = Vec::with_capacity(cmp::max(self.len(), other.len()));
let mut self_iter = self.iter();
let mut other_iter = other.iter();
loop {
match (self_iter.next(), other_iter.next()) {
(Some(sval), Some(oval)) => buf.push(func(*sval, *oval)),
(Some(sval), None) => {
buf.push(*sval);
buf.extend(self_iter);
break;
}
(None, Some(oval)) => {
buf.push(*oval);
buf.extend(other_iter);
break;
}
(None, None) => break,
}
}
Alphabetic::new(buf)
}
//exposed functions from the inner vec
pub fn len(&self) -> usize {
self.0.len()
}
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
pub fn iter(&self) -> std::slice::Iter<Letter> {
self.0.iter()
}
}
impl Display for Alphabetic {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", {
let chars = String::from_utf8(self.iter().map(Letter::to_utf8).collect());
chars.map_err(|_e| fmt::Error)?
})
}
}
//copy-paste boilerplate land
///Addition and subtraction on `Alphabetic`s works by adding/subtracting each
/// pair of `Letter`s, until we reach the end of either string, at which point
/// the remainder of the longer string will be appended.
impl Add<Alphabetic> for Alphabetic {
type Output = Self;
fn add(self, other: Self) -> Self {
self.pairwise_map(&other, Box::new(|x, y| x + y))
}
}
impl Add<Letter> for Alphabetic {
type Output = Self;
fn add(self, other: Letter) -> Self {
Alphabetic::new(self.iter().map(|x| *x + other).collect())
}
}
impl Add<i8> for Alphabetic {
type Output = Self;
fn add(self, other: i8) -> Self {
Alphabetic::new(self.iter().map(|x| *x + other).collect())
}
}
impl Sub<Alphabetic> for Alphabetic {
type Output = Self;
fn sub(self, other: Self) -> Self {
self.pairwise_map(&other, Box::new(|x, y| x - y))
}
}
impl Sub<Letter> for Alphabetic {
type Output = Self;
fn sub(self, other: Letter) -> Self {
Alphabetic::new(self.iter().map(|x| *x - other).collect())
}
}
impl Sub<i8> for Alphabetic {
type Output = Self;
fn sub(self, other: i8) -> Self {
Alphabetic::new(self.iter().map(|x| *x - other).collect())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_char_display() {
let mut letter = Letter::try_from_char('U').unwrap();
//display property works properly
assert_eq!(format!("{}", letter), "U");
letter = Letter::new(6, Case::Lower);
//initialising letters from their values works properly
assert_eq!(format!("{}", letter), "g");
}
#[test]
fn test_char_operators() {
let letter1 = Letter::new(8, Case::Lower);
let letter2 = Letter::from_signed(-16, Case::Lower);
assert_eq!(format!("{}", letter1 + letter2), "s");
assert_eq!(format!("{}", letter1 - letter2), "y");
assert!(letter2 > letter1);
assert!(letter2 != letter1);
}
#[test]
fn test_alphabetic_display() {
let alpha = Alphabetic::try_from_str("hello").unwrap();
//display property works properly
assert_eq!(format!("{}", alpha), "hello");
let beta = Alphabetic::try_from_str("helloり");
//try_from_str correctly does not accept non-alphabetic chars
assert_eq!(beta, None);
}
#[test]
fn test_alphabetic_addition() {
let alpha = Alphabetic::try_from_str("hello").unwrap();
let beta = Alphabetic::try_from_str("bbbbb").unwrap();
assert_eq!((alpha + beta).to_string(), "ifmmp");
let long = Alphabetic::try_from_str("longabcdefgh").unwrap();
let short = Alphabetic::try_from_str("short").unwrap();
//strings of different lengths can be added, commutatively
assert_eq!((long.clone() + short.clone()).to_string(), "dvbxtbcdefgh");
assert_eq!((short.clone() + long.clone()).to_string(), "dvbxtbcdefgh");
//letter can be added to alphabetic
assert_eq!(
(Alphabetic::try_from_str("bbbbbb").unwrap() + Letter::try_from_char('b').unwrap())
.to_string(),
"cccccc"
);
}
#[test]
fn test_empty_values() {
let a = Alphabetic::try_from_str("").unwrap();
let b = Alphabetic::from_str_filtered("");
let c = Alphabetic::new(vec![]);
assert_eq!(a.to_string(), "");
assert_eq!(b.to_string(), "");
assert_eq!(c.to_string(), "");
}
}
frequency.rs
///Provides utilities relating to frequency analysis, to be used by cipher
/// modules.
use crate::alphabetic::{self, Alphabetic, Case, Letter};
//https://en.wikipedia.org/wiki/Letter_frequency
//relative frequencies of letters in the english language, in alphabet order
pub const ENGLISH_FREQUENCIES: [f64; alphabetic::ALPHABET_SIZE] = [
0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153,
0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056,
0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074,
];
///Returns a `Vec` of relative frequencies of each `Letter` in the string.
pub fn frequencies(string: &Alphabetic) -> Vec<f64> {
let mut counts = vec![0usize; alphabetic::ALPHABET_SIZE];
string.iter().for_each(|x| {
counts[x.value as usize] += 1;
});
let sum = counts.iter().sum::<usize>();
if sum == 0 {
return vec![0f64; alphabetic::ALPHABET_SIZE];
}
counts.into_iter().map(|x| x as f64 / sum as f64).collect()
}
///Returns the `Letter` which occurs most frequently in the given string.
///# Panics
///There are 2 `unwrap`s in this function. One of them
/// unwraps the result of a `std::slice::Iter::max_by()`,
/// which yields `None` only when the iter is empty Since we
/// use the constant iter `(0..26)`, this is not a concern.
/// The other unwrap is on the result of an
/// `f64::partial_cmp()`, which would fail if one of the
/// `f64`s is an unusual value, like `NaN`. We obtain these
/// values from division and check for division by zero, so
/// there *should* be no way for this panic to occur.
pub fn most_frequent_letter(string: &Alphabetic) -> Letter {
let freqs = frequencies(string);
Letter::new(
(0..26)
.max_by(|x, y| freqs[*x].partial_cmp(&freqs[*y]).unwrap())
.unwrap() as u8,
Case::Lower,
)
}
///Returns a `Vec` containing the `Letters` representing `a` through `z`, in
/// order from most frequent to least frequent in the given string.
pub fn letters_by_frequency(string: &Alphabetic) -> Vec<Letter> {
let freqs = frequencies(string);
let mut indices: Vec<usize> = (0..26).collect();
indices.sort_by(|x, y| freqs[*y].partial_cmp(&freqs[*x]).unwrap());
indices
.into_iter()
.map(|x| Letter::new(x as u8, Case::Lower))
.collect()
}
///Returns the mean squared difference between two `f64` slices. The mean
/// squared difference is only defined on two slices of the same length (if the
/// slices are not the same length, this function returns `None`). It is defined
/// as the sum of the squares of the differences between each pair of items (one
/// from each slice), divided by the length of the slices.
pub fn mean_squared_difference(freqs1: &[f64], freqs2: &[f64]) -> Option<f64> {
let length = match (freqs1.len(), freqs2.len()) {
(0, _) | (_, 0) => {
return None;
}
(x, y) if x == y => x,
_ => return None,
};
let mut sum = 0f64;
for i in 0..length {
sum += (freqs1[i] - freqs2[i]).powi(2)
}
Some(sum)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_frequency() {
let string = Alphabetic::try_from_str("hello").unwrap();
assert_eq!(
most_frequent_letter(&string),
Letter::try_from_char('l').unwrap()
);
let freqs: Vec<f64> = vec![
0.0, 0.0, 0.0, 0.0, 0.2, 0.0, 0.0, 0.2, 0.0, 0.0, 0.0, 0.4, 0.0, 0.0, 0.2, 0.0, 0.0,
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
];
assert_eq!(frequencies(&string), freqs);
let letters = letters_by_frequency(&string);
assert_eq!(letters[0], Letter::try_from_char('l').unwrap());
assert_eq!(letters[1], Letter::try_from_char('e').unwrap());
assert_eq!(letters[2], Letter::try_from_char('h').unwrap());
assert_eq!(letters[3], Letter::try_from_char('o').unwrap());
}
}
caesar.rs
///Provides functions for encrypting and cracking Caesar ciphers.
use crate::{
alphabetic::{self, Alphabetic, Letter},
frequency::{frequencies, mean_squared_difference, most_frequent_letter, ENGLISH_FREQUENCIES},
};
///Shift the given string by the given number of places.
pub fn shift(string: &Alphabetic, num_places: i8) -> Alphabetic {
string.clone() + num_places
}
///Iterator over all of the possible shifts of a given string.
pub struct GenShifts(Alphabetic, i8);
impl GenShifts {
fn new(string: Alphabetic) -> GenShifts {
GenShifts(string, 0)
}
}
impl Iterator for GenShifts {
type Item = Alphabetic;
fn next(&mut self) -> Option<Self::Item> {
if self.1 == alphabetic::ALPHABET_SIZE as i8 {
return None;
}
self.1 += 1;
Some(shift(&self.0, self.1 - 1))
}
}
pub fn gen_shifts(string: Alphabetic) -> GenShifts {
GenShifts::new(string)
}
///Crack an encrypted string by shifting the string such
/// that the most common character therein is mapped to 'e'
/// (the most common letter in English)
pub fn crack_match_maxima(string: &Alphabetic) -> Alphabetic {
const MOST_FREQUENT_ENGLISH: Letter = Letter::try_from_char('e').unwrap();
string.clone() - most_frequent_letter(&string) + MOST_FREQUENT_ENGLISH
}
///Crack an encrypted string by choosing the shift which
/// minimises the MSE (mean squared error) between the
/// observed letter frequencies and the expected letter
/// frequencies (based on a large sample of English text)
pub fn crack_minimise_mse(string: &Alphabetic) -> Alphabetic {
gen_shifts(string.clone())
.min_by(|x, y| {
let mse = |x| mean_squared_difference(&frequencies(x), &ENGLISH_FREQUENCIES).unwrap();
mse(x).partial_cmp(&mse(y)).unwrap()
})
.unwrap()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_shift() {
assert_eq!(
shift(&Alphabetic::try_from_str("abcdef").unwrap(), 1).to_string(),
"bcdefg"
);
let mut shifts = gen_shifts(Alphabetic::try_from_str("abcdef").unwrap());
assert_eq!(shifts.next().unwrap().to_string(), "abcdef");
assert_eq!(shifts.next().unwrap().to_string(), "bcdefg");
assert_eq!(shifts.next().unwrap().to_string(), "cdefgh");
assert_eq!(shifts.next().unwrap().to_string(), "defghi");
}
#[test]
fn test_crack() {
let original = Alphabetic::from_str_filtered(
"If it were done when 'tis done, then 'twere well
It were done quickly: if the assassination
Could trammel up the consequence, and catch
With his surcease success; that but this blow
Might be the be-all and the end-all here,
But here, upon this bank and shoal of time,
We'ld jump the life to come. But in these cases
We still have judgment here; that we but teach
Bloody instructions, which, being taught, return
To plague the inventor: this even-handed justice
Commends the ingredients of our poison'd chalice
To our own lips. He's here in double trust;
First, as I am his kinsman and his subject,
Strong both against the deed; then, as his host,
Who should against his murderer shut the door,
Not bear the knife myself. Besides, this Duncan
Hath borne his faculties so meek, hath been
So clear in his great office, that his virtues
Will plead like angels, trumpet-tongued, against
The deep damnation of his taking-off;
And pity, like a naked new-born babe,
Striding the blast, or heaven's cherubim, horsed
Upon the sightless couriers of the air,
Shall blow the horrid deed in every eye,
That tears shall drown the wind. I have no spur
To prick the sides of my intent, but only
Vaulting ambition, which o'erleaps itself
And falls on the other.",
);
let shifted = shift(&original, 6);
assert_eq!(crack_match_maxima(&shifted), original);
assert_eq!(crack_minimise_mse(&shifted), original);
}
}
