Forum

[solved] Challenge "RSA Factoring Challenge: RSA-210"  

  By: admin on Feb. 7, 2012, 10:37 a.m.

This challenge descends from the RSA Laboratories contest to encourage research into the practical difficulty of factoring large integers of different length (between 330 and 2048 bit) and cracking RSA keys used in cryptography. This challenge is about factoring a number with 210 decimal digits.
Read more...

 Last edited by: admin on Oct. 31, 2021, 2:54 a.m., edited 2 times in total.

Re: Challenge  

  By: DarkFibre on Feb. 13, 2012, 2:54 a.m.

Is there any way to estimate how long these numbers take to factor? Are we talking computer-years? Months?

Re: Challenge  

  By: Javex on Feb. 13, 2012, 10:41 a.m.

Well this surely depends on the algorithms used, the computer you have and the efficiency of either your or someone else's implementation.

Additionally I am sure you will see a huge boost if you are using a graphics card (or multiple) or a set of FPGA (though this would be quite expensive for a private person).

Then you can test how fast your machine is (how many numbers it tests per sec) and calculate how many possible numbers there are.
RSA-210 has 696 bits and so p and q will roughly be of size 350 bits, so would have to evaluate all numbers that could make up this n and are in range of 350 bits (as this is far more likely). So if you go from say 340 bits to 360 bits you can calculate all possible outcomes and compare this number against how many tests you do per sec.

Keep in mind that to break a 56-bit DES on modern FPGA-arrays takes roughly one day to a week (depending on what you got), but since you will be using graphic cards most likely, it's hard to compare those numbers.

Just do a quick implementation by yourself and see what turns out to be.

If you ask for just a rough estimate my personal estimate would be in the scope of many months or years.

Re: Challenge  

  By: kataanglover1 on March 7, 2012, 6:53 a.m.

I'm currently working this one without use of a sieving field, servers, or any of the fancy stuff. I'm using a calculator at http://comptune.com/calc.php and a word doc. I've got it limited down to a range of odd number 105 digits in length and I'm slowly working till I get an answer out of the system. I thought about programming something to do it, but I figured I might as well solve it out by "hand" for fun. I've been at this for about 3 months on hand and i figure it will take about 4-5 months of 24/7 work to find a viable answer.

Re: Challenge  

  By: Veselovský on March 7, 2012, 3:04 p.m.

I've been at this for about 3 months on hand and i figure it will take about 4-5 months of 24/7 work to find a viable answer.

Do I understand it correctly, that your idea is to check by trial division every odd integer "n" in the interval 10^104<=n<10^105 whether it divides N?
If so, then my calculation revealed that even if you were able to check billions of numbers every nanosecond it still would take far far, unimaginable far more than the current age of the universe.

But maybe I misunderstood your idea.

For comparison, the best current estimate of the age of the universe is 4.336 x 10^17 seconds, i.e. 13.75 x 10^9 years.

Re: Challenge  

  By: kataanglover1 on March 23, 2012, 11:38 a.m.

Do I understand it correctly, that your idea is to check by trial division every odd integer "n" in the interval 10^104<=n<10^105 whether it divides N?

Except you don't have to check every odd integer. You only have to check against the primes.

Also, actually you don't have to start at 10^104 and go all the way up to 10^105, you only need to start at:

245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549104

and go to the square root of the RSA number. Since you already know that both numbers have to be 105 digits, this number outputs a quotient right at the limit of breaking 105 digits. All you have to do is know every prime number in the space between that number and the square root and then systematically divide it out.

It's still probably an impossibility with all these handicaps in place, but nobody has said that I can't do it. I've got the primes, all I lack is a program to systematically divide them. My programming skills have been going down the drain as of late. If anyone wants to help with that part, I'm up for any help that can be given.

Re: Challenge  

  By: Veselovský on March 23, 2012, 2:04 p.m.

All you have to do is know every prime number in the space between that number and the square root and then systematically divide it out.

Checking by trial division only the primes reduces the space of search very little compared to checking every odd number for such a big N. You still would need to live unimaginably more than the age of the universe to do this. There are much more efficient methods then trial division (whether you divide by all odd numbers or only by primes)

I've got the primes, all I lack is a program to systematically divide them.

In what sense you got the primes? Even if every atom in the universe stores one prime, there still would not be enough to store all primes in the search space.

Re: Challenge  

  By: kataanglover1 on March 23, 2012, 2:15 p.m.

Checking by trial division only the primes reduces the space of search very little compared to checking every odd number for such a big N. You still would need to live unimaginably more than the age of the universe to do this. There are much more efficient methods then trial division (whether you divide by all odd numbers or only by primes)

I've got the primes, all I lack is a program to systematically divide them.

In what sense you got the primes? Even if every atom in the universe stores one prime, there still would not be enough to store all primes in the search space.

I'm always one for efficiency! What do you have in mind? For now I've just been manually putting through a calculator with copypaste. Anything has to be better that that.

When I say I've got every prime, I mean I have the ability to find every prime in the search space without using extra resources on the order of a gpu cluter, aka a website with every viable prime in the search space listed and searchable.

Re: Challenge  

  By: Veselovský on March 23, 2012, 2:50 p.m.

http://en.wikipedia.org/wiki/Integer_factorization
Look at "Factoring algorithms".

For now I've just been manually putting through a calculator with copypaste.

:-) Do you think that RSA would be considered as secure if it were possible to break it manually? Surely you can do it manually for a small number… but I doubt you can do it for such a "small" semi-prime like this: 19093349095069286057. Can you? :-)

Re: Challenge  

  By: DarkFibre on Dec. 7, 2012, 4:56 p.m.

In case anyone is trying to get the 1000 points:

At 663 bits, RSA-200 is the largest RSA Challenge Number factored to date.
The sieving effort is estimated to have taken the equivalent of 55 years on a single 2.2 GHz Opteron CPU. The matrix step reportedly took about 3 months on a cluster of 80 2.2 GHz Opterons. The sieving began in late 2003 and the matrix step was completed in May 2005. P. Montgomery and H. te Riele at the CWI, and F. Bahr and his family also contributed to the project.

I think this makes them a lot harder than the average level II, and I would argue all of these should be made level X because barring some breakthrough in number theory or computing hardware there is no way we'll be able to break them. Unless maybe you work for Google or Amazon and can get your hands on a lot of spare cycles, that was a temptation for me to find work at Google…

Re: Challenge  

  By: fmoraes on Nov. 27, 2013, 4:47 p.m.

This number has already been factored and the results made public. I guess this should be changed into a Level X challenge. See http://en.wikipedia.org/wiki/RSA_numbers#RSA-210

Re: Challenge  

  By: Veselovský on Nov. 27, 2013, 6:34 p.m.

I could not resist to test it :-D
Was it factored in less than 52 hours??? I wonder what computational power was used…

Re: Challenge  

  By: aurelie on Nov. 28, 2013, 11:15 p.m.

This number has already been factored and the results made public. I guess this should be changed into a Level X challenge. See http://en.wikipedia.org/wiki/RSA_numbers#RSA-210

Thank you for hinting at this development! We are going to mark this in the same way as we've marked the RSA-704 challenge.

Re: [solved] Challenge  

  By: Javex on Dec. 1, 2013, 6:08 p.m.

We have set the date of solving back to the 26th of September where it was originally published here. Now you can enter the solution at will, but you will not get any points. Users that have already entered the solution have also automatically had their points removed.


Currently 22 guests and 0 members are online.
Powered by the CrypTool project
Contact | Privacy | Imprint
© 2009-2024 MysteryTwister team