aes-elk 0.1.0

ELK (Encrypted LFSR Keystream) mode of operation for block ciphers
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

//! Search tool for primitive ELK polynomials.
//!
//! Requirest instealled SageMath.
//!
//! https://doc.sagemath.org/html/en/installation/index.html

use std::process::Command;

const N: usize = 128;

fn is_prime(num: usize) -> bool {
    if num < 2 { return false; }
    for i in 2..=(num as f64).sqrt() as usize {
        if num.is_multiple_of(i) { return false; }
    }
    true
}

fn check_distinct_differences(exponents: &[usize; 9]) -> bool {
    let mut seen = [false; N + 1];
    
    for i in 0..9 {
        for j in (i + 1)..9 {
            let diff = exponents[j].abs_diff(exponents[i]);
            if seen[diff] {
                return false; 
            }
            seen[diff] = true;
        }
    }
    true
}

/// Returns `true` if the primitive polynomial is found, halting the search.
fn find_candidates(
    buckets: &Vec<Vec<usize>>, 
    current_idx: usize, 
    current_exponents: &mut [usize; 9]
) -> bool {
    // Base Case: We picked 1 prime from all 7 buckets
    if current_idx == 8 {
        if check_distinct_differences(current_exponents) {
            
            // Format the candidate string for SageMath
            let candidate_str = format!("x^{} + x^{} + x^{} + x^{} + x^{} + x^{} + x^{} + x^{} + 1", 
                current_exponents[8], current_exponents[7], current_exponents[6], 
                current_exponents[5], current_exponents[4], current_exponents[3], 
                current_exponents[2], current_exponents[1]
            );
            
            println!("Testing candidate: {}", candidate_str);

            // Construct the SageMath python script
            let sage_script = format!(
                "R.<x> = GF(2)[]\nP = {}\nif P.is_primitive():\n    print('SUCCESS')\nelse:\n    print('FAILED')",
                candidate_str
            );

            // Execute SageMath via the command line
            let output = Command::new("sage")
                .arg("-c")
                .arg(&sage_script)
                .output();

            match output {
                Ok(out) => {
                    let out_str = String::from_utf8_lossy(&out.stdout);
                    if out_str.contains("SUCCESS") {
                        println!("\n=======================================================");
                        println!("SUCCESS! FOUND PRIMITIVE ELK POLYNOMIAL:");
                        println!("{}", candidate_str);
                        println!("=======================================================\n");
                        return true; // Stop the search!
                    }
                },
                Err(e) => {
                    eprintln!("\n[ERROR] Failed to execute SageMath. Is it installed and in your PATH?");
                    eprintln!("System Error: {}", e);
                    std::process::exit(1);
                }
            }
        }
        return false;
    }

    // Recursive Step
    for &prime in &buckets[current_idx - 1] {
        current_exponents[current_idx] = prime;
        // If the recursive call found the winner, bubble up the `true` to halt execution
        if find_candidates(buckets, current_idx + 1, current_exponents) {
            return true;
        }
    }
    
    false
}

fn main() {
    println!("Searching for ELK polynomial candidates for N = {}", N);
    
    // The paper specifies i = 1 to 7 for the interior taps
    let interval_size = N / 8;
    let mut buckets: Vec<Vec<usize>> = vec![Vec::new(); 7];

    for i in 1..=7 {
        // [ (n/8 * i), (n/8 * (i+1) - 1) ]
        let start = interval_size * i;
        let end = interval_size * (i + 1) - 1;
        
        for num in start..=end {
            if is_prime(num) {
                buckets[i - 1].push(num);
            }
        }
        // Print to verify we are matching the paper's bucket sizes
        println!("Bucket {} ({} to {}): {} primes", i, start, end, buckets[i-1].len());
    }

    // Exponents array: 
    // exponents[0] = 0 (the constant '1')
    // exponents[1..=7] = the interior taps (the i-th prime)
    // exponents[8] = N (the degree of the polynomial)
    let mut exponents = [0; 9];
    exponents[0] = 0;
    exponents[8] = N;

    println!("\nStarting search and primitivity testing...\n");

    let mut reversed_buckets = buckets.clone();
    reversed_buckets.reverse();
    
    let found = find_candidates(&reversed_buckets, 1, &mut exponents);
    
    if !found {
        println!("\nNo candidates found matching the specific prime distribution constraints.");
    }
}