Skip to content

Instantly share code, notes, and snippets.

@kiwiyou

kiwiyou/encrypt.rs

Created December 11, 2025 01:30
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kiwiyou/3a5e56811c77aa9bea2a31ca6c24d165 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kiwiyou/3a5e56811c77aa9bea2a31ca6c24d165 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
encrypt.rs
pub struct Feistel {
pub bits: u32,
pub rounds: u32,
salt: u64,
key: u64,
half_bits: u32,
half_mask: u64,
}
impl Feistel {
pub fn new(bits: u32, rounds: u32, salt: u32, key: u32) -> Self {
assert!((2..=62).contains(&bits));
assert!(bits % 2 == 0);
assert!((1..=32).contains(&rounds));
let half_bits = bits / 2;
assert!((0..(1 << half_bits)).contains(&salt));
assert!((0..(1 << half_bits)).contains(&key));
Self {
bits,
rounds,
salt: salt as u64,
key: key as u64,
half_bits,
half_mask: (1u64 << half_bits) - 1,
}
}
pub fn encrypt(&self, input: u64) -> u64 {
let mut upper_half = input >> self.half_bits;
assert!(upper_half <= self.half_mask);
let mut lower_half = input & self.half_mask;
for _ in 0..self.rounds {
(upper_half, lower_half) = (
lower_half,
upper_half ^ ((((lower_half ^ self.salt) * self.salt) ^ self.key) & self.half_mask),
);
}
// swapped
(lower_half << self.half_bits) | upper_half
}
}
Raw
lib.rs
pub mod encrypt;
pub mod solver;
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn bits_4_round_1() {
let feistel = encrypt::Feistel::new(4, 1, 1, 2);
let mut problem = solver::FeistelProblem::new(feistel.bits, feistel.rounds);
for i in 0..1 {
problem.add_next_cryptotext(feistel.encrypt(7 + i));
}
let solution = problem.solve();
eprintln!("{solution:#?}");
let reconstructed =
encrypt::Feistel::new(feistel.bits, feistel.rounds, solution.salt, solution.key);
for (i, &cryptotext) in problem.cryptotexts.iter().enumerate() {
assert_eq!(
reconstructed.encrypt(solution.initial + i as u64),
cryptotext
);
}
}
#[test]
fn bits_4_round_32() {
let feistel = encrypt::Feistel::new(4, 32, 1, 2);
let mut problem = solver::FeistelProblem::new(feistel.bits, feistel.rounds);
for i in 0..1 {
problem.add_next_cryptotext(feistel.encrypt(7 + i));
}
let solution = problem.solve();
eprintln!("{solution:#?}");
let reconstructed =
encrypt::Feistel::new(feistel.bits, feistel.rounds, solution.salt, solution.key);
for (i, &cryptotext) in problem.cryptotexts.iter().enumerate() {
assert_eq!(
reconstructed.encrypt(solution.initial + i as u64),
cryptotext
);
}
}
#[test]
fn bits_62_round_1() {
let feistel = encrypt::Feistel::new(62, 1, 1182378, 237213);
let mut problem = solver::FeistelProblem::new(feistel.bits, feistel.rounds);
for i in 0..1 {
problem.add_next_cryptotext(feistel.encrypt(1823621 + i));
}
let solution = problem.solve();
eprintln!("{solution:#?}");
let reconstructed =
encrypt::Feistel::new(feistel.bits, feistel.rounds, solution.salt, solution.key);
for (i, &cryptotext) in problem.cryptotexts.iter().enumerate() {
assert_eq!(
reconstructed.encrypt(solution.initial + i as u64),
cryptotext
);
}
}
#[test]
fn bits_62_round_32_sample_1() {
let feistel = encrypt::Feistel::new(62, 32, 1182378, 237213);
let mut problem = solver::FeistelProblem::new(feistel.bits, feistel.rounds);
for i in 0..1 {
problem.add_next_cryptotext(feistel.encrypt(1823621 + i));
}
let solution = problem.solve();
eprintln!("{solution:#?}");
let reconstructed =
encrypt::Feistel::new(feistel.bits, feistel.rounds, solution.salt, solution.key);
for (i, &cryptotext) in problem.cryptotexts.iter().enumerate() {
assert_eq!(
reconstructed.encrypt(solution.initial + i as u64),
cryptotext
);
}
}
#[test]
fn bits_62_round_32_sample_2() {
let feistel = encrypt::Feistel::new(62, 32, 1182378, 237213);
let mut problem = solver::FeistelProblem::new(feistel.bits, feistel.rounds);
for i in 0..2 {
problem.add_next_cryptotext(feistel.encrypt(1823621 + i));
}
let solution = problem.solve();
eprintln!("{solution:#?}");
let reconstructed =
encrypt::Feistel::new(feistel.bits, feistel.rounds, solution.salt, solution.key);
for (i, &cryptotext) in problem.cryptotexts.iter().enumerate() {
assert_eq!(
reconstructed.encrypt(solution.initial + i as u64),
cryptotext
);
}
}
#[test]
fn bits_62_round_16_sample_10() {
let feistel = encrypt::Feistel::new(62, 16, 1182378, 237213);
let mut problem = solver::FeistelProblem::new(feistel.bits, feistel.rounds);
for i in 0..10 {
problem.add_next_cryptotext(feistel.encrypt(1823621 + i));
}
let solution = problem.solve();
eprintln!("{solution:#?}");
let reconstructed =
encrypt::Feistel::new(feistel.bits, feistel.rounds, solution.salt, solution.key);
for (i, &cryptotext) in problem.cryptotexts.iter().enumerate() {
assert_eq!(
reconstructed.encrypt(solution.initial + i as u64),
cryptotext
);
}
}
}
Raw
solver.rs
use z3::{Solver, ast};
pub struct FeistelProblem {
pub bits: u32,
pub rounds: u32,
half_bits: u32,
half_mask: u64,
pub cryptotexts: Vec<u64>,
}
#[derive(Debug)]
pub struct FeistelSolution {
pub salt: u32,
pub key: u32,
pub initial: u64,
}
impl FeistelProblem {
/// * `bits`: even numbers ∈ [2, 62]
/// * `rounds`: [1, 32]
pub fn new(bits: u32, rounds: u32) -> Self {
assert!((2..=62).contains(&bits));
assert!(bits % 2 == 0);
assert!((1..=32).contains(&rounds));
let half_bits = bits / 2;
Self {
bits,
rounds,
half_bits,
half_mask: (1u64 << half_bits) - 1,
cryptotexts: vec![],
}
}
pub fn add_next_cryptotext(&mut self, cryptotext: u64) {
self.cryptotexts.push(cryptotext);
}
pub fn solve(&self) -> FeistelSolution {
let salt = ast::BV::fresh_const("salt", self.half_bits);
let key = ast::BV::fresh_const("key", self.half_bits);
let salt_wide = salt.zero_ext(self.bits);
let initial = ast::BV::fresh_const("initial", self.bits);
let solver = Solver::new();
let mut plaintext = initial.clone();
for &cryptotext in &self.cryptotexts {
let mut upper_half = plaintext.extract(self.bits - 1, self.half_bits);
let mut lower_half = plaintext.extract(self.half_bits - 1, 0);
for _ in 0..self.rounds {
(upper_half, lower_half) = (
lower_half.clone(),
lower_half
.bvxor(&salt)
.zero_ext(self.bits)
.bvmul(&salt_wide)
.extract(self.half_bits - 1, 0)
.bvxor(&key)
.bvxor(&upper_half),
);
}
solver.assert(lower_half.eq(cryptotext >> self.half_bits));
solver.assert(upper_half.eq(cryptotext & self.half_mask));
plaintext = plaintext.bvadd(1);
}
let [salt, key, initial] = solver
.solutions([salt, key, initial], false)
.next()
.unwrap();
FeistelSolution {
salt: salt.as_u64().unwrap() as u32,
key: key.as_u64().unwrap() as u32,
initial: initial.as_u64().unwrap(),
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment