mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-10-29, 06:50   #1
siew
 
Oct 2009

32·7 Posts
Default 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
siew is offline   Reply With Quote
Old 2009-10-29, 08:06   #2
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by siew View Post
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.
10metreh is offline   Reply With Quote
Old 2009-10-29, 08:07   #3
BigBrother
 
Feb 2005
The Netherlands

2×109 Posts
Default

Quote:
Originally Posted by siew View Post
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
BigBrother is offline   Reply With Quote
Old 2009-10-29, 08:09   #4
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52·17 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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?
lfm is offline   Reply With Quote
Old 2009-10-29, 08:13   #5
10metreh
 
10metreh's Avatar
 
Nov 2008

232210 Posts
Default

Quote:
Originally Posted by lfm View Post
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
10metreh is offline   Reply With Quote
Old 2009-10-29, 08:48   #6
siew
 
Oct 2009

32×7 Posts
Default

Please, that was my first big factorization, so what do you mean "ECM before"?
siew is offline   Reply With Quote
Old 2009-10-29, 09:01   #7
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

42510 Posts
Default

Quote:
Originally Posted by siew View Post
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.
lfm is offline   Reply With Quote
Old 2009-10-29, 09:37   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×29×109 Posts
Default

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?
fivemack is offline   Reply With Quote
Old 2009-10-29, 12:08   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2009-10-29, 12:15   #10
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

7·353 Posts
Default

Quote:
Originally Posted by fivemack View Post
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?
Andi47 is offline   Reply With Quote
Old 2009-10-29, 13:19   #11
siew
 
Oct 2009

32×7 Posts
Default

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 ?
siew is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Something strange ... bayanne Software 6 2016-04-06 04:33
Something *really* strange schickel FactorDB 7 2012-02-02 00:10
A strange applet: 3.14159 Miscellaneous Math 7 2010-06-01 01:29
Strange bug with GMP-ECM MatWur-S530113 GMP-ECM 2 2007-11-19 00:01
Strange bug 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

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.