>>BACK TO MAIN CICADA 3301 2014 ARTICLE<<
DETAILS:
- Distributed approach using CADO-NFS v2.0
- Number Field Sieve (NFS) algorithm
Executive summary:
- Factorization of a 131 digit RSA modulus in ~9 hours, including disruptions.
- 3.5 hours of heavily parallelized computation (est. 87 CPU cores)
- 40 minutes spent investigating and eliminating bogus sieving results (broken clients)
- 4.5 hours unparallelized linear algebra (Amazon EC2 Xeon quad core, 8GB)
Detailed summary:
- 2014-01-06 20:22 (est.) Polynomial selection started
- 2014-01-06 21:22 Polynomial selection ended (best: MurphyE = 6.82e-11)
- 2014-01-06 21:38:41,752 Lattice Sieving: Starting
- 2014-01-07 00:05:43,563 Lattice Sieving: Reached target of 29000000 relations, now have 29007362
- 2014-01-07 00:46:49,369 Info:Filtering - Singleton removal: Have enough relations
- 2014-01-07 00:46:49,371 Info:Filtering - Merging: Starting
- 2014-01-07 00:51:16,940 Info:Linear Algebra: Starting
- 2014-01-07 05:24:05,567 Info:Square Root: Starting
- 2014-01-07 05:27:44,555 Info:Square Root: finished
- 2014-01-07 05:27:44,555 Info:Square Root: Factors: 97513779050322159297664671238670850085661086043266591739338007321 77506098606928780021829964781695212837195959082370473820509360759
2014-01-07 05:27:44,555 Debug:Square Root: Exit SqrtTask.run(sqrt)
2014-01-07 05:27:44,556 Info:Generate Factor Base: Total cpu/real time for makefb: 6.39/6.40458
2014-01-07 05:27:44,556 Info:Generate Free Relations: Total cpu/real time for freerel: 194.68/193.151
2014-01-07 05:27:44,556 Info:Lattice Sieving: Aggregate statistics:
2014-01-07 05:27:44,557 Info:Lattice Sieving: Total number of relations: 29007362
2014-01-07 05:27:44,557 Info:Lattice Sieving: Average J: 2020.6977172213888 for 1273010 special-q, max bucket fill: 0.763608
2014-01-07 05:27:44,557 Info:Lattice Sieving: Total CPU time: 878768.6999999997s
2014-01-07 05:27:44,557 Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 185.11/136.935
2014-01-07 05:27:44,557 Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 429.07/127.801
2014-01-07 05:27:44,557 Info:Filtering - Singleton removal: Total cpu/real time for purge: 610.26/424.892
2014-01-07 05:27:44,558 Info:Filtering - Merging: Total cpu/real time for merge: 215.06/229.408
2014-01-07 05:27:44,558 Info:Filtering - Merging: Total cpu/real time for replay: 43.01/37.4837
2014-01-07 05:27:44,558 Info:Linear Algebra: Total cpu/real time for bwc: 58021.2/16341.7
2014-01-07 05:27:44,558 Info:Linear Algebra: Aggregate statistics:
2014-01-07 05:27:44,558 Info:Linear Algebra: Krylov: CPU time 34471.22, COMM time 954.22
2014-01-07 05:27:44,559 Info:Linear Algebra: Lingen CPU time 1432.65
2014-01-07 05:27:44,559 Info:Linear Algebra: Mksol: CPU time 20060.39, COMM time 512.27
2014-01-07 05:27:44,559 Info:Quadratic Characters: Total cpu/real time for characters: 64.28/26.5294
2014-01-07 05:27:44,559 Info:Square Root: Total cpu/real time for sqrt: 220.05/217.513
2014-01-07 05:27:44,559 Info:HTTP server: Shutting down HTTP server
2014-01-07 05:27:44,667 Info:Complete Factorization: Total cpu/real time for everything: 938758/18361
Remarks
- Distributed CADO-NFS expects to run in a low-latency environment on a single operating system. We had to enable threading on the HTTP master server and patch clients to not fetch executables run from the master server
- There are zero safeguards against misbehaving or malicious clients. Polynomial selection suffered from clients consuming large amounts of work units (WUs) due to misbehavior (failed jobs due to incompatible executables retrieved from master server)
- Lattice sieving was shortly disrupted by server failure (operator error)
- 6/547 sets of sieving result data were corrupted (Python v3.3 incompatibility?) - these had to be manually removed and purged from the database
- Filtering, linear algebra and square root steps were performed on the master server
FEW LOGS:
GMT (timestamps)
[07:38] <mdzhb> so
[07:38] <mdzhb> here goes
[07:39] <mdzhb> PID28389 2014-01-07 05:27:44,557 Info:Lattice Sieving: Total CPU time: 878768.6999999997s
[07:39] <mdzhb> PID28389 2014-01-07 05:27:44,557 Info:Filtering - Singleton removal: Total cpu/real time for purge: 610.26/424.892
[07:39] <mdzhb> PID28389 2014-01-07 05:27:44,558 Info:Filtering - Merging: Total cpu/real time for replay: 43.01/37.4837
[07:39] <mdzhb> PID28389 2014-01-07 05:27:44,558 Info:Linear Algebra: Krylov: CPU time 34471.22, COMM time 954.22
[07:39] <mdzhb> PID28389 2014-01-07 05:27:44,559 Info:Linear Algebra: Mksol: CPU time 20060.39, COMM time 512.27
[07:39] <mdzhb> PID28389 2014-01-07 05:27:44,667 Info:Complete Factorization: Total cpu/real time for everything: 938758/18361
[07:39] <mdzhb> those are the stats
[07:39] <mdzhb> but those are boring
[07:39] <mdzhb> what we all came for
[07:39] <soulseekah> Those are sick
[07:39] <soulseekah> Lurker69: ready?
[07:39] <mdzhb> PID28389 2014-01-07 05:27:44,555 Info:Square Root: finished
[07:39] <cheetahburn> teh anticipation
[07:39] <mdzhb> PID28389 2014-01-07 05:27:44,555 Info:Square Root: Factors: 97513779050322159297664671238670850085661086043266591739338007321 77506098606928780021829964781695212837195959082370473820509360759
[07:39] <soulseekah> NICE!
[07:40] <mdzhb> sage: p = 97513779050322159297664671238670850085661086043266591739338007321
[07:40] <mdzhb> sage: q = 77506098606928780021829964781695212837195959082370473820509360759
[07:40] <mdzhb> sage: p.is_prime()
[07:40] <mdzhb> True
[07:40] <mdzhb> sage: q.is_prime()
[07:40] <mdzhb> True
[07:40] <mdzhb> sage: p*q
[07:40] <mancha> confirmed!
[07:40] <soulseekah> Thanks
[07:40] <mdzhb> 7557912574608535164426718292058021255641310207187633095795069445700059210248050757270234679993673844203148013173091173786572116639
[08:16] <nsh> mm_freak, the RSA n was finally factorized if you didn't hear
[08:17] <snappy> n is factorized!
[08:17] <nsh> http://cado-nfs.gforge.inria.fr/
[08:17] <nsh> was used
[08:17] <nsh> - http://uncovering-cicada.wikia.com/wiki/CICADA_3301_2014_PUZZLE
[08:17] <nsh> not sure how many participants as i was sleeping
[08:17] <nsh> but seemed to take about 8h or so
[08:18] <nsh> primes were about the same size:
[08:18] <nsh> sage: p = 97513779050322159297664671238670850085661086043266591739338007321
[08:18] <nsh> sage: q = 77506098606928780021829964781695212837195959082370473820509360759
[08:27] <cudos> nsh: i'm glad to hear that… it means that this cicada crap will finally stop
[08:28] <nsh> optimistic... :)
[08:28] <nsh> probably in for about a month of this
[89:29] <cudos> it's like a bored anonymous kid put up a boring crypto challenge and all the nerds go WOW! I SEE THE MATRIX!
[08:29] <nsh> if they learn a few things along the way, so much the better
[08:29] <nsh> beats television...
[08:29] <cudos> nsh: what did you learn?
[08:30] <nsh> some things about the applicability of various factoring algorithms
[08:30] <nsh> (thanks)
[08:30] <codos> nsh: you mean like: "ah, 430 bits, i'll go for NFS" ;)
[08:31] <cudos> this was a challenge in computing power, not knowledge
[08:31] <nsh> something like that
[08:31] <cudos> oh and how to compile ready-made programs ;)
[08:32] <cudos> anyway, i really expected more from this guy… i expected an interesting challenge that requires actual thinking
[08:33] <nsh> perhaps later maybe :)
[09:35] <cudos> no opportunity to join a secret wannabe-h4x0r-elite on that site though
[09:35] <cudos> so if that's what you're looking for there is always cryptokids from the NSA =)
[09:35] <cudos> http://www.nsa.gov/kids/
[09:36] <nsh> we're not on speaking terms atm
[09:36] <codos> seriously, cryptokids is a great site
[09:36] <cudos> i don't like the NSA, but i have to give them credit for cryptokids