Need help with a virus tales-from-the-crypt 2.0 - Msieve - Page 9

wombatman · 2016-01-04, 18:29

Your first number will be here (not factored fully yet): http://factordb.com/index.php?id=1100000000812652970

Your second will be here: http://factordb.com/index.php?id=1100000000812695855

It didn't work because that last large number (starting with 322...) is not fully factored yet.

Try YAFU first on both of the unfactored numbers (see the factordb links in this post).

chalsall · 2016-01-04, 19:21

Quote:

Originally Posted by wombatman

It didn't work because that last large number (starting with 322...) is not fully factored yet.

Just to put this out there...

This "ransomware" went easy on many.

The next time they'll get their code correct.

Don't click on links and download stuff. Never click "OK" when a program asks to escalate it's permissions.

Back up off-line regularly.

Trust no one.

wombatman · 2016-01-04, 19:31

Munoz, your first number is fully factored.

wombatman · 2016-01-05, 13:33

Munoz, second one is factored as well: http://factordb.com/index.php?id=1100000000812695855

jux · 2016-01-06, 01:33

Quote:

Originally Posted by wombatman

Munoz, second one is factored as well: http://factordb.com/index.php?id=1100000000812695855

I was just a few hours late...I did get a useful benchmark though. My factorization took somewhat longer than I expected - maybe it was because the two inputs were relatively unequal in size?

wombatman · 2016-01-06, 03:42

Probably so. For every 5 digit increase in terms of the size of the composite, the time to factor it roughly doubles, if I recall correctly.

jux · 2016-01-06, 04:49

Oh by input I meant prime factor

VBCurtis · 2016-01-06, 05:20

The input is the composite. The outputs are the primes. The time for the factorization to run (GNFS) is a function of input size, not output size. Even composites that break into 3 primes are not meaningfully longer jobs (though the sqrt step may take more iterations to recover all 3 factors). As The Wombat says, every 5 digits roughly doubles factorization effort for GNFS.

For an ECM run, the (expected) time to find a factor is a function of prime-factor size as well as composite size- but the size of the factor dominates the expected runtime.

Dubslow · 2016-01-06, 05:39

To summarize, some numbers are made up of entirely small factors, which can be found by ECM. If a number fails to be factored by ECM, then it's likely got "large" factors, and on average it's less time to switch to NFS, which while substantially longer than the ECM stage run by YAFU, it is roughly fixed duration (based on input composite size), unlike ECM, and is "guaranteed" to produce results, no matter the size of the factors, again unlike ECM.

So when factoring these teslacrypt key, the run time being "short" or "long" more or less boils down to if it was necessary to resort to NFS, i.e. if there is more than 1 large factor.

For the most recent key we are discussing, the small factors are found by simpler methods, then ECM was run on the resulting C147, which successfully knocked out the P20. Then there would be a C127 left, and after ECM tried and failed to find factors up to around ~39 digits, it gave up and ran NFS on the C127, resulting in the seemingly longer run time. The NFS of course split the C127 as P54*P74.

LaurV · 2016-01-06, 07:42

How about "a graph worth a thousand words"?

Click image for larger version

Name: factoring_algs.PNG
Views: 181
Size: 76.4 KB
ID: 13677

This I put together right now, during the lunch break, maybe it is not exactly... exact, but it will give to the beginners an idea of what's going on. The trial factoring is faster at first, because it has no "overhead", you just try every prime in order, and see if your number splits in small primes. With every digit you add, you have to test many more primes, so if you don't find a small factor fast, then the time becomes too long, exponentially long, and you have to switch to a more efficient algorithm. There are some algorithms out there which will find a factor if the factor has some special form, or property, or if the composite is not too big (like QS for example), and if you are lucky and the factor has such property, you still can find the factor "almost efficiently" (i.e. in sub-exponential time). This "based on luck" condition is symbolized by the dotted lines on the graphic. These algorithms have some "overhead" that you have to do, before (and during) you find/look for/ the factor, that is why they are not suitable to look for very small factors (where TF is faster, as not many primes to be tested). Also, they may or may not find the factors, depending on their properties, and your luck. For example, Pollard rho may find the factors if they are "close together", or P-1 may find the factors if they are "smooth", or ECM may find the factor if some magic animal called "group order" of it is enough smooth, and you were enough lucky to start with the right "seed". But all these algorithms work "between some limits", and when you increase the limits, to extend the size or the properties set of the factors you are searching, then the working time also goes up very fast. At the end, you unlucky poor bastard who didn't find a factor, are left with NFS and you have to crunch at it for days, or sometimes weeks (where other algorithms would take months/years, and TF would take centuries).

Dubslow · 2016-01-06, 08:05

I think you are looking for "overhead" rather than "overload"? In the sense of a minimum constant effort for any job, no matter how small (while for larger jobs the constant-size overhead becomes insignificant).

2016-01-04, 18:29	#89
wombatman I moo ablest echo power! May 2013 29·61 Posts	Your first number will be here (not factored fully yet): http://factordb.com/index.php?id=1100000000812652970 Your second will be here: http://factordb.com/index.php?id=1100000000812695855 It didn't work because that last large number (starting with 322...) is not fully factored yet. Try YAFU first on both of the unfactored numbers (see the factordb links in this post). Last fiddled with by wombatman on 2016-01-04 at 18:30

2016-01-04, 19:31	#91
wombatman I moo ablest echo power! May 2013 29×61 Posts	Munoz, your first number is fully factored. Last fiddled with by wombatman on 2016-01-04 at 19:45

2016-01-06, 05:20	#96
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	The input is the composite. The outputs are the primes. The time for the factorization to run (GNFS) is a function of input size, not output size. Even composites that break into 3 primes are not meaningfully longer jobs (though the sqrt step may take more iterations to recover all 3 factors). As The Wombat says, every 5 digits roughly doubles factorization effort for GNFS. For an ECM run, the (expected) time to find a factor is a function of prime-factor size as well as composite size- but the size of the factor dominates the expected runtime. Last fiddled with by VBCurtis on 2016-01-06 at 05:20

2016-01-06, 07:42	#98
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	How about "a graph worth a thousand words"? This I put together right now, during the lunch break, maybe it is not exactly... exact, but it will give to the beginners an idea of what's going on. The trial factoring is faster at first, because it has no "overhead", you just try every prime in order, and see if your number splits in small primes. With every digit you add, you have to test many more primes, so if you don't find a small factor fast, then the time becomes too long, exponentially long, and you have to switch to a more efficient algorithm. There are some algorithms out there which will find a factor if the factor has some special form, or property, or if the composite is not too big (like QS for example), and if you are lucky and the factor has such property, you still can find the factor "almost efficiently" (i.e. in sub-exponential time). This "based on luck" condition is symbolized by the dotted lines on the graphic. These algorithms have some "overhead" that you have to do, before (and during) you find/look for/ the factor, that is why they are not suitable to look for very small factors (where TF is faster, as not many primes to be tested). Also, they may or may not find the factors, depending on their properties, and your luck. For example, Pollard rho may find the factors if they are "close together", or P-1 may find the factors if they are "smooth", or ECM may find the factor if some magic animal called "group order" of it is enough smooth, and you were enough lucky to start with the right "seed". But all these algorithms work "between some limits", and when you increase the limits, to extend the size or the properties set of the factors you are searching, then the working time also goes up very fast. At the end, you unlucky poor bastard who didn't find a factor, are left with NFS and you have to crunch at it for days, or sometimes weeks (where other algorithms would take months/years, and TF would take centuries). Last fiddled with by Batalov on 2016-01-06 at 09:03 Reason: added a time scale to the graphic, for clarity; s/overload/overhead/g

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Using msieve with c	burrobert	Msieve	9	2012-10-26 22:46
Yes: Tales from Typographic Oceans	xilman	Lounge	79	2012-05-26 23:53
msieve help	em99010pepe	Msieve	23	2009-09-27 16:13
95% sure I have a virus, please help	jasong	Hardware	8	2006-11-19 22:57
virus hardware damage?	TTn	Hardware	18	2006-11-04 09:41

2016-01-05, 13:33	#92
wombatman I moo ablest echo power! May 2013 1769₁₀ Posts	Munoz, second one is factored as well: http://factordb.com/index.php?id=1100000000812695855

2016-01-06, 03:42	#94
wombatman I moo ablest echo power! May 2013 29·61 Posts	Probably so. For every 5 digit increase in terms of the size of the composite, the time to factor it roughly doubles, if I recall correctly.

2016-01-06, 04:49	#95
jux Aug 2015 2·3³ Posts	Oh by input I meant prime factor

2016-01-06, 05:39	#97
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	To summarize, some numbers are made up of entirely small factors, which can be found by ECM. If a number fails to be factored by ECM, then it's likely got "large" factors, and on average it's less time to switch to NFS, which while substantially longer than the ECM stage run by YAFU, it is roughly fixed duration (based on input composite size), unlike ECM, and is "guaranteed" to produce results, no matter the size of the factors, again unlike ECM. So when factoring these teslacrypt key, the run time being "short" or "long" more or less boils down to if it was necessary to resort to NFS, i.e. if there is more than 1 large factor. For the most recent key we are discussing, the small factors are found by simpler methods, then ECM was run on the resulting C147, which successfully knocked out the P20. Then there would be a C127 left, and after ECM tried and failed to find factors up to around ~39 digits, it gave up and ran NFS on the C127, resulting in the seemingly longer run time. The NFS of course split the C127 as P54*P74.

2016-01-06, 08:05	#99
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	I think you are looking for "overhead" rather than "overload"? In the sense of a minimum constant effort for any job, no matter how small (while for larger jobs the constant-size overhead becomes insignificant).