Factorization Project

[elrosti]

Hi All. Sorry for my english, I speak spanish.

I was reading your forum for the last week in a daily basis and learning a lot about this new (for me) world of "Factorization ", I'm a Software Programmer and I'm working in a project and as a part of this project I need to break a 512 RSA key.

I run a polinomial sarch for couple of days and I found this plinomial. I think that is a good one because I read that others with a 155 digits numbers found polinomials with a worst Murphy Score.

n: 9330647851749976394640049245988341084251457066477254064387678593246658843721286080407870681103449135685712977746375526208381757210885555288474534773885843
# norm 7.208858e-015 alpha -6.647080 e 3.636e-012 rroots 5
skew: 20221494.43
c0: 127448258002115900251200751741968833225
c1: 195288306526916322821130677351970
c2: -11339011323431739879025280
c3: -2189856519884767486
c4: 26236783015
c5: 876
Y0: -1605023981925215696711560719284
Y1: 7801575093334627
rlim: 25000000
alim: 25000000
lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
rlambda: 2.5
alambda: 2.5

I start sieving with a Q of 20M, I don't know exactly why, I just read that is a good start in this forum, I wish to know a little more about that, I don't have a big background in mathematic, but I can learn.

I read that here are people with big hardware resourses for sieving, so if anyone want to help me, I'd really appreciate it. I mostly want to learn, this project (The whole project I'm working on, not the RSA key break) is only for learning and experiment purposes, there is no real "gain" or something.

Cheers.

[debrouxl]

In the last week, I factored a 512-bit RSA key, with up to 42 hyperthreads on 8 computers with 7 different processor types.
The sieving went from Thursday evening to Sunday morning, and the post-processing from Sunday mid-day to Monday afternoon. I could have made the post-processing somewhat faster with another computer, but bandwidth constraints got in the way.

This shows (unsurprisingly) that factoring a 512-bit RSA key has become quite a bit easier since 2009, when RSALS was set up to speed up the factorization of a dozen keys (with a quorum of 2 on WUs, so we effectively wasted half of our of CPU power).


If you can put 32 recent cores (running 64-bit Linux, that's where ggnfs is the most efficient) to the task of sieving, it will be done pretty quickly :)


A polynomial with E=3.636e-12 is indeed decent for your number.

[elrosti]

Thanks for your comments debrouxl. I read a lot of forums post with your interventions and learn a lot from you. I read about RSALS and I liked so much the story about the Texas Instruments signing keys.

I don't have hardware resources, only a Core i5 notebook :(, so I'm sieving slowly, I think that I can continue working in other parts of my project while is sieving but I'm very intrigued if I will have succes in the search of the factors.

I read that I need at least 60M raw relations, is this ok? I'm obtaining something like 2X the number of Q proseced ¿Is that a good relation?

I don't read a lot about the post procesing fase, ¿Can you give some advises?. ¿Can it be paralelized?

[henryzz]

Originally Posted by elrosti

Thanks for your comments debrouxl. I read a lot of forums post with your interventions and learn a lot from you. I read about RSALS and I liked so much the story about the Texas Instruments signing keys.

I don't have hardware resources, only a Core i5 notebook :(, so I'm sieving slowly, I think that I can continue working in other parts of my project while is sieving but I'm very intrigued if I will have succes in the search of the factors.

I read that I need at least 60M raw relations, is this ok? I'm obtaining something like 2X the number of Q proseced ¿Is that a good relation?

I don't read a lot about the post procesing fase, ¿Can you give some advises?. ¿Can it be paralelized?

Postprocessing shouldn't take a huge amount of time for your job. A few hours should be all. You might need >2GB of memory. I can't remember how much is needed for this sort of job. More than 4GB shouldn't be necessary.

2X the number of Q processed is a good ratio.

[elrosti]

thanks henryzz, I have 4 GB RAM so I think that should be suficient. I'm runing multiple GGNFS threads with diferent jobs files in diferent folders for paralelize it, I don't know if there is a better way of do that.

[henryzz]

Originally Posted by elrosti

thanks henryzz, I have 4 GB RAM so I think that should be suficient. I'm runing multiple GGNFS threads with diferent jobs files in diferent folders for paralelize it, I don't know if there is a better way of do that.

Assuming you are sieving different Qs with the different threads that is pretty much the best way to do it. Something worth mentioning is that the sievers are much faster on 64-bit Linux due to better asm than windows.

[debrouxl]

For jobs of this size, post-processing doesn't need parallelization, indeed
On a C154-C155, with the 14e siever, 1.7-2 relations per q value at the bottom of the range are the expected yield; it will decrease as you move upwards, you'll probably have to sieve a range of 35-40M q values.
On your computer, a month of wall clock time should be enough for sieving, assuming 64-bit Linux siever and assuming 2 cores / 4 hyperthreads for a mobile Core i5.


Note that I didn't create RSALS, but I've fed it almost all of its numbers over three years, and I've served as its de-facto public face.

[elrosti]

Thanks for your coments. So I think this will be a large task...

[elrosti]

I don't know howt to reconstruct my private key file after obtaining my factors ¿ There is a tool that helpme in this task?.

Cheers.

[Dubslow]

Try going through the ssh-keygen source.

http://www.openssh.org/portable.html#http

[elrosti]

HI Again.

Thanks for the link Dubslow.

Now I'm having a problem, I'm runing this comand

..\msieve -v -s todasrelaciones.dat -i rsa100.n -nf rsa100.fb -nc1 -v

And getting this error, I don't know what I'm doing wrong.

Mon Dec 10 23:00:19 2012  Msieve v. 1.50 (SVN 708)
Mon Dec 10 23:00:19 2012  random seeds: 340fbce0 990c5b54
Mon Dec 10 23:00:19 2012  factoring 9330647851749976394640049245988341084251457066477254064387678593246658843721286080407870681103449135685712977746375526208381757210885555288474534773885843 (154 digits)
Mon Dec 10 23:00:20 2012  searching for 15-digit factors
Mon Dec 10 23:00:21 2012  commencing number field sieve (154-digit input)
Mon Dec 10 23:00:21 2012  warning: factor base file uninitialized
Mon Dec 10 23:00:21 2012  elapsed time 00:00:02

Thanks in advance.