mersenneforum.org Stop Gpcode!
 Register FAQ Search Today's Posts Mark Forums Read

 2008-06-07, 16:16 #1 IronBits I ♥ BOINC!     Oct 2002 Glendale, AZ. (USA) 3×7×53 Posts Stop Gpcode! http://forum.kaspersky.com/index.php?showtopic=71652 Anyone up for a challenge and a possible new DC project ? So we're calling on you: crytographers, governmental and scientific institutions, antivirus companies, independent researchers…join with us to stop Gpcode. This is a unique project – uniting brain-power and resources out of ethical, rather than theoretical or malicious considerations. Here are the public keys used by the authors of Gpcode. The first is used for encryption in Windows XP and higher. Key type: RSA KeyExchange bitlength: 1024 RSA exponent: 00010001 RSA modulus: c0c21d693223d68fb573c5318982595799d2d295ed37da38be41ac8486ef900a ee78b4729668fc920ee15fe0b587d1b61894d1ee15f5793c18e2d2c8cc64b053 9e01d088e41e0eafd85055b6f55d232749ef48cfe6fe905011c197e4ac6498c0 e60567819eab1471cfa4f2f4a27e3275b62d4d1bf0c79c66546782b81e93f85d The second is used for encryption in versions of Windows prior to XP. Key type: RSA KeyExchange bitlength: 1024 RSA exponent: 00010001 RSA modulus: d6046ad6f2773df8dc98b4033a3205f21c44703da73d91631c6523fe73560724 7cc9a5e0f936ed75c75ac7ce5c6ef32fff996e94c01ed301289479d8d7d708b2 c030fb79d225a7e0be2a64e5e46e8336e03e0f6ced482939fc571514b8d7280a b5f4045106b7a4b7fa6bd586c8d26dafb14b3de71ca521432d6538526f308afb The RSA exponent for both keys is 0x10001 (65537). The information above is sufficient to start factoring the key. A specially created utility could be of great help in factoring.
 2008-06-07, 16:25 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 178016 Posts Why do we need to crack these two RSA keys? Can you please explain more about what you think Gpcode is and what is so dangerous about it. I found this link (and many other similar websites) that says Gpcode uses simple encryption that is easily reversible. If it is just a virus that encrypts some of one's files then it is a simple matter to reformat and restore from one's backup. Standard procedure.
 2008-06-07, 16:43 #3 mdettweiler A Sunny Moo     Aug 2007 USA (GMT-5) 3·2,083 Posts Hmmm.....both of those are 309 digit numbers, assuming my hexadecimal-to-decimal conversion worked right. The fastest known method for factoring numbers of this type would be GNFS--though, unfortunately, even a 180-digit GNFS factorization is considered huge with today's resources. (Initial prep-work for such an effort is currently being coordinated in the Factoring forum.) There's a slim chance that it could be done, with lots of resources and time, though the outlook may even be worse than that. (One of the gurus in the Factoring forum should be able to tell you whether it's even at all possible.) You might have better luck by hiring some hackers to find, and then break into, the virus writer's computer, and get the private key that way. If even one of these numbers was successfully factored, AFAIK it would set a new world record for the largest factorization completed to date!
2008-06-07, 16:44   #4
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

141518 Posts

Quote:
 Originally Posted by retina Why do we need to crack these two RSA keys? Can you please explain more about what you think Gpcode is and what is so dangerous about it. I found this link (and many other similar websites) that says Gpcode uses simple encryption that is easily reversible. If it is just a virus that encrypts some of one's files then it is a simple matter to reformat and restore from one's backup. Standard procedure.
According to the website IronBits linked to, this was a "dangerous new variant" of Gpcode. Presumably, the easily-reversible encryption would have been from an earlier version.

 2008-06-07, 16:53 #5 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 27·47 Posts There is no point in bothering to crack it. Once some malware takes over your data you can't trust it from then on, encrypted or not, it has been compromised. Even if, by some magic, the factors are found, by then the hacker will likely have tweaked his code to 2048bit, or put in a new key, or switched to ECC, or any number of other things to make the effort futile.
2008-06-07, 21:49   #6
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

3×112×29 Posts

Quote:
 Originally Posted by retina There is no point in bothering to crack it. Once some malware takes over your data you can't trust it from then on, encrypted or not, it has been compromised. Even if, by some magic, the factors are found, by then the hacker will likely have tweaked his code to 2048bit, or put in a new key, or switched to ECC, or any number of other things to make the effort futile.
Almost certainly true!

Anyway, factoring kilobit hard integers, whether by GNFS or any other known algorithm, is significantly beyond the current state of the art. It should just about be possible in around ten years time with massive effort --- assuming that the last 40 years of progress in integer factorization is a reasonable guide to the next ten. Do not bet too much money on that assumption!

Paul

2008-06-11, 17:48   #7
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by xilman Almost certainly true! Anyway, factoring kilobit hard integers, whether by GNFS or any other known algorithm, is significantly beyond the current state of the art. It should just about be possible in around ten years time with massive effort --- assuming that the last 40 years of progress in integer factorization is a reasonable guide to the next ten. Do not bet too much money on that assumption! Paul
The progress has come from two sources: new algorithms and faster/bigger
computers. We have not had a new algorithm in 20 years. Determining how
much more can be squeezed from NFS via faster/bigger computers is
problematic. Note that new algorithms alone have not helped. GNFS
could not have even been run on computers from (say) 1987. They did not
have enough memory.

And trying to predict the occurrence of a new algorithm is pure guesswork.

Hey Paul! How about a bet? Not too small, Not too big. Say $20 U.S.? I bet that a 1024-bit GNFS factorization will NOT be achieved within 10 years. 2008-06-11, 19:36 #8 xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 3×112×29 Posts Quote:  Originally Posted by R.D. Silverman The progress has come from two sources: new algorithms and faster/bigger computers. We have not had a new algorithm in 20 years. Determining how much more can be squeezed from NFS via faster/bigger computers is problematic. Note that new algorithms alone have not helped. GNFS could not have even been run on computers from (say) 1987. They did not have enough memory. And trying to predict the occurrence of a new algorithm is pure guesswork. Hey Paul! How about a bet? Not too small, Not too big. Say$20 U.S.? I bet that a 1024-bit GNFS factorization will NOT be achieved within 10 years.
You're on.

However, to hedge against currency fluctuations, I suggest that the amount be USD20 or GBP10, whichever is the greater at the time the bet becomes payable --- either 2018-06-12 00:00:01 UTC or when a factorization is announced, whichever is the earlier.

Note that at the current exchange rate, GBP10 is worth a few cents more than USD20.

Paul

 2008-06-11, 19:58 #9 Wacky     Jun 2003 The Texas Hill Country 32·112 Posts Or perhaps a more stable "currency" ... Like some good "single-malt" :)
2008-06-12, 07:37   #10
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

3·112·29 Posts

Quote:
 Originally Posted by R.D. Silverman Hey Paul! How about a bet? Not too small, Not too big. Say \$20 U.S.? I bet that a 1024-bit GNFS factorization will NOT be achieved within 10 years.

Same conditions except that there's no requirement that the factorization be performed by GNFS but, rather, is a demonstration of an algorithm and its implementation which is capable of factoring a hard 1024-bit (or greater) integer.

The quantum computer people, last time I heard (8 years ago) were also predicting "15-20 years" for kilobit factorizations by Shor's algorithm. We've no idea (at least, I've no idea) whether a new algorithm will turn up in the near future. If it does, or if the QC people hit their target, it may well be possible to perform a kilobit GNFS within ten years but not cost-effective to do so. Compare the situation with 512-bit factorizations. It's undoubtedly possible to do one with QS now but there's no real incentive to prove that claim.

Paul

2008-06-12, 13:17   #11
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by xilman How about a side bet? Same conditions except that there's no requirement that the factorization be performed by GNFS but, rather, is a demonstration of an algorithm and its implementation which is capable of factoring a hard 1024-bit (or greater) integer. The quantum computer people, last time I heard (8 years ago) were also predicting "15-20 years" for kilobit factorizations by Shor's algorithm. We've no idea (at least, I've no idea) whether a new algorithm will turn up in the near future. If it does, or if the QC people hit their target, it may well be possible to perform a kilobit GNFS within ten years but not cost-effective to do so. Compare the situation with 512-bit factorizations. It's undoubtedly possible to do one with QS now but there's no real incentive to prove that claim. Paul
You are on.

 Similar Threads Thread Thread Starter Forum Replies Last Post 137ben PrimeNet 5 2012-03-29 12:43 SaneMur Riesel Prime Search 4 2011-07-18 17:04 ThomRuley Msieve 20 2010-05-19 02:12 jocelynl 15k Search 2 2004-07-10 13:31 paulunderwood 3*2^n-1 Search 8 2004-05-19 07:10

All times are UTC. The time now is 06:19.

Thu Jan 28 06:19:17 UTC 2021 up 56 days, 2:30, 0 users, load averages: 2.48, 2.77, 2.64