mersenneforum.org A strange RSA key
 Register FAQ Search Today's Posts Mark Forums Read

 2009-10-29, 06:50 #1 siew   Oct 2009 32·7 Posts A strange RSA key Finally С154 job is done: 78M relations collected, from 0 to 35M 39M Unique relations Three prp found, prp24,prp96,prp34 It tooks about a week totally. 1 np 4 days sieving 4 Dual Xeons 1 day matrix solving 12 hours square Last fiddled with by siew on 2009-10-29 at 07:27
2009-10-29, 08:06   #2
10metreh

Nov 2008

2·33·43 Posts

Quote:
 Originally Posted by siew Finally С154 job is done: 78M relations collected, from 0 to 35M 39M Unique relations Three prp found, prp24,prp96,prp34 It tooks about a week totally. 1 np 4 days sieving 4 Dual Xeons 1 day matrix solving 12 hours square
Oops, it wasn't a proper RSA key if it had p24 and p34 factors...

If it isn't a proper RSA key, you must do ECM first. Then you would have probably found the p24 in 1-2 minutes, and the p34 in 1-2 hours.

2009-10-29, 08:07   #3
BigBrother

Feb 2005
The Netherlands

2×109 Posts

Quote:
 Originally Posted by siew Finally С154 job is done: 78M relations collected, from 0 to 35M 39M Unique relations Three prp found, prp24,prp96,prp34 It tooks about a week totally. 1 np 4 days sieving 4 Dual Xeons 1 day matrix solving 12 hours square
prp24 and prp34? Didn't you do some ECM before sieving? Could have save you about a week...

Last fiddled with by BigBrother on 2009-10-29 at 08:07

2009-10-29, 08:09   #4
lfm

Jul 2006
Calgary

52·17 Posts

Quote:
 Originally Posted by 10metreh Oops, it wasn't a proper RSA key if it had p24 and p34 factors... If it isn't a proper RSA key, you must do ECM first. Then you would have probably found the p24 in 1-2 minutes, and the p34 in 1-2 hours.
Do you think the key generator might have somehow mistakenly considered p24 times p34 as a probable prime?

2009-10-29, 08:13   #5
10metreh

Nov 2008

232210 Posts

Quote:
 Originally Posted by lfm Do you think the key generator might have somehow mistakenly considered p24 times p34 as a probable prime?
No, the primes in RSA keys are usually very similar in size, so I would have expected something like p77 * p77.

Earlier in the thread, siew wrote:
Quote:
 Originally Posted by siew Yes, you right, thats RSA key, which used for signing some MCU code i want to change.
Lie detector output: LIE, or else VERY BAD KEY GENERATOR.

Actually, I'm surprised I didn't catch that as a lie early on: if it is a real RSA key used for signing real code, then it has to be better than 512 bits nowadays.

Last fiddled with by 10metreh on 2009-10-29 at 08:14

 2009-10-29, 08:48 #6 siew   Oct 2009 32×7 Posts Please, that was my first big factorization, so what do you mean "ECM before"?
2009-10-29, 09:01   #7
lfm

Jul 2006
Calgary

42510 Posts

Quote:
 Originally Posted by siew Please, that was my first big factorization, so what do you mean "ECM before"?
try the eliptic curve method of factoring before you try the full number field fqactoring. Its a different program.

 2009-10-29, 09:37 #8 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×29×109 Posts The problem is that, if you know the key is an RSA number, 'ECM before' is extremely bad advice; it's absolutely guaranteed to waste time. The crucial question: does the private key you obtain from the factorisation allow you to sign code that works? If so then the encryption system is very peculiar; if not, then maybe the number's in the wrong byte order or has an implicit leading bit or something?
 2009-10-29, 12:08 #9 jasonp Tribal Bullet     Oct 2004 3·1,163 Posts fivemack is right, the most likely explanation is that the string of bits you think is an RSA key needs to be byte-swapped or something.
2009-10-29, 12:15   #10
Andi47

Oct 2004
Austria

7·353 Posts

Quote:
 Originally Posted by fivemack The problem is that, if you know the key is an RSA number, 'ECM before' is extremely bad advice; it's absolutely guaranteed to waste time.
Hmmm... maybe one should spend a few hours (not more!) of ECM and P-1 even on RSA keys to see if things like that have happened?

 2009-10-29, 13:19 #11 siew   Oct 2009 32×7 Posts Will try to ECM too :-) tanx. And what about 3 prp ? It it possible , that original key generator used 3 primes, not 2 ? p,q ?

 Similar Threads Thread Thread Starter Forum Replies Last Post bayanne Software 6 2016-04-06 04:33 schickel FactorDB 7 2012-02-02 00:10 3.14159 Miscellaneous Math 7 2010-06-01 01:29 MatWur-S530113 GMP-ECM 2 2007-11-19 00:01 HiddenWarrior Software 5 2005-08-22 08:34

All times are UTC. The time now is 18:57.

Tue Oct 27 18:57:04 UTC 2020 up 47 days, 16:08, 1 user, load averages: 2.15, 2.23, 2.17