mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-04-29, 19:44   #23
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Batalov View Post
What R.D.Silverman may have meant was that many keys in real life are broken by other than math means of: social engineering, rubber hose cryptanalysis (and don't discard such methods as analyzing people's garbage, unshredded notes, statements and such).

Also, here's xkcd's contribution to real-life security. Priceless.
Bingo.
R.D. Silverman is offline   Reply With Quote
Old 2010-04-29, 19:51   #24
Romulas
 
Apr 2010

1910 Posts
Default

Quote:
Originally Posted by Batalov View Post
What R.D.Silverman may have meant was that many keys in real life are broken by other than math means of: social engineering, rubber hose cryptanalysis (and don't discard such methods as analyzing people's garbage, unshredded notes, statements and such).

Also, here's xkcd's contribution to real-life security. Priceless.
Oh, I see. No, she won't mention it, but that too is quietly encouraged. This is like an all-out battle to give us a feel for what cryptology entails.
Romulas is offline   Reply With Quote
Old 2010-04-30, 08:41   #25
chris2be8
 
chris2be8's Avatar
 
Sep 2009

35508 Posts
Default

Quote:
Originally Posted by fivemack View Post
Has your class included anything on how to generate cryptographic-quality random numbers, and do your classmates have access to good-quality implementations of good RNGs?

If not, you might have a lot more luck poking around that area with a crowbar than trying to go in through the front door with a GNFS-powered battering-ram.
To generate your own key look at ssh-keygen (you will need to modify the source to let you generate a key less than 768 bits). That should generate one immune to everything except a GNFS-powered battering-ram.

Chris K
chris2be8 is offline   Reply With Quote
Old 2010-04-30, 10:20   #26
debrouxl
 
debrouxl's Avatar
 
Sep 2009

977 Posts
Default

The RSALS grid can definitely sieve GNFS tasks of difficulty 159: we've already sieved two GNFS C160s (XYYXF), two C163s (current XYYXF record, and a participation in the team sieving of a C163 in Aliquot sequence 4788) and a C165 (20009_241, current near-repdigit-related record).

Using GGNFS siever 14e, RSALS is helping factoring in a range of difficulty limited by:
* on the "easy" side, integers reasonably sievable by a handful of cores;
* on the "hard" side, integers on which the 14e siever produces unreasonably low yields (difficulty between 165 and 170 for GNFS, about 250 for SNFS). Those are the territory of 15e and higher sievers, used by NFS@Home and other organizations. We're not ruling out deploying 15e for a once-in-a-while usage, but we have not deployed it so far.


But as jasonp wrote, factoring a C159 by GNFS in one week is very hard:
Quote:
Finishing both the sieving and postprocessing together in a week or less is a very tall order; just the postprocessing will take almost a week on a fast machine with 4GB of memory.
Let's be optimistic and reserve:
* 1 day for polynomial selection on several leading-edge CUDA-capable GPUs;
* 4 days for post-processing on a leading-edge 2 x quad-core i7 featuring fast RAM handled in quad-channel mode.
That leaves two days for sieving a C159... and the current power of the RSALS grid is too short to make sieving fit in that time budget, by a factor of at least two or even three.


=> Wesley/Romulas, even if factoring one of your schoolmates' short RSA keys in a week would be an excellent display of the power of grids, I'm afraid that RSALS can't help on the challenge of factoring a C159 in one week. It's too hard of a challenge.
(if you were talking about 512-bit RSA keys, we might consider... after all, the project was born to sieve keys of such length, and we've fully sieved 12 of them and partially sieved a 13th one in about a month)
debrouxl is offline   Reply With Quote
Old 2010-04-30, 14:03   #27
Romulas
 
Apr 2010

1910 Posts
Default

Quote:
Originally Posted by debrouxl View Post
The RSALS grid can definitely sieve GNFS tasks of difficulty 159: we've already sieved two GNFS C160s (XYYXF), two C163s (current XYYXF record, and a participation in the team sieving of a C163 in Aliquot sequence 4788) and a C165 (20009_241, current near-repdigit-related record).

Using GGNFS siever 14e, RSALS is helping factoring in a range of difficulty limited by:
* on the "easy" side, integers reasonably sievable by a handful of cores;
* on the "hard" side, integers on which the 14e siever produces unreasonably low yields (difficulty between 165 and 170 for GNFS, about 250 for SNFS). Those are the territory of 15e and higher sievers, used by NFS@Home and other organizations. We're not ruling out deploying 15e for a once-in-a-while usage, but we have not deployed it so far.


But as jasonp wrote, factoring a C159 by GNFS in one week is very hard:


Let's be optimistic and reserve:
* 1 day for polynomial selection on several leading-edge CUDA-capable GPUs;
* 4 days for post-processing on a leading-edge 2 x quad-core i7 featuring fast RAM handled in quad-channel mode.
That leaves two days for sieving a C159... and the current power of the RSALS grid is too short to make sieving fit in that time budget, by a factor of at least two or even three.


=> Wesley/Romulas, even if factoring one of your schoolmates' short RSA keys in a week would be an excellent display of the power of grids, I'm afraid that RSALS can't help on the challenge of factoring a C159 in one week. It's too hard of a challenge.
(if you were talking about 512-bit RSA keys, we might consider... after all, the project was born to sieve keys of such length, and we've fully sieved 12 of them and partially sieved a 13th one in about a month)
Well, it was worth a shot. Thanks everyone for the info! This is awesome!
Romulas is offline   Reply With Quote
Old 2010-04-30, 15:19   #28
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Romulas View Post
Well, it was worth a shot. Thanks everyone for the info! This is awesome!
I assume that the code you wrote to generate your keys is on one of
your school's computer systems. Other students might have their code
there as well.

STEAL IT. If they used a simple PRNG you should be able to just brute
force their RNG. If it is (say) a 32-bit RNG, you can try all possible
seeds very quickly. Now you can factor their RSA public modulus by
trial division.
R.D. Silverman is offline   Reply With Quote
Old 2010-05-04, 00:53   #29
Romulas
 
Apr 2010

19 Posts
Default

Well, the keys are posted.

Adam's modulus R is not a multiple of two large primes. It looks like an R that came from an Elliptic Curve key.

Oh, by the way, R is the modulus, n is the public exponent. The notation is different from RSA, since this is LUC RSA.

Last fiddled with by Romulas on 2010-05-04 at 01:11
Romulas is offline   Reply With Quote
Old 2010-06-04, 23:10   #30
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13×41 Posts
Default

so have you tried ecm or fermat's method on them yet?
Joshua2 is offline   Reply With Quote
Old 2010-06-04, 23:37   #31
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

139710 Posts
Default

Quote:
Originally Posted by Romulas View Post
Well, the keys are posted.

My guess is that Adam Curran failed on the exam. Look at his key!

Last fiddled with by R. Gerbicz on 2010-06-04 at 23:37
R. Gerbicz is offline   Reply With Quote
Old 2010-06-06, 04:25   #32
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13·41 Posts
Default

his n following, is it weak?
P1 = 2
P1 = 2
P1 = 3
P4 = 1381
P4 = 1787
PRP5 = 40819
PRP5 = 62653

Last fiddled with by Joshua2 on 2010-06-06 at 04:28
Joshua2 is offline   Reply With Quote
Old 2010-06-06, 15:08   #33
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3,347 Posts
Default

I thought it was due to messing up the part about using the product of two 81 digit primes.

His R value is 23 * 34 * 13 * 19 * 31 * 53 * 431 * 228341 * c146

The fact that R was even, looked a bit odd. . .
EdH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factoring 90 512-bit RSA Keys in 3 minutes Mini-Geek Lounge 1 2015-03-17 17:27
openssl weak keys Unregistered Information & Answers 1 2011-10-07 22:14
Asymetric keys JohnFullspeed Factoring 3 2011-07-23 12:24
Assignment keys NBtarheel_33 PrimeNet 17 2010-02-18 04:38
Where I find the best program to it factor keys? I use AMD. chrow Factoring 5 2004-02-19 10:15

All times are UTC. The time now is 07:54.

Sun Sep 27 07:54:25 UTC 2020 up 17 days, 5:05, 0 users, load averages: 0.97, 1.19, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.