rsacracker 0.8.0

Powerful RSA cracker for CTFs. Supports RSA, X509, OPENSSH in PEM and DER formats.
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

use rug::{
    ops::{DivRounding, Pow},
    Integer,
};

pub fn rational_to_contfrac(x: &Integer, y: &Integer) -> Vec<Integer> {
    let a = x.clone().div_floor(y);

    if a.clone() * y == *x {
        vec![a]
    } else {
        let mut pquotients = rational_to_contfrac(y, &(x - a.clone() * y));
        pquotients.insert(0, a);
        pquotients
    }
}

pub fn contfrac_to_rational(frac: &[Integer]) -> (Integer, Integer) {
    if frac.is_empty() {
        (0.into(), 1.into())
    } else if frac.len() == 1 {
        (frac[0].clone(), 1.into())
    } else {
        let remainder = frac[1..frac.len()].to_vec();
        let (num, denom) = contfrac_to_rational(&remainder);
        (frac[0].clone() * num.clone() + denom, num)
    }
}

#[allow(dead_code)]
pub fn convergents_from_contfrac(frac: &[Integer]) -> Vec<(Integer, Integer)> {
    let mut convs = Vec::new();

    for i in 0..frac.len() {
        convs.push(contfrac_to_rational(&frac[0..i]));
    }
    convs
}

pub fn trivial_factorization_with_n_phi(n: &Integer, phi: &Integer) -> Option<(Integer, Integer)> {
    let m = n.clone() - phi.clone() + Integer::from(1);
    let m2n2 = m.clone().pow(2) - Integer::from(n << 2);

    if m2n2 > 0 {
        let (i, _) = m2n2.sqrt_rem(Integer::new());
        let roots: (Integer, Integer) = ((m.clone() - i.clone()) >> 1, (m + i) >> 1);

        if roots.0.clone() * roots.1.clone() == *n {
            return Some(roots);
        }
    }
    None
}

pub fn crt(residues: &[Integer], modulli: &[Integer]) -> Option<Integer> {
    let prod = modulli.iter().product::<Integer>();
    let mut sum = Integer::ZERO;

    for (residue, modulus) in residues.iter().zip(modulli) {
        let p = prod.clone() / modulus;
        sum += residue * Integer::from(p.invert_ref(modulus)?) * p
    }

    Some(sum % prod)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn chinese_remainder_theorem() {
        assert_eq!(
            crt(
                &[3.into(), 5.into(), 7.into()],
                &[2.into(), 3.into(), 1.into()]
            ),
            Some(Integer::from(5))
        );
        assert_eq!(
            crt(
                &[1.into(), 4.into(), 6.into()],
                &[3.into(), 5.into(), 7.into()]
            ),
            Some(Integer::from(34))
        );
        assert_eq!(
            crt(
                &[1.into(), 4.into(), 6.into()],
                &[1.into(), 2.into(), 0.into()]
            ),
            None
        );
        assert_eq!(
            crt(
                &[2.into(), 5.into(), 7.into()],
                &[6.into(), 9.into(), 15.into()]
            ),
            None
        );
    }
}