use zeroize::Zeroizing;
const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
const PREFIX: &str = "MN1";
const GROUPS: usize = 13;
const GROUP_LEN: usize = 5;
const SYMBOLS: usize = GROUPS * GROUP_LEN;
const POLY: u8 = 0b10_0101;
fn gmul(mut a: u8, mut b: u8) -> u8 {
let mut r = 0;
while b != 0 {
if b & 1 != 0 {
r ^= a;
}
b >>= 1;
a <<= 1;
if a & 0b10_0000 != 0 {
a ^= POLY;
}
}
r
}
const WEIGHTS: [u8; 4] = [2, 4, 8, 16];
fn check(i: usize, d: &[u8; 4]) -> u8 {
let mut c = i as u8;
for (w, v) in WEIGHTS.iter().zip(d) {
c ^= gmul(*w, *v);
}
c
}
pub fn encode(key: &[u8; 32]) -> Zeroizing<String> {
let syms = data_symbols(key);
let mut out = Zeroizing::new(String::with_capacity(
PREFIX.len() + GROUPS * (GROUP_LEN + 1),
));
out.push_str(PREFIX);
for i in 0..GROUPS {
let mut d = [0u8; 4];
d.copy_from_slice(&syms[4 * i..4 * i + 4]);
out.push('-');
for v in d {
out.push(ALPHABET[v as usize] as char);
}
out.push(ALPHABET[check(i, &d) as usize] as char);
}
out
}
fn data_symbols(key: &[u8; 32]) -> Zeroizing<[u8; 52]> {
let mut syms = Zeroizing::new([0u8; 52]);
for (k, sym) in syms.iter_mut().enumerate() {
let mut v = 0u8;
for b in 0..5 {
let bit = 5 * k + b;
let set = bit < 256 && key[bit / 8] & (0x80 >> (bit % 8)) != 0;
v = (v << 1) | u8::from(set);
}
*sym = v;
}
syms
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CodeError(pub String);
impl std::fmt::Display for CodeError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.0)
}
}
impl std::error::Error for CodeError {}
fn symbol(c: char) -> Option<u8> {
let c = match c.to_ascii_uppercase() {
'I' | 'L' => '1',
'O' => '0',
c => c,
};
ALPHABET
.iter()
.position(|&a| a as char == c)
.map(|p| p as u8)
}
pub fn looks_like_code(text: &str) -> bool {
let t: String = text.trim().chars().take(3).collect();
t.chars().count() == 3
&& t.chars().map(symbol).collect::<Option<Vec<_>>>() == Some(vec![20, 21, 1])
}
pub fn parse(text: &str) -> Result<Zeroizing<[u8; 32]>, CodeError> {
let typed: Zeroizing<String> =
Zeroizing::new(text.chars().filter(|c| !c.is_whitespace()).collect());
if !looks_like_code(&typed) {
return Err(CodeError(
"a recovery code starts with MN1 (this one doesn't, or it was made by a newer mnemo)"
.into(),
));
}
let body = typed[3..].trim_start_matches('-');
let mut values: Zeroizing<Vec<u8>> = Zeroizing::new(Vec::with_capacity(SYMBOLS));
for (pos, c) in body.chars().filter(|&c| c != '-').enumerate() {
match symbol(c) {
Some(v) => values.push(v),
None => {
return Err(CodeError(format!(
"{:?} isn't a recovery-code character (group {})",
c,
(pos / GROUP_LEN + 1).min(GROUPS)
)))
}
}
}
if values.len() != SYMBOLS {
return Err(CodeError(wrong_length(body, &values)));
}
let bad: Vec<usize> = (0..GROUPS)
.filter(|&i| !group_checks(i, &values[GROUP_LEN * i..GROUP_LEN * i + GROUP_LEN]))
.collect();
if !bad.is_empty() {
let names: Vec<String> = bad.iter().map(|i| (i + 1).to_string()).collect();
return Err(CodeError(match names.len() {
1 => format!(
"group {} doesn't check out; look for a typo there",
names[0]
),
_ => format!(
"groups {} don't check out; look for typos there",
names.join(", ")
),
}));
}
let last = values[GROUP_LEN * (GROUPS - 1) + 3];
if last != 0 && last != 16 {
return Err(CodeError(format!(
"group {GROUPS} doesn't check out (its fourth character must be 0 or G)"
)));
}
let mut key = Zeroizing::new([0u8; 32]);
let mut bit = 0usize;
for i in 0..GROUPS {
for &v in &values[GROUP_LEN * i..GROUP_LEN * i + 4] {
for b in (0..5).rev() {
if bit < 256 && (v >> b) & 1 == 1 {
key[bit / 8] |= 0x80 >> (bit % 8);
}
bit += 1;
}
}
}
Ok(key)
}
fn group_checks(i: usize, g: &[u8]) -> bool {
g.len() == GROUP_LEN && check(i, &[g[0], g[1], g[2], g[3]]) == g[4]
}
fn wrong_length(body: &str, values: &[u8]) -> String {
let count = format!(
"{} characters after {PREFIX}, {SYMBOLS} expected",
values.len()
);
let parts: Vec<&str> = body.split('-').filter(|p| !p.is_empty()).collect();
if parts.len() > 1 {
let odd: Vec<String> = parts
.iter()
.enumerate()
.filter(|(_, p)| p.chars().count() != GROUP_LEN)
.map(|(i, p)| format!("group {} has {}", i + 1, p.chars().count()))
.collect();
if !odd.is_empty() {
return format!("{count}: {}, {GROUP_LEN} expected", odd.join(", "));
}
}
let complete = values.len() / GROUP_LEN;
let first_bad = (0..complete.min(GROUPS))
.find(|&i| !group_checks(i, &values[GROUP_LEN * i..GROUP_LEN * i + GROUP_LEN]));
match first_bad {
Some(0) => format!("{count}; group 1 doesn't check out, so look there"),
Some(i) => format!(
"{count}; groups 1 to {i} check out and group {} doesn't, so look in group {} or \
the one before it",
i + 1,
i + 1
),
None => format!(
"{count}; every complete group checks out, so look in the last group ({})",
(complete + 1).min(GROUPS)
),
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_worked_example_encodes_as_the_note_shows() {
let key: [u8; 32] = std::array::from_fn(|i| i as u8);
assert_eq!(
encode(&key).as_str(),
"MN1-000GD-40R4X-0M300-E209K-185G3-R38ED-1W811-24GKZ-2GAH1-C5RR2-34D1B-P70XX-3RFGZ"
);
assert_eq!(*parse(&encode(&key)).unwrap(), key);
}
#[test]
fn group_one_of_the_example_checks_as_the_note_works_it() {
assert_eq!(gmul(16, 4), 10);
assert_eq!(gmul(8, 24), 30);
assert_eq!(check(1, &[4, 0, 24, 4]), 29);
assert_eq!(ALPHABET[29], b'X');
}
}