rsa-640 challenge

[ValerieVonck]

Hi everyone!

This is a code snippet of the program I have written in hope to crack this number:

          BigInteger p = new BigInteger(SIZE, 10, new Random());
       // BigInteger q = new BigInteger(SIZE, 10, new Random());
       // BigInteger N = p.multiply(q);

         BigInteger z = challenge_number.remainder(p);

        if (z.equals(new String("0"))) {
          System.out.println(p);
          BigInteger q = challenge_number.divide(p);
          System.out.println(q);

First question, is the logic above correct?

if challenge_number modulo random number == 0 then random number is a factor

Second Question:

For the SIZE, I set this equal to 320.
Is this correct? Because the challenge number itself is a mere 193 bits long?
Wich SIZE should I choose?

Third question:
Is it possible to use this Java Class in a distributed approach?

Fourth question:
Can I make other optimisations to the code? (better checks on the numbers)?


Thnx & Regards,

Cedric

[R.D. Silverman]

Originally Posted by CedricVonck

Hi everyone!

This is a code snippet of the program I have written in hope to crack this number:

          BigInteger p = new BigInteger(SIZE, 10, new Random());
       // BigInteger q = new BigInteger(SIZE, 10, new Random());
       // BigInteger N = p.multiply(q);

         BigInteger z = challenge_number.remainder(p);

        if (z.equals(new String("0"))) {
          System.out.println(p);
          BigInteger q = challenge_number.divide(p);
          System.out.println(q);

First question, is the logic above correct?

if challenge_number modulo random number == 0 then random number is a factor

Second Question:

For the SIZE, I set this equal to 320.
Is this correct? Because the challenge number itself is a mere 193 bits long?
Wich SIZE should I choose?

Third question:
Is it possible to use this Java Class in a distributed approach?

Fourth question:
Can I make other optimisations to the code? (better checks on the numbers)?


Thnx & Regards,

Cedric

Among all the ways of trying to crack RSA-640, you have chosen one of
the worst. You will NEVER succeed in breaking it using trial division by
random integers.

The number itself is 640 bits. The factors are 320 bits. There are
approximately 10^94 primes less than 2^320. How long do you think
it will take you to try them? If you do trial division by all odd numbers,
rather than just primes, the number of trial divisors increases by a factor
of about 220.

Is there some point to this exercise????

[xilman]

Originally Posted by R.D. Silverman

Is there some point to this exercise????

I think the point is to see whether anyone will answer the questions as asked.


The approach is correct (from a quick glance at the code), it can be distributed over many machines and it can most certainly be optimized. For instance, we know that both factors of RSA-640 have the same number of bits and both are odd, so we should ensure that (by an extremely rapid single-bit setting operation) before embarking on a relatively expensive division. I'm assuming, possibly incorrectly, that the library routine generates a random number < 2^320.

There is one minor error in the interpretation of the challenge but not in the proposed method of solution. RSA-640 is only 193 digits long but it is 640 bits.

OTOH, Bob is correct in pointing out that the approach is essentially useless in practice.


Paul

[R.D. Silverman]

Originally Posted by xilman

I think the point is to see whether anyone will answer the questions as asked.


The approach is correct (from a quick glance at the code), it can be distributed over many machines and it can most certainly be optimized. For instance, we know that both factors of RSA-640 have the same number of bits and both are odd, so we should ensure that (by an extremely rapid single-bit setting operation) before embarking on a relatively expensive division. I'm assuming, possibly incorrectly, that the library routine generates a random number < 2^320.

There is one minor error in the interpretation of the challenge but not in the proposed method of solution. RSA-640 is only 193 digits long but it is 640 bits.

OTOH, Bob is correct in pointing out that the approach is essentially useless in practice.


Paul

Allow me to also point out that once one has done about 10^48 such
trial divisions, one will start to repeat divisions already done. (i.e.
get collisions). The number of such collisions rises rapidly as the algorithm
progresses until almost all divisions performed are repeats of earlier divisions.
There are (2^320 - 2^319)/2 odd 320 bit numbers. (~ 5 x 10^95)
Even if you do this number of divisions, you will miss out on testing
about 1/e ~ 36% of the numbers.

[ValerieVonck]

Originally Posted by R.D. Silverman

The number itself is 640 bits. The factors are 320 bits. There are
approximately 10^94 primes less than 2^320. How long do you think
it will take you to try them? If you do trial division by all odd numbers,
rather than just primes, the number of trial divisors increases by a factor
of about 220.

Is there some point to this exercise????

Imho, yes

1) See that I can program a "decent" java program
2)

I'm assuming, possibly incorrectly, that the library routine generates a random number < 2^320.


You assumed incorrectly. Random(SIZE,10,new Random()) generates an unique random number based on the timestamp (wich it takes as seed) with a certaintity of 100% that the number will of SIZE n (or n +/- 1)

3) What I have noticed when I generating factors, Java spits out only Integers that end in 1,3,7,9 ( I think also 5)

BTW, BigInteger is a Java class found in the (default) Math Package:
import java.lang.Math; (probably not needed (the import)).

Mr Silverman, maybe I am lucky in the first run, maybe never.. I will see

Regards & Tx.

[grandpascorpion]

You can be virtually certain you won't find it in your lifetime. It's a big waste of electricity. You have a better chance of winning the lottery 5 times over.

[akruppa]

CedricVonck, you will definitely never be lucky with a program like that. First off, what is the period of the Random() function? It is entirely possible that values start repeating after, say, 2^64 calls, so it is highly probable that the required divisor will not be among them. Second, please compute the cost of one trial division attempt (electricity and computer devaluation) and the average gain (prize money times probability per candidate divisor). How do they compare? How does this ratio compare to, say, playing the lottery?

Alex

[R.D. Silverman]

Originally Posted by CedricVonck

Imho, yes


You assumed incorrectly. Random(SIZE,10,new Random()) generates an unique random number based on the timestamp (wich it takes as seed) with a certaintity of 100% that the number will of SIZE n (or n +/- 1)


Regards & Tx.

If you are simply learning Java, then go ahead. However, as a
computational exercise it is a total waste of time, your stubborn
refusal to accept this notwithstanding.

Why not do something that has a chance of succeeding? For example,
find integers a,b, x,y with x,y > 1 such that a^x - b^y = 6. or 14 or 50??
(there are no known solutions)


I assumed nothing incorrectly. Count the number of odd 320 bit integers.
I also suggest that you investigate both the period of the RNG, as well
as the *number of different seeds*. "Unique random number" is meaningless
gibberish. The seed will have some finite length. Given a clock resolution
of (say) 10^9/sec, and starting at 0, you have approximately 6 x 10^19
(2005 x 31 million sec/yr x 10^9) different seeds. This is a mere 76
orders of magnitude short of what you need.

I ask the more general audience:

(1) Why can't people do simple arithmetic?
(2) Why do people stubbornly persist with something that is unlikely to
succeed in the lifetime of the universe? Especially when an expert suggests
simple alternatives with far greater chance of success.

You are beginning to sound like a crank, Mr. Vonck.

[ewmayer]

Baby steps, baby steps...

Cedric, why don't you try factoring a really small number using your code first? Say this one, which is roughly one-tenth the size:

46346456565690422177

Tell us how long your code takes for that. Then, once you're warmed up, try these:

128-bit: 100932962400917909775165520235579282579

192-bit: 1269978474870826099469200719269667649673577514427443201007

256-bit: 57947655096138611771015791829549915741168624880634687983385128259250717742871

320-bit: 332510945314407585369353816108066418700825249657921338102510381124554301151561291698818402774601

Once you've finished the 320-bit composite, we can talk about optimizing your Java applet to tackle the 640-bit.

[VJS]

Well I wouldn't be so hard on CedricVonck,

People do things not nessarily b/c they understand them, especially when it comes to us internet geeks and number theory.

People do things especially DC, b/c they don't understand and both hope to learn something in the process and get the warm fuzzy feelings. Silverman you have to understand that this isn't anyones job nor does solving a mathematical theory help them in their daily lives.

Question for you: what % of people participating in Math projects do you think ... Understand the mod function? How about taken an into number theory course? do multi-variable calc? Single Variable calc? Lets go even further and say "define composite"?

I do agree with you however that the RSA challenges are a waste of computing power. Most of these challenges can be solved with simple stats.

I.e. It would take x computers y years to compute z itterations with program ??? to crack the key.

Who really cares what the two factors are in the long run, but this could be said about alot of the projects we are doing.

CedricVonck, really, don't start please.

I'd also agree with akruppa, if you simply shut off the machine instead of running RSA you would "win" more money.

Now if someone spent their time working on a code or ??? which would complete the RSA-640 in <1 month on one machine. That would be something, not by luck but 100% postive solution within a month. Cedric you have a ways to go with your code according to the experts here.

[VJS]

Also why don't you have a look at this site...

http://www.frenchfries.net/paul/factoring/theory/