rsacracker 0.9.1

Powerful RSA cracker for CTFs. Supports RSA, X509, OPENSSH, PKCS#12, PKCS#7, and CSR 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
103
104
105
106
107
108
109
110
111
112

use std::str::FromStr;

use indicatif::ProgressBar;
use rug::Integer;

use crate::{key::PrivateKey, Attack, AttackSpeed, Error, Parameters, Solution};

/// Known factors attack
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct KnownFactorsAttack;

impl Attack for KnownFactorsAttack {
    fn name(&self) -> &'static str {
        "known_factors"
    }

    fn speed(&self) -> AttackSpeed {
        AttackSpeed::Fast
    }

    fn run(&self, params: &Parameters, _pb: Option<&ProgressBar>) -> Result<Solution, Error> {
        let e = &params.e;
        let n = params.n.as_ref().ok_or(Error::MissingParameters)?;

        // https://en.wikipedia.org/wiki/RSA_numbers
        let rsa_numbers_challenge_factors = [
            "37975227936943673922808872755445627854565536638199", // RSA-100
            "40094690950920881030683735292761468389214899724061",
            "6122421090493547576937037317561418841225758554253106999", // RSA-110
            "5846418214406154678836553182979162384198610505601062333",
            "327414555693498015751146303749141488063642403240171463406883", // RSA-120
            "693342667110830181197325401899700641361965863127336680673013",
            "3490529510847650949147849619903898133417764638493387843990820577", // RSA-129
            "32769132993266709549961988190834461413177642967992942539798288533",
            "39685999459597454290161126162883786067576449112810064832555157243", // RSA-130
            "45534498646735972188403686897274408864356301263205069600999044599",
            "3398717423028438554530123627613875835633986495969597423490929302771479", // RSA-140
            "6264200187401285096151654948264442219302037178623509019111660653946049",
            "348009867102283695483970451047593424831012817350385456889559637548278410717", // RSA-150
            "445647744903640741533241125787086176005442536297766153493419724532460296199",
            "102639592829741105772054196573991675900716567808038066803341933521790711307779", // RSA-155
            "106603488380168454820927220360012878679207958575989291522270608237193062808643",
            "45427892858481394071686190649738831656137145778469793250959984709250004157335359", // RSA-160
            "47388090603832016196633832303788951973268922921040957944741354648812028493909367",
            "3586420730428501486799804587268520423291459681059978161140231860633948450858040593963", // RSA-170
            "7267029064107019078863797763923946264136137803856996670313708936002281582249587494493",
            "398075086424064937397125500550386491199064362342526708406385189575946388957261768583317", // RSA-576
            "472772146107435302536223071973048224632914695302097116459852171130520711256363590397527",
            "400780082329750877952581339104100572526829317815807176564882178998497572771950624613470377", // RSA-180
            "476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833",
            "31711952576901527094851712897404759298051473160294503277847619278327936427981256542415724309619", // RSA-190
            "60152600204445616415876416855266761832435433594718110725997638280836157040460481625355619404899",
            "1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579", // RSA-640
            "1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571",
            "3532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349", // RSA-200
            "7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467",
            "435958568325940791799951965387214406385470910265220196318705482144524085345275999740244625255428455944579" , // RSA-210
            "562545761726884103756277007304447481743876944007510545104946851094548396577479473472146228550799322939273",
            "9091213529597818878440658302600437485892608310328358720428512168960411528640933367824950788367956756806141", // RSA-704
            "8143859259110045265727809126284429335877899002167627883200914172429324360133004116702003240828777970252499",
            "68636564122675662743823714992884378001308422399791648446212449933215410614414642667938213644208420192054999687", // RSA-220
            "32929074394863498120493015492129352919164551965362339524626860511692903493094652463337824866390738191765712603",
            "4528450358010492026612439739120166758911246047493700040073956759261590397250033699357694507193523000343088601688589", // RSA-230
            "3968132623150957588532394439049887341769533966621957829426966084093049516953598120833228447171744337427374763106901",
            "29669093332083606603617799242426306347429462625218523944018571574194370194723262390744910112571804274494074452751891", // RSA-232
            "34038161751975634380066094984915214205471217607347231727351634132760507061748526506443144325148088881115083863017669",
            "33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489", // RSA-768
            "36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917",
            "509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517", // RSA-240
            "244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447",
            "64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367", // RSA-250
            "33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711",
        ].iter().map(|s| Integer::from_str(s).unwrap()).collect::<Vec<Integer>>();

        for factor in rsa_numbers_challenge_factors.iter() {
            let (q, rem) = n.clone().div_rem(factor.clone());
            if rem == Integer::ZERO {
                return Ok(Solution::new_pk(
                    self.name(),
                    PrivateKey::from_p_q(factor, q, e)?,
                ));
            }
        }
        Err(Error::NotFound)
    }
}

#[cfg(test)]
mod tests {
    use std::str::FromStr;

    use crate::{Attack, Parameters};

    use super::*;

    #[test]
    fn attack() {
        let p = Integer::from_str("29669093332083606603617799242426306347429462625218523944018571574194370194723262390744910112571804274494074452751891").unwrap();
        let q = Integer::from_str("33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711").unwrap();

        let params = Parameters {
            n: Some(p.clone() * &q),
            ..Default::default()
        };

        let solution = KnownFactorsAttack.run(&params, None).unwrap();
        let pk = solution.pk.unwrap();

        assert_eq!(pk.p(), p);
        assert_eq!(pk.q(), q);
    }
}