lcg_tools/
lib.rs

1//! I'm putting all the neat LCG utilities I use in this library so i can stop copy/pasting python functions from old writeups every time i have to break an lcg for a CTF.
2//!
3//! Currently it can solve an LCG forward and backwards and derive parameters when provided a collection of values
4
5#![forbid(unsafe_code)]
6#![deny(
7missing_debug_implementations,
8missing_docs,
9trivial_casts,
10trivial_numeric_casts,
11unused_extern_crates,
12unused_import_braces,
13unused_qualifications,
14warnings
15)]
16
17use itertools::izip;
18use num::Integer;
19use num_bigint::{BigInt, ToBigInt};
20
21/// Rust's modulo operator is really remainder and not modular arithmetic so i have this
22fn modulo(a: &BigInt, m: &BigInt) -> BigInt {
23    ((a % m) + m) % m
24}
25
26fn modinv(a: &BigInt, m: &BigInt) -> Option<BigInt> {
27    let egcd = std::cmp::max(a, m).extended_gcd(&std::cmp::min(a.clone(), m.clone()));
28    if egcd.gcd != num::one() {
29        None
30    } else {
31        Some(modulo(&egcd.y, m))
32    }
33}
34
35/// Represents a linear congruential generator which can calculate both forwards and backwards
36#[derive(Debug, Eq, PartialEq)]
37pub struct LCG {
38    /// Seed
39    pub state: BigInt,
40    /// Multiplier
41    pub a: BigInt,
42    /// Increment
43    pub c: BigInt,
44    /// Modulus
45    pub m: BigInt,
46}
47
48/// Tries to derive LCG parameters based on known values
49///
50/// This is probabilistic and may be wrong, especially for low number of values
51///
52/// [https://tailcall.net/blog/cracking-randomness-lcgs/](https://tailcall.net/blog/cracking-randomness-lcgs/)
53pub fn crack_lcg(values: &[isize]) -> Option<LCG> {
54    // not sure how this can be made generic across integral types
55    // main hangup is the primitive 0isize in the fold for the modulus
56    // because can't add isize and impl Integer + ops::Add
57    // searched around and didn't find anything so you need to pass variables in as isize until i can fix that
58    if values.len() < 3 {
59        return None;
60    }
61    let diffs = izip!(values, values.iter().skip(1))
62        .map(|(a, b)| b - a)
63        .collect::<Vec<isize>>();
64    let zeroes = izip!(&diffs, (&diffs).iter().skip(1), (&diffs).iter().skip(2))
65        .map(|(a, b, c)| c * a - b * b)
66        .collect::<Vec<_>>();
67    let modulus = zeroes
68        .iter()
69        .fold(0isize, |sum, val| sum.gcd(val))
70        .to_bigint()?;
71
72    let multiplier = modulo(
73        &((values[2] - values[1]).to_bigint()?
74            * modinv(
75                &(&values[1].to_bigint()? - &values[0].to_bigint()?),
76                &modulus,
77            )?),
78        &modulus,
79    );
80
81    let increment = modulo(&(values[1] - values[0] * &multiplier), &modulus);
82    Some(LCG {
83        state: values.last()?.to_bigint()?,
84        m: modulus,
85        a: multiplier,
86        c: increment,
87    })
88}
89
90impl Iterator for LCG {
91    type Item = BigInt;
92
93    fn next(&mut self) -> Option<BigInt> {
94        Some(self.rand())
95    }
96}
97
98impl LCG {
99    /// Calculate the next value of the LCG
100    ///
101    /// `state * a + c % m`
102    pub fn rand(&mut self) -> BigInt {
103        self.state = modulo(&(&self.state * (&self.a) + (&self.c)), &self.m);
104        self.state.clone()
105    }
106
107    /// Calculate the previous value of the LCG
108    ///
109    /// `modinv(a,m) * (state - c) % m`
110    ///
111    /// relies on modinv(a,m) existing (aka a and m must be coprime) and will return None otherwise
112    pub fn prev(&mut self) -> Option<BigInt> {
113        self.state = modulo(
114            &(modinv(&self.a, &self.m)? * (&self.state - (&self.c))),
115            &self.m,
116        );
117        Some(self.state.clone())
118    }
119}
120
121#[cfg(test)]
122mod tests {
123    use crate::{crack_lcg, LCG};
124    use num::ToPrimitive;
125    use num_bigint::ToBigInt;
126
127    #[test]
128    fn it_generates_numbers_correctly_forward_and_backwards() {
129        let mut rand = LCG {
130            state: 32760.to_bigint().unwrap(),
131            a: 5039.to_bigint().unwrap(),
132            c: 76581.to_bigint().unwrap(),
133            m: 479001599.to_bigint().unwrap(),
134        };
135
136        let mut forward = (&mut rand).take(10).collect::<Vec<_>>();
137
138        assert_eq!(
139            forward,
140            vec![
141                165154221.to_bigint().unwrap(),
142                186418737.to_bigint().unwrap(),
143                41956685.to_bigint().unwrap(),
144                180107137.to_bigint().unwrap(),
145                330911418.to_bigint().unwrap(),
146                58145764.to_bigint().unwrap(),
147                326604388.to_bigint().unwrap(),
148                389095148.to_bigint().unwrap(),
149                96982646.to_bigint().unwrap(),
150                113998795.to_bigint().unwrap()
151            ]
152        );
153        forward.reverse();
154        rand.rand();
155        assert_eq!(
156            (0..10).filter_map(|_| rand.prev()).collect::<Vec<_>>(),
157            forward
158        );
159    }
160
161    #[test]
162    fn it_cracks_lcg_correctly() {
163        let mut rand = LCG {
164            state: 32760.to_bigint().unwrap(),
165            a: 5039.to_bigint().unwrap(),
166            c: 0.to_bigint().unwrap(),
167            m: 479001599.to_bigint().unwrap(),
168        };
169
170        let cracked_lcg = crack_lcg(
171            &(&mut rand)
172                .take(10)
173                .map(|x| x.to_isize().unwrap())
174                .collect::<Vec<_>>(),
175        )
176        .unwrap();
177        assert_eq!(rand, cracked_lcg);
178    }
179}
lcg_tools/lib.rs

lcg_tools/
lib.rs
